minerva 0.2.0

//! A bounded prototype of the epoch commutation boundary.
//!
//! The production types deliberately stay untouched. This model retains the
//! Rhapsody rules that can decide the experiment: the full sided identity
//! anchor, rank-descending sibling order with a dot tie-break, the reversed
//! `Before` traversal, invisible order tombstones, walk-order re-chaining, and
//! metathesis replay in `(rank, testimony)` order with cycle refusal. Payload
//! labels survive identity reminting so the two boundary paths can compare the
//! same semantic read. In-flight movement ranks are retained, as in the scoped
//! identity/anchor translation map; remapping replay timestamps would be a
//! different boundary mechanism.
//!
//! The S213 half (the matrix and falsifier tests over [`cross_boundary`])
//! proved the annex-only shape cannot carry the exact law. The S215 half
//! models the shape PRD 0024 chose instead, the sealed-stratum shadow:
//! old-addressed window traffic is judged in the old epoch's own topology
//! (basis, retained movement record, and window set together), and only the
//! deterministic outcome crosses, projected through a dot map frozen at
//! declaration (live-at-cut compaction by walk order below, the affine shift
//! above). The [`shadow::Shadow`] is the maintained form owing exact agreement with
//! the eager recompute at every prefix of every causal arrival order
//! (requirement R4); the new-epoch locus encoding for outcomes is
//! deliberately out of model (a mechanism-slice representation decision,
//! requirement R3), so agreement is pinned at reading, decision, and
//! identity grade.

extern crate alloc;

mod annex;
mod shadow;

use alloc::collections::BTreeMap;
use alloc::vec::Vec;

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Epoch(u8);

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Dot {
    epoch: Epoch,
    index: u8,
}

impl Dot {
    const fn old(index: u8) -> Self {
        Self {
            epoch: Epoch(0),
            index,
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum Anchor {
    Origin,
    After(Dot),
    Before(Dot),
}

impl Anchor {
    const fn dot(self) -> Option<Dot> {
        match self {
            Self::Origin => None,
            Self::After(dot) | Self::Before(dot) => Some(dot),
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Locus {
    anchor: Anchor,
    rank: u8,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Node {
    label: char,
    locus: Locus,
    visible: bool,
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct State {
    epoch: Epoch,
    nodes: BTreeMap<Dot, Node>,
}

impl State {
    fn new() -> Self {
        Self {
            epoch: Epoch(0),
            nodes: BTreeMap::new(),
        }
    }

    fn insert(&mut self, dot: Dot, node: Node) {
        assert_eq!(dot.epoch, self.epoch);
        if let Some(anchor) = node.locus.anchor.dot() {
            assert_eq!(anchor.epoch, self.epoch);
        }
        assert!(self.nodes.insert(dot, node).is_none(), "one node per dot");
    }

    fn walk(&self) -> Vec<Dot> {
        enum Frame {
            Visit(Dot),
            Emit(Dot),
        }

        let mut children: BTreeMap<Anchor, Vec<Dot>> = BTreeMap::new();
        for (&dot, node) in &self.nodes {
            children.entry(node.locus.anchor).or_default().push(dot);
        }
        for siblings in children.values_mut() {
            siblings.sort_by(|a, b| {
                self.nodes[b]
                    .locus
                    .rank
                    .cmp(&self.nodes[a].locus.rank)
                    .then_with(|| a.cmp(b))
            });
        }

        let mut stack: Vec<Frame> = children
            .get(&Anchor::Origin)
            .into_iter()
            .flatten()
            .rev()
            .copied()
            .map(Frame::Visit)
            .collect();
        let mut order = Vec::with_capacity(self.nodes.len());
        while let Some(frame) = stack.pop() {
            match frame {
                Frame::Emit(dot) => order.push(dot),
                Frame::Visit(dot) => {
                    if let Some(descendants) = children.get(&Anchor::After(dot)) {
                        for &child in descendants.iter().rev() {
                            stack.push(Frame::Visit(child));
                        }
                    }
                    stack.push(Frame::Emit(dot));
                    if let Some(descendants) = children.get(&Anchor::Before(dot)) {
                        for &child in descendants {
                            stack.push(Frame::Visit(child));
                        }
                    }
                }
            }
        }
        order
    }

    fn reading(&self) -> Vec<char> {
        self.walk()
            .into_iter()
            .filter_map(|dot| {
                let node = self.nodes[&dot];
                node.visible.then_some(node.label)
            })
            .collect()
    }

    fn apply(&mut self, movement: Movement) -> Verdict {
        assert_eq!(movement.target.epoch, self.epoch);
        let Some(anchor) = movement.to.anchor.dot() else {
            self.nodes
                .get_mut(&movement.target)
                .expect("a movement target is live at the cut")
                .locus = movement.to;
            return Verdict::Applied;
        };
        assert_eq!(anchor.epoch, self.epoch);
        assert!(
            self.nodes.contains_key(&anchor),
            "translated anchor support"
        );

        let mut cursor = Some(anchor);
        let mut steps = 0usize;
        while let Some(dot) = cursor {
            if dot == movement.target {
                return Verdict::RefusedCycle;
            }
            steps += 1;
            assert!(
                steps <= self.nodes.len(),
                "the effective skeleton is acyclic"
            );
            cursor = self.nodes[&dot].locus.anchor.dot();
        }

        self.nodes
            .get_mut(&movement.target)
            .expect("a movement target is live at the cut")
            .locus = movement.to;
        Verdict::Applied
    }

    fn refound(&self, support: BoundarySupport) -> Refounded {
        let next_epoch = Epoch(self.epoch.0.checked_add(1).expect("bounded toy epoch"));
        let walk = self.walk();
        let live: Vec<Dot> = walk
            .iter()
            .copied()
            .filter(|dot| self.nodes[dot].visible)
            .collect();

        let mut dots = BTreeMap::new();
        for (offset, old) in live.iter().copied().enumerate() {
            let index = u8::try_from(offset + 1).expect("bounded toy state");
            let _ = dots.insert(
                old,
                Dot {
                    epoch: next_epoch,
                    index,
                },
            );
        }

        let mut state = Self {
            epoch: next_epoch,
            nodes: BTreeMap::new(),
        };
        let mut predecessor = None;
        for old in &live {
            let new = dots[old];
            let old_node = self.nodes[old];
            state.insert(
                new,
                Node {
                    label: old_node.label,
                    locus: Locus {
                        anchor: predecessor.map_or(Anchor::Origin, Anchor::After),
                        rank: 0,
                    },
                    visible: true,
                },
            );
            predecessor = Some(new);
        }

        let mut fallbacks = BTreeMap::new();
        let mut live_predecessor = None;
        for (offset, old) in walk.iter().enumerate() {
            if self.nodes[old].visible {
                live_predecessor = Some(dots[old]);
            } else {
                let live_successor = walk[offset + 1..]
                    .iter()
                    .find(|next| self.nodes[next].visible)
                    .map(|next| dots[next]);
                let before = live_predecessor.map_or_else(
                    || live_successor.map_or(Anchor::Origin, Anchor::Before),
                    Anchor::After,
                );
                let after = live_successor.map_or_else(
                    || live_predecessor.map_or(Anchor::Origin, Anchor::After),
                    Anchor::Before,
                );
                let _ = fallbacks.insert(*old, PositionalFallback { before, after });
            }
        }

        if support == BoundarySupport::TombstoneAnnex {
            for old in walk.iter().filter(|dot| !self.nodes[dot].visible) {
                let index = u8::try_from(dots.len() + 1).expect("bounded toy state");
                let _ = dots.insert(
                    *old,
                    Dot {
                        epoch: next_epoch,
                        index,
                    },
                );
            }
            for old in walk.iter().filter(|dot| !self.nodes[dot].visible) {
                let old_node = self.nodes[old];
                let translated_anchor = match old_node.locus.anchor {
                    Anchor::Origin => Anchor::Origin,
                    Anchor::After(parent) => Anchor::After(dots[&parent]),
                    Anchor::Before(parent) => Anchor::Before(dots[&parent]),
                };
                state.insert(
                    dots[old],
                    Node {
                        label: old_node.label,
                        locus: Locus {
                            anchor: translated_anchor,
                            rank: old_node.locus.rank,
                        },
                        visible: false,
                    },
                );
            }
        }

        Refounded {
            state,
            translation: Translation {
                support,
                dots,
                fallbacks,
            },
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Movement {
    testimony: Testimony,
    target: Dot,
    to: Locus,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Testimony(u8);

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Verdict {
    Applied,
    RefusedCycle,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum BoundarySupport {
    PositionOnly,
    TombstoneAnnex,
}

#[derive(Clone, Debug)]
struct Translation {
    support: BoundarySupport,
    dots: BTreeMap<Dot, Dot>,
    fallbacks: BTreeMap<Dot, PositionalFallback>,
}

#[derive(Clone, Copy, Debug)]
struct PositionalFallback {
    before: Anchor,
    after: Anchor,
}

impl Translation {
    fn movement(&self, movement: Movement) -> Movement {
        let target = self.dots[&movement.target];
        let anchor = match movement.to.anchor {
            Anchor::Origin => Anchor::Origin,
            Anchor::After(old) => self.dots.get(&old).copied().map_or_else(
                || {
                    assert_eq!(self.support, BoundarySupport::PositionOnly);
                    self.fallbacks[&old].after
                },
                Anchor::After,
            ),
            Anchor::Before(old) => self.dots.get(&old).copied().map_or_else(
                || {
                    assert_eq!(self.support, BoundarySupport::PositionOnly);
                    self.fallbacks[&old].before
                },
                Anchor::Before,
            ),
        };
        Movement {
            testimony: movement.testimony,
            target,
            to: Locus {
                anchor,
                rank: movement.to.rank,
            },
        }
    }
}

#[derive(Clone, Debug)]
struct Refounded {
    state: State,
    translation: Translation,
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct BoundaryResult {
    fold_then_refound: Vec<char>,
    refound_then_fold: Vec<char>,
    old_decisions: Vec<Decision>,
    translated_decisions: Vec<Decision>,
}

impl BoundaryResult {
    fn commutes(&self) -> bool {
        self.fold_then_refound == self.refound_then_fold
            && self.old_decisions == self.translated_decisions
    }
}

fn cross_boundary(
    state_at_cut: &State,
    movements: &[Movement],
    support: BoundarySupport,
) -> BoundaryResult {
    let mut folded = state_at_cut.clone();
    let old_decisions = replay(&mut folded, movements);
    let fold_then_refound = folded.refound(support).state.reading();

    let Refounded {
        mut state,
        translation,
    } = state_at_cut.refound(support);
    let translated: Vec<Movement> = movements
        .iter()
        .copied()
        .map(|movement| translation.movement(movement))
        .collect();
    let translated_decisions = replay(&mut state, &translated);
    let refound_then_fold = state.reading();

    BoundaryResult {
        fold_then_refound,
        refound_then_fold,
        old_decisions,
        translated_decisions,
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Decision {
    testimony: Testimony,
    verdict: Verdict,
}

fn replay(state: &mut State, movements: &[Movement]) -> Vec<Decision> {
    replay_order(movements)
        .into_iter()
        .map(|movement| Decision {
            testimony: movement.testimony,
            verdict: state.apply(movement),
        })
        .collect()
}

fn replay_order(movements: &[Movement]) -> Vec<Movement> {
    let mut ordered = movements.to_vec();
    ordered.sort_by_key(|movement| (movement.to.rank, movement.testimony));
    ordered
}

fn anchor_case(anchor_is_live: bool, ranks: [u8; 2]) -> (State, [Movement; 2]) {
    let mut state = State::new();
    let a = Dot::old(1);
    let anchor = Dot::old(2);
    let incumbent = Dot::old(3);
    let first_target = Dot::old(4);
    let second_target = Dot::old(5);
    state.insert(
        a,
        Node {
            label: 'a',
            locus: Locus {
                anchor: Anchor::Origin,
                rank: 3,
            },
            visible: true,
        },
    );
    state.insert(
        anchor,
        Node {
            label: 't',
            locus: Locus {
                anchor: Anchor::After(a),
                rank: 2,
            },
            visible: anchor_is_live,
        },
    );
    state.insert(
        incumbent,
        Node {
            label: 'b',
            locus: Locus {
                anchor: Anchor::After(a),
                rank: 1,
            },
            visible: true,
        },
    );
    state.insert(
        first_target,
        Node {
            label: 'x',
            locus: Locus {
                anchor: Anchor::Origin,
                rank: 0,
            },
            visible: true,
        },
    );
    state.insert(
        second_target,
        Node {
            label: 'y',
            locus: Locus {
                anchor: Anchor::Origin,
                rank: 0,
            },
            visible: true,
        },
    );
    (
        state,
        [
            Movement {
                testimony: Testimony(1),
                target: first_target,
                to: Locus {
                    anchor: Anchor::After(anchor),
                    rank: ranks[0],
                },
            },
            Movement {
                testimony: Testimony(2),
                target: second_target,
                to: Locus {
                    anchor: Anchor::After(anchor),
                    rank: ranks[1],
                },
            },
        ],
    )
}