shape/accepts.rs
1use indexmap::IndexSet;
2
3use super::Shape;
4use super::ShapeCase;
5use crate::helpers::Ref;
6
7/// The `Shape::validate*` methods return a vector of `ShapeMismatch` errors
8/// that is non-empty when validation fails.
9///
10/// Each `ShapeMismatch` error contains the `expected` shape and the `received`
11/// shape, whose metadata (e.g. shape.locations) provide context for the
12/// mismatch.
13///
14/// Conveniently, the `expected`/`received` terminology works for both the
15/// `expected.accepts(received)` and `received.satisfies(expected)` directions
16/// of comparison, so `ShapeMismatch` does not encode whether the `accepts` or
17/// `satisfies` was used internally (though `validate` is similar to `accepts`
18/// in its order of arguments).
19///
20/// Once issue #5 is implemented, you'll be able to obtain source location
21/// information from the `expected` and `received` shapes (instead of adding
22/// additional fields to the `ShapeMismatch` struct).
23#[derive(Debug, PartialEq, Eq, Clone, Hash)]
24pub struct ShapeMismatch {
25 pub expected: Shape,
26 pub received: Shape,
27 pub causes: Vec<ShapeMismatch>,
28}
29
30impl Shape {
31 /// Returns true if the other shape meets all the expectations of the self
32 /// shape. In set theory terms, the set of all values accepted by other is a
33 /// subset of the set of all values accepted by self.
34 #[must_use]
35 pub fn accepts(&self, other: &Shape) -> bool {
36 self.validate(other).is_none()
37 }
38
39 /// Returns true iff the given [`serde_json::Value`] satisfies self.
40 #[must_use]
41 pub fn accepts_json(&self, json: &serde_json::Value) -> bool {
42 self.accepts(&Shape::from_json(json))
43 }
44
45 /// Returns true iff the given [`serde_json_bytes::Value`] satisfies self.
46 pub fn accepts_json_bytes(&self, json: &serde_json_bytes::Value) -> bool {
47 self.accepts(&Shape::from_json_bytes(json))
48 }
49
50 /// `Shape::validate_json` is to `Shape::validate` as `Shape::accepts_json`
51 /// is to `Shape::accepts`.
52 #[must_use]
53 pub fn validate_json(&self, json: &serde_json::Value) -> Option<ShapeMismatch> {
54 self.validate(&Shape::from_json(json))
55 }
56
57 /// `Shape::validate_json_bytes` is to `Shape::validate` as
58 /// `Shape::accepts_json_bytes` is to `Shape::accepts`.
59 pub fn validate_json_bytes(&self, json: &serde_json_bytes::Value) -> Option<ShapeMismatch> {
60 self.validate(&Shape::from_json_bytes(json))
61 }
62
63 /// Returns `true` if the `self` shape meets all the expectations of the
64 /// `other` shape. In set theory terms, `self` satisfying `other` means the
65 /// set of all values accepted by `self` is a subset of the set of all
66 /// values accepted by `other`.
67 ///
68 /// The `satisfies` method is the inverse of the `accepts` method, in the
69 /// sense that `a.accepts(b)` is equivalent to `b.satisfies(a)`. For
70 /// historical reasons, the bulk of the `accepts`/`satisfies` logic happens
71 /// in the internal `validate` method, though I have since realized
72 /// the `accepts` direction generalizes a bit better to situations where
73 /// `other` is not a `Shape`, such as `Shape::accepts_json(&self, json:
74 /// &serde_json::Value)`.
75 #[must_use]
76 pub fn satisfies(&self, other: &Shape) -> bool {
77 other.validate(self).is_none()
78 }
79
80 /// Validates that all expectations of the `self` shape are met by the
81 /// `other` shape, erroring with a non-empty vector of `ShapeMismatch`
82 /// errors when validation fails.
83 #[allow(clippy::too_many_lines)]
84 #[must_use]
85 pub fn validate(&self, other: &Shape) -> Option<ShapeMismatch> {
86 // Since self.case and other.case are the only information that
87 // logically matters for validation, we can skip doing any actual
88 // validation work if they point to the same ShapeCase in memory.
89 if Ref::ptr_eq(&self.case, &other.case) {
90 return None;
91 }
92
93 // Helper closure that translates boolean results to vector results. The
94 // `path` and `mismatches` parameters are always the local parameter and
95 // variable of the same names from the outer scope, but passing them in
96 // this way simplifies ownership logic and strips mutability.
97 let report = |is_valid: bool, causes: Vec<ShapeMismatch>| -> Option<ShapeMismatch> {
98 if is_valid {
99 // Use the report closure only in situations where the truth of
100 // `is_valid` should hide any previous mismatches.
101 None
102 } else {
103 Some(ShapeMismatch {
104 expected: self.clone(),
105 received: other.clone(),
106 causes,
107 })
108 }
109 };
110
111 let self_causes = match self.case() {
112 ShapeCase::One(self_shapes) => {
113 // If the union is empty (i.e. self.is_never()), then the only
114 // other shapes that can be validated by this empty union are
115 // other never shapes and None.
116 if self_shapes.is_empty() {
117 return if other.is_never() || other.is_none() {
118 None
119 } else {
120 // Reporting this error is important, since there are no
121 // self shapes to produce mismatches below.
122 Some(ShapeMismatch {
123 expected: self.clone(),
124 received: other.clone(),
125 causes: Vec::new(),
126 })
127 };
128 }
129
130 // If other is validated by any single shape in self_shapes,
131 // then other is validated by the union. However, we want to try
132 // any shapes other than *bound* ShapeCase::Name shapes first,
133 // since bound ::Name shapes are the gateway to infinite cycles,
134 // and the names might resolve to shapes we've already seen in
135 // the union, so we don't need to validate them again.
136 let mut bound_name_target_shapes = Vec::new();
137
138 // It's acceptable not to use a MergeSet<Shape> here, because we
139 // don't care about name/location metadata, but only whether one
140 // of the resolved bound_name_target_shapes is one we've seen already,
141 // which concerns only ShapeCase equality/hashing.
142 let mut not_bound_names: IndexSet<&Shape> = IndexSet::new();
143
144 let mut causes = Vec::new();
145
146 for self_shape in self_shapes.iter() {
147 if let ShapeCase::Name(name, weak) = self_shape.case() {
148 if let Some(named_shape) = weak.upgrade(name) {
149 // Handle in a later loop.
150 bound_name_target_shapes.push(named_shape);
151 continue;
152 }
153 }
154 // If self_shape is not a bound named shape, validate it
155 // against other.
156 if let Some(mismatch) = self_shape.validate(other) {
157 // If the unbound named shape does not validate other,
158 // we need to report it.
159 causes.push(mismatch);
160 } else {
161 // If the unbound named shape validates other, we can
162 // skip the rest of the shapes.
163 return None;
164 }
165 not_bound_names.insert(self_shape);
166 }
167
168 for target_shape in &bound_name_target_shapes {
169 // If we resolved a bound name to a shape we've already
170 // seen, we do not need to validate it again.
171 if !not_bound_names.contains(target_shape) {
172 if let Some(mismatch) = target_shape.validate(other) {
173 // If the bound named shape does not validate other,
174 // we need to report it.
175 causes.push(mismatch);
176 } else {
177 // If the bound named shape validates other,
178 // we can skip the rest of the shapes.
179 return None;
180 }
181 }
182 }
183
184 // Importantly, we do not return false here (in contrast with
185 // the ::All case below), because the union might still validate
186 // other, e.g. when other is Bool and the union contains both
187 // true and false as members.
188 //
189 // We will need to handle ShapeCase::One logic in the ::Bool
190 // case below, but otherwise the loop above saves most of the
191 // cases below from explicitly worrying about self being a
192 // ShapeCase::One.
193 causes
194 }
195
196 ShapeCase::All(self_shapes) => {
197 let mut causes = Vec::new();
198
199 for self_shape in self_shapes.iter() {
200 if let Some(mismatch) = self_shape.validate(other) {
201 // If the intersection member does not validate other,
202 // we need to report it.
203 causes.push(mismatch);
204 }
205 }
206
207 return report(causes.is_empty(), causes);
208 }
209
210 // Sometimes we don't know anything (yet) about the structure of a
211 // shape, but still want to refer to it by name and access the
212 // shapes of subproperties (symbolically if not concretely). That's
213 // what the ShapeCase::Name variant models.
214 ShapeCase::Name(name, weak) => {
215 return if let Some(named_shape) = weak.upgrade(name) {
216 named_shape.validate(other)
217 } else {
218 // When self is an unbound named shape reference, it
219 // validates any other shape trivially, since it imposes no
220 // expectations on the other shape (and could eventually
221 // resolve to a shape that validates other).
222 None
223 };
224 }
225
226 ShapeCase::Unknown => {
227 // Unknown shapes validate any shape.
228 return None;
229 }
230
231 _ => Vec::new(),
232 };
233
234 match other.case() {
235 ShapeCase::Bool(Some(value)) => report(
236 match self.case() {
237 ShapeCase::Bool(self_value) => {
238 Some(value) == self_value.as_ref() || self_value.is_none()
239 }
240 // We already handled the ::One and ::All cases above.
241 _ => false,
242 },
243 self_causes,
244 ),
245
246 ShapeCase::Bool(None) => report(
247 (|| match self.case() {
248 ShapeCase::Bool(None) => true,
249
250 // This case goes beyond the basic ShapeCase::One handling
251 // provided at the top of the function, because we want to allow
252 // ::Bool(None) to be validated by a union of true and false.
253 ShapeCase::One(self_shapes) => {
254 let true_shape = Shape::bool_value(true, []);
255 let false_shape = Shape::bool_value(false, []);
256 let mut true_found = false;
257 let mut false_found = false;
258
259 for self_shape in self_shapes.iter() {
260 if true_shape.accepts(self_shape) {
261 true_found = true;
262 }
263 if false_shape.accepts(self_shape) {
264 false_found = true;
265 }
266 // If both true and false accept/validate at least
267 // one self_shape, the union validates Bool.
268 if true_found && false_found {
269 // Returns from the (|| match ...)() closure.
270 return true;
271 }
272 }
273
274 false
275 }
276
277 _ => false,
278 })(),
279 self_causes,
280 ),
281
282 ShapeCase::String(value) => report(
283 match self.case() {
284 ShapeCase::String(self_value) => value == self_value || self_value.is_none(),
285 // We already handled the ::One case above.
286 _ => false,
287 },
288 self_causes,
289 ),
290
291 ShapeCase::Int(value) => report(
292 match self.case() {
293 ShapeCase::Int(self_value) => value == self_value || self_value.is_none(),
294 // All Int values are also (trivially convertible to) Float
295 // values, so Int is a subshape of Float.
296 ShapeCase::Float => true,
297 // We already handled the ::One case above.
298 _ => false,
299 },
300 self_causes,
301 ),
302
303 ShapeCase::Float => report(matches!(self.case(), ShapeCase::Float), Vec::new()),
304
305 // Both ::Null and ::None accept/validate only themselves, but they
306 // have an important difference in behavior when they appear in
307 // ::All intersections. The null value "poisons" intersections,
308 // reducing the whole intersection to null, which can be appropriate
309 // behavior when reporting certain kinds of top-level errors. The
310 // None value simply disappears from intersections, as it imposes no
311 // additional constraints on the intersection shape.
312 ShapeCase::Null => report(matches!(self.case(), ShapeCase::Null), Vec::new()),
313 ShapeCase::None => report(matches!(self.case(), ShapeCase::None), Vec::new()),
314
315 // ShapeCase::Unknown is validated by no other shapes except itself.
316 // We already handled the case when self is ::Unknown above, so we
317 // can report false here.
318 ShapeCase::Unknown => report(false, Vec::new()),
319
320 ShapeCase::Array {
321 prefix: other_prefix,
322 tail: other_tail,
323 } => match self.case() {
324 ShapeCase::Array {
325 prefix: self_prefix,
326 tail: self_tail,
327 } => {
328 let mut causes = Vec::new();
329
330 for i in 0..self_prefix.len().max(other_prefix.len()) {
331 if let Some(self_item) = self_prefix.get(i) {
332 if let Some(other_item) = other_prefix.get(i) {
333 if let Some(mismatch) = self_item.validate(other_item) {
334 causes.push(mismatch);
335 }
336 } else if let Some(mismatch) = self_item.validate(other_tail) {
337 // other is shorter, so position i in other is
338 // governed by other_tail (possibly None when
339 // other is a closed tuple).
340 causes.push(mismatch);
341 }
342 } else if let Some(other_item) = other_prefix.get(i) {
343 // self has no prefix position i; self_tail
344 // governs.
345 if self_tail.is_none() {
346 // self is closed at length self_prefix.len()
347 // but other carries another element here.
348 causes.push(ShapeMismatch {
349 expected: self.clone(),
350 received: other.clone(),
351 causes: Vec::new(),
352 });
353 } else if let Some(mismatch) = self_tail.validate(other_item) {
354 causes.push(mismatch);
355 }
356 }
357 // `i < max(self_prefix.len(), other_prefix.len())`
358 // guarantees at least one of the two `get(i)` calls
359 // above returns `Some`, so there is no else branch.
360 }
361
362 #[allow(clippy::match_same_arms)]
363 match (self_tail.case(), other_tail.case()) {
364 // other's tail is None, so it is effectively a fixed
365 // tuple; nothing more to check against self_tail.
366 (_, ShapeCase::None) => {}
367 // self is closed but other has a tail, so other may
368 // carry elements beyond self_prefix.len() that self
369 // cannot accept.
370 (ShapeCase::None, _) => {
371 causes.push(ShapeMismatch {
372 expected: self.clone(),
373 received: other.clone(),
374 causes: Vec::new(),
375 });
376 }
377 _ => {
378 if let Some(mismatch) = self_tail.validate(other_tail) {
379 causes.push(mismatch);
380 }
381 }
382 }
383
384 report(causes.is_empty(), causes)
385 }
386
387 // We already handled the ::One and ::All cases above.
388 _ => report(false, Vec::new()),
389 },
390
391 ShapeCase::Object { fields, rest } => match self.case() {
392 ShapeCase::Object {
393 fields: self_fields,
394 rest: self_rest,
395 } => {
396 let mut causes = Vec::new();
397
398 // For each field self declares, determine the shape it
399 // can take under `other` and check self's expectation
400 // accepts it.
401 for (field_name, field_shape) in self_fields {
402 if let Some(other_field_shape) = fields.get(field_name) {
403 if let Some(mismatch) = field_shape.validate(other_field_shape) {
404 causes.push(mismatch);
405 }
406 } else {
407 // other does not declare field_name. Under other,
408 // v.field_name is either absent (None) or, if
409 // other has a non-None rest shape, a dynamic
410 // property of that rest shape. Self must accept
411 // any such possibility.
412 if rest.is_none() {
413 // Field is guaranteed absent under other;
414 // self must tolerate None (be optional).
415 if let Some(mismatch) = field_shape.validate(&Shape::none()) {
416 causes.push(mismatch);
417 }
418 } else {
419 let possible = Shape::one([Shape::none(), rest.clone()], []);
420 if let Some(mismatch) = field_shape.validate(&possible) {
421 causes.push(mismatch);
422 }
423 }
424 }
425 }
426
427 // For each field other declares that self does not, the
428 // field must be absorbed by self's rest shape. A closed
429 // self (rest: None) cannot absorb any extra declared
430 // field — unless the field is provably always absent,
431 // which we conservatively detect as field_shape being
432 // the literal None shape.
433 for (field_name, other_field_shape) in fields {
434 if self_fields.contains_key(field_name) {
435 continue;
436 }
437 if self_rest.is_none() {
438 if !other_field_shape.is_none() {
439 causes.push(ShapeMismatch {
440 expected: self.clone(),
441 received: other.clone(),
442 causes: Vec::new(),
443 });
444 }
445 } else if let Some(mismatch) = self_rest.validate(other_field_shape) {
446 causes.push(mismatch);
447 }
448 }
449
450 // Finally, reconcile the two rest shapes themselves.
451 match (rest.case(), self_rest.case()) {
452 // Either other declares no dynamic properties, so
453 // there is nothing more for self.rest to absorb,
454 // regardless of whether self is open or closed.
455 (ShapeCase::None, _) => {}
456 // other permits dynamic properties but self is
457 // closed — other's values can carry extras that
458 // self does not permit.
459 (_, ShapeCase::None) => {
460 causes.push(ShapeMismatch {
461 expected: self.clone(),
462 received: other.clone(),
463 causes: Vec::new(),
464 });
465 }
466 // Both sides permit dynamic properties; self's rest
467 // must be at least as permissive as other's.
468 _ => {
469 if let Some(mismatch) = self_rest.validate(rest) {
470 causes.push(mismatch);
471 }
472 }
473 }
474
475 report(causes.is_empty(), causes)
476 }
477
478 // We already handled the ::One and ::All cases above.
479 _ => report(false, Vec::new()),
480 },
481
482 // If *other* is a ShapeCase::One union, then every possibility must
483 // be validated by self. For example, if other is One<true, false>,
484 // and self is Bool, then since true and false are each individually
485 // validated by Bool, Bool validates the union One<true, false>.
486 ShapeCase::One(other_shapes) => {
487 // If other is an empty union (Never), then only None or other
488 // Never shapes can validate it. We already handled the case
489 // when self is Never in the first match, so here we only need
490 // to check for None.
491 if other_shapes.is_empty() {
492 return if self.is_none() {
493 None
494 } else {
495 Some(ShapeMismatch {
496 expected: self.clone(),
497 received: other.clone(),
498 causes: Vec::new(),
499 })
500 };
501 }
502
503 let mut causes = Vec::new();
504
505 for other_shape in other_shapes.iter() {
506 if let Some(mismatch) = self.validate(other_shape) {
507 // If the union member does not validate self, we need
508 // to report it.
509 causes.push(mismatch);
510 }
511 }
512
513 report(causes.is_empty(), causes)
514 }
515
516 // If other is a ShapeCase::All intersection, then it is validated
517 // by self if any of the member shapes are validated by self.
518 ShapeCase::All(other_shapes) => {
519 let mut causes = Vec::new();
520
521 for other_shape in other_shapes.iter() {
522 let mismatch_opt = self.validate(other_shape);
523 if let Some(mismatch) = mismatch_opt {
524 causes.push(mismatch);
525 } else {
526 return None;
527 }
528 }
529
530 report(causes.is_empty(), causes)
531 }
532
533 ShapeCase::Name(name, weak) => {
534 if let Some(other_shape) = weak.upgrade(name) {
535 // If other is a bound named shape reference, pretend we
536 // validated against the named shape.
537 return self.validate(&other_shape);
538 }
539 // When other is an unbound named shape reference, it is
540 // accepted/validated by no shape except itself.
541 report(other.case == self.case, Vec::new())
542 }
543 }
544 }
545}