rialo-types 0.5.0-alpha.0

// Copyright (c) Subzero Labs, Inc.
// SPDX-License-Identifier: Apache-2.0

//! [`HandoverChain`] and [`HandoverChainError`].

use std::{
    collections::{BTreeSet, HashMap},
    convert::TryFrom,
    ops::{Deref, Index},
};

use serde::{Deserialize, Deserializer, Serialize, Serializer};

use super::{
    super::{epoch::EpochIdentifier, HandoverAttestation, RecordDigest},
    certificate::HandoverCertificate,
    errors::{HandoverAttestationRoutingError, HandoverChainError},
    record::HandoverRecord,
};

fn validate_canonical_genesis_first(record: &HandoverRecord) -> Result<(), HandoverChainError> {
    if record.is_genesis() {
        Ok(())
    } else {
        Err(HandoverChainError::InvalidGenesisFirstRecord)
    }
}

/// Append-only chain of [`HandoverCertificate`](crate::HandoverCertificate) (quorum) entries for epoch transitions.
///
/// Blockpool and other crates may use a separate legacy skiplist type for wire-compat; this
/// type is the record-centric quorum model with attestation routing.
///
/// API surface: public methods return references to values this type owns (certificates), not
/// references into nested fields of those certificates (e.g. configs or records).
///
/// **Serialization:** [`serde::Deserialize`] runs [`Self::validate`]. Malformed chains (wrong
/// epoch order, non-monotone `block_index`, duplicate `dest_epoch`, etc.) fail deserialization.
///
/// **Lookups:** [`Self::certificate_for_epoch`], [`Self::certificate_for_block`], and
/// [`Self::epoch_for_block`] return `None` if [`Self::validate`] fails, so invalid storage order
/// cannot produce a misleading "epoch at height" (see [`Self::validate`]).
#[derive(Clone, Debug, Default)]
pub struct HandoverChain {
    certs: Vec<HandoverCertificate>,
    digest_to_idx: HashMap<RecordDigest, usize>,
}

impl PartialEq for HandoverChain {
    fn eq(&self, other: &Self) -> bool {
        self.certs == other.certs
    }
}

impl Eq for HandoverChain {}

impl Serialize for HandoverChain {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        self.certs.serialize(serializer)
    }
}

impl<'de> Deserialize<'de> for HandoverChain {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        let certs = Vec::<HandoverCertificate>::deserialize(deserializer)?;
        Self::try_from_vec(certs).map_err(serde::de::Error::custom)
    }
}

impl TryFrom<Vec<HandoverCertificate>> for HandoverChain {
    type Error = HandoverChainError;

    fn try_from(value: Vec<HandoverCertificate>) -> Result<Self, Self::Error> {
        Self::try_from_vec(value)
    }
}

impl HandoverChain {
    pub fn new() -> Self {
        Self {
            certs: Vec::new(),
            digest_to_idx: HashMap::new(),
        }
    }

    /// Builds and validates a [`HandoverChain`] from raw certificates.
    ///
    /// This is the checked constructor used by production deserialization paths.
    pub fn try_from_vec(certs: Vec<HandoverCertificate>) -> Result<Self, HandoverChainError> {
        let digest_to_idx = certs
            .iter()
            .enumerate()
            .map(|(i, c)| (c.handover_record().record_digest(), i))
            .collect();
        let chain = Self {
            certs,
            digest_to_idx,
        };
        chain.validate()?;
        Ok(chain)
    }

    /// Verifies the same invariants enforced by [`Self::insert_next_handover`] across the whole
    /// vector: canonical genesis first row, strictly increasing `block_index`, sequential
    /// single-step epoch transitions, `previous_handover_hash` chain integrity, and unique
    /// [`HandoverRecord::dest_epoch`] per certificate.
    pub fn validate(&self) -> Result<(), HandoverChainError> {
        if self.certs.is_empty() {
            return Ok(());
        }
        let r0 = self.certs[0].handover_record();
        if !r0.is_genesis() {
            return Err(HandoverChainError::InvalidGenesisFirstRecord);
        }
        let mut seen = BTreeSet::new();
        if !seen.insert(r0.dest_epoch()) {
            return Err(HandoverChainError::DuplicateDestEpoch {
                epoch: r0.dest_epoch(),
            });
        }
        let mut prev_bi = r0.block_index();
        let mut prev_dest = r0.dest_epoch();
        let mut prev_hash = self.certs[0].handover_record().record_digest();

        for cert in self.certs.iter().skip(1) {
            let cur = cert.handover_record();
            if *cur.previous_handover_hash() != prev_hash {
                return Err(HandoverChainError::PreviousHashMismatch {
                    expected: prev_hash,
                    got: *cur.previous_handover_hash(),
                });
            }
            if !seen.insert(cur.dest_epoch()) {
                return Err(HandoverChainError::DuplicateDestEpoch {
                    epoch: cur.dest_epoch(),
                });
            }
            if cur.block_index() <= prev_bi {
                return Err(HandoverChainError::NonAscendingBlockIndex {
                    new: cur.block_index(),
                    last: prev_bi,
                });
            }
            if cur.source_epoch() != prev_dest {
                return Err(HandoverChainError::SourceEpochMismatch {
                    last_dest: prev_dest,
                    got: cur.source_epoch(),
                });
            }
            let Some(next_n) = prev_dest.as_u64().checked_add(1) else {
                return Err(HandoverChainError::DestEpochOverflow);
            };
            let expected_dest = EpochIdentifier::new(next_n);
            if cur.dest_epoch() != expected_dest {
                if cur.dest_epoch().as_u64() < expected_dest.as_u64() {
                    return Err(HandoverChainError::DestEpochRegression {
                        last_dest: prev_dest,
                        expected: expected_dest,
                        got: cur.dest_epoch(),
                    });
                }
                return Err(HandoverChainError::DestEpochSkipped {
                    last_dest: prev_dest,
                    expected: expected_dest,
                    got: cur.dest_epoch(),
                });
            }
            prev_bi = cur.block_index();
            prev_dest = cur.dest_epoch();
            prev_hash = cur.record_digest();
        }
        Ok(())
    }

    /// Preferred way to start a chain with a **quorum-complete** genesis certificate once
    /// production wiring exists.
    ///
    /// **Not yet used in production:** only compiled for unit tests and when the `testing`
    /// feature is enabled. Until bootstrap is ready, use [`Self::new`] and
    /// [`Self::insert_next_handover`] (the first row may be an unsigned genesis-shaped record).
    /// When production is ready to require a fully attested genesis head, this constructor should
    /// become the default and [`Self::new`] should be restricted to tests only.
    #[cfg(any(test, feature = "testing"))]
    pub fn new_from_genesis(
        genesis_certificate: HandoverCertificate,
    ) -> Result<Self, HandoverChainError> {
        if !genesis_certificate.handover_record().is_genesis() {
            return Err(HandoverChainError::InvalidGenesisFirstRecord);
        }
        genesis_certificate.validate_attestation_consistency()?;
        let digest = genesis_certificate.handover_record().record_digest();
        let chain = Self {
            certs: vec![genesis_certificate],
            digest_to_idx: HashMap::from([(digest, 0)]),
        };
        if !chain[0].is_complete(&chain) {
            return Err(HandoverChainError::IncompleteGenesisCertificate);
        }
        chain.validate()?;
        Ok(chain)
    }

    /// Appends the next [`HandoverCertificate`](crate::HandoverCertificate), enforcing strictly increasing `block_index`,
    /// `previous_handover_hash` chain integrity, and a single-step epoch transition:
    /// `record.source_epoch` must equal the previous record's `dest_epoch`, and
    /// `record.dest_epoch` must be exactly one greater.
    ///
    /// On an empty chain (from [`Self::new`] only), the first record must satisfy
    /// [`HandoverRecord::is_genesis`] — the same canonical `0→0` shape as for a genesis record.
    ///
    /// For a **fully attested** genesis head (tests / `testing` feature), see
    /// `HandoverChain::new_from_genesis` (requires the `testing` crate feature).
    pub fn insert_next_handover(
        &mut self,
        record: HandoverRecord,
    ) -> Result<(), HandoverChainError> {
        debug_assert!(
            self.validate().is_ok(),
            "chain invariant violated before insert"
        );
        if self.certs.is_empty() {
            validate_canonical_genesis_first(&record)?;
            let digest = record.record_digest();
            self.certs.push(HandoverCertificate::new(record));
            self.digest_to_idx.insert(digest, 0);
            return Ok(());
        }
        let last = self.certs.last().expect("non-empty");
        let last_rec = last.handover_record();
        let expected_hash = last_rec.record_digest();
        if *record.previous_handover_hash() != expected_hash {
            return Err(HandoverChainError::PreviousHashMismatch {
                expected: expected_hash,
                got: *record.previous_handover_hash(),
            });
        }
        let last_bi = last_rec.block_index();
        if record.block_index() <= last_bi {
            return Err(HandoverChainError::NonAscendingBlockIndex {
                new: record.block_index(),
                last: last_bi,
            });
        }
        let last_dest = last_rec.dest_epoch();
        if record.source_epoch() != last_dest {
            return Err(HandoverChainError::SourceEpochMismatch {
                last_dest,
                got: record.source_epoch(),
            });
        }
        let Some(next_n) = last_dest.as_u64().checked_add(1) else {
            return Err(HandoverChainError::DestEpochOverflow);
        };
        let expected_dest = EpochIdentifier::new(next_n);
        if record.dest_epoch() != expected_dest {
            if record.dest_epoch().as_u64() < expected_dest.as_u64() {
                return Err(HandoverChainError::DestEpochRegression {
                    last_dest,
                    expected: expected_dest,
                    got: record.dest_epoch(),
                });
            }
            return Err(HandoverChainError::DestEpochSkipped {
                last_dest,
                expected: expected_dest,
                got: record.dest_epoch(),
            });
        }
        let idx = self.certs.len();
        let digest = record.record_digest();
        self.certs.push(HandoverCertificate::new(record));
        self.digest_to_idx.insert(digest, idx);
        Ok(())
    }

    pub fn iter(&self) -> impl Iterator<Item = &HandoverCertificate> {
        self.certs.iter()
    }

    pub fn last(&self) -> Option<&HandoverCertificate> {
        self.certs.last()
    }

    pub fn len(&self) -> usize {
        self.certs.len()
    }

    pub fn is_empty(&self) -> bool {
        self.certs.is_empty()
    }

    pub fn iter_after_epoch(
        &self,
        after_epoch: EpochIdentifier,
    ) -> impl Iterator<Item = &HandoverCertificate> + '_ {
        debug_assert!(
            self.validate().is_ok(),
            "chain invariant violated in iter_after_epoch"
        );
        let start = after_epoch.as_u64().saturating_add(1);
        let start = usize::try_from(start).unwrap_or(usize::MAX);
        self.certs.iter().skip(start)
    }

    /// The [`HandoverCertificate`](crate::HandoverCertificate) whose [`HandoverRecord::dest_epoch`] equals `epoch`
    /// (the transition into `epoch`).
    ///
    /// # Errors
    ///
    /// Returns `Err` if [`Self::validate`] fails. Returns `Ok(None)` when the chain is
    /// valid but no certificate matches `epoch`.
    pub fn certificate_for_epoch(
        &self,
        epoch: EpochIdentifier,
    ) -> Result<Option<&HandoverCertificate>, HandoverChainError> {
        self.validate()?;
        Ok(self
            .certs
            .iter()
            .find(|cert| cert.handover_record().dest_epoch() == epoch))
    }

    /// Like [`Self::certificate_for_epoch`], but mutable.
    pub fn certificate_for_epoch_mut(
        &mut self,
        epoch: EpochIdentifier,
    ) -> Result<Option<&mut HandoverCertificate>, HandoverChainError> {
        self.validate()?;
        Ok(self
            .certs
            .iter_mut()
            .find(|cert| cert.handover_record().dest_epoch() == epoch))
    }

    /// Returns the [`HandoverCertificate`](crate::HandoverCertificate) for the epoch containing `block_height`.
    ///
    /// Returns `Ok(None)` for epoch 0 (genesis) since there is no transition *into* epoch 0 —
    /// the genesis certificate at index 0 is skipped. For later epochs, returns the
    /// certificate whose transition *into* that epoch applies at `block_height`.
    ///
    /// # Errors
    ///
    /// Returns `Err` if [`Self::validate`] fails.
    pub fn certificate_for_block(
        &self,
        block_height: u64,
    ) -> Result<Option<&HandoverCertificate>, HandoverChainError> {
        self.validate()?;
        let mut result = None;
        for cert in self.certs.iter().skip(1) {
            if block_height >= cert.handover_record().block_index() {
                result = Some(cert);
            } else {
                break;
            }
        }
        Ok(result)
    }

    /// Epoch id ([`HandoverRecord::dest_epoch`] of the transition) that applies at `block_height`.
    ///
    /// Same coverage as [`Self::certificate_for_block`]: `Ok(None)` for heights before the
    /// first non-genesis transition (epoch 0), and otherwise the destination epoch of the
    /// latest transition at or before `block_height`.
    ///
    /// # Errors
    ///
    /// Returns `Err` if [`Self::validate`] fails.
    pub fn epoch_for_block(
        &self,
        block_height: u64,
    ) -> Result<Option<EpochIdentifier>, HandoverChainError> {
        Ok(self
            .certificate_for_block(block_height)?
            .map(|cert| cert.handover_record().dest_epoch()))
    }

    /// Route a handover attestation to the matching certificate (by record digest). Returns
    /// `Ok(true)` when quorum completeness is first reached.
    ///
    /// The target certificate is located in O(1) via the digest index. The source-epoch
    /// committee record is resolved via `rfind` from the newest certificate, since
    /// attestations typically target the most recent handover.
    pub fn add_handover_attestation(
        &mut self,
        attestation: &HandoverAttestation,
    ) -> Result<bool, HandoverAttestationRoutingError> {
        let digest = *attestation.record_digest();
        let idx = *self.digest_to_idx.get(&digest).ok_or(
            HandoverAttestationRoutingError::NoCertificateForDigest(digest),
        )?;

        let was_complete = self.certs[idx].is_complete(self);

        let source_epoch = self.certs[idx].handover_record().source_epoch();
        let source_record = self
            .certs
            .iter()
            .rfind(|c| c.handover_record().dest_epoch() == source_epoch)
            .ok_or(HandoverAttestationRoutingError::NoSourceEpochCertificate(
                source_epoch,
            ))?
            .handover_record()
            .clone();

        self.certs[idx]
            .add_attestation_for_committee_record(attestation.clone(), &source_record)?;

        Ok(!was_complete && self.certs[idx].is_complete(self))
    }

    /// Returns the highest epoch that is safe to garbage collect, or `None`.
    ///
    /// When two consecutive certificates are both [`HandoverCertificate::is_complete`], the epoch
    /// strictly before the lower certificate's destination epoch is GC-safe. This method returns
    /// `Some(lower_dest_epoch - 1)` for the highest such pair (scanning left to right).
    ///
    /// Returns `None` if the `enable-gc` feature is not enabled, the chain has fewer than two
    /// rows, no consecutive complete pair exists, or the qualifying window would imply GC before
    /// epoch 0.
    pub fn gc_eligible_epoch(&self) -> Option<EpochIdentifier> {
        #[cfg(not(feature = "enable-gc"))]
        return None;

        #[cfg(feature = "enable-gc")]
        {
            const FIRST_GC_ELIGIBLE_LOWER_DEST_EPOCH: u64 = 1;
            const PREDECESSOR_EPOCH_STEP: u64 = 1;

            let mut result: Option<EpochIdentifier> = None;
            for window in self.certs.windows(2) {
                if window[0].is_complete(self) && window[1].is_complete(self) {
                    let lower_dest = window[0].handover_record().dest_epoch().as_u64();
                    if lower_dest >= FIRST_GC_ELIGIBLE_LOWER_DEST_EPOCH {
                        result = Some(EpochIdentifier::new(lower_dest - PREDECESSOR_EPOCH_STEP));
                    }
                }
            }
            result
        }
    }

    /// Test-only: builds a chain without checking invariants (for asserting [`Self::validate`] /
    /// lookup behavior on corrupt vectors).
    #[cfg(test)]
    pub(crate) fn from_vec_unchecked_for_test(inner: Vec<HandoverCertificate>) -> Self {
        let digest_to_idx = inner
            .iter()
            .enumerate()
            .map(|(i, c)| (c.handover_record().record_digest(), i))
            .collect();
        Self {
            certs: inner,
            digest_to_idx,
        }
    }
}

impl Index<usize> for HandoverChain {
    type Output = HandoverCertificate;

    fn index(&self, index: usize) -> &Self::Output {
        &self.certs[index]
    }
}

impl Deref for HandoverChain {
    type Target = [HandoverCertificate];

    fn deref(&self) -> &Self::Target {
        &self.certs
    }
}