minerva 0.2.0

extern crate alloc;

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

use super::placement::Dot;
use super::{DotSet, Rhapsody};
use crate::metis::HaveSetDecodeBudget;

/// Version tag for the canonical [`Rhapsody`] wire encoding (PRD 0017 / S127). A
/// distinct version space from the `DotSet` have-set frame (PRD 0016), the
/// `VersionVector` frame (PRD 0007), and the `Kairos` stamp (PRD 0002): the four
/// frames evolve independently. Private, exactly as the have-set frame's
/// `HAVE_SET_WIRE_V1` is: the tag is an implementation detail of this codec, and a
/// test that pins it reads the leading byte of an encoded frame.
///
/// v2 (S127) widens the anchor tag to carry the Fugue side (origin, after,
/// before). v1 is RETIRED pre-adoption: the v1 frame never shipped, so a
/// v2-only decoder keeps the frame canonical (one store, one encoding) by
/// refusing v1 (`0x01`) as an unknown version rather than translating it.
const RHAPSODY_WIRE_V2: u8 = 0x02;

/// Frame header: one version byte plus a `u32` big-endian skeleton locus count.
const RHAPSODY_WIRE_HEADER_LEN: usize = 5;

mod error;
mod locus;
mod snapshot;

pub use error::RhapsodyDecodeError;
pub use snapshot::SnapshotDecodeError;

/// The chain law's successor half, surfaced for the clock-fold agreement
/// harness and its sampled twin (the codec itself reaches it through its
/// own module).
#[cfg(any(test, kani))]
pub use snapshot::rank_successor;

/// The shared chain derivation (PRD 0023's interlock): the run-coalesced
/// identity plane stores and materializes its inline rank steps through the
/// codec's own chain law, so a plane run and a wire run can never name
/// different chains.
pub(super) use snapshot::{apply_chain_step, chain_step};

use locus::{decode_locus, encode_locus};

impl Rhapsody {
    /// Encodes this rhapsody as its canonical version-2 wire frame (S127). The
    /// frame is a version byte, a `u32` locus count, the locus records in
    /// strictly ascending woven-dot order, then the visible set as its own
    /// have-set frame (PRD 0016). Each locus record is a dot, a tagged sided
    /// anchor, and a 17-byte [`Kairos`](crate::kairos::Kairos) rank frame, so
    /// the stamp codec stays the single source of rank bytes. Big-endian
    /// throughout. Infallible; the only allocation is the frame.
    ///
    /// The two coordinates ship separately because they mean different
    /// things: the skeleton is the grow-only ordering record, the suffix
    /// the visible causal coordinate, a subset of its dots. Equal
    /// rhapsodies encode to identical bytes, so the frame is a sound
    /// content hash (the canonical bijection); it is deliberately not a
    /// sort key, since document order is a read, not a byte property.
    ///
    /// # 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; see `snapshot/` for the
    /// shipped sibling). v2 supersedes the retired, sideless v1 (S127),
    /// which decode refuses rather than translates.
    #[must_use]
    pub fn to_bytes(&self) -> Vec<u8> {
        // Saturate rather than panic on the unreachable 2^32-locus case:
        // `to_bytes` is infallible.
        let locus_count = u32::try_from(self.skeleton.len()).unwrap_or(u32::MAX);
        let mut out = Vec::with_capacity(RHAPSODY_WIRE_HEADER_LEN);
        out.push(RHAPSODY_WIRE_V2);
        out.extend_from_slice(&locus_count.to_be_bytes());
        // The plane enumerates ascending by dot, the order decode demands.
        for (dot, locus) in self.skeleton.iter() {
            encode_locus(&mut out, dot, &locus);
        }
        // The suffix frame is self-describing, so no outer length prefix.
        out.extend_from_slice(&self.visible.to_bytes());
        out
    }

    /// Decodes exactly one canonical frame produced by [`to_bytes`](Self::to_bytes),
    /// rejecting trailing bytes.
    ///
    /// # Errors
    /// [`RhapsodyDecodeError::UnexpectedLength`] if `bytes` carries trailing bytes;
    /// otherwise the variants of [`from_prefix`](Self::from_prefix). Never panics on
    /// adversarial input.
    pub fn from_bytes(bytes: &[u8]) -> Result<Self, RhapsodyDecodeError> {
        let (rhapsody, tail) = Self::from_prefix(bytes)?;
        if tail.is_empty() {
            Ok(rhapsody)
        } else {
            // `from_bytes` is `from_prefix` plus "the tail must be empty"; the
            // consumed prefix is the exact frame the counts described.
            Err(RhapsodyDecodeError::UnexpectedLength {
                expected: bytes.len() - tail.len(),
                found: bytes.len(),
            })
        }
    }

    /// Decodes a canonical frame from the start of `bytes`, returning the rhapsody and
    /// the unconsumed tail (the [`DotSet::from_prefix`] seam, one type up).
    ///
    /// Decode refuses any frame the encoder could not produce, so accepted
    /// frames re-encode bit for bit (the canonical bijection). Canonical
    /// form: loci strictly ascending by woven dot, no zero-index dot (which
    /// [`weave`](Rhapsody::weave) refuses), no anchor tag above `0x02`; the
    /// retired sideless v1 header is refused as
    /// [`UnknownVersion`](RhapsodyDecodeError::UnknownVersion) (S127).
    /// Structural law: every visible dot must carry a locus, the
    /// cross-coordinate invariant no byte count can express; admitting a
    /// violation would leave `order()` unable to place a live element.
    ///
    /// A dangling anchor (naming a dot the frame does not carry) is
    /// deliberately accepted: it is a legal, reachable value (an
    /// out-of-order weave, or a removal whose testimony outran the anchor's
    /// locus; the S117 fuzz finding), so refusing it would break the
    /// bijection over legal values. Reachability is a read, not a wire
    /// refusal.
    ///
    /// # The suffix dot budget is the skeleton's cardinality (S197)
    ///
    /// The visible suffix decodes under a dot budget of the decoded
    /// skeleton's cardinality, not the byte length: visibility is a subset
    /// of the skeleton, and every locus is backed by real frame bytes, so
    /// the skeleton bounds any honest visible set. Consequences (the S197
    /// gate review's finding): a legal dense-above-a-hole visible set
    /// round-trips instead of refusing the codec's own output, and prefix
    /// acceptance is independent of trailing bytes (a byte-length budget
    /// read through the tail inflates with it). A hostile over-dense
    /// suffix still refuses; the standalone have-set frame keeps its
    /// PRD 0016 byte-length budget, where no outer structure vouches.
    ///
    /// Allocation is bounded by the input, never by an untrusted count. Before
    /// each record the decoder checks the remaining bytes against the
    /// per-locus minimum, so a frame claiming `u32::MAX` loci refuses in
    /// `O(1)`. A count past the identity plane's live-entry ceiling refuses up
    /// front as [`TooManyLoci`](RhapsodyDecodeError::TooManyLoci), never
    /// folding into a truncated skeleton. That ceiling is `2^31 - 2`, below
    /// this field's `u32` domain since the plane run-coalesced (S199).
    ///
    /// # Errors
    /// [`RhapsodyDecodeError::UnknownVersion`] for an unrecognized version byte;
    /// [`RhapsodyDecodeError::UnexpectedLength`] if the input is shorter than the
    /// declared locus count requires;
    /// [`RhapsodyDecodeError::TooManyLoci`] for a count past the plane's
    /// ceiling; [`RhapsodyDecodeError::ZeroDot`],
    /// [`RhapsodyDecodeError::NonAscendingLoci`], and [`RhapsodyDecodeError::BadAnchorTag`]
    /// for the canonical-form violations; [`RhapsodyDecodeError::VisibleWithoutLocus`]
    /// for the structural violation;
    /// [`RhapsodyDecodeError::Rank`] for a malformed rank frame; and
    /// [`RhapsodyDecodeError::Visible`] for a malformed have-set suffix. Never panics on
    /// adversarial input.
    pub fn from_prefix(bytes: &[u8]) -> Result<(Self, &[u8]), RhapsodyDecodeError> {
        let header: [u8; RHAPSODY_WIRE_HEADER_LEN] = bytes
            .get(..RHAPSODY_WIRE_HEADER_LEN)
            .and_then(|h| h.try_into().ok())
            .ok_or(RhapsodyDecodeError::UnexpectedLength {
                expected: RHAPSODY_WIRE_HEADER_LEN,
                found: bytes.len(),
            })?;
        let [version, c0, c1, c2, c3] = header;
        // v2 only: the retired v1 (`0x01`) is refused as an unknown version, since
        // its sideless anchor tag is a different value shape (S127).
        if version != RHAPSODY_WIRE_V2 {
            return Err(RhapsodyDecodeError::UnknownVersion(version));
        }
        let locus_count = u32::from_be_bytes([c0, c1, c2, c3]);
        // Refuse a count no plane can hold before any record work: the
        // identity plane's live-entry ceiling sits below this field's u32
        // domain (the step tag's half of the handle space, S199), and a
        // frame past it must refuse rather than fold into a silently
        // truncated skeleton (the S199 gate review's finding).
        if u64::from(locus_count) > super::identity::PLANE_CAPACITY as u64 {
            return Err(RhapsodyDecodeError::TooManyLoci {
                count: u64::from(locus_count),
                capacity: super::identity::PLANE_CAPACITY as u64,
            });
        }

        // 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[RHAPSODY_WIRE_HEADER_LEN..];
        let mut skeleton = BTreeMap::new();
        let mut previous_dot: Option<Dot> = None;

        for _ in 0..locus_count {
            let (dot, locus, tail) = decode_locus(bytes, rest)?;
            rest = tail;

            if let Some(previous) = previous_dot
                && dot <= previous
            {
                return Err(RhapsodyDecodeError::NonAscendingLoci {
                    previous: previous.into(),
                    found: dot.into(),
                });
            }
            previous_dot = Some(dot);
            let _ = skeleton.insert(dot, locus);
        }

        // The visible causal coordinate: its own canonical have-set frame, whose
        // decoder consumes exactly its own bytes and re-validates its own form.
        // Its dot budget is the decoded skeleton's cardinality, not the byte
        // length: visibility is a subset of the skeleton, so the skeleton the
        // frame just vouched for bounds the honest set exactly. This keeps a
        // legal dense-above-a-hole visible set decodable (the S197 gate
        // review's finding: a deleted low dot under a long live run encodes
        // to fewer suffix bytes than dots, so a byte budget refuses the
        // codec's own output) and makes prefix acceptance independent of any
        // trailing bytes (a byte budget read through the tail inflates with
        // it). A hostile over-dense suffix still refuses: the budget is the
        // skeleton the loci bytes actually paid for.
        let budget = HaveSetDecodeBudget::new(skeleton.len());
        let (visible, tail) =
            DotSet::from_prefix_with_budget(rest, budget).map_err(RhapsodyDecodeError::Visible)?;
        rest = tail;

        // The structural law the byte layout cannot carry: every visible dot must
        // have a locus in the skeleton. Visibility is a subset of the skeleton by
        // construction (`weave` inserts into both, `causal_merge` unions skeletons
        // and merges visibility under the survivor law), so a frame whose have-set
        // over-reaches the skeleton is a value no encoder produces, and admitting it
        // would leave `order()` unable to place a live dot. This is the structural
        // check the 41-byte-per-dot estimate cannot express: a cross-reference
        // invariant between the two coordinates, not a byte count.
        //
        // A DANGLING ANCHOR (a `Some` anchor naming a dot the frame does not carry)
        // is DELIBERATELY NOT refused: it is a legal, reachable `Rhapsody` value, not a
        // corruption. `weave` accepts a dangling anchor (an out-of-order delta), and
        // a full state reaches one whenever a removal's testimony (a bare context
        // delta, no skeleton) lets a peer's context cover an anchor dot whose locus
        // it never received, so a later delta omits that locus as non-novel. The
        // rhapsody-convergence fuzz rung discovered this reachable state (S117 finding);
        // refusing it here would make a legal value un-serializable and break the
        // bijection. `order()` already handles a dangling anchor soundly (its
        // subtree is simply unreachable), and the reachability diagnostic is a read
        // (PRD 0017 `is_reachable`), not a wire refusal.
        for dot in visible.dots() {
            if !skeleton.contains_key(&dot) {
                return Err(RhapsodyDecodeError::VisibleWithoutLocus {
                    station: dot.station(),
                    index: dot.counter(),
                });
            }
        }

        let consumed = bytes.len() - rest.len();
        // Rebuild the maintained child index (S116) from the decoded skeleton:
        // it is a pure function of the skeleton and does not travel on the wire,
        // so a decoded rhapsody materializes it once via `from_parts`.
        Ok((Self::from_parts(skeleton, visible), &bytes[consumed..]))
    }
}