plugins/native/znippy-plugin-git/src/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::PathBuf::from(std::env::var_os("HOME").unwrap_or_default()).join("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));
}
}