shape/

accepts.rs

use std::cell::RefCell;
use std::collections::HashMap;

use indexmap::IndexSet;

use super::Shape;
use super::ShapeCase;

/// The `Shape::validate*` methods return a vector of `ShapeMismatch` errors
/// that is non-empty when validation fails.
///
/// Each `ShapeMismatch` error contains the `expected` shape and the `received`
/// shape, whose metadata (e.g. shape.locations) provide context for the
/// mismatch.
///
/// Conveniently, the `expected`/`received` terminology works for both the
/// `expected.accepts(received)` and `received.satisfies(expected)` directions
/// of comparison, so `ShapeMismatch` does not encode whether the `accepts` or
/// `satisfies` was used internally (though `validate` is similar to `accepts`
/// in its order of arguments).
///
/// Once issue #5 is implemented, you'll be able to obtain source location
/// information from the `expected` and `received` shapes (instead of adding
/// additional fields to the `ShapeMismatch` struct).
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub struct ShapeMismatch {
    pub expected: Shape,
    pub received: Shape,
    pub causes: Vec<ShapeMismatch>,
}

/// Answers already computed during one top-level [`Shape::validate`] call, so
/// a question the search asks twice is answered once.
///
/// Keyed structurally, on the pair of shapes and the split depth the answer was
/// computed at. Structural keying is affordable only because each case stores
/// its hash (see `CaseWithHash`): hashing a key is two field reads rather than
/// two walks, and the walk is the work the memo exists to avoid. Address
/// keying was the alternative and is strictly weaker -- it hits only when the
/// repeated question is a repetition of the *same* allocation, and misses every
/// shape that was rebuilt rather than cloned, which is common enough to have
/// turned a measured win into overhead.
///
/// The depth belongs in the key because the bound is a path property: an answer
/// computed with one distribution remaining is not necessarily the answer with
/// three. Keyed that precisely, a hit is exactly what the search would have
/// recomputed, so the memo can change how long a comparison takes and never
/// what it answers. That is the difference between this and the comparison
/// meter the crate used to carry, whose shared state was itself part of the
/// answer.
///
/// "What it answers" is the verdict. The `ShapeMismatch` a hit returns is a
/// different matter, because `PartialEq for Shape` ignores metadata: two
/// occurrences of the same shapes at different source locations share an
/// entry, and the entry holds whichever pair asked first. The outer frame of a
/// hit is therefore rebuilt from the shapes in hand (see
/// [`Shape::validate_within`]), so `expected` and `received` always carry the
/// locations of the comparison that was actually made. The `causes` below
/// that frame are not rebuilt: a location one level down on a memo hit may
/// belong to another structurally identical occurrence of the same pair.
/// Re-anchoring the whole tree is well defined for the same reason the hit is
/// sound, and can be done if a consumer comes to need it.
///
/// [`MAX_SPLIT_DEPTH`] leans on this memo. Its value of twelve is affordable
/// only because the member loop's repeated union-against-subtree questions are
/// answered once; without the memo the nested doomed families take minutes
/// rather than milliseconds, and the tests that pin the depth cap do not
/// finish. Weakening the memo therefore hangs the suite rather than failing
/// it, which is worth knowing before touching either.
///
/// Equality is verified rather than assumed: a bucket collision falls through
/// to `PartialEq for Shape`, which short-circuits on pointer equality before
/// walking. Trusting the 64-bit hash alone would be faster and is very
/// probably safe at the few thousand keys one comparison generates, but a type
/// system should not answer a subtyping question wrongly with any probability
/// at all.
///
/// The map lives on the stack of one `validate` call and is dropped with it,
/// so nothing is retained between comparisons. It is wrapped in an `Option` so
/// that a comparison which never meets a union constructs nothing but a null:
/// an empty `HashMap` does not allocate, but building one is not free either,
/// and `validate` is called often enough on trivially cheap pairs that a fixed
/// cost there is measurable (17ns per call when the map was built eagerly).
type SplitMemo = RefCell<Option<HashMap<MemoKey, Option<ShapeMismatch>>>>;

/// Expected shape, received shape, and the number of distributions already
/// taken on the path to the comparison.
type MemoKey = (Shape, Shape, usize);

/// The (expected, received) pairs whose comparison is already in progress on
/// the path from the top of one `validate` call down to here, recorded at
/// every hop that resolves a bound [`ShapeCase::Name`] reference: the two
/// `::Name` arms of `validate_uncached` and the union member deferral loop.
///
/// Name resolution is the only recursion in `validate` that does not descend
/// into a strictly smaller shape: every other arm walks a finite tree, so an
/// infinite descent must pass through a guarded resolution hop on every lap,
/// and a lap that arrives at a pair already on this path will repeat
/// deterministically forever. When such a revisit is detected, the pair is
/// *assumed* valid and the answer is `None` -- the coinductive hypothesis,
/// which the enclosing occurrence of the same comparison is still in the
/// process of discharging. A descent that would find a mismatch finds it
/// before the pair can recur, since everything after the recurrence is an
/// exact repetition of what already ran, so the hypothesis never hides
/// evidence that exists.
///
/// What a hypothesis must not do is leak. An answer computed while a
/// hypothesis is live rests on it, and the hypothesis holds only until the
/// frame that owns its pair completes -- which may refute it. [`SplitMemo`]
/// answers questions for the rest of the `validate` call, including from
/// contexts where a given hypothesis had already been refuted or never
/// applied, so an answer computed under a live hypothesis must never be
/// memoized. `lowest_assumed` makes that decidable: it is the smallest path
/// index of any hypothesis assumed anywhere in the subtree currently being
/// computed, and because a hypothesis about a pair is discharged when that
/// pair's own frame pops, it is always either `usize::MAX` (nothing assumed)
/// or the index of a pair still on the path, meaning the answer in progress
/// still rests on it. `starved` plays the same role for depth-cap answers
/// (see [`MAX_VALIDATE_DEPTH`]), which are approximations tuned to the
/// budget that produced them.
///
/// The path holds the shapes themselves rather than their stored hashes:
/// `PartialEq` compares the hashes first, so each probe of the stack costs
/// two loads per entry, and keeping the whole pair means the answer never
/// depends on a 64-bit collision going the right way. A `Vec` rather than a
/// set because an empty `Vec` never allocates, and a comparison that never
/// resolves a bound name -- the overwhelming majority -- pays nothing at
/// all.
struct Resolving {
    path: Vec<(Shape, Shape)>,
    /// Smallest `path` index of any hypothesis assumed in the subtree
    /// currently being computed; `usize::MAX` when it has assumed none.
    /// `validate_within` saves, resets, and merges this around each memoized
    /// subtree, so at memo time it describes exactly that subtree.
    lowest_assumed: usize,
    /// Whether the depth cap fired anywhere in the subtree currently being
    /// computed, saved and merged alongside `lowest_assumed`.
    starved: bool,
}

impl Default for Resolving {
    fn default() -> Self {
        Resolving {
            path: Vec::new(),
            lowest_assumed: usize::MAX,
            starved: false,
        }
    }
}

type ResolvingPairs = RefCell<Resolving>;

/// Runs `f` with `pair` on the resolving path, or answers `None` -- the
/// coinductive hypothesis -- if `pair` is already on it.
///
/// A hypothesis is scoped to the frame that owns its pair: it is discharged
/// when that frame pops, because by then the pair's verdict stands on its
/// own, the frame having either found real evidence or completed the
/// coinductive proof. So a revisit only records the assumed pair's index in
/// `lowest_assumed`, and when this frame pops, every hypothesis at its own
/// index is discharged with it. Indices below it belong to pairs still on
/// the path (stack discipline means nothing deeper survives to this point),
/// so those stay live; indices above it cannot occur, because a deeper
/// pair's pop has already discharged its own hypotheses by the time it
/// merged its accounting upward.
fn guarded(
    resolving: &ResolvingPairs,
    pair: (Shape, Shape),
    f: impl FnOnce() -> Option<ShapeMismatch>,
) -> Option<ShapeMismatch> {
    let index = {
        let mut r = resolving.borrow_mut();
        if let Some(i) = r.path.iter().position(|p| *p == pair) {
            r.lowest_assumed = r.lowest_assumed.min(i);
            return None;
        }
        r.path.push(pair);
        r.path.len() - 1
    };
    let mismatch = f();
    let mut r = resolving.borrow_mut();
    r.path.pop();
    debug_assert_eq!(r.path.len(), index);
    // Discharge hypotheses about this pair; keep any about pairs still on
    // the path above.
    if r.lowest_assumed >= index {
        r.lowest_assumed = usize::MAX;
    }
    mismatch
}

/// The deepest `validate_within` recursion one comparison will perform before
/// declining to look further, returning `None` -- no mismatch found -- for
/// anything deeper.
///
/// This is stack-overflow insurance, not semantics. Every other bound in this
/// file is a structural fact about the shapes, but this one exists because the
/// recursion runs on the native call stack, which is finite and shared with
/// whoever called `validate`. The budget counts `validate_within` frames, not
/// semantic levels: one level of a shape costs one frame in a plain list,
/// two in a record, and four to six when a bound `Name` resolves along the
/// way, so 128 frames covers anywhere from ~128 levels of structural nesting
/// down to ~25 levels of nullable-named-field chaining.
///
/// The value is measured, not guessed. In the debug profile on a 2MiB stack
/// -- the smallest default stack in play, used by both Rust test threads and
/// tokio workers -- descent overflows at roughly 300 frames for the fattest
/// measured family (records chained through `One<Name, null>` fields, the
/// connectors shape) and roughly 470 for the leanest (nested lists); the
/// per-frame cost is dominated by this function's own locals and runs
/// 4.5-9KB. 128 retains at least a 2.3x margin under the worst measurement,
/// and release frames are several times smaller still. Fully validating a
/// document at `serde_json`'s default 128-level nesting limit would take
/// ~256 frames, which 2MiB debug stacks cannot afford; that gap is the
/// known price of fail-open insurance, and closing it belongs to shrinking
/// the frame, not raising the budget.
///
/// The failure direction at the cap is open, matching what the `::Name` arms
/// already do for unbound names: a comparison too deep to finish is accepted
/// rather than reported. A cap high enough to be unreachable in practice is
/// what makes that acceptable -- it can only fire on inputs no honest schema
/// or default-configured parser produces, where the alternative is a process
/// abort. Because a starved answer is an approximation of what a
/// better-funded comparison would compute, `depth_remaining` is not part of
/// [`MemoKey`]; instead, starvation is tracked in [`Resolving`], and a
/// starved answer is never memoized at all. The memo only ever serves what
/// the search would recompute with the hypothesis slate clean and the budget
/// intact.
pub(crate) const MAX_VALIDATE_DEPTH: usize = 128;

impl Shape {
    /// Returns true if the other shape meets all the expectations of the self
    /// shape. In set theory terms, the set of all values accepted by other is a
    /// subset of the set of all values accepted by self.
    #[must_use]
    pub fn accepts(&self, other: &Shape) -> bool {
        self.validate(other).is_none()
    }

    /// Returns true iff the given [`serde_json::Value`] satisfies self.
    #[must_use]
    pub fn accepts_json(&self, json: &serde_json::Value) -> bool {
        self.accepts(&Shape::from_json(json))
    }

    /// Returns true iff the given [`serde_json_bytes::Value`] satisfies self.
    pub fn accepts_json_bytes(&self, json: &serde_json_bytes::Value) -> bool {
        self.accepts(&Shape::from_json_bytes(json))
    }

    /// `Shape::validate_json` is to `Shape::validate` as `Shape::accepts_json`
    /// is to `Shape::accepts`.
    #[must_use]
    pub fn validate_json(&self, json: &serde_json::Value) -> Option<ShapeMismatch> {
        self.validate(&Shape::from_json(json))
    }

    /// `Shape::validate_json_bytes` is to `Shape::validate` as
    /// `Shape::accepts_json_bytes` is to `Shape::accepts`.
    pub fn validate_json_bytes(&self, json: &serde_json_bytes::Value) -> Option<ShapeMismatch> {
        self.validate(&Shape::from_json_bytes(json))
    }

    /// Returns `true` if the `self` shape meets all the expectations of the
    /// `other` shape. In set theory terms, `self` satisfying `other` means the
    /// set of all values accepted by `self` is a subset of the set of all
    /// values accepted by `other`.
    ///
    /// The `satisfies` method is the inverse of the `accepts` method, in the
    /// sense that `a.accepts(b)` is equivalent to `b.satisfies(a)`. For
    /// historical reasons, the bulk of the `accepts`/`satisfies` logic happens
    /// in the internal `validate` method, though I have since realized
    /// the `accepts` direction generalizes a bit better to situations where
    /// `other` is not a `Shape`, such as `Shape::accepts_json(&self, json:
    /// &serde_json::Value)`.
    #[must_use]
    pub fn satisfies(&self, other: &Shape) -> bool {
        other.validate(self).is_none()
    }

    /// Validates that all expectations of the `self` shape are met by the
    /// `other` shape, erroring with a non-empty vector of `ShapeMismatch`
    /// errors when validation fails.
    #[must_use]
    pub fn validate(&self, other: &Shape) -> Option<ShapeMismatch> {
        // Nothing but a null until a union comparison needs somewhere to put an
        // answer, so a comparison that never meets a union pays nothing here.
        let memo = SplitMemo::default();
        let resolving = ResolvingPairs::default();
        self.validate_within(other, 0, MAX_VALIDATE_DEPTH, &memo, &resolving)
    }

    /// The body of [`Shape::validate`], carrying the union splitting search's
    /// depth.
    ///
    /// `splits_taken` counts the union positions distributed along the path
    /// from the top of this comparison down to here. Every recursion in the
    /// body passes it along unchanged -- member loops, name resolution, and
    /// each descent into a field or item -- and only the split recursion
    /// itself increments it. Descending into a field therefore does not hand
    /// back a fresh allowance, which is what makes [`MAX_SPLIT_DEPTH`] a bound
    /// on the whole comparison rather than on each object level separately. A
    /// per-level bound multiplies: with one union-typed field at each of d
    /// levels, one level's worst case is paid d times over.
    ///
    /// It is a property of the path and never a ledger of work done. Sibling
    /// comparisons do not spend each other's allowance, so the two fields of
    /// an object are compared with the same one, and a pair of shapes reached
    /// by the same number of distributions always answers the same way.
    ///
    /// `resolving` is the coinductive cycle guard for name resolution (see
    /// [`Resolving`]). Like `splits_taken` it is a property of the path:
    /// every recursion passes it along unchanged. The three hops that resolve
    /// a bound name -- the two `ShapeCase::Name` arms and the union member
    /// deferral loop -- push and probe its path through [`guarded`], and the
    /// memo below consults its hypothesis accounting before inserting.
    ///
    /// `depth_remaining` is the stack-overflow insurance budget (see
    /// [`MAX_VALIDATE_DEPTH`]). Each frame spends one unit on entry, so every
    /// recursion passes the already-decremented value along unchanged.
    #[must_use]
    fn validate_within(
        &self,
        other: &Shape,
        splits_taken: usize,
        depth_remaining: usize,
        memo: &SplitMemo,
        resolving: &ResolvingPairs,
    ) -> Option<ShapeMismatch> {
        // Past the depth cap, decline to look further and accept: see
        // MAX_VALIDATE_DEPTH for the measurement and the fail-open rationale.
        // Mark the subtree starved so the answer is never memoized for a
        // query holding more budget.
        if depth_remaining == 0 {
            resolving.borrow_mut().starved = true;
            return None;
        }
        let depth_remaining = depth_remaining - 1;

        // Only union comparisons are worth an entry. A union is the only
        // expected shape whose comparison searches, and it is where a repeated
        // question arrives: the fan-out that makes nesting expensive is the
        // member loop asking the same union-versus-subtree question once per
        // branch of every level above it. Everything else answers in time
        // proportional to the shapes themselves and would spend more on
        // bookkeeping than it saved.
        //
        // Restricting this further to comparisons inside an active search
        // (splits_taken > 0) was measured. It leaves the allocation baseline
        // untouched, but a union of records whose fields are wide unions never
        // starts a search at all and so never gets an entry: that family goes
        // from 4.6ms back to 402ms. The entries a top-level union comparison
        // makes are the ones its own subtree comparisons hit.
        if !matches!(self.case(), ShapeCase::One(_)) {
            return self.validate_uncached(other, splits_taken, depth_remaining, memo, resolving);
        }

        let key: MemoKey = (self.clone(), other.clone(), splits_taken);
        // The borrow ends with the statement, so the recursion below never runs
        // while the map is borrowed.
        if let Some(answer) = memo.borrow().as_ref().and_then(|map| map.get(&key)) {
            // The key is structural and `PartialEq for Shape` ignores metadata,
            // so the entry may have been computed for a different occurrence
            // of these shapes, carrying that occurrence's source locations.
            // The verdict is the same either way; the shapes on the mismatch
            // are not, and carrying that metadata is what `ShapeMismatch` is
            // for. Re-anchor the outer frame on the pair actually in hand.
            // The `causes` beneath it are kept as computed for the first
            // occurrence, so a location one level down may still belong to
            // another structurally identical pair; see the note on
            // `SplitMemo`.
            return answer.as_ref().map(|mismatch| ShapeMismatch {
                expected: self.clone(),
                received: other.clone(),
                causes: mismatch.causes.clone(),
            });
        }

        // An answer that rests on a live hypothesis or on an exhausted depth
        // budget is valid only in the context that produced it: serving it
        // to another occurrence of the same key would hand over an
        // assumption the asker did not make, or a leniency it did not need.
        // Account for this subtree alone, and memoize only what the search
        // would recompute anywhere. See Resolving.
        let (saved_lowest, saved_starved) = {
            let mut r = resolving.borrow_mut();
            (
                std::mem::replace(&mut r.lowest_assumed, usize::MAX),
                std::mem::replace(&mut r.starved, false),
            )
        };
        let answer = self.validate_uncached(other, splits_taken, depth_remaining, memo, resolving);
        let mut r = resolving.borrow_mut();
        if r.lowest_assumed == usize::MAX && !r.starved {
            memo.borrow_mut()
                .get_or_insert_with(HashMap::new)
                .insert(key, answer.clone());
        }
        r.lowest_assumed = saved_lowest.min(r.lowest_assumed);
        r.starved = saved_starved || r.starved;
        answer
    }

    /// The uncached body of [`Shape::validate_within`]. Call that instead; this
    /// exists only so the memo has a single place to wrap.
    #[allow(clippy::too_many_lines)]
    #[must_use]
    fn validate_uncached(
        &self,
        other: &Shape,
        splits_taken: usize,
        depth_remaining: usize,
        memo: &SplitMemo,
        resolving: &ResolvingPairs,
    ) -> Option<ShapeMismatch> {
        // Since self.case and other.case are the only information that
        // logically matters for validation, a shape accepts any shape whose
        // case equals its own, and we can skip doing any actual validation
        // work.
        //
        // Testing equality rather than pointer identity is what the stored
        // case hash buys: unequal cases are separated by comparing two u64s,
        // and equal ones are confirmed by `PartialEq for CaseWithHash`, which
        // short circuits on the pointer before walking. Pointer identity alone
        // caught only shapes that share an allocation, and misses the far more
        // common case of a shape rebuilt rather than cloned.
        if self.case == other.case {
            return None;
        }

        // Helper closure that translates boolean results to vector results. The
        // `path` and `mismatches` parameters are always the local parameter and
        // variable of the same names from the outer scope, but passing them in
        // this way simplifies ownership logic and strips mutability.
        let report = |is_valid: bool, causes: Vec<ShapeMismatch>| -> Option<ShapeMismatch> {
            if is_valid {
                // Use the report closure only in situations where the truth of
                // `is_valid` should hide any previous mismatches.
                None
            } else {
                Some(ShapeMismatch {
                    expected: self.clone(),
                    received: other.clone(),
                    causes,
                })
            }
        };

        let self_causes = match self.case() {
            ShapeCase::One(self_shapes) => {
                // If the union is empty (i.e. self.is_never()), then the only
                // other shapes that can be validated by this empty union are
                // other never shapes and None.
                if self_shapes.is_empty() {
                    return if other.is_never() || other.is_none() {
                        None
                    } else {
                        // Reporting this error is important, since there are no
                        // self shapes to produce mismatches below.
                        Some(ShapeMismatch {
                            expected: self.clone(),
                            received: other.clone(),
                            causes: Vec::new(),
                        })
                    };
                }

                // If other is validated by any single shape in self_shapes,
                // then other is validated by the union. However, we want to try
                // any shapes other than *bound* ShapeCase::Name shapes first,
                // since bound ::Name shapes are the gateway to infinite cycles,
                // and the names might resolve to shapes we've already seen in
                // the union, so we don't need to validate them again.
                let mut bound_name_target_shapes = Vec::new();

                // It's acceptable not to use a MergeSet<Shape> here, because we
                // don't care about name/location metadata, but only whether one
                // of the resolved bound_name_target_shapes is one we've seen already,
                // which concerns only ShapeCase equality/hashing.
                let mut not_bound_names: IndexSet<&Shape> = IndexSet::new();

                let mut causes = Vec::new();

                for self_shape in self_shapes.iter() {
                    if let ShapeCase::Name(name, weak) = self_shape.case() {
                        if let Some(named_shape) = weak.upgrade(name) {
                            // Handle in a later loop, keeping the reference
                            // itself: the deferral hop resolves a name, so it
                            // goes through the same guard as the ::Name arms.
                            bound_name_target_shapes.push((self_shape, named_shape));
                            continue;
                        }
                    }
                    // If self_shape is not a bound named shape, validate it
                    // against other. If it validates other (validate returns
                    // None), `?` returns None early, skipping the rest of the
                    // shapes.
                    let mismatch = self_shape.validate_within(
                        other,
                        splits_taken,
                        depth_remaining,
                        memo,
                        resolving,
                    )?;
                    // If the unbound named shape does not validate other, we
                    // need to report it.
                    causes.push(mismatch);
                    not_bound_names.insert(self_shape);
                }

                for (name_shape, target_shape) in &bound_name_target_shapes {
                    // If we resolved a bound name to a shape we've already
                    // seen, we do not need to validate it again.
                    if !not_bound_names.contains(target_shape) {
                        // If the bound named shape validates other (validate
                        // returns None), `?` returns None early, skipping the
                        // rest of the shapes. The hop resolves a name without
                        // passing through a ::Name arm, so it is guarded
                        // here: a union whose members are nothing but each
                        // other's names would otherwise lap this loop until
                        // the depth cap. (Such non-contractive cycles are
                        // degenerate -- the equations carry no structure --
                        // and unreachable from GraphQL, where fields always
                        // interpose an object between name references.)
                        let mismatch =
                            guarded(resolving, ((*name_shape).clone(), other.clone()), || {
                                target_shape.validate_within(
                                    other,
                                    splits_taken,
                                    depth_remaining,
                                    memo,
                                    resolving,
                                )
                            })?;
                        // If the bound named shape does not validate other, we
                        // need to report it.
                        causes.push(mismatch);
                    }
                }

                // A single union member can cover only part of other when
                // other hides a union inside a field or item position. No
                // member of One<{a: Int}, {a: String}> accepts
                // {a: One<Int, String>} whole, even though every value of the
                // latter belongs to one of the former. Distributing those
                // inner unions yields branches the members can cover one at a
                // time, so the union validates other if it validates every
                // branch.
                //
                // Rather than materializing the whole cartesian product of
                // union-typed positions, split one position at a time. Each
                // child re-enters this arm, which tries every member whole
                // before splitting again, so a child already covered by a
                // single member prunes every completion below it without
                // examining any of them. The full product is only ever walked
                // when no member covers anything until the leaves.
                //
                // A union on the other side is not one of those cases. Its
                // members are already the branches, and the ::One arm of the
                // match on other.case() below tries all of them, so splitting
                // here would ask the same question twice and pay for the
                // privilege.
                //
                // That arm carries splits_taken rather than starting over, as
                // every recursion here does, so it shares this comparison's
                // remaining allowance instead of getting a fresh one. Skipping
                // the split is still free of consequence -- the same branches
                // are tried either way -- but a received union reached with the
                // allowance already spent is answered without further
                // distribution, exactly as any other shape would be.
                //
                // The search is bounded by three structural caps, so that
                // where it stops is a fact about the shapes alone, readable
                // off them in advance, rather than about a meter that ran
                // out partway through: a union wider than MAX_SPLIT_MEMBERS
                // never starts a search, a position of arity above
                // MAX_SPLIT_ARITY is never distributed, and at most
                // MAX_SPLIT_DEPTH positions are distributed along any one
                // path through the comparison -- counted across descent into
                // fields and items, not restarted at each object level, so
                // that nesting adds to the count rather than multiplying the
                // cost. A member covering a child whole still ends that
                // branch immediately, so a shape whose product is
                // astronomical but whose branches are covered a level down
                // stays as cheap as ever. Falling outside any cap costs precision only:
                // validate reports the mismatch it would have reported
                // before splitting existed.
                if !matches!(other.case(), ShapeCase::One(_))
                    && splits_taken < MAX_SPLIT_DEPTH
                    // take() so refusing a pathologically wide union costs a
                    // bounded walk, not a count of every member.
                    && self_shapes.iter().take(MAX_SPLIT_MEMBERS + 1).count() <= MAX_SPLIT_MEMBERS
                {
                    if let Split::Children(children) = split_alternatives(other) {
                        if children.iter().all(|child| {
                            self.validate_within(
                                child,
                                splits_taken + 1,
                                depth_remaining,
                                memo,
                                resolving,
                            )
                            .is_none()
                        }) {
                            return None;
                        }
                    }
                }

                // Importantly, we do not return false here (in contrast with
                // the ::All case below), because the union might still validate
                // other, e.g. when other is Bool and the union contains both
                // true and false as members.
                //
                // We will need to handle ShapeCase::One logic in the ::Bool
                // case below, but otherwise the loop above saves most of the
                // cases below from explicitly worrying about self being a
                // ShapeCase::One.
                causes
            }

            ShapeCase::All(self_shapes) => {
                let mut causes = Vec::new();

                for self_shape in self_shapes.iter() {
                    if let Some(mismatch) = self_shape.validate_within(
                        other,
                        splits_taken,
                        depth_remaining,
                        memo,
                        resolving,
                    ) {
                        // If the intersection member does not validate other,
                        // we need to report it.
                        causes.push(mismatch);
                    }
                }

                return report(causes.is_empty(), causes);
            }

            // Sometimes we don't know anything (yet) about the structure of a
            // shape, but still want to refer to it by name and access the
            // shapes of subproperties (symbolically if not concretely). That's
            // what the ShapeCase::Name variant models.
            ShapeCase::Name(name, weak) => {
                return if let Some(named_shape) = weak.upgrade(name) {
                    // If this pair is already being compared on the path
                    // above, another lap of name resolution would repeat it
                    // deterministically, so assume the pair valid (the
                    // coinductive hypothesis) and let the enclosing
                    // comparison finish discharging it. See Resolving.
                    guarded(resolving, (self.clone(), other.clone()), || {
                        named_shape.validate_within(
                            other,
                            splits_taken,
                            depth_remaining,
                            memo,
                            resolving,
                        )
                    })
                } else {
                    // When self is an unbound named shape reference, it
                    // validates any other shape trivially, since it imposes no
                    // expectations on the other shape (and could eventually
                    // resolve to a shape that validates other).
                    None
                };
            }

            ShapeCase::Unknown => {
                // Unknown shapes validate any shape.
                return None;
            }

            _ => Vec::new(),
        };

        match other.case() {
            ShapeCase::Bool(Some(value)) => report(
                match self.case() {
                    ShapeCase::Bool(self_value) => {
                        Some(value) == self_value.as_ref() || self_value.is_none()
                    }
                    // We already handled the ::One and ::All cases above.
                    _ => false,
                },
                self_causes,
            ),

            ShapeCase::Bool(None) => report(
                (|| match self.case() {
                    ShapeCase::Bool(None) => true,

                    // This case goes beyond the basic ShapeCase::One handling
                    // provided at the top of the function, because we want to allow
                    // ::Bool(None) to be validated by a union of true and false.
                    ShapeCase::One(self_shapes) => {
                        let true_shape = Shape::bool_value(true, []);
                        let false_shape = Shape::bool_value(false, []);
                        let mut true_found = false;
                        let mut false_found = false;

                        for self_shape in self_shapes.iter() {
                            // Note the direction: the question is whether a
                            // member CONTAINS true, not whether it is
                            // contained in {true}. The two coincide on the
                            // shapes simplification can produce, since the
                            // only simplified member contained in {true} is
                            // the true literal itself, which is why the
                            // reversed test was harmless. It is still the
                            // wrong question, and it stops being harmless the
                            // moment an unsimplified union reaches here.
                            if self_shape
                                .validate_within(
                                    &true_shape,
                                    splits_taken,
                                    depth_remaining,
                                    memo,
                                    resolving,
                                )
                                .is_none()
                            {
                                true_found = true;
                            }
                            if self_shape
                                .validate_within(
                                    &false_shape,
                                    splits_taken,
                                    depth_remaining,
                                    memo,
                                    resolving,
                                )
                                .is_none()
                            {
                                false_found = true;
                            }
                            // Between them the members cover both booleans, so
                            // the union covers Bool.
                            if true_found && false_found {
                                // Returns from the (|| match ...)() closure.
                                return true;
                            }
                        }

                        false
                    }

                    _ => false,
                })(),
                self_causes,
            ),

            ShapeCase::String(value) => report(
                match self.case() {
                    ShapeCase::String(self_value) => value == self_value || self_value.is_none(),
                    // We already handled the ::One case above.
                    _ => false,
                },
                self_causes,
            ),

            ShapeCase::Int(value) => report(
                match self.case() {
                    ShapeCase::Int(self_value) => value == self_value || self_value.is_none(),
                    // All Int values are also (trivially convertible to) Float
                    // values, so Int is a subshape of Float.
                    ShapeCase::Float => true,
                    // We already handled the ::One case above.
                    _ => false,
                },
                self_causes,
            ),

            ShapeCase::Float => report(matches!(self.case(), ShapeCase::Float), Vec::new()),

            // Both ::Null and ::None accept/validate only themselves, but they
            // have an important difference in behavior when they appear in
            // ::All intersections. The null value "poisons" intersections,
            // reducing the whole intersection to null, which can be appropriate
            // behavior when reporting certain kinds of top-level errors. The
            // None value simply disappears from intersections, as it imposes no
            // additional constraints on the intersection shape.
            ShapeCase::Null => report(matches!(self.case(), ShapeCase::Null), Vec::new()),
            ShapeCase::None => report(matches!(self.case(), ShapeCase::None), Vec::new()),

            // ShapeCase::Unknown is validated by no other shapes except itself.
            // We already handled the case when self is ::Unknown above, so we
            // can report false here.
            ShapeCase::Unknown => report(false, Vec::new()),

            ShapeCase::Array {
                prefix: other_prefix,
                tail: other_tail,
            } => match self.case() {
                ShapeCase::Array {
                    prefix: self_prefix,
                    tail: self_tail,
                } => {
                    let mut causes = Vec::new();

                    for i in 0..self_prefix.len().max(other_prefix.len()) {
                        if let Some(self_item) = self_prefix.get(i) {
                            if let Some(other_item) = other_prefix.get(i) {
                                if let Some(mismatch) = self_item.validate_within(
                                    other_item,
                                    splits_taken,
                                    depth_remaining,
                                    memo,
                                    resolving,
                                ) {
                                    causes.push(mismatch);
                                }
                            } else {
                                // other is shorter, so position i in other is
                                // either governed by other_tail or absent
                                // entirely, since a tailed array may end at
                                // any length. self_item has to accept both
                                // possibilities: checking only other_tail
                                // accepts [Int, Int, ...] against
                                // [Int, ...Int], which the value [5] refutes.
                                // This mirrors the One<None, rest> probe the
                                // object walk already uses for a field other
                                // does not declare.
                                //
                                // The two short circuits are the ones the
                                // object walk takes for the same probe: a None
                                // tail means the position is simply absent,
                                // since One<None, None> is None, and an
                                // Unknown tail absorbs the None, since
                                // One<None, Unknown> is Unknown. Both spare a
                                // union build per position per call, and the
                                // closed tuple that takes the first one is the
                                // common case.
                                let possible = if other_tail.is_none() || other_tail.is_unknown() {
                                    other_tail.clone()
                                } else {
                                    Shape::one([Shape::none(), other_tail.clone()], [])
                                };
                                if let Some(mismatch) = self_item.validate_within(
                                    &possible,
                                    splits_taken,
                                    depth_remaining,
                                    memo,
                                    resolving,
                                ) {
                                    causes.push(mismatch);
                                }
                            }
                        } else if let Some(other_item) = other_prefix.get(i) {
                            // self has no prefix position i; self_tail
                            // governs.
                            if self_tail.is_none() {
                                // self is closed at length self_prefix.len()
                                // but other carries another element here.
                                causes.push(ShapeMismatch {
                                    expected: self.clone(),
                                    received: other.clone(),
                                    causes: Vec::new(),
                                });
                            } else if let Some(mismatch) = self_tail.validate_within(
                                other_item,
                                splits_taken,
                                depth_remaining,
                                memo,
                                resolving,
                            ) {
                                causes.push(mismatch);
                            }
                        }
                        // `i < max(self_prefix.len(), other_prefix.len())`
                        // guarantees at least one of the two `get(i)` calls
                        // above returns `Some`, so there is no else branch.
                    }

                    #[allow(clippy::match_same_arms)]
                    match (self_tail.case(), other_tail.case()) {
                        // other's tail is None, so it is effectively a fixed
                        // tuple; nothing more to check against self_tail.
                        (_, ShapeCase::None) => {}
                        // self is closed but other has a tail, so other may
                        // carry elements beyond self_prefix.len() that self
                        // cannot accept.
                        (ShapeCase::None, _) => {
                            causes.push(ShapeMismatch {
                                expected: self.clone(),
                                received: other.clone(),
                                causes: Vec::new(),
                            });
                        }
                        _ => {
                            if let Some(mismatch) = self_tail.validate_within(
                                other_tail,
                                splits_taken,
                                depth_remaining,
                                memo,
                                resolving,
                            ) {
                                causes.push(mismatch);
                            }
                        }
                    }

                    report(causes.is_empty(), causes)
                }

                // We already handled the ::One and ::All cases above.
                _ => report(false, Vec::new()),
            },

            ShapeCase::Object { fields, rest } => match self.case() {
                ShapeCase::Object {
                    fields: self_fields,
                    rest: self_rest,
                } => {
                    let mut causes = Vec::new();

                    // For each field self declares, determine the shape it
                    // can take under `other` and check self's expectation
                    // accepts it.
                    for (field_name, field_shape) in self_fields {
                        if let Some(other_field_shape) = fields.get(field_name) {
                            if let Some(mismatch) = field_shape.validate_within(
                                other_field_shape,
                                splits_taken,
                                depth_remaining,
                                memo,
                                resolving,
                            ) {
                                causes.push(mismatch);
                            }
                        } else {
                            // other does not declare field_name. Under other,
                            // v.field_name is either absent (None) or, if
                            // other has a non-None rest shape, a dynamic
                            // property of that rest shape. Self must accept
                            // any such possibility.
                            if rest.is_none() {
                                // Field is guaranteed absent under other;
                                // self must tolerate None (be optional).
                                if let Some(mismatch) = field_shape.validate_within(
                                    &Shape::none(),
                                    splits_taken,
                                    depth_remaining,
                                    memo,
                                    resolving,
                                ) {
                                    causes.push(mismatch);
                                }
                            } else if rest.is_unknown() {
                                // `One<None, Unknown>` simplifies to `Unknown`,
                                // which is the most permissive shape — it
                                // validates `field_shape` iff `field_shape`
                                // validates `Unknown`. This is the new
                                // open-by-default case after 0.8.0; short-
                                // circuiting it skips an allocation-heavy
                                // `Shape::one([Shape::none(), ...])` build per
                                // missing field per `accepts` call.
                                if let Some(mismatch) = field_shape.validate_within(
                                    rest,
                                    splits_taken,
                                    depth_remaining,
                                    memo,
                                    resolving,
                                ) {
                                    causes.push(mismatch);
                                }
                            } else {
                                let possible = Shape::one([Shape::none(), rest.clone()], []);
                                if let Some(mismatch) = field_shape.validate_within(
                                    &possible,
                                    splits_taken,
                                    depth_remaining,
                                    memo,
                                    resolving,
                                ) {
                                    causes.push(mismatch);
                                }
                            }
                        }
                    }

                    // For each field other declares that self does not, the
                    // field must be absorbed by self's rest shape. A closed
                    // self (rest: None) cannot absorb any extra declared
                    // field.
                    for (field_name, other_field_shape) in fields {
                        if self_fields.contains_key(field_name) {
                            continue;
                        }
                        // A field whose shape admits no value is provably
                        // always absent, so it constrains nothing and there is
                        // nothing for self's rest to absorb. Skipping it is
                        // exact, not generous, and it has to happen on both
                        // sides of the closed/open split below: skipping it
                        // only for a closed self is what made accepts
                        // non-transitive, since a closed middle shape could
                        // accept such a field while an open outer shape that
                        // accepts the middle could not.
                        if other_field_shape.is_none() || other_field_shape.is_never() {
                            continue;
                        }
                        if self_rest.is_none() {
                            causes.push(ShapeMismatch {
                                expected: self.clone(),
                                received: other.clone(),
                                causes: Vec::new(),
                            });
                        } else if let Some(mismatch) = self_rest.validate_within(
                            other_field_shape,
                            splits_taken,
                            depth_remaining,
                            memo,
                            resolving,
                        ) {
                            causes.push(mismatch);
                        }
                    }

                    // Finally, reconcile the two rest shapes themselves.
                    match (rest.case(), self_rest.case()) {
                        // Either other declares no dynamic properties, so
                        // there is nothing more for self.rest to absorb,
                        // regardless of whether self is open or closed.
                        (ShapeCase::None, _) => {}
                        // other permits dynamic properties but self is
                        // closed — other's values can carry extras that
                        // self does not permit.
                        (_, ShapeCase::None) => {
                            causes.push(ShapeMismatch {
                                expected: self.clone(),
                                received: other.clone(),
                                causes: Vec::new(),
                            });
                        }
                        // Both sides permit dynamic properties; self's rest
                        // must be at least as permissive as other's.
                        _ => {
                            if let Some(mismatch) = self_rest.validate_within(
                                rest,
                                splits_taken,
                                depth_remaining,
                                memo,
                                resolving,
                            ) {
                                causes.push(mismatch);
                            }
                        }
                    }

                    report(causes.is_empty(), causes)
                }

                // We already handled the ::One and ::All cases above.
                _ => report(false, Vec::new()),
            },

            // If *other* is a ShapeCase::One union, then every possibility must
            // be validated by self. For example, if other is One<true, false>,
            // and self is Bool, then since true and false are each individually
            // validated by Bool, Bool validates the union One<true, false>.
            ShapeCase::One(other_shapes) => {
                // If other is an empty union (Never), then only None or other
                // Never shapes can validate it. We already handled the case
                // when self is Never in the first match, so here we only need
                // to check for None.
                if other_shapes.is_empty() {
                    return if self.is_none() {
                        None
                    } else {
                        Some(ShapeMismatch {
                            expected: self.clone(),
                            received: other.clone(),
                            causes: Vec::new(),
                        })
                    };
                }

                let mut causes = Vec::new();

                for other_shape in other_shapes.iter() {
                    if let Some(mismatch) = self.validate_within(
                        other_shape,
                        splits_taken,
                        depth_remaining,
                        memo,
                        resolving,
                    ) {
                        // If the union member does not validate self, we need
                        // to report it.
                        causes.push(mismatch);
                    }
                }

                report(causes.is_empty(), causes)
            }

            // If other is a ShapeCase::All intersection, then it is validated
            // by self if any of the member shapes are validated by self.
            ShapeCase::All(other_shapes) => {
                let mut causes = Vec::new();

                for other_shape in other_shapes.iter() {
                    // If self validates this member (validate returns None), `?`
                    // returns None early — the intersection is validated.
                    let mismatch = self.validate_within(
                        other_shape,
                        splits_taken,
                        depth_remaining,
                        memo,
                        resolving,
                    )?;
                    causes.push(mismatch);
                }

                report(causes.is_empty(), causes)
            }

            ShapeCase::Name(name, weak) => {
                if let Some(other_shape) = weak.upgrade(name) {
                    // If other is a bound named shape reference, pretend we
                    // validated against the named shape, under the same
                    // coinductive guard as the self-side ::Name arm above.
                    return guarded(resolving, (self.clone(), other.clone()), || {
                        self.validate_within(
                            &other_shape,
                            splits_taken,
                            depth_remaining,
                            memo,
                            resolving,
                        )
                    });
                }
                // When other is an unbound named shape reference, it is
                // accepted/validated by no shape except itself.
                report(other.case == self.case, Vec::new())
            }
        }
    }
}

/// The three caps that bound the union splitting search, together. Splitting
/// distributes a cartesian product over union-typed positions, so a search
/// that reaches the leaves can blow up combinatorially and has to be stopped
/// somewhere. These caps are all structural: whether a pair of shapes falls
/// inside them is a fact about those shapes alone, readable off them in
/// advance, the same at every depth of every larger comparison — never a
/// meter that ran out partway, whose position nobody could have predicted.
///
/// The rule in one breath: a union of at most [`MAX_SPLIT_MEMBERS`] members
/// distributes received positions of arity at most [`MAX_SPLIT_ARITY`], at
/// most [`MAX_SPLIT_DEPTH`] positions deep along any one path through the
/// comparison.
///
/// The caps are deliberately not a census of the received shape. A member
/// that covers a branch whole prunes every completion below it, so only
/// positions the search actually resolves count against the depth: a record
/// with sixty-four union-typed fields absorbed by the expected members' rest
/// resolves one position and stays as cheap as it looks, however astronomical
/// its nominal product. Counting the product instead was this bound's first
/// design, and it refused exactly those cheap shapes; metering comparisons
/// performed was its second, and its cliff depended on how much of the meter
/// sibling comparisons had already spent. Falling outside any cap costs
/// precision only: `validate` reports the mismatch it would have reported
/// before splitting existed.
///
/// Worst case, all three caps at their limits with nothing pruning:
/// `MAX_SPLIT_MEMBERS * (MAX_SPLIT_ARITY ^ MAX_SPLIT_DEPTH and change)` is
/// about 300k member-vs-branch comparisons, tens of milliseconds, and
/// reaching it takes a shape as contrived as the tests' every-assignment
/// unions. The
/// common doomed walk — two-member positions that never prune, which is what
/// a union of wide records looks like — dies at the depth cap after a few
/// thousand comparisons.
///
/// Note that caps of any size are a cliff for transitivity, not just for
/// precision: inside them acceptance composes along chains, outside them the
/// fallback answer does not, so `accepts` is not transitive for chains that
/// straddle a cap — but which side of the cliff a chain sits on is now
/// decidable by inspection. The Lean model on the `lean-model` branch omits
/// this splitting clause entirely (its divergence 5), in part because such
/// cases do not compose under it.
///
/// A position is distributed only if its union has at most this many members.
/// Real unions reachable from GraphQL stay small — a nullable field is two, a
/// union or interface type is one per member or implementor — so eight covers
/// them with room while keeping the worst-case fanout per level a single
/// digit.
const MAX_SPLIT_ARITY: usize = 8;

/// At most this many positions are distributed along any one path through a
/// comparison before the search falls back. Pruned positions do not count, so
/// this is a limit on how many unions must simultaneously be distributed
/// before any member covers, not on how many a shape may contain. The count
/// survives descent into fields and items (see [`Shape::validate_within`]),
/// so it bounds the comparison as a whole; were it per object level instead,
/// nesting would multiply one level's worst case once per level.
///
/// A dozen is far above what the search costs, and that is deliberate: this
/// cap buys precision, and it is [`MAX_SPLIT_MEMBERS`] that bounds cost. The
/// reason is that the `all` over a split's children short circuits on the
/// first child that fails, so a search whose answer is a rejection walks one
/// path and abandons it rather than walking the product. The product is only
/// walked when branches succeed, and making every branch need its own member
/// requires a member per branch, which the member cap already limits to 64.
/// Measured against twelve positions of arity eight and 64 members that cover
/// nothing, raising this from 4 through 32 moved the worst case from 3.9ms to
/// 6.9ms and nothing else; the value is chosen for what it admits, not for
/// what it forbids.
///
/// Twelve nested distributions is deeper than a selection set reaches, and
/// past it the benign families stop gaining: a chain needing one distribution
/// at each of twelve levels is accepted here and costs 402µs.
///
/// The short circuit is necessary for twelve to be affordable but not
/// sufficient: the memo in [`SplitMemo`] is the other half. The member loop
/// asks the same union-against-subtree question once per branch of every
/// level above it, and it is the memo answering that question once that keeps
/// a doomed search nested several levels deep in the milliseconds. Without it
/// the same shapes run for minutes, and the tests that pin this cap
/// (`test_union_splitting_cliffs_at_each_cap` and
/// `test_split_depth_counts_the_whole_comparison_not_each_object_level`) do
/// not finish. The two were raised and introduced together, and should be
/// changed together.
const MAX_SPLIT_DEPTH: usize = 12;

/// An expected union wider than this never starts a split search, since every
/// resolved position is compared against every member, and no cap on the
/// received shape bounds that factor.
const MAX_SPLIT_MEMBERS: usize = 64;

/// What [`split_alternatives`] found while walking a shape for a union-typed
/// position it can distribute. Only `Children` costs anything; the caller
/// treats the other two alike, and they are kept apart so the walk can say
/// which of the two reasons it came back empty for.
enum Split {
    /// No union-typed position to distribute anywhere in the shape.
    Nothing,
    /// Every union-typed position the walk found was wider than
    /// [`MAX_SPLIT_ARITY`], so none of them was distributed.
    ///
    /// An over-wide position is **skipped, not declined on the spot**: the
    /// walk keeps looking for a narrower one. Declining on the spot was the
    /// original rule, on the grounds that sliding ahead would let the cap's
    /// size decide which position gets distributed, and with it the answer.
    /// That is right about the hazard and wrong about which choice avoids it.
    /// The walk visits an object's fields in `IndexMap` order, so declining at
    /// the first over-wide position makes the answer depend on **field
    /// insertion order** -- and insertion order is not part of a shape's
    /// identity, since `PartialEq` and `Hash` for `ShapeCase` are both
    /// order-insensitive. Two shapes comparing equal could then be accepted
    /// and rejected respectively, which
    /// `test_union_splitting_ignores_field_order` pins against. A named
    /// constant a reader can look up is a far better thing for an answer to
    /// depend on than an order nobody can see.
    ///
    /// Skipping keeps the part of the cap that matters. What the cap is for is
    /// that [`split_alternatives`] clones the containing container once per
    /// member of the position it distributes, and a position that is skipped
    /// is never materialized, so the allocation blowup the cap exists to
    /// prevent is prevented either way. Measured on a received record holding
    /// a 200,000-member union beside a hundred sibling fields, best of three:
    ///
    /// ```text
    /// declining at the position    12.0ms
    /// skipping past it             14.9ms
    /// no arity cap at all         872ms
    /// ```
    ///
    /// The 3ms is the walk carrying on through the remaining positions looking
    /// for a narrower one and finding none, which is a scan rather than a
    /// materialization. That is the honest price of the change, and it buys an
    /// answer that does not depend on field order.
    TooWide,
    /// One shape per member of the first distributable position's union.
    Children(Vec<Shape>),
}

/// Replaces one union-typed position of `shape` with each member of that
/// union, returning the resulting shapes as [`Split::Children`], or
/// [`Split::Nothing`] when `shape` has no union-typed position to split.
///
/// The returned shapes are strictly smaller than `shape`, since each drops a
/// union node in favor of one of its members. That is what makes the search in
/// `validate` terminate.
///
/// Each returned shape is a clone of the containing object or array, so the
/// materialization itself costs the union's arity times the container's
/// width. The arity cap is therefore checked before anything is built: a
/// union wider than [`MAX_SPLIT_ARITY`] comes back as [`Split::TooWide`], at
/// zero allocations, and the walk moves on to look for a narrower position
/// rather than giving up where it stood. Skipping rather than declining is
/// what keeps the answer independent of the order an object's fields were
/// inserted in; see [`Split::TooWide`] for why that matters more than the
/// property the earlier rule was protecting.
///
/// For example `{a: One<Int, String>, b: Bool}` yields `{a: Int, b: Bool}` and
/// `{a: String, b: Bool}`. Only the first distributable position found is
/// expanded; the caller recurses to reach the rest. A more sophisticated
/// version could order positions by which one best discriminates among the
/// union members, the way a word search tries the rarest letter first, but the
/// prune that matters is the caller's, which tests whole members before
/// splitting again.
///
/// Three positions deliberately never split:
///
/// * `rest` and `tail` shapes, which constrain unboundedly many values that
///   each choose independently. Distributing them would lose meaning, since
///   `{...One<Int, String>}` accepts `{"p": 1, "q": "s"}` while neither
///   `{...Int}` nor `{...String}` does.
/// * Members of a [`ShapeCase::All`] intersection, which the intersection
///   itself is responsible for resolving.
/// * [`ShapeCase::Name`] references, so splitting cannot follow a cycle.
fn split_alternatives(shape: &Shape) -> Split {
    match shape.case() {
        ShapeCase::One(shapes) => {
            // A union of one member, or the empty union, offers no choice to
            // distribute. Reporting Nothing for the singleton case also keeps
            // the caller from recursing on an unchanged shape forever. The
            // count is bounded and taken before any member is cloned, so a
            // union too wide to split costs nothing to refuse.
            let count = shapes.iter().take(MAX_SPLIT_ARITY + 1).count();
            if count <= 1 {
                Split::Nothing
            } else if count > MAX_SPLIT_ARITY {
                Split::TooWide
            } else {
                Split::Children(shapes.iter().cloned().collect())
            }
        }

        ShapeCase::Object { fields, rest } => {
            let mut skipped_too_wide = false;
            for (key, field_shape) in fields {
                let options = match split_alternatives(field_shape) {
                    Split::Nothing => continue,
                    // Skip and keep looking rather than declining here, so
                    // that field order cannot decide the answer. See
                    // [`Split::TooWide`].
                    Split::TooWide => {
                        skipped_too_wide = true;
                        continue;
                    }
                    Split::Children(options) => options,
                };
                return Split::Children(
                    options
                        .into_iter()
                        .map(|option| {
                            let mut split_fields = fields.clone();
                            split_fields.insert(key.clone(), option);
                            Shape::object(split_fields, rest.clone(), shape.locations().cloned())
                        })
                        .collect(),
                );
            }
            if skipped_too_wide {
                Split::TooWide
            } else {
                Split::Nothing
            }
        }

        ShapeCase::Array { prefix, tail } => {
            let mut skipped_too_wide = false;
            for (index, item_shape) in prefix.iter().enumerate() {
                let options = match split_alternatives(item_shape) {
                    Split::Nothing => continue,
                    // Skip and keep looking, as in the object walk above.
                    Split::TooWide => {
                        skipped_too_wide = true;
                        continue;
                    }
                    Split::Children(options) => options,
                };
                return Split::Children(
                    options
                        .into_iter()
                        .map(|option| {
                            let mut split_prefix = prefix.clone();
                            split_prefix[index] = option;
                            Shape::array(split_prefix, tail.clone(), shape.locations().cloned())
                        })
                        .collect(),
                );
            }
            if skipped_too_wide {
                Split::TooWide
            } else {
                Split::Nothing
            }
        }

        _ => Split::Nothing,
    }
}