package gudusoft.gsqlparser.lineage.v2.json;

import gudusoft.gsqlparser.lineage.v2.SqllrException;

import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.charset.CharacterCodingException;
import java.nio.charset.CodingErrorAction;
import java.nio.charset.StandardCharsets;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

/**
 * {@code canonical-json-v1} of SQL-LR ({@code lineage-spec/algorithms/canonical-json-v1.md}): the strict
 * reader of Section 3, the RFC 8785 writer restricted to integers of Section 4, and the array ordering of
 * the {@code DOCUMENT} mode (Sections 5 and 6).
 *
 * <p>A JSON value is one of these Java objects: {@code Map<String, Object>} (members in input order),
 * {@code List<Object>}, {@code String}, {@code Long}, {@code Boolean}, or {@code null} for JSON null. The
 * reader returns exactly these types; the writer also accepts {@code Integer}, {@code Short}, {@code Byte}
 * and {@code BigInteger} within the integer range.</p>
 *
 * <p>The reference implementation is {@code lineage-spec/algorithms/reference/sqllr_ids.py}
 * ({@code parse_json_strict}, {@code jcs_bytes}, {@code canonicalize_document}). Where the two can report
 * different codes for one input, this class reports the code the reference reports: the parse runs left to
 * right, a duplicate member name is detected when its object closes, and an unpaired surrogate is reported
 * only after the whole text parsed.</p>
 *
 * <p>Every traversal uses an explicit stack, so nesting is limited by {@link #MAX_DEPTH} alone, not by the
 * thread's stack size. A value nested deeper is {@code SCHEMA_INVALID_JSON} for the reader, the writer and
 * the canonicalizer alike, so the writer never produces bytes the reader rejects. (The reference raises an
 * uncaught {@code RecursionError} from about 500 levels on; no fixture comes near either limit.)</p>
 *
 * @since 4.2.17
 */
public final class CanonicalJson {

    /** The two modes of Section 2, and the {@code DOCUMENT} mode that rejects unregistered arrays. */
    public enum Mode {
        /** Every array keeps its order. */
        JCS,
        /** Arrays are ordered as registered; an unregistered array keeps its order. */
        DOCUMENT,
        /** As {@link #DOCUMENT}, and an unregistered array outside open content is {@code SCHEMA_VIOLATION}. */
        DOCUMENT_STRICT
    }

    /** 2^53 - 1: the largest integer the format admits (Section 3, rule 7). */
    public static final long MAX_SAFE_INTEGER = 9007199254740991L;

    /**
     * The most objects and arrays that may enclose one another; the outermost container is level 1. A
     * deeper value is {@code SCHEMA_INVALID_JSON}.
     */
    public static final int MAX_DEPTH = 1000;

    public static final String SCHEMA_INVALID_JSON = "SCHEMA_INVALID_JSON";
    public static final String SCHEMA_DUPLICATE_KEY = "SCHEMA_DUPLICATE_KEY";
    public static final String SCHEMA_NON_INTEGER_NUMBER = "SCHEMA_NON_INTEGER_NUMBER";
    public static final String SCHEMA_VIOLATION = "SCHEMA_VIOLATION";
    public static final String SEMANTIC_ARRAY_KIND_VIOLATION = "SEMANTIC_ARRAY_KIND_VIOLATION";

    private static final BigInteger MAX_BIG = BigInteger.valueOf(MAX_SAFE_INTEGER);

    private CanonicalJson() {
    }

    // ---------------------------------------------------------------------------------------------
    // Reading (Section 3)
    // ---------------------------------------------------------------------------------------------

    /**
     * Parses JSON bytes under the eight input rules of Section 3.
     *
     * @throws SqllrException {@code SCHEMA_INVALID_JSON}, {@code SCHEMA_DUPLICATE_KEY} or
     *                        {@code SCHEMA_NON_INTEGER_NUMBER}
     */
    public static Object parse(byte[] data) {
        if (data.length >= 3 && (data[0] & 0xff) == 0xef && (data[1] & 0xff) == 0xbb && (data[2] & 0xff) == 0xbf) {
            throw new SqllrException(SCHEMA_INVALID_JSON, "a byte order mark is not allowed");
        }
        String text;
        try {
            text = StandardCharsets.UTF_8.newDecoder()
                    .onMalformedInput(CodingErrorAction.REPORT)
                    .onUnmappableCharacter(CodingErrorAction.REPORT)
                    .decode(ByteBuffer.wrap(data)).toString();
        } catch (CharacterCodingException e) {
            throw new SqllrException(SCHEMA_INVALID_JSON, "input is not well-formed UTF-8");
        }
        return new Parser(text).parseText();
    }

    /** The canonical bytes of JSON input bytes in the given mode. */
    public static byte[] canonicalBytes(byte[] data, Mode mode) {
        Object value = parse(data);
        if (mode == Mode.JCS) {
            return jcsBytes(value);
        }
        return jcsBytes(canonicalizeDocument(value, mode == Mode.DOCUMENT_STRICT, ArrayRegistry.standard(), null));
    }

    // ---------------------------------------------------------------------------------------------
    // Writing (Section 4)
    // ---------------------------------------------------------------------------------------------

    /** The RFC 8785 bytes of a value, every array in its current order ({@code JCS} mode). */
    public static byte[] jcsBytes(Object value) {
        return jcsText(value).getBytes(StandardCharsets.UTF_8);
    }

    /**
     * The RFC 8785 text of a value, every array in its current order. Its UTF-8 encoding is
     * {@link #jcsBytes(Object)}.
     */
    public static String jcsText(Object value) {
        StringBuilder out = new StringBuilder();
        if (!isContainer(value)) {
            writeScalar(value, out);
            return out.toString();
        }
        Deque<WriteFrame> stack = new ArrayDeque<WriteFrame>();
        stack.push(WriteFrame.open(value, out, 1));
        while (!stack.isEmpty()) {
            WriteFrame frame = stack.peek();
            if (!frame.hasNext()) {
                out.append(frame.close);
                stack.pop();
                continue;
            }
            Object child = frame.next(out);
            if (isContainer(child)) {
                stack.push(WriteFrame.open(child, out, stack.size() + 1));
            } else {
                writeScalar(child, out);
            }
        }
        return out.toString();
    }

    /** {@code jcsBytes(canonicalizeDocument(value, true))}: the canonical wire form of a lineage document. */
    public static byte[] documentBytes(Object value) {
        return jcsBytes(canonicalizeDocument(value, true));
    }

    private static boolean isContainer(Object value) {
        return value instanceof Map<?, ?> || value instanceof List<?>;
    }

    /** One object or array being written: its members in JCS order, or its elements in order. */
    private static final class WriteFrame {
        final char close;
        private final Map<?, ?> map;
        private final List<String> names;
        private final Iterator<?> elements;
        private int index;

        private WriteFrame(char close, Map<?, ?> map, List<String> names, Iterator<?> elements) {
            this.close = close;
            this.map = map;
            this.names = names;
            this.elements = elements;
        }

        static WriteFrame open(Object value, StringBuilder out, int level) {
            if (level > MAX_DEPTH) {
                throw new SqllrException(SCHEMA_INVALID_JSON, "nesting deeper than " + MAX_DEPTH);
            }
            if (value instanceof Map<?, ?>) {
                Map<?, ?> map = (Map<?, ?>) value;
                List<String> names = new ArrayList<String>(map.size());
                for (Object name : map.keySet()) {
                    if (!(name instanceof String)) {
                        throw new IllegalArgumentException("JSON member name is not a String: " + name);
                    }
                    names.add((String) name);
                }
                // String.compareTo compares UTF-16 code units, unsigned: RFC 8785, Section 3.2.3.
                Collections.sort(names);
                out.append('{');
                return new WriteFrame('}', map, names, null);
            }
            out.append('[');
            return new WriteFrame(']', null, null, ((List<?>) value).iterator());
        }

        boolean hasNext() {
            return map != null ? index < names.size() : elements.hasNext();
        }

        /** Writes the separator (and the member name) before the next child and returns the child. */
        Object next(StringBuilder out) {
            if (index > 0) {
                out.append(',');
            }
            if (map != null) {
                String name = names.get(index++);
                writeString(name, out);
                out.append(':');
                return map.get(name);
            }
            index++;
            return elements.next();
        }
    }

    private static void writeScalar(Object value, StringBuilder out) {
        if (value == null) {
            out.append("null");
        } else if (value instanceof Boolean) {
            out.append(((Boolean) value).booleanValue() ? "true" : "false");
        } else if (value instanceof String) {
            writeString((String) value, out);
        } else if (value instanceof Number) {
            out.append(integerValue((Number) value));
        } else {
            throw new IllegalArgumentException("not a JSON value: " + value.getClass().getName());
        }
    }

    /** The value of an integer {@link Number} within the integer range of Section 3, rule 7. */
    static long integerValue(Number number) {
        if (number instanceof Long || number instanceof Integer || number instanceof Short || number instanceof Byte) {
            long value = number.longValue();
            if (value > MAX_SAFE_INTEGER || value < -MAX_SAFE_INTEGER) {
                throw new SqllrException(SCHEMA_NON_INTEGER_NUMBER, "integer out of range: " + value);
            }
            return value;
        }
        if (number instanceof BigInteger) {
            BigInteger big = (BigInteger) number;
            if (big.abs().compareTo(MAX_BIG) > 0) {
                throw new SqllrException(SCHEMA_NON_INTEGER_NUMBER, "integer out of range: " + big);
            }
            return big.longValue();
        }
        throw new SqllrException(SCHEMA_NON_INTEGER_NUMBER, String.valueOf(number));
    }

    private static void writeString(String value, StringBuilder out) {
        if (firstUnpairedSurrogate(value) >= 0) {
            throw new SqllrException(SCHEMA_INVALID_JSON, "unpaired surrogate in a string");
        }
        out.append('"');
        for (int i = 0; i < value.length(); i++) {
            char c = value.charAt(i);
            switch (c) {
                case '"': out.append("\\\""); break;
                case '\\': out.append("\\\\"); break;
                case '\b': out.append("\\b"); break;
                case '\t': out.append("\\t"); break;
                case '\n': out.append("\\n"); break;
                case '\f': out.append("\\f"); break;
                case '\r': out.append("\\r"); break;
                default:
                    if (c < 0x20) {
                        out.append("\\u00").append(HEX[c >> 4]).append(HEX[c & 0xf]);
                    } else {
                        out.append(c);
                    }
            }
        }
        out.append('"');
    }

    private static final char[] HEX = "0123456789abcdef".toCharArray();

    /** The index of the first unpaired surrogate code unit of {@code value}, or -1. */
    static int firstUnpairedSurrogate(String value) {
        for (int i = 0; i < value.length(); i++) {
            char c = value.charAt(i);
            if (Character.isHighSurrogate(c)) {
                if (i + 1 < value.length() && Character.isLowSurrogate(value.charAt(i + 1))) {
                    i++;
                } else {
                    return i;
                }
            } else if (Character.isLowSurrogate(c)) {
                return i;
            }
        }
        return -1;
    }

    // ---------------------------------------------------------------------------------------------
    // Ordering (Sections 5 and 6)
    // ---------------------------------------------------------------------------------------------

    /** {@code canonicalizeDocument(value, strict, ArrayRegistry.standard(), null)}. */
    public static Object canonicalizeDocument(Object value, boolean strict) {
        return canonicalizeDocument(value, strict, ArrayRegistry.standard(), null);
    }

    /**
     * A copy of a lineage document with every {@code SET} array sorted by its registered key; every
     * {@code SEQUENCE} and {@code DISPLAY_ORDER} array, and every array in open content, keeps its order.
     * Members keep their order (the writer orders them). Children are visited in input order and an array
     * is checked after its elements, as the reference does, so the first rejection is the reference's.
     *
     * @param strict reject an unregistered array outside open content with {@code SCHEMA_VIOLATION}
     *               (Section 5, rule 5); otherwise keep it in order
     * @param notes  when not null and not strict, receives one line per unregistered array kept in order
     * @throws SqllrException {@code SEMANTIC_ARRAY_KIND_VIOLATION} for a {@code SET} holding two equal elements
     *                        or a {@code SEQUENCE} whose ordinals are not 0..n-1 (Section 5, rules 3 and 4);
     *                        {@code SCHEMA_VIOLATION} as above
     */
    public static Object canonicalizeDocument(Object value, boolean strict, ArrayRegistry registry, List<String> notes) {
        ArrayRegistry.Position root = registry.root();
        if (!isContainer(value)) {
            return value;
        }
        Deque<WalkFrame> stack = new ArrayDeque<WalkFrame>();
        stack.push(new WalkFrame(value, root, "$", root != null && root.isOpenContent(), 1));
        Object result = null;
        while (!stack.isEmpty()) {
            WalkFrame frame = stack.peek();
            if (frame.hasNext()) {
                WalkFrame child = frame.nextChild();
                if (child != null) {
                    stack.push(child);
                }
                continue;
            }
            stack.pop();
            Object done = frame.finish(strict, notes);
            if (stack.isEmpty()) {
                result = done;
            } else {
                stack.peek().accept(done);
            }
        }
        return result;
    }

    /** One object or array being canonicalized. */
    private static final class WalkFrame {
        private final ArrayRegistry.Position position;
        private final String path;
        private final boolean inOpen;
        private final int level;
        private final Iterator<? extends Map.Entry<?, ?>> members;
        private final Map<String, Object> outMap;
        private final Iterator<?> elements;
        private final List<Object> outList;
        private String pendingName;

        WalkFrame(Object node, ArrayRegistry.Position position, String path, boolean inOpen, int level) {
            if (level > MAX_DEPTH) {
                throw new SqllrException(SCHEMA_INVALID_JSON, "nesting deeper than " + MAX_DEPTH);
            }
            this.position = position;
            this.path = path;
            this.inOpen = inOpen;
            this.level = level;
            if (node instanceof Map<?, ?>) {
                this.members = ((Map<?, ?>) node).entrySet().iterator();
                this.outMap = new LinkedHashMap<String, Object>();
                this.elements = null;
                this.outList = null;
            } else {
                this.members = null;
                this.outMap = null;
                this.elements = ((List<?>) node).iterator();
                this.outList = new ArrayList<Object>(((List<?>) node).size());
            }
        }

        boolean hasNext() {
            return members != null ? members.hasNext() : elements.hasNext();
        }

        /** Takes the next child: a scalar is copied at once (null returned), a container gets a frame. */
        WalkFrame nextChild() {
            Object child;
            ArrayRegistry.Position childPosition;
            String childPath;
            boolean childOpen;
            if (members != null) {
                Map.Entry<?, ?> entry = members.next();
                String name = (String) entry.getKey();
                child = entry.getValue();
                childPosition = position == null ? null : position.member(name);
                childPath = path + "." + name;
                childOpen = inOpen || "extensions".equals(name);
                pendingName = name;
            } else {
                child = elements.next();
                childPosition = position == null ? null : position.element();
                childPath = path + "[]";
                childOpen = inOpen;
            }
            if (!isContainer(child)) {
                accept(child);
                return null;
            }
            childOpen = childOpen || (childPosition != null && childPosition.isOpenContent());
            return new WalkFrame(child, childPosition, childPath, childOpen, level + 1);
        }

        void accept(Object value) {
            if (outMap != null) {
                outMap.put(pendingName, value);
            } else {
                outList.add(value);
            }
        }

        Object finish(boolean strict, List<String> notes) {
            if (outMap != null) {
                return outMap;
            }
            ArrayRegistry.Registration registration = inOpen ? ArrayRegistry.Registration.OPEN_SEQUENCE
                    : position == null ? null : position.registration();
            if (registration == null) {
                if (strict) {
                    throw new SqllrException(SCHEMA_VIOLATION, "unregistered array " + path);
                }
                if (notes != null) {
                    notes.add("unregistered array " + path + " kept in order");
                }
                return outList;
            }
            if (registration.getOrder() == ArrayRegistry.Order.SET) {
                return sortSet(outList, registration.getSortKey(), path);
            }
            checkOrdinals(outList, path);
            return outList;
        }
    }

    private static List<Object> sortSet(List<Object> items, ArrayRegistry.SortKey key, String path) {
        List<Keyed> keyed = new ArrayList<Keyed>(items.size());
        for (Object item : items) {
            keyed.add(new Keyed(item, key));
        }
        Collections.sort(keyed, KEYED_ORDER);
        List<Object> out = new ArrayList<Object>(items.size());
        for (int i = 0; i < keyed.size(); i++) {
            if (i > 0 && Arrays.equals(keyed.get(i - 1).bytes, keyed.get(i).bytes)) {
                throw new SqllrException(SEMANTIC_ARRAY_KIND_VIOLATION, path + " holds equal elements");
            }
            out.add(keyed.get(i).element);
        }
        return out;
    }

    /** Section 5, rule 3: when every element carries an integer ordinal, they are 0..n-1 in array order. */
    private static void checkOrdinals(List<Object> items, String path) {
        if (items.isEmpty()) {
            return;
        }
        for (Object item : items) {
            if (!(item instanceof Map<?, ?>) || !isInteger(((Map<?, ?>) item).get("ordinal"))) {
                return;
            }
        }
        for (int i = 0; i < items.size(); i++) {
            long ordinal = integerValue((Number) ((Map<?, ?>) items.get(i)).get("ordinal"));
            if (ordinal != i) {
                throw new SqllrException(SEMANTIC_ARRAY_KIND_VIOLATION, path + " ordinals are not 0..n-1 in array order");
            }
        }
    }

    /** A deep copy of a JSON value in which every object and array is unmodifiable. */
    public static Object immutableCopy(Object value) {
        if (!isContainer(value)) {
            return value;
        }
        Deque<CopyFrame> stack = new ArrayDeque<CopyFrame>();
        stack.push(new CopyFrame(value, 1));
        Object result = null;
        while (!stack.isEmpty()) {
            CopyFrame frame = stack.peek();
            if (frame.hasNext()) {
                Object child = frame.next();
                if (isContainer(child)) {
                    stack.push(new CopyFrame(child, stack.size() + 1));
                } else {
                    frame.accept(child);
                }
                continue;
            }
            stack.pop();
            Object done = frame.finish();
            if (stack.isEmpty()) {
                result = done;
            } else {
                stack.peek().accept(done);
            }
        }
        return result;
    }

    /** One object or array being copied. */
    private static final class CopyFrame {
        private final Iterator<? extends Map.Entry<?, ?>> members;
        private final Map<String, Object> outMap;
        private final Iterator<?> elements;
        private final List<Object> outList;
        private String pendingName;

        CopyFrame(Object node, int level) {
            if (level > MAX_DEPTH) {
                throw new SqllrException(SCHEMA_INVALID_JSON, "nesting deeper than " + MAX_DEPTH);
            }
            if (node instanceof Map<?, ?>) {
                members = ((Map<?, ?>) node).entrySet().iterator();
                outMap = new LinkedHashMap<String, Object>();
                elements = null;
                outList = null;
            } else {
                members = null;
                outMap = null;
                elements = ((List<?>) node).iterator();
                outList = new ArrayList<Object>(((List<?>) node).size());
            }
        }

        boolean hasNext() {
            return members != null ? members.hasNext() : elements.hasNext();
        }

        Object next() {
            if (members != null) {
                Map.Entry<?, ?> entry = members.next();
                pendingName = (String) entry.getKey();
                return entry.getValue();
            }
            return elements.next();
        }

        void accept(Object value) {
            if (outMap != null) {
                outMap.put(pendingName, value);
            } else {
                outList.add(value);
            }
        }

        Object finish() {
            return outMap != null ? Collections.unmodifiableMap(outMap) : Collections.unmodifiableList(outList);
        }
    }

    /** True for a JSON integer (not a boolean). */
    public static boolean isInteger(Object value) {
        return value instanceof Long || value instanceof Integer || value instanceof Short || value instanceof Byte
                || value instanceof BigInteger;
    }

    /** An element with its precomputed sort key and canonical bytes. */
    private static final class Keyed {
        final Object element;
        final TypedKey[] key;
        final byte[] bytes;

        Keyed(Object element, ArrayRegistry.SortKey sortKey) {
            this.element = element;
            this.bytes = jcsBytes(element);
            switch (sortKey.getKind()) {
                case SELF:
                    key = new TypedKey[] {new TypedKey(element, bytes)};
                    break;
                case REF:
                    key = new TypedKey[] {new TypedKey(member(element, "ref"), null)};
                    break;
                case BYTES:
                    key = new TypedKey[0];
                    break;
                default:
                    List<String> names = sortKey.getMembers();
                    key = new TypedKey[names.size()];
                    for (int i = 0; i < key.length; i++) {
                        key[i] = new TypedKey(member(element, names.get(i)), null);
                    }
            }
        }

        private static Object member(Object element, String name) {
            return element instanceof Map<?, ?> ? ((Map<?, ?>) element).get(name) : null;
        }
    }

    private static final Comparator<Keyed> KEYED_ORDER = new Comparator<Keyed>() {
        @Override
        public int compare(Keyed a, Keyed b) {
            for (int i = 0; i < a.key.length; i++) {
                int c = a.key[i].compareTo(b.key[i]);
                if (c != 0) {
                    return c;
                }
            }
            return compareUnsigned(a.bytes, b.bytes);
        }
    };

    /**
     * The total order of Section 6.2 over JSON values: absent or {@code null} &lt; {@code false} &lt;
     * {@code true} &lt; integers (numerically) &lt; strings (unsigned UTF-8 bytes) &lt; arrays and objects
     * (their canonical bytes, unsigned).
     */
    public static int compareTyped(Object a, Object b) {
        return new TypedKey(a, null).compareTo(new TypedKey(b, null));
    }

    /** Unsigned lexicographic order of byte arrays. */
    public static int compareUnsigned(byte[] a, byte[] b) {
        int common = Math.min(a.length, b.length);
        for (int i = 0; i < common; i++) {
            int c = (a[i] & 0xff) - (b[i] & 0xff);
            if (c != 0) {
                return c;
            }
        }
        return a.length - b.length;
    }

    /** One component of a sort key, ranked as in Section 6.2. */
    private static final class TypedKey implements Comparable<TypedKey> {
        final int rank;
        final long number;
        final byte[] bytes;

        TypedKey(Object value, byte[] canonical) {
            if (value == null) {
                rank = 0;
                number = 0;
                bytes = null;
            } else if (value instanceof Boolean) {
                rank = 1;
                number = ((Boolean) value).booleanValue() ? 1 : 0;
                bytes = null;
            } else if (value instanceof Number) {
                rank = 2;
                number = integerValue((Number) value);
                bytes = null;
            } else if (value instanceof String) {
                if (firstUnpairedSurrogate((String) value) >= 0) {
                    throw new SqllrException(SCHEMA_INVALID_JSON, "unpaired surrogate in a string");
                }
                rank = 3;
                number = 0;
                bytes = ((String) value).getBytes(StandardCharsets.UTF_8);
            } else {
                rank = 4;
                number = 0;
                bytes = canonical != null ? canonical : jcsBytes(value);
            }
        }

        @Override
        public int compareTo(TypedKey other) {
            if (rank != other.rank) {
                return rank < other.rank ? -1 : 1;
            }
            if (rank == 1 || rank == 2) {
                return number < other.number ? -1 : number == other.number ? 0 : 1;
            }
            if (rank == 0) {
                return 0;
            }
            return compareUnsigned(bytes, other.bytes);
        }
    }

    // ---------------------------------------------------------------------------------------------
    // The parser
    // ---------------------------------------------------------------------------------------------

    /**
     * An RFC 8259 parser that follows the decisions of CPython's {@code json} scanner as the reference
     * configures it (strict strings, integers through {@code parse_int}, fractions and exponents rejected,
     * duplicate names detected by the object hook when the object closes), with an explicit stack.
     */
    private static final class Parser {
        private final String s;
        private final int length;
        private int pos;
        private boolean unpairedSurrogate;

        /** An object or array whose closing bracket has not been read yet. */
        private static final class Open {
            final List<String> names;
            final List<Object> values;
            String pendingName;

            Open(boolean object) {
                names = object ? new ArrayList<String>() : null;
                values = new ArrayList<Object>();
            }
        }

        Parser(String s) {
            this.s = s;
            this.length = s.length();
        }

        Object parseText() {
            skipWhitespace();
            Object value = value();
            skipWhitespace();
            if (pos != length) {
                throw invalid("extra data");
            }
            if (unpairedSurrogate) {
                throw new SqllrException(SCHEMA_INVALID_JSON, "unpaired surrogate in a string or member name");
            }
            return value;
        }

        /** One JSON value at {@code pos}, the text before it already skipped. */
        private Object value() {
            Deque<Open> stack = new ArrayDeque<Open>();
            while (true) {
                // Read the start of a value: a scalar completes it, a non-empty container opens a level.
                Object completed;
                if (pos >= length) {
                    throw invalid("expecting value");
                }
                char c = s.charAt(pos);
                if (c == '{' || c == '[') {
                    if (stack.size() + 1 > MAX_DEPTH) {
                        throw invalid("nesting deeper than " + MAX_DEPTH);
                    }
                    pos++;
                    skipWhitespace();
                    boolean object = c == '{';
                    if (pos < length && s.charAt(pos) == (object ? '}' : ']')) {
                        pos++;
                        completed = object ? new LinkedHashMap<String, Object>() : new ArrayList<Object>();
                    } else {
                        Open open = new Open(object);
                        if (object) {
                            open.pendingName = memberName();
                        }
                        stack.push(open);
                        continue;
                    }
                } else {
                    completed = scalar(c);
                }
                // Attach the completed value to the open containers, closing those that end here.
                while (true) {
                    Open top = stack.peek();
                    if (top == null) {
                        return completed;
                    }
                    boolean object = top.names != null;
                    if (object) {
                        top.names.add(top.pendingName);
                    }
                    top.values.add(completed);
                    skipWhitespace();
                    if (pos < length && s.charAt(pos) == (object ? '}' : ']')) {
                        pos++;
                        stack.pop();
                        completed = object ? closeObject(top) : top.values;
                        continue;
                    }
                    if (pos >= length || s.charAt(pos) != ',') {
                        throw invalid("expecting ',' delimiter");
                    }
                    pos++;
                    skipWhitespace();
                    if (object) {
                        top.pendingName = memberName();
                    }
                    break;
                }
            }
        }

        /** {@code "name"}, whitespace, {@code :}, whitespace; the reader is at the opening quote. */
        private String memberName() {
            if (pos >= length || s.charAt(pos) != '"') {
                throw invalid("expecting property name enclosed in double quotes");
            }
            pos++;
            String name = string();
            skipWhitespace();
            if (pos >= length || s.charAt(pos) != ':') {
                throw invalid("expecting ':' delimiter");
            }
            pos++;
            skipWhitespace();
            return name;
        }

        /** Rule 5 is checked when the object closes, as the reference's object_pairs_hook does. */
        private Map<String, Object> closeObject(Open open) {
            Map<String, Object> out = new LinkedHashMap<String, Object>(open.names.size() * 2);
            for (int i = 0; i < open.names.size(); i++) {
                if (out.containsKey(open.names.get(i))) {
                    throw new SqllrException(SCHEMA_DUPLICATE_KEY, "duplicate member " + open.names.get(i));
                }
                out.put(open.names.get(i), open.values.get(i));
            }
            return out;
        }

        private Object scalar(char c) {
            switch (c) {
                case '"':
                    pos++;
                    return string();
                case 'n':
                    return literal("null", null);
                case 't':
                    return literal("true", Boolean.TRUE);
                case 'f':
                    return literal("false", Boolean.FALSE);
                default:
                    if (c == '-' || (c >= '0' && c <= '9')) {
                        return number();
                    }
                    // NaN, Infinity and every other token are not JSON.
                    throw invalid("expecting value");
            }
        }

        private Object literal(String word, Object value) {
            if (!s.startsWith(word, pos)) {
                throw invalid("expecting value");
            }
            pos += word.length();
            return value;
        }

        /** The string whose opening quote has been consumed. */
        private String string() {
            StringBuilder out = new StringBuilder();
            while (true) {
                if (pos >= length) {
                    throw invalid("unterminated string");
                }
                char c = s.charAt(pos++);
                if (c == '"') {
                    break;
                }
                if (c == '\\') {
                    if (pos >= length) {
                        throw invalid("unterminated string");
                    }
                    char e = s.charAt(pos++);
                    switch (e) {
                        case '"': out.append('"'); break;
                        case '\\': out.append('\\'); break;
                        case '/': out.append('/'); break;
                        case 'b': out.append('\b'); break;
                        case 'f': out.append('\f'); break;
                        case 'n': out.append('\n'); break;
                        case 'r': out.append('\r'); break;
                        case 't': out.append('\t'); break;
                        case 'u': out.append(hex4()); break;
                        default: throw invalid("invalid escape");
                    }
                } else if (c < 0x20) {
                    throw invalid("invalid control character in a string");
                } else {
                    out.append(c);
                }
            }
            String value = out.toString();
            if (firstUnpairedSurrogate(value) >= 0) {
                // Reported after the whole text parsed, as the reference checks values after json.loads.
                unpairedSurrogate = true;
            }
            return value;
        }

        private char hex4() {
            if (pos + 4 > length) {
                throw invalid("invalid \\uXXXX escape");
            }
            int value = 0;
            for (int i = 0; i < 4; i++) {
                char c = s.charAt(pos++);
                int digit;
                if (c >= '0' && c <= '9') {
                    digit = c - '0';
                } else if (c >= 'a' && c <= 'f') {
                    digit = c - 'a' + 10;
                } else if (c >= 'A' && c <= 'F') {
                    digit = c - 'A' + 10;
                } else {
                    throw invalid("invalid \\uXXXX escape");
                }
                value = (value << 4) | digit;
            }
            return (char) value;
        }

        private Long number() {
            int start = pos;
            if (s.charAt(pos) == '-') {
                pos++;
                if (pos >= length) {
                    throw invalid("expecting value");
                }
            }
            char c = s.charAt(pos);
            if (c >= '1' && c <= '9') {
                pos++;
                while (pos < length && isDigit(s.charAt(pos))) {
                    pos++;
                }
            } else if (c == '0') {
                pos++;
            } else {
                throw invalid("expecting value");
            }
            boolean fraction = false;
            if (pos + 1 < length && s.charAt(pos) == '.' && isDigit(s.charAt(pos + 1))) {
                pos += 2;
                while (pos < length && isDigit(s.charAt(pos))) {
                    pos++;
                }
                fraction = true;
            }
            if (pos < length && (s.charAt(pos) == 'e' || s.charAt(pos) == 'E')) {
                int exponentStart = pos;
                pos++;
                if (pos < length && (s.charAt(pos) == '-' || s.charAt(pos) == '+')) {
                    pos++;
                }
                int digits = pos;
                while (pos < length && isDigit(s.charAt(pos))) {
                    pos++;
                }
                if (pos > digits) {
                    fraction = true;
                } else {
                    pos = exponentStart;
                }
            }
            String token = s.substring(start, pos);
            if (fraction) {
                throw new SqllrException(SCHEMA_NON_INTEGER_NUMBER, token);
            }
            if ("-0".equals(token)) {
                throw new SqllrException(SCHEMA_NON_INTEGER_NUMBER, "-0 is not a canonical integer");
            }
            int digitCount = token.startsWith("-") ? token.length() - 1 : token.length();
            if (digitCount > 16) {
                throw new SqllrException(SCHEMA_NON_INTEGER_NUMBER, "integer out of range: " + token);
            }
            long value = Long.parseLong(token);
            if (value > MAX_SAFE_INTEGER || value < -MAX_SAFE_INTEGER) {
                throw new SqllrException(SCHEMA_NON_INTEGER_NUMBER, "integer out of range: " + token);
            }
            return Long.valueOf(value);
        }

        private static boolean isDigit(char c) {
            return c >= '0' && c <= '9';
        }

        private void skipWhitespace() {
            while (pos < length) {
                char c = s.charAt(pos);
                if (c != ' ' && c != '\t' && c != '\n' && c != '\r') {
                    return;
                }
                pos++;
            }
        }

        private SqllrException invalid(String message) {
            return new SqllrException(SCHEMA_INVALID_JSON, message + " at character " + pos);
        }
    }
}