001package gudusoft.gsqlparser.lineage.v2.validation;
002
003import gudusoft.gsqlparser.lineage.v2.SqllrResources;
004import gudusoft.gsqlparser.lineage.v2.json.CanonicalJson;
005
006import java.math.BigInteger;
007import java.util.ArrayList;
008import java.util.Arrays;
009import java.util.Collections;
010import java.util.HashMap;
011import java.util.HashSet;
012import java.util.IdentityHashMap;
013import java.util.Iterator;
014import java.util.LinkedHashSet;
015import java.util.List;
016import java.util.Map;
017import java.util.Set;
018import java.util.regex.Pattern;
019
020/**
021 * A JSON Schema Draft 2020-12 validator for the keywords the SQL-LR lineage document schema uses, with no
022 * third-party dependency.
023 *
024 * <p>Supported: {@code $ref} (to the root {@code #} or a top-level {@code #/$defs/...} only), {@code type},
025 * {@code enum}, {@code const}, {@code required}, {@code properties}, {@code additionalProperties},
026 * {@code items}, {@code propertyNames}, {@code allOf}, {@code anyOf}, {@code oneOf}, {@code not},
027 * {@code if}/{@code then}/{@code else}, {@code unevaluatedProperties}, {@code pattern}, {@code minItems},
028 * {@code minLength}, {@code minimum}, {@code maximum}, and boolean schemas. {@code format} is an annotation and
029 * asserts nothing, which is the Draft 2020-12 default and what the reference runner does. Annotation keywords
030 * ({@code description}, {@code title}, {@code $schema}, {@code $id}, {@code $comment}, {@code examples},
031 * {@code default}, {@code x-*}, and {@code $defs} at the root) are ignored. <b>Any other keyword, a nested
032 * {@code $defs}, a {@code $ref} cycle, or a pattern outside the supported regex subset makes the constructor
033 * throw</b>, so a schema change that needs more of the specification cannot be validated silently wrong.</p>
034 *
035 * <p>{@code unevaluatedProperties} follows the 2020-12 annotation model: a property counts as evaluated when
036 * {@code properties} or {@code additionalProperties} of the same schema object, or of a subschema applied in
037 * place that validated ({@code $ref}, {@code allOf}, {@code anyOf}, {@code oneOf}, {@code if}/{@code then}/
038 * {@code else}, a nested {@code unevaluatedProperties}), covered it. Every branch of {@code anyOf} is
039 * evaluated for its annotations.</p>
040 *
041 * <p>Errors form the tree the reference runner inspects (python-jsonschema): an error per failing keyword (per
042 * missing member for {@code required}), nested errors of the subschemas descended into, and for a failing
043 * {@code anyOf} or {@code oneOf} the errors of every branch as its context. A subschema reached twice at one
044 * instance location is reported once. Patterns are searched (not anchored unless they anchor themselves), with
045 * Python's {@code re} meaning of {@code \s} and {@code $}.</p>
046 *
047 * <p>The validator copies the schema and is immutable; one instance may serve concurrent callers.</p>
048 *
049 * @since 4.2.17
050 */
051public final class SchemaValidator {
052
053    /** One validation error: the failing keyword, its schema object, the instance and where it is. */
054    public static final class SchemaError {
055        private final String keyword;
056        private final Map<?, ?> schema;
057        private final Object instance;
058        private final List<Object> path;
059        private final String message;
060        private final List<SchemaError> context;
061
062        SchemaError(String keyword, Map<?, ?> schema, Object instance, List<Object> path, String message,
063                    List<SchemaError> context) {
064            this.keyword = keyword;
065            this.schema = schema;
066            this.instance = instance;
067            this.path = Collections.unmodifiableList(new ArrayList<Object>(path));
068            this.message = message;
069            this.context = context == null ? Collections.<SchemaError>emptyList() : Collections.unmodifiableList(context);
070        }
071
072        /** The keyword that failed, such as {@code enum}; {@code false} for a false schema. */
073        public String getKeyword() {
074            return keyword;
075        }
076
077        /** The schema object holding the keyword (empty for a false schema). */
078        public Map<?, ?> getSchema() {
079            return schema;
080        }
081
082        public Object getInstance() {
083            return instance;
084        }
085
086        /** The instance location: member names and array indexes from the root. */
087        public List<Object> getPath() {
088            return path;
089        }
090
091        public String getMessage() {
092            return message;
093        }
094
095        /** For {@code anyOf} and {@code oneOf}: the errors of every branch. */
096        public List<SchemaError> getContext() {
097            return context;
098        }
099
100        @Override
101        public String toString() {
102            StringBuilder where = new StringBuilder("$");
103            for (Object step : path) {
104                where.append(step instanceof String ? "." + step : "[" + step + "]");
105            }
106            return where + ": " + keyword + ": " + message;
107        }
108    }
109
110    private static final Set<String> SUPPORTED = new HashSet<String>(Arrays.asList(
111            "$ref", "type", "enum", "const", "required", "properties", "additionalProperties", "items", "propertyNames",
112            "allOf", "anyOf", "oneOf", "not", "if", "then", "else", "unevaluatedProperties", "pattern", "minItems",
113            "minLength", "minimum", "maximum", "format"));
114    private static final Set<String> ANNOTATIONS = new HashSet<String>(Arrays.asList(
115            "description", "title", "$schema", "$id", "$comment", "examples", "default"));
116    /** Keywords whose value is one schema. */
117    private static final Set<String> ONE_SCHEMA = new HashSet<String>(Arrays.asList(
118            "additionalProperties", "items", "propertyNames", "not", "if", "then", "else", "unevaluatedProperties"));
119    /** Keywords whose value is a list of schemas. */
120    private static final Set<String> SCHEMA_LIST = new HashSet<String>(Arrays.asList("allOf", "anyOf", "oneOf"));
121    private static final Set<String> TYPES = new HashSet<String>(Arrays.asList(
122            "object", "array", "string", "integer", "number", "boolean", "null"));
123
124    /** What Python's {@code re} matches with {@code \s} in a str pattern. */
125    private static final String PYTHON_WHITESPACE =
126            "\\t\\n\\x0B\\f\\r\\x1C-\\x1F \\x85\\xA0\\u1680\\u2000-\\u200A\\u2028\\u2029\\u202F\\u205F\\u3000";
127
128    /**
129     * Java's regex engine recurses once per repetition of a group, so {@code (\.[a-z]+)*} over a long string
130     * exhausts the thread stack where Python's engine does not. Each pattern of the schema that repeats a group
131     * is listed here with an equivalent possessive form, which matches iteratively. They are equivalent because
132     * every repeated group starts with a separator its body cannot match, so giving back characters never helps.
133     * A pattern that repeats a group and is not listed is refused, so a schema change needs a review here.
134     */
135    private static final Map<String, String> POSSESSIVE = new HashMap<String, String>();
136
137    static {
138        POSSESSIVE.put("^(0|[1-9][0-9]*)\\.(0|[1-9][0-9]*)\\.(0|[1-9][0-9]*)(-[0-9A-Za-z-]+(\\.[0-9A-Za-z-]+)*)?$",
139                "^(0|[1-9][0-9]*)\\.(0|[1-9][0-9]*)\\.(0|[1-9][0-9]*)(-[0-9A-Za-z-]+(?:\\.[0-9A-Za-z-]++)*+)?$");
140        POSSESSIVE.put("^0\\.1\\.(0|[1-9][0-9]*)(-[0-9A-Za-z-]+(\\.[0-9A-Za-z-]+)*)?$",
141                "^0\\.1\\.(0|[1-9][0-9]*)(-[0-9A-Za-z-]+(?:\\.[0-9A-Za-z-]++)*+)?$");
142        POSSESSIVE.put("^([a-z][a-z0-9+.-]*:[^\\s]+|[a-z][a-z0-9-]*(\\.[a-z0-9-]+)+)$",
143                "^([a-z][a-z0-9+.-]*:[^\\s]+|[a-z][a-z0-9-]*(?:\\.[a-z0-9-]++)++)$");
144        POSSESSIVE.put("^[a-z][a-z0-9]*([._-][a-z0-9]+)*$", "^[a-z][a-z0-9]*(?:[._-][a-z0-9]++)*+$");
145    }
146
147    private final Object root;
148    private final Map<?, ?> defs;
149    /** Every pattern of the schema, compiled at construction; read-only afterwards. */
150    private final Map<String, Pattern> patterns = new HashMap<String, Pattern>();
151
152    /**
153     * A validator for a parsed schema (an object or a boolean), copied so later changes to the argument have no
154     * effect.
155     *
156     * @throws IllegalStateException when the schema uses a keyword this validator does not implement, a
157     *                               {@code $ref} it cannot resolve, a {@code $ref} cycle, or a pattern outside
158     *                               the supported regex subset
159     */
160    public SchemaValidator(Object schema) {
161        if (!(schema instanceof Map<?, ?>) && !(schema instanceof Boolean)) {
162            throw new IllegalStateException("the schema is not an object or a boolean");
163        }
164        this.root = CanonicalJson.immutableCopy(schema);
165        Object defsValue = root instanceof Map<?, ?> ? ((Map<?, ?>) root).get("$defs") : null;
166        if (defsValue != null && !(defsValue instanceof Map<?, ?>)) {
167            throw new IllegalStateException("$defs is not an object");
168        }
169        this.defs = defsValue == null ? Collections.emptyMap() : (Map<?, ?>) defsValue;
170        Map<String, Set<String>> refs = new HashMap<String, Set<String>>();
171        refs.put("#", checkSupported(root, "#", true));
172        for (Map.Entry<?, ?> def : defs.entrySet()) {
173            refs.put("#/$defs/" + def.getKey(), checkSupported(def.getValue(), "#/$defs/" + def.getKey(), false));
174        }
175        checkAcyclic(refs);
176    }
177
178    /** A validator for the lineage document schema this library ships. */
179    public static SchemaValidator lineageDocument() {
180        return Standard.INSTANCE;
181    }
182
183    private static final class Standard {
184        static final SchemaValidator INSTANCE = new SchemaValidator(SqllrResources.lineageDocumentSchema());
185    }
186
187    /**
188     * Checks every keyword reachable through schema-valued positions and returns the {@code $ref} targets met.
189     * Values of annotation keywords ({@code examples}, {@code default}, ...) and of {@code enum} and
190     * {@code const} are data, not schemas, and are not walked.
191     */
192    private Set<String> checkSupported(Object schema, String where, boolean isRoot) {
193        Set<String> targets = new LinkedHashSet<String>();
194        List<Object[]> stack = new ArrayList<Object[]>();
195        stack.add(new Object[] {schema, where});
196        while (!stack.isEmpty()) {
197            Object[] top = stack.remove(stack.size() - 1);
198            Object node = top[0];
199            String at = (String) top[1];
200            if (node instanceof Boolean) {
201                continue;
202            }
203            if (!(node instanceof Map<?, ?>)) {
204                throw new IllegalStateException("not a schema at " + at);
205            }
206            for (Map.Entry<?, ?> entry : ((Map<?, ?>) node).entrySet()) {
207                String keyword = (String) entry.getKey();
208                Object value = entry.getValue();
209                String path = at + "/" + keyword;
210                if ("$defs".equals(keyword)) {
211                    if (!(isRoot && node == schema)) {
212                        throw new IllegalStateException("a nested $defs is not supported at " + at);
213                    }
214                    continue;
215                }
216                if (ANNOTATIONS.contains(keyword) || keyword.startsWith("x-")) {
217                    continue;
218                }
219                if (!SUPPORTED.contains(keyword)) {
220                    throw new IllegalStateException("unsupported JSON Schema keyword " + keyword + " at " + at);
221                }
222                if ("$ref".equals(keyword)) {
223                    resolve(value, at);
224                    targets.add((String) value);
225                } else if ("pattern".equals(keyword)) {
226                    if (!(value instanceof String)) {
227                        throw new IllegalStateException("pattern is not a string at " + at);
228                    }
229                    patterns.put((String) value, compile((String) value));
230                } else if ("type".equals(keyword)) {
231                    for (Object type : value instanceof List<?> ? (List<?>) value : Collections.singletonList(value)) {
232                        if (!TYPES.contains(type)) {
233                            throw new IllegalStateException("unknown type " + type + " at " + at);
234                        }
235                    }
236                } else if ("properties".equals(keyword)) {
237                    for (Map.Entry<?, ?> property : ((Map<?, ?>) value).entrySet()) {
238                        stack.add(new Object[] {property.getValue(), path + "/" + property.getKey()});
239                    }
240                } else if (ONE_SCHEMA.contains(keyword)) {
241                    stack.add(new Object[] {value, path});
242                } else if (SCHEMA_LIST.contains(keyword)) {
243                    List<?> subs = (List<?>) value;
244                    for (int i = 0; i < subs.size(); i++) {
245                        stack.add(new Object[] {subs.get(i), path + "/" + i});
246                    }
247                }
248            }
249        }
250        return targets;
251    }
252
253    /**
254     * Validation recurses along the schema, so a {@code $ref} cycle (the root {@code #} included) would let a
255     * deep instance exhaust the thread stack. The lineage document schema has none; refuse a schema that does.
256     */
257    private static void checkAcyclic(Map<String, Set<String>> edges) {
258        Map<String, Integer> state = new HashMap<String, Integer>();
259        for (String start : edges.keySet()) {
260            if (state.containsKey(start)) {
261                continue;
262            }
263            List<Object[]> stack = new ArrayList<Object[]>();
264            stack.add(new Object[] {start, edges.get(start).iterator()});
265            state.put(start, 1);
266            while (!stack.isEmpty()) {
267                Object[] top = stack.get(stack.size() - 1);
268                @SuppressWarnings("unchecked")
269                Iterator<String> next = (Iterator<String>) top[1];
270                if (!next.hasNext()) {
271                    state.put((String) top[0], 2);
272                    stack.remove(stack.size() - 1);
273                    continue;
274                }
275                String target = next.next();
276                Integer seen = state.get(target);
277                if (seen != null && seen == 1) {
278                    throw new IllegalStateException("the schema has a $ref cycle through " + target);
279                }
280                if (seen == null && edges.containsKey(target)) {
281                    state.put(target, 1);
282                    stack.add(new Object[] {target, edges.get(target).iterator()});
283                }
284            }
285        }
286    }
287
288    private Object resolve(Object ref, String where) {
289        if (!(ref instanceof String)) {
290            throw new IllegalStateException("$ref is not a string at " + where);
291        }
292        String text = (String) ref;
293        if ("#".equals(text)) {
294            return root;
295        }
296        if (text.startsWith("#/$defs/") && defs.containsKey(text.substring("#/$defs/".length()))) {
297            return defs.get(text.substring("#/$defs/".length()));
298        }
299        throw new IllegalStateException("unresolvable $ref " + text + " at " + where);
300    }
301
302    /**
303     * Compiles a pattern to Python {@code re} search semantics. Only a subset that means the same in both
304     * engines is accepted: literal characters; escaped metacharacters; {@code \s} (translated to Python's
305     * whitespace set), {@code \t \n \r \f}; character classes without nested classes or {@code &&}; groups
306     * {@code ( )} and {@code (?: )}; the quantifiers {@code * + ? {n} {n,} {n,m}} and their lazy forms;
307     * anchors {@code ^ $} ({@code $} under {@code UNIX_LINES}: the end or before a final {@code \n}); {@code |};
308     * {@code .} (not {@code \n}).
309     */
310    static Pattern compile(String source) {
311        checkRegexSubset(source);
312        String rewritten = POSSESSIVE.containsKey(source) ? POSSESSIVE.get(source) : source;
313        String translated = rewritten.replace("[^\\s]", "[^" + PYTHON_WHITESPACE + "]")
314                .replace("\\s", "[" + PYTHON_WHITESPACE + "]");
315        return Pattern.compile(translated, Pattern.UNIX_LINES);
316    }
317
318    private static final String METACHARACTERS = ".^$*+?()[]{}|\\/-";
319
320    private static void checkRegexSubset(String source) {
321        boolean atom = false; // whether a quantifier may follow
322        boolean repeatedGroup = false;
323        int depth = 0;
324        for (int i = 0; i < source.length(); i++) {
325            char c = source.charAt(i);
326            if (c == '\\') {
327                if (i + 1 >= source.length()) {
328                    throw unsupported(source, "a trailing backslash");
329                }
330                char e = source.charAt(++i);
331                if (METACHARACTERS.indexOf(e) < 0 && "stnrf".indexOf(e) < 0) {
332                    throw unsupported(source, "the escape \\" + e);
333                }
334                atom = true;
335            } else if (c == '[') {
336                i = classEnd(source, i);
337                atom = true;
338            } else if (c == '(') {
339                if (source.startsWith("(?", i) && !source.startsWith("(?:", i)) {
340                    throw unsupported(source, "a (? group other than (?:");
341                }
342                if (source.startsWith("(?:", i)) {
343                    i += 2;
344                }
345                depth++;
346                atom = false;
347            } else if (c == ')') {
348                if (--depth < 0) {
349                    throw unsupported(source, "an unbalanced )");
350                }
351                atom = true;
352                if (i + 1 < source.length() && "*+{".indexOf(source.charAt(i + 1)) >= 0) {
353                    repeatedGroup = true;
354                }
355            } else if (c == '*' || c == '+' || c == '?') {
356                if (!atom) {
357                    throw unsupported(source, "a quantifier without an atom");
358                }
359                if (i + 1 < source.length() && source.charAt(i + 1) == '+') {
360                    throw unsupported(source, "a possessive quantifier");
361                }
362                if (i + 1 < source.length() && source.charAt(i + 1) == '?') {
363                    i++;
364                }
365                atom = false;
366            } else if (c == '{') {
367                int close = source.indexOf('}', i);
368                if (!atom || close < 0 || !source.substring(i + 1, close).matches("[0-9]+(,[0-9]*)?")) {
369                    throw unsupported(source, "a { that is not a {n}, {n,} or {n,m} quantifier");
370                }
371                i = close;
372                if (i + 1 < source.length() && source.charAt(i + 1) == '+') {
373                    throw unsupported(source, "a possessive quantifier");
374                }
375                if (i + 1 < source.length() && source.charAt(i + 1) == '?') {
376                    i++;
377                }
378                atom = false;
379            } else if (c == '}' || c == ']') {
380                throw unsupported(source, "an unescaped " + c);
381            } else if (c == '^' || c == '$' || c == '|') {
382                atom = false;
383            } else {
384                atom = true;
385            }
386        }
387        if (depth != 0) {
388            throw unsupported(source, "an unbalanced (");
389        }
390        if (repeatedGroup && !POSSESSIVE.containsKey(source)) {
391            throw new IllegalStateException("pattern repeats a group and has no reviewed iterative form: " + source);
392        }
393    }
394
395    /** The index of the {@code ]} closing the class that starts at {@code start}. */
396    private static int classEnd(String source, int start) {
397        int i = start + 1;
398        if (i < source.length() && source.charAt(i) == '^') {
399            i++;
400        }
401        if (i < source.length() && source.charAt(i) == ']') {
402            throw unsupported(source, "a class starting with ]");
403        }
404        for (; i < source.length(); i++) {
405            char c = source.charAt(i);
406            if (c == '\\') {
407                if (i + 1 >= source.length()) {
408                    throw unsupported(source, "a trailing backslash");
409                }
410                char e = source.charAt(++i);
411                if (METACHARACTERS.indexOf(e) < 0 && "stnrf".indexOf(e) < 0) {
412                    throw unsupported(source, "the escape \\" + e + " in a class");
413                }
414            } else if (c == '[') {
415                throw unsupported(source, "a [ inside a class (a nested class in Java)");
416            } else if (c == '&' && i + 1 < source.length() && source.charAt(i + 1) == '&') {
417                throw unsupported(source, "&& inside a class (an intersection in Java)");
418            } else if (c == ']') {
419                return i;
420            }
421        }
422        throw unsupported(source, "an unterminated class");
423    }
424
425    private static IllegalStateException unsupported(String source, String what) {
426        return new IllegalStateException("pattern " + source + " uses " + what
427                + ", outside the regex subset that Python and Java read alike");
428    }
429
430    // ---------------------------------------------------------------------------------------------
431    // Public entry points
432    // ---------------------------------------------------------------------------------------------
433
434    /** Every error of an instance against the schema; empty when it is valid. */
435    public List<SchemaError> errors(Object instance) {
436        Run run = new Run();
437        List<SchemaError> out = new ArrayList<SchemaError>();
438        if (!run.evaluate(instance, root).valid) {
439            run.report(instance, root, new ArrayList<Object>(), out);
440        }
441        return out;
442    }
443
444    /** True when the instance is valid against the schema. */
445    public boolean isValid(Object instance) {
446        return new Run().evaluate(instance, root).valid;
447    }
448
449    /**
450     * Every error of an instance against one definition of the schema, such as {@code Fact}.
451     *
452     * @throws IllegalArgumentException when the schema has no such definition
453     */
454    public List<SchemaError> errors(Object instance, String definition) {
455        Object schema = defs.get(definition);
456        if (schema == null) {
457            throw new IllegalArgumentException("no definition " + definition);
458        }
459        Run run = new Run();
460        List<SchemaError> out = new ArrayList<SchemaError>();
461        if (!run.evaluate(instance, schema).valid) {
462            run.report(instance, schema, new ArrayList<Object>(), out);
463        }
464        return out;
465    }
466
467    /**
468     * True when the instance is valid against one definition of the schema, such as {@code Fact}.
469     *
470     * @throws IllegalArgumentException when the schema has no such definition
471     */
472    public boolean isValid(Object instance, String definition) {
473        Object schema = defs.get(definition);
474        if (schema == null) {
475            throw new IllegalArgumentException("no definition " + definition);
476        }
477        return new Run().evaluate(instance, schema).valid;
478    }
479
480    // ---------------------------------------------------------------------------------------------
481    // Evaluation: validity and evaluated properties
482    // ---------------------------------------------------------------------------------------------
483
484    private static final class Outcome {
485        static final Outcome INVALID = new Outcome(false, Collections.<String>emptySet());
486        static final Outcome VALID_NONE = new Outcome(true, Collections.<String>emptySet());
487
488        final boolean valid;
489        /** For an object instance: the properties this schema evaluated (when valid). */
490        final Set<String> evaluated;
491
492        Outcome(boolean valid, Set<String> evaluated) {
493            this.valid = valid;
494            this.evaluated = evaluated;
495        }
496    }
497
498    private static boolean isObject(Object value) {
499        return value instanceof Map<?, ?>;
500    }
501
502    private static boolean isArray(Object value) {
503        return value instanceof List<?>;
504    }
505
506    private static boolean isInteger(Object value) {
507        return value instanceof Long || value instanceof Integer || value instanceof Short || value instanceof Byte
508                || value instanceof BigInteger;
509    }
510
511    private static boolean isType(Object value, String type) {
512        if ("object".equals(type)) {
513            return isObject(value);
514        }
515        if ("array".equals(type)) {
516            return isArray(value);
517        }
518        if ("string".equals(type)) {
519            return value instanceof String;
520        }
521        if ("integer".equals(type) || "number".equals(type)) {
522            return isInteger(value);
523        }
524        if ("boolean".equals(type)) {
525            return value instanceof Boolean;
526        }
527        return value == null; // "null"
528    }
529
530    /** JSON equality: integers by value whatever their Java type, booleans distinct from numbers. */
531    static boolean jsonEquals(Object a, Object b) {
532        if (isInteger(a) && isInteger(b)) {
533            return new BigInteger(a.toString()).equals(new BigInteger(b.toString()));
534        }
535        if (a instanceof Map<?, ?> && b instanceof Map<?, ?>) {
536            Map<?, ?> x = (Map<?, ?>) a;
537            Map<?, ?> y = (Map<?, ?>) b;
538            if (x.size() != y.size()) {
539                return false;
540            }
541            for (Map.Entry<?, ?> entry : x.entrySet()) {
542                if (!y.containsKey(entry.getKey()) || !jsonEquals(entry.getValue(), y.get(entry.getKey()))) {
543                    return false;
544                }
545            }
546            return true;
547        }
548        if (a instanceof List<?> && b instanceof List<?>) {
549            List<?> x = (List<?>) a;
550            List<?> y = (List<?>) b;
551            if (x.size() != y.size()) {
552                return false;
553            }
554            for (int i = 0; i < x.size(); i++) {
555                if (!jsonEquals(x.get(i), y.get(i))) {
556                    return false;
557                }
558            }
559            return true;
560        }
561        return a == null ? b == null : a.equals(b);
562    }
563
564    /** A memo key for a scalar instance: its value, integers normalized to Long where they fit. */
565    private static Object scalarKey(Object value) {
566        if (value instanceof Integer || value instanceof Short || value instanceof Byte) {
567            return Long.valueOf(((Number) value).longValue());
568        }
569        return value == null ? NULL_KEY : value;
570    }
571
572    private static final Object NULL_KEY = new Object();
573
574    private static List<Object> extend(List<Object> path, Object step) {
575        List<Object> out = new ArrayList<Object>(path.size() + 1);
576        out.addAll(path);
577        out.add(step);
578        return out;
579    }
580
581    /**
582     * One validation. Outcomes of (schema, instance) pairs are memoized, containers by identity and scalars by
583     * value, so a subschema reached many ways is evaluated once per instance; errors of a (schema, location) pair
584     * are reported once.
585     */
586    private final class Run {
587        private final Map<Object, Map<Object, Outcome>> containers = new IdentityHashMap<Object, Map<Object, Outcome>>();
588        private final Map<Object, Map<Object, Outcome>> scalars = new IdentityHashMap<Object, Map<Object, Outcome>>();
589        private final Map<Object, Set<List<Object>>> reported = new IdentityHashMap<Object, Set<List<Object>>>();
590
591        Outcome evaluate(Object instance, Object schema) {
592            if (schema instanceof Boolean) {
593                return ((Boolean) schema).booleanValue() ? Outcome.VALID_NONE : Outcome.INVALID;
594            }
595            boolean container = isObject(instance) || isArray(instance);
596            Map<Object, Map<Object, Outcome>> memo = container ? containers : scalars;
597            Map<Object, Outcome> bySchema = memo.get(schema);
598            if (bySchema == null) {
599                bySchema = container ? new IdentityHashMap<Object, Outcome>() : new HashMap<Object, Outcome>();
600                memo.put(schema, bySchema);
601            }
602            Object key = container ? instance : scalarKey(instance);
603            Outcome cached = bySchema.get(key);
604            if (cached != null) {
605                return cached;
606            }
607            Outcome outcome = compute(instance, (Map<?, ?>) schema);
608            bySchema.put(key, outcome);
609            return outcome;
610        }
611
612        private Outcome compute(Object instance, Map<?, ?> schema) {
613            boolean valid = true;
614            Set<String> evaluated = isObject(instance) ? new LinkedHashSet<String>() : null;
615            Map<?, ?> object = isObject(instance) ? (Map<?, ?>) instance : null;
616            for (Map.Entry<?, ?> entry : schema.entrySet()) {
617                String keyword = (String) entry.getKey();
618                Object value = entry.getValue();
619                if ("unevaluatedProperties".equals(keyword) || "then".equals(keyword) || "else".equals(keyword)
620                        || !SUPPORTED.contains(keyword)) {
621                    continue; // unevaluatedProperties after the others; then/else with if
622                }
623                if ("$ref".equals(keyword)) {
624                    Outcome ref = evaluate(instance, resolve(value, "$ref"));
625                    valid &= ref.valid;
626                    if (ref.valid && evaluated != null) {
627                        evaluated.addAll(ref.evaluated);
628                    }
629                } else if ("properties".equals(keyword)) {
630                    if (object != null) {
631                        for (Map.Entry<?, ?> property : ((Map<?, ?>) value).entrySet()) {
632                            if (object.containsKey(property.getKey())) {
633                                evaluated.add((String) property.getKey());
634                                valid &= evaluate(object.get(property.getKey()), property.getValue()).valid;
635                            }
636                        }
637                    }
638                } else if ("additionalProperties".equals(keyword)) {
639                    if (object != null) {
640                        Object properties = schema.get("properties");
641                        for (Object name : object.keySet()) {
642                            if (!(properties instanceof Map<?, ?>) || !((Map<?, ?>) properties).containsKey(name)) {
643                                evaluated.add((String) name);
644                                valid &= evaluate(object.get(name), value).valid;
645                            }
646                        }
647                    }
648                } else if (SCHEMA_LIST.contains(keyword)) {
649                    int passing = 0;
650                    for (Object sub : (List<?>) value) {
651                        Outcome branch = evaluate(instance, sub);
652                        if (branch.valid) {
653                            passing++;
654                            if (evaluated != null) {
655                                evaluated.addAll(branch.evaluated);
656                            }
657                        }
658                    }
659                    int total = ((List<?>) value).size();
660                    valid &= "allOf".equals(keyword) ? passing == total : "anyOf".equals(keyword) ? passing > 0 : passing == 1;
661                } else if ("not".equals(keyword)) {
662                    valid &= !evaluate(instance, value).valid;
663                } else if ("if".equals(keyword)) {
664                    Outcome condition = evaluate(instance, value);
665                    String branchKeyword = condition.valid ? "then" : "else";
666                    if (condition.valid && evaluated != null) {
667                        evaluated.addAll(condition.evaluated);
668                    }
669                    if (schema.containsKey(branchKeyword)) {
670                        Outcome branch = evaluate(instance, schema.get(branchKeyword));
671                        valid &= branch.valid;
672                        if (branch.valid && evaluated != null) {
673                            evaluated.addAll(branch.evaluated);
674                        }
675                    }
676                } else if ("items".equals(keyword)) {
677                    if (isArray(instance)) {
678                        for (Object item : (List<?>) instance) {
679                            valid &= evaluate(item, value).valid;
680                        }
681                    }
682                } else if ("propertyNames".equals(keyword)) {
683                    if (object != null) {
684                        for (Object name : object.keySet()) {
685                            valid &= evaluate(name, value).valid;
686                        }
687                    }
688                } else if ("required".equals(keyword)) {
689                    valid &= missing(value, instance).isEmpty();
690                } else {
691                    valid &= assertion(keyword, value, instance) == null;
692                }
693            }
694            if (schema.containsKey("unevaluatedProperties") && object != null) {
695                Object unevaluated = schema.get("unevaluatedProperties");
696                for (Object name : object.keySet()) {
697                    if (!evaluated.contains(name)) {
698                        valid &= evaluate(object.get(name), unevaluated).valid;
699                    }
700                }
701                if (valid) {
702                    for (Object name : object.keySet()) {
703                        evaluated.add((String) name);
704                    }
705                }
706            }
707            if (!valid) {
708                return Outcome.INVALID;
709            }
710            return evaluated == null || evaluated.isEmpty() ? Outcome.VALID_NONE : new Outcome(true, evaluated);
711        }
712
713        /** The errors of an invalid (schema, instance) pair, descending only where evaluation failed. */
714        void report(Object instance, Object schema, List<Object> path, List<SchemaError> out) {
715            Set<List<Object>> at = reported.get(schema);
716            if (at == null) {
717                at = new HashSet<List<Object>>();
718                reported.put(schema, at);
719            }
720            // propertyNames validates several names at one path, so a scalar's location includes its value
721            List<Object> location = isObject(instance) || isArray(instance) ? path
722                    : Arrays.asList(path, scalarKey(instance));
723            if (!at.add(location)) {
724                return; // this subschema at this location is already reported
725            }
726            if (schema instanceof Boolean) {
727                if (!((Boolean) schema).booleanValue()) {
728                    out.add(new SchemaError("false", Collections.emptyMap(), instance, path,
729                            "False schema does not allow " + instance, null));
730                }
731                return;
732            }
733            Map<?, ?> map = (Map<?, ?>) schema;
734            Map<?, ?> object = isObject(instance) ? (Map<?, ?>) instance : null;
735            for (Map.Entry<?, ?> entry : map.entrySet()) {
736                String keyword = (String) entry.getKey();
737                Object value = entry.getValue();
738                if (!SUPPORTED.contains(keyword) || "then".equals(keyword) || "else".equals(keyword)) {
739                    continue;
740                }
741                if ("$ref".equals(keyword)) {
742                    descend(instance, resolve(value, "$ref"), path, out);
743                } else if ("properties".equals(keyword)) {
744                    if (object != null) {
745                        for (Map.Entry<?, ?> property : ((Map<?, ?>) value).entrySet()) {
746                            if (object.containsKey(property.getKey())) {
747                                descend(object.get(property.getKey()), property.getValue(), extend(path, property.getKey()),
748                                        out);
749                            }
750                        }
751                    }
752                } else if ("additionalProperties".equals(keyword)) {
753                    if (object != null) {
754                        Object properties = map.get("properties");
755                        List<Object> extras = new ArrayList<Object>();
756                        for (Object name : object.keySet()) {
757                            if (!(properties instanceof Map<?, ?>) || !((Map<?, ?>) properties).containsKey(name)) {
758                                extras.add(name);
759                            }
760                        }
761                        if (value instanceof Map<?, ?>) {
762                            for (Object name : extras) {
763                                descend(object.get(name), value, extend(path, name), out);
764                            }
765                        } else if (Boolean.FALSE.equals(value) && !extras.isEmpty()) {
766                            out.add(new SchemaError(keyword, map, instance, path, "Additional properties are not allowed "
767                                    + extras, null));
768                        }
769                    }
770                } else if ("allOf".equals(keyword)) {
771                    for (Object sub : (List<?>) value) {
772                        descend(instance, sub, path, out);
773                    }
774                } else if ("anyOf".equals(keyword) || "oneOf".equals(keyword)) {
775                    int passing = 0;
776                    List<SchemaError> context = new ArrayList<SchemaError>();
777                    for (Object sub : (List<?>) value) {
778                        if (evaluate(instance, sub).valid) {
779                            passing++;
780                        } else {
781                            report(instance, sub, path, context);
782                        }
783                    }
784                    if (passing == 0) {
785                        out.add(new SchemaError(keyword, map, instance, path, "is not valid under any of the given schemas",
786                                context));
787                    } else if ("oneOf".equals(keyword) && passing > 1) {
788                        out.add(new SchemaError(keyword, map, instance, path,
789                                "is valid under more than one of the given schemas", null));
790                    }
791                } else if ("not".equals(keyword)) {
792                    if (evaluate(instance, value).valid) {
793                        out.add(new SchemaError(keyword, map, instance, path, "should not be valid under " + value, null));
794                    }
795                } else if ("if".equals(keyword)) {
796                    String branch = evaluate(instance, value).valid ? "then" : "else";
797                    if (map.containsKey(branch)) {
798                        descend(instance, map.get(branch), path, out);
799                    }
800                } else if ("items".equals(keyword)) {
801                    if (isArray(instance)) {
802                        List<?> items = (List<?>) instance;
803                        for (int i = 0; i < items.size(); i++) {
804                            descend(items.get(i), value, extend(path, Long.valueOf(i)), out);
805                        }
806                    }
807                } else if ("propertyNames".equals(keyword)) {
808                    if (object != null) {
809                        for (Object name : object.keySet()) {
810                            descend(name, value, path, out);
811                        }
812                    }
813                } else if ("unevaluatedProperties".equals(keyword)) {
814                    if (object != null) {
815                        Set<String> evaluated = evaluatedBy(instance, map);
816                        List<Object> unexpected = new ArrayList<Object>();
817                        for (Object name : object.keySet()) {
818                            if (!evaluated.contains(name) && !evaluate(object.get(name), value).valid) {
819                                unexpected.add(name);
820                            }
821                        }
822                        if (!unexpected.isEmpty()) {
823                            out.add(new SchemaError(keyword, map, instance, path, "Unevaluated properties are not allowed "
824                                    + unexpected, null));
825                        }
826                    }
827                } else if ("required".equals(keyword)) {
828                    for (Object name : missing(value, instance)) {
829                        out.add(new SchemaError(keyword, map, instance, path, name + " is a required property", null));
830                    }
831                } else {
832                    String message = assertion(keyword, value, instance);
833                    if (message != null) {
834                        out.add(new SchemaError(keyword, map, instance, path, message, null));
835                    }
836                }
837            }
838        }
839
840        private void descend(Object instance, Object schema, List<Object> path, List<SchemaError> out) {
841            if (!evaluate(instance, schema).valid) {
842                report(instance, schema, path, out);
843            }
844        }
845
846        /**
847         * The properties evaluated by the keywords of one schema object other than its own
848         * {@code unevaluatedProperties}, and by its in-place subschemas that validated: what its
849         * {@code unevaluatedProperties} applies to the rest of. A failing sibling keyword does not remove them.
850         */
851        private Set<String> evaluatedBy(Object instance, Map<?, ?> schema) {
852            Set<String> out = new HashSet<String>();
853            Map<?, ?> object = (Map<?, ?>) instance;
854            Object properties = schema.get("properties");
855            if (properties instanceof Map<?, ?>) {
856                for (Object name : ((Map<?, ?>) properties).keySet()) {
857                    if (object.containsKey(name)) {
858                        out.add((String) name);
859                    }
860                }
861            }
862            if (schema.containsKey("additionalProperties")) {
863                for (Object name : object.keySet()) {
864                    if (!(properties instanceof Map<?, ?>) || !((Map<?, ?>) properties).containsKey(name)) {
865                        out.add((String) name);
866                    }
867                }
868            }
869            if (schema.containsKey("$ref")) {
870                Outcome ref = evaluate(instance, resolve(schema.get("$ref"), "$ref"));
871                if (ref.valid) {
872                    out.addAll(ref.evaluated);
873                }
874            }
875            for (String keyword : new String[] {"allOf", "anyOf", "oneOf"}) {
876                if (schema.containsKey(keyword)) {
877                    for (Object sub : (List<?>) schema.get(keyword)) {
878                        Outcome branch = evaluate(instance, sub);
879                        if (branch.valid) {
880                            out.addAll(branch.evaluated);
881                        }
882                    }
883                }
884            }
885            if (schema.containsKey("if")) {
886                Outcome condition = evaluate(instance, schema.get("if"));
887                String branchKeyword = condition.valid ? "then" : "else";
888                if (condition.valid) {
889                    out.addAll(condition.evaluated);
890                }
891                if (schema.containsKey(branchKeyword)) {
892                    Outcome branch = evaluate(instance, schema.get(branchKeyword));
893                    if (branch.valid) {
894                        out.addAll(branch.evaluated);
895                    }
896                }
897            }
898            return out;
899        }
900    }
901
902    private static List<Object> missing(Object required, Object instance) {
903        List<Object> out = new ArrayList<Object>();
904        if (isObject(instance)) {
905            for (Object name : (List<?>) required) {
906                if (!((Map<?, ?>) instance).containsKey(name)) {
907                    out.add(name);
908                }
909            }
910        }
911        return out;
912    }
913
914    /** The message of a failing assertion keyword, or null when it holds (or does not apply). */
915    private String assertion(String keyword, Object value, Object instance) {
916        if ("type".equals(keyword)) {
917            List<?> types = value instanceof List<?> ? (List<?>) value : Collections.singletonList(value);
918            for (Object type : types) {
919                if (isType(instance, (String) type)) {
920                    return null;
921                }
922            }
923            return "is not of type " + types;
924        }
925        if ("enum".equals(keyword)) {
926            for (Object option : (List<?>) value) {
927                if (jsonEquals(option, instance)) {
928                    return null;
929                }
930            }
931            return "is not one of " + value;
932        }
933        if ("const".equals(keyword)) {
934            return jsonEquals(value, instance) ? null : "was expected to be " + value;
935        }
936        if ("pattern".equals(keyword)) {
937            if (!(instance instanceof String)) {
938                return null;
939            }
940            return patterns.get(value).matcher((String) instance).find() ? null : "does not match " + value;
941        }
942        if ("minItems".equals(keyword)) {
943            return isArray(instance) && ((List<?>) instance).size() < ((Number) value).longValue()
944                    ? "should be non-empty or longer" : null;
945        }
946        if ("minLength".equals(keyword)) {
947            if (!(instance instanceof String)) {
948                return null;
949            }
950            String text = (String) instance;
951            return text.codePointCount(0, text.length()) < ((Number) value).longValue() ? "is too short" : null;
952        }
953        if ("minimum".equals(keyword) || "maximum".equals(keyword)) {
954            if (!isInteger(instance)) {
955                return null;
956            }
957            int c = new BigInteger(instance.toString()).compareTo(new BigInteger(value.toString()));
958            return "minimum".equals(keyword) ? (c < 0 ? "is less than the minimum of " + value : null)
959                    : (c > 0 ? "is greater than the maximum of " + value : null);
960        }
961        if ("format".equals(keyword)) {
962            return null;
963        }
964        throw new IllegalStateException("unsupported keyword " + keyword);
965    }
966}