Skip to main content

trilean_json_shape/
validate.rs

1//! Checking a value against a shape. The rules here and the keywords the schema emitter writes are the two readings
2//! of one descriptor, and the agreement tables in `tests/agreement.rs` keep them equal.
3//!
4//! The work of a check is linear in the size of the document, whatever the shape: a union decides among its
5//! alternatives by first discarding those that cannot match the value's kind or lack a required key, and remembers
6//! which alternative accepted which value, so two alternatives that descend into the same child check it once.
7
8use std::collections::{HashMap, HashSet};
9
10use crate::def::{Definitions, Kind, ObjectDef, ShapeDef};
11use crate::path::{Issue, Path};
12use crate::value::Value;
13
14/// Every way `value` does not match `shape`, with the path of the value each is about. Empty when it matches.
15pub fn check(definitions: &Definitions, shape: &ShapeDef, value: &Value) -> Vec<Issue> {
16    check_with_work(definitions, shape, value).0
17}
18
19/// [`check`] and the number of shapes it visited, which is at most a constant times the size of the document times
20/// the size of the shape.
21pub fn check_with_work(
22    definitions: &Definitions,
23    shape: &ShapeDef,
24    value: &Value,
25) -> (Vec<Issue>, u64) {
26    let mut checker = Checker::new(definitions, HashMap::new());
27    checker.shape(shape, value);
28    (checker.issues, checker.work)
29}
30
31/// The document as `shape` reads it, for a document that `check` accepted: an object keeps the keys its shape names, in
32/// the order the shape lists them (a tag first), then the keys its shape types without naming (in the document's
33/// order), a map drops a key called `__proto__`, and a union is read as the alternative that matches. A closed object
34/// that strips (see [`crate::ObjectDef::strips`]) loses the keys it does not name. The value is undefined for a
35/// document `check` refused.
36pub fn normalise(definitions: &Definitions, shape: &ShapeDef, value: &Value) -> Value {
37    let checker = Checker::new(definitions, HashMap::new());
38    checker.normalised(shape, value)
39}
40
41/// Whether `value` matches `shape`.
42pub fn accepts(definitions: &Definitions, shape: &ShapeDef, value: &Value) -> bool {
43    check(definitions, shape, value).is_empty()
44}
45
46/// Whether `alternative` accepts `value`, remembering the answer in the memory `path` carries, so a conversion that
47/// asks the same question at every node of a document asks each once.
48pub(crate) fn decide(
49    path: &mut Path,
50    definitions: &Definitions,
51    alternative: &ShapeDef,
52    value: &Value,
53) -> bool {
54    let mut checker = Checker::new(definitions, std::mem::take(&mut path.memo));
55    let accepted = checker.accepts_memo(alternative, value);
56    path.memo = checker.memo;
57    accepted
58}
59
60/// A JSON string literal, which is how every message writes a string, so no message depends on Rust's own escaping.
61fn json_text(text: &str) -> String {
62    crate::pattern::json_quote(text)
63}
64
65fn json_list(items: &[String]) -> String {
66    Value::Array(
67        items
68            .iter()
69            .map(|item| Value::String(item.clone()))
70            .collect(),
71    )
72    .to_string()
73}
74
75/// How deep a union may nest before its kind pre-filter stops looking, so a recursive definition cannot loop.
76const FILTER_DEPTH: usize = 16;
77
78struct Checker<'a> {
79    definitions: &'a Definitions,
80    path: Path,
81    issues: Vec<Issue>,
82    memo: HashMap<(usize, usize), bool>,
83    work: u64,
84}
85
86impl<'a> Checker<'a> {
87    fn new(definitions: &'a Definitions, memo: HashMap<(usize, usize), bool>) -> Self {
88        Checker {
89            definitions,
90            path: Path::new(),
91            issues: Vec::new(),
92            memo,
93            work: 0,
94        }
95    }
96
97    fn report(&mut self, message: impl Into<String>) {
98        self.issues.push(Issue {
99            path: self.path.segments().to_vec(),
100            message: message.into(),
101        });
102    }
103
104    fn expect_type(&mut self, expected: &str, value: &Value) {
105        self.report(format!("expected {expected}, found {}", value.type_name()));
106    }
107
108    /// Whether `shape` accepts `value`, asked once per pair: the addresses name the pair, and both outlive the check.
109    fn accepts_memo(&mut self, shape: &ShapeDef, value: &Value) -> bool {
110        let key = (
111            std::ptr::from_ref(shape) as usize,
112            std::ptr::from_ref(value) as usize,
113        );
114        if let Some(known) = self.memo.get(&key) {
115            return *known;
116        }
117        let before = self.issues.len();
118        self.shape(shape, value);
119        let accepted = self.issues.len() == before;
120        self.issues.truncate(before);
121        self.memo.insert(key, accepted);
122        accepted
123    }
124
125    /// Whether `value` could match `shape`: false only when it certainly does not, from its kind and the keys a
126    /// closed or required field demands. Cheap and never descends into children. With `sharp` it also compares a
127    /// constant string a required field holds and the tag a tagged union is told apart by, which tells the variants of
128    /// a union apart for reading a document as a shape; a check does not use it, so that a value whose tag no variant
129    /// has is reported at the tag and not as matching none of the alternatives.
130    fn may_match(&self, shape: &ShapeDef, value: &Value, depth: usize, sharp: bool) -> bool {
131        match &shape.kind {
132            Kind::Any => true,
133            Kind::Null => *value == Value::Null,
134            Kind::Bool | Kind::ConstBool(_) => matches!(value, Value::Bool(_)),
135            Kind::ConstString(_) | Kind::Enum(_) | Kind::String { .. } => {
136                matches!(value, Value::String(_))
137            }
138            Kind::Integer { .. } | Kind::Number { .. } => matches!(value, Value::Number(_)),
139            Kind::Array { .. } => matches!(value, Value::Array(_)),
140            Kind::Map { .. } => matches!(value, Value::Object(_)),
141            Kind::Tagged { tag, variants } => {
142                matches!(value, Value::Object(_))
143                    && (!sharp
144                        || value.get(tag).and_then(Value::as_str).is_some_and(|name| {
145                            variants.iter().any(|(variant, _)| variant == name)
146                        }))
147            }
148            Kind::Object(object) => {
149                matches!(value, Value::Object(_))
150                    && object.fields.iter().all(|field| {
151                        match (value.get(&field.name), &field.shape.kind) {
152                            (None, _) => !field.required,
153                            (Some(found), Kind::ConstString(expected)) if sharp => {
154                                found.as_str() == Some(expected)
155                            }
156                            (Some(_), _) => true,
157                        }
158                    })
159            }
160            Kind::OneOf(alternatives) => {
161                depth >= FILTER_DEPTH
162                    || alternatives
163                        .iter()
164                        .any(|alternative| self.may_match(alternative, value, depth + 1, sharp))
165            }
166            Kind::Not(_) => true,
167            Kind::AllOf(parts) => parts
168                .iter()
169                .all(|part| self.may_match(part, value, depth + 1, sharp)),
170            Kind::Ref(name) => match self.definitions.get(name) {
171                Some(target) if depth < FILTER_DEPTH => {
172                    self.may_match(target, value, depth + 1, sharp)
173                }
174                _ => true,
175            },
176        }
177    }
178
179    /// `value` read as `shape` (see [`normalise`]).
180    fn normalised(&self, shape: &ShapeDef, value: &Value) -> Value {
181        match (&shape.kind, value) {
182            (Kind::Array { items, .. }, Value::Array(elements)) => Value::Array(
183                elements
184                    .iter()
185                    .map(|element| self.normalised(items, element))
186                    .collect(),
187            ),
188            (Kind::Map { values, .. }, Value::Object(pairs)) => Value::Object(
189                pairs
190                    .iter()
191                    .filter(|(key, _)| key != "__proto__")
192                    .map(|(key, entry)| (key.clone(), self.normalised(values, entry)))
193                    .collect(),
194            ),
195            (Kind::Object(object), Value::Object(pairs)) => {
196                let mut read: Vec<(String, Value)> = object
197                    .fields
198                    .iter()
199                    .filter_map(|field| {
200                        value
201                            .get(&field.name)
202                            .map(|entry| (field.name.clone(), self.normalised(&field.shape, entry)))
203                    })
204                    .collect();
205                if !object.closed || object.additional.is_some() {
206                    for (key, entry) in pairs {
207                        if object.fields.iter().any(|field| field.name == *key) {
208                            continue;
209                        }
210                        let kept = match &object.additional {
211                            Some(shape) => self.normalised(shape, entry),
212                            None => entry.clone(),
213                        };
214                        read.push((key.clone(), kept));
215                    }
216                }
217                Value::Object(read)
218            }
219            (Kind::OneOf(alternatives), _) => {
220                let candidates: Vec<&ShapeDef> = alternatives
221                    .iter()
222                    .filter(|alternative| self.may_match(alternative, value, 0, true))
223                    .collect();
224                let chosen = match candidates.as_slice() {
225                    [only] => Some(*only),
226                    _ => candidates.iter().copied().find(|alternative| {
227                        let mut checker = Checker::new(self.definitions, HashMap::new());
228                        checker.accepts_memo(alternative, value)
229                    }),
230                };
231                chosen.map_or_else(
232                    || value.clone(),
233                    |alternative| self.normalised(alternative, value),
234                )
235            }
236            (Kind::Tagged { tag, variants }, _) => value
237                .get(tag)
238                .and_then(Value::as_str)
239                .and_then(|name| variants.iter().find(|(variant, _)| variant == name))
240                .map_or_else(
241                    || value.clone(),
242                    |(_, variant)| self.normalised(variant, value),
243                ),
244            (Kind::Ref(name), _) => self
245                .definitions
246                .get(name)
247                .map_or_else(|| value.clone(), |target| self.normalised(target, value)),
248            _ => value.clone(),
249        }
250    }
251
252    fn shape(&mut self, shape: &ShapeDef, value: &Value) {
253        self.work += 1;
254        match &shape.kind {
255            Kind::Any => {}
256            Kind::Null => {
257                if *value != Value::Null {
258                    self.expect_type("null", value);
259                }
260            }
261            Kind::Bool => {
262                if !matches!(value, Value::Bool(_)) {
263                    self.expect_type("a boolean", value);
264                }
265            }
266            Kind::ConstBool(expected) => {
267                if *value != Value::Bool(*expected) {
268                    self.report(format!("expected {expected}"));
269                }
270            }
271            Kind::ConstString(expected) => {
272                if value.as_str() != Some(expected) {
273                    self.report(format!("expected {}", json_text(expected)));
274                }
275            }
276            Kind::Enum(options) => {
277                if !value
278                    .as_str()
279                    .is_some_and(|text| options.iter().any(|option| option == text))
280                {
281                    self.report(format!("expected one of {}", json_list(options)));
282                }
283            }
284            Kind::String {
285                min_length,
286                pattern,
287            } => self.string(*min_length, pattern.as_deref(), value),
288            Kind::Integer {
289                min,
290                exclusive_min,
291                max,
292            } => self.number(true, [*min, *exclusive_min, *max], value),
293            Kind::Number {
294                min,
295                exclusive_min,
296                max,
297            } => self.number(false, [*min, *exclusive_min, *max], value),
298            Kind::Array {
299                items,
300                min_items,
301                max_items,
302                unique,
303            } => self.array(items, *min_items, *max_items, *unique, value),
304            Kind::Map {
305                values,
306                min_properties,
307                key_pattern,
308            } => self.map(values, *min_properties, key_pattern.as_deref(), value),
309            Kind::Object(object) => self.object(object, value),
310            Kind::OneOf(alternatives) => self.one_of(alternatives, value),
311            Kind::Not(inner) => {
312                if self.accepts_memo(inner, value) {
313                    self.report("matches a shape it must not match");
314                }
315            }
316            Kind::AllOf(parts) => {
317                for part in parts {
318                    self.shape(part, value);
319                }
320            }
321            Kind::Tagged { tag, variants } => self.tagged(tag, variants, value),
322            Kind::Ref(name) => match self.definitions.get(name) {
323                Some(target) => self.shape(target, value),
324                None => self.report(format!("the definition {} does not exist", json_text(name))),
325            },
326        }
327    }
328
329    fn string(&mut self, min_length: Option<usize>, pattern: Option<&str>, value: &Value) {
330        let Some(text) = value.as_str() else {
331            return self.expect_type("a string", value);
332        };
333        if let Some(least) = min_length
334            && text.chars().count() < least
335        {
336            self.report(format!("expected at least {least} characters"));
337        }
338        if let Some(source) = pattern {
339            match crate::pattern::shared(source) {
340                Ok(compiled) if !compiled.is_match(text) => {
341                    self.report(format!("expected a string matching {}", json_text(source)));
342                }
343                Ok(_) => {}
344                Err(error) => self.report(error.to_string()),
345            }
346        }
347    }
348
349    fn number(&mut self, whole: bool, [min, exclusive_min, max]: [Option<f64>; 3], value: &Value) {
350        let Some(number) = value.as_f64() else {
351            return self.expect_type(if whole { "an integer" } else { "a number" }, value);
352        };
353        if whole && number.fract() != 0.0 {
354            return self.report("expected an integer, found a fraction");
355        }
356        if let Some(least) = min
357            && number < least
358        {
359            self.report(format!("expected at least {least}"));
360        }
361        if let Some(above) = exclusive_min
362            && number <= above
363        {
364            self.report(format!("expected more than {above}"));
365        }
366        if let Some(most) = max
367            && number > most
368        {
369            self.report(format!("expected at most {most}"));
370        }
371    }
372
373    fn array(
374        &mut self,
375        items: &ShapeDef,
376        min_items: Option<usize>,
377        max_items: Option<usize>,
378        unique: bool,
379        value: &Value,
380    ) {
381        let Some(elements) = value.as_array() else {
382            return self.expect_type("an array", value);
383        };
384        if let Some(least) = min_items
385            && elements.len() < least
386        {
387            self.report(format!("expected at least {least} items"));
388        }
389        if let Some(most) = max_items
390            && elements.len() > most
391        {
392            self.report(format!("expected at most {most} items"));
393        }
394        if unique {
395            let mut seen = HashSet::new();
396            if elements
397                .iter()
398                .any(|element| !seen.insert(element.canonical()))
399            {
400                self.report("expected every item to be different");
401            }
402        }
403        for (position, element) in elements.iter().enumerate() {
404            self.path.push_index(position);
405            self.shape(items, element);
406            self.path.pop();
407        }
408    }
409
410    fn map(
411        &mut self,
412        values: &ShapeDef,
413        min_properties: Option<usize>,
414        key_pattern: Option<&str>,
415        value: &Value,
416    ) {
417        let Some(pairs) = value.as_object() else {
418            return self.expect_type("an object", value);
419        };
420        if let Some(least) = min_properties
421            && pairs.len() < least
422        {
423            self.report(format!("expected at least {least} properties"));
424        }
425        let key_check = key_pattern.map(|source| (source, crate::pattern::shared(source)));
426        for (key, entry) in pairs {
427            self.path.push_key(key);
428            match &key_check {
429                Some((source, Ok(compiled))) if !compiled.is_match(key) => {
430                    self.report(format!("the key must match {}", json_text(source)));
431                }
432                Some((_, Err(error))) => self.report(error.to_string()),
433                _ => {}
434            }
435            self.shape(values, entry);
436            self.path.pop();
437        }
438    }
439
440    fn object(&mut self, object: &ObjectDef, value: &Value) {
441        let Some(pairs) = value.as_object() else {
442            return self.expect_type("an object", value);
443        };
444        if let Some(least) = object.min_properties
445            && pairs.len() < least
446        {
447            self.report(format!("expected at least {least} properties"));
448        }
449        for field in &object.fields {
450            match value.get(&field.name) {
451                Some(entry) => {
452                    self.path.push_key(&field.name);
453                    self.shape(&field.shape, entry);
454                    self.path.pop();
455                }
456                None if field.required => {
457                    self.path.push_key(&field.name);
458                    self.report("missing the required property");
459                    self.path.pop();
460                }
461                None => {}
462            }
463        }
464        if (object.closed && !object.strips) || object.additional.is_some() {
465            for (key, entry) in pairs {
466                if object.fields.iter().any(|field| field.name == *key) {
467                    continue;
468                }
469                self.path.push_key(key);
470                match &object.additional {
471                    Some(shape) => self.shape(shape, entry),
472                    None => self.report("unexpected property"),
473                }
474                self.path.pop();
475            }
476        }
477        if !object.any_of_keys.is_empty() || !object.one_of_keys.is_empty() {
478            let present =
479                |keys: &[String]| keys.iter().filter(|key| value.get(key).is_some()).count();
480            if !object.any_of_keys.is_empty() && present(&object.any_of_keys) == 0 {
481                self.report(format!(
482                    "expected at least one of {}",
483                    json_list(&object.any_of_keys)
484                ));
485            }
486            if !object.one_of_keys.is_empty() && present(&object.one_of_keys) != 1 {
487                self.report(format!(
488                    "expected exactly one of {}",
489                    json_list(&object.one_of_keys)
490                ));
491            }
492        }
493        for (key, required) in &object.dependent_required {
494            if value.get(key).is_none() {
495                continue;
496            }
497            for other in required {
498                if value.get(other).is_none() {
499                    self.report(format!("{} requires {}", json_text(key), json_text(other)));
500                }
501            }
502        }
503    }
504
505    fn one_of(&mut self, alternatives: &[ShapeDef], value: &Value) {
506        let candidates: Vec<&ShapeDef> = alternatives
507            .iter()
508            .filter(|alternative| self.may_match(alternative, value, 0, false))
509            .collect();
510        let mut matching = 0;
511        for candidate in &candidates {
512            if self.accepts_memo(candidate, value) {
513                matching += 1;
514            }
515        }
516        match (matching, candidates.as_slice()) {
517            (1, _) => {}
518            // The one alternative the value could be is the one it fails, so its issues, at their own paths, say why.
519            (0, [only]) => self.shape(only, value),
520            (0, _) => self.report("matches none of the alternatives"),
521            _ => self.report("matches more than one alternative"),
522        }
523    }
524
525    fn tagged(&mut self, tag: &str, variants: &[(String, ShapeDef)], value: &Value) {
526        if value.as_object().is_none() {
527            return self.expect_type("an object", value);
528        }
529        let Some(chosen) = value.get(tag).and_then(Value::as_str) else {
530            self.path.push_key(tag);
531            self.report("expected a string naming the kind");
532            self.path.pop();
533            return;
534        };
535        match variants.iter().find(|(name, _)| name == chosen) {
536            Some((_, variant)) => self.shape(variant, value),
537            None => {
538                self.path.push_key(tag);
539                let names: Vec<String> = variants.iter().map(|(name, _)| name.clone()).collect();
540                self.report(format!("expected one of {}", json_list(&names)));
541                self.path.pop();
542            }
543        }
544    }
545}
546
547#[cfg(test)]
548mod tests {
549    use crate::{Definitions, Kind, ShapeDef, Value, check};
550
551    #[test]
552    fn a_pattern_is_compiled_once_however_many_values_are_checked() {
553        let source = "^unique-counted-[0-9]+$";
554        let shape = ShapeDef::new(Kind::Array {
555            items: Box::new(ShapeDef::new(Kind::String {
556                min_length: None,
557                pattern: Some(source.to_owned()),
558            })),
559            min_items: None,
560            max_items: None,
561            unique: false,
562        });
563        let strings = (0..1000)
564            .map(|n| Value::String(format!("unique-counted-{n}")))
565            .collect();
566        assert!(check(&Definitions::default(), &shape, &Value::Array(strings)).is_empty());
567        assert_eq!(crate::pattern::compilations_of(source), 1);
568
569        let key_source = "^unique-keyed-[0-9]+$";
570        let keyed = ShapeDef::new(Kind::Map {
571            values: Box::new(ShapeDef::new(Kind::Any)),
572            min_properties: None,
573            key_pattern: Some(key_source.to_owned()),
574        });
575        let members = (0..500)
576            .map(|n| (format!("unique-keyed-{n}"), Value::Null))
577            .collect();
578        assert!(check(&Definitions::default(), &keyed, &Value::Object(members)).is_empty());
579        assert_eq!(crate::pattern::compilations_of(key_source), 1);
580    }
581}