znippy_plugin_git/

forest.rs

//! **The forest a pack already is** — and the reason resolving one is a
//! [`gatling`](znippy_zoomies::gatling_forkjoin) job rather than a `for` loop.
//!
//! Every pack entry has **at most one** delta base. One parent per node is the
//! definition of a forest, so the dependents [`crate::resolve`] has always
//! collected (`ofs_deps`, `ref_deps`) are not an incidental index — they are the
//! **children lists** of a forest whose roots are the entries that delta against
//! nothing in this pack. Two different roots' subtrees share no object and no
//! ordering constraint, so they are independent work.
//!
//! # Why this exists (MEASURED, oden 2026-08-30, lane Z)
//!
//! `torvalds/linux --mirror`: 8.12 GiB pack, 13 948 244 objects, 11 215 872
//! deltas, on the appliance's 4 vCPU / 16 GB shape. Time to ack **3974 s**, of
//! which `resolve_ms=3159178` — **52.6 minutes inside `Resolver::run`'s
//! fixpoint, on ONE thread at ~4200 obj/s while three vCPUs sat idle**. Stock
//! git acks the same mirror in ~11 minutes. The connectivity walk everybody
//! blamed was 7m59s of the 66m14s.
//!
//! # What the shape buys, beyond the cores
//!
//! The fixpoint held a base from the moment it resolved until its **last
//! dependent's position in the pack**, which is a distance the pack format does
//! not bound — that is what `base_budget` and Belady eviction exist to cap. A
//! depth-first walk of one subtree holds a base only while its **own subtree**
//! is being walked, so the live set is the **path from the root to the current
//! node** and nothing else. The ceiling is still there and still honoured; it is
//! simply far below it.
//!
//! # What it costs, exactly
//!
//! Three `Vec<u32>` over the walk: `parent` (one slot per entry), `child_start`
//! (one per entry plus one) and `child_of` (one per delta). For the kernel pack
//! that is 55.8 + 55.8 + 44.9 = **156.5 MB**, and it **replaces**
//! `HashMap<u64, Vec<usize>> ofs_deps` (2.7 M keys, 2.7 M heap `Vec`s, 11.2 M
//! `usize`s — ~230 MB) plus the fixpoint's `remaining`/`stuck` index vectors
//! (111 MB each). The forest is the cheaper of the two representations of the
//! same fact (LAW 5: it is built from `PackWalk::entries` and nothing else).

use anyhow::{Result, bail};

use crate::pack_walk::{DeltaBase, PackWalk};

/// No parent — the entry is a root of its tree.
pub const NO_PARENT: u32 = u32::MAX;

/// A bitset over the pack's entries. One bit per entry: 1.7 MB for the kernel
/// pack, against 111 MB for the `Vec<usize>` of indices it replaces.
#[derive(Clone)]
pub struct EntrySet {
    words: Vec<u64>,
    len: usize,
    count: usize,
}

impl EntrySet {
    pub fn new(len: usize) -> Self {
        Self {
            words: vec![0u64; len.div_ceil(64)],
            len,
            count: 0,
        }
    }

    #[inline]
    pub fn contains(&self, i: usize) -> bool {
        i < self.len && (self.words[i >> 6] >> (i & 63)) & 1 == 1
    }

    #[inline]
    pub fn insert(&mut self, i: usize) -> bool {
        let (w, b) = (i >> 6, i & 63);
        if (self.words[w] >> b) & 1 == 1 {
            return false;
        }
        self.words[w] |= 1u64 << b;
        self.count += 1;
        true
    }

    /// How many entries are in the set — the round's object count, without a
    /// second pass over the bits.
    pub fn len(&self) -> usize {
        self.count
    }

    pub fn is_empty(&self) -> bool {
        self.count == 0
    }

    /// Fold another set of the same width in. What a fixpoint uses to say
    /// "these are resolved now" without a pass over the entries.
    pub fn union_with(&mut self, other: &EntrySet) {
        debug_assert_eq!(self.len_bits(), other.len_bits());
        let mut count = 0usize;
        for (a, b) in self.words.iter_mut().zip(other.words.iter()) {
            *a |= *b;
            count += a.count_ones() as usize;
        }
        self.count = count;
    }

    /// How many entries the set spans, set or not.
    pub fn len_bits(&self) -> usize {
        self.len
    }

    pub fn clear(&mut self) {
        self.words.iter_mut().for_each(|w| *w = 0);
        self.count = 0;
    }
}

/// **The dependents of every entry, as a forest.**
///
/// Children are in **ascending entry order** inside `child_of`, which is what
/// makes a depth-first walk of a subtree a fixed sequence and therefore makes
/// the resolver's output independent of how many workers walked it.
pub struct DeltaForest {
    parent: Vec<u32>,
    child_start: Vec<u32>,
    child_of: Vec<u32>,
    /// Entries that delta against nothing at all: the roots that are resolvable
    /// without a single lookup.
    whole_roots: Vec<u32>,
    /// Entries that delta against an oid. Their parent is not knowable from the
    /// walk — an oid is what the resolver *computes* — so they are roots of
    /// their own subtrees until a round places them.
    ref_roots: Vec<u32>,
}

impl DeltaForest {
    /// Build it from the walk, and from nothing else.
    pub fn build(w: &PackWalk) -> Result<Self> {
        let n = w.entries.len();
        let mut parent = vec![NO_PARENT; n];
        let mut whole_roots = Vec::new();
        let mut ref_roots = Vec::new();
        let mut kids = vec![0u32; n + 1];
        for (i, e) in w.entries.iter().enumerate() {
            match &e.delta_base {
                DeltaBase::None => whole_roots.push(i as u32),
                DeltaBase::Ref(_) => ref_roots.push(i as u32),
                DeltaBase::Offset(o) => {
                    // Offsets ascend in entry order — the walk's own invariant —
                    // so the base is found by binary search and is always
                    // *earlier* than the entry that deltas against it.
                    let p = w.entries.binary_search_by_key(o, |x| x.offset).map_err(|_| {
                        anyhow::anyhow!(
                            "entry at offset {} deltas against offset {o} which no entry starts \
                             at — the pack is corrupt",
                            e.offset
                        )
                    })?;
                    if p >= i {
                        bail!(
                            "entry at offset {} deltas against offset {o}, which is not earlier \
                             in the pack — the pack is corrupt",
                            e.offset
                        );
                    }
                    parent[i] = p as u32;
                    kids[p] += 1;
                }
            }
        }
        // Counting sort into CSR: prefix-sum the per-parent counts, then fill in
        // ascending entry order so every child list comes out sorted.
        let mut child_start = vec![0u32; n + 1];
        let mut acc = 0u32;
        for i in 0..n {
            child_start[i] = acc;
            acc += kids[i];
        }
        child_start[n] = acc;
        let mut fill = child_start.clone();
        let mut child_of = vec![0u32; acc as usize];
        for i in 0..n {
            let p = parent[i];
            if p != NO_PARENT {
                child_of[fill[p as usize] as usize] = i as u32;
                fill[p as usize] += 1;
            }
        }
        Ok(Self {
            parent,
            child_start,
            child_of,
            whole_roots,
            ref_roots,
        })
    }

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

    #[inline]
    pub fn children(&self, i: u32) -> &[u32] {
        let (a, b) = (self.child_start[i as usize] as usize, self.child_start[i as usize + 1] as usize);
        &self.child_of[a..b]
    }

    #[inline]
    pub fn parent(&self, i: u32) -> u32 {
        self.parent[i as usize]
    }

    /// The entries that need no lookup at all to resolve.
    pub fn whole_roots(&self) -> &[u32] {
        &self.whole_roots
    }

    /// The `REF_DELTA` entries, in ascending order.
    pub fn ref_roots(&self) -> &[u32] {
        &self.ref_roots
    }

    /// **Which entries a round covers**, given the roots it starts from.
    ///
    /// One forward sweep and no stack: a parent's index is always lower than its
    /// child's (offsets ascend), so `i` is reachable exactly when its parent is,
    /// and that is already decided by the time the sweep gets to `i`.
    pub fn closure_of(&self, roots: &[u32]) -> EntrySet {
        let n = self.entries();
        let mut set = EntrySet::new(n);
        let mut is_root = EntrySet::new(n);
        for &r in roots {
            is_root.insert(r as usize);
        }
        for i in 0..n {
            let reachable = if is_root.contains(i) {
                true
            } else {
                match self.parent[i] {
                    NO_PARENT => false,
                    p => set.contains(p as usize),
                }
            };
            if reachable {
                set.insert(i);
            }
        }
        set
    }

    /// Total nodes in the subtree rooted at `r`, counting `r`. What a scheduler
    /// weighs a unit by, and what a test asserts a partition against.
    pub fn subtree_size(&self, r: u32) -> u64 {
        let mut stack = vec![r];
        let mut n = 0u64;
        while let Some(x) = stack.pop() {
            n += 1;
            stack.extend_from_slice(self.children(x));
        }
        n
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::object::GitHashKind;
    use crate::pack_walk::walk;

    /// The generated corpus first — a pack this repository states in source, so
    /// the assertions below hold on a fresh clone — then whatever real packs
    /// this machine happens to carry, which is the only place a **thin** pack
    /// (a `REF_DELTA` root) turns up in the wild.
    fn corpus(cap: usize) -> Vec<(String, Vec<u8>)> {
        let mut out: Vec<(String, Vec<u8>)> =
            vec![("the generated corpus".to_string(), crate::pack_fixture::corpus().pack.clone())];
        let Ok(repos) = std::fs::read_dir(std::path::Path::new("/home/rickard/git")) else {
            return out;
        };
        for repo in repos.flatten() {
            let Ok(files) = std::fs::read_dir(repo.path().join(".git/objects/pack")) else {
                continue;
            };
            for f in files.flatten() {
                let p = f.path();
                if p.extension().is_some_and(|e| e == "pack")
                    && f.metadata().map(|m| m.len() < 32 << 20).unwrap_or(false)
                    && let Ok(bytes) = std::fs::read(&p)
                {
                    out.push((p.display().to_string(), bytes));
                    if out.len() >= cap {
                        return out;
                    }
                }
            }
        }
        out
    }

    #[test]
    fn every_entry_has_at_most_one_parent_and_the_children_are_its_dependents() {
        let mut seen = 0;
        for (name, pack) in corpus(6) {
            let w = walk(&pack, GitHashKind::Sha1.oid_len()).expect("walk");
            let f = DeltaForest::build(&w).expect("forest");
            assert_eq!(f.entries(), w.entries.len(), "{name}");
            // Every OFS delta is a child of exactly the entry at its base offset.
            let mut children_seen = 0usize;
            for (i, e) in w.entries.iter().enumerate() {
                match &e.delta_base {
                    crate::pack_walk::DeltaBase::Offset(o) => {
                        let p = f.parent(i as u32);
                        assert_ne!(p, NO_PARENT, "{name} entry {i}");
                        assert_eq!(w.entries[p as usize].offset, *o, "{name} entry {i}");
                        assert!(f.children(p).contains(&(i as u32)), "{name} entry {i}");
                        children_seen += 1;
                    }
                    _ => assert_eq!(f.parent(i as u32), NO_PARENT, "{name} entry {i}"),
                }
            }
            let total: usize = (0..w.entries.len()).map(|i| f.children(i as u32).len()).sum();
            assert_eq!(total, children_seen, "{name}: every child is somebody's");
            // Children are ascending — the fixed sequence determinism rests on.
            for i in 0..w.entries.len() {
                let c = f.children(i as u32);
                assert!(c.windows(2).all(|p| p[0] < p[1]), "{name} entry {i} children unsorted");
            }
            seen += 1;
        }
        assert!(seen > 0, "no real packs in the corpus — the assertion above proved nothing");
    }

    #[test]
    fn the_closure_of_the_whole_roots_is_every_entry_that_is_not_a_ref_delta_subtree() {
        for (name, pack) in corpus(6) {
            let w = walk(&pack, GitHashKind::Sha1.oid_len()).expect("walk");
            let f = DeltaForest::build(&w).expect("forest");
            let set = f.closure_of(f.whole_roots());
            // A self-contained pack has no ref deltas, so the closure is everything.
            let refs = f.ref_roots().len();
            if refs == 0 {
                assert_eq!(set.len(), w.entries.len(), "{name}");
            } else {
                assert!(set.len() < w.entries.len(), "{name}");
            }
            // The two sets partition the pack: closure(whole) + closure(refs).
            let rest = f.closure_of(f.ref_roots());
            assert_eq!(set.len() + rest.len(), w.entries.len(), "{name}");
            for i in 0..w.entries.len() {
                assert!(set.contains(i) ^ rest.contains(i), "{name} entry {i} in both or neither");
            }
        }
    }

    #[test]
    fn the_subtree_sizes_of_the_roots_sum_to_the_pack() {
        for (name, pack) in corpus(4) {
            let w = walk(&pack, GitHashKind::Sha1.oid_len()).expect("walk");
            let f = DeltaForest::build(&w).expect("forest");
            let total: u64 = f
                .whole_roots()
                .iter()
                .chain(f.ref_roots().iter())
                .map(|r| f.subtree_size(*r))
                .sum();
            assert_eq!(total, w.entries.len() as u64, "{name}");
        }
    }

    #[test]
    fn an_empty_pack_has_an_empty_forest() {
        let set = EntrySet::new(0);
        assert!(set.is_empty());
        assert!(!set.contains(0));
    }
}