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. If it validates other (validate returns
156 // None), `?` returns None early, skipping the rest of the
157 // shapes.
158 let mismatch = self_shape.validate(other)?;
159 // If the unbound named shape does not validate other, we
160 // need to report it.
161 causes.push(mismatch);
162 not_bound_names.insert(self_shape);
163 }
164
165 for target_shape in &bound_name_target_shapes {
166 // If we resolved a bound name to a shape we've already
167 // seen, we do not need to validate it again.
168 if !not_bound_names.contains(target_shape) {
169 // If the bound named shape validates other (validate
170 // returns None), `?` returns None early, skipping the
171 // rest of the shapes.
172 let mismatch = target_shape.validate(other)?;
173 // If the bound named shape does not validate other, we
174 // need to report it.
175 causes.push(mismatch);
176 }
177 }
178
179 // A single union member can cover only part of other when
180 // other hides a union inside a field or item position. No
181 // member of One<{a: Int}, {a: String}> accepts
182 // {a: One<Int, String>} whole, even though every value of the
183 // latter belongs to one of the former. Distributing those
184 // inner unions yields branches the members can cover one at a
185 // time, so the union validates other if it validates every
186 // branch.
187 //
188 // Rather than materializing the whole cartesian product of
189 // union-typed positions, split one position at a time. Each
190 // child re-enters this arm, which tries every member whole
191 // before splitting again, so a child already covered by a
192 // single member prunes every completion below it without
193 // examining any of them. The full product is only ever walked
194 // when no member covers anything until the leaves.
195 if split_branch_count(other) <= MAX_SPLIT_BRANCHES {
196 if let Some(children) = split_alternatives(other) {
197 if children.iter().all(|child| self.accepts(child)) {
198 return None;
199 }
200 }
201 }
202
203 // Importantly, we do not return false here (in contrast with
204 // the ::All case below), because the union might still validate
205 // other, e.g. when other is Bool and the union contains both
206 // true and false as members.
207 //
208 // We will need to handle ShapeCase::One logic in the ::Bool
209 // case below, but otherwise the loop above saves most of the
210 // cases below from explicitly worrying about self being a
211 // ShapeCase::One.
212 causes
213 }
214
215 ShapeCase::All(self_shapes) => {
216 let mut causes = Vec::new();
217
218 for self_shape in self_shapes.iter() {
219 if let Some(mismatch) = self_shape.validate(other) {
220 // If the intersection member does not validate other,
221 // we need to report it.
222 causes.push(mismatch);
223 }
224 }
225
226 return report(causes.is_empty(), causes);
227 }
228
229 // Sometimes we don't know anything (yet) about the structure of a
230 // shape, but still want to refer to it by name and access the
231 // shapes of subproperties (symbolically if not concretely). That's
232 // what the ShapeCase::Name variant models.
233 ShapeCase::Name(name, weak) => {
234 return if let Some(named_shape) = weak.upgrade(name) {
235 named_shape.validate(other)
236 } else {
237 // When self is an unbound named shape reference, it
238 // validates any other shape trivially, since it imposes no
239 // expectations on the other shape (and could eventually
240 // resolve to a shape that validates other).
241 None
242 };
243 }
244
245 ShapeCase::Unknown => {
246 // Unknown shapes validate any shape.
247 return None;
248 }
249
250 _ => Vec::new(),
251 };
252
253 match other.case() {
254 ShapeCase::Bool(Some(value)) => report(
255 match self.case() {
256 ShapeCase::Bool(self_value) => {
257 Some(value) == self_value.as_ref() || self_value.is_none()
258 }
259 // We already handled the ::One and ::All cases above.
260 _ => false,
261 },
262 self_causes,
263 ),
264
265 ShapeCase::Bool(None) => report(
266 (|| match self.case() {
267 ShapeCase::Bool(None) => true,
268
269 // This case goes beyond the basic ShapeCase::One handling
270 // provided at the top of the function, because we want to allow
271 // ::Bool(None) to be validated by a union of true and false.
272 ShapeCase::One(self_shapes) => {
273 let true_shape = Shape::bool_value(true, []);
274 let false_shape = Shape::bool_value(false, []);
275 let mut true_found = false;
276 let mut false_found = false;
277
278 for self_shape in self_shapes.iter() {
279 // Note the direction: the question is whether a
280 // member CONTAINS true, not whether it is
281 // contained in {true}. The two coincide on the
282 // shapes simplification can produce, since the
283 // only simplified member contained in {true} is
284 // the true literal itself, which is why the
285 // reversed test was harmless. It is still the
286 // wrong question, and it stops being harmless the
287 // moment an unsimplified union reaches here.
288 if self_shape.accepts(&true_shape) {
289 true_found = true;
290 }
291 if self_shape.accepts(&false_shape) {
292 false_found = true;
293 }
294 // Between them the members cover both booleans, so
295 // the union covers Bool.
296 if true_found && false_found {
297 // Returns from the (|| match ...)() closure.
298 return true;
299 }
300 }
301
302 false
303 }
304
305 _ => false,
306 })(),
307 self_causes,
308 ),
309
310 ShapeCase::String(value) => report(
311 match self.case() {
312 ShapeCase::String(self_value) => value == self_value || self_value.is_none(),
313 // We already handled the ::One case above.
314 _ => false,
315 },
316 self_causes,
317 ),
318
319 ShapeCase::Int(value) => report(
320 match self.case() {
321 ShapeCase::Int(self_value) => value == self_value || self_value.is_none(),
322 // All Int values are also (trivially convertible to) Float
323 // values, so Int is a subshape of Float.
324 ShapeCase::Float => true,
325 // We already handled the ::One case above.
326 _ => false,
327 },
328 self_causes,
329 ),
330
331 ShapeCase::Float => report(matches!(self.case(), ShapeCase::Float), Vec::new()),
332
333 // Both ::Null and ::None accept/validate only themselves, but they
334 // have an important difference in behavior when they appear in
335 // ::All intersections. The null value "poisons" intersections,
336 // reducing the whole intersection to null, which can be appropriate
337 // behavior when reporting certain kinds of top-level errors. The
338 // None value simply disappears from intersections, as it imposes no
339 // additional constraints on the intersection shape.
340 ShapeCase::Null => report(matches!(self.case(), ShapeCase::Null), Vec::new()),
341 ShapeCase::None => report(matches!(self.case(), ShapeCase::None), Vec::new()),
342
343 // ShapeCase::Unknown is validated by no other shapes except itself.
344 // We already handled the case when self is ::Unknown above, so we
345 // can report false here.
346 ShapeCase::Unknown => report(false, Vec::new()),
347
348 ShapeCase::Array {
349 prefix: other_prefix,
350 tail: other_tail,
351 } => match self.case() {
352 ShapeCase::Array {
353 prefix: self_prefix,
354 tail: self_tail,
355 } => {
356 let mut causes = Vec::new();
357
358 for i in 0..self_prefix.len().max(other_prefix.len()) {
359 if let Some(self_item) = self_prefix.get(i) {
360 if let Some(other_item) = other_prefix.get(i) {
361 if let Some(mismatch) = self_item.validate(other_item) {
362 causes.push(mismatch);
363 }
364 } else {
365 // other is shorter, so position i in other is
366 // either governed by other_tail or absent
367 // entirely, since a tailed array may end at
368 // any length. self_item has to accept both
369 // possibilities: checking only other_tail
370 // accepts [Int, Int, ...] against
371 // [Int, ...Int], which the value [5] refutes.
372 // This mirrors the One<None, rest> probe the
373 // object walk already uses for a field other
374 // does not declare.
375 let possible = if other_tail.is_unknown() {
376 // One<None, Unknown> simplifies to Unknown.
377 other_tail.clone()
378 } else {
379 Shape::one([Shape::none(), other_tail.clone()], [])
380 };
381 if let Some(mismatch) = self_item.validate(&possible) {
382 causes.push(mismatch);
383 }
384 }
385 } else if let Some(other_item) = other_prefix.get(i) {
386 // self has no prefix position i; self_tail
387 // governs.
388 if self_tail.is_none() {
389 // self is closed at length self_prefix.len()
390 // but other carries another element here.
391 causes.push(ShapeMismatch {
392 expected: self.clone(),
393 received: other.clone(),
394 causes: Vec::new(),
395 });
396 } else if let Some(mismatch) = self_tail.validate(other_item) {
397 causes.push(mismatch);
398 }
399 }
400 // `i < max(self_prefix.len(), other_prefix.len())`
401 // guarantees at least one of the two `get(i)` calls
402 // above returns `Some`, so there is no else branch.
403 }
404
405 #[allow(clippy::match_same_arms)]
406 match (self_tail.case(), other_tail.case()) {
407 // other's tail is None, so it is effectively a fixed
408 // tuple; nothing more to check against self_tail.
409 (_, ShapeCase::None) => {}
410 // self is closed but other has a tail, so other may
411 // carry elements beyond self_prefix.len() that self
412 // cannot accept.
413 (ShapeCase::None, _) => {
414 causes.push(ShapeMismatch {
415 expected: self.clone(),
416 received: other.clone(),
417 causes: Vec::new(),
418 });
419 }
420 _ => {
421 if let Some(mismatch) = self_tail.validate(other_tail) {
422 causes.push(mismatch);
423 }
424 }
425 }
426
427 report(causes.is_empty(), causes)
428 }
429
430 // We already handled the ::One and ::All cases above.
431 _ => report(false, Vec::new()),
432 },
433
434 ShapeCase::Object { fields, rest } => match self.case() {
435 ShapeCase::Object {
436 fields: self_fields,
437 rest: self_rest,
438 } => {
439 let mut causes = Vec::new();
440
441 // For each field self declares, determine the shape it
442 // can take under `other` and check self's expectation
443 // accepts it.
444 for (field_name, field_shape) in self_fields {
445 if let Some(other_field_shape) = fields.get(field_name) {
446 if let Some(mismatch) = field_shape.validate(other_field_shape) {
447 causes.push(mismatch);
448 }
449 } else {
450 // other does not declare field_name. Under other,
451 // v.field_name is either absent (None) or, if
452 // other has a non-None rest shape, a dynamic
453 // property of that rest shape. Self must accept
454 // any such possibility.
455 if rest.is_none() {
456 // Field is guaranteed absent under other;
457 // self must tolerate None (be optional).
458 if let Some(mismatch) = field_shape.validate(&Shape::none()) {
459 causes.push(mismatch);
460 }
461 } else if rest.is_unknown() {
462 // `One<None, Unknown>` simplifies to `Unknown`,
463 // which is the most permissive shape — it
464 // validates `field_shape` iff `field_shape`
465 // validates `Unknown`. This is the new
466 // open-by-default case after 0.8.0; short-
467 // circuiting it skips an allocation-heavy
468 // `Shape::one([Shape::none(), ...])` build per
469 // missing field per `accepts` call.
470 if let Some(mismatch) = field_shape.validate(rest) {
471 causes.push(mismatch);
472 }
473 } else {
474 let possible = Shape::one([Shape::none(), rest.clone()], []);
475 if let Some(mismatch) = field_shape.validate(&possible) {
476 causes.push(mismatch);
477 }
478 }
479 }
480 }
481
482 // For each field other declares that self does not, the
483 // field must be absorbed by self's rest shape. A closed
484 // self (rest: None) cannot absorb any extra declared
485 // field.
486 for (field_name, other_field_shape) in fields {
487 if self_fields.contains_key(field_name) {
488 continue;
489 }
490 // A field whose shape admits no value is provably
491 // always absent, so it constrains nothing and there is
492 // nothing for self's rest to absorb. Skipping it is
493 // exact, not generous, and it has to happen on both
494 // sides of the closed/open split below: skipping it
495 // only for a closed self is what made accepts
496 // non-transitive, since a closed middle shape could
497 // accept such a field while an open outer shape that
498 // accepts the middle could not.
499 if other_field_shape.is_none() || other_field_shape.is_never() {
500 continue;
501 }
502 if self_rest.is_none() {
503 causes.push(ShapeMismatch {
504 expected: self.clone(),
505 received: other.clone(),
506 causes: Vec::new(),
507 });
508 } else if let Some(mismatch) = self_rest.validate(other_field_shape) {
509 causes.push(mismatch);
510 }
511 }
512
513 // Finally, reconcile the two rest shapes themselves.
514 match (rest.case(), self_rest.case()) {
515 // Either other declares no dynamic properties, so
516 // there is nothing more for self.rest to absorb,
517 // regardless of whether self is open or closed.
518 (ShapeCase::None, _) => {}
519 // other permits dynamic properties but self is
520 // closed — other's values can carry extras that
521 // self does not permit.
522 (_, ShapeCase::None) => {
523 causes.push(ShapeMismatch {
524 expected: self.clone(),
525 received: other.clone(),
526 causes: Vec::new(),
527 });
528 }
529 // Both sides permit dynamic properties; self's rest
530 // must be at least as permissive as other's.
531 _ => {
532 if let Some(mismatch) = self_rest.validate(rest) {
533 causes.push(mismatch);
534 }
535 }
536 }
537
538 report(causes.is_empty(), causes)
539 }
540
541 // We already handled the ::One and ::All cases above.
542 _ => report(false, Vec::new()),
543 },
544
545 // If *other* is a ShapeCase::One union, then every possibility must
546 // be validated by self. For example, if other is One<true, false>,
547 // and self is Bool, then since true and false are each individually
548 // validated by Bool, Bool validates the union One<true, false>.
549 ShapeCase::One(other_shapes) => {
550 // If other is an empty union (Never), then only None or other
551 // Never shapes can validate it. We already handled the case
552 // when self is Never in the first match, so here we only need
553 // to check for None.
554 if other_shapes.is_empty() {
555 return if self.is_none() {
556 None
557 } else {
558 Some(ShapeMismatch {
559 expected: self.clone(),
560 received: other.clone(),
561 causes: Vec::new(),
562 })
563 };
564 }
565
566 let mut causes = Vec::new();
567
568 for other_shape in other_shapes.iter() {
569 if let Some(mismatch) = self.validate(other_shape) {
570 // If the union member does not validate self, we need
571 // to report it.
572 causes.push(mismatch);
573 }
574 }
575
576 report(causes.is_empty(), causes)
577 }
578
579 // If other is a ShapeCase::All intersection, then it is validated
580 // by self if any of the member shapes are validated by self.
581 ShapeCase::All(other_shapes) => {
582 let mut causes = Vec::new();
583
584 for other_shape in other_shapes.iter() {
585 // If self validates this member (validate returns None), `?`
586 // returns None early — the intersection is validated.
587 let mismatch = self.validate(other_shape)?;
588 causes.push(mismatch);
589 }
590
591 report(causes.is_empty(), causes)
592 }
593
594 ShapeCase::Name(name, weak) => {
595 if let Some(other_shape) = weak.upgrade(name) {
596 // If other is a bound named shape reference, pretend we
597 // validated against the named shape.
598 return self.validate(&other_shape);
599 }
600 // When other is an unbound named shape reference, it is
601 // accepted/validated by no shape except itself.
602 report(other.case == self.case, Vec::new())
603 }
604 }
605 }
606}
607
608/// Upper bound on the number of leaves the union splitting search may walk.
609/// Splitting distributes a cartesian product over union-typed positions, so a
610/// shape with several of them can blow up combinatorially. Exceeding the bound
611/// abandons the search, which costs only precision: `validate` then reports the
612/// same mismatch it would have reported before splitting existed.
613///
614/// Note that the bound is a cliff for transitivity, not just precision: below
615/// it, the split makes acceptance compose along chains the sweep test
616/// exercises; above it, the fallback answer does not. So `accepts` is known
617/// non-transitive for chains that straddle the bound — there is a witness
618/// whose acceptance flips exactly at 64 branches, pinned by
619/// `test_union_splitting_cliff_at_the_branch_bound`. The Lean model on the
620/// `lean-model` branch omits this splitting clause entirely (its divergence
621/// 5), in part because such cases do not compose under it.
622const MAX_SPLIT_BRANCHES: usize = 64;
623
624/// Counts the leaves a full split of `shape` would produce, saturating rather
625/// than overflowing. This is the cheap upfront guard for the search in
626/// `validate`: it walks the shape once and allocates nothing, where building
627/// the branches would allocate all of them.
628fn split_branch_count(shape: &Shape) -> usize {
629 match shape.case() {
630 // Saturating like the arms below, not `sum()`: the products they build
631 // reach `usize::MAX` on shapes with enough union-typed positions, and
632 // adding two saturated counts overflows.
633 ShapeCase::One(shapes) => shapes
634 .iter()
635 .map(split_branch_count)
636 .fold(0, usize::saturating_add),
637
638 ShapeCase::Object { fields, .. } => fields
639 .values()
640 .map(split_branch_count)
641 .fold(1, usize::saturating_mul),
642
643 ShapeCase::Array { prefix, .. } => prefix
644 .iter()
645 .map(split_branch_count)
646 .fold(1, usize::saturating_mul),
647
648 _ => 1,
649 }
650}
651
652/// Replaces one union-typed position of `shape` with each member of that
653/// union, returning the resulting shapes, or `None` when `shape` has no
654/// union-typed position to split.
655///
656/// The returned shapes are strictly smaller than `shape`, since each drops a
657/// union node in favor of one of its members. That is what makes the search in
658/// `validate` terminate.
659///
660/// For example `{a: One<Int, String>, b: Bool}` yields `{a: Int, b: Bool}` and
661/// `{a: String, b: Bool}`. Only the first splittable position found is
662/// expanded; the caller recurses to reach the rest. A more sophisticated
663/// version could order positions by which one best discriminates among the
664/// union members, the way a word search tries the rarest letter first, but the
665/// prune that matters is the caller's, which tests whole members before
666/// splitting again.
667///
668/// Three positions deliberately never split:
669///
670/// * `rest` and `tail` shapes, which constrain unboundedly many values that
671/// each choose independently. Distributing them would lose meaning, since
672/// `{...One<Int, String>}` accepts `{"p": 1, "q": "s"}` while neither
673/// `{...Int}` nor `{...String}` does.
674/// * Members of a [`ShapeCase::All`] intersection, which the intersection
675/// itself is responsible for resolving.
676/// * [`ShapeCase::Name`] references, so splitting cannot follow a cycle.
677fn split_alternatives(shape: &Shape) -> Option<Vec<Shape>> {
678 match shape.case() {
679 ShapeCase::One(shapes) => {
680 let members: Vec<Shape> = shapes.iter().cloned().collect();
681 // A union of one member, or the empty union, offers no choice to
682 // distribute. Returning None for the singleton case also keeps the
683 // caller from recursing on an unchanged shape forever.
684 if members.len() > 1 {
685 Some(members)
686 } else {
687 None
688 }
689 }
690
691 ShapeCase::Object { fields, rest } => {
692 for (key, field_shape) in fields {
693 let Some(options) = split_alternatives(field_shape) else {
694 continue;
695 };
696 return Some(
697 options
698 .into_iter()
699 .map(|option| {
700 let mut split_fields = fields.clone();
701 split_fields.insert(key.clone(), option);
702 Shape::object(split_fields, rest.clone(), shape.locations().cloned())
703 })
704 .collect(),
705 );
706 }
707 None
708 }
709
710 ShapeCase::Array { prefix, tail } => {
711 for (index, item_shape) in prefix.iter().enumerate() {
712 let Some(options) = split_alternatives(item_shape) else {
713 continue;
714 };
715 return Some(
716 options
717 .into_iter()
718 .map(|option| {
719 let mut split_prefix = prefix.clone();
720 split_prefix[index] = option;
721 Shape::array(split_prefix, tail.clone(), shape.locations().cloned())
722 })
723 .collect(),
724 );
725 }
726 None
727 }
728
729 _ => None,
730 }
731}