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