minerva 0.2.0

extern crate alloc;

use alloc::vec::Vec;

use super::children::{Bucket, sibling_cmp};
use super::placement::Dot;
use super::placement::RawDot;
use super::{Anchor, Rhapsody};

/// A frame of the in-order walk's explicit stack ([`order`](Rhapsody::order) /
/// [`OrderWalk`]): `Visit` expands a dot's Before/self/After schedule, `Emit`
/// yields it if visible.
#[derive(Clone, Copy, Debug)]
enum Frame {
    /// Expand this dot's children and schedule its own emit.
    Visit(Dot),
    /// Emit this dot (if visible); its subtrees are already scheduled.
    Emit(Dot),
}

/// The lazy in-order walk over a [`Rhapsody`]'s document order: the visible
/// dots, yielded one at a time in sequence order.
///
/// From [`order_walk`](Rhapsody::order_walk) (whole document) or
/// [`order_walk_after`](Rhapsody::order_walk_after) (resumed after a placed
/// element). This is the walk that [`order()`](Rhapsody::order) runs.
/// `order()` is exactly `order_walk().collect()`, so the eager and lazy reads
/// cannot drift.
///
/// # Shape and cost
///
/// `O(1)` amortized per skeleton dot passed, and the iterator holds only its
/// pending stack, so a consumer taking `k` elements pays for the window
/// rather than the document.
///
/// A *resumed* walk also carries its climb: the anchor-chain levels above the
/// resume point, scheduled lazily one level at a time as the frames below run
/// dry. A window that ends inside the resume point's own subtree never climbs.
/// This is the common case for a forward-typed document. It keeps the resume
/// `O(log n)` instead of `O(depth)` on
/// chain-shaped documents where depth equals length.
///
/// The walk descends through invisible skeleton, since an order tombstone
/// still anchors its descendants, so a window over a tombstone-heavy region
/// pays for what it steps past; `condense` is the cure.
///
/// Borrows the store, so a live walk cannot observe a half-applied write.
/// Fused.
#[derive(Clone, Debug)]
pub struct OrderWalk<'a> {
    /// The store being walked; the walk reads its child index and visibility.
    rhapsody: &'a Rhapsody,
    /// Pending frames, popped LIFO; empty means this level is exhausted.
    stack: Vec<Frame>,
    /// The resume climb's next level: the chain dot whose ancestors' pending
    /// frames have not been scheduled yet. `None` once the climb has passed
    /// the origin, and always `None` for a from-the-start walk. Exhausted
    /// means: empty `stack` AND `None` here.
    climb: Option<Dot>,
}

impl OrderWalk<'_> {
    /// Schedules one climb level's pending frames: the siblings that traverse
    /// after the chain dot at this level, plus, for a
    /// [`Before`](Anchor::Before) link, the anchor's own emit and its
    /// [`After`](Anchor::After) bucket (those read after the before-region).
    /// Returns `None` when the climb is exhausted (or was never a resume).
    ///
    /// The resume point was verified placed at construction, so the chain
    /// reaches the origin through present loci and every lookup here is
    /// total; the `?`s keep the walk total anyway (an impossible miss ends
    /// the iterator rather than panicking).
    fn climb_one_level(&mut self) -> Option<()> {
        let cursor = self.climb?;
        let locus = self.rhapsody.skeleton.get(&cursor)?;
        // Frames must pop in traversal order, so each block below pushes its
        // contribution in the reverse of that reading order.
        match locus.anchor {
            Anchor::Origin => {
                self.climb = None;
                let bucket = self
                    .rhapsody
                    .children
                    .bucket(&self.rhapsody.skeleton, Anchor::Origin)?;
                let pos = self.rhapsody.sibling_position(&bucket, cursor)?;
                // Later root siblings read in stored order: push reversed.
                for kid in bucket.suffix(pos).rev() {
                    self.stack.push(Frame::Visit(kid));
                }
            }
            Anchor::After(parent) => {
                // The resume point was verified placed, so its anchor chain
                // runs through woven dots and this crossing never refuses;
                // `ok()?` keeps the walk total anyway (ruling R-91).
                self.climb = Some(Dot::try_from(parent).ok()?);
                let bucket = self
                    .rhapsody
                    .children
                    .bucket(&self.rhapsody.skeleton, Anchor::After(parent))?;
                let pos = self.rhapsody.sibling_position(&bucket, cursor)?;
                // The parent's own emit preceded its After bucket, so only
                // the later siblings remain at this level.
                for kid in bucket.suffix(pos).rev() {
                    self.stack.push(Frame::Visit(kid));
                }
            }
            Anchor::Before(parent) => {
                let parent_dot = Dot::try_from(parent).ok()?;
                self.climb = Some(parent_dot);
                // Reading order at this level: the before-siblings below the
                // cursor (stored order REVERSED), then the parent's emit,
                // then its After bucket in stored order. Push it reversed.
                for kid in self
                    .rhapsody
                    .children
                    .iter(&self.rhapsody.skeleton, Anchor::After(parent))
                    .rev()
                {
                    self.stack.push(Frame::Visit(kid));
                }
                self.stack.push(Frame::Emit(parent_dot));
                let bucket = self
                    .rhapsody
                    .children
                    .bucket(&self.rhapsody.skeleton, Anchor::Before(parent))?;
                let pos = self.rhapsody.sibling_position(&bucket, cursor)?;
                for kid in bucket.prefix(pos) {
                    self.stack.push(Frame::Visit(kid));
                }
            }
        }
        Some(())
    }
}

impl OrderWalk<'_> {
    /// Steps to the next skeleton *slot* in walk order, live or order
    /// tombstone, returning the dot and its visibility: the slot-level read
    /// the boundary scan ([`Rhapsody::extent`]) drives, where the public
    /// iterator yields only what is visible.
    ///
    /// One walk serves both reads: [`Iterator::next`] is exactly this loop
    /// with the invisible slots filtered, so the two cannot drift.
    pub(super) fn next_slot(&mut self) -> Option<(Dot, bool)> {
        loop {
            // The same schedule order() always ran: pushes are LIFO, so to
            // read a node's Before-subtrees, then itself, then its
            // After-subtrees, each Visit pushes them in the reverse of that
            // reading order.
            while let Some(frame) = self.stack.pop() {
                match frame {
                    Frame::Emit(dot) => {
                        return Some((dot, self.rhapsody.visible.contains(dot)));
                    }
                    Frame::Visit(dot) => {
                        // After-kids: read in stored order, so push reversed.
                        for kid in self
                            .rhapsody
                            .children
                            .iter(&self.rhapsody.skeleton, Anchor::After(dot.into()))
                            .rev()
                        {
                            self.stack.push(Frame::Visit(kid));
                        }
                        self.stack.push(Frame::Emit(dot));
                        // Before-kids: read in stored order REVERSED (rank
                        // ascending, newest adjacent), so push forward.
                        for kid in self
                            .rhapsody
                            .children
                            .iter(&self.rhapsody.skeleton, Anchor::Before(dot.into()))
                        {
                            self.stack.push(Frame::Visit(kid));
                        }
                    }
                }
            }
            // This level's frames are dry: schedule the next climb level, or
            // finish when the climb is exhausted too.
            self.climb_one_level()?;
        }
    }
}

impl Iterator for OrderWalk<'_> {
    type Item = Dot;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let (dot, visible) = self.next_slot()?;
            if visible {
                return Some(dot);
            }
        }
    }
}

impl core::iter::FusedIterator for OrderWalk<'_> {}

/// The reverse lazy walk (arc 11 phase three, S200): the visible dots in
/// REVERSE document order.
///
/// The scroll-up direction the forward walk cannot serve: its stack
/// schedules forward only, so a backward viewport cost a whole `order()`
/// pass before this read existed.
///
/// Obtained from [`order_walk_rev`](Rhapsody::order_walk_rev) (from the
/// document end) or [`order_walk_rev_before`](Rhapsody::order_walk_rev_before)
/// (from a placed element's slot, exclusive). Each step is one `O(log)`
/// descent of the order thread's aggregates, so a `k`-element backward window
/// costs `O(k log n)`, never the document. The iterator is exact-size and
/// fused. It borrows the store, so mutation under a live walk is a borrow
/// error here exactly as it is forward.
#[derive(Clone, Debug)]
pub struct OrderWalkRev<'a> {
    /// The store being walked; steps read the order thread.
    rhapsody: &'a Rhapsody,
    /// Visible offsets still to yield: the next step yields offset
    /// `remaining - 1`.
    remaining: usize,
}

impl Iterator for OrderWalkRev<'_> {
    type Item = Dot;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            return None;
        }
        self.remaining -= 1;
        self.rhapsody.order_at(self.remaining)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

impl ExactSizeIterator for OrderWalkRev<'_> {}
impl core::iter::FusedIterator for OrderWalkRev<'_> {}

impl Rhapsody {
    /// Document order: the visible dots, in the sequence order the skeleton
    /// defines.
    ///
    /// An in-order traversal from the origin, emitting per node its
    /// [`Before`](Anchor::Before) subtrees, the node, then its
    /// [`After`](Anchor::After) subtrees.
    ///
    /// Within a bucket the sibling order is rank descending, dot ascending on
    /// ties: after-buckets read stored order, before-buckets read it
    /// reversed. The mirror is deliberate, so both sides obey one law --- a
    /// rank above every incumbent lands the element adjacent to its anchor.
    /// That gives insert-before the same subtree isolation insert-after has,
    /// so a backward run stays a contiguous block instead of interleaving
    /// with a concurrent one.
    ///
    /// Yields *visible* dots only, but descends through invisible skeleton,
    /// since an order tombstone still anchors its descendants. An element
    /// whose anchor is not in the skeleton is unreachable and not yielded ---
    /// a dangling delta awaiting repair.
    ///
    /// # Shape and cost
    ///
    /// `O(n)`: each dot gets one visit and one emit. Descent follows child
    /// edges and a dot has exactly one locus, so no cycle is enterable from
    /// the origin and a crafted mutual-anchor pair is simply unreachable.
    ///
    /// The traversal is iterative over an explicit stack, never recursive,
    /// because skeleton depth is attacker-controllable: a chain of a million
    /// single-child anchors would blow a recursive stack. The per-anchor child
    /// index is maintained rather than rebuilt, so this read walks
    /// already-sorted buckets and the `O(n log n)` sort has been paid
    /// incrementally by the mutations.
    ///
    /// Collecting the whole order is the honest contract for a whole-document
    /// consumer; a windowed one takes [`order_walk`](Self::order_walk) or
    /// [`order_walk_after`](Self::order_walk_after) and pays only for the
    /// window.
    #[must_use]
    pub fn order(&self) -> Vec<Dot> {
        self.order_walk().collect()
    }

    /// The lazy in-order walk from the document start: yields exactly what
    /// [`order()`](Self::order) collects, one visible dot at a time.
    ///
    /// The windowed entry for a front-of-document view: `order_walk().take(k)`
    /// reads the first `k` visible elements without allocating the document
    /// order. To resume mid-document, see
    /// [`order_walk_after`](Self::order_walk_after); for shape and cost, see
    /// [`OrderWalk`].
    #[must_use]
    pub fn order_walk(&self) -> OrderWalk<'_> {
        // Seed from the origin bucket, stored (rank-descending) order reversed
        // so the head pops (and reads) first. An anchor with no bucket has no
        // children, so a dangling delta's descendants stay unreachable.
        let mut stack: Vec<Frame> = Vec::new();
        for root in self.children.iter(&self.skeleton, Anchor::Origin).rev() {
            stack.push(Frame::Visit(root));
        }
        OrderWalk {
            rhapsody: self,
            stack,
            climb: None,
        }
    }

    /// A dot's position in a sibling bucket, by binary search under the
    /// stored sibling order: `O(log bucket)` however wide a concurrent-heavy
    /// anchor has grown it, `O(1)` on the chain-child singleton.
    ///
    /// `None` when the dot is absent, which the maintained-index invariant
    /// makes unreachable for a woven dot in its own anchor's bucket.
    pub(super) fn sibling_position(&self, bucket: &Bucket<'_>, dot: Dot) -> Option<usize> {
        match bucket {
            Bucket::Explicit(bucket) => {
                let pos = bucket
                    .partition_point(|&other| sibling_cmp(&self.skeleton, other, dot).is_lt());
                (bucket.get(pos) == Some(&dot)).then_some(pos)
            }
            Bucket::Implicit(child) => (*child == dot).then_some(0),
        }
    }

    /// The in-order walk resumed immediately after the placed element
    /// `dot`: exactly [`order()`](Self::order)'s suffix past that
    /// element's slot.
    ///
    /// The windowed read. An editor resumes at the element its viewport
    /// starts on and takes the next `k`, paying `O(resume + window)` rather
    /// than the whole document.
    ///
    /// The resume point may be live or an order tombstone --- a tombstone
    /// still holds a slot in the skeleton walk --- so a viewport anchor
    /// deleted concurrently still resumes correctly.
    ///
    /// `None` when the element has no place in the current order, so no
    /// suffix exists: a dot never woven here, or one whose anchor chain
    /// does not reach the origin. Fabricating an empty walk
    /// would let a dangling delta read as "at the document end".
    ///
    /// # Shape and cost
    ///
    /// The resume is `O(log n)`: the placement verdict reads the maintained
    /// placement set, and the initial frames are the element's own After
    /// bucket. Levels above it are scheduled *lazily* by [`OrderWalk`]'s
    /// climb, one per level as the frames below run dry. Eager
    /// reconstruction would be `O(depth)`, and a forward-typed chain is as
    /// deep as the document --- handing back with one hand what the windowed
    /// read took with the other. Iterative both up and down.
    #[must_use]
    pub fn order_walk_after(&self, dot: Dot) -> Option<OrderWalk<'_>> {
        let start = dot;
        if !self.skeleton.contains(start) || self.unplaced.contains(&start) {
            return None;
        }
        // At the moment order()'s walk has just emitted (or skipped, for a
        // tombstone) this element, the nearest pending frames are the
        // element's own After-subtrees; everything above them is the climb's,
        // scheduled lazily per level.
        let mut stack: Vec<Frame> = Vec::new();
        for kid in self
            .children
            .iter(&self.skeleton, Anchor::After(start.into()))
            .rev()
        {
            stack.push(Frame::Visit(kid));
        }
        Some(OrderWalk {
            rhapsody: self,
            stack,
            climb: Some(start),
        })
    }

    /// The [`Anchor`] that places a fresh top-rank element immediately after the
    /// visible element the caret sits on (`after`; `None` at the document
    /// start).
    ///
    /// The Fugue placement rule (S127; the rhapsody-anchoring foundations note).
    /// The caller's caret sits immediately after visible element `after`:
    ///
    /// 1. `base` is [`After(a)`](Anchor::After) when `after == Some(a)`, else
    ///    [`Origin`](Anchor::Origin).
    /// 2. If the `base` bucket is empty (no skeleton child, tombstones included),
    ///    return `base`: a top rank there lands the element right after the caret.
    /// 3. Otherwise the in-order successor `s` of the caret slot already lives in
    ///    that subtree region, so the element must hang [`Before(s)`](Anchor::Before)
    ///    to read between the caret and `s`. `s` is found by descending: start at
    ///    the `base` bucket's traversal-first element (its stored head, the max
    ///    rank), then while that element has a nonempty Before bucket, step to
    ///    that bucket's traversal-first element (its stored LAST, the min rank,
    ///    since Before buckets traverse reversed). Return `Before(s)`.
    ///
    /// The descent is an iterative loop bounded by skeleton size (child edges, and
    /// a dot has one parent, so no cycle is enterable). Choosing `Before(s)` over
    /// a top-rank `After(a)` is the whole slice: both place correctly today, but
    /// only the Fugue choice groups a backward run into its own subtree, so two
    /// concurrent backward runs cannot interleave. This is Fugue-level, not
    /// FugueMax-level: concurrent forward-and-backward insertion at one gap can
    /// still interleave at the seam corner Fugue's own paper concedes (PRD 0018).
    ///
    /// # Invariant
    ///
    /// For the returned anchor and any rank above its current bucket, the
    /// woven element sorts adjacent to that anchor, so
    /// [`order()`](Self::order) yields it exactly at the caret slot.
    ///
    /// The rank half is the caller's, and it is the half a naive
    /// "anchor to the left neighbour" editor skips: a fresh mint does *not*
    /// automatically outrank a sibling a concurrent peer wove earlier in
    /// physical time. Read the incumbent ranks off
    /// [`children_of`](Self::children_of) and mint above them.
    #[must_use]
    pub fn anchor_for_visual_insert(&self, after: Option<RawDot>) -> Anchor {
        let base = after.map_or(Anchor::Origin, Anchor::After);
        // An empty base bucket has the caret slot free: a top rank there reads
        // right after the caret (or first, at the origin).
        let Some(head) = self
            .children
            .bucket(&self.skeleton, base)
            .map(|b| b.first())
        else {
            return base;
        };
        // The base bucket is nonempty, so the caret's in-order successor lives in
        // this subtree region. Descend to it: the successor is the deepest
        // traversal-first element down the Before chain, so the fresh element
        // hangs Before it and reads between the caret and the successor.
        // Before buckets traverse reversed, so the traversal-first element is
        // the stored LAST.
        let mut successor = head;
        while let Some(next) = self
            .children
            .bucket(&self.skeleton, Anchor::Before(successor.into()))
            .map(|bucket| bucket.last())
        {
            successor = next;
        }
        Anchor::Before(successor.into())
    }

    /// The skeleton children of `anchor` in STORED order: rank DESCENDING, dot
    /// ascending on ties (PRD 0017 R4), for BOTH sides.
    ///
    /// Reads the maintained child index, so reaching the bucket is `O(1)` and
    /// no document walk is needed. Mirrors the skeleton rather than
    /// visibility, yielding tombstones too, which is what the placement rule
    /// needs: a tombstone still occupies its sibling slot, so it still sets
    /// the rank a new sibling must beat.
    ///
    /// The head is always the highest-ranked current child --- the rank to
    /// beat, on both sides. Minting above it lands the element adjacent to
    /// the anchor in [`order()`](Self::order): directly, for an
    /// [`After`](Anchor::After) bucket whose stored order is the read order,
    /// and equally for a [`Before`](Anchor::Before) bucket, which reads
    /// reversed so the stored head still lands right before the anchor.
    pub fn children_of(&self, anchor: Anchor) -> impl Iterator<Item = Dot> + '_ {
        self.children.iter(&self.skeleton, anchor)
    }

    /// The reverse lazy walk from the document end: what
    /// [`order()`](Self::order) collects, backward, one visible dot at a
    /// time. `order_walk_rev().take(k)` reads the last `k` visible elements
    /// without allocating the order; see [`OrderWalkRev`] for cost.
    #[must_use]
    pub fn order_walk_rev(&self) -> OrderWalkRev<'_> {
        OrderWalkRev {
            rhapsody: self,
            remaining: self.thread.visible_len(),
        }
    }

    /// The reverse walk resumed immediately before the placed element `dot`.
    /// It yields the visible dots strictly before that element's slot, in
    /// reverse document order: exactly the reversed prefix of
    /// [`order()`](Self::order) up to that slot. This is the scroll-up mirror
    /// of [`order_walk_after`](Self::order_walk_after). A tombstone resume
    /// point holds its slot here exactly as it does forward.
    ///
    /// Returns `None` when the element has no place in the current document
    /// order: a dot never woven, or a dangling delta before its repair. This
    /// is the same [`is_reachable`](Self::is_reachable) boundary the forward
    /// resume refuses on. The reason is also the same: fabricating "at the
    /// document start" for an out-of-order delta would misplace it.
    #[must_use]
    pub fn order_walk_rev_before(&self, dot: Dot) -> Option<OrderWalkRev<'_>> {
        self.thread
            .position_of(dot)
            .map(|(_, visible_before)| OrderWalkRev {
                rhapsody: self,
                remaining: visible_before,
            })
    }

    /// Whether `dot`'s anchor chain reaches the origin through loci
    /// present in the skeleton: the dangling-weave diagnostic.
    ///
    /// Reachable iff [`order()`](Self::order)'s walk from the origin descends
    /// through it, visible or not --- an order tombstone on a live chain
    /// counts. Unreachable iff its anchor chain hits a dot with no locus
    /// here, which is a dangling delta whose anchor has not yet merged, and
    /// it stays so until the repair merge weaves that anchor.
    ///
    /// The point is to tell an out-of-order delta from a placed element, so a
    /// caller can hold it back from display without rebuilding the document
    /// order. Two set lookups, `O(log n)`, against the maintained placement
    /// set: the chain walk happens once per dangling episode on the write
    /// path, never per read. A crafted mutual-anchor cycle is never reached
    /// from the origin, so it is marked unplaced and no walk needs a cycle
    /// guard.
    ///
    /// `false` for a dot never woven here.
    #[must_use]
    pub fn is_reachable(&self, dot: Dot) -> bool {
        self.skeleton.contains(dot) && !self.unplaced.contains(&dot)
    }
}