package gudusoft.gsqlparser.lineage.v2.validation;

import gudusoft.gsqlparser.lineage.v2.Finding;
import gudusoft.gsqlparser.lineage.v2.identity.IdentityV1;
import gudusoft.gsqlparser.lineage.v2.identity.PathV1;

import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.charset.CharacterCodingException;
import java.nio.charset.CharsetDecoder;
import java.nio.charset.CoderResult;
import java.nio.charset.CodingErrorAction;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import static gudusoft.gsqlparser.lineage.v2.validation.DocumentIndex.intRef;
import static gudusoft.gsqlparser.lineage.v2.validation.DocumentIndex.items;

/**
 * Validation stage {@code SEMANTIC} (specification Section 14.2) as the reference runner implements it
 * ({@code conformance/run.py}, {@code stage_semantic}): module presence, Facts without an Occurrence,
 * declaration bases, document-local identities, the proof/binding/coverage contracts of Sections 4.3 and 4.4,
 * source embedding, PATH-V1 nesting, FROM-item row propagation, spans against the source text, the column
 * ordinals of the ExplainGraph, and the FOLD-V1 checks of a {@link FoldCheck} when one is given.
 *
 * @since 4.2.17
 */
public final class SemanticStage {

    /** The FOLD-V1 {@code PROJECTOR} checks, run when the document has an ExplainGraph. */
    public interface FoldCheck {
        void check(DocumentIndex index, List<Finding> findings, List<String> notes);
    }

    private static final Map<String, String> MODULE_OF_MEMBER = new TreeMap<String, String>();

    static {
        MODULE_OF_MEMBER.put("explainGraph", "explain");
        MODULE_OF_MEMBER.put("evidence", "evidence");
        MODULE_OF_MEMBER.put("dynamicSqlSites", "dynamic-sql");
        MODULE_OF_MEMBER.put("expressionSpans", "exact-spans");
        MODULE_OF_MEMBER.put("reproducibilityManifest", "reproducibility");
        MODULE_OF_MEMBER.put("typedSteps", "typed-steps");
        MODULE_OF_MEMBER.put("routineCalls", "routines");
        MODULE_OF_MEMBER.put("wildcardSelections", "wildcards");
        MODULE_OF_MEMBER.put("structuralSignatures", "structural-signature");
        MODULE_OF_MEMBER.put("refinements", "join-semantics");
        MODULE_OF_MEMBER.put("naryFacts", "nary-facts");
    }

    private static final List<String> LOCAL_ONLY_KINDS = Arrays.asList("QUERY_RESULT", "TEMP_TABLE", "TABLE_VARIABLE",
            "CTE", "VARIABLE", "PARAMETER");
    private static final List<String> LOCAL_OR_OPAQUE_KINDS = Arrays.asList("SEQUENCE", "STAGE", "STORAGE_LOCATION");
    private static final List<String> DECLARING_BASES = Arrays.asList("CATALOG_VERIFIED", "DDL_IN_INPUT",
            "DERIVED_OUTPUT", "ROUTINE_DECLARATION", "LOCAL_DECLARATION");
    private static final List<String> ROW_SOURCE_KINDS = Arrays.asList("RELATION", "TABLE", "VIEW", "MATERIALIZED_VIEW",
            "EXTERNAL_TABLE", "SYNONYM", "TEMP_TABLE", "TABLE_VARIABLE", "CTE");
    private static final List<String> QUERY_BLOCK_STEPS = Arrays.asList("SELECT", "SUBQUERY", "CTE", "BRANCH");
    private static final List<String> QUERY_STATEMENT_ROOTS = Arrays.asList("SELECT", "INSERT", "CREATE_TABLE",
            "CREATE_VIEW");

    private final SourceTextProvider sources;
    private final FoldCheck fold;

    /**
     * @param sources where the text of NAMED source units is found; {@link SourceTextProvider#NONE} for none
     * @param fold    the FOLD-V1 checks, or null to skip them
     */
    public SemanticStage(SourceTextProvider sources, FoldCheck fold) {
        this.sources = sources == null ? SourceTextProvider.NONE : sources;
        this.fold = fold;
    }

    /**
     * The findings of the stage for a document that passed stage {@code SCHEMA}.
     *
     * @param deferred findings stage SCHEMA deferred to this stage
     * @param notes    receives what the stage could not check
     */
    public List<Finding> run(Map<?, ?> doc, List<Finding> deferred, List<String> notes) {
        List<Finding> findings = new ArrayList<Finding>(deferred);
        DocumentIndex index = new DocumentIndex(doc);
        Set<String> modules = new HashSet<String>();
        if (doc.get("modules") instanceof List<?>) {
            for (Object module : (List<?>) doc.get("modules")) {
                if (module instanceof String) {
                    modules.add((String) module);
                }
            }
        }
        for (String[] content : moduleContent(doc, index)) {
            if (!modules.contains(content[0])) {
                findings.add(new Finding("SEMANTIC_MODULE_NOT_DECLARED", content[1], "module " + content[0] + " is not listed"));
            }
        }

        // Section 3.2, rule 1: every published Fact has at least one Occurrence.
        Set<Long> asserted = new HashSet<Long>();
        for (Map<?, ?> occurrence : index.all("occurrence")) {
            asserted.add(intRef(occurrence.get("factRef")));
        }
        for (Map<?, ?> fact : index.all("fact")) {
            if (!asserted.contains(intRef(fact.get("ref")))) {
                findings.add(new Finding("SEMANTIC_FACT_WITHOUT_OCCURRENCE", "facts ref " + fact.get("ref"), ""));
            }
        }

        declarationBases(index, findings);
        checkIdentities(index, findings);
        checkContracts(doc, index, findings);
        checkSourceEmbedding(doc, index, findings);
        checkPaths(doc, index, findings);
        checkRowPropagation(index, findings);
        checkSpans(index, findings, notes);
        checkColumnOrdinals(index, findings);
        if (index.hasGraph()) {
            if (fold != null) {
                fold.check(index, findings, notes);
            } else {
                notes.add("explainGraph: no FOLD-V1 check configured; facts, candidates and write bounds not checked"
                        + " against the graph");
            }
        }
        return findings;
    }

    // ---------------------------------------------------------------------------------------------

    private static List<String[]> moduleContent(Map<?, ?> doc, DocumentIndex index) {
        List<String[]> found = new ArrayList<String[]>();
        for (Map.Entry<String, String> entry : MODULE_OF_MEMBER.entrySet()) {
            if (doc.containsKey(entry.getKey())) {
                found.add(new String[] {entry.getValue(), entry.getKey()});
            }
        }
        for (Map<?, ?> occurrence : index.all("occurrence")) {
            if (occurrence.containsKey("supportPathRefs")) {
                found.add(new String[] {"explain", "occurrences ref " + occurrence.get("ref") + " supportPathRefs"});
            }
            if (occurrence.containsKey("evidenceRefs")) {
                found.add(new String[] {"evidence", "occurrences ref " + occurrence.get("ref") + " evidenceRefs"});
            }
        }
        for (String kind : new String[] {"fact", "factCandidate"}) {
            for (Map<?, ?> obj : index.all(kind)) {
                if ("DATASET_DEPENDENCY".equals(obj.get("kind")) || obj.containsKey("datasetDependency")) {
                    found.add(new String[] {"dataset-dependency", kind + "s ref " + obj.get("ref")});
                }
                if ("CALL".equals(obj.get("kind"))) {
                    found.add(new String[] {"routines", kind + "s ref " + obj.get("ref")});
                }
            }
        }
        for (Map<?, ?> endpoint : index.all("endpoint")) {
            if (endpoint.containsKey("pathSegments") || endpoint.containsKey("displayPath")) {
                found.add(new String[] {"nested-fields", "endpoints ref " + endpoint.get("ref")});
            }
            if (endpoint.containsKey("routineNamespace") || endpoint.containsKey("routineKind")
                    || endpoint.containsKey("signature")) {
                found.add(new String[] {"routines", "endpoints ref " + endpoint.get("ref")});
            }
        }
        for (Map<?, ?> unit : index.all("sourceUnit")) {
            if (unit.containsKey("originMap")) {
                found.add(new String[] {"exact-spans", "sourceUnits ref " + unit.get("ref") + " originMap"});
            }
        }
        for (Map<?, ?> set : index.all("candidateSet")) {
            if (set.containsKey("details")) {
                found.add(new String[] {"evidence", "candidate set ref " + set.get("ref") + " details"});
            }
        }
        for (Object[] position : positions(index)) {
            if (position[1] instanceof Map<?, ?> && ((Map<?, ?>) position[1]).containsKey("utf16Offset0")) {
                found.add(new String[] {"exact-spans", position[0] + ".utf16Offset0"});
            }
        }
        return found;
    }

    /** (where, position) for every position of the core and the ExplainGraph. */
    private static List<Object[]> positions(DocumentIndex index) {
        List<Object[]> out = new ArrayList<Object[]>();
        for (Map<?, ?> statement : index.all("statement")) {
            for (String end : new String[] {"start", "end"}) {
                out.add(new Object[] {"statements ref " + statement.get("ref") + "." + end, statement.get(end)});
            }
        }
        List<Object[]> spans = new ArrayList<Object[]>();
        for (Map<?, ?> unit : index.all("sourceUnit")) {
            spans.add(new Object[] {"sourceUnits ref " + unit.get("ref") + ".siteSpan", unit.get("siteSpan")});
        }
        for (Map<?, ?> node : index.all("node")) {
            spans.add(new Object[] {"explainGraph.nodes ref " + node.get("ref") + ".span", node.get("span")});
        }
        for (Map<?, ?> diagnostic : index.all("diagnostic")) {
            spans.add(new Object[] {"diagnostics ref " + diagnostic.get("ref") + ".span", diagnostic.get("span")});
        }
        for (Object[] span : spans) {
            if (span[1] instanceof Map<?, ?>) {
                for (String end : new String[] {"start", "end"}) {
                    out.add(new Object[] {span[0] + "." + end, ((Map<?, ?>) span[1]).get(end)});
                }
            }
        }
        for (Map<?, ?> edge : index.all("microEdge")) {
            out.add(new Object[] {"explainGraph.microEdges ref " + edge.get("ref") + ".referenceStart",
                    edge.get("referenceStart")});
        }
        return out;
    }

    private static boolean isField(DocumentIndex index, Object ref) {
        Map<?, ?> endpoint = index.get("endpoint", ref);
        return endpoint != null && "FIELD".equals(endpoint.get("kind"));
    }

    private static boolean sideIsField(DocumentIndex index, Object end) {
        if (!(end instanceof Map<?, ?>)) {
            return false;
        }
        Map<?, ?> side = (Map<?, ?>) end;
        if (side.containsKey("endpointRef")) {
            return isField(index, side.get("endpointRef"));
        }
        List<?> members = candidateRefs(side.get("candidateSet"));
        if (members.isEmpty()) {
            return false;
        }
        for (Object member : members) {
            if (!isField(index, member)) {
                return false;
            }
        }
        return true;
    }

    private static List<?> candidateRefs(Object set) {
        Object refs = set instanceof Map<?, ?> ? ((Map<?, ?>) set).get("candidateRefs") : null;
        return refs instanceof List<?> ? (List<?>) refs : Collections.emptyList();
    }

    /** Section 4.2: the binding of every field endpoint carries declarationBasis. */
    private static void declarationBases(DocumentIndex index, List<Finding> findings) {
        for (Map<?, ?> occurrence : index.all("occurrence")) {
            Map<?, ?> fact = index.get("fact", occurrence.get("factRef"));
            Map<?, ?> candidate = index.get("factCandidate", occurrence.get("factCandidateRef"));
            boolean[] fields;
            if (fact != null) {
                fields = new boolean[] {isField(index, fact.get("sourceRef")), isField(index, fact.get("targetRef"))};
            } else if (candidate != null) {
                fields = new boolean[] {sideIsField(index, candidate.get("source")),
                        sideIsField(index, candidate.get("target"))};
            } else {
                continue;
            }
            String[] members = {"sourceBinding", "targetBinding"};
            for (int i = 0; i < 2; i++) {
                Object binding = occurrence.get(members[i]);
                if (fields[i] && binding instanceof Map<?, ?> && !((Map<?, ?>) binding).containsKey("declarationBasis")) {
                    findings.add(new Finding("SEMANTIC_DECLARATION_BASIS_MISSING",
                            "occurrences ref " + occurrence.get("ref") + " " + members[i], ""));
                }
            }
        }
        for (Map<?, ?> edge : index.all("microEdge")) {
            Object[][] sides = {{"sourceBinding", edge.get("sourceRef")}, {"targetBinding", edge.get("targetRef")}};
            for (Object[] side : sides) {
                Object binding = edge.get(side[0]);
                if (binding instanceof Map<?, ?> && isField(index, side[1])
                        && !((Map<?, ?>) binding).containsKey("declarationBasis")) {
                    findings.add(new Finding("SEMANTIC_DECLARATION_BASIS_MISSING",
                            "explainGraph.microEdges ref " + edge.get("ref") + " " + side[0], ""));
                }
            }
        }
    }

    /**
     * Whether the owner chain of an endpoint reaches an endpoint of one kind. Each endpoint is walked once, so a
     * document is checked in time linear in its endpoints; a chain that ends at a missing owner, or loops without
     * meeting the kind, does not reach it.
     */
    static final class OwnerChains {
        private final DocumentIndex index;
        private final String kind;
        /** For an endpoint ref: whether it, or an endpoint on its owner chain, has the kind. */
        private final Map<Long, Boolean> selfOrChain = new HashMap<Long, Boolean>();

        OwnerChains(DocumentIndex index, String kind) {
            this.index = index;
            this.kind = kind;
        }

        boolean reaches(Map<?, ?> endpoint) {
            Long owner = intRef(endpoint.get("ownerRef"));
            return owner != null && selfOrChain(owner);
        }

        private boolean selfOrChain(Long start) {
            List<Long> path = new ArrayList<Long>();
            Set<Long> onPath = new HashSet<Long>();
            Long current = start;
            boolean result;
            while (true) {
                Boolean known = selfOrChain.get(current);
                if (known != null) {
                    result = known;
                    break;
                }
                Map<?, ?> endpoint = index.get("endpoint", current);
                if (endpoint == null || !onPath.add(current)) {
                    result = false;
                    break;
                }
                if (kind.equals(endpoint.get("kind"))) {
                    selfOrChain.put(current, Boolean.TRUE);
                    result = true;
                    break;
                }
                path.add(current);
                current = intRef(endpoint.get("ownerRef"));
                if (current == null) {
                    result = false;
                    break;
                }
            }
            for (Long ref : path) {
                selfOrChain.put(ref, result);
            }
            return result;
        }
    }

    /** Section 3.2, rule 6: endpoints whose identity is document-local. */
    private static void checkIdentities(DocumentIndex index, List<Finding> findings) {
        OwnerChains queryResults = new OwnerChains(index, "QUERY_RESULT");
        for (Map<?, ?> endpoint : index.all("endpoint")) {
            Object identity = endpoint.get("identity");
            Object status = identity instanceof Map<?, ?> ? ((Map<?, ?>) identity).get("status") : null;
            Object kind = endpoint.get("kind");
            String where = "endpoints ref " + endpoint.get("ref");
            if (LOCAL_ONLY_KINDS.contains(kind) && !"LOCAL".equals(status)) {
                findings.add(new Finding("SEMANTIC_LOCAL_IDENTITY_REQUIRED", where, kind + " declares " + status));
            } else if (LOCAL_OR_OPAQUE_KINDS.contains(kind) && !"LOCAL".equals(status)
                    && !"OPAQUE_PRODUCER_LOCAL".equals(status)) {
                findings.add(new Finding("SEMANTIC_LOCAL_IDENTITY_REQUIRED", where, kind + " declares " + status));
            } else if (!"LOCAL".equals(status) && queryResults.reaches(endpoint)) {
                findings.add(new Finding("SEMANTIC_LOCAL_IDENTITY_REQUIRED", where,
                        "owned by a QUERY_RESULT but declares " + status));
            }
        }
    }

    private static List<Object[]> bindings(DocumentIndex index) {
        List<Object[]> out = new ArrayList<Object[]>();
        for (Map<?, ?> occurrence : index.all("occurrence")) {
            for (String member : new String[] {"sourceBinding", "targetBinding"}) {
                if (occurrence.get(member) instanceof Map<?, ?>) {
                    out.add(new Object[] {"occurrences ref " + occurrence.get("ref") + " " + member, occurrence.get(member)});
                }
            }
        }
        for (Map<?, ?> edge : index.all("microEdge")) {
            for (String member : new String[] {"sourceBinding", "targetBinding"}) {
                if (edge.get(member) instanceof Map<?, ?>) {
                    out.add(new Object[] {"explainGraph.microEdges ref " + edge.get("ref") + " " + member, edge.get(member)});
                }
            }
        }
        return out;
    }

    /**
     * The ExplainGraph candidate sets that the first (source side) or last (target side) micro-edge of an Occurrence's
     * support paths binds through, one per set, by ref.
     */
    private static List<Map<?, ?>> walkedSets(DocumentIndex index, Map<?, ?> occurrence, String side) {
        TreeMap<Long, Map<?, ?>> out = new TreeMap<Long, Map<?, ?>>();
        for (Object pathRef : occurrence.get("supportPathRefs") instanceof List<?>
                ? (List<?>) occurrence.get("supportPathRefs") : Collections.emptyList()) {
            Map<?, ?> path = index.get("supportPath", pathRef);
            List<?> refs = path != null && path.get("microEdgeRefs") instanceof List<?> ? (List<?>) path.get("microEdgeRefs")
                    : Collections.emptyList();
            Map<?, ?> edge = refs.isEmpty() ? null
                    : index.get("microEdge", "sourceBinding".equals(side) ? refs.get(0) : refs.get(refs.size() - 1));
            Object binding = edge == null ? null : edge.get(side);
            if (ambiguous(binding)) {
                Map<?, ?> set = index.get("candidateSet", ((Map<?, ?>) binding).get("candidateSetRef"));
                if (set != null) {
                    out.put(DocumentIndex.intRef(set.get("ref")), set);
                }
            }
        }
        return new ArrayList<Map<?, ?>>(out.values());
    }

    /** A binding with status CANDIDATE or UNRESOLVED. */
    private static boolean ambiguous(Object binding) {
        return binding instanceof Map<?, ?> && ("CANDIDATE".equals(((Map<?, ?>) binding).get("status"))
                || "UNRESOLVED".equals(((Map<?, ?>) binding).get("status")));
    }

    /** The proof, binding and coverage rules of Sections 4.3 and 4.4 that relate two statuses or two objects. */
    private static void checkContracts(Map<?, ?> doc, DocumentIndex index, List<Finding> findings) {
        // Section 4.3, rule 1: a Fact holds whichever candidate each reference denotes (rule 4); its Occurrence at an
        // ambiguous reference is ASSUMED and names a candidate set of the document's candidateSets (in L2, the Endpoint
        // projection of the set its walks read or write through), and for each side on which its binding is ambiguous
        // the Fact has another Occurrence of the same statement whose binding on that side is not (fold-v1, Sections
        // 7.1 and 8.1)
        Map<String, Map<?, ?>> rootSets = new HashMap<String, Map<?, ?>>();
        for (Map<?, ?> set : DocumentIndex.items(doc.get("candidateSets"))) {
            rootSets.put(String.valueOf(set.get("ref")), set);
        }
        Map<String, Set<Object>> settled = new HashMap<String, Set<Object>>();
        for (Map<?, ?> occurrence : index.all("occurrence")) {
            for (String side : new String[] {"sourceBinding", "targetBinding"}) {
                if (occurrence.containsKey("factRef") && !ambiguous(occurrence.get(side))) {
                    String key = side + " " + occurrence.get("factRef") + " " + occurrence.get("statementRef");
                    if (!settled.containsKey(key)) {
                        settled.put(key, new HashSet<Object>());
                    }
                    settled.get(key).add(occurrence.get("ref"));
                }
            }
        }
        for (Map<?, ?> occurrence : index.all("occurrence")) {
            String where = "occurrences ref " + occurrence.get("ref");
            List<Object> statuses = new ArrayList<Object>();
            for (String member : new String[] {"sourceBinding", "targetBinding"}) {
                if (occurrence.get(member) instanceof Map<?, ?>) {
                    statuses.add(((Map<?, ?>) occurrence.get(member)).get("status"));
                }
            }
            boolean ambiguous = statuses.contains("CANDIDATE") || statuses.contains("UNRESOLVED");
            if (occurrence.containsKey("factRef") && ambiguous) {
                if (!"ASSUMED".equals(occurrence.get("proofStatus"))) {
                    findings.add(new Finding("SEMANTIC_BINDING_STATUS_MISMATCH", where,
                            "an Occurrence of a Fact with a CANDIDATE or UNRESOLVED binding is not ASSUMED"));
                }
                for (String side : new String[] {"sourceBinding", "targetBinding"}) {
                    Object binding = occurrence.get(side);
                    if (!ambiguous(binding)) {
                        continue;
                    }
                    Set<Object> others = settled.get(side + " " + occurrence.get("factRef") + " "
                            + occurrence.get("statementRef"));
                    if (others == null || others.isEmpty()
                            || (others.size() == 1 && others.contains(occurrence.get("ref")))) {
                        findings.add(new Finding("SEMANTIC_BINDING_STATUS_MISMATCH", where,
                                "a Fact rests on Occurrences with a CANDIDATE or UNRESOLVED " + side));
                    }
                    Map<?, ?> root = rootSets.get(String.valueOf(((Map<?, ?>) binding).get("candidateSetRef")));
                    if (root == null) {
                        findings.add(new Finding("SEMANTIC_BINDING_STATUS_MISMATCH", where,
                                "the candidate set of an Occurrence of a Fact is not in candidateSets"));
                        continue;
                    }
                    for (Map<?, ?> graphSet : walkedSets(index, occurrence, side)) {
                        List<Long> members = new ArrayList<Long>();
                        int total = 0;
                        for (Object r : graphSet.get("candidateRefs") instanceof List<?>
                                ? (List<?>) graphSet.get("candidateRefs") : Collections.emptyList()) {
                            if (index.get("endpoint", r) != null) {
                                members.add(DocumentIndex.intRef(r));
                            }
                            total++;
                        }
                        boolean complete = "COMPLETE".equals(graphSet.get("membership")) && members.size() >= 2
                                && members.size() == total;
                        List<Long> listed = new ArrayList<Long>();
                        for (Object r : root.get("candidateRefs") instanceof List<?>
                                ? (List<?>) root.get("candidateRefs") : Collections.emptyList()) {
                            listed.add(DocumentIndex.intRef(r));
                        }
                        Collections.sort(members);
                        Collections.sort(listed);
                        if (!members.equals(listed)
                                || !(complete ? "COMPLETE" : "INCOMPLETE").equals(root.get("membership"))) {
                            findings.add(new Finding("SEMANTIC_BINDING_STATUS_MISMATCH", where, "the candidate set "
                                    + root.get("ref") + " is not the Endpoint projection of set " + graphSet.get("ref")));
                        }
                    }
                }
            }
            if (occurrence.containsKey("factCandidateRef") && !ambiguous) {
                findings.add(new Finding("SEMANTIC_BINDING_STATUS_MISMATCH", where,
                        "an Occurrence of a FactCandidate carries no CANDIDATE or UNRESOLVED binding"));
            }
            if ("PROVEN".equals(occurrence.get("proofStatus")) && statuses.contains("ASSUMED")) {
                findings.add(new Finding("SEMANTIC_PROOF_STRONGER_THAN_BINDING", where, "PROVEN with an ASSUMED binding"));
            }
        }
        for (Object[] item : bindings(index)) {
            Map<?, ?> binding = (Map<?, ?>) item[1];
            Set<String> bases = new HashSet<String>();
            if (binding.get("bases") instanceof List<?>) {
                for (Object base : (List<?>) binding.get("bases")) {
                    if (base instanceof String) {
                        bases.add((String) base);
                    }
                }
            }
            Object status = binding.get("status");
            if (bases.contains("PRODUCER_DEFAULT") && "PROVEN".equals(status)) {
                findings.add(new Finding("SEMANTIC_BINDING_BASIS_VIOLATION", (String) item[0],
                        "PROVEN on a PRODUCER_DEFAULT basis"));
            }
            boolean declaring = false;
            for (String base : DECLARING_BASES) {
                declaring |= bases.contains(base);
            }
            if (bases.contains("SINGLE_SOURCE_SCOPE") && !declaring
                    && ("PROVEN".equals(status) || !bases.contains("USAGE_INFERRED"))) {
                findings.add(new Finding("SEMANTIC_BINDING_BASIS_VIOLATION", (String) item[0],
                        "SINGLE_SOURCE_SCOPE alone must be ASSUMED or weaker, with USAGE_INFERRED"));
            }
            if (bases.contains("LOCAL_COLUMN_ASSUMED") && (!"ASSUMED".equals(status)
                    || !bases.contains("SINGLE_SOURCE_SCOPE") || !bases.contains("USAGE_INFERRED"))) {
                findings.add(new Finding("SEMANTIC_BINDING_BASIS_VIOLATION", (String) item[0],
                        "LOCAL_COLUMN_ASSUMED must be ASSUMED, with SINGLE_SOURCE_SCOPE and USAGE_INFERRED"));
            }
        }
        for (Map<?, ?> set : index.all("candidateSet")) {
            Object refs = set.get("candidateRefs");
            int size = refs instanceof List<?> ? ((List<?>) refs).size() : 0;
            if ("COMPLETE".equals(set.get("membership")) && size < 2) {
                findings.add(new Finding("SEMANTIC_CANDIDATE_SET_INVALID", "candidate set ref " + set.get("ref"),
                        "membership COMPLETE with fewer than two members"));
            }
        }
        decidedReferences(index, findings);
        for (Map<?, ?> tfo : index.all("tfo")) {
            String where = "targetFieldOccurrences ref " + tfo.get("ref");
            List<Map<?, ?>> inputs = items(tfo.get("inputs"));
            Object completeness = tfo.get("upstreamCompleteness");
            int disposition = (tfo.containsKey("upstreamDisposition") ? 1 : 0)
                    + (tfo.containsKey("upstreamDispositionReason") ? 1 : 0);
            if (inputs.isEmpty() && "COMPLETE".equals(completeness) && disposition != 2) {
                findings.add(new Finding("SEMANTIC_ZERO_UPSTREAM_INVALID", where,
                        "no inputs, COMPLETE, without upstreamDisposition and its reason"));
            } else if (inputs.isEmpty() && !"COMPLETE".equals(completeness)
                    && (!"UNKNOWN".equals(completeness) || disposition > 0)) {
                findings.add(new Finding("SEMANTIC_ZERO_UPSTREAM_INVALID", where,
                        "no inputs and lowered: must be UNKNOWN without a disposition"));
            } else if (!inputs.isEmpty() && disposition > 0) {
                findings.add(new Finding("SEMANTIC_ZERO_UPSTREAM_INVALID", where, "inputs and an upstreamDisposition"));
            }
            boolean viaCandidate = false;
            boolean unknownInput = false;
            for (Map<?, ?> input : inputs) {
                viaCandidate |= input.containsKey("factCandidateRef");
                unknownInput |= "UNKNOWN_INPUT".equals(input.get("kind"));
            }
            if ("COMPLETE".equals(completeness) && viaCandidate) {
                findings.add(new Finding("SEMANTIC_COVERAGE_NOT_LOWERED", where,
                        "a FIELD_REF input through a FactCandidate, yet COMPLETE"));
            }
            if ("COMPLETE".equals(completeness) && unknownInput) {
                findings.add(new Finding("SEMANTIC_COVERAGE_NOT_LOWERED", where, "an UNKNOWN_INPUT input, yet COMPLETE"));
            }
        }
        List<Object[]> lowered = new ArrayList<Object[]>();
        for (Map<?, ?> unit : index.all("sourceUnit")) {
            lowered.add(new Object[] {"sourceUnits ref " + unit.get("ref"), !"COMPLETE".equals(unit.get("analysisCompleteness")),
                    unit});
        }
        for (Map<?, ?> statement : index.all("statement")) {
            lowered.add(new Object[] {"statements ref " + statement.get("ref"),
                    !"COMPLETE".equals(statement.get("analysisCompleteness")), statement});
        }
        List<Object[]> features = new ArrayList<Object[]>();
        features.add(new Object[] {"featureCompleteness", doc.get("featureCompleteness")});
        for (Map<?, ?> unit : index.all("sourceUnit")) {
            features.add(new Object[] {"sourceUnits ref " + unit.get("ref") + " featureCompleteness",
                    unit.get("featureCompleteness")});
        }
        for (Map<?, ?> statement : index.all("statement")) {
            features.add(new Object[] {"statements ref " + statement.get("ref") + " featureCompleteness",
                    statement.get("featureCompleteness")});
        }
        for (Object[] collection : features) {
            for (Map<?, ?> feature : items(collection[1])) {
                lowered.add(new Object[] {collection[0] + " " + feature.get("feature"),
                        !"COMPLETE".equals(feature.get("status")), feature});
            }
        }
        for (Map<?, ?> tfo : index.all("tfo")) {
            lowered.add(new Object[] {"targetFieldOccurrences ref " + tfo.get("ref"),
                    !"COMPLETE".equals(tfo.get("upstreamCompleteness")), tfo});
        }
        for (Map<?, ?> node : index.all("node")) {
            Object completeness = node.get("upstreamCompleteness");
            lowered.add(new Object[] {"explainGraph.nodes ref " + node.get("ref"),
                    "PARTIAL".equals(completeness) || "UNKNOWN".equals(completeness), node});
        }
        for (Object[] item : lowered) {
            Object refs = ((Map<?, ?>) item[2]).get("diagnosticRefs");
            if ((Boolean) item[1] && !truthy(refs)) {
                findings.add(new Finding("SEMANTIC_COVERAGE_DIAGNOSTIC_MISSING", (String) item[0],
                        "lowered without a diagnostic"));
            }
        }
    }

    /** Python truthiness of a JSON value. */
    static boolean truthy(Object value) {
        if (value == null || Boolean.FALSE.equals(value)) {
            return false;
        }
        if (value instanceof List<?>) {
            return !((List<?>) value).isEmpty();
        }
        if (value instanceof Map<?, ?>) {
            return !((Map<?, ?>) value).isEmpty();
        }
        if (value instanceof String) {
            return !((String) value).isEmpty();
        }
        if (value instanceof Number) {
            return ((Number) value).longValue() != 0;
        }
        return true;
    }

    /** Section 12.3: the embedded text agrees with header.sourceEmbedding. */
    private static void checkSourceEmbedding(Map<?, ?> doc, DocumentIndex index, List<Finding> findings) {
        Object header = doc.get("header");
        Object embedding = header instanceof Map<?, ?> ? ((Map<?, ?>) header).get("sourceEmbedding") : null;
        String need = "FULL".equals(embedding) ? "DECODED_TEXT_SHA256"
                : "REDACTED".equals(embedding) ? "REDACTED_TEXT_SHA256" : null;
        for (Map<?, ?> unit : index.all("sourceUnit")) {
            String where = "sourceUnits ref " + unit.get("ref");
            Set<Object> domains = new HashSet<Object>();
            for (Map<?, ?> digest : items(unit.get("digests"))) {
                domains.add(digest.get("domain"));
            }
            if ("NONE".equals(embedding) && unit.containsKey("text")) {
                findings.add(new Finding("SEMANTIC_SOURCE_EMBEDDING_MISMATCH", where, "text under sourceEmbedding NONE"));
            }
            if (need != null && (!unit.containsKey("text") || !domains.contains(need))) {
                findings.add(new Finding("SEMANTIC_SOURCE_EMBEDDING_MISMATCH", where,
                        "sourceEmbedding " + embedding + " needs text and a " + need + " digest"));
            }
        }
    }

    /** path-v1.md: every path of an analysis context that declares sqllr-path-1 follows PATH-V1. */
    private static void checkPaths(Map<?, ?> doc, final DocumentIndex index, List<Finding> findings) {
        final Map<Long, Object> contexts = new LinkedHashMap<Long, Object>();
        for (Map<?, ?> context : items(doc.get("analysisContexts"))) {
            contexts.put(intRef(context.get("ref")), context.get("pathProfile"));
        }
        Set<Object> profiles = new HashSet<Object>(contexts.values());
        final Object fallback = !contexts.isEmpty() && profiles.size() == 1
                && profiles.contains(IdentityV1.PATH_PROFILE_V1) ? IdentityV1.PATH_PROFILE_V1 : null;
        List<Object[]> paths = new ArrayList<Object[]>();
        for (Map<?, ?> occurrence : index.all("occurrence")) {
            paths.add(new Object[] {"occurrences ref " + occurrence.get("ref") + " path", occurrence.get("path"),
                    profileOf(index, contexts, fallback, occurrence.get("statementRef"))});
        }
        for (Map<?, ?> scope : index.all("scope")) {
            if (scope.containsKey("path")) {
                paths.add(new Object[] {"scopes ref " + scope.get("ref") + " path", scope.get("path"),
                        profileOf(index, contexts, fallback, scope.get("statementRef"))});
            }
        }
        for (Map<?, ?> unit : index.all("sourceUnit")) {
            if (unit.containsKey("sitePath")) {
                paths.add(new Object[] {"sourceUnits ref " + unit.get("ref") + " sitePath", unit.get("sitePath"),
                        profileOf(index, contexts, fallback, unit.get("siteStatementRef"))});
            }
        }
        for (Map<?, ?> node : index.all("node")) {
            paths.add(new Object[] {"explainGraph.nodes ref " + node.get("ref") + " path", node.get("path"),
                    profileOf(index, contexts, fallback, node.get("statementRef"))});
        }
        for (Map<?, ?> edge : index.all("microEdge")) {
            if (edge.containsKey("referencePath")) {
                paths.add(new Object[] {"explainGraph.microEdges ref " + edge.get("ref") + " referencePath",
                        edge.get("referencePath"), profileOf(index, contexts, fallback, edge.get("statementRef"))});
            }
        }
        for (Object[] path : paths) {
            if (IdentityV1.PATH_PROFILE_V1.equals(path[2])) {
                List<String> problems = PathV1.violations(path[1]);
                if (!problems.isEmpty()) {
                    findings.add(new Finding("SEMANTIC_PATH_PROFILE_VIOLATION", (String) path[0], path[1] + ": "
                            + problems.get(0)));
                }
            }
        }
    }

    private static Object profileOf(DocumentIndex index, Map<Long, Object> contexts, Object fallback, Object statementRef) {
        Map<?, ?> statement = index.get("statement", statementRef);
        Map<?, ?> unit = statement == null ? null : index.get("sourceUnit", statement.get("sourceUnitRef"));
        Long context = unit == null ? null : intRef(unit.get("analysisContextRef"));
        return contexts.containsKey(context) ? contexts.get(context) : fallback;
    }

    static List<String> stepCodes(Object path) {
        List<String> out = new ArrayList<String>();
        if (path instanceof String) {
            for (String step : ((String) path).split("/", -1)) {
                int bracket = step.indexOf('[');
                out.add(bracket < 0 ? step : step.substring(0, bracket));
            }
        }
        return out;
    }

    static Map<?, ?> topOwner(DocumentIndex index, Map<?, ?> endpoint) {
        Set<Long> seen = new HashSet<Long>();
        while (endpoint != null && "FIELD".equals(endpoint.get("kind"))) {
            Long owner = intRef(endpoint.get("ownerRef"));
            if (owner == null || !seen.add(owner)) {
                return null;
            }
            endpoint = index.get("endpoint", owner);
        }
        return endpoint;
    }

    /** (source refs, target refs, kind) of the Fact or FactCandidate of an Occurrence. */
    static Object[] subjectEnds(DocumentIndex index, Map<?, ?> occurrence) {
        Map<?, ?> fact = index.get("fact", occurrence.get("factRef"));
        if (fact != null) {
            return new Object[] {Collections.singletonList(fact.get("sourceRef")),
                    Collections.singletonList(fact.get("targetRef")), fact.get("kind")};
        }
        Map<?, ?> candidate = index.get("factCandidate", occurrence.get("factCandidateRef"));
        if (candidate == null) {
            candidate = Collections.emptyMap();
        }
        List<List<Object>> ends = new ArrayList<List<Object>>();
        for (String side : new String[] {"source", "target"}) {
            Map<?, ?> end = candidate.get(side) instanceof Map<?, ?> ? (Map<?, ?>) candidate.get(side)
                    : Collections.emptyMap();
            if (end.containsKey("endpointRef")) {
                ends.add(Collections.singletonList(end.get("endpointRef")));
            } else {
                Object set = end.get("candidateSet");
                ends.add(new ArrayList<Object>(truthy(set) ? candidateRefs(set) : Collections.emptyList()));
            }
        }
        return new Object[] {ends.get(0), ends.get(1), candidate.get("kind")};
    }

    /**
     * fold-v1.md, Section 4.4: a COMPLETE SELECT, INSERT or CREATE statement that reads a field of a relation
     * inside a query block also asserts ROW Facts (or FactCandidates) from that relation's ROW_SET.
     */
    @SuppressWarnings("unchecked")
    private static void checkRowPropagation(DocumentIndex index, List<Finding> findings) {
        Map<Long, List<Map<?, ?>>> byStatement = new HashMap<Long, List<Map<?, ?>>>();
        for (Map<?, ?> occurrence : index.all("occurrence")) {
            Long statement = intRef(occurrence.get("statementRef"));
            List<Map<?, ?>> list = byStatement.get(statement);
            if (list == null) {
                list = new ArrayList<Map<?, ?>>();
                byStatement.put(statement, list);
            }
            list.add(occurrence);
        }
        // a routine that returns a set of rows owns a ROW_SET (spec Section 7.3): a call in FROM that reads its fields
        // reads its rows too; a routine that returns one value or one row owns none and is no row source
        Set<Long> rowSetOwners = new HashSet<Long>();
        for (Map<?, ?> endpoint : index.all("endpoint")) {
            if ("ROW_SET".equals(endpoint.get("kind")) && endpoint.get("ownerRef") != null) {
                rowSetOwners.add(intRef(endpoint.get("ownerRef")));
            }
        }
        for (Map<?, ?> statement : index.all("statement")) {
            if (!"COMPLETE".equals(statement.get("analysisCompleteness"))) {
                continue;
            }
            List<Map<?, ?>> occurrences = byStatement.get(intRef(statement.get("ref")));
            if (occurrences == null) {
                occurrences = Collections.emptyList();
            }
            boolean unresolved = false;
            for (Map<?, ?> occurrence : occurrences) {
                Object[] ends = subjectEnds(index, occurrence);
                for (int side = 0; side < 2; side++) {
                    for (Object ref : (List<Object>) ends[side]) {
                        unresolved |= index.get("endpoint", ref) == null;
                    }
                }
            }
            if (unresolved) {
                continue; // a reference that does not resolve is reported at stage REFERENCE
            }
            Set<Long> propagated = new HashSet<Long>();
            Map<Long, Object> read = new TreeMap<Long, Object>();
            for (Map<?, ?> occurrence : occurrences) {
                Object[] ends = subjectEnds(index, occurrence);
                for (Object source : (List<Object>) ends[0]) {
                    Map<?, ?> endpoint = index.get("endpoint", source);
                    if (endpoint == null) {
                        endpoint = Collections.emptyMap();
                    }
                    if ("ROW".equals(ends[2]) && "ROW_SET".equals(endpoint.get("kind"))) {
                        propagated.add(intRef(endpoint.get("ownerRef")));
                    }
                    List<String> codes = stepCodes(occurrence.get("path"));
                    boolean inBlock = false;
                    for (String code : codes) {
                        inBlock |= QUERY_BLOCK_STEPS.contains(code);
                    }
                    if ("FIELD".equals(endpoint.get("kind")) && !codes.isEmpty()
                            && QUERY_STATEMENT_ROOTS.contains(codes.get(0)) && inBlock) {
                        Map<?, ?> owner = topOwner(index, endpoint);
                        if (owner != null && (ROW_SOURCE_KINDS.contains(owner.get("kind"))
                                || ("ROUTINE".equals(owner.get("kind"))
                                && rowSetOwners.contains(intRef(owner.get("ref")))))) {
                            Long ownerRef = intRef(owner.get("ref"));
                            if (!read.containsKey(ownerRef)) {
                                read.put(ownerRef, occurrence.get("ref"));
                            }
                        }
                    }
                }
            }
            for (Map.Entry<Long, Object> entry : read.entrySet()) {
                if (!propagated.contains(entry.getKey())) {
                    findings.add(new Finding("SEMANTIC_ROW_PROPAGATION_MISSING", "statements ref " + statement.get("ref"),
                            "fields of endpoint ref " + entry.getKey() + " are read (occurrences ref " + entry.getValue()
                                    + ") but no ROW Fact leaves its ROW_SET"));
                }
            }
        }
    }

    // ---------------------------------------------------------------------------------------------
    // Spans (Sections 7.8 and 12.2)
    // ---------------------------------------------------------------------------------------------

    /**
     * The text of a source unit, already checked to be UTF-8: the line and column (in code points, 1-based) of a
     * UTF-8 offset. It keeps the bytes, the offset of every line start and the code points before every 64th byte,
     * so its size is about that of the text and a lookup reads at most 63 bytes.
     */
    static final class SourceText {
        private static final int STRIDE = 64;
        private final byte[] data;
        private final int[] lineStarts;
        private final int[] codePointsBefore;

        SourceText(byte[] data) {
            this.data = data;
            int lines = 1;
            for (byte b : data) {
                if (b == '\n') {
                    lines++;
                }
            }
            lineStarts = new int[lines];
            codePointsBefore = new int[data.length / STRIDE + 1];
            int line = 1;
            int codePoints = 0;
            for (int i = 0; i < data.length; i++) {
                if (i % STRIDE == 0) {
                    codePointsBefore[i / STRIDE] = codePoints;
                }
                if (!continuation(data[i])) {
                    codePoints++;
                }
                if (data[i] == '\n') {
                    lineStarts[line++] = i + 1;
                }
            }
            if (data.length % STRIDE == 0) {
                codePointsBefore[data.length / STRIDE] = codePoints;
            }
        }

        private static boolean continuation(byte b) {
            return (b & 0xc0) == 0x80;
        }

        private int codePointsBefore(int offset) {
            int count = codePointsBefore[offset / STRIDE];
            for (int i = offset - offset % STRIDE; i < offset; i++) {
                if (!continuation(data[i])) {
                    count++;
                }
            }
            return count;
        }

        /** {line, column} of a UTF-8 offset, or null when it is outside the text or inside a character. */
        long[] position(long offset) {
            if (offset < 0 || offset > data.length || (offset < data.length && continuation(data[(int) offset]))) {
                return null;
            }
            int at = (int) offset;
            int low = 0;
            int high = lineStarts.length - 1;
            while (low < high) {
                int mid = (low + high + 1) >>> 1;
                if (lineStarts[mid] <= at) {
                    low = mid;
                } else {
                    high = mid - 1;
                }
            }
            return new long[] {low + 1, codePointsBefore(at) - codePointsBefore(lineStarts[low]) + 1};
        }
    }

    private SourceText sourceText(Map<?, ?> unit, List<String> notes) {
        if (!"NAMED".equals(unit.get("identityKind"))) {
            return null;
        }
        Object namespace = unit.get("namespace");
        Object name = unit.get("logicalName");
        if (!(namespace instanceof String) || !(name instanceof String)) {
            return null;
        }
        byte[] data = sources.read((String) namespace, (String) name);
        if (data == null) {
            notes.add("source unit ref " + unit.get("ref") + ": " + name + " not available; spans not checked against text");
            return null;
        }
        String digest = sha256(data);
        Map<Object, Object> declared = new HashMap<Object, Object>();
        for (Map<?, ?> d : items(unit.get("digests"))) {
            declared.put(d.get("domain"), d.get("value"));
        }
        for (String domain : new String[] {"RAW_BYTES_SHA256", "DECODED_TEXT_SHA256"}) {
            if (declared.containsKey(domain) && !digest.equals(declared.get(domain))) {
                notes.add("source unit ref " + unit.get("ref") + ": " + domain + " does not match " + name
                        + "; spans not checked against text");
                return null;
            }
        }
        if (data.length >= 3 && (data[0] & 0xff) == 0xef && (data[1] & 0xff) == 0xbb && (data[2] & 0xff) == 0xbf) {
            return null;
        }
        try {
            CharsetDecoder decoder = StandardCharsets.UTF_8.newDecoder().onMalformedInput(CodingErrorAction.REPORT)
                    .onUnmappableCharacter(CodingErrorAction.REPORT);
            ByteBuffer in = ByteBuffer.wrap(data);
            CharBuffer out = CharBuffer.allocate(4096);
            CoderResult result;
            do {
                // through Buffer: CharBuffer.clear() exists only from Java 9, and a build on a newer JDK without
                // --release 8 would bind to it (NoSuchMethodError on Java 8)
                ((java.nio.Buffer) out).clear();
                result = decoder.decode(in, out, true);
                if (result.isError()) {
                    result.throwException();
                }
            } while (result.isOverflow());
            do {
                ((java.nio.Buffer) out).clear();
                result = decoder.flush(out);
            } while (result.isOverflow());
            return new SourceText(data);
        } catch (CharacterCodingException e) {
            notes.add("source unit ref " + unit.get("ref") + ": " + name + " is not UTF-8; spans not checked against text");
            return null;
        }
    }

    private static String sha256(byte[] data) {
        try {
            byte[] digest = MessageDigest.getInstance("SHA-256").digest(data);
            StringBuilder out = new StringBuilder();
            for (byte b : digest) {
                out.append(Character.forDigit((b >> 4) & 0xf, 16)).append(Character.forDigit(b & 0xf, 16));
            }
            return out.toString();
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e);
        }
    }

    private static Long offsetOf(Object position) {
        return position instanceof Map<?, ?> ? intRef(((Map<?, ?>) position).get("utf8ByteOffset0")) : null;
    }

    private static void checkPosition(SourceText text, Object position, String where, List<Finding> findings) {
        Long offset = offsetOf(position);
        if (offset == null || text == null) {
            return;
        }
        long[] expected = text.position(offset);
        if (expected == null) {
            findings.add(new Finding("SEMANTIC_INVALID_SPAN", where, "offset " + offset
                    + " is outside the text or inside a character"));
            return;
        }
        Map<?, ?> p = (Map<?, ?>) position;
        Long line = intRef(p.get("line1"));
        Long column = intRef(p.get("column1"));
        if (line == null || column == null || line != expected[0] || column != expected[1]) {
            findings.add(new Finding("SEMANTIC_INVALID_SPAN", where, "line/column " + p.get("line1") + "/"
                    + p.get("column1") + " disagree with offset " + offset));
        }
    }

    private static void checkSpan(Map<Long, SourceText> texts, Object unitRef, Object start, Object end, String where,
                                  List<Finding> findings) {
        Long a = offsetOf(start);
        Long b = offsetOf(end);
        if (a != null && b != null && b < a) {
            findings.add(new Finding("SEMANTIC_INVALID_SPAN", where, "ends before it starts"));
            return;
        }
        SourceText text = texts.get(intRef(unitRef));
        checkPosition(text, start, where + ".start", findings);
        checkPosition(text, end, where + ".end", findings);
    }

    private void checkSpans(DocumentIndex index, List<Finding> findings, List<String> notes) {
        Map<Long, SourceText> texts = new HashMap<Long, SourceText>();
        for (Map<?, ?> unit : index.all("sourceUnit")) {
            texts.put(intRef(unit.get("ref")), sourceText(unit, notes));
        }
        for (Map<?, ?> statement : index.all("statement")) {
            checkSpan(texts, statement.get("sourceUnitRef"), statement.get("start"), statement.get("end"),
                    "statements ref " + statement.get("ref"), findings);
        }
        for (Map<?, ?> node : index.all("node")) {
            Map<?, ?> span = node.get("span") instanceof Map<?, ?> ? (Map<?, ?>) node.get("span") : Collections.emptyMap();
            checkSpan(texts, span.get("sourceUnitRef"), span.get("start"), span.get("end"),
                    "explainGraph.nodes ref " + node.get("ref") + " span", findings);
        }
        for (Map<?, ?> edge : index.all("microEdge")) {
            Map<?, ?> statement = index.get("statement", edge.get("statementRef"));
            if (edge.containsKey("referenceStart")) {
                checkPosition(texts.get(statement == null ? null : intRef(statement.get("sourceUnitRef"))),
                        edge.get("referenceStart"), "explainGraph.microEdges ref " + edge.get("ref") + " referenceStart",
                        findings);
            }
        }
        for (Map<?, ?> diagnostic : index.all("diagnostic")) {
            if (diagnostic.get("span") instanceof Map<?, ?>) {
                Map<?, ?> span = (Map<?, ?>) diagnostic.get("span");
                checkSpan(texts, span.get("sourceUnitRef"), span.get("start"), span.get("end"),
                        "diagnostics ref " + diagnostic.get("ref") + " span", findings);
            }
        }
    }

    /** canonical-json-v1 Section 5 and Section 7.7, item 4: the columns of one result set carry 0..n-1. */
    private static void checkColumnOrdinals(DocumentIndex index, List<Finding> findings) {
        Map<Long, List<Object>> columns = new TreeMap<Long, List<Object>>();
        for (Map<?, ?> node : index.all("node")) {
            Long owner = intRef(node.get("ownerRef"));
            if ("FIELD".equals(node.get("kind")) && owner != null) {
                List<Object> list = columns.get(owner);
                if (list == null) {
                    list = new ArrayList<Object>();
                    columns.put(owner, list);
                }
                list.add(node.get("ordinal"));
            }
        }
        for (Map.Entry<Long, List<Object>> entry : columns.entrySet()) {
            List<Long> ordinals = new ArrayList<Long>();
            for (Object ordinal : entry.getValue()) {
                if (ordinal instanceof Boolean) {
                    ordinals.add(((Boolean) ordinal).booleanValue() ? 1L : 0L); // Python: bool is an int
                } else if (intRef(ordinal) != null) {
                    ordinals.add(intRef(ordinal));
                }
            }
            Collections.sort(ordinals);
            boolean ok = ordinals.size() == entry.getValue().size();
            for (int i = 0; ok && i < ordinals.size(); i++) {
                ok = ordinals.get(i) == i;
            }
            if (!ok) {
                findings.add(new Finding("SEMANTIC_ARRAY_KIND_VIOLATION", "explainGraph.nodes owner " + entry.getKey(),
                        "column ordinals " + entry.getValue() + " are not 0..n-1"));
            }
        }
    }

    /**
     * fold-v1, Sections 4.3 and 7.1: a candidate set decided by another reference. decidedBy appears in
     * explainGraph.candidateSets, naming a deciding set of the graph, and at the ends of FactCandidates, naming a set of
     * the document's candidateSets; never on a set of the document's candidateSets. The deciding set is not itself
     * decided; the alignment pairs every candidate exactly once with an alternative of the deciding set, each
     * alternative at most once; a COMPLETE decided set needs a COMPLETE deciding set whose every alternative is paired.
     */
    private static void decidedReferences(DocumentIndex index, List<Finding> findings) {
        Map<Long, Map<?, ?>> graphSets = new java.util.TreeMap<Long, Map<?, ?>>();
        for (Map<?, ?> set : DocumentIndex.items(index.graph().get("candidateSets"))) {
            Long ref = DocumentIndex.intRef(set.get("ref"));
            if (ref != null) {
                graphSets.put(ref, set);
            }
        }
        Map<Long, Map<?, ?>> rootSets = new java.util.TreeMap<Long, Map<?, ?>>();
        for (Map<?, ?> set : DocumentIndex.items(index.document().get("candidateSets"))) {
            Long ref = DocumentIndex.intRef(set.get("ref"));
            if (ref != null) {
                rootSets.put(ref, set);
            }
            if (set.containsKey("decidedBy")) {
                findings.add(new Finding("SEMANTIC_CANDIDATE_SET_INVALID", "candidate set ref " + set.get("ref"),
                        "decidedBy on a set of the document's candidateSets"));
            }
        }
        List<Object[]> decided = new ArrayList<Object[]>();
        for (Map<?, ?> set : graphSets.values()) {
            decided.add(new Object[] {set, graphSets});
        }
        for (Map<?, ?> candidate : index.all("factCandidate")) {
            for (String side : new String[] {"source", "target"}) {
                Object end = candidate.get(side);
                Object set = end instanceof Map<?, ?> ? ((Map<?, ?>) end).get("candidateSet") : null;
                if (set instanceof Map<?, ?>) {
                    decided.add(new Object[] {set, rootSets});
                }
            }
        }
        for (Object[] item : decided) {
            Map<?, ?> set = (Map<?, ?>) item[0];
            @SuppressWarnings("unchecked")
            Map<Long, Map<?, ?>> pool = (Map<Long, Map<?, ?>>) item[1];
            if (!(set.get("decidedBy") instanceof Map<?, ?>)) {
                continue;
            }
            Map<?, ?> decidedBy = (Map<?, ?>) set.get("decidedBy");
            Map<?, ?> deciding = pool.get(DocumentIndex.intRef(decidedBy.get("candidateSetRef")));
            List<Long> members = refs(set.get("candidateRefs"));
            List<Long> alternatives = deciding == null ? Collections.<Long>emptyList() : refs(deciding.get("candidateRefs"));
            List<Long> paired = new ArrayList<Long>();
            List<Long> chosen = new ArrayList<Long>();
            for (Map<?, ?> pair : DocumentIndex.items(decidedBy.get("alignment"))) {
                paired.add(DocumentIndex.intRef(pair.get("candidateRef")));
                chosen.add(DocumentIndex.intRef(pair.get("alternativeRef")));
            }
            String problem = null;
            if (deciding == null || deciding == set || deciding.containsKey("decidedBy")) {
                problem = pool == graphSets ? "decidedBy names no deciding set of the graph (one without decidedBy)"
                        : "decidedBy of a FactCandidate end names no set of the document's candidateSets";
            } else if (!sortedCopy(paired).equals(sortedCopy(members))) {
                problem = "the alignment does not pair every candidate exactly once";
            } else if (new java.util.HashSet<Long>(chosen).size() != chosen.size()
                    || !alternatives.containsAll(chosen)) {
                problem = "an alternative of the alignment is not one of the deciding set's, or is paired twice";
            } else if ("COMPLETE".equals(set.get("membership")) && (!"COMPLETE".equals(deciding.get("membership"))
                    || !new java.util.HashSet<Long>(chosen).equals(new java.util.HashSet<Long>(alternatives)))) {
                problem = "membership COMPLETE, but the deciding set is INCOMPLETE or an alternative has no candidate";
            }
            if (problem != null) {
                findings.add(new Finding("SEMANTIC_CANDIDATE_SET_INVALID", "candidate set ref " + set.get("ref"),
                        problem));
            }
        }
    }

    private static List<Long> refs(Object list) {
        List<Long> out = new ArrayList<Long>();
        if (list instanceof List<?>) {
            for (Object r : (List<?>) list) {
                out.add(DocumentIndex.intRef(r));
            }
        }
        return out;
    }

    private static List<Long> sortedCopy(List<Long> list) {
        List<Long> out = new ArrayList<Long>();
        for (Long l : list) {
            out.add(l == null ? Long.valueOf(Long.MIN_VALUE) : l);
        }
        Collections.sort(out);
        return out;
    }
}