minerva 0.2.0

extern crate alloc;

use alloc::collections::BTreeMap;

use super::DotSet;
use super::stability::UnknownStation;

mod retired;

pub use retired::Retired;

/// A cross-node *retirement* tracker: the meet of every roster member's applied
/// removals, the removal dual of [`Stability`](crate::metis::Stability).
///
/// Where [`Stability`](crate::metis::Stability) tracks how far each member has
/// *received* (a mint-side cut, the watermark below which every event is
/// delivered everywhere), this tracks which removed dots each member has
/// *applied*. A [`Rhapsody::condense`](crate::metis::Rhapsody::condense) may
/// excise an order tombstone only when its dot has been removed and applied at every
/// replica that will ever write again; over-claiming strands a laggard's future
/// anchor forever, the unrecoverable direction. The tracker computes the honest
/// claim, [`retired`](Self::retired): the dots *all* members have acknowledged.
///
/// # Mint evidence is the wrong witness
///
/// Removal deltas mint no dot, so "everyone has applied this deletion" is not
/// derivable from the crate's mint-based [`Cut`](crate::metis::Cut) or the
/// [`Stability`](crate::metis::Stability) watermark: those witness what has been
/// *seen*, not what has been *applied*. Application evidence only the deployment
/// can gather (an ack round, an app-level epoch, a quorum sweep) is the input
/// here, the same standing-claims posture as
/// [`Stability::report`](crate::metis::Stability::report)'s unverifiable cut
/// (PRD 0011 R8). The tracker turns per-member acknowledgements into the one
/// claim [`condense`](crate::metis::Rhapsody::condense) accepts, and nothing else
/// can build a [`Retired`] except the audited [`Retired::trust`] escape.
///
/// # The roster is the meaning
///
/// A meet is only as trustworthy as the family it ranges over, and the failure
/// direction is unrecoverable (forgetting a thread a laggard still anchors to
/// loses reachable text). So the roster is *fixed at construction* and
/// acknowledgements from stations off it are refused ([`UnknownStation`]):
/// admitting an unheralded member, or quietly meeting over "members heard from
/// so far", would widen or narrow the family mid-flight, and membership change
/// is the caller's policy, not this type's. A member that has never
/// acknowledged holds bottom (the empty applied-set) and pins
/// [`retired`](Self::retired) at bottom: nothing is safe to excise until
/// everyone vouches. Handling stragglers, joiners, and leavers means building a
/// new tracker over the new roster.
///
/// # Totality
///
/// [`acknowledge`](Self::acknowledge) folds by [`DotSet::merge`] (a join), so it
/// is idempotent, commutative, and monotone: duplicated, reordered, or stale
/// acknowledgements are absorbed and a member's applied-set never regresses,
/// which is exactly what licenses meeting them. A genuinely regressed member (a
/// peer restarted from scratch) is a membership event the caller handles by
/// rebuilding; the tracker will not un-vouch on its behalf.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Retirement {
    /// Per roster member, the join of every applied-removal set it has
    /// acknowledged; bottom (the empty [`DotSet`]) until the first
    /// acknowledgement.
    applied: BTreeMap<u32, DotSet>,
}

impl Retirement {
    /// Creates a tracker over a fixed roster of `station_id`s, every member at
    /// bottom (nothing acknowledged, nothing retired). Duplicate ids collapse.
    ///
    /// An empty roster is degenerate: see [`retired`](Self::retired) for why it
    /// answers bottom rather than the vacuous "everything is retired".
    #[must_use]
    pub fn new(roster: impl IntoIterator<Item = u32>) -> Self {
        Self {
            applied: roster
                .into_iter()
                .map(|station| (station, DotSet::new()))
                .collect(),
        }
    }

    /// Folds a roster member's acknowledged applied-removal set into its slot,
    /// by join: the member testifies it has applied the removal of these dots.
    ///
    /// Absorbing rather than replacing is what makes acknowledgement
    /// order-robust: a stale or duplicated acknowledgement (a gossip replay, a
    /// reordered channel) can never shrink a member's applied-set, so
    /// [`retired`](Self::retired) is monotone non-decreasing, which is exactly
    /// what licenses excising below it.
    ///
    /// # Errors
    ///
    /// Refuses a `station` that is not on the roster, returning
    /// [`UnknownStation`] and leaving the tracker unchanged: an unheralded
    /// member is a membership change, the caller's policy.
    pub fn acknowledge(&mut self, station: u32, applied: &DotSet) -> Result<(), UnknownStation> {
        let vouched = self
            .applied
            .get_mut(&station)
            .ok_or(UnknownStation { station })?;
        *vouched = vouched.merge(applied);
        Ok(())
    }

    /// The honest condense claim: the dots *every* roster member has
    /// acknowledged applying, the n-ary [`intersect`](DotSet::intersect) of the
    /// members' applied-sets.
    ///
    /// Monotone non-decreasing across [`acknowledge`](Self::acknowledge)s. Any
    /// member still at bottom pins the result at bottom: no dot is retired
    /// everywhere until every member has vouched for it.
    ///
    /// For an *empty* roster the mathematical meet is the lattice top: "every
    /// dot is retired", vacuously. That answer is a fabrication. It would
    /// license excising any tombstone, the maximally unsafe over-claim a
    /// safe-to-forget quantity must never invent. The degenerate answer is
    /// therefore bottom: nobody vouches for nothing (the meet-shaped-read μή
    /// rule: state the empty-family value). `O(roster x dots)`, computed on
    /// read.
    #[must_use]
    pub fn retired(&self) -> Retired {
        let mut vouched = self.applied.values();
        let Some(first) = vouched.next() else {
            return Retired::from_meet(DotSet::new());
        };
        Retired::from_meet(vouched.fold(first.clone(), |acc, applied| acc.intersect(applied)))
    }

    /// Iterates the roster's `(station_id, applied-set)` slots in ascending
    /// station order, un-acknowledged members at bottom.
    ///
    /// The observability read: the member pinning [`retired`](Self::retired)
    /// (the laggard a caller may want to page, or evict via a new roster) is
    /// visible here.
    pub fn acknowledged(&self) -> impl Iterator<Item = (u32, &DotSet)> {
        self.applied
            .iter()
            .map(|(&station, applied)| (station, applied))
    }
}