haematite 0.7.0

//! Shared reachability walk (STORAGE-VACUUM.md §2).
//!
//! The crate-internal reusable form of `branch::prune::collect_reachable`:
//! ONE depth-first walk — dedup by hash, push every internal node's children,
//! fail-fast the instant a referenced node cannot be resolved — parameterised
//! over a [`NodeSource`] so its two callers share the traversal by
//! construction rather than by duplicated skeleton:
//!
//! - `branch::prune` (a [`crate::store::NodeStore`]-cached source, LOGICAL
//!   serialised bytes, must-resolve-here — a missing node is [`PruneError`]);
//! - `db::vacuum::mark` (a verified-file-map source that recomputes every
//!   traversed node's content hash before trusting its child list — COMPRESSED
//!   file bytes, and DUAL fail-mode: a declared root must resolve here, while a
//!   probed root may legitimately resolve in another store).
//!
//! The two axes the design names — byte-mode and fail-mode — live in the
//! caller, not here: byte-mode is the source's [`NodeSource::Bytes`] measure,
//! and fail-mode is how the caller maps [`ReachError::Missing`] (a hard
//! refusal for the declared walk, "try the next store" for the probe). The
//! walk itself is fail-fast and mode-free, so prune's observable behaviour is
//! unchanged: same dedup, same traversal order, same logical-byte measure, and
//! a missing node still stops the walk before any deletion.
//!
//! [`PruneError`]: crate::branch::prune::PruneError

use std::collections::HashMap;

use crate::tree::Hash;

/// A source of nodes for a reachability walk.
///
/// [`resolve`](NodeSource::resolve) reports one node's byte weight and pushes
/// its child hashes onto the walk's stack, or signals the node's absence, or
/// fails hard. Pushing children through the caller-owned stack (rather than
/// returning them) keeps the walk allocation-free per node — the same shape
/// both callers had before the extraction.
pub trait NodeSource {
    /// A hard failure the walk propagates verbatim (unreadable bytes, a
    /// content-hash mismatch, a store read error).
    type Error;
    /// The per-node byte measure this source reports: logical serialised bytes
    /// for prune, compressed on-disk file bytes for the vacuum.
    type Bytes;

    /// Resolve `hash` against this source:
    ///
    /// - `Ok(Some(bytes))` — present. The node's child hashes have been pushed
    ///   onto `stack`, and `bytes` is its byte weight.
    /// - `Ok(None)` — absent from THIS source. Never an error at the walk
    ///   level; the caller decides whether absence is fatal.
    /// - `Err(_)` — a hard failure that aborts the walk regardless of the
    ///   caller's fail-mode (corruption evidence must never be swept around).
    fn resolve(
        &self,
        hash: Hash,
        stack: &mut Vec<Hash>,
    ) -> Result<Option<Self::Bytes>, Self::Error>;
}

/// Why a walk stopped before resolving every reachable node.
pub enum ReachError<E> {
    /// The source raised a hard error (propagated verbatim).
    Source(E),
    /// A node was absent from the source ([`NodeSource::resolve`] returned
    /// `Ok(None)`). A must-resolve-here caller maps this to its own typed
    /// refusal; a may-resolve-elsewhere caller treats it as "not in this
    /// store, try the next".
    Missing(Hash),
}

/// Depth-first walk from `roots`, deduplicating by hash.
///
/// Returns every reached node mapped to its byte weight. Fail-fast: the first
/// hard error or first absent node stops the walk immediately — nothing is
/// deleted or marked on a partial result, which is what earns the "fail loud
/// on any missing or unreadable referenced node" contract (§2).
pub fn collect_reachable<S: NodeSource>(
    source: &S,
    roots: impl IntoIterator<Item = Hash>,
) -> Result<HashMap<Hash, S::Bytes>, ReachError<S::Error>> {
    let mut reached: HashMap<Hash, S::Bytes> = HashMap::new();
    let mut stack: Vec<Hash> = roots.into_iter().collect();
    while let Some(hash) = stack.pop() {
        if reached.contains_key(&hash) {
            continue;
        }
        match source
            .resolve(hash, &mut stack)
            .map_err(ReachError::Source)?
        {
            Some(bytes) => {
                reached.insert(hash, bytes);
            }
            None => return Err(ReachError::Missing(hash)),
        }
    }
    Ok(reached)
}