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 // If the item shape does not validate
335 // other, we need to report it.
336 causes.push(mismatch);
337 }
338 } else if let Some(mismatch) = self_item.validate(other_tail) {
339 causes.push(mismatch);
340 }
341 } else if !self_tail.is_none() {
342 if let Some(other_item) = other_prefix.get(i) {
343 if let Some(mismatch) = self_tail.validate(other_item) {
344 // If the tail shape does not validate
345 // other, we need to report it.
346 causes.push(mismatch);
347 }
348 } else if let Some(mismatch) = self_tail.validate(other_tail) {
349 causes.push(mismatch);
350 }
351 }
352 }
353
354 if !causes.is_empty() {
355 return report(false, causes);
356 }
357
358 #[allow(clippy::match_same_arms)]
359 match (self_tail.case(), other_tail.case()) {
360 // If neither other nor self have a rest shape (and
361 // self_prefix validates prefix), self validates other.
362 (ShapeCase::None, ShapeCase::None) => None,
363 // If other has no rest shape while self does, other
364 // will always be a static tuple of elements that we
365 // know satisfies self. self may permit additional rest
366 // elements, but their absence does not prevent
367 // validation.
368 (_, ShapeCase::None) => None,
369 // If other has a rest shape but self does not, self has
370 // no expectations about other's rest shape (and we
371 // already checked prefixes), so self validates other.
372 (ShapeCase::None, _) => None,
373 // If ShapeCase::None is not involved on either side,
374 // then self expects a certain rest shape and other has
375 // its own rest shape, so self_tail must validate
376 // other_tail for self to validate other.
377 _ => {
378 if let Some(mismatch) = self_tail.validate(other_tail) {
379 // If the tail shape does not validate other,
380 // we need to report it.
381 causes.push(mismatch);
382 }
383 report(causes.is_empty(), causes)
384 }
385 }
386 }
387
388 // We already handled the ::One and ::All cases above.
389 _ => report(false, Vec::new()),
390 },
391
392 ShapeCase::Object { fields, rest } => match self.case() {
393 ShapeCase::Object {
394 fields: self_fields,
395 rest: self_rest,
396 } => {
397 let mut causes = Vec::new();
398
399 // Check that all fields expected by self are present in
400 // other.
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 // If the field shape does not validate other,
405 // we need to report it.
406 causes.push(mismatch);
407 }
408 } else {
409 // Optional properties of shape S can be represented
410 // by a Shape::one(&[S, Shape::none()]) field_shape
411 // in self_fields, which accept/validate None (that
412 // is, the shape of the missing field in other).
413 if let Some(mismatch) = field_shape.validate(&Shape::none()) {
414 causes.push(mismatch);
415 }
416 }
417 }
418
419 if !causes.is_empty() {
420 return report(false, causes);
421 }
422
423 #[allow(clippy::match_same_arms)]
424 match (rest.case(), self_rest.case()) {
425 // If neither other nor self have a rest shape (and
426 // self_fields validates fields), self validates other.
427 (ShapeCase::None, ShapeCase::None) => None,
428 // If other has a rest shape but self does not, self has
429 // no expectations about other's rest shape (and we already
430 // checked static fields), so self validates other.
431 (_, ShapeCase::None) => None,
432 // If other has no rest shape while self does, other
433 // will always be a static set of fields that we know
434 // self validates. self may permit additional rest
435 // properties, but their absence does not prevent
436 // validation.
437 (ShapeCase::None, _) => None,
438 // If ShapeCase::None is not involved on either side,
439 // then self expects a certain rest shape and other has
440 // its own rest shape, so self_rest must validate rest.
441 _ => {
442 if let Some(mismatch) = self_rest.validate(rest) {
443 // If the rest shape does not validate other,
444 // we need to report it.
445 causes.push(mismatch);
446 }
447 report(causes.is_empty(), causes)
448 }
449 }
450 }
451
452 // We already handled the ::One and ::All cases above.
453 _ => report(false, Vec::new()),
454 },
455
456 // If *other* is a ShapeCase::One union, then every possibility must
457 // be validated by self. For example, if other is One<true, false>,
458 // and self is Bool, then since true and false are each individually
459 // validated by Bool, Bool validates the union One<true, false>.
460 ShapeCase::One(other_shapes) => {
461 // If other is an empty union (Never), then only None or other
462 // Never shapes can validate it. We already handled the case
463 // when self is Never in the first match, so here we only need
464 // to check for None.
465 if other_shapes.is_empty() {
466 return if self.is_none() {
467 None
468 } else {
469 Some(ShapeMismatch {
470 expected: self.clone(),
471 received: other.clone(),
472 causes: Vec::new(),
473 })
474 };
475 }
476
477 let mut causes = Vec::new();
478
479 for other_shape in other_shapes.iter() {
480 if let Some(mismatch) = self.validate(other_shape) {
481 // If the union member does not validate self, we need
482 // to report it.
483 causes.push(mismatch);
484 }
485 }
486
487 report(causes.is_empty(), causes)
488 }
489
490 // If other is a ShapeCase::All intersection, then it is validated
491 // by self if any of the member shapes are validated by self.
492 ShapeCase::All(other_shapes) => {
493 let mut causes = Vec::new();
494
495 for other_shape in other_shapes.iter() {
496 let mismatch_opt = self.validate(other_shape);
497 if let Some(mismatch) = mismatch_opt {
498 causes.push(mismatch);
499 } else {
500 return None;
501 }
502 }
503
504 report(causes.is_empty(), causes)
505 }
506
507 ShapeCase::Name(name, weak) => {
508 if let Some(other_shape) = weak.upgrade(name) {
509 // If other is a bound named shape reference, pretend we
510 // validated against the named shape.
511 return self.validate(&other_shape);
512 }
513 // When other is an unbound named shape reference, it is
514 // accepted/validated by no shape except itself.
515 report(other.case == self.case, Vec::new())
516 }
517 }
518 }
519}