minerva 0.2.0

//! The canonical [`RefoundMap`] wire frame (S278, ruling R-60): the
//! rename-map commitment the lineage recipe needs at every epoch boundary.
//!
//! The S275 state-identity intake recorded the gap this codec closes: no
//! published system commits the old-to-new identity map across a
//! history-destroying compaction cut as a first-class object, yet a
//! consumer's payload re-keys through exactly that map, so two replicas
//! agreeing on successor bytes while disagreeing on the map would silently
//! misassociate payload with the wrong elements, and nothing could audit
//! the difference. The frame makes the map's bytes canonical, so a lineage
//! node can bind a rename digest over real bytes (the S274 joint table
//! owns the digest and preimage composition; this codec owns only the
//! bytes, the R-8 division).
//!
//! The spelling is the map's own structure, which the re-mint core proves
//! (`refound/pure.rs`): station `s`'s survivors compact onto exactly
//! `(s, 1..=n_s)`, station preserved. So a row carries the station once
//! and the new dots never at all: entry position *is* the new index (the
//! `k`-th entry of a row, one-based, names the old index that compacts
//! onto `(s, k)`), and a cross-station rename is unrepresentable rather
//! than checked. Entry order is therefore semantic, not convention: two
//! frames with the same entries in different positions are different maps,
//! both canonical.

extern crate alloc;

use alloc::collections::BTreeMap;
use alloc::vec::Vec;
use core::num::NonZeroU64;

use crate::metis::VersionVector;

use super::super::placement::Dot;
use super::RefoundMap;

mod error;

pub use error::{RefoundMapDecodeBudget, RefoundMapDecodeError};

/// Version tag for the canonical [`RefoundMap`] wire encoding (S278,
/// ruling R-60). A distinct version space from every sibling frame (the
/// rhapsody pair, the have-set, the metatheses record, the epoch ledger,
/// the `VersionVector`, the `Kairos` stamp): the frames evolve
/// independently. Private, exactly as the sibling tags are: the tag is an
/// implementation detail of this codec, and a test that pins it reads the
/// leading byte of an encoded frame.
const REFOUND_MAP_WIRE_V1: u8 = 0x01;

/// Frame header: one version byte plus a `u64` big-endian station-row
/// count. The width covers every constructible map, so encoding is total
/// and the canonical bijection unconditional (a saturating count would
/// emit a frame its own decoder refuses, the R-56 elenchus lesson).
const REFOUND_MAP_WIRE_HEADER_LEN: usize = 9;

/// The fixed prefix of one station row before its variable entry run: a
/// `u32` station, a `u64` cut ceiling, and a `u64` live-entry count.
/// `O(1)`-checkable before any entry is read, and the whole of a
/// zero-survivor row, so it is also the per-row minimum length.
const REFOUND_MAP_WIRE_ROW_PREFIX_LEN: usize = 20;

/// The width of one translation entry on the wire: the `u64` old-epoch
/// index whose new index is its one-based position in the row.
const REFOUND_MAP_WIRE_ENTRY_LEN: usize = 8;

impl RefoundMap {
    /// Encodes this rename map as its canonical version-1 wire frame
    /// (S278): version byte, `u64` station-row count, then one row per
    /// ceiling station in strictly ascending station order (`u32` station,
    /// `u64` cut ceiling, `u64` live count `n`, then `n` `u64` old-epoch
    /// indices whose one-based position is the new index they compact
    /// onto). Big-endian throughout (ruling R-58). Infallible and total:
    /// the count fields' widths cover every constructible map, so no value
    /// encodes to a frame its own decoder refuses. The only allocations
    /// are the frame and one per-station image buffer.
    ///
    /// The row set is the ceilings' station set: a fully swept station
    /// (every identity dead at the cut) rides as a zero-count row, because
    /// its ceiling still bounds the affine window and dropping it would
    /// change [`translate`](Self::translate). Equal maps encode to
    /// identical bytes and distinct maps to distinct bytes, so the frame
    /// is a sound digest preimage (the canonical bijection the S274
    /// lineage recipe requires).
    ///
    /// # Byte identity is a versioned contract, not an evolving format
    ///
    /// Every accepted frame re-encodes to its own bytes; every value has
    /// one encoding. A future need is a sibling codec under a new version
    /// byte, never an in-place evolution (R-8).
    #[must_use]
    pub fn to_bytes(&self) -> Vec<u8> {
        let count = self.ceilings.iter().count();
        let mut out = Vec::with_capacity(
            REFOUND_MAP_WIRE_HEADER_LEN
                + count * REFOUND_MAP_WIRE_ROW_PREFIX_LEN
                + self.live_len() * REFOUND_MAP_WIRE_ENTRY_LEN,
        );
        out.push(REFOUND_MAP_WIRE_V1);
        out.extend_from_slice(&(count as u64).to_be_bytes());

        let mut entries_emitted: usize = 0;
        for (station, ceiling) in &self.ceilings {
            // The row's images, keyed by the new index they compact onto:
            // the map stores old-to-new, the row spells new-to-old by
            // position, so the range inverts through one sort.
            // Counter one is the least identity, so the one-based bounds
            // select exactly the rows the zero-based tuple bounds did:
            // counter zero was never a key (ruling R-91).
            let mut images: Vec<(u64, u64)> = self
                .compacted
                .range(Dot::new(station, NonZeroU64::MIN)..=Dot::new(station, NonZeroU64::MAX))
                .map(|(old, new)| {
                    debug_assert_eq!(new.station(), station, "the re-mint preserves the station");
                    (new.counter(), old.counter())
                })
                .collect();
            images.sort_unstable();
            debug_assert!(
                images
                    .iter()
                    .enumerate()
                    .all(|(position, &(new, _))| new == position as u64 + 1),
                "station {station}'s new indices are exactly 1..=n (the proven compaction image)"
            );
            debug_assert_eq!(images.len() as u64, self.live_of(station));

            out.extend_from_slice(&station.to_be_bytes());
            out.extend_from_slice(&ceiling.to_be_bytes());
            out.extend_from_slice(&(images.len() as u64).to_be_bytes());
            for &(_, old) in &images {
                out.extend_from_slice(&old.to_be_bytes());
            }
            entries_emitted += images.len();
        }
        debug_assert_eq!(
            entries_emitted,
            self.live_len(),
            "every compacted station sits inside the ceilings (the bound-cut invariant)"
        );
        out
    }

    /// Decodes exactly one canonical frame produced by
    /// [`to_bytes`](Self::to_bytes), and rejects trailing bytes. The
    /// input-length ceiling is the only bound: at least its fixed minimum of
    /// frame bytes backs every row, and its fixed width backs every entry. The
    /// input therefore already bounds allocation, and no separate policy is
    /// required. An embedding protocol that owns a stricter roster or entry
    /// policy states it through
    /// [`from_bytes_with_budget`](Self::from_bytes_with_budget).
    ///
    /// # Errors
    ///
    /// The variants of
    /// [`from_bytes_with_budget`](Self::from_bytes_with_budget), except
    /// [`RefoundMapDecodeError::TooManyStations`] and
    /// [`RefoundMapDecodeError::TooManyEntries`]: this door states no
    /// budget, so a count the bytes cannot back refuses as
    /// [`UnexpectedLength`](RefoundMapDecodeError::UnexpectedLength) at
    /// its first unbacked row or entry run, in `O(1)`.
    /// Never panics on adversarial input.
    pub fn from_bytes(bytes: &[u8]) -> Result<Self, RefoundMapDecodeError> {
        Self::decode(bytes, None)
    }

    /// Decodes exactly one canonical frame under caller-owned station and
    /// entry budgets (the embedding door: a protocol that caps its roster
    /// or its document size states the caps in the frame's own units).
    ///
    /// Decode refuses any frame the encoder could not produce, so accepted
    /// frames re-encode bit for bit (the canonical bijection). Canonical
    /// form: rows strictly ascending by station, no zero ceiling, the live
    /// count at most the ceiling, every old index inside the compacted
    /// domain `1..=ceiling`, and no old index named twice within a row.
    /// Entry *order* is deliberately not constrained beyond position: it
    /// carries the walk-order permutation, which is the map's semantic
    /// content, so distinct orders are distinct values, both canonical.
    ///
    /// Allocation is bounded before any row work. The decoder checks the
    /// declared station count against the input length and the caller's budget
    /// up front. Every row then checks its declared entry run against the
    /// remaining length and the cumulative entry budget. A frame whose
    /// declared counts its bytes cannot back refuses in `O(1)`, against the
    /// buffer it cannot fill.
    ///
    /// # Errors
    ///
    /// [`RefoundMapDecodeError::UnknownVersion`] for an unrecognized
    /// version byte; [`RefoundMapDecodeError::TooManyStations`] and
    /// [`RefoundMapDecodeError::TooManyEntries`] for declared counts past
    /// the budget; [`RefoundMapDecodeError::UnexpectedLength`] if the
    /// input is shorter than the declared counts require, or carries
    /// trailing bytes;
    /// [`RefoundMapDecodeError::NonAscendingStations`],
    /// [`RefoundMapDecodeError::ZeroCeiling`],
    /// [`RefoundMapDecodeError::LiveExceedsCeiling`],
    /// [`RefoundMapDecodeError::IndexOutOfRange`], and
    /// [`RefoundMapDecodeError::DuplicateIndex`] for the canonical-form
    /// violations. Never panics on adversarial input.
    pub fn from_bytes_with_budget(
        bytes: &[u8],
        budget: RefoundMapDecodeBudget,
    ) -> Result<Self, RefoundMapDecodeError> {
        Self::decode(bytes, Some(budget))
    }

    /// The one decode core behind both doors: the caller's budget when one
    /// was stated, otherwise the input length alone bounds the work (each
    /// row and entry read checks the remaining bytes against its fixed
    /// width, so declared counts the buffer cannot back refuse at their
    /// first unbacked read, in `O(1)`).
    fn decode(
        bytes: &[u8],
        budget: Option<RefoundMapDecodeBudget>,
    ) -> Result<Self, RefoundMapDecodeError> {
        let header: [u8; REFOUND_MAP_WIRE_HEADER_LEN] = bytes
            .get(..REFOUND_MAP_WIRE_HEADER_LEN)
            .and_then(|h| h.try_into().ok())
            .ok_or(RefoundMapDecodeError::UnexpectedLength {
                expected: REFOUND_MAP_WIRE_HEADER_LEN,
                found: bytes.len(),
            })?;
        let [version, c0, c1, c2, c3, c4, c5, c6, c7] = header;
        if version != REFOUND_MAP_WIRE_V1 {
            return Err(RefoundMapDecodeError::UnknownVersion(version));
        }
        let count = u64::from_be_bytes([c0, c1, c2, c3, c4, c5, c6, c7]);
        // Refuse a station count past the caller's licence before any row
        // work; the per-row length checks below keep allocation bounded by
        // the input regardless.
        if let Some(budget) = budget
            && count > budget.max_stations() as u64
        {
            return Err(RefoundMapDecodeError::TooManyStations {
                count,
                budget: budget.max_stations() as u64,
            });
        }
        // Refuse a count the body cannot back before decoding a single
        // row: every row costs at least the fixed prefix, so this one
        // division is the promised `O(1)` rejection.
        let body = bytes.len() - REFOUND_MAP_WIRE_HEADER_LEN;
        if count > (body / REFOUND_MAP_WIRE_ROW_PREFIX_LEN) as u64 {
            let expected = count
                .saturating_mul(REFOUND_MAP_WIRE_ROW_PREFIX_LEN as u64)
                .saturating_add(REFOUND_MAP_WIRE_HEADER_LEN as u64);
            return Err(RefoundMapDecodeError::UnexpectedLength {
                expected: usize::try_from(expected).unwrap_or(usize::MAX),
                found: bytes.len(),
            });
        }

        // A cursor over the frame body. `rest` always points at the
        // unconsumed suffix, and every read first checks the remaining
        // length, so allocation and iteration are bounded by
        // `bytes.len()`, never by a declared count.
        let mut rest = &bytes[REFOUND_MAP_WIRE_HEADER_LEN..];
        let mut compacted: BTreeMap<Dot, Dot> = BTreeMap::new();
        let mut ceilings = VersionVector::new();
        let mut live: BTreeMap<u32, u64> = BTreeMap::new();
        let mut previous_station: Option<u32> = None;
        let mut entries_declared: u64 = 0;

        for _ in 0..count {
            let (station, ceiling, declared_live, tail) = decode_row(
                bytes,
                rest,
                previous_station,
                budget,
                &mut entries_declared,
                &mut compacted,
            )?;
            rest = tail;
            previous_station = Some(station);
            ceilings.observe(station, ceiling);
            if declared_live > 0 {
                let _ = live.insert(station, declared_live);
            }
        }

        if rest.is_empty() {
            Ok(Self {
                compacted,
                ceilings,
                live,
            })
        } else {
            // The consumed prefix is the exact frame the counts described.
            Err(RefoundMapDecodeError::UnexpectedLength {
                expected: bytes.len() - rest.len(),
                found: bytes.len(),
            })
        }
    }
}

/// One decoded station row: its station, ceiling, and live count, plus the
/// unconsumed tail.
type DecodedRow<'a> = (u32, u64, u64, &'a [u8]);

/// Decodes one station row off the front of `rest`, folding its
/// translation entries into `compacted` and returning the row's station,
/// ceiling, live count, and the unconsumed tail. Length-checks the fixed
/// prefix (against the per-row minimum, so a large count cannot force an
/// unbacked read), validates the canonical form (ascending station, the
/// nonzero ceiling, the tally bound, the compacted domain, within-row
/// distinctness), charges the caller's cumulative entry licence before any
/// entry is materialized, and refuses an entry run the remaining bytes
/// cannot back in `O(1)`; each read is a total, panic-free slice
/// conversion.
fn decode_row<'a>(
    bytes: &[u8],
    rest: &'a [u8],
    previous_station: Option<u32>,
    budget: Option<RefoundMapDecodeBudget>,
    entries_declared: &mut u64,
    compacted: &mut BTreeMap<Dot, Dot>,
) -> Result<DecodedRow<'a>, RefoundMapDecodeError> {
    let prefix: [u8; REFOUND_MAP_WIRE_ROW_PREFIX_LEN] = rest
        .get(..REFOUND_MAP_WIRE_ROW_PREFIX_LEN)
        .and_then(|p| p.try_into().ok())
        .ok_or(RefoundMapDecodeError::UnexpectedLength {
            // The bytes consumed so far plus one whole minimal row is a
            // sound lower bound on the frame the count requires.
            expected: bytes.len() - rest.len() + REFOUND_MAP_WIRE_ROW_PREFIX_LEN,
            found: bytes.len(),
        })?;
    let [
        s0,
        s1,
        s2,
        s3,
        h0,
        h1,
        h2,
        h3,
        h4,
        h5,
        h6,
        h7,
        n0,
        n1,
        n2,
        n3,
        n4,
        n5,
        n6,
        n7,
    ] = prefix;
    let station = u32::from_be_bytes([s0, s1, s2, s3]);
    let ceiling = u64::from_be_bytes([h0, h1, h2, h3, h4, h5, h6, h7]);
    let declared_live = u64::from_be_bytes([n0, n1, n2, n3, n4, n5, n6, n7]);
    let rest = &rest[REFOUND_MAP_WIRE_ROW_PREFIX_LEN..];

    // Ascending first: it is what makes cross-row collisions in
    // `compacted` impossible, so the duplicate refusal below can name the
    // within-row shape precisely.
    if let Some(previous) = previous_station
        && station <= previous
    {
        return Err(RefoundMapDecodeError::NonAscendingStations {
            previous,
            found: station,
        });
    }
    if ceiling == 0 {
        return Err(RefoundMapDecodeError::ZeroCeiling { station });
    }
    if declared_live > ceiling {
        return Err(RefoundMapDecodeError::LiveExceedsCeiling {
            station,
            live: declared_live,
            ceiling,
        });
    }
    // The cumulative entry licence, charged before this row's entries are
    // materialized (the running sum is bounded by the input length once
    // rows are backed, but the saturation keeps the arithmetic total
    // regardless).
    *entries_declared = entries_declared.saturating_add(declared_live);
    if let Some(budget) = budget
        && *entries_declared > budget.max_entries() as u64
    {
        return Err(RefoundMapDecodeError::TooManyEntries {
            count: *entries_declared,
            budget: budget.max_entries() as u64,
        });
    }
    // Refuse an entry run the remaining bytes cannot back before reading
    // one entry: the `O(1)` division again.
    if declared_live > (rest.len() / REFOUND_MAP_WIRE_ENTRY_LEN) as u64 {
        let expected = declared_live
            .saturating_mul(REFOUND_MAP_WIRE_ENTRY_LEN as u64)
            .saturating_add((bytes.len() - rest.len()) as u64);
        return Err(RefoundMapDecodeError::UnexpectedLength {
            expected: usize::try_from(expected).unwrap_or(usize::MAX),
            found: bytes.len(),
        });
    }

    let rest = decode_entries(bytes, rest, station, ceiling, declared_live, compacted)?;

    Ok((station, ceiling, declared_live, rest))
}

/// Folds one row's translation entries into `compacted`, returning the
/// unconsumed tail. An entry's one-based position IS the new index it
/// compacts onto, so both identities are built only AFTER the range
/// refusal below and decode acceptance is byte-identical (ruling R-91).
/// Every read is a total, panic-free slice conversion; the caller already
/// proved the remaining bytes back the declared run.
fn decode_entries<'a>(
    bytes: &[u8],
    mut rest: &'a [u8],
    station: u32,
    ceiling: u64,
    declared_live: u64,
    compacted: &mut BTreeMap<Dot, Dot>,
) -> Result<&'a [u8], RefoundMapDecodeError> {
    for new_index in 1..=declared_live {
        let entry: [u8; REFOUND_MAP_WIRE_ENTRY_LEN] = rest
            .get(..REFOUND_MAP_WIRE_ENTRY_LEN)
            .and_then(|e| e.try_into().ok())
            .ok_or(RefoundMapDecodeError::UnexpectedLength {
                expected: bytes.len() - rest.len() + REFOUND_MAP_WIRE_ENTRY_LEN,
                found: bytes.len(),
            })?;
        rest = &rest[REFOUND_MAP_WIRE_ENTRY_LEN..];
        let old_index = u64::from_be_bytes(entry);
        // The one refusal, unchanged: the non-dot zero and anything past
        // the ceiling. `new_index` runs the one-based range, so both
        // crossings succeed exactly when the refusal does not fire.
        let (Some(old), Some(new)) = (
            NonZeroU64::new(old_index).filter(|_| old_index <= ceiling),
            NonZeroU64::new(new_index),
        ) else {
            return Err(RefoundMapDecodeError::IndexOutOfRange {
                station,
                index: old_index,
                ceiling,
            });
        };
        // Ascending stations make cross-row collisions impossible, so a
        // duplicate key here is exactly a within-row duplicate.
        if compacted
            .insert(Dot::new(station, old), Dot::new(station, new))
            .is_some()
        {
            return Err(RefoundMapDecodeError::DuplicateIndex {
                station,
                index: old_index,
            });
        }
    }
    Ok(rest)
}