shape/

lib.rs

mod accepts;
mod cached;
mod case_enum;
mod child_shape;
mod display;
mod from_json;
mod hashing;
mod helpers;
mod merge;
mod meta;
pub mod name;

pub mod location;
#[cfg(test)]
mod tests;
mod visitor;

use std::hash::Hash;
use std::hash::Hasher;
use std::iter::empty;

pub use accepts::ShapeMismatch;
pub use case_enum::Error;
pub use case_enum::ShapeCase;
pub use display::PrintLimits;
use helpers::inner_hasher;
pub use helpers::OffsetRange;
use helpers::Ref;
use indexmap::IndexMap;
use indexmap::IndexSet;
use meta::ShapeMeta;
pub use visitor::ShapeVisitor;

use crate::case_enum::all::all;
use crate::case_enum::one::one;
use crate::location::Location;
use crate::merge::MergeSet;
use crate::name::Name;
use crate::name::WeakScope;

/// The `shape::Shape` struct provides a recursive, immutable, reference-counted
/// tree/DAG format for representing and enforcing common structures and usage
/// patterns of JSON-like data.
///
/// The `Shape` system is not bound to any particular programming language, so
/// it does not inherit a data model that it must represent and defend, yet it
/// must adopt/assume _some_ concrete data model, since a type system without a
/// data model to enforce is as useful as a straitjacket on a coat rack. JSON
/// was chosen for its relative simplicity, its ubiquity as a data interchange
/// format used across programming languages, and because JSON is often used in
/// scenarios without a static type system to help catch errors before runtime.
///
/// The `Shape` system has no source syntax for denoting shapes directly, but
/// you can use the `Shape::*` helper functions to create shapes
/// programmatically, in Rust. `Shape::pretty_print()` provides a human-readable
/// representation of a `Shape` for debugging and testing purposes.
///
/// All in all, this _Static `Shape` System_ (SSS) supports the following
/// type-theoretic features:
///
/// - [x] Primitive shapes: `Bool`, `String`, `Int`, `Float`, `Null`
/// - [x] Singleton primitive shapes: `true`, `false`, `"hello"`, `42`, `null`
/// - [x] `Array` shapes, supporting both static tuples and dynamic lists
/// - [x] `Object` shapes, supporting both static fields and dynamic string keys
/// - [x] `One<S1, S2, ...>` union shapes, representing a set of shape
///   alternatives
/// - [x] `All<S1, S2, ...>` intersection shapes, representing a set
///   simultaneous requirements
/// - [x] `shape.field(name)` and `shape.item(index)` methods for accessing the
///   shape of a subproperty of a shape
/// - [x] `Name` shape references, with support for symbolic subproperty shape
///   access
/// - [x] `Error` shapes, representing a failure of shape processing, with
///   support for chains of errors and partial shape data
/// - [x] `None` shapes, representing the absence of a value (helpful for
///   representing optionality of shapes)
/// - [x] `subshape.satisfies(supershape)` and `supershape.accepts(subshape)`
///   methods for testing shape relationships
/// - [x] `shape.accepts_json(json)` method for testing whether concrete JSON
///   data satisfies some expected shape
/// - [x] `shape.pretty_print()` method for debugging and testing

#[derive(Clone, Eq)]
// [`Shape`] enforces the simplification of [`ShapeCase`] variants, because
// there is no way to create a [`Shape`] without simplifying the input
// [`ShapeCase`]. This is a very useful invariant because it allows each
// [`ShapeCase`] to assume its immediate [`Shape`] children have already been
// simplified.
//
// In addition simplification, [`Shape`] supports testing shape-shape acceptance
// (or the equivalent inverse, satisfaction) with `super.accepts(sub)` and/or
// `sub.satisfies(super)`. See also `shape.accepts_json(json)` for testing
// whether concrete JSON data satisfies some expected `shape`.
//
// In the future, we may internalize/canonize shapes to reduce memory usage,
// especially for well-known shapes like `Bool` and `Int` and `String`. This
// would require either thread safety (is `type Ref<T> = std::sync::Arc<T>`
// enough?) or maintaining per-thread canonical shape tables.
pub struct Shape {
    // This field is private, but if you want to match against an immutable
    // reference to the `ShapeCase` variant, use `match shape.case() { ... }`.
    case: Ref<CaseWithHash>,

    /// The combination of locations which, combined, produce this shape.
    ///
    /// Many cases will only have a single location, but when shapes are
    /// simplified, their locations are all retained in the result.
    ///
    /// Currently [`ShapeMeta::Loc(Location)`] is the only variant here, but we
    /// can add other kinds of metadata in the future.
    meta: Ref<ShapeMeta>,
}

impl PartialEq for Shape {
    fn eq(&self, other: &Self) -> bool {
        self.case == other.case
    }
}

impl Hash for Shape {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Since the PartialEq implementation ignores self.locations, so must
        // the Hash implementation.
        //
        // Reading the cached hash rather than walking the case is also what
        // makes hashing incremental: a parent's hash combines its children's
        // stored values, so no subtree is ever walked twice. See
        // [`CaseWithHash`].
        self.case.hash(state);
    }
}

/// A [`ShapeCase`] stored alongside its hash.
///
/// The hash is computed once, when the case is first wrapped, and read
/// thereafter. That is worth doing because [`Hash`] for [`Shape`] is the hook
/// the recursive [`Hash`] for [`ShapeCase`] reaches its children through: with
/// the hash stored, hashing a case reads its children's values instead of
/// walking their subtrees, so it costs its direct children rather than its
/// whole tree. Cases are built bottom up, so a tree's hashes cost one pass in
/// total and every hash afterwards is a field read.
///
/// It lives here rather than on [`Shape`] so that it is stored once per case
/// allocation and shared by every shape that clones the `Ref`, instead of once
/// per shape. Keeping it out of `Shape` also keeps that struct two pointers
/// wide, which matters because shapes are stored inline in array prefixes,
/// object field maps and `MergeSet` members. And it does not belong in
/// [`ShapeMeta`], which is by definition the part of a shape that identity
/// ignores, and which is merged in place by
/// [`crate::merge::MetaMergeable::merge_meta_from`] -- an operation a hash has
/// no meaningful answer for.
///
/// Both [`PartialEq`] and [`Hash`] here agree with their counterparts on
/// [`Shape`]: equality compares hashes and then cases, and hashing writes the
/// stored hash rather than re-deriving it.
///
/// # Invariant
///
/// **A case is never mutated in a way that changes its logical hash or its
/// equality.** [`Ref::make_mut`] is reached on a case in three places, and in
/// every one of them it is copy-on-write in service of installing distinct
/// [`ShapeMeta`] values on children: the two name-propagation walks in
/// `name.rs` rewrite children so they carry names, and
/// `MetaMergeable::merge_meta_from` in `merge.rs` merges child metadata behind
/// a `debug_assert_eq!` that the two cases already match. The `ShapeCase::Name`
/// arm of the first rebinds only a `WeakScope`, which neither equality nor
/// hashing covers.
///
/// Nothing in the crate may mutate a case so as to change what `PartialEq`
/// sees. A change that did would not merely cost a cache miss: since equality
/// consults the stored hash first, two equal cases would begin comparing
/// unequal. `test_case_hash_survives_in_place_case_mutation` pins this from
/// outside, and it is the reason that test asserts equality rather than hash
/// agreement alone.
/// `Clone` is required by [`Ref::make_mut`], which the copy-on-write case
/// mutations in `name.rs` and `merge.rs` go through. A clone copies the stored
/// hash rather than re-deriving it, which is correct for exactly the reason
/// those mutations are safe at all: by the invariant above, none of them
/// changes the part of a case that equality looks at.
#[derive(Clone)]
pub(crate) struct CaseWithHash {
    pub(crate) case: ShapeCase,
    hash: u64,
}

impl CaseWithHash {
    /// Wrap a case, hashing it once.
    ///
    /// Uses [`inner_hasher`] so the value is keyed by the same per-process seed
    /// the order-insensitive combiners in [`crate::hashing`] use, which is
    /// initialized once per run. Equal cases therefore hash equally for the
    /// whole run, which is what `Hash`/`Eq` consistency requires; the value is
    /// not stable across processes, exactly as any default `HashMap` key hash
    /// is not.
    fn new(case: ShapeCase) -> Self {
        let mut hasher = inner_hasher();
        case.hash(&mut hasher);
        let hash = hasher.finish();
        Self { case, hash }
    }
}

impl PartialEq for CaseWithHash {
    /// Hashes first, cases second.
    ///
    /// Equal cases always have equal hashes, so a hash mismatch settles
    /// inequality in two loads and a compare, without walking either shape.
    /// Only a match goes on to confirm structurally, and `PartialEq` for
    /// `ShapeCase` reaches its children through `PartialEq` for [`Shape`],
    /// which reaches this again, so shared subtrees settle by pointer.
    ///
    /// This makes the stored hash load bearing for equality and not only for
    /// hashing: a stale hash would now make two equal cases compare unequal,
    /// rather than merely missing a cache. That is the invariant
    /// `test_case_hash_survives_in_place_case_mutation` pins, and it is why
    /// that test asserts equality rather than only hash agreement.
    fn eq(&self, other: &Self) -> bool {
        self.hash == other.hash && self.case == other.case
    }
}

impl Eq for CaseWithHash {}

impl Hash for CaseWithHash {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.hash.hash(state);
    }
}

impl std::fmt::Debug for CaseWithHash {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.case.fmt(f)
    }
}

impl Shape {
    /// Create a `Shape` from a [`ShapeCase`] variant.
    ///
    /// This method is crate-private to help enforce some invariants.
    pub(crate) fn new(case: ShapeCase, locations: impl IntoIterator<Item = Location>) -> Shape {
        let meta = ShapeMeta::new(&case, locations, []);
        Shape {
            case: Ref::new(CaseWithHash::new(case)),
            meta: Ref::new(meta),
        }
    }

    /// Create a `Shape` from a [`ShapeCase`] variant with errors attached.
    pub(crate) fn new_with_errors(
        case: ShapeCase,
        locations: impl IntoIterator<Item = Location>,
        errors: impl IntoIterator<Item = Error>,
    ) -> Shape {
        let meta = ShapeMeta::new_with_errors(&case, locations, [], errors);
        Shape {
            case: Ref::new(CaseWithHash::new(case)),
            meta: Ref::new(meta),
        }
    }

    /// When `locations` is empty, return a clone of the cached canonical
    /// singleton; otherwise build a fresh [`Shape`] from the [`ShapeCase`]
    /// produced by `case`. `case` is a closure so its construction cost
    /// (which may itself involve `Arc` clones, e.g. for `any_object` /
    /// `any_array`) is paid only on the non-cached path. We use
    /// [`Peekable::peek`] to test emptiness without disassembling the
    /// iterator — the same iterator is then forwarded to [`Shape::new`].
    fn cached_or_else(
        cached: &std::sync::LazyLock<Shape>,
        locations: impl IntoIterator<Item = Location>,
        case: impl FnOnce() -> ShapeCase,
    ) -> Shape {
        let mut iter = locations.into_iter().peekable();
        if iter.peek().is_none() {
            // Explicit double-deref so we clone the inner `Shape`, not the
            // outer `&LazyLock<Shape>` (the blanket `Clone for &T` would
            // otherwise win method resolution and return the reference).
            return (**cached).clone();
        }
        Shape::new(case(), iter)
    }

    /// When boolean helper methods like `.is_none()` and `.is_null()` are not
    /// enough, you can match against the underlying [`ShapeCase`] by obtaining an
    /// immutable `&ShapeCase` reference using the `shape.case()` method.
    #[must_use]
    pub fn case(&self) -> &ShapeCase {
        &self.case.case
    }

    /// Returns an iterator over all [`Location`]s associated with this shape.
    pub fn locations(&self) -> impl Iterator<Item = &Location> {
        let self_locs = self.meta.locations();

        let unique_locs: IndexSet<&Location> = match self.case() {
            ShapeCase::One(shapes) => self_locs
                .chain(shapes.iter().flat_map(|s| s.meta.locations()))
                .collect(),
            ShapeCase::All(shapes) => self_locs
                .chain(shapes.iter().flat_map(|s| s.meta.locations()))
                .collect(),
            _ => self_locs.collect(),
        };

        unique_locs.into_iter()
    }

    /// Returns an iterator over all [`Name`]s associated with this shape.
    pub fn names(&self) -> impl Iterator<Item = &Name> {
        self.meta.names()
    }

    pub fn nested_base_names(&self) -> impl Iterator<Item = &str> {
        self.meta.nested_base_names()
    }

    /// Returns a [`Shape`] that accepts any boolean value, `true` or `false`.
    ///
    /// When called with empty `locations`, returns a clone of a cached
    /// canonical singleton — two atomic refcount bumps instead of two heap
    /// allocations.
    #[must_use]
    pub fn bool(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::cached_or_else(&cached::BOOL, locations, || ShapeCase::Bool(None))
    }

    /// Returns a [`Shape`] that accepts only the specified boolean value.
    #[must_use]
    pub fn bool_value(value: bool, locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Bool(Some(value)), locations)
    }

    /// Returns a [`Shape`] that accepts any string value.
    ///
    /// When called with empty `locations`, returns a clone of a cached
    /// canonical singleton.
    #[must_use]
    pub fn string(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::cached_or_else(&cached::STRING, locations, || ShapeCase::String(None))
    }

    /// Returns a [`Shape`] that accepts only the specified string value.
    #[must_use]
    pub fn string_value(value: &str, locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::String(Some(value.to_string())), locations)
    }

    /// Returns a [`Shape`] that accepts any integer value.
    ///
    /// When called with empty `locations`, returns a clone of a cached
    /// canonical singleton.
    #[must_use]
    pub fn int(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::cached_or_else(&cached::INT, locations, || ShapeCase::Int(None))
    }

    /// Returns a [`Shape`] that accepts only the specified integer value.
    #[must_use]
    pub fn int_value(value: i64, locations: impl IntoIterator<Item = Location>) -> Self {
        Self::new(ShapeCase::Int(Some(value)), locations)
    }

    /// Returns a [`Shape`] that accepts any floating point value.
    ///
    /// When called with empty `locations`, returns a clone of a cached
    /// canonical singleton.
    #[must_use]
    pub fn float(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::cached_or_else(&cached::FLOAT, locations, || ShapeCase::Float)
    }

    /// Returns a [`Shape`] that accepts only the JSON `null` value.
    ///
    /// When called with empty `locations`, returns a clone of a cached
    /// canonical singleton.
    #[must_use]
    pub fn null(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::cached_or_else(&cached::NULL, locations, || ShapeCase::Null)
    }

    #[must_use]
    pub fn is_null(&self) -> bool {
        self.case().is_null()
    }

    /// Returns a symbolic reference to a named shape, potentially not yet
    /// defined.
    ///
    /// In order to add items to the subpath of this named shape, call the
    /// `.field(name)` and/or `.item(index)` methods.
    ///
    /// Note that variable shapes are represented by [`ShapeCase::Name`] where the
    /// name string includes the initial `$` character.
    #[must_use]
    pub fn name(name: &str, locations: impl IntoIterator<Item = Location>) -> Self {
        let locations = locations.into_iter().collect::<Vec<_>>();
        Self::new(
            ShapeCase::Name(
                name::Name::base(name.to_string(), locations.clone()),
                WeakScope::none(),
            ),
            locations.clone(),
        )
    }

    /// Useful for obtaining the kind of [`IndexMap`] this library uses for the
    /// [`ShapeCase::Object`] variant.
    #[must_use]
    pub fn empty_map() -> IndexMap<String, Self> {
        IndexMap::new()
    }

    /// Returns an open object [`Shape`] with no declared fields, which accepts
    /// any object value because the unknown `rest` shape permits any dynamic
    /// property. Useful as an "is this any object?" probe via
    /// [`Shape::accepts`], or directly via [`Shape::is_object`].
    /// For the closed `{}` shape (no fields, no rest — only the
    /// literal empty object is accepted), use [`Shape::empty_object`].
    ///
    /// When called with empty `locations`, returns a clone of a cached
    /// canonical singleton.
    #[must_use]
    pub fn any_object(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::cached_or_else(&cached::ANY_OBJECT, locations, || ShapeCase::Object {
            fields: Shape::empty_map(),
            rest: Shape::unknown([]),
        })
    }

    /// Returns a closed empty object [`Shape`]: no declared fields and no
    /// dynamic properties, so only the literal empty object `{}` satisfies it.
    /// This is the counterpart to [`Shape::any_object`] (the open form that
    /// accepts any object). There is no `open_empty_object` / `closed_*` pair
    /// here because the two forms are distinct enough to name directly:
    /// `any_object` (open) and `empty_object` (closed `{}`).
    #[must_use]
    pub fn empty_object(locations: impl IntoIterator<Item = Location>) -> Self {
        Shape::new(
            ShapeCase::Object {
                fields: Shape::empty_map(),
                rest: Shape::none(),
            },
            locations,
        )
    }

    /// To get a compatible empty mutable [`IndexMap`] without directly
    /// depending on the [`indexmap`] crate yourself, use [`Shape::empty_map()`].
    #[must_use]
    pub fn object(
        fields: IndexMap<String, Shape>,
        rest: Shape,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::new(ShapeCase::Object { fields, rest }, locations)
    }

    /// An open record is a [`ShapeCase::Object`] with statically known
    /// fields and an open (`Unknown`) `rest`, so it accepts objects that
    /// carry the declared fields plus any number of additional dynamic
    /// properties. For the closed counterpart that rejects keys not listed
    /// in `fields`, use [`Shape::closed_record`].
    #[must_use]
    pub fn open_record(
        fields: IndexMap<String, Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::object(fields, Shape::unknown([]), locations)
    }

    /// Previous name for a record constructor. The bare name `record` is
    /// ambiguous about whether extra dynamic properties are permitted, so it
    /// is deprecated in favor of the explicit pair. Its body produces the
    /// **closed** form (no `rest`, rejecting unlisted keys), matching the
    /// 0.7.0 behavior, so existing callers keep their semantics until they
    /// migrate. Pick explicitly: [`Shape::closed_record`] for that same
    /// closed record, or [`Shape::open_record`] to permit additional dynamic
    /// properties. The "any object?" probe is better served by
    /// [`Shape::any_object`] or [`Shape::is_object`].
    #[deprecated(
        since = "0.8.0",
        note = "use Shape::closed_record for a closed record, Shape::open_record if extra properties should be permitted, or Shape::any_object / Shape::is_object for the bare \"any object?\" probe"
    )]
    #[must_use]
    pub fn record(
        fields: IndexMap<String, Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::closed_record(fields, locations)
    }

    /// Returns a closed record [`Shape`]: an object with the given
    /// static fields and no dynamic properties. Values with additional keys
    /// not listed in `fields` are rejected. For the open variant that
    /// permits additional properties, use [`Shape::open_record`].
    #[must_use]
    pub fn closed_record(
        fields: IndexMap<String, Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::object(fields, Shape::none(), locations)
    }

    /// Returns a [`Shape`] that accepts any dictionary-like object with dynamic
    /// string properties having a given value shape.
    #[must_use]
    pub fn dict(value_shape: Shape, locations: impl IntoIterator<Item = Location>) -> Self {
        Shape::object(Shape::empty_map(), value_shape, locations)
    }

    /// Arrays, tuples, and lists are all manifestations of the same underlying
    /// [`ShapeCase::Array`] representation.
    #[must_use]
    pub fn array(
        prefix: impl IntoIterator<Item = Shape>,
        tail: Shape,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        let prefix = prefix.into_iter().collect();
        Self::new(ShapeCase::Array { prefix, tail }, locations)
    }

    /// Previous name for a tuple constructor. The bare name `tuple` is
    /// ambiguous about whether extra trailing elements are permitted, so it
    /// is deprecated in favor of the explicit pair. Its body produces the
    /// **closed** form (no tail, an exact n-tuple), matching the 0.7.0
    /// behavior, so existing callers keep their semantics until they migrate.
    /// Pick explicitly: [`Shape::closed_tuple`] for that same exact n-tuple,
    /// or [`Shape::open_tuple`] to assert a prefix while allowing additional
    /// trailing elements. The "any array?" probe is better served by
    /// [`Shape::any_array`] or [`Shape::is_array`].
    #[deprecated(
        since = "0.8.0",
        note = "use Shape::closed_tuple for an exact n-tuple, Shape::open_tuple if extras should be permitted, or Shape::any_array / Shape::is_array for the bare \"any array?\" probe"
    )]
    pub fn tuple(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::closed_tuple(shapes, locations)
    }

    /// An open tuple is a [`ShapeCase::Array`] with statically known leading
    /// element shapes and an open (`Unknown`) tail, so it accepts arrays
    /// starting with the declared prefix and continuing with any number of
    /// trailing elements of any shape. For the closed counterpart that
    /// accepts only arrays of the exact declared length, use
    /// [`Shape::closed_tuple`].
    #[must_use]
    pub fn open_tuple(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::array(shapes, Shape::unknown([]), locations)
    }

    /// A closed tuple is a [`ShapeCase::Array`] with statically known (though
    /// possibly empty) element shapes and no dynamic tail shape, so it accepts
    /// only arrays of exactly the same length and element shapes. For the
    /// open-tailed counterpart that permits extra trailing elements beyond
    /// the declared prefix, use [`Shape::open_tuple`].
    #[must_use]
    pub fn closed_tuple(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        Shape::array(shapes, Shape::none(), locations)
    }

    /// A `List<S>` is a [`ShapeCase::Array`] with an empty static `prefix` and a
    /// dynamic element shape `S`.
    #[must_use]
    pub fn list(of: Shape, locations: impl IntoIterator<Item = Location>) -> Self {
        Shape::array(empty(), of, locations)
    }

    /// Returns an open [`ShapeCase::Array`] with no required leading elements
    /// and an unknown tail, so it accepts any array value. Useful as an "is
    /// this any array?" probe via [`Shape::accepts`], or directly via
    /// [`Shape::is_array`].
    ///
    /// When called with empty `locations`, returns a clone of a cached
    /// canonical singleton.
    #[must_use]
    pub fn any_array(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::cached_or_else(&cached::ANY_ARRAY, locations, || ShapeCase::Array {
            prefix: Vec::new(),
            tail: Shape::unknown([]),
        })
    }

    /// Returns a [`ShapeCase::One`] union of the given shapes, simplified.
    ///
    /// Note that `locations` in this case should _not_ refer to each individual inner shape, but
    /// to the thing that caused all of these shapes to be combined, like maybe a `->match`. If
    /// there is no obvious cause to point users to, then the location should be empty.
    pub fn one(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        one(shapes.into_iter(), locations.into_iter().collect())
    }

    /// Returns a [`ShapeCase::All`] intersection of the given shapes, simplified.
    ///
    /// Note that `locations` in this case should _not_ refer to each individual inner shape, but
    /// to the thing that caused all of these shapes to be combined, like maybe a `IntfA & IntfB`.
    /// If there is no obvious cause to point users to, then the location should be empty.
    ///
    /// If what you want is to combine several partial descriptions of one value
    /// (a spread, a selection set accumulated field by field) rather than to
    /// constrain a value by several requirements at once, use [`Shape::merge`],
    /// which is that operation under its own name. See its documentation for
    /// the three ways this simplification currently departs from set
    /// intersection, and why the distinction is worth recording at the call
    /// site.
    pub fn all(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        all(shapes.into_iter(), locations.into_iter().collect())
    }

    /// Returns the shape of a value assembled by combining several partial
    /// descriptions of that same value: the composition, or "spread", operator.
    /// Use it for `{ a: 1, ...$(expr) }`-style spreads, for accumulating the
    /// output shape of a selection set one selection at a time, and generally
    /// wherever the inputs describe *contributions* to one value rather than
    /// *constraints* on it.
    ///
    /// `merge` is the same operation as [`Shape::all`] today, and delegates to
    /// the same code path, so moving a call site from `all` to `merge` cannot
    /// change its result. The two names exist because that one operation is
    /// doing two jobs, and the jobs are coming apart.
    ///
    /// [`Shape::all`] is documented as intersection, and on many inputs it is
    /// one, but the simplification departs from set intersection in three
    /// ways. Each is right for composition and wrong for intersection:
    ///
    /// * **`Null` absorbs.** `All<Bool(true), Null>` simplifies to `Null`,
    ///   which is what makes GraphQL-style null bubbling work. As an
    ///   intersection it should be empty, since no value is both `true` and
    ///   `null`.
    /// * **`None` drops.** `All<Int, None>` simplifies to `Int`, so an
    ///   optional contribution that turns out to be absent contributes
    ///   nothing. As an intersection it should be empty, since `None` denotes
    ///   absence and `Int` denotes values.
    /// * **Objects merge, and lose closedness.** `All<{a: Int}, {b: String}>`
    ///   declares both keys, which neither input accepts, and
    ///   `All<{a: Int}, {a: Int, ...}>` is the *open* record, which is wider
    ///   than either input. Combining two partial records is supposed to
    ///   widen. An intersection never can.
    ///
    /// Each of those breaks the law that makes an operation a meet, namely that
    /// every member accepts the intersection (`a.accepts(All<a, b>)`). So if
    /// `All<..>` is ever corrected towards true intersection, every call site
    /// that meant composition would quietly change meaning. Calling `merge`
    /// records which one you meant, so that when the two operations are given
    /// separate implementations, composition call sites keep composition
    /// semantics and intersection call sites move.
    ///
    /// # What this does and does not guarantee yet
    ///
    /// Being the same function is what makes adopting `merge` free, and it is
    /// also the limit of what `merge` currently promises. Until the two are
    /// given separate implementations, **`merge` tracks `Shape::all`**, so a
    /// change to `Shape::all` changes `merge` with it. That includes changes
    /// already planned: array members are combined positionwise today, and are
    /// scheduled to stop being combined and to remain side by side as an exact
    /// intersection instead. Composing arrays through `merge` is therefore
    /// version-unstable across that release, while composing objects, records
    /// and primitives is not.
    ///
    /// Concretely: adopt `merge` now for the intent it records, rely on it for
    /// object and record composition, and do not depend on its array behavior
    /// until the two operations have diverged.
    ///
    /// As with [`Shape::all`], `locations` should refer to the construct that
    /// caused the shapes to be combined, such as the spread or the selection
    /// set, and not to the individual inputs. If there is nothing useful to
    /// point a reader at, pass an empty iterator.
    pub fn merge(
        shapes: impl IntoIterator<Item = Shape>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        all(shapes.into_iter(), locations.into_iter().collect())
    }

    /// Returns a shape that accepts any JSON value (including [`ShapeCase::None`]
    /// and [`ShapeCase::Unknown`]), and is not accepted by any shape other than itself.
    ///
    /// When called with empty `locations`, returns a clone of a cached
    /// canonical singleton. Constructors that internally build an open
    /// `rest` / `tail` (`Shape::open_record`, `Shape::open_tuple`,
    /// `Shape::any_object`, `Shape::any_array`) inherit this caching.
    #[must_use]
    pub fn unknown(locations: impl IntoIterator<Item = Location>) -> Self {
        Self::cached_or_else(&cached::UNKNOWN, locations, || ShapeCase::Unknown)
    }

    #[must_use]
    pub fn is_unknown(&self) -> bool {
        matches!(self.case(), ShapeCase::Unknown)
    }

    /// Returns true iff this shape would be accepted by [`Shape::any_array`],
    /// i.e. every value the shape can take is an array. Recurses through
    /// `ShapeCase::One` (every branch must be an array), `ShapeCase::All`
    /// (at least one intersection member must be an array), and bound
    /// `ShapeCase::Name` shapes (the resolved shape must be an array).
    #[must_use]
    pub fn is_array(&self) -> bool {
        match self.case() {
            ShapeCase::Array { .. } => true,
            ShapeCase::One(members) if !members.is_empty() => members.iter().all(Shape::is_array),
            ShapeCase::All(members) => members.iter().any(Shape::is_array),
            ShapeCase::Name(name, weak) => weak.upgrade(name).is_some_and(|s| s.is_array()),
            _ => false,
        }
    }

    /// Returns true iff this shape would be accepted by [`Shape::any_object`],
    /// i.e. every value the shape can take is an object. Recurses through
    /// `ShapeCase::One`, `ShapeCase::All`, and bound `ShapeCase::Name`
    /// shapes in the same way as [`Shape::is_array`].
    #[must_use]
    pub fn is_object(&self) -> bool {
        match self.case() {
            ShapeCase::Object { .. } => true,
            ShapeCase::One(members) if !members.is_empty() => members.iter().all(Shape::is_object),
            ShapeCase::All(members) => members.iter().any(Shape::is_object),
            ShapeCase::Name(name, weak) => weak.upgrade(name).is_some_and(|s| s.is_object()),
            _ => false,
        }
    }

    /// Returns a shape representing the absence of a JSON value, which is
    /// satisfied/accepted only by itself.
    ///
    /// Because this represents the absence of a value, it shouldn't have a location. Basically,
    /// nothing can produce none alone, and if it were a union, that union would have its own
    /// location. Returns a clone of the cached canonical singleton.
    #[must_use]
    pub fn none() -> Self {
        cached::NONE.clone()
    }

    #[must_use]
    pub fn is_none(&self) -> bool {
        self.case().is_none()
    }

    /// Report a failure of shape processing. Creates an Unknown shape with
    /// the error attached as metadata.
    #[must_use]
    pub fn error(
        message: impl Into<String>,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        let locations: Vec<_> = locations.into_iter().collect();
        Self::new_with_errors(
            ShapeCase::Unknown,
            locations,
            [Error {
                message: message.into(),
            }],
        )
    }

    /// Returns true if this shape has any errors attached directly (not nested).
    #[deprecated(
        since = "0.7.0",
        note = "use `has_errors()` for recursive check or `has_own_errors()` for own-only"
    )]
    #[must_use]
    pub fn is_error(&self) -> bool {
        self.meta.has_errors()
    }

    /// Returns true if this shape has errors attached to it (not nested children).
    #[must_use]
    pub fn has_own_errors(&self) -> bool {
        self.meta.has_errors()
    }

    /// Returns true if this shape or any nested child has errors.
    #[must_use]
    pub fn has_errors(&self) -> bool {
        if self.has_own_errors() {
            return true;
        }
        match self.case() {
            ShapeCase::Array { prefix, tail } => {
                prefix.iter().any(Shape::has_errors) || tail.has_errors()
            }
            ShapeCase::Object { fields, rest } => {
                fields.values().any(Shape::has_errors) || rest.has_errors()
            }
            ShapeCase::One(one) => one.iter().any(Shape::has_errors),
            ShapeCase::All(all) => all.iter().any(Shape::has_errors),
            // Name references are not followed (could cause cycles)
            // Leaf cases have no children to traverse
            ShapeCase::Name(_, _)
            | ShapeCase::Bool(_)
            | ShapeCase::String(_)
            | ShapeCase::Int(_)
            | ShapeCase::Float
            | ShapeCase::Null
            | ShapeCase::Unknown
            | ShapeCase::None => false,
        }
    }

    /// Iterate over errors attached to this shape (not nested children).
    pub fn own_errors(&self) -> impl Iterator<Item = &Error> {
        self.meta.errors()
    }

    /// Recursively iterate over all errors from this shape and its nested
    /// children. This traverses Array elements, Object fields, One/All
    /// variants, but does NOT follow Name references (to avoid cycles and
    /// because named shapes are conceptually separate).
    ///
    /// Internally, errors are gathered into a single buffer in pre-order and
    /// returned via [`Vec::into_iter`]; this is a single allocation per call
    /// regardless of tree depth, where a naive recursive
    /// `Vec`-of-`Vec`-collecting implementation would allocate one per
    /// visited shape.
    pub fn errors(&self) -> impl Iterator<Item = &Error> + '_ {
        let mut buf: Vec<&Error> = Vec::new();
        self.collect_errors_into(&mut buf);
        buf.into_iter()
    }

    fn collect_errors_into<'a>(&'a self, out: &mut Vec<&'a Error>) {
        out.extend(self.own_errors());
        match self.case() {
            ShapeCase::Array { prefix, tail } => {
                for child in prefix {
                    child.collect_errors_into(out);
                }
                tail.collect_errors_into(out);
            }
            ShapeCase::Object { fields, rest } => {
                for child in fields.values() {
                    child.collect_errors_into(out);
                }
                rest.collect_errors_into(out);
            }
            ShapeCase::One(one) => {
                for child in one.iter() {
                    child.collect_errors_into(out);
                }
            }
            ShapeCase::All(all) => {
                for child in all.iter() {
                    child.collect_errors_into(out);
                }
            }
            // Name references are not followed (could cause cycles).
            // Leaf cases have no children to traverse.
            ShapeCase::Name(_, _)
            | ShapeCase::Bool(_)
            | ShapeCase::String(_)
            | ShapeCase::Int(_)
            | ShapeCase::Float
            | ShapeCase::Null
            | ShapeCase::Unknown
            | ShapeCase::None => {}
        }
    }

    /// Report a failure of shape processing associated with a
    /// partial/best-guess shape that may still be useful. The error is
    /// attached to the partial shape as metadata.
    #[must_use]
    pub fn error_with_partial(
        message: impl Into<String>,
        partial: Shape,
        locations: impl IntoIterator<Item = Location>,
    ) -> Self {
        partial
            .with_error(Error {
                message: message.into(),
            })
            .with_locations(locations.into_iter().collect::<Vec<_>>().iter())
    }

    /// Clone the shape with an additional error attached.
    #[must_use]
    pub fn with_error(mut self, error: Error) -> Self {
        Ref::make_mut(&mut self.meta).add_error(error);
        self
    }

    /// Clone the shape, adding the provided `locations` to the existing locations.
    #[must_use]
    pub fn with_locations<'a>(mut self, locations: impl IntoIterator<Item = &'a Location>) -> Self {
        for loc in locations {
            if !self.meta.has_location(loc) {
                Ref::make_mut(&mut self.meta).add_location(loc);
            }
        }
        self
    }
}

#[cfg(test)]
mod test_errors {
    use super::*;

    #[test]
    fn error_shape_has_error() {
        let error_shape = Shape::error("Expected a string", []);
        let errors: Vec<_> = error_shape.errors().collect();
        assert_eq!(errors.len(), 1);
        assert_eq!(errors[0].message, "Expected a string");
        assert!(error_shape.has_errors());
    }

    #[test]
    fn error_with_partial_preserves_shape() {
        let error_shape = Shape::error_with_partial("Parse failed", Shape::bool([]), []);
        // The shape should be Bool with an error attached
        assert!(matches!(error_shape.case(), ShapeCase::Bool(None)));
        assert!(error_shape.has_errors());
        let errors: Vec<_> = error_shape.errors().collect();
        assert_eq!(errors.len(), 1);
        assert_eq!(errors[0].message, "Parse failed");
    }

    #[test]
    fn multiple_errors_can_attach() {
        let shape = Shape::bool([])
            .with_error(Error {
                message: "First error".to_string(),
            })
            .with_error(Error {
                message: "Second error".to_string(),
            });
        let errors: Vec<_> = shape.errors().collect();
        assert_eq!(errors.len(), 2);
        assert_eq!(errors[0].message, "First error");
        assert_eq!(errors[1].message, "Second error");
    }

    #[test]
    fn plain_shapes_have_no_errors() {
        let int_shape = Shape::int([]);
        assert!(!int_shape.has_errors());
        assert_eq!(int_shape.errors().count(), 0);
    }

    #[test]
    fn errors_collects_from_nested_shapes() {
        // Create an array with an error on a nested element
        let error_element = Shape::string([]).with_error(Error {
            message: "nested error".to_string(),
        });
        let array = Shape::array([], error_element.clone(), []);

        // own_errors() should be empty on the array itself
        assert!(!array.has_own_errors());
        assert!(array.own_errors().next().is_none());

        // errors() should find the nested error (recursive)
        let all: Vec<_> = array.errors().collect();
        assert_eq!(all.len(), 1);
        assert_eq!(all[0].message, "nested error");

        // has_errors() should return true (recursive check)
        assert!(array.has_errors());
    }

    #[test]
    fn errors_collects_from_object_fields() {
        let error_field = Shape::int([]).with_error(Error {
            message: "field error".to_string(),
        });
        let mut fields = Shape::empty_map();
        fields.insert("count".to_string(), error_field);
        let obj = Shape::object(fields, Shape::none(), []);

        // No own errors on obj, but nested field has one
        assert!(!obj.has_own_errors());
        assert!(obj.has_errors());

        let all: Vec<_> = obj.errors().collect();
        assert_eq!(all.len(), 1);
        assert_eq!(all[0].message, "field error");
    }

    #[test]
    fn errors_collects_from_multiple_levels() {
        // Object with error -> array with error -> element with error
        let deep_error = Shape::bool([]).with_error(Error {
            message: "deep".to_string(),
        });
        let array_with_error = Shape::array([], deep_error, []).with_error(Error {
            message: "middle".to_string(),
        });
        let mut fields = Shape::empty_map();
        fields.insert("items".to_string(), array_with_error);
        let obj = Shape::object(fields, Shape::none(), []).with_error(Error {
            message: "top".to_string(),
        });

        let all: Vec<_> = obj.errors().collect();
        assert_eq!(all.len(), 3);
        // Errors collected in traversal order: top, middle, deep
        assert_eq!(all[0].message, "top");
        assert_eq!(all[1].message, "middle");
        assert_eq!(all[2].message, "deep");
    }

    #[test]
    fn has_errors_short_circuits() {
        // Should return true as soon as it finds an error
        let clean_shape = Shape::int([]);
        assert!(!clean_shape.has_errors());

        let error_shape = Shape::error("oops", []);
        assert!(error_shape.has_errors());
    }

    #[test]
    fn errors_and_names_single_each() {
        // One error, one name
        let shape = Shape::string([])
            .with_error(Error {
                message: "invalid value".to_string(),
            })
            .with_base_name("MyString", []);

        assert!(shape.has_errors());
        assert_eq!(shape.errors().count(), 1);
        assert!(shape.has_base_name("MyString"));

        assert_eq!(shape.pretty_print(), r#"String (err "invalid value")"#);
        assert_eq!(shape.pretty_print_without_errors(), "String");
        assert_eq!(
            shape.pretty_print_with_names(),
            r#"String (err "invalid value") (aka MyString)"#
        );
    }

    #[test]
    fn multiple_errors_no_names() {
        let shape = Shape::int([])
            .with_error(Error {
                message: "first error".to_string(),
            })
            .with_error(Error {
                message: "second error".to_string(),
            });

        assert!(shape.has_errors());
        assert_eq!(shape.errors().count(), 2);
        assert_eq!(shape.names().count(), 0);

        assert_eq!(
            shape.pretty_print(),
            r#"Int (err "first error", "second error")"#
        );
        assert_eq!(shape.pretty_print_without_errors(), "Int");
        assert_eq!(
            shape.pretty_print_with_names(),
            r#"Int (err "first error", "second error")"#
        );
    }

    #[test]
    fn no_errors_multiple_names() {
        // Create a shape, apply one name, then apply another
        // Note: with_base_name propagates names to children, but for a leaf
        // shape like Int, multiple calls add multiple names
        let shape = Shape::int([])
            .with_base_name("Count", [])
            .with_base_name("Total", []);

        assert!(!shape.has_errors());
        assert!(shape.has_base_name("Count"));
        assert!(shape.has_base_name("Total"));

        assert_eq!(shape.pretty_print(), "Int");
        assert_eq!(shape.pretty_print_without_errors(), "Int");
        // Names are collected via MergeSet, order may vary
        let with_names = shape.pretty_print_with_names();
        assert!(with_names.contains("(aka"));
        assert!(with_names.contains("Count"));
        assert!(with_names.contains("Total"));
    }

    #[test]
    fn multiple_errors_multiple_names() {
        let shape = Shape::bool([])
            .with_error(Error {
                message: "err1".to_string(),
            })
            .with_error(Error {
                message: "err2".to_string(),
            })
            .with_base_name("Flag", [])
            .with_base_name("Toggle", []);

        assert!(shape.has_errors());
        assert_eq!(shape.errors().count(), 2);
        assert!(shape.has_base_name("Flag"));
        assert!(shape.has_base_name("Toggle"));

        // pretty_print shows errors only
        assert_eq!(shape.pretty_print(), r#"Bool (err "err1", "err2")"#);

        // pretty_print_without_errors shows neither
        assert_eq!(shape.pretty_print_without_errors(), "Bool");

        // pretty_print_with_names shows errors first, then names
        let with_names = shape.pretty_print_with_names();
        assert!(with_names.starts_with(r#"Bool (err "err1", "err2") (aka "#));
        assert!(with_names.contains("Flag"));
        assert!(with_names.contains("Toggle"));
    }

    #[test]
    fn nested_errors_and_names() {
        // Create an object with a field that has both error and name
        let field_with_error = Shape::string([])
            .with_error(Error {
                message: "field error".to_string(),
            })
            .with_base_name("FieldName", []);

        let mut fields = Shape::empty_map();
        fields.insert("field".to_string(), field_with_error);
        let obj = Shape::object(fields, Shape::none(), [])
            .with_error(Error {
                message: "object error".to_string(),
            })
            .with_base_name("MyObject", []);

        // Object has its own error, field has its own error
        assert!(obj.has_own_errors());
        assert!(obj.has_errors());
        // errors() is recursive - should find both
        assert_eq!(obj.errors().count(), 2);

        // Check object-level pretty print
        let pp = obj.pretty_print();
        assert!(pp.contains(r#"(err "object error")"#));
        assert!(pp.contains(r#"(err "field error")"#));

        // With names shows errors first, then names at each level
        let with_names = obj.pretty_print_with_names();
        assert!(with_names.contains("MyObject"));
        assert!(with_names.contains("FieldName"));
    }
}