shape/

name.rs

use std::fmt::Debug;
use std::fmt::Display;
use std::hash::Hash;
use std::hash::Hasher;
use std::marker::PhantomData;
use std::sync::RwLock;

use indexmap::IndexMap;
use indexmap::IndexSet;

use crate::helpers::quote_non_identifier;
use crate::helpers::RefWeak;
use crate::location::Location;
use crate::merge::MetaMergeable;
use crate::MergeSet;
use crate::Ref;
use crate::Shape;
use crate::ShapeCase;

/// A [`Namespace`] is a collection of named [`Shape`]s, which can be used to
/// give meaning to (resolve) [`ShapeCase::Name`] references.
///
/// The [`Namespace<NotFinal>`] and [`Namespace<Final>`] types represent the two
/// stages of a namespace's lifecycle: before and after finalization. The
/// finalization process resolves all [`ShapeCase::Name`] references within the
/// shapes of the namespace, ensuring every name has a stable weak reference
/// back to the named shape's [`ShapeCase`].
///
/// We implement `Clone` for `Namespace` manually below, always returning a
/// `Namespace<NotFinal>`.
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Namespace<T = NotFinal> {
    // Once the Namespace has been finalized, the pointer addresses of the
    // Ref<Shape> references must not change, because nested child shapes may
    // refer back to them via WeakRef<Shape> pointers. This means the map must
    // be assigned at most once per key.
    map: Ref<IndexMap<String, Ref<Shape>>>,
    _final_state: PhantomData<T>,
}

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct NotFinal;

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Final;

impl Namespace {
    /// Create a new empty unfinalized [`Namespace`].
    #[must_use]
    pub fn new() -> Namespace<NotFinal> {
        Namespace::<NotFinal> {
            map: Ref::new(IndexMap::new()),
            _final_state: PhantomData::<NotFinal>,
        }
    }
}

impl Default for Namespace<NotFinal> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> Namespace<T> {
    /// Any [`Namespace`] (`Namespace<NotFinal>` or `Namespace<Final>`) can tell
    /// you whether a given name is bound, using the `has` method.
    #[must_use]
    pub fn has(&self, name: &str) -> bool {
        self.map.contains_key(name)
    }

    /// Returns an iterator over the names in the namespace.
    pub fn names(&self) -> impl Iterator<Item = &str> + '_ {
        self.map.keys().map(String::as_str)
    }

    /// Non-destructively merges two [`Namespace`]s (`self` and `other`)
    /// together into a new [`Namespace`]. When there are collisions, [`Shape`]s
    /// of the same name will be combined with `Shape::all([self_shape,
    /// other_shape], [])`. The `T` and `U` types of `self: &Namespace<T>` and
    /// `other: &Namespace<U>` are unrestricted and do not have to agree, though
    /// the final merged result is always `Namespace<NotFinal>`.
    #[must_use]
    pub fn merge<U>(&self, other: &Namespace<U>) -> Namespace<NotFinal> {
        let mut merged = Namespace::<NotFinal> {
            map: self.map.clone(),
            _final_state: PhantomData::<NotFinal>,
        };
        merged.extend(other);
        merged
    }
}

impl Namespace<NotFinal> {
    /// Mutably extends the current [`Namespace`] with the contents of another
    /// [`Namespace`]. If a name already exists in `self`, the corresponding
    /// `self_shape` will be merged with `other_shape` (from `other`) using
    /// `Shape::all([self_shape, other_shape], [])`.
    pub fn extend<T>(&mut self, other: &Namespace<T>) {
        for (name, shape) in other.map.as_ref() {
            self.insert(name.clone(), shape.as_ref().clone());
        }
    }

    /// Mutably binds `name` to `shape` in the current [`Namespace`], cloning
    /// `shape` and recursively propagating names derived from `name` to all
    /// nested child shapes. Since this cloning and name propagation generally
    /// creates a new [`Shape`], the `insert` method returns a clone of that
    /// final `Shape` (inspectable with [`Shape::pretty_print_with_names`]).
    pub fn insert(&mut self, name: impl Into<String>, shape: Shape) -> Shape {
        let name = name.into();
        if let Some(existing_shape) = self.map.get(&name) {
            let merged = Ref::new(
                Shape::all([existing_shape.as_ref().clone(), shape], [])
                    // Note that [`Shape::with_base_name`] and
                    // [`Shape::with_name`] are intentionally crate-private
                    // (that is, `pub(crate)`), so external code can only assign
                    // names to shapes by inserting them into [`Namespace`]s.
                    .with_base_name(&name, []),
            );
            let merged_shape = merged.as_ref().clone();
            Ref::make_mut(&mut self.map).insert(name.clone(), merged);
            merged_shape
        } else {
            let named_shape_ref = Ref::new(shape.with_base_name(&name, []));
            let named_shape_clone = named_shape_ref.as_ref().clone();
            Ref::make_mut(&mut self.map).insert(name, named_shape_ref);
            named_shape_clone
        }
    }

    /// Returns a finalized version of `self`, ensuring exclusive ownership of
    /// all `Ref<Shape>` references, then binding all [`ShapeCase::Name`]
    /// references nested within shapes owned by the new namespace.
    #[must_use]
    pub fn finalize(&self) -> Namespace<Final> {
        // Create a shared WeakScope that will be assigned to all ShapeCase::Name
        // elements during ensure_deep_exclusive_name_ownership. Initially empty,
        // it will be populated with the weak map reference after final_map is built.
        let weak_scope = WeakScope::none();

        let final_map = Ref::new(
            self.map
                .iter()
                .map(|(name, shape)| {
                    // Ensure the shape has the name, and all its descendants have
                    // recursively derived child names.
                    let named_shape = shape.as_ref().clone().with_base_name(name, []);
                    (
                        name.clone(),
                        // Ensuring deep exclusive ShapeCase::Name ownership means
                        // recursively calling Ref::make_mut(&mut self.case) to
                        // enforce Ref::strong_count(&self.case) == 1 throughout any
                        // subtrees that transitively contain ShapeCase::Name
                        // elements. While doing so, we also assign the shared
                        // weak_scope to each ShapeCase::Name element.
                        Ref::new(ensure_deep_exclusive_name_ownership(
                            named_shape,
                            &weak_scope,
                        )),
                    )
                })
                .collect::<IndexMap<_, _>>(),
        );

        // Now that final_map exists, we can create a weak reference to it and
        // populate the shared WeakScope. All ShapeCase::Name elements that were
        // assigned this weak_scope will now be able to resolve their names.
        weak_scope.set_weak(Ref::downgrade(&final_map));

        if cfg!(debug_assertions) {
            for (name, shape_ref) in final_map.as_ref() {
                debug_assert!(shape_ref.has_base_name(name));
            }
        }

        Namespace::<Final> {
            map: final_map,
            _final_state: PhantomData::<Final>,
        }
    }
}

fn ensure_deep_exclusive_name_ownership(mut shape: Shape, weak_scope: &WeakScope) -> Shape {
    if shape.meta.nested_base_names().next().is_none() {
        // If the shape has no names, we can skip the deep exclusive ownership
        // check and just return the shape as-is.
        return shape;
    }

    match &mut Ref::make_mut(&mut shape.case).case {
        ShapeCase::Object { fields, rest } => {
            for field_shape in fields.values_mut() {
                *field_shape =
                    ensure_deep_exclusive_name_ownership(field_shape.clone(), weak_scope);
            }
            *rest = ensure_deep_exclusive_name_ownership(rest.clone(), weak_scope);
        }

        ShapeCase::Array { prefix, tail } => {
            for element_shape in prefix {
                *element_shape =
                    ensure_deep_exclusive_name_ownership(element_shape.clone(), weak_scope);
            }
            *tail = ensure_deep_exclusive_name_ownership(tail.clone(), weak_scope);
        }

        ShapeCase::One(shapes) => {
            shapes.shapes = MergeSet::new(
                shapes
                    .iter()
                    .map(|shape| ensure_deep_exclusive_name_ownership(shape.clone(), weak_scope)),
            );
        }

        ShapeCase::All(shapes) => {
            shapes.shapes = MergeSet::new(
                shapes
                    .iter()
                    .map(|shape| ensure_deep_exclusive_name_ownership(shape.clone(), weak_scope)),
            );
        }

        ShapeCase::Name(_name, weak) => {
            // Assign the shared WeakScope to this ShapeCase::Name. All Name
            // elements in the same namespace will share this WeakScope, so
            // when we call set_weak() once after building the final map, all
            // of them will see the update through the shared RwLock.
            *weak = weak_scope.clone();
        }

        ShapeCase::Null
        | ShapeCase::None
        | ShapeCase::Unknown
        | ShapeCase::Bool(_)
        | ShapeCase::Int(_)
        | ShapeCase::Float
        | ShapeCase::String(_) => {}
    }

    shape
}

/// A [`WeakScope`] is a interior-mutable `RwLock` holding a map of weak
/// shape references that can be used to resolve the [`Name`]s of
/// [`ShapeCase::Name`] shapes. Though this struct is `pub`, its
/// [`Ref<RwLock<WeakShapeMap>>`] parameter is not, so you cannot
/// directly create your own [`WeakScope`] outside this crate.
#[derive(Clone, Debug)]
pub struct WeakScope(Ref<RwLock<Option<WeakShapeMap>>>);

/// A reference-counted [`Ref`] to a map from shape names to [`RefWeak<Shape>`]
/// references, referring weakly into some [`Namespace<Final>`]. The `Weak` in
/// `WeakShapeMap` refers to the weakness of the `IndexMap` values, not the
/// [`WeakShapeMap`] itself, which is a strong [`Ref`] (for easy cloning).
type WeakShapeMap = RefWeak<IndexMap<String, Ref<Shape>>>;

impl WeakScope {
    #[must_use]
    pub fn none() -> Self {
        Self(Ref::new(RwLock::new(None)))
    }

    /// Upgrades a given [`Name`] in the [`WeakScope`] to a [`Shape`] if
    /// possible.
    #[must_use]
    pub fn upgrade(&self, name: &Name) -> Option<Shape> {
        match name.case() {
            NameCase::Base(base_name) => {
                if let Ok(guard) = self.0.read() {
                    guard
                        .as_ref()
                        .and_then(RefWeak::upgrade)
                        .and_then(|map| map.get(base_name).map(|shape| shape.as_ref().clone()))
                } else {
                    None
                }
            }
            NameCase::Field(parent, field_name) => self
                .upgrade(parent)
                .map(|shape| shape.field(field_name, name.locations().cloned())),
            NameCase::Item(parent, index) => self
                .upgrade(parent)
                .map(|shape| shape.item(*index, name.locations().cloned())),
            NameCase::AnyField(parent) => self
                .upgrade(parent)
                .map(|shape| shape.any_field(name.locations().cloned())),
            NameCase::AnyItem(parent) => self
                .upgrade(parent)
                .map(|shape| shape.any_item(name.locations().cloned())),
            NameCase::Question(parent) => self
                .upgrade(parent)
                .map(|shape| shape.question(name.locations().cloned())),
            NameCase::NotNone(parent) => self
                .upgrade(parent)
                .map(|shape| shape.not_none(name.locations().cloned())),
        }
    }

    fn set_weak(&self, weak: WeakShapeMap) {
        *self.0.write().unwrap() = Some(weak);
    }
}

impl Namespace<Final> {
    #[must_use]
    pub fn finalize(&self) -> Namespace<Final> {
        // Cloning the IndexMap<String, Ref<Shape>> of self.map when self is a
        // Namespace<Final> is safe because it increments the reference count of
        // each Ref<Shape> but does not change any Ref pointer addresses, so we
        // do not have to re-propagate weak references.
        self.clone()
    }

    /// Returns an iterator over the name-shape pairs in the finalized namespace.
    pub fn iter(&self) -> impl Iterator<Item = (String, Shape)> + '_ {
        self.map
            .iter()
            .map(|(name, shape)| (name.clone(), shape.as_ref().clone()))
    }

    /// You must have a finalized [`Namespace<Final>`] to use the `get` method
    /// to look up shapes in the [`Namespace`].
    ///
    /// While [`Namespace<NotFinal>`] supports `has` and `insert` and other
    /// [`Namespace`]-building methods, the `Namespace` has to be promoted to
    /// [`Namespace<Final>`] before you can actually look up any names.
    #[must_use]
    pub fn get(&self, name: &str) -> Option<Shape> {
        self.map.get(name).map(|shape| shape.as_ref().clone())
    }

    /// In case self.get returns a Rust None, this method returns a
    /// [`Shape::none()`] that's named with the given `name`.
    #[must_use]
    pub fn get_or_none(&self, name: &str) -> Shape {
        if let Some(shape) = self.get(name) {
            shape
        } else {
            Shape::none().with_base_name(name, [])
        }
    }

    /// In case self.get returns a Rust None, this method returns an `Unknown`
    /// shape that's named with the given `name`.
    #[must_use]
    pub fn get_or_unknown(&self, name: &str) -> Shape {
        if let Some(shape) = self.get(name) {
            shape
        } else {
            Shape::unknown([]).with_base_name(name, [])
        }
    }
}

impl Shape {
    /// Returns `true` if this [`Shape`] is known by the given base
    /// name, among potentially multiple names it may have.
    pub fn has_base_name(&self, base_name: impl Into<String>) -> bool {
        let name = Name::base(base_name.into(), []);
        self.meta.has_name(&name)
    }

    /// Assigns a base `name` to this [`Shape`], propagating derived
    /// child names to all nested child shapes. This method is called
    /// automatically when adding shapes to a [`Namespace`] (which
    /// always requires providing a base name). The `locs` for this
    /// operation should indicate where the `name` came from in source
    /// code, if that information is available.
    #[must_use]
    pub fn with_base_name(
        self,
        name: impl Into<String>,
        locs: impl IntoIterator<Item = Location>,
    ) -> Self {
        self.with_name(&Name::base(name, locs))
    }

    #[must_use]
    pub(crate) fn with_name(mut self, name: &Name) -> Self {
        if self.meta.has_name(name) {
            // If the name is already present, we can assume its child names
            // have also already been propagated.
            return self;
        }

        Ref::make_mut(&mut self.meta).add_name(name.clone());

        // Recursively propagate the name to child shapes
        match &mut Ref::make_mut(&mut self.case).case {
            ShapeCase::Object { fields, rest } => {
                for (field_name, field_shape) in fields.iter_mut() {
                    *field_shape = field_shape.clone().with_name(&name.field(field_name, []));
                }
                // Even if rest is None, it may still be useful for it to carry
                // the ObjectType.** name from name.any_field([]).
                *rest = rest.clone().with_name(&name.any_field([]));
                self
            }

            ShapeCase::Array { prefix, tail } => {
                for (index, prefix_shape) in prefix.iter_mut().enumerate() {
                    *prefix_shape = prefix_shape.clone().with_name(&name.item(index, []));
                }
                // Even if tail is None, it may still be useful for it to carry
                // the ArrayType.* name from name.any_item([]).
                *tail = tail.clone().with_name(&name.any_item([]));
                self
            }

            ShapeCase::One(shapes) => {
                shapes.shapes =
                    MergeSet::new(shapes.iter().map(|shape| shape.clone().with_name(name)));
                self
            }

            ShapeCase::All(shapes) => {
                shapes.shapes =
                    MergeSet::new(shapes.iter().map(|shape| shape.clone().with_name(name)));
                self
            }

            // Listing these cases explicitly rather than using a catch-all case
            // to avoid missing ShapeCase variants added in the future.
            ShapeCase::Bool(_)
            | ShapeCase::String(_)
            | ShapeCase::Int(_)
            | ShapeCase::Float
            | ShapeCase::Null
            | ShapeCase::Unknown
            | ShapeCase::None => {
                // These shapes do not have children to propagate names to.
                self
            }
            // Although some ShapeCase::Name(name, weak) variants have
            // weakly-held children that can be traversed, those children
            // typically correspond to immutable shapes retrieved from finalized
            // namespaces, so we do not want to propagate child names into them.
            // Also, ShapeCase::Name is the gateway to cyclic shape references,
            // so if we avoid propagating names through the ::Name variant, name
            // propagation won't have to worry about cycles.
            ShapeCase::Name(_, _) => self,
        }
    }
}

#[derive(Clone, Eq)]
pub struct Name {
    case: Ref<NameCase>,
    // Names can have Location metadata, but they cannot have other names as
    // metadata, because names for names for names (and so on) is not a pattern
    // we want to support.
    locs: Ref<IndexSet<Location>>,
}

impl Debug for Name {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "Name(")?;
        <Name as Display>::fmt(self, f)?;
        write!(f, ")")
    }
}

impl Hash for Name {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Only self.case matters for hashing (a la Shape::hash), because only
        // self.case matters for partial equality.
        self.case.hash(state);
    }
}

impl PartialEq for Name {
    fn eq(&self, other: &Self) -> bool {
        // Only self.case matters for equality, a la Shape::eq.
        self.case == other.case
    }
}

impl MetaMergeable for Name {
    fn merge_meta_from(&mut self, other: &Self) -> bool {
        let mut locs_changed = false;

        if !Ref::ptr_eq(&self.locs, &other.locs) {
            // Keep a backup Arc reference so we can restore the original Arc if
            // it gets unnecessarily cloned/severed by Ref::make_mut, but only
            // if the Ref::strong_count is greater than 1.
            //
            // Restoring the backup only matters when Ref::strong_count > 1
            // because if the count is 1, Ref::make_mut is a no-op (needing no
            // defensive cloning), and if we call self.locs.clone() in that case
            // we end up forcing a needless defensive clone because the
            // Ref::strong_count increases to 2 before we call Ref::make_mut.
            let self_locs_backup = if Ref::strong_count(&self.locs) > 1 {
                Some(self.locs.clone())
            } else {
                None
            };

            for locs in other.locs.as_ref() {
                if !self.locs.contains(locs) {
                    Ref::make_mut(&mut self.locs).insert(locs.clone());
                    locs_changed = true;
                }
            }

            if let (false, Some(backup)) = (locs_changed, self_locs_backup) {
                self.locs = backup;
            }
        }

        // One of the reasons it's important to "heal" unnecessarily cloned Arc
        // references is that it gives us a better chance of hitting the
        // Ref::ptr_eq case in the future. We can't unpay the cost of the
        // unnecessary clone, but limiting memory fragmentation can save a
        // significant number of future clones.
        //
        // Another way to prevent fragmentation would be to require
        // MetaMergeable-implementing types also to implement a `fn
        // should_merge_meta_from(&self, other: &Self) -> bool` method, so we
        // could avoid doing any mutative merging if we detect in advance that
        // no metadata will change. However, in the steady state, that approach
        // would always require calling should_merge_meta_from, which is linear
        // in the recursive size of self.case. By contrast, the current method
        // sometimes makes unnecessary shallow clones of self.case via
        // Ref::make_mut, but then falls into a steady state where the Ref data
        // is exclusively owned and no more cloning needs to happen to permit
        // future merges.
        let case_changed = if Ref::ptr_eq(&self.case, &other.case) {
            false
        } else {
            // Similar backup rationale as above, but for self.case.
            let self_case_backup = if Ref::strong_count(&self.case) > 1 {
                Some(self.case.clone())
            } else {
                None
            };

            let case_changed = Ref::make_mut(&mut self.case).merge_parent_meta_from(&other.case);

            if let (false, Some(backup)) = (case_changed, self_case_backup) {
                self.case = backup;
            }

            case_changed
        };

        locs_changed || case_changed
    }
}

impl Name {
    pub(crate) fn new(case: NameCase, locs: impl IntoIterator<Item = Location>) -> Self {
        Self {
            case: Ref::new(case),
            locs: Ref::new(locs.into_iter().collect()),
        }
    }

    pub(crate) fn base(name: impl Into<String>, locs: impl IntoIterator<Item = Location>) -> Self {
        Self::new(NameCase::Base(name.into()), locs)
    }

    #[must_use]
    pub fn base_shape_name(&self) -> &str {
        match self.case() {
            NameCase::Base(name) => name.as_str(),
            NameCase::Field(parent, _)
            | NameCase::AnyField(parent)
            | NameCase::Item(parent, _)
            | NameCase::Question(parent)
            | NameCase::NotNone(parent)
            | NameCase::AnyItem(parent) => parent.base_shape_name(),
        }
    }

    pub(crate) fn field(
        &self,
        field: impl Into<String>,
        locs: impl IntoIterator<Item = Location>,
    ) -> Self {
        Self::new(NameCase::Field(self.clone(), field.into()), locs)
    }

    pub(crate) fn any_field(&self, locs: impl IntoIterator<Item = Location>) -> Self {
        Self::new(NameCase::AnyField(self.clone()), locs)
    }

    pub(crate) fn item(&self, index: usize, locs: impl IntoIterator<Item = Location>) -> Self {
        Self::new(NameCase::Item(self.clone(), index), locs)
    }

    pub(crate) fn any_item(&self, locs: impl IntoIterator<Item = Location>) -> Self {
        // Disallow consecutive .*.* name cases, which should collapse to just a
        // single .* case.
        if let NameCase::AnyItem(_) = self.case() {
            self.clone()
        } else {
            Self::new(NameCase::AnyItem(self.clone()), locs)
        }
    }

    pub(crate) fn question(&self, locs: impl IntoIterator<Item = Location>) -> Self {
        // Disallow consecutive ??? operators, as their effect should be
        // idempotent, and ?? is ambiguous with the nullish coalescing operator.
        if let NameCase::Question(_) = self.case() {
            self.clone()
        } else {
            Self::new(NameCase::Question(self.clone()), locs)
        }
    }

    pub(crate) fn not_none(&self, locs: impl IntoIterator<Item = Location>) -> Self {
        // Disallow consecutive !!! operators, as their effect should be
        // idempotent.
        if let NameCase::NotNone(_) = self.case() {
            self.clone()
        } else {
            Self::new(NameCase::NotNone(self.clone()), locs)
        }
    }

    /// Returns an immutable reference to the [`NameCase`] of this name.
    #[must_use]
    pub fn case(&self) -> &NameCase {
        self.case.as_ref()
    }

    /// Iterates over the segments of this name from the base segment to this
    /// one, walking the parent links once so a name k segments deep costs O(k).
    pub fn iter(&self) -> impl Iterator<Item = &Name> {
        let mut names = vec![self];
        let mut current = self;
        while let Some(parent) = current.parent() {
            names.push(parent);
            current = parent;
        }
        names.into_iter().rev()
    }

    #[allow(dead_code)]
    pub(crate) fn iter_cases(&self) -> impl Iterator<Item = &NameCase> {
        self.iter().map(Name::case)
    }

    /// Returns all Location metadata for this name and all its parents.
    /// Parent locations come before child locations, and a location repeated
    /// by a later segment keeps its first position.
    pub fn locations(&self) -> impl Iterator<Item = &Location> {
        let unique_locs: IndexSet<&Location> = self.iter().flat_map(Name::locs).collect();
        unique_locs.into_iter()
    }

    /// Locations specific to *this* name segment, excluding inherited
    /// locations from parent segments. Use [`Self::locations`] for the
    /// recursive view that also includes parents.
    pub fn locs(&self) -> impl Iterator<Item = &Location> {
        self.locs.iter()
    }

    #[allow(dead_code)]
    pub(crate) fn with_locs<'a>(&self, locs: impl IntoIterator<Item = &'a Location>) -> Self {
        let mut clone = self.clone();
        clone.add_locs(locs);
        clone
    }

    #[allow(dead_code)]
    pub(crate) fn add_locs<'a>(&mut self, locs: impl IntoIterator<Item = &'a Location>) -> bool {
        let mut changed = false;
        for loc in locs {
            if !self.locs.contains(loc) {
                Ref::make_mut(&mut self.locs).insert(loc.clone());
                changed = true;
            }
        }
        changed
    }

    pub(crate) fn parent(&self) -> Option<&Name> {
        self.case.parent()
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum NameCase {
    Base(String),
    Field(Name, String),
    AnyField(Name),
    Item(Name, usize),
    AnyItem(Name),
    Question(Name),
    NotNone(Name),
}

impl NameCase {
    pub(crate) fn parent(&self) -> Option<&Name> {
        match self {
            Self::Base(_) => None,
            Self::Field(parent, _)
            | Self::AnyField(parent)
            | Self::Item(parent, _)
            | Self::Question(parent)
            | Self::NotNone(parent)
            | Self::AnyItem(parent) => Some(parent),
        }
    }

    pub(crate) fn parent_mut(&mut self) -> Option<&mut Name> {
        match self {
            Self::Base(_) => None,
            Self::Field(parent, _)
            | Self::AnyField(parent)
            | Self::Item(parent, _)
            | Self::Question(parent)
            | Self::NotNone(parent)
            | Self::AnyItem(parent) => Some(parent),
        }
    }

    pub(crate) fn merge_parent_meta_from(&mut self, other: &NameCase) -> bool {
        match (self.parent_mut(), other.parent()) {
            (Some(self_parent), Some(other_parent))
                if self_parent.case() == other_parent.case() =>
            {
                // If (and only if) the parent names are the same, then we can
                // merge their metadata.
                self_parent.merge_meta_from(other_parent)
            }

            // This happens normally with NameCase::Base, which can have
            // metadata but has no children with metadata to be merged. However,
            // it is covered by the _ => false catch-all case, so we keep Clippy
            // happy by commenting it out.
            // (None, None) => false,

            // If the parent names are different (or both None; see above), we
            // cannot merge metadata.
            _ => false,
        }
    }
}

impl Display for Name {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if let Some(parent) = self.parent() {
            write!(f, "{parent}")?;
        }
        write!(f, "{}", self.case())
    }
}

impl Display for NameCase {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Base(name) => write!(f, "{name}"),
            Self::Field(_parent, field) => write!(f, ".{}", quote_non_identifier(field)),
            Self::AnyField(_parent) => write!(f, ".**"),
            Self::Item(_parent, index) => write!(f, ".{index}"),
            Self::AnyItem(_parent) => write!(f, ".*"),
            Self::Question(_parent) => write!(f, "?"),
            Self::NotNone(_parent) => write!(f, "!"),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Shape;

    #[test]
    fn test_name() {
        let args = Name::base("$args", []);
        assert_eq!(args.to_string(), "$args");

        let args_limit = args.field("limit", []);
        assert_eq!(args_limit.to_string(), "$args.limit");

        let args_object_any_field = args.field("object", []).any_field([]);
        assert_eq!(args_object_any_field.to_string(), "$args.object.**");

        let args_array_item_0 = args.field("array", []).item(0, []);
        assert_eq!(args_array_item_0.to_string(), "$args.array.0");

        let args_array_any_item = args.field("array", []).any_item([]);
        assert_eq!(args_array_any_item.to_string(), "$args.array.*");

        let args_array_name = args_array_any_item.field("name", []);
        assert_eq!(args_array_name.to_string(), "$args.array.*.name");
    }

    #[test]
    fn test_name_iter_and_locations_order() {
        let source = crate::location::SourceId::new("name.json");
        let loc_a = source.location(0..1);
        let loc_b = source.location(1..2);
        let loc_c = source.location(2..3);

        let base = Name::base("$root", [loc_a.clone()]);
        let b = base.field("b", [loc_b.clone(), loc_a.clone()]);
        let c = b.field("c", [loc_c.clone(), loc_b.clone()]);
        let c_item = c.item(0, []);

        assert_eq!(
            c_item.iter().map(ToString::to_string).collect::<Vec<_>>(),
            vec!["$root", "$root.b", "$root.b.c", "$root.b.c.0"],
        );
        assert_eq!(base.iter().collect::<Vec<_>>(), vec![&base]);

        // Locations come root first, and a location repeated by a later
        // segment keeps the position where it first appeared.
        assert_eq!(
            c_item.locations().collect::<Vec<_>>(),
            vec![&loc_a, &loc_b, &loc_c],
        );
        assert_eq!(c.locs().collect::<Vec<_>>(), vec![&loc_c, &loc_b]);
    }

    #[test]
    fn test_shapes_with_names() {
        let args = Shape::closed_record(
            {
                let mut fields = Shape::empty_map();
                fields.insert("value".to_string(), Shape::int_value(123, []));
                fields.insert("array".to_string(), Shape::list(Shape::string([]), []));
                fields
            },
            [],
        )
        .with_base_name("$args", []);

        let args_value = args.field("value", []);
        assert_eq!(
            args_value.pretty_print_with_names(),
            "123 (aka $args.value)"
        );

        let list_of_args_value = Shape::list(args_value.clone(), []);
        assert_eq!(
            list_of_args_value.pretty_print_with_names(),
            "[...123 (aka $args.value)]"
        );
        assert_eq!(
            list_of_args_value
                .with_base_name("TheList", [])
                .pretty_print_with_names(),
            "[...123 (aka $args.value, TheList.*)] (aka TheList)"
        );

        let record_of_args_value = Shape::closed_record(
            {
                let mut fields = Shape::empty_map();
                fields.insert("limit".to_string(), Shape::int([]));
                fields.insert("value".to_string(), args_value.clone());
                fields
            },
            [],
        );
        assert_eq!(
            record_of_args_value.pretty_print_with_names(),
            "{ limit: Int, value: 123 (aka $args.value) }"
        );
        assert_eq!(
            record_of_args_value
                .with_base_name("SomeRecord", [])
                .pretty_print_with_names(),
            r#"{
  limit: Int (aka SomeRecord.limit),
  value: 123 (aka $args.value, SomeRecord.value),
} (aka SomeRecord)"#,
        );

        let args_value_any_item = args_value.any_item([]);
        assert_eq!(
            args_value_any_item.pretty_print_with_names(),
            // TODO These names seem a bit redundant?
            "123 (aka $args.value)"
        );

        let args_any_field = args.any_field([]);
        assert_eq!(
            args_any_field.pretty_print_with_names(),
            r#"One<
  123 (aka $args.value),
  [...String (aka $args.array.*)] (aka $args.array),
>"#
        );

        let args_array_item_2 = args.field("array", []).item(2, []);
        assert_eq!(
            args_array_item_2.pretty_print_with_names(),
            r#"One<
  String (aka $args.array.*, $args.array.2),
  None (aka $args.array.2),
> (aka $args.array.2)"#
        );
    }

    #[test]
    fn test_name_merging() {
        let record = Shape::closed_record(
            {
                let mut fields = Shape::empty_map();

                fields.insert("a".to_string(), Shape::int([]));
                fields.insert("b".to_string(), Shape::string([]));
                fields.insert("c".to_string(), Shape::bool([]));
                fields.insert("d".to_string(), Shape::null([]));

                fields.insert("A".to_string(), Shape::int([]));
                fields.insert("B".to_string(), Shape::string([]));
                fields.insert("C".to_string(), Shape::bool([]));
                fields.insert("D".to_string(), Shape::null([]));

                fields.insert("xyz".to_string(), Shape::list(Shape::string([]), []));

                fields
            },
            [],
        )
        .with_base_name("Record", []);

        assert_eq!(
            record.pretty_print(),
            r#"{
  A: Int,
  B: String,
  C: Bool,
  D: null,
  a: Int,
  b: String,
  c: Bool,
  d: null,
  xyz: [...String],
}"#
        );

        assert_eq!(
            record.pretty_print_with_names(),
            r#"{
  A: Int (aka Record.A),
  B: String (aka Record.B),
  C: Bool (aka Record.C),
  D: null (aka Record.D),
  a: Int (aka Record.a),
  b: String (aka Record.b),
  c: Bool (aka Record.c),
  d: null (aka Record.d),
  xyz: [...String (aka Record.xyz.*)] (aka Record.xyz),
} (aka Record)"#
        );

        let record_any_field = record.any_field([]);

        assert_eq!(
            record_any_field.pretty_print(),
            "One<Int, String, Bool, null, [...String]>"
        );

        assert_eq!(
            record_any_field.pretty_print_with_names(),
            r#"One<
  Int (aka Record.a, Record.A),
  String (aka Record.b, Record.B),
  Bool (aka Record.c, Record.C),
  null (aka Record.d, Record.D),
  [...String (aka Record.xyz.*)] (aka Record.xyz),
>"#,
        );

        let case_insensitive_a = Shape::one([record.field("a", []), record.field("A", [])], []);

        assert_eq!(case_insensitive_a.pretty_print(), "Int");

        assert_eq!(
            case_insensitive_a.pretty_print_with_names(),
            "Int (aka Record.a, Record.A)",
        );
    }
}