1use std::collections::{HashMap, HashSet};
9
10use crate::def::{Definitions, Kind, ObjectDef, ShapeDef};
11use crate::path::{Issue, Path};
12use crate::value::Value;
13
14pub fn check(definitions: &Definitions, shape: &ShapeDef, value: &Value) -> Vec<Issue> {
16 check_with_work(definitions, shape, value).0
17}
18
19pub 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
31pub fn normalise(definitions: &Definitions, shape: &ShapeDef, value: &Value) -> Value {
37 let checker = Checker::new(definitions, HashMap::new());
38 checker.normalised(shape, value)
39}
40
41pub fn accepts(definitions: &Definitions, shape: &ShapeDef, value: &Value) -> bool {
43 check(definitions, shape, value).is_empty()
44}
45
46pub(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
60fn 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
75const 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 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 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 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 (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}