minerva 0.2.0

//! Rooted exact ancestry over the effective identity plane.
//!
//! The coordinate owns one stable node per woven dot and one synthetic root.
//! Dot lookup follows the identity plane's station/page/slot factoring, so no
//! per-dot key map accompanies the arena. Unplaced dots keep their reserved
//! nodes detached until the effective topology repairs them.

extern crate alloc;

use alloc::boxed::Box;
use alloc::collections::{BTreeMap, BTreeSet};
use alloc::vec::Vec;
use core::num::NonZeroU32;

use super::identity::{IdentityPlane, PAGE_LEN, PLANE_CAPACITY};
use super::placement::{Dot, Locus};
use crate::metis::dot::RawDot;

const PAGE_LEN_U64: u64 = PAGE_LEN as u64;

/// A non-null arena address. `None` is the only absent link spelling.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct NodeId(NonZeroU32);

const _: () = assert!(core::mem::size_of::<Option<NodeId>>() == 4);

impl NodeId {
    const ROOT: Self = Self(NonZeroU32::MIN);

    fn for_index(index: usize) -> Option<Self> {
        u32::try_from(index)
            .ok()
            .and_then(|raw| raw.checked_add(1))
            .and_then(NonZeroU32::new)
            .map(Self)
    }

    const fn index(self) -> usize {
        self.0.get() as usize - 1
    }
}

/// One link-cut node. Auxiliary links and represented parent links share the
/// standard link-cut `parent` field.
#[derive(Clone, Copy, Debug, Default)]
struct Node {
    left: Option<NodeId>,
    right: Option<NodeId>,
    parent: Option<NodeId>,
}

const _: () = assert!(core::mem::size_of::<Node>() == 12);

#[derive(Clone, Debug)]
struct AddressPage {
    slots: [Option<NodeId>; PAGE_LEN],
    occupancy: u8,
}

impl AddressPage {
    const fn empty() -> Self {
        Self {
            slots: [None; PAGE_LEN],
            occupancy: 0,
        }
    }
}

/// A station fiber with the same dense-prefix/sparse-exception split as the
/// identity plane.
#[derive(Clone, Debug, Default)]
struct AddressFiber {
    prefix: Vec<Option<Box<AddressPage>>>,
    above: BTreeMap<u64, Box<AddressPage>>,
}

impl AddressFiber {
    fn page(&self, number: u64) -> Option<&AddressPage> {
        match usize::try_from(number) {
            Ok(offset) if offset < self.prefix.len() => self.prefix[offset].as_deref(),
            _ => self.above.get(&number).map(Box::as_ref),
        }
    }

    fn page_mut_or_create(&mut self, number: u64) -> &mut AddressPage {
        if let Ok(offset) = usize::try_from(number) {
            if offset < self.prefix.len() {
                return self.prefix[offset].get_or_insert_with(|| Box::new(AddressPage::empty()));
            }
            if offset == self.prefix.len() {
                self.prefix.push(Some(Box::new(AddressPage::empty())));
                self.promote_contiguous();
                return self.prefix[offset]
                    .as_deref_mut()
                    .expect("the page was just inserted");
            }
        }
        self.above
            .entry(number)
            .or_insert_with(|| Box::new(AddressPage::empty()))
    }

    fn promote_contiguous(&mut self) {
        while let Ok(next) = u64::try_from(self.prefix.len()) {
            let Some(page) = self.above.remove(&next) else {
                break;
            };
            self.prefix.push(Some(page));
        }
    }

    #[cfg(any(test, feature = "instrumentation"))]
    fn pages(&self) -> usize {
        self.prefix.iter().filter(|page| page.is_some()).count() + self.above.len()
    }

    #[cfg(any(test, feature = "instrumentation"))]
    const fn prefix_slots(&self) -> usize {
        self.prefix.len()
    }

    #[cfg(any(test, feature = "instrumentation"))]
    const fn prefix_capacity(&self) -> usize {
        self.prefix.capacity()
    }

    #[cfg(any(test, feature = "instrumentation"))]
    fn exception_pages(&self) -> usize {
        self.above.len()
    }
}

#[derive(Clone, Debug, Default)]
struct AddressPlane {
    stations: BTreeMap<u32, AddressFiber>,
    len: usize,
}

impl AddressPlane {
    fn get(&self, dot: Dot) -> Option<NodeId> {
        let (page, slot) = page_slot(dot.counter())?;
        self.stations.get(&dot.station())?.page(page)?.slots[slot]
    }

    fn insert(&mut self, dot: Dot, id: NodeId) -> bool {
        let Some((page_number, slot)) = page_slot(dot.counter()) else {
            return false;
        };
        let page = self
            .stations
            .entry(dot.station())
            .or_default()
            .page_mut_or_create(page_number);
        if page.slots[slot].is_some() {
            return false;
        }
        page.slots[slot] = Some(id);
        page.occupancy += 1;
        self.len += 1;
        true
    }

    #[cfg(any(test, feature = "instrumentation"))]
    fn pages(&self) -> usize {
        self.stations.values().map(AddressFiber::pages).sum()
    }

    #[cfg(any(test, feature = "instrumentation"))]
    fn prefix_slots(&self) -> usize {
        self.stations.values().map(AddressFiber::prefix_slots).sum()
    }

    #[cfg(any(test, feature = "instrumentation"))]
    fn prefix_capacity(&self) -> usize {
        self.stations
            .values()
            .map(AddressFiber::prefix_capacity)
            .sum()
    }

    #[cfg(any(test, feature = "instrumentation"))]
    fn exception_pages(&self) -> usize {
        self.stations
            .values()
            .map(AddressFiber::exception_pages)
            .sum()
    }
}

fn page_slot(index: u64) -> Option<(u64, usize)> {
    let zero_based = index.checked_sub(1)?;
    Some((
        zero_based / PAGE_LEN_U64,
        usize::try_from(zero_based % PAGE_LEN_U64).expect("a page offset fits usize"),
    ))
}

/// Representation failures are structural, never movement verdicts.
#[derive(Clone, Copy, Debug, PartialEq, Eq, thiserror::Error)]
pub enum CoordinateError {
    /// The effective identity plane exceeds the coordinate's node ceiling.
    #[error("{nodes} resident identities exceed the ancestry ceiling of {maximum}")]
    CapacityExceeded {
        /// Resident woven identities requested.
        nodes: usize,
        /// Maximum resident woven identities supported.
        maximum: usize,
    },
    /// The effective placement plane and coordinate disagree structurally.
    #[error("the ancestry coordinate violates its structural invariant")]
    InvariantViolation,
}

/// Inclusive exact ancestry over the effective parent plane.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum AncestryRelation {
    /// Both operands name the same effective identity.
    Same,
    /// The first operand reaches the second through one or more parent edges.
    Descendant,
    /// Both operands are known and placed, but no such parent path exists.
    NotDescendant,
}

pub(super) type Relation = AncestryRelation;

/// Failure to answer an admitted exact ancestry query.
#[derive(Clone, Copy, Debug, PartialEq, Eq, thiserror::Error)]
pub enum AncestryQueryError {
    /// The descendant is not woven into the effective reading.
    #[error("the ancestry descendant {dot:?} is not woven")]
    UnknownDescendant {
        /// The unknown identity.
        dot: Dot,
    },
    /// The ancestor is not woven into the effective reading.
    #[error("the ancestry ancestor {dot:?} is not woven")]
    UnknownAncestor {
        /// The unknown identity.
        dot: Dot,
    },
    /// The coordinate could not complete its bounded structural operation.
    #[error("the ancestry coordinate violates its structural invariant")]
    InvariantViolation,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum QueryError {
    UnknownDescendant { dot: Dot },
    UnknownAncestor { dot: Dot },
    UnplacedReading { first_unplaced: Dot },
    InvariantViolation,
}

impl QueryError {
    pub(super) const fn into_public(self) -> AncestryQueryError {
        match self {
            Self::UnknownDescendant { dot } => AncestryQueryError::UnknownDescendant { dot },
            Self::UnknownAncestor { dot } => AncestryQueryError::UnknownAncestor { dot },
            Self::UnplacedReading { .. } | Self::InvariantViolation => {
                AncestryQueryError::InvariantViolation
            }
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum CoordinateState {
    Ready,
    Unplaced { first: Dot },
}

/// Complete structural accounting. Container allocator overhead is a property
/// of the allocator; every retained element that drives it is counted here.
#[cfg(any(test, feature = "instrumentation"))]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct AncestryProfile {
    /// Woven identities with reserved coordinate nodes.
    pub resident_nodes: usize,
    /// Allocated node arena slots, including the synthetic root.
    pub node_capacity: usize,
    /// Resident 64-dot address pages.
    pub address_pages: usize,
    /// Address slots per resident page.
    pub address_page_capacity: usize,
    /// Dense-prefix page slots across station fibers.
    pub address_prefix_slots: usize,
    /// Allocated dense-prefix page slots across station fibers.
    pub address_prefix_capacity: usize,
    /// Sparse address pages above station prefixes.
    pub address_exception_pages: usize,
    /// Stations retaining at least one address fiber.
    pub station_fibers: usize,
    /// Reusable node slots retained after removal.
    pub free_nodes: usize,
    /// Allocated reusable-node slots.
    pub free_node_capacity: usize,
}

/// A rooted dynamic forest over every effective identity.
#[derive(Clone, Debug)]
pub(super) struct Coordinate {
    nodes: Vec<Node>,
    addresses: AddressPlane,
    state: CoordinateState,
}

impl Coordinate {
    /// Builds the whole coordinate off to the side. No caller-visible state
    /// exists until every resident address and placed edge validates.
    pub(super) fn build(
        skeleton: &IdentityPlane,
        unplaced: &BTreeSet<Dot>,
    ) -> Result<Self, CoordinateError> {
        Self::build_with_limit(skeleton, unplaced, PLANE_CAPACITY)
    }

    fn build_with_limit(
        skeleton: &IdentityPlane,
        unplaced: &BTreeSet<Dot>,
        maximum: usize,
    ) -> Result<Self, CoordinateError> {
        let resident = skeleton.len();
        let maximum = maximum.min(PLANE_CAPACITY);
        if resident > maximum {
            return Err(CoordinateError::CapacityExceeded {
                nodes: resident,
                maximum,
            });
        }
        for &dot in unplaced {
            let locus = skeleton
                .get(&dot)
                .ok_or(CoordinateError::InvariantViolation)?;
            // An anchor is a payload coordinate; a non-dot one names no
            // woven element, so it falls through exactly where an unwoven
            // coordinate does (the payload funnel, ruling R-91).
            match locus.anchor.dot().map(|raw| Dot::try_from(raw).ok()) {
                None => return Err(CoordinateError::InvariantViolation),
                Some(Some(parent)) if skeleton.contains(parent) && !unplaced.contains(&parent) => {
                    return Err(CoordinateError::InvariantViolation);
                }
                Some(_) => {}
            }
        }

        let mut nodes = Vec::new();
        nodes.reserve_exact(resident + 1);
        nodes.push(Node::default());
        let mut addresses = AddressPlane::default();
        for (dot, _) in skeleton.iter() {
            let id = NodeId::for_index(nodes.len()).ok_or(CoordinateError::CapacityExceeded {
                nodes: resident,
                maximum: u32::MAX as usize - 1,
            })?;
            nodes.push(Node::default());
            if !addresses.insert(dot, id) {
                return Err(CoordinateError::InvariantViolation);
            }
        }

        let state = unplaced
            .first()
            .copied()
            .map_or(CoordinateState::Ready, |first| CoordinateState::Unplaced {
                first,
            });
        let mut coordinate = Self {
            nodes,
            addresses,
            state,
        };
        for (dot, locus) in skeleton.iter() {
            if unplaced.contains(&dot) {
                continue;
            }
            let child = coordinate
                .addresses
                .get(dot)
                .ok_or(CoordinateError::InvariantViolation)?;
            let parent = match locus.anchor.dot().map(|raw| Dot::try_from(raw).ok()) {
                None => NodeId::ROOT,
                Some(Some(parent)) if !unplaced.contains(&parent) => coordinate
                    .addresses
                    .get(parent)
                    .ok_or(CoordinateError::InvariantViolation)?,
                // A parked or non-dot anchor has no resident address here.
                Some(_) => return Err(CoordinateError::InvariantViolation),
            };
            coordinate.link_isolated(child, parent)?;
        }
        coordinate.validate(skeleton, unplaced)?;
        Ok(coordinate)
    }

    pub(super) fn relation(
        &mut self,
        descendant: Dot,
        ancestor: Dot,
    ) -> Result<Relation, QueryError> {
        let descendant_id = self
            .addresses
            .get(descendant)
            .ok_or(QueryError::UnknownDescendant { dot: descendant })?;
        let ancestor_id = self
            .addresses
            .get(ancestor)
            .ok_or(QueryError::UnknownAncestor { dot: ancestor })?;
        if let CoordinateState::Unplaced { first } = self.state {
            return Err(QueryError::UnplacedReading {
                first_unplaced: first,
            });
        }
        if descendant_id == ancestor_id {
            return Ok(Relation::Same);
        }
        let lca = self
            .lowest_common_ancestor(descendant_id, ancestor_id)
            .map_err(|_| QueryError::InvariantViolation)?;
        Ok(if lca == ancestor_id {
            Relation::Descendant
        } else {
            Relation::NotDescendant
        })
    }

    pub(super) const fn first_unplaced(&self) -> Option<Dot> {
        match self.state {
            CoordinateState::Ready => None,
            CoordinateState::Unplaced { first } => Some(first),
        }
    }

    /// Reserves one resident node and publishes its initial represented edge.
    /// The caller supplies the effective plane's post-transition readiness.
    pub(super) fn add(
        &mut self,
        dot: Dot,
        parent: Option<RawDot>,
        placed: bool,
        first_unplaced: Option<Dot>,
    ) -> Result<(), CoordinateError> {
        let resident = self.nodes.len().saturating_sub(1);
        if resident >= PLANE_CAPACITY {
            return Err(CoordinateError::CapacityExceeded {
                nodes: resident.saturating_add(1),
                maximum: PLANE_CAPACITY,
            });
        }
        // The non-dot index needs no arm: [`Dot`] carries that law now
        // (ruling R-91).
        if self.addresses.get(dot).is_some() {
            return Err(CoordinateError::InvariantViolation);
        }
        let parent = if placed {
            parent
                .map(|raw| {
                    Dot::try_from(raw)
                        .ok()
                        .and_then(|parent| self.addresses.get(parent))
                        .ok_or(CoordinateError::InvariantViolation)
                })
                .transpose()?
        } else {
            None
        };
        let id = NodeId::for_index(self.nodes.len()).ok_or_else(|| {
            CoordinateError::CapacityExceeded {
                nodes: resident.saturating_add(1),
                maximum: u32::MAX as usize - 1,
            }
        })?;
        self.nodes.push(Node::default());
        if placed {
            let parent = parent.unwrap_or(NodeId::ROOT);
            if let Err(error) = self.link_isolated(id, parent) {
                let _ = self.nodes.pop();
                return Err(error);
            }
        }
        if !self.addresses.insert(dot, id) {
            if self.represented_parent(id)?.is_some() {
                self.cut_parent(id)?;
            }
            let _ = self.nodes.pop();
            return Err(CoordinateError::InvariantViolation);
        }
        self.publish_state(first_unplaced);
        Ok(())
    }

    /// Replaces one placed node's represented parent. Cycle admission belongs
    /// to the caller; this operation performs no ancestry relation query.
    pub(super) fn replace_parent(
        &mut self,
        dot: Dot,
        parent: Option<RawDot>,
    ) -> Result<(), CoordinateError> {
        let child = self
            .addresses
            .get(dot)
            .ok_or(CoordinateError::InvariantViolation)?;
        let parent = self.parent_id(parent)?;
        let old_parent = self
            .represented_parent(child)?
            .ok_or(CoordinateError::InvariantViolation)?;
        self.cut_parent(child)?;
        if let Err(error) = self.link_isolated(child, parent) {
            self.link_isolated(child, old_parent)?;
            return Err(error);
        }
        Ok(())
    }

    /// Detaches one previously placed node. A parked region is detached one
    /// resident node at a time and published as unplaced only after completion.
    pub(super) fn park(&mut self, dot: Dot) -> Result<(), CoordinateError> {
        let child = self
            .addresses
            .get(dot)
            .ok_or(CoordinateError::InvariantViolation)?;
        self.cut_parent(child)
    }

    /// Reattaches one isolated resident node under a placed parent or origin.
    /// Repair order is parent before child.
    pub(super) fn repair(
        &mut self,
        dot: Dot,
        parent: Option<RawDot>,
    ) -> Result<(), CoordinateError> {
        let child = self
            .addresses
            .get(dot)
            .ok_or(CoordinateError::InvariantViolation)?;
        let parent = self.parent_id(parent)?;
        self.link_isolated(child, parent)
    }

    pub(super) const fn publish_state(&mut self, first_unplaced: Option<Dot>) {
        self.state = match first_unplaced {
            Some(first) => CoordinateState::Unplaced { first },
            None => CoordinateState::Ready,
        };
    }

    #[cfg(any(test, feature = "instrumentation"))]
    pub(super) fn profile(&self) -> AncestryProfile {
        AncestryProfile {
            resident_nodes: self.addresses.len,
            node_capacity: self.nodes.capacity(),
            address_pages: self.addresses.pages(),
            address_page_capacity: PAGE_LEN,
            address_prefix_slots: self.addresses.prefix_slots(),
            address_prefix_capacity: self.addresses.prefix_capacity(),
            address_exception_pages: self.addresses.exception_pages(),
            station_fibers: self.addresses.stations.len(),
            free_nodes: 0,
            free_node_capacity: 0,
        }
    }

    fn node(&self, id: NodeId) -> Result<&Node, CoordinateError> {
        self.nodes
            .get(id.index())
            .ok_or(CoordinateError::InvariantViolation)
    }

    fn node_mut(&mut self, id: NodeId) -> Result<&mut Node, CoordinateError> {
        self.nodes
            .get_mut(id.index())
            .ok_or(CoordinateError::InvariantViolation)
    }

    /// The node for an anchor coordinate: the synthetic root at the origin,
    /// the resident address otherwise. A non-dot coordinate names no
    /// resident address, so it refuses exactly as an unknown one does (the
    /// payload funnel, ruling R-91).
    fn parent_id(&self, parent: Option<RawDot>) -> Result<NodeId, CoordinateError> {
        parent.map_or(Ok(NodeId::ROOT), |raw| {
            Dot::try_from(raw)
                .ok()
                .and_then(|dot| self.addresses.get(dot))
                .ok_or(CoordinateError::InvariantViolation)
        })
    }

    fn is_aux_root(&self, id: NodeId) -> Result<bool, CoordinateError> {
        let Some(parent) = self.node(id)?.parent else {
            return Ok(true);
        };
        let parent = self.node(parent)?;
        Ok(parent.left != Some(id) && parent.right != Some(id))
    }

    fn rotate(&mut self, id: NodeId) -> Result<(), CoordinateError> {
        let parent = self
            .node(id)?
            .parent
            .ok_or(CoordinateError::InvariantViolation)?;
        let grand = self.node(parent)?.parent;
        let parent_is_aux_root = self.is_aux_root(parent)?;
        let id_is_left = self.node(parent)?.left == Some(id);
        let id_is_right = self.node(parent)?.right == Some(id);
        if id_is_left == id_is_right {
            return Err(CoordinateError::InvariantViolation);
        }
        let middle = if id_is_left {
            self.node(id)?.right
        } else {
            self.node(id)?.left
        };
        if id_is_left {
            self.node_mut(parent)?.left = middle;
            self.node_mut(id)?.right = Some(parent);
        } else {
            self.node_mut(parent)?.right = middle;
            self.node_mut(id)?.left = Some(parent);
        }
        if let Some(middle) = middle {
            self.node_mut(middle)?.parent = Some(parent);
        }
        self.node_mut(parent)?.parent = Some(id);
        self.node_mut(id)?.parent = grand;
        if !parent_is_aux_root {
            let grand = grand.ok_or(CoordinateError::InvariantViolation)?;
            if self.node(grand)?.left == Some(parent) {
                self.node_mut(grand)?.left = Some(id);
            } else if self.node(grand)?.right == Some(parent) {
                self.node_mut(grand)?.right = Some(id);
            } else {
                return Err(CoordinateError::InvariantViolation);
            }
        }
        Ok(())
    }

    fn splay(&mut self, id: NodeId) -> Result<(), CoordinateError> {
        for _ in 0..=self.nodes.len() {
            if self.is_aux_root(id)? {
                return Ok(());
            }
            let parent = self
                .node(id)?
                .parent
                .ok_or(CoordinateError::InvariantViolation)?;
            if !self.is_aux_root(parent)? {
                let grand = self
                    .node(parent)?
                    .parent
                    .ok_or(CoordinateError::InvariantViolation)?;
                let id_is_left = self.node(parent)?.left == Some(id);
                let parent_is_left = self.node(grand)?.left == Some(parent);
                if id_is_left == parent_is_left {
                    self.rotate(parent)?;
                } else {
                    self.rotate(id)?;
                }
            }
            self.rotate(id)?;
        }
        Err(CoordinateError::InvariantViolation)
    }

    /// Exposes the represented-root-to-`id` path. The returned node is the
    /// last represented vertex visited and is the LCA after a prior access.
    fn access(&mut self, id: NodeId) -> Result<NodeId, CoordinateError> {
        let mut current = Some(id);
        let mut last = None;
        for _ in 0..=self.nodes.len() {
            let Some(at) = current else {
                self.splay(id)?;
                return last.ok_or(CoordinateError::InvariantViolation);
            };
            self.splay(at)?;
            current = self.node(at)?.parent;
            self.node_mut(at)?.right = last;
            if let Some(last) = last {
                self.node_mut(last)?.parent = Some(at);
            }
            last = Some(at);
        }
        Err(CoordinateError::InvariantViolation)
    }

    fn represented_root(&mut self, id: NodeId) -> Result<NodeId, CoordinateError> {
        let _ = self.access(id)?;
        let mut root = id;
        for _ in 0..self.nodes.len() {
            let Some(left) = self.node(root)?.left else {
                self.splay(root)?;
                return Ok(root);
            };
            root = left;
        }
        Err(CoordinateError::InvariantViolation)
    }

    fn represented_parent(&mut self, id: NodeId) -> Result<Option<NodeId>, CoordinateError> {
        let _ = self.access(id)?;
        let Some(mut parent) = self.node(id)?.left else {
            return Ok(None);
        };
        for _ in 0..self.nodes.len() {
            let Some(right) = self.node(parent)?.right else {
                self.splay(parent)?;
                return Ok(Some(parent));
            };
            parent = right;
        }
        Err(CoordinateError::InvariantViolation)
    }

    fn lowest_common_ancestor(
        &mut self,
        left: NodeId,
        right: NodeId,
    ) -> Result<NodeId, CoordinateError> {
        if self.represented_root(left)? != self.represented_root(right)? {
            return Err(CoordinateError::InvariantViolation);
        }
        let _ = self.access(left)?;
        self.access(right)
    }

    fn link_isolated(&mut self, child: NodeId, parent: NodeId) -> Result<(), CoordinateError> {
        let child_root = self.represented_root(child)?;
        let parent_root = self.represented_root(parent)?;
        if child_root != child || parent_root == child {
            return Err(CoordinateError::InvariantViolation);
        }
        let _ = self.access(child)?;
        self.node_mut(child)?.parent = Some(parent);
        Ok(())
    }

    fn cut_parent(&mut self, child: NodeId) -> Result<(), CoordinateError> {
        let _ = self.access(child)?;
        let path = self
            .node(child)?
            .left
            .ok_or(CoordinateError::InvariantViolation)?;
        self.node_mut(child)?.left = None;
        self.node_mut(path)?.parent = None;
        Ok(())
    }

    pub(super) fn validate(
        &mut self,
        skeleton: &IdentityPlane,
        unplaced: &BTreeSet<Dot>,
    ) -> Result<(), CoordinateError> {
        if self.addresses.len != skeleton.len() || self.nodes.len() != skeleton.len() + 1 {
            return Err(CoordinateError::InvariantViolation);
        }
        for (dot, locus) in skeleton.iter() {
            let id = self
                .addresses
                .get(dot)
                .ok_or(CoordinateError::InvariantViolation)?;
            let expected = if unplaced.contains(&dot) {
                None
            } else {
                expected_parent(&self.addresses, locus, unplaced)?
            };
            let actual_parent = self.represented_parent(id)?;
            if actual_parent != expected {
                return Err(CoordinateError::InvariantViolation);
            }
            let expected_root = if unplaced.contains(&dot) {
                id
            } else {
                NodeId::ROOT
            };
            let actual_root = self.represented_root(id)?;
            if actual_root != expected_root {
                return Err(CoordinateError::InvariantViolation);
            }
        }
        Ok(())
    }
}

fn expected_parent(
    addresses: &AddressPlane,
    locus: Locus,
    unplaced: &BTreeSet<Dot>,
) -> Result<Option<NodeId>, CoordinateError> {
    match locus.anchor.dot().map(|raw| Dot::try_from(raw).ok()) {
        None => Ok(Some(NodeId::ROOT)),
        Some(Some(parent)) if unplaced.contains(&parent) => Ok(None),
        Some(Some(parent)) => addresses
            .get(parent)
            .map(Some)
            .ok_or(CoordinateError::InvariantViolation),
        // A non-dot anchor coordinate has no resident address (R-91).
        Some(None) => Err(CoordinateError::InvariantViolation),
    }
}

#[cfg(test)]
mod tests;