minerva 0.2.0

//! The Rhapsody: the sequence store instance of the causal store axis.

extern crate alloc;

use alloc::collections::BTreeMap;

use super::DotSet;

mod ancestry;
mod children;
mod condense;
mod extent;
mod identity;
mod maintenance;
mod placement;
mod possession;
mod recension;
mod refound;
mod reparent;
mod store;
mod thread;
mod traversal;
mod wire;

#[cfg(feature = "instrumentation")]
pub use ancestry::AncestryProfile;
pub use ancestry::{
    AncestryQueryError, AncestryRelation, CoordinateError as AncestryCoordinateError,
};
use children::ChildPlane;
pub use extent::{Extent, Verge};
use identity::IdentityPlane;
use placement::Dot;
pub use placement::{Anchor, Locus};
use possession::OccupancyPlane;
#[cfg(feature = "instrumentation")]
pub use recension::RecensionProfile;
pub use recension::{
    AncestryAdmissionError, ExactAncestry, MovementBatch, MovementBatchError, Recension,
};
#[cfg(feature = "timing")]
pub use recension::{
    MovementBatchMoveProfile, MovementCycleValidationProfile, MovementCycleValidationWork,
    MovementTopologyPhases, MovementTopologyProfile, MovementTopologyWork, ProfiledMovement,
};
pub use refound::{
    RefoundMap, RefoundMapDecodeBudget, RefoundMapDecodeError, Refounded, UnsealedStratum,
};
use reparent::PlacementEffect;
use thread::OrderThread;
pub use traversal::{OrderWalk, OrderWalkRev};
pub use wire::RhapsodyDecodeError;
pub use wire::SnapshotDecodeError;

/// A bounded structural snapshot of a [`Rhapsody`] for first-party
/// measurement.
///
/// Enabled by the `instrumentation` feature. The profile exposes counts, not
/// internal containers, so measurement code can identify which retained term
/// grows without acquiring mutation capability or depending on storage layout.
#[cfg(feature = "instrumentation")]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct RhapsodyProfile {
    /// Dots ever woven, including invisible order tombstones.
    pub skeleton_dots: usize,
    /// Explicit locus-column entries after chain factoring.
    pub explicit_loci: usize,
    /// Placed order slots, visible and tombstone alike.
    pub placed_slots: usize,
    /// Fragments carrying the placed order slots.
    pub order_fragments: usize,
    /// Nonzero pages in the derived visible occupancy plane.
    pub visible_pages: usize,
    /// Exceptions in the visible have-set above its contiguous floors.
    pub visible_exceptions: usize,
    /// Exceptions in the recording have-set above its contiguous floors.
    pub woven_exceptions: usize,
}

/// The snapshot chain law's successor half, surfaced for the clock-fold
/// agreement harness (`kairos::clock::proofs`) and its sampled twin.
#[cfg(any(test, kani))]
pub use wire::rank_successor;

/// The sequence store: a grow-only ordering skeleton plus causal liveness.
///
/// The first sequence-shaped instance of the open
/// [`DotStore`](crate::metis::DotStore) axis (PRD 0017). An element's identity
/// is a dot minted off a causal pair's context
/// (the PRD 0015 kernel supplies identity, causality, and removal); the Rhapsody
/// supplies *order*. Two coordinates carry that split, the pair's own
/// asymmetry applied to sequencing:
///
/// * the *skeleton* is the grow-only ordering structure, a [`Locus`] per
///   dot ever woven. It never shrinks: a deleted element keeps its locus as
///   an *order tombstone*, because its descendants still anchor through it.
///   Equal dots carry equal loci by the honest basis (a dot names one
///   write, trait law 3), so the
///   [`causal_merge`](crate::metis::DotStore::causal_merge) unions skeletons
///   and keeps either side's locus.
/// * the *visible* set is the live elements, governed by the survivor law
///   ([`DotSet`] is the store there): a dot leaves visibility exactly when a
///   removal delta supersedes it, and a stale peer cannot resurrect it.
///
/// [`order()`](Self::order) reads a document order out of the two coordinates:
/// a depth-first walk of the skeleton from the origin, each anchor's children
/// in rank-descending order, yielding the visible dots and descending through
/// the invisible ones. Deletion is causal invisibility, not structural
/// removal, so an element deleted in the middle of a sequence leaves its
/// following text exactly where it was.
///
/// # Derived coordinates
///
/// Five accelerations ride beside the two carried coordinates. Each is a pure
/// function of carried state, kept current by every mutation, never on the
/// wire, and excluded from equality and hashing. Layout and history are not
/// the value.
///
/// * `children`: per-anchor sibling buckets in sibling order, trading the
///   `O(n log n)` index rebuild per `order()` for an `O(log n)` insert per
///   weave. Maintenance lives on the `&mut` write path, with no interior
///   mutability. The carried form is the coalesced child plane: only
///   exceptional buckets are stored, and a chain interior's sole-child
///   bucket derives from the identity plane per read.
/// * `unplaced`: the woven dots whose anchor chain does not reach the
///   origin. Makes the placement verdict a set lookup where the chain walk
///   would be as deep as the document, which is what lets
///   [`is_reachable`](Self::is_reachable) and
///   [`order_walk_after`](Self::order_walk_after) answer in `O(log n)`.
/// * `woven`: the skeleton's key set in compact [`DotSet`] form, the
///   recording-possession witness handed to a peer per anti-entropy probe.
///   Maintained so the handover is `O(1)` rather than a fold of the
///   document.
/// * `thread`: the monoid-annotated order thread, the positional view of the
///   placed walk, caching slots and visible elements per subtree. Lets
///   [`order_len`](Self::order_len), [`order_at`](Self::order_at),
///   [`offset_of`](Self::offset_of), and the reverse walks answer in
///   `O(log)` where each previously cost a whole `order()` pass. Every
///   placement threads incrementally in walk order, so there is no stale or
///   deferred thread state.
/// * `visible_pages`: the visible plane's paged occupancy masks, one `u64`
///   per station and 64-dot page. The possession-diff shell the collation's
///   mark walk reads, so the visible scan's cost stops depending on
///   have-set fragmentation.
///
/// # What this type does not own
///
/// There is no text buffer and there are no character values. The caller owns
/// each element's dot-keyed payload. There is no cursor or selection model, no undo, and no
/// interleaving-anomaly cure beyond the rank order: the maximal
/// non-interleaving literature is a recorded open question, and the
/// anchoring semantics the visual reads implement are analysed in
/// `docs/metis-rhapsody-anchoring.adoc`.
///
/// It is a `DotStore`, so it travels and converges through
/// [`Dotted`](crate::metis::Dotted). It also carries its own canonical wire
/// frame ([`to_bytes`](Self::to_bytes) / [`from_bytes`](Self::from_bytes)),
/// a byte-identity serialization for shipping and content-addressing that is
/// distinct from that convergence path.
#[derive(Clone, Debug, Default)]
pub struct Rhapsody {
    /// Per dot, its locus; grows forever (order tombstones are retained,
    /// until a retirement claim excises them through `condense`). Carried
    /// as the interned identity plane (crdt-vision arc 11 phase one): the
    /// contract form is still a `dot -> Locus` map, and the plane is its
    /// cost shell (station-paged handle fibers over one locus column),
    /// with layout excluded from the value exactly like the maintained
    /// coordinates below.
    skeleton: IdentityPlane,
    /// The live elements, survivor-law governed.
    visible: DotSet,
    /// Derived: per-[`Anchor`] sibling buckets in sibling order (rank
    /// descending, dot ascending on ties), skeleton dots visible and
    /// tombstone alike. Carried coalesced (arc 11 phase four): exceptional
    /// buckets stored, chain-interior singletons derived from the skeleton
    /// plane per read.
    children: ChildPlane,
    /// Derived (S183): the woven dots whose anchor chain does not reach the
    /// origin, i.e. dangling deltas awaiting repair.
    unplaced: alloc::collections::BTreeSet<Dot>,
    /// Derived (arc 10): the skeleton's key set in compact form, the
    /// recording-plane twin of `visible`, served by [`woven`](Self::woven).
    woven: DotSet,
    /// Derived (arc 11 phase three): the monoid-annotated order thread,
    /// the placed walk's positional view.
    thread: OrderThread,
    /// Derived (S205): the visible plane's paged occupancy masks, the
    /// possession-diff shell the collation's mark walk reads
    /// (`possession/mod.rs`); maintained beside every visibility flip.
    visible_pages: OccupancyPlane,
}

// The child index, the placement set, and the recording have-set are pure
// functions of the skeleton, so a rhapsody's identity is its two carried
// coordinates; equality and hashing ignore the accelerations.
impl PartialEq for Rhapsody {
    fn eq(&self, other: &Self) -> bool {
        self.skeleton == other.skeleton && self.visible == other.visible
    }
}
impl Eq for Rhapsody {}
impl core::hash::Hash for Rhapsody {
    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
        self.skeleton.hash(state);
        self.visible.hash(state);
    }
}

impl Rhapsody {
    /// Creates the empty rhapsody: no skeleton, nothing visible (the lattice
    /// bottom).
    #[must_use]
    pub const fn new() -> Self {
        Self {
            skeleton: IdentityPlane::new(),
            visible: DotSet::new(),
            children: ChildPlane::new(),
            unplaced: alloc::collections::BTreeSet::new(),
            woven: DotSet::new(),
            thread: OrderThread::new(),
            visible_pages: OccupancyPlane::new(),
        }
    }

    /// Builds a rhapsody from its two carried coordinates, materializing the child
    /// index and the placement set once. The single constructor the fresh-`Self`
    /// sites ([`causal_merge`](crate::metis::DotStore::causal_merge),
    /// [`restrict`](crate::metis::DotStore::restrict),
    /// [`novel_to`](crate::metis::DotStore::novel_to)) route through, so both
    /// maintained-coordinate invariants hold by construction wherever a
    /// rhapsody is built from parts.
    fn from_parts(skeleton: BTreeMap<Dot, Locus>, visible: DotSet) -> Self {
        // The map is the contract form; fold it into the interned plane
        // (the cost shell) and derive the maintained coordinates off the
        // plane, so both forms stay compiled and exercised on every build
        // (the shell-discipline agreement posture). The ascending fold
        // rolls the chain predecessor, so the whole build stays linear.
        let mut plane = IdentityPlane::new();
        plane.extend_ascending(skeleton);
        Self::from_plane(plane, visible)
    }

    /// Builds a rhapsody from the carried identity plane, materializing the
    /// derived coordinates once.
    fn from_plane(skeleton: IdentityPlane, visible: DotSet) -> Self {
        let children = ChildPlane::build(&skeleton);
        let unplaced = Self::build_unplaced(&skeleton, &children);
        let mut woven = DotSet::new();
        for (dot, _) in skeleton.iter() {
            let _ = woven.insert(dot);
        }
        let visible_pages = OccupancyPlane::from_pages(visible.occupancy_pages());
        let mut built = Self {
            skeleton,
            visible,
            children,
            unplaced,
            woven,
            thread: OrderThread::new(),
            visible_pages,
        };
        // An empty skeleton's thread is the empty thread it already holds:
        // the guard keeps the hot fragment constructions (a caught-up
        // peer's owed read builds an empty store per probe) off the walk.
        if !built.skeleton.is_empty() {
            built.rebuild_thread();
        }
        built
    }

    /// The recording have-set: every dot ever woven here and not excised,
    /// live elements and order tombstones alike, in compact [`DotSet`] form
    /// (the skeleton's key set, maintained rather than folded per call).
    ///
    /// This is the store's *recording-possession* read, the value a replica
    /// hands a peer so the peer's owed read
    /// ([`Dotted::delta_for_witnessed`](crate::metis::Dotted::delta_for_witnessed))
    /// can withhold the skeleton it demonstrably already holds instead of
    /// shipping the plane whole. It claims possession, never survival: a dot
    /// here may be long deleted (its locus is an order tombstone), and the
    /// survivor coordinate stays [`is_visible`](Self::is_visible)'s. Reading
    /// it from the maintained coordinate cannot over-claim by construction,
    /// which is what makes the witness honest at its source.
    #[must_use]
    pub const fn woven(&self) -> &DotSet {
        &self.woven
    }

    /// The locus of `dot`, if it has ever been woven (a live element or an
    /// order tombstone).
    ///
    /// By value since the plane run-coalesced (S199): a chain-interior
    /// element stores an inline rank step rather than a `Locus`, so the
    /// read materializes its answer instead of lending a reference.
    /// [`Locus`] is `Copy`, and every field read on the binding is
    /// unchanged.
    #[must_use]
    pub fn locus(&self, dot: Dot) -> Option<Locus> {
        self.skeleton.get(&dot)
    }

    /// Whether `dot` is a currently live element.
    #[must_use]
    pub fn is_visible(&self, dot: Dot) -> bool {
        self.visible.contains(dot)
    }

    /// The number of currently live (visible) elements. Counted per call
    /// over the have-set, unlike the `O(1)`
    /// [`skeleton_len`](Self::skeleton_len) and
    /// [`order_len`](Self::order_len).
    #[must_use]
    pub fn visible_len(&self) -> usize {
        self.visible.dots().count()
    }

    /// The number of dots ever woven (live elements plus order tombstones):
    /// the size of the grow-only skeleton.
    #[must_use]
    pub const fn skeleton_len(&self) -> usize {
        self.skeleton.len()
    }

    /// Captures the representation terms used by deterministic scale
    /// instruments.
    ///
    /// This is a read-only accounting boundary. Counts describe the current
    /// implementation and carry no convergence or wire semantics.
    #[cfg(feature = "instrumentation")]
    #[must_use]
    pub fn profile(&self) -> RhapsodyProfile {
        RhapsodyProfile {
            skeleton_dots: self.skeleton.len(),
            explicit_loci: self.skeleton_explicit_entries(),
            placed_slots: self.thread.slot_len(),
            order_fragments: self.order_thread_fragments(),
            visible_pages: self.visible_pages.page_count(),
            visible_exceptions: self.visible.exceptions_len(),
            woven_exceptions: self.woven.exceptions_len(),
        }
    }

    /// Live explicit locus-column entries in the identity plane: chain
    /// heads plus everything unchained, everything else riding as inline
    /// rank steps (crdt-vision arc 11 phase two). The run-coalescing
    /// accounting read the closed-forms probe asserts; on honest chained
    /// traffic this is the run count, not the element count.
    #[cfg(any(test, feature = "instrumentation"))]
    pub(crate) const fn skeleton_explicit_entries(&self) -> usize {
        self.skeleton.explicit_entries()
    }

    /// Exceptional sibling buckets stored by the coalesced child plane
    /// (crdt-vision arc 11 phase four); every other anchor's children are
    /// derived from the identity plane per read. On honest chained traffic
    /// this is the run-boundary count, not the element count.
    #[cfg(test)]
    pub(crate) fn child_explicit_buckets(&self) -> usize {
        self.children.explicit_buckets()
    }

    /// Children stored explicitly by the coalesced child plane; every
    /// other woven element's sole-child bucket rides as its own plane
    /// entry (arc 11 phase four).
    #[cfg(test)]
    pub(crate) fn child_explicit_children(&self) -> usize {
        self.children.explicit_children()
    }

    /// Order-thread fragments held: the positional plane's run-coalescing
    /// accounting read (crdt-vision arc 11 phase three); each maximal run
    /// occupies one fragment per 64-slot segment.
    #[cfg(any(test, feature = "instrumentation"))]
    pub(crate) fn order_thread_fragments(&self) -> usize {
        self.thread.fragments()
    }

    /// Placed dots covered by the dynamic region-endpoint plane's
    /// segments (the coverage invariant's read).
    #[cfg(test)]
    pub(crate) fn order_thread_region_nodes(&self) -> usize {
        self.thread.region_nodes()
    }

    /// Region segments held by the endpoint plane (arc 11 phase five):
    /// on honest chained traffic, the run count.
    #[cfg(test)]
    pub(crate) fn order_thread_region_segments(&self) -> usize {
        self.thread.region_segments()
    }

    /// Link-cut nodes actually allocated across both region forests: the
    /// lazy-allocation accounting read (stored edges only, never chain
    /// arithmetic).
    #[cfg(test)]
    pub(crate) fn order_thread_region_forest_nodes(&self) -> usize {
        self.thread.region_forest_nodes()
    }

    /// Exhaustive order-thread structural check for the test suites:
    /// settled, parent links exact, aggregates exact, fragment index
    /// covering.
    #[cfg(test)]
    pub(crate) fn check_order_thread(&self) {
        self.thread.check_invariants();
        assert_eq!(
            self.thread.region_nodes(),
            self.thread.slot_len(),
            "the region segments cover every placed slot exactly once"
        );
        // The occupancy shell rides the same exhaustive check: every
        // suite that samples the thread samples the possession plane's
        // agreement with its carried set (S205).
        self.visible_pages.check_against(self.visible.dots());
    }

    /// The length of [`order()`](Self::order) without materializing it:
    /// the placed visible element count, read off the order thread's root
    /// aggregate in `O(1)` (arc 11 phase three, S200).
    ///
    /// Deliberately not [`visible_len`](Self::visible_len): a dangling
    /// delta's element is visible but has no place in the current order
    /// until its repair merge, so the two counts differ exactly where
    /// [`is_reachable`](Self::is_reachable) says so.
    #[must_use]
    pub fn order_len(&self) -> usize {
        self.thread.visible_len()
    }

    /// The element at visible offset `offset` (zero-based): exactly
    /// `order()[offset]`, in `O(log)` off the order thread's aggregates
    /// instead of one whole `order()` pass (arc 11 phase three, S200).
    /// `None` at and past [`order_len`](Self::order_len): out of range is
    /// a verdict, never a clamp.
    #[must_use]
    pub fn order_at(&self, offset: usize) -> Option<Dot> {
        self.thread.order_at(offset)
    }

    /// The visible offset of `dot`'s slot: for a visible
    /// element, its index in [`order()`](Self::order); for an order
    /// tombstone, the count of visible elements strictly before its slot
    /// (the offset its slot bounds, the same degrade
    /// [`extent`](Self::extent) reads through tombstone boundaries).
    /// `O(log)` off the order thread. Returns `None` exactly where
    /// [`is_reachable`](Self::is_reachable) is false (a dot never woven
    /// here, or a dangling delta before its repair): an
    /// unplaced element has no offset, and fabricating one would let an
    /// out-of-order delta read as positioned.
    #[must_use]
    pub fn offset_of(&self, dot: Dot) -> Option<usize> {
        self.thread
            .position_of(dot)
            .map(|(_, visible_before)| visible_before)
    }
}