plugins/native/znippy-plugin-git/src/reach.rs
//! `__gunnar_reach__` — reachability bitmaps.
//!
//! For each *selected* commit, the set of objects reachable from it — the commit
//! itself, its ancestors, and every tree and blob those commits point at —
//! recorded as a roaring bitmap over **object ordinals**.
//!
//! # Two ordinal spaces, one view
//!
//! A **sealed archive** numbers its objects in oid-lexicographic order: the order
//! the sorted lookup sub-index is in and the order `__gunnar_oid__` records in
//! its `ordinal` column, so a bitmap position is resolvable with the oid index
//! alone. [`OrdinalSpace::new`] is that space.
//!
//! A **live store** numbers its objects in an append-only space
//! ([`OrdinalTable`]): a sorted base laid down by the first fold, then every
//! object a later push brings in appended behind it in arrival order. The point
//! is that a push never renumbers anything — a bitmap is a fact about an
//! immutable commit, and under the sorted space every push shifted every ordinal
//! above the new oids, so every stored bitmap had to be rewritten bit by bit
//! (`carry_reach`, 512 entries × every object, after every push). Under the
//! stable space a push appends a few ordinals and the table is untouched. The
//! sorted order is restored only when the store seals or the appended part
//! outgrows the base, both through one remap table ([`OrdinalTable::remap_to`]).
//!
//! # No hex on any hot path
//!
//! Everything below the public builders is in integers: the graph is
//! [`OrdGraph`] (rows and ordinals), the table is [`ReachTable`] (ordinals and
//! bitmaps), a tree is read by its raw oid and each of its entries is resolved
//! with one [`OrdinalSpace::ordinal_of_raw`] — a 16-bit fanout and a short
//! binary search, no decode. GUN-PERF measured the hex form on git.git
//! (402 227 objects): the build took 85 to 150 s and `ordinal_of_hex` alone was
//! 51 % of a 65 s clone (gunnar 18c10860).
//!
//! # The builder is git's, not a closure memo
//!
//! [`build_reach_table`] walks the commits parents-before-children, starts each
//! commit's bitmap from its parents' and adds the trees with the skip rule
//! (`should_include_obj`: a set bit means that object AND everything under it
//! is already accounted for). Work is O(objects + commits), and the memory is
//! the frontier — the bitmaps of commits whose children are still to come — not
//! one closure bitmap per distinct tree. The old builder kept the latter and
//! paid a hex `String` per tree entry on top.
use std::collections::HashMap;
use std::path::Path;
use std::sync::Arc;
use anyhow::{Result, anyhow};
use roaring::RoaringBitmap;
use znippy_common::GUNNAR_REACH_MODULE;
use znippy_common::arrow::array::{Array, BinaryArray, BinaryBuilder, StringArray, StringBuilder};
use znippy_common::arrow::datatypes::{DataType, Field, Schema};
use znippy_common::arrow::record_batch::RecordBatch;
use znippy_common::read_reserved_section_bytes;
use crate::graph::CommitNode;
use crate::object::{GitObjectKind, tree_entries};
/// "No ordinal" / "no row" in the integer tables.
pub const NONE: u32 = u32::MAX;
/// Which commits get a bitmap.
#[derive(Debug, Clone, Copy)]
pub struct ReachPolicy {
/// Upper bound on how many bitmaps are sealed. Tips are taken first (a
/// commit with no child inside the archive — the branch heads a clone
/// negotiates against), then the remaining commits are sampled at an even
/// stride through generation order.
pub max_commits: usize,
}
impl Default for ReachPolicy {
fn default() -> Self {
// git's own bitmap selection is of this order: cover the tips, then
// sample the history so a `have` usually lands near a bitmapped commit.
Self { max_commits: 512 }
}
}
/// One sealed bitmap, in the sealed archive's spelling (hex commit oid). The
/// live store keeps a [`ReachTable`]; this is the `__gunnar_reach__` row.
#[derive(Debug, Clone, PartialEq)]
pub struct ReachEntry {
pub commit: String,
pub bitmap: RoaringBitmap,
}
pub fn reach_schema() -> Arc<Schema> {
Arc::new(Schema::new(vec![
Field::new("commit_oid", DataType::Utf8, false),
Field::new("cardinality", DataType::UInt64, false),
Field::new("bitmap", DataType::Binary, false),
]))
}
/// **Where a tree's bytes come from** — a lookup, not a table, keyed by the
/// **raw** oid.
///
/// It was `&HashMap<String, Vec<u8>>`: every tree payload in the repository,
/// resident, keyed by a hex `String`. MEASURED on oden 2026-08-30, the real
/// `torvalds/linux` mirror through [`crate::git_ops::GitStore`]: **28.24 GB**
/// of tree payloads held on disk so that map could be rebuilt into RAM on every
/// fold; peak RSS 50.9 GiB on a 16 GB appliance. So the map became a lookup,
/// and the store's arm resolves a tree the way any other read does.
///
/// `None` is *"not a tree this archive holds"* and is an ordinary answer, not
/// a fault: a blob is a leaf, a gitlink is a commit in another repository, and
/// a thin push's base may be outside the archive. Every caller treats it as
/// "stop here".
pub trait TreeSource: Sync {
fn tree(&self, oid: &[u8]) -> Option<std::borrow::Cow<'_, [u8]>>;
}
/// The eager arm keyed by hex (the sealed builder and the tests): one encode
/// per tree *visited*, never per entry.
impl TreeSource for HashMap<String, Vec<u8>> {
fn tree(&self, oid: &[u8]) -> Option<std::borrow::Cow<'_, [u8]>> {
self.get(&hex::encode(oid)).map(|v| std::borrow::Cow::Borrowed(v.as_slice()))
}
}
impl TreeSource for HashMap<Vec<u8>, Vec<u8>> {
fn tree(&self, oid: &[u8]) -> Option<std::borrow::Cow<'_, [u8]>> {
self.get(oid).map(|v| std::borrow::Cow::Borrowed(v.as_slice()))
}
}
/// Number of 16-bit prefixes plus one: `fanout[p]` is the first base index whose
/// two leading bytes are `>= p`, and `fanout[65536]` is the base length. git's
/// `.idx` has the 8-bit version of the same table; two bytes cut a 400 000-oid
/// search to about six entries.
const FANOUT_LEN: usize = (1 << 16) + 1;
fn build_fanout(base: &[u8], oid_len: usize) -> Vec<u32> {
let n = if oid_len == 0 { 0 } else { base.len() / oid_len };
let mut fan = vec![0u32; FANOUT_LEN];
let mut i = 0usize;
for p in 0..(1usize << 16) {
while i < n {
let at = i * oid_len;
let key = (usize::from(base[at]) << 8) | usize::from(base[at + 1]);
if key >= p {
break;
}
i += 1;
}
fan[p] = i as u32;
}
fan[1 << 16] = n as u32;
fan
}
/// **oid ⇄ ordinal, as a `Copy` view that owns nothing.**
///
/// Two layouts share it. A sorted buffer alone ([`Self::new`]) is the sealed
/// archive's space. An [`OrdinalTable`]'s view adds the fanout and the appended
/// part: ordinal `o < base_len` is the slice at `o * oid_len` of `base`, and
/// `o >= base_len` is the slice at `(o - base_len) * oid_len` of `extra`, which
/// is in arrival order and is searched through `extra_sorted` (its ordinals,
/// sorted by oid).
#[derive(Clone, Copy)]
pub struct OrdinalSpace<'a> {
base: &'a [u8],
/// Empty for a plain sorted buffer; `FANOUT_LEN` entries otherwise.
fanout: &'a [u32],
extra: &'a [u8],
extra_sorted: &'a [u32],
oid_len: usize,
}
impl<'a> OrdinalSpace<'a> {
/// Borrow a flat, **sorted**, fixed-width oid buffer as the ordinal space.
/// The sort is the caller's invariant (every sealed builder produces it in
/// oid-lexicographic order); the binary search below rests on it.
pub fn new(raw: &'a [u8], oid_len: usize) -> Self {
debug_assert!(oid_len > 0 && raw.len() % oid_len == 0, "ragged ordinal space");
Self { base: raw, fanout: &[], extra: &[], extra_sorted: &[], oid_len }
}
/// How many oids the space holds.
pub fn len(&self) -> usize {
if self.oid_len == 0 { 0 } else { (self.base.len() + self.extra.len()) / self.oid_len }
}
pub fn is_empty(&self) -> bool {
self.base.is_empty() && self.extra.is_empty()
}
pub fn oid_len(&self) -> usize {
self.oid_len
}
fn base_len(&self) -> usize {
if self.oid_len == 0 { 0 } else { self.base.len() / self.oid_len }
}
/// ordinal → raw oid, a slice into the flat buffers. `None` for an ordinal
/// outside the space.
pub fn oid(&self, ordinal: u32) -> Option<&'a [u8]> {
let o = ordinal as usize;
let b = self.base_len();
if o < b {
let at = o * self.oid_len;
self.base.get(at..at + self.oid_len)
} else {
let at = (o - b).checked_mul(self.oid_len)?;
self.extra.get(at..at + self.oid_len)
}
}
/// raw oid → ordinal: the fanout narrows the base to one 16-bit prefix, a
/// binary search finishes it, and the appended part is searched through
/// its sorted index. This is the exact inverse of [`Self::oid`].
pub fn ordinal_of_raw(&self, oid: &[u8]) -> Option<u32> {
if oid.len() != self.oid_len {
return None;
}
let (mut lo, mut hi) = if self.fanout.len() == FANOUT_LEN && self.oid_len >= 2 {
let p = (usize::from(oid[0]) << 8) | usize::from(oid[1]);
(self.fanout[p] as usize, self.fanout[p + 1] as usize)
} else {
(0usize, self.base_len())
};
while lo < hi {
let mid = lo + (hi - lo) / 2;
let at = mid * self.oid_len;
match self.base[at..at + self.oid_len].cmp(oid) {
std::cmp::Ordering::Less => lo = mid + 1,
std::cmp::Ordering::Greater => hi = mid,
std::cmp::Ordering::Equal => return Some(mid as u32),
}
}
if self.extra_sorted.is_empty() {
return None;
}
let b = self.base_len();
let (mut lo, mut hi) = (0usize, self.extra_sorted.len());
while lo < hi {
let mid = lo + (hi - lo) / 2;
let o = self.extra_sorted[mid];
let at = (o as usize - b) * self.oid_len;
match self.extra[at..at + self.oid_len].cmp(oid) {
std::cmp::Ordering::Less => lo = mid + 1,
std::cmp::Ordering::Greater => hi = mid,
std::cmp::Ordering::Equal => return Some(o),
}
}
None
}
/// hex oid → ordinal. Decodes the hex into a **stack** buffer (≤ 32 bytes),
/// so a lookup allocates nothing, then searches the raw form. Not on any
/// serving path: the walk and the builder carry raw oids.
pub fn ordinal_of_hex(&self, hex: &str) -> Option<u32> {
let mut buf = [0u8; 32];
let dst = buf.get_mut(..self.oid_len)?;
hex::decode_to_slice(hex, dst).ok()?;
self.ordinal_of_raw(dst)
}
/// The oids in ordinal order, concatenated — what a sealed builder sorts
/// and what [`OrdinalTable::from_sorted`] takes.
pub fn concat(&self) -> Vec<u8> {
let mut v = Vec::with_capacity(self.base.len() + self.extra.len());
v.extend_from_slice(self.base);
v.extend_from_slice(self.extra);
v
}
}
/// **The live store's ordinal space: a sorted base, then arrivals appended.**
/// Owned; [`Self::view`] is the lookup. See the module header for why it is
/// append-only.
#[derive(Clone, Default)]
pub struct OrdinalTable {
oid_len: usize,
base: Vec<u8>,
fanout: Vec<u32>,
extra: Vec<u8>,
extra_sorted: Vec<u32>,
}
impl OrdinalTable {
pub fn empty(oid_len: usize) -> Self {
Self { oid_len, ..Default::default() }
}
/// A fresh table over a **sorted** full oid list: base only, nothing appended.
pub fn from_sorted(raw: Vec<u8>, oid_len: usize) -> Self {
debug_assert!(oid_len > 0 && raw.len() % oid_len == 0, "ragged ordinal table");
let fanout = build_fanout(&raw, oid_len);
Self { oid_len, base: raw, fanout, extra: Vec::new(), extra_sorted: Vec::new() }
}
/// The persisted form, replayed: `full_sorted` is the store's current sorted
/// oid list and `extra` the appended part in arrival order. The base is
/// `full − extra`. `None` when the two do not agree (an oid in `extra` that
/// the store no longer holds, or a width mismatch) — rebuild from scratch.
pub fn from_parts(full_sorted: &[u8], extra: &[u8], oid_len: usize) -> Option<Self> {
if oid_len == 0 || full_sorted.len() % oid_len != 0 || extra.len() % oid_len != 0 {
return None;
}
let mut ex: Vec<&[u8]> = extra.chunks_exact(oid_len).collect();
ex.sort_unstable();
ex.dedup();
if ex.len() * oid_len != extra.len() {
return None;
}
let mut base = Vec::with_capacity(full_sorted.len().saturating_sub(extra.len()));
let mut j = 0usize;
for oid in full_sorted.chunks_exact(oid_len) {
if j < ex.len() && ex[j] == oid {
j += 1;
} else {
base.extend_from_slice(oid);
}
}
if j != ex.len() {
return None;
}
let mut t = Self::from_sorted(base, oid_len);
t.extra = extra.to_vec();
t.reindex_extra();
Some(t)
}
/// The persisted form, replayed from the two raw parts: `base` must be
/// sorted and distinct (the binary search rests on it), `extra` distinct
/// and disjoint from it. `None` otherwise — a malformed file is a rebuild,
/// never a wrong ordinal.
pub fn from_base_and_extra(base: Vec<u8>, extra: Vec<u8>, oid_len: usize) -> Option<Self> {
if oid_len == 0 || base.len() % oid_len != 0 || extra.len() % oid_len != 0 {
return None;
}
if base.chunks_exact(oid_len).zip(base.chunks_exact(oid_len).skip(1)).any(|(a, b)| a >= b) {
return None;
}
let mut t = Self::from_sorted(base, oid_len);
t.extra = extra;
t.reindex_extra();
let v = t.view();
for (i, o) in t.extra.chunks_exact(oid_len).enumerate() {
// Each appended oid must resolve to ITS ordinal: absent from the
// base, and not a duplicate inside `extra`.
if v.ordinal_of_raw(o) != Some((t.base_len() + i) as u32) {
return None;
}
}
Some(t)
}
/// The sorted base, raw — what the persisted form stores.
pub fn base_raw(&self) -> &[u8] {
&self.base
}
fn reindex_extra(&mut self) {
let b = (self.base.len() / self.oid_len) as u32;
let n = self.extra.len() / self.oid_len;
let mut idx: Vec<u32> = (0..n as u32).map(|i| i + b).collect();
let (extra, w, bb) = (&self.extra, self.oid_len, b as usize);
idx.sort_unstable_by(|&x, &y| {
let a = &extra[(x as usize - bb) * w..(x as usize - bb + 1) * w];
let c = &extra[(y as usize - bb) * w..(y as usize - bb + 1) * w];
a.cmp(c)
});
self.extra_sorted = idx;
}
pub fn len(&self) -> usize {
if self.oid_len == 0 { 0 } else { (self.base.len() + self.extra.len()) / self.oid_len }
}
pub fn is_empty(&self) -> bool {
self.base.is_empty() && self.extra.is_empty()
}
pub fn oid_len(&self) -> usize {
self.oid_len
}
pub fn base_len(&self) -> usize {
if self.oid_len == 0 { 0 } else { self.base.len() / self.oid_len }
}
/// How many ordinals were appended behind the sorted base.
pub fn extra_len(&self) -> usize {
if self.oid_len == 0 { 0 } else { self.extra.len() / self.oid_len }
}
/// The appended part, arrival order — what the persisted form stores.
pub fn extra_raw(&self) -> &[u8] {
&self.extra
}
pub fn view(&self) -> OrdinalSpace<'_> {
OrdinalSpace {
base: &self.base,
fanout: &self.fanout,
extra: &self.extra,
extra_sorted: &self.extra_sorted,
oid_len: self.oid_len,
}
}
/// **Follow the store**: `full_sorted` is every oid the store holds now, in
/// sorted order. Every oid in it that this table does not number is
/// appended (in sorted order among themselves, after everything already
/// numbered) and the range of new ordinals is returned. `None` when an oid
/// the table numbers is **absent** from `full_sorted` — something was
/// removed under the table (a gc, a retain) and the numbering cannot be
/// kept; the caller rebuilds from scratch.
pub fn follow(&mut self, full_sorted: &[u8]) -> Option<std::ops::Range<u32>> {
let w = self.oid_len;
if w == 0 || full_sorted.len() % w != 0 {
return None;
}
let before = self.len() as u32;
// The known oids in sorted order: a merge of the base and the sorted
// view of the appended part.
let mut known = KnownIter { table: self, i: 0, j: 0 };
let mut appended: Vec<u8> = Vec::new();
let mut cur = known.next();
for oid in full_sorted.chunks_exact(w) {
loop {
match cur {
None => {
appended.extend_from_slice(oid);
break;
}
Some(k) if k == oid => {
cur = known.next();
break;
}
Some(k) if k > oid => {
appended.extend_from_slice(oid);
break;
}
// A known oid smaller than the next store oid: the store
// no longer holds it.
Some(_) => return None,
}
}
}
if cur.is_some() {
return None;
}
if appended.is_empty() {
return Some(before..before);
}
self.extra.extend_from_slice(&appended);
self.reindex_extra();
Some(before..self.len() as u32)
}
/// **old ordinal → ordinal in `target`**, as one table, for a seal or a
/// compaction. [`NONE`] where `target` lacks the oid. O(n) lookups through
/// the target's fanout, once — not once per set bit.
pub fn remap_to(&self, target: &OrdinalSpace<'_>) -> Vec<u32> {
let me = self.view();
(0..me.len() as u32)
.map(|o| me.oid(o).and_then(|oid| target.ordinal_of_raw(oid)).unwrap_or(NONE))
.collect()
}
}
/// The oids an [`OrdinalTable`] numbers, in sorted order: a merge of the base
/// and the sorted view of the appended part.
struct KnownIter<'a> {
table: &'a OrdinalTable,
i: usize,
j: usize,
}
impl<'a> Iterator for KnownIter<'a> {
type Item = &'a [u8];
fn next(&mut self) -> Option<&'a [u8]> {
let t = self.table;
let w = t.oid_len;
let base_n = t.base_len();
let a = (self.i < base_n).then(|| &t.base[self.i * w..(self.i + 1) * w]);
let b = t.extra_sorted.get(self.j).map(|&o| {
let at = (o as usize - base_n) * w;
&t.extra[at..at + w]
});
match (a, b) {
(Some(a), Some(b)) => {
if a <= b {
self.i += 1;
Some(a)
} else {
self.j += 1;
Some(b)
}
}
(Some(a), None) => {
self.i += 1;
Some(a)
}
(None, Some(b)) => {
self.j += 1;
Some(b)
}
(None, None) => None,
}
}
}
/// **The commit graph in integers**: one row per commit, rows in the order the
/// [`CommitNode`] list came in (parents before children, as
/// [`crate::graph::assign_generations`] guarantees).
#[derive(Clone, Default)]
pub struct OrdGraph {
/// row → the commit's ordinal.
pub ords: Vec<u32>,
/// row → the root tree's ordinal, or [`NONE`].
pub tree: Vec<u32>,
/// row → parent **rows** (a parent outside the graph contributes nothing).
pub parents: Vec<Vec<u32>>,
/// row → generation.
pub generation: Vec<u32>,
/// The commit ordinals, as a set.
commits: RoaringBitmap,
/// rank in `commits` → row.
row_by_rank: Vec<u32>,
}
impl OrdGraph {
/// Decode each node's hex **once** and resolve it against the space. A node
/// whose oid the space does not hold is kept as a row with no ordinal (it
/// cannot be asked for by ordinal, and its children still see it as a
/// parent row).
pub fn from_nodes(nodes: &[CommitNode], space: &OrdinalSpace<'_>) -> Self {
let n = nodes.len();
let mut ords = Vec::with_capacity(n);
let mut commits = RoaringBitmap::new();
for node in nodes {
let o = space.ordinal_of_hex(&node.oid).unwrap_or(NONE);
if o != NONE {
commits.insert(o);
}
ords.push(o);
}
let mut row_by_rank = vec![NONE; commits.len() as usize];
for (row, &o) in ords.iter().enumerate() {
if o != NONE {
row_by_rank[commits.rank(o) as usize - 1] = row as u32;
}
}
let g = Self { ords, tree: Vec::new(), parents: Vec::new(), generation: Vec::new(), commits, row_by_rank };
let mut tree = Vec::with_capacity(n);
let mut parents = Vec::with_capacity(n);
let mut generation = Vec::with_capacity(n);
for node in nodes {
tree.push(node.tree.as_deref().and_then(|t| space.ordinal_of_hex(t)).unwrap_or(NONE));
let mut ps: Vec<u32> = node
.parents
.iter()
.filter_map(|p| space.ordinal_of_hex(p))
.filter_map(|o| g.row_of(o))
.collect();
ps.sort_unstable();
ps.dedup();
parents.push(ps);
generation.push(node.generation);
}
Self { tree, parents, generation, ..g }
}
pub fn len(&self) -> usize {
self.ords.len()
}
pub fn is_empty(&self) -> bool {
self.ords.is_empty()
}
/// The set of commit ordinals.
pub fn commits(&self) -> &RoaringBitmap {
&self.commits
}
#[inline]
pub fn is_commit(&self, ordinal: u32) -> bool {
self.commits.contains(ordinal)
}
/// ordinal → row, for a commit.
#[inline]
pub fn row_of(&self, ordinal: u32) -> Option<u32> {
if !self.commits.contains(ordinal) {
return None;
}
self.row_by_rank.get(self.commits.rank(ordinal) as usize - 1).copied()
}
/// Rows with no child in the graph — the tips.
pub fn tip_rows(&self) -> Vec<u32> {
let mut has_child = vec![false; self.len()];
for ps in &self.parents {
for &p in ps {
has_child[p as usize] = true;
}
}
(0..self.len() as u32).filter(|&r| !has_child[r as usize]).collect()
}
}
/// **The live reachability table**: entry `i` is the closure of the commit at
/// ordinal `commits[i]`.
#[derive(Clone, Default, Debug, PartialEq)]
pub struct ReachTable {
pub commits: Vec<u32>,
pub bitmaps: Vec<RoaringBitmap>,
}
impl ReachTable {
pub fn len(&self) -> usize {
self.commits.len()
}
pub fn is_empty(&self) -> bool {
self.commits.is_empty()
}
/// row → entry index (or [`NONE`]), over `graph`. Rebuilt at every fold
/// beside the graph; the table itself is not.
pub fn by_row(&self, graph: &OrdGraph) -> Vec<u32> {
let mut v = vec![NONE; graph.len()];
for (i, &o) in self.commits.iter().enumerate() {
if let Some(r) = graph.row_of(o) {
v[r as usize] = i as u32;
}
}
v
}
/// The sealed spelling, with every ordinal mapped through `remap` (old →
/// sorted). `None` if a set bit maps to [`NONE`] — an entry naming an object
/// the target space lacks would be a silent over-claim.
pub fn to_entries(&self, space: &OrdinalSpace<'_>, remap: Option<&[u32]>) -> Option<Vec<ReachEntry>> {
let mut out = Vec::with_capacity(self.len());
for (i, &o) in self.commits.iter().enumerate() {
// The commit's name comes out of the TARGET space, through the
// same remap its bits go through.
let c = match remap {
None => o,
Some(m) => match m.get(o as usize).copied() {
Some(n) if n != NONE => n,
_ => return None,
},
};
let commit = hex::encode(space.oid(c)?);
let bitmap = match remap {
None => self.bitmaps[i].clone(),
Some(m) => {
let mut mapped: Vec<u32> = Vec::with_capacity(self.bitmaps[i].len() as usize);
for b in self.bitmaps[i].iter() {
match m.get(b as usize).copied() {
Some(n) if n != NONE => mapped.push(n),
_ => return None,
}
}
mapped.sort_unstable();
RoaringBitmap::from_sorted_iter(mapped).ok()?
}
};
out.push(ReachEntry { commit, bitmap });
}
Some(out)
}
/// Renumber every bit through `remap` (old ordinal → new ordinal); an entry
/// whose commit maps to [`NONE`] is dropped, a BIT that does is a refusal
/// (`None`: rebuild). One array index per bit.
pub fn remapped(&self, remap: &[u32]) -> Option<ReachTable> {
let mut out = ReachTable::default();
for (i, &o) in self.commits.iter().enumerate() {
let c = *remap.get(o as usize)?;
if c == NONE {
continue;
}
let mut mapped: Vec<u32> = Vec::with_capacity(self.bitmaps[i].len() as usize);
for b in self.bitmaps[i].iter() {
match remap.get(b as usize).copied() {
Some(n) if n != NONE => mapped.push(n),
_ => return None,
}
}
mapped.sort_unstable();
out.commits.push(c);
out.bitmaps.push(RoaringBitmap::from_sorted_iter(mapped).ok()?);
}
Some(out)
}
/// Keep at most `max` entries: the current tips first, then an even sample
/// of the rest in table order.
pub fn pruned(&self, graph: &OrdGraph, max: usize) -> ReachTable {
if self.len() <= max {
return self.clone();
}
let mut is_tip = vec![false; graph.len()];
for r in graph.tip_rows() {
is_tip[r as usize] = true;
}
let tip_idx: Vec<usize> = (0..self.len())
.filter(|&i| graph.row_of(self.commits[i]).is_some_and(|r| is_tip[r as usize]))
.collect();
let mut chosen: Vec<usize> = tip_idx.iter().copied().take(max).collect();
if chosen.len() < max {
let room = max - chosen.len();
let rest: Vec<usize> = (0..self.len()).filter(|i| !tip_idx.contains(i)).collect();
if !rest.is_empty() {
let stride = rest.len().div_ceil(room).max(1);
chosen.extend(rest.iter().step_by(stride).take(room));
}
}
chosen.sort_unstable();
chosen.dedup();
ReachTable {
commits: chosen.iter().map(|&i| self.commits[i]).collect(),
bitmaps: chosen.iter().map(|&i| self.bitmaps[i].clone()).collect(),
}
}
}
/// **Carry a sealed-spelling table across a renumbering** — kept for the sealed
/// builders and the tests that speak hex; the live store uses
/// [`ReachTable::remapped`] with one remap table. `keep` decides which commits
/// survive. `None` means the carry cannot be exact (a set bit's object is gone).
pub fn carry_reach(
old: &[ReachEntry],
old_space: &OrdinalSpace<'_>,
new_space: &OrdinalSpace<'_>,
keep: impl Fn(&str) -> bool,
) -> Option<Vec<ReachEntry>> {
if old.is_empty() || old_space.is_empty() {
return None;
}
let remap: Vec<u32> = (0..old_space.len() as u32)
.map(|o| old_space.oid(o).and_then(|oid| new_space.ordinal_of_raw(oid)).unwrap_or(NONE))
.collect();
let mut out = Vec::with_capacity(old.len());
for e in old {
if !keep(&e.commit) {
continue;
}
let mut mapped = Vec::with_capacity(e.bitmap.len() as usize);
for b in e.bitmap.iter() {
match remap.get(b as usize).copied() {
Some(n) if n != NONE => mapped.push(n),
_ => return None,
}
}
mapped.sort_unstable();
let bitmap = RoaringBitmap::from_sorted_iter(mapped).ok()?;
out.push(ReachEntry { commit: e.commit.clone(), bitmap });
}
Some(out)
}
/// What the builder needs to know about every object in the archive.
pub struct ObjectFacts<'a> {
/// oid ⇄ ordinal — the bitmap space.
pub ordinal: OrdinalSpace<'a>,
/// Tree payloads, by raw oid. Blobs are not needed (they are leaves) and
/// are deliberately not asked for.
pub trees: &'a dyn TreeSource,
/// Raw oid width, needed to walk tree records.
pub oid_len: usize,
}
/// **Every object under `root` that `acc` does not already hold** — git's
/// `fill_bitmap_tree` with `should_include_obj`.
///
/// A set bit means that object and, for a tree, everything under it, is already
/// accounted for: either by a parent's closure the caller started `acc` from, or
/// by an earlier tree in this same walk. Descending anyway would be correct and
/// would make the whole exercise O(commits × tree). Iterative: a deep source
/// tree is not a stack-depth bet, and a corrupt cycle terminates because the
/// revisited oid's bit is already set.
pub(crate) fn fill_tree(root: u32, facts: &ObjectFacts<'_>, acc: &mut RoaringBitmap) {
fill_tree_counted(root, facts, acc, &mut BuildCount::default());
}
/// What a build spent, for the opt-in report (`ZNIPPY_REACH_TIMING=1`):
/// counters, not clocks, except the one clock around the tree reads.
#[derive(Default)]
struct BuildCount {
trees_read: u64,
tree_bytes: u64,
entries: u64,
tree_read: std::time::Duration,
}
fn fill_tree_counted(root: u32, facts: &ObjectFacts<'_>, acc: &mut RoaringBitmap, count: &mut BuildCount) {
let mut stack: Vec<u32> = vec![root];
while let Some(o) = stack.pop() {
if !acc.insert(o) {
continue;
}
let Some(oid) = facts.ordinal.oid(o) else { continue };
let t0 = std::time::Instant::now();
let payload = facts.trees.tree(oid);
count.tree_read += t0.elapsed();
count.trees_read += 1;
if let Some(payload) = payload {
count.tree_bytes += payload.len() as u64;
for e in tree_entries(&payload, facts.oid_len) {
count.entries += 1;
// An entry the archive does not hold (a gitlink, a thin base
// outside) has no ordinal and is not selected for emission.
if let Some(c) = facts.ordinal.ordinal_of_raw(e.oid) {
stack.push(c);
}
}
}
}
}
/// Tips first, then an even sample through the rest, capped at `max_commits`.
fn select_rows(graph: &OrdGraph, policy: ReachPolicy) -> Vec<u32> {
let n = graph.len();
let mut has_child = vec![false; n];
for ps in &graph.parents {
for &p in ps {
has_child[p as usize] = true;
}
}
let mut chosen: Vec<u32> = (0..n as u32).filter(|&i| !has_child[i as usize]).collect();
chosen.truncate(policy.max_commits);
if chosen.len() < policy.max_commits {
let room = policy.max_commits - chosen.len();
let rest: Vec<u32> = (0..n as u32).filter(|&i| has_child[i as usize]).collect();
if !rest.is_empty() {
let stride = rest.len().div_ceil(room).max(1);
chosen.extend(rest.iter().step_by(stride).take(room));
}
}
chosen.sort_unstable();
chosen.dedup();
chosen
}
/// **Build the table from scratch**, parents before children, each bitmap
/// started from its parents' and completed by [`fill_tree`].
///
/// Memory is the frontier: a commit's bitmap lives only while a child still
/// needs it (or it was selected). The last child to need a parent takes the
/// parent's bitmap by move; every other child clones it. Rows that are not in
/// the ordinal space (no oid) still get a bitmap so their children inherit the
/// history, but they are never selected.
pub fn build_reach_table(graph: &OrdGraph, facts: &ObjectFacts<'_>, policy: ReachPolicy) -> ReachTable {
let n = graph.len();
if n == 0 || policy.max_commits == 0 {
return ReachTable::default();
}
let selected = select_rows(graph, policy);
let mut keep = vec![false; n];
for &r in &selected {
keep[r as usize] = graph.ords[r as usize] != NONE;
}
let mut pending: Vec<u32> = vec![0; n];
for ps in &graph.parents {
for &p in ps {
pending[p as usize] += 1;
}
}
let mut live: Vec<Option<RoaringBitmap>> = (0..n).map(|_| None).collect();
let report = std::env::var_os(crate::arms::ENV_REACH_TIMING).is_some();
let started = std::time::Instant::now();
let mut count = BuildCount::default();
let mut live_peak = 0usize;
let mut live_now = 0usize;
for i in 0..n {
let ps = &graph.parents[i];
let mut bm: Option<RoaringBitmap> = None;
for &p in ps {
let p = p as usize;
pending[p] -= 1;
let last = pending[p] == 0 && !keep[p];
if last && live[p].is_some() {
live_now -= 1;
}
match (&mut bm, last) {
(None, true) => bm = live[p].take(),
(None, false) => bm = live[p].clone(),
(Some(acc), true) => {
if let Some(pb) = live[p].take() {
*acc |= pb;
}
}
(Some(acc), false) => {
if let Some(pb) = &live[p] {
*acc |= pb;
}
}
}
}
let mut bm = bm.unwrap_or_default();
if graph.ords[i] != NONE {
bm.insert(graph.ords[i]);
}
if graph.tree[i] != NONE {
fill_tree_counted(graph.tree[i], facts, &mut bm, &mut count);
}
if pending[i] > 0 || keep[i] {
live[i] = Some(bm);
live_now += 1;
live_peak = live_peak.max(live_now);
}
}
if report {
eprintln!(
"reach build: {} commits, {} objects, {} entries; {} trees read ({} MB, {} entries) in {:.2} s of {:.2} s; live bitmaps peak {live_peak}, end {live_now}",
n,
facts.ordinal.len(),
selected.len(),
count.trees_read,
count.tree_bytes >> 20,
count.entries,
count.tree_read.as_secs_f64(),
started.elapsed().as_secs_f64(),
);
}
let mut out = ReachTable::default();
for &r in &selected {
if !keep[r as usize] {
continue;
}
// `expect`, not `unwrap_or_default`: a missing bitmap here means the
// retention rule let a kept row be dropped, and an EMPTY bitmap would
// be a silent under-send — a clone served one object per branch.
let bitmap = live[r as usize].take().unwrap_or_else(|| {
panic!("row {r} was selected for a reachability bitmap and its bitmap is not live at the end of the build")
});
out.commits.push(graph.ords[r as usize]);
out.bitmaps.push(bitmap);
}
out
}
/// Give every `EXTEND_STRIDE`-th new commit an entry besides the new tips, so a
/// later walk down a long pushed branch is bounded by this many commits' trees.
const EXTEND_STRIDE: usize = 64;
/// **Extend a table after a push**: entries for the new tips (and a sample of
/// the other new commits), each computed by the bounded walk down to the
/// entries that already exist. Nothing already in the table is touched or
/// recomputed; the cost is the pushed commits' trees, whatever the repository's
/// size. `new_rows` must be in parents-before-children order (the caller takes
/// them off the generation-ordered graph).
pub fn extend_reach_table(
table: &ReachTable,
graph: &OrdGraph,
facts: &ObjectFacts<'_>,
new_rows: &[u32],
policy: ReachPolicy,
) -> ReachTable {
if new_rows.is_empty() || policy.max_commits == 0 {
return table.clone();
}
let mut out = table.clone();
let mut by_row = out.by_row(graph);
let mut has_child = vec![false; graph.len()];
for ps in &graph.parents {
for &p in ps {
has_child[p as usize] = true;
}
}
for (k, &r) in new_rows.iter().enumerate() {
let row = r as usize;
if graph.ords[row] == NONE || by_row[row] != NONE {
continue;
}
if has_child[row] && k % EXTEND_STRIDE != EXTEND_STRIDE - 1 {
continue;
}
let mut bm = RoaringBitmap::new();
{
let view = ReachView { table: &out, by_row: &by_row, graph };
accumulate(r, &view, facts, &mut bm);
}
by_row[row] = out.len() as u32;
out.commits.push(graph.ords[row]);
out.bitmaps.push(bm);
}
if out.len() > policy.max_commits.saturating_mul(2) {
out = out.pruned(graph, policy.max_commits);
}
out
}
/// The table, its row index and the graph, paired by the fold that built them
/// so a lookup can never mix a table with another fold's rows.
#[derive(Clone, Copy)]
pub struct ReachView<'a> {
pub table: &'a ReachTable,
pub by_row: &'a [u32],
pub graph: &'a OrdGraph,
}
impl<'a> ReachView<'a> {
/// The stored bitmap of the commit at `row`, if it has one.
#[inline]
pub fn bitmap_of_row(&self, row: u32) -> Option<&'a RoaringBitmap> {
match self.by_row.get(row as usize).copied() {
Some(i) if i != NONE => self.table.bitmaps.get(i as usize),
_ => None,
}
}
}
/// **The bounded walk: OR into `acc` everything reachable from the commit at
/// `row`, stopping at every commit that already has a bitmap.**
///
/// A stored bitmap is closed under reachability, so reaching one accounts for
/// the entire history behind it; what the walk covers is only what has been
/// pushed since the table last covered it, whatever the repository's size.
/// This is git's `add_to_include_set` rule.
///
/// The two phases are an ordering, not a style: the commit walk runs to
/// completion before a single tree is opened, so that every stored bitmap the
/// request will OR in is already in `acc` when the tree walk's skip rule runs.
/// Get it wrong and the first unbitmapped commit costs a walk of every tree in
/// the repository.
pub fn accumulate(row: u32, view: &ReachView<'_>, facts: &ObjectFacts<'_>, acc: &mut RoaringBitmap) {
// ── phase 1: the commit walk, to completion ────────────────────────────
let mut unbitmapped: Vec<u32> = Vec::new();
let mut seen = RoaringBitmap::new();
let mut stack: Vec<u32> = vec![row];
while let Some(r) = stack.pop() {
if !seen.insert(r) {
continue;
}
// **Already covered.** `acc` only ever holds closed sets — stored
// bitmaps, and the results of completed walks — so a commit whose bit
// is set has its whole history in `acc` and there is nothing to walk.
// This is what makes a clone's 1 006 wants (most of them tags on old,
// unbitmapped commits) cost nothing once the branch tips are in: the
// caller ORs the bitmapped wants first, then walks the rest.
let o = view.graph.ords[r as usize];
if o != NONE && acc.contains(o) {
continue;
}
if let Some(bm) = view.bitmap_of_row(r) {
*acc |= bm;
continue;
}
unbitmapped.push(r);
if let Some(ps) = view.graph.parents.get(r as usize) {
stack.extend(ps.iter().copied());
}
}
// ── phase 2: the trees, with the skip rule ─────────────────────────────
for r in unbitmapped {
let r = r as usize;
if view.graph.ords[r] != NONE {
acc.insert(view.graph.ords[r]);
}
if view.graph.tree[r] != NONE {
fill_tree(view.graph.tree[r], facts, acc);
}
}
}
/// Which objects a repack must hold to make the reachability pass exact.
///
/// Only commits and trees carry pointers; blobs are leaves. The builder
/// therefore needs tree payloads and nothing else, which is why
/// [`ObjectFacts::trees`] exists and there is no `blobs` field.
pub fn needs_payload(kind: GitObjectKind) -> bool {
matches!(kind, GitObjectKind::Commit | GitObjectKind::Tree)
}
/// **The sealed builder**: hex nodes in, hex entries out, over a sorted space.
/// Decodes each node once into an [`OrdGraph`] and runs [`build_reach_table`].
pub fn build_reach(commits: &[CommitNode], facts: &ObjectFacts<'_>, policy: ReachPolicy) -> Vec<ReachEntry> {
let graph = OrdGraph::from_nodes(commits, &facts.ordinal);
let table = build_reach_table(&graph, facts, policy);
table.to_entries(&facts.ordinal, None).unwrap_or_default()
}
pub fn build_reach_batch(entries: &[ReachEntry]) -> Result<RecordBatch> {
use znippy_common::arrow::array::UInt64Builder;
let n = entries.len();
let mut oid_b = StringBuilder::with_capacity(n, n * 64);
let mut card_b = UInt64Builder::with_capacity(n);
let mut bm_b = BinaryBuilder::with_capacity(n, n * 128);
for e in entries {
oid_b.append_value(&e.commit);
card_b.append_value(e.bitmap.len());
let mut buf = Vec::new();
e.bitmap
.serialize_into(&mut buf)
.map_err(|err| anyhow!("reach bitmap serialize: {err}"))?;
bm_b.append_value(&buf);
}
RecordBatch::try_new(
reach_schema(),
vec![Arc::new(oid_b.finish()), Arc::new(card_b.finish()), Arc::new(bm_b.finish())],
)
.map_err(|e| anyhow!("reach batch: {e}"))
}
pub fn decode_reach(bytes: &[u8]) -> Result<Vec<ReachEntry>> {
// Through the IPC guard: the section comes out of an archive.
let reader = znippy_common::ipc_guard::stream_reader(bytes)
.map_err(|e| anyhow!("reach reader: {e}"))?;
let mut out = Vec::new();
for batch in reader {
let batch = batch.map_err(|e| anyhow!("reach batch read: {e}"))?;
let oids = batch
.column_by_name("commit_oid")
.and_then(|c| c.as_any().downcast_ref::<StringArray>())
.ok_or_else(|| anyhow!("reach: no `commit_oid` column"))?;
let bms = batch
.column_by_name("bitmap")
.and_then(|c| c.as_any().downcast_ref::<BinaryArray>())
.ok_or_else(|| anyhow!("reach: no `bitmap` column"))?;
for i in 0..batch.num_rows() {
let bitmap = RoaringBitmap::deserialize_from(bms.value(i))
.map_err(|e| anyhow!("reach bitmap deserialize: {e}"))?;
out.push(ReachEntry { commit: oids.value(i).to_string(), bitmap });
}
}
Ok(out)
}
/// Read the reachability bitmaps out of a sealed archive. `Ok(None)` when absent.
pub fn read_reach(archive: &Path) -> Result<Option<Vec<ReachEntry>>> {
match read_reserved_section_bytes(archive, GUNNAR_REACH_MODULE)? {
Some(b) => Ok(Some(decode_reach(&b)?)),
None => Ok(None),
}
}
// ── the live table's persisted form ─────────────────────────────────────────
fn live_schema() -> Arc<Schema> {
Arc::new(Schema::new(vec![
Field::new("commit_ordinal", DataType::UInt32, false),
Field::new("bitmap", DataType::Binary, false),
]))
}
/// The live table as Arrow IPC stream bytes: `(commit_ordinal, bitmap)`.
pub fn encode_live_table(table: &ReachTable) -> Result<Vec<u8>> {
use znippy_common::arrow::array::UInt32Builder;
let n = table.len();
let mut ord_b = UInt32Builder::with_capacity(n);
let mut bm_b = BinaryBuilder::with_capacity(n, n * 128);
for (i, &o) in table.commits.iter().enumerate() {
ord_b.append_value(o);
let mut buf = Vec::new();
table.bitmaps[i]
.serialize_into(&mut buf)
.map_err(|err| anyhow!("reach bitmap serialize: {err}"))?;
bm_b.append_value(&buf);
}
let batch = RecordBatch::try_new(live_schema(), vec![Arc::new(ord_b.finish()), Arc::new(bm_b.finish())])
.map_err(|e| anyhow!("live reach batch: {e}"))?;
let mut buf = Vec::new();
{
let mut w = znippy_common::arrow::ipc::writer::StreamWriter::try_new(&mut buf, &live_schema())
.map_err(|e| anyhow!("live reach writer: {e}"))?;
w.write(&batch).map_err(|e| anyhow!("live reach write: {e}"))?;
w.finish().map_err(|e| anyhow!("live reach finish: {e}"))?;
}
Ok(buf)
}
/// The inverse of [`encode_live_table`], through the IPC guard: hostile bytes
/// are an `Err`, never a panic or an allocation abort. `space_len` bounds the
/// ordinals: an entry naming one outside the space is refused.
pub fn decode_live_table(bytes: &[u8], space_len: u32) -> Result<ReachTable> {
use znippy_common::arrow::array::UInt32Array;
let reader = znippy_common::ipc_guard::stream_reader(bytes).map_err(|e| anyhow!("live reach reader: {e}"))?;
let mut out = ReachTable::default();
for batch in reader {
let batch = batch.map_err(|e| anyhow!("live reach batch read: {e}"))?;
let ords = batch
.column_by_name("commit_ordinal")
.and_then(|c| c.as_any().downcast_ref::<UInt32Array>())
.ok_or_else(|| anyhow!("live reach: no `commit_ordinal` column"))?;
let bms = batch
.column_by_name("bitmap")
.and_then(|c| c.as_any().downcast_ref::<BinaryArray>())
.ok_or_else(|| anyhow!("live reach: no `bitmap` column"))?;
for i in 0..batch.num_rows() {
let o = ords.value(i);
if o >= space_len {
return Err(anyhow!("live reach: commit ordinal {o} is outside the space ({space_len})"));
}
let bitmap = RoaringBitmap::deserialize_from(bms.value(i))
.map_err(|e| anyhow!("live reach bitmap deserialize: {e}"))?;
if bitmap.max().is_some_and(|m| m >= space_len) {
return Err(anyhow!("live reach: a bitmap names an ordinal outside the space ({space_len})"));
}
out.commits.push(o);
out.bitmaps.push(bitmap);
}
}
Ok(out)
}
#[cfg(test)]
mod carry_tests {
use super::*;
fn space(oids: &[u8]) -> Vec<u8> {
// 1-byte "oids" are enough for the arithmetic; the space is sorted.
let mut v = oids.to_vec();
v.sort_unstable();
v
}
/// The carry renumbers every bit through the remap, drops an entry whose
/// commit is gone, and refuses when a set bit's object is gone.
#[test]
fn a_carry_renumbers_bits_drops_dead_commits_and_refuses_a_missing_object() {
let old_raw = space(&[10, 20, 30, 40]);
let old = OrdinalSpace::new(&old_raw, 1);
// Two oids inserted below 30 and one above 40: ordinals shift by 2 and 2.
let new_raw = space(&[10, 15, 20, 25, 30, 40, 50]);
let new = OrdinalSpace::new(&new_raw, 1);
let entries = vec![
ReachEntry { commit: "keep".into(), bitmap: [0u32, 2, 3].into_iter().collect() },
ReachEntry { commit: "gone".into(), bitmap: [1u32].into_iter().collect() },
];
let carried = carry_reach(&entries, &old, &new, |c| c == "keep").expect("exact carry");
assert_eq!(carried.len(), 1, "the dead commit's entry is dropped, not carried");
assert_eq!(carried[0].commit, "keep");
let bits: Vec<u32> = carried[0].bitmap.iter().collect();
assert_eq!(bits, vec![0, 4, 5], "10→0, 30→4, 40→5 in the new numbering");
// An object removed from the space under a kept entry: refuse the carry.
let shrunk_raw = space(&[10, 20, 40]);
let shrunk = OrdinalSpace::new(&shrunk_raw, 1);
assert!(carry_reach(&entries, &old, &shrunk, |_| true).is_none(), "30 is gone; a bitmap naming it must not survive");
// Nothing to carry is not a carry.
assert!(carry_reach(&[], &old, &new, |_| true).is_none());
}
}
#[cfg(test)]
mod table_tests {
use super::*;
fn oid(i: u32) -> [u8; 20] {
let mut o = [0u8; 20];
// Spread the two fanout bytes so the prefix table does real work.
o[0] = (i.wrapping_mul(2654435761) >> 24) as u8;
o[1] = (i.wrapping_mul(40503) >> 8) as u8;
o[16..20].copy_from_slice(&i.to_be_bytes());
o
}
fn sorted_concat(ids: &[u32]) -> Vec<u8> {
let mut v: Vec<[u8; 20]> = ids.iter().map(|&i| oid(i)).collect();
v.sort_unstable();
v.dedup();
v.concat()
}
/// **Stable ordinals**: a follow appends behind the base and moves nothing;
/// every oid is found both ways through the fanout and the appended index;
/// a removed oid refuses the follow; the persisted form replays exactly.
/// Seen RED with `fanout[p+1]` off by one (misses in the last bucket) and
/// with `extra_sorted` left stale after a follow (appended oids absent).
#[test]
fn an_ordinal_table_appends_and_never_renumbers() {
let first: Vec<u32> = (0..3000).collect();
let mut t = OrdinalTable::from_sorted(sorted_concat(&first), 20);
assert_eq!(t.len(), 3000);
let v = t.view();
for o in 0..3000u32 {
let raw = v.oid(o).unwrap();
assert_eq!(v.ordinal_of_raw(raw), Some(o), "base inverse at {o}");
}
let before: Vec<[u8; 20]> = (0..3000u32).map(|o| v.oid(o).unwrap().try_into().unwrap()).collect();
// Push 1: 7 new oids.
let second: Vec<u32> = (0..3007).collect();
let r = t.follow(&sorted_concat(&second)).expect("a superset follows");
assert_eq!(r, 3000..3007);
assert_eq!(t.extra_len(), 7);
// Nothing moved.
let v = t.view();
for (o, raw) in before.iter().enumerate() {
assert_eq!(v.oid(o as u32), Some(raw.as_slice()), "ordinal {o} moved");
assert_eq!(v.ordinal_of_raw(raw), Some(o as u32));
}
for o in 3000..3007u32 {
let raw = v.oid(o).unwrap();
assert_eq!(v.ordinal_of_raw(raw), Some(o), "appended inverse at {o}");
}
// Push 2: no change is an empty range; then 5 more.
assert_eq!(t.follow(&sorted_concat(&second)), Some(3007..3007));
let third: Vec<u32> = (0..3012).collect();
assert_eq!(t.follow(&sorted_concat(&third)), Some(3007..3012));
let v = t.view();
assert_eq!(v.len(), 3012);
for o in 0..3012u32 {
assert_eq!(v.ordinal_of_raw(v.oid(o).unwrap()), Some(o));
}
assert_eq!(v.ordinal_of_raw(&oid(999_999)), None, "an absent oid is None, not a neighbour");
assert_eq!(v.ordinal_of_raw(&[0u8; 19]), None);
assert_eq!(v.oid(3012), None);
// The persisted form: (full sorted now, extra in arrival order).
let replay = OrdinalTable::from_parts(&sorted_concat(&third), t.extra_raw(), 20).expect("replays");
let (a, b) = (t.view(), replay.view());
for o in 0..3012u32 {
assert_eq!(a.oid(o), b.oid(o), "replayed ordinal {o} differs");
}
// An extra the store no longer holds does not replay.
let shrunk: Vec<u32> = (0..3011).collect();
assert!(OrdinalTable::from_parts(&sorted_concat(&shrunk), t.extra_raw(), 20).is_none());
// A removal under the table refuses the follow (a gc, a retain).
let mut gone: Vec<u32> = (0..3012).collect();
gone.remove(1500);
assert!(t.follow(&sorted_concat(&gone)).is_none(), "an oid the table numbers is gone");
let mut gone_extra: Vec<u32> = (0..3012).collect();
gone_extra.remove(3005);
assert!(t.follow(&sorted_concat(&gone_extra)).is_none(), "an appended oid is gone");
// The remap to a sorted space over the same oids is a permutation.
let sorted = sorted_concat(&third);
let target = OrdinalSpace::new(&sorted, 20);
let remap = t.remap_to(&target);
let mut seen: Vec<u32> = remap.clone();
seen.sort_unstable();
assert_eq!(seen, (0..3012u32).collect::<Vec<_>>());
for (o, &n) in remap.iter().enumerate() {
assert_eq!(t.view().oid(o as u32), target.oid(n));
}
}
/// The live table round-trips through its IPC form, and hostile bytes are
/// an `Err` (the ipc guard), including an ordinal outside the space.
#[test]
fn the_live_table_roundtrips_and_refuses_hostile_bytes() {
let t = ReachTable {
commits: vec![5, 9],
bitmaps: vec![[1u32, 5].into_iter().collect(), [0u32, 1, 5, 9].into_iter().collect()],
};
let bytes = encode_live_table(&t).unwrap();
assert_eq!(decode_live_table(&bytes, 10).unwrap(), t);
assert!(decode_live_table(&bytes, 9).is_err(), "ordinal 9 is outside a space of 9");
assert!(decode_live_table(b"not arrow at all, not even close to a stream", 10).is_err());
let mut torn = bytes.clone();
torn.truncate(bytes.len() / 2);
assert!(decode_live_table(&torn, 10).is_err());
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::graph::assign_generations;
fn hexid(c: char) -> String {
std::iter::repeat_n(c, 40).collect()
}
/// A flat, sorted, fixed-width ordinal buffer from oids **already in
/// ordinal order** — the shape [`OrdinalSpace`] borrows.
fn ordinal_raw(oids_in_order: &[&str]) -> Vec<u8> {
let mut v = Vec::new();
for o in oids_in_order {
v.extend_from_slice(&hex::decode(o).unwrap());
}
v
}
/// Returns (commits, facts-owned-data).
#[allow(clippy::type_complexity)]
fn tiny_repo() -> (Vec<CommitNode>, Vec<u8>, HashMap<String, Vec<u8>>) {
let blob1 = hexid('1');
let blob2 = hexid('2');
let tree1 = hexid('3');
let tree2 = hexid('4');
let c1 = hexid('5');
let c2 = hexid('6');
let mut trees: HashMap<String, Vec<u8>> = HashMap::new();
let mut t1 = Vec::new();
t1.extend_from_slice(b"100644 a\0");
t1.extend_from_slice(&hex::decode(&blob1).unwrap());
trees.insert(tree1.clone(), t1);
let mut t2 = Vec::new();
t2.extend_from_slice(b"100644 a\0");
t2.extend_from_slice(&hex::decode(&blob1).unwrap());
t2.extend_from_slice(b"100644 b\0");
t2.extend_from_slice(&hex::decode(&blob2).unwrap());
trees.insert(tree2.clone(), t2);
// Ordinal = oid-lexicographic rank: hexid('1') < … < hexid('6'), so the
// sorted raw buffer is simply these six in this order.
let ordinal = ordinal_raw(&[&blob1, &blob2, &tree1, &tree2, &c1, &c2]);
let commits = assign_generations(vec![
CommitNode {
oid: c1.clone(),
parents: vec![],
tree: Some(hexid('3')),
committer_time: Some(1),
generation: 0,
},
CommitNode {
oid: c2.clone(),
parents: vec![c1.clone()],
tree: Some(hexid('4')),
committer_time: Some(2),
generation: 0,
},
]);
(commits, ordinal, trees)
}
#[test]
fn bitmap_contains_exactly_the_reachable_objects() {
let (commits, ordinal, trees) = tiny_repo();
let facts = ObjectFacts { ordinal: OrdinalSpace::new(&ordinal, 20), trees: &trees, oid_len: 20 };
let entries = build_reach(&commits, &facts, ReachPolicy { max_commits: 16 });
let by_commit: HashMap<&str, &RoaringBitmap> =
entries.iter().map(|e| (e.commit.as_str(), &e.bitmap)).collect();
// c1 reaches: blob1(0), tree1(2), c1(4).
let b1: Vec<u32> = by_commit[hexid('5').as_str()].iter().collect();
assert_eq!(b1, vec![0, 2, 4], "c1 must not reach blob2/tree2/c2");
// c2 reaches everything.
let b2: Vec<u32> = by_commit[hexid('6').as_str()].iter().collect();
assert_eq!(b2, vec![0, 1, 2, 3, 4, 5]);
}
#[test]
fn want_minus_have_is_an_andnot() {
let (commits, ordinal, trees) = tiny_repo();
let facts = ObjectFacts { ordinal: OrdinalSpace::new(&ordinal, 20), trees: &trees, oid_len: 20 };
let entries = build_reach(&commits, &facts, ReachPolicy { max_commits: 16 });
let by: HashMap<&str, &RoaringBitmap> =
entries.iter().map(|e| (e.commit.as_str(), &e.bitmap)).collect();
let want = by[hexid('6').as_str()].clone();
let have = by[hexid('5').as_str()].clone();
let delta: Vec<u32> = (want - have).iter().collect();
// Exactly the objects the second commit introduced: blob2(1), tree2(3), c2(5).
assert_eq!(delta, vec![1, 3, 5]);
}
#[test]
fn selection_takes_tips_first_and_respects_the_cap() {
let (commits, ordinal, trees) = tiny_repo();
let facts = ObjectFacts { ordinal: OrdinalSpace::new(&ordinal, 20), trees: &trees, oid_len: 20 };
let entries = build_reach(&commits, &facts, ReachPolicy { max_commits: 1 });
assert_eq!(entries.len(), 1);
assert_eq!(entries[0].commit, hexid('6'), "the tip, not the root");
}
#[test]
fn batch_roundtrips_through_arrow_ipc() {
let (commits, ordinal, trees) = tiny_repo();
let facts = ObjectFacts { ordinal: OrdinalSpace::new(&ordinal, 20), trees: &trees, oid_len: 20 };
let entries = build_reach(&commits, &facts, ReachPolicy::default());
let batch = build_reach_batch(&entries).unwrap();
let mut buf = Vec::new();
{
let mut w = znippy_common::arrow::ipc::writer::StreamWriter::try_new(
&mut buf,
&reach_schema(),
)
.unwrap();
w.write(&batch).unwrap();
w.finish().unwrap();
}
let back = decode_reach(&buf).unwrap();
assert_eq!(back, entries);
}
#[test]
fn a_corrupt_tree_cycle_terminates() {
// t -> t (self-referential): must not hang or blow the stack.
let t = hexid('a');
let mut payload = Vec::new();
payload.extend_from_slice(b"40000 self\0");
payload.extend_from_slice(&hex::decode(&t).unwrap());
let trees: HashMap<String, Vec<u8>> = [(t.clone(), payload)].into_iter().collect();
let ordinal = ordinal_raw(&[&t, &hexid('b')]);
let facts = ObjectFacts { ordinal: OrdinalSpace::new(&ordinal, 20), trees: &trees, oid_len: 20 };
let commits = assign_generations(vec![CommitNode {
oid: hexid('b'),
parents: vec![],
tree: Some(t),
committer_time: None,
generation: 0,
}]);
let entries = build_reach(&commits, &facts, ReachPolicy::default());
assert_eq!(entries.len(), 1);
let bits: Vec<u32> = entries[0].bitmap.iter().collect();
assert_eq!(bits, vec![0, 1]);
}
/// **The binary search is the exact inverse of the slice, and it is the same
/// answer a `HashMap<String, u32>` over the sorted list would give.**
#[test]
fn ordinal_space_is_the_inverse_of_the_slice() {
// 32 distinct sha1-width oids, deliberately built OUT of order so the
// sort is doing real work, then sorted into the flat space.
let mut oids: Vec<[u8; 20]> = (0..32u8)
.map(|i| {
let mut o = [0u8; 20];
o[0] = i.wrapping_mul(37);
o[19] = i;
o
})
.collect();
oids.sort_unstable();
oids.dedup();
let mut raw = Vec::new();
for o in &oids {
raw.extend_from_slice(o);
}
let space = OrdinalSpace::new(&raw, 20);
assert_eq!(space.len(), oids.len());
for (o, oid) in oids.iter().enumerate() {
assert_eq!(space.oid(o as u32), Some(oid.as_slice()));
assert_eq!(space.ordinal_of_raw(oid), Some(o as u32));
assert_eq!(space.ordinal_of_hex(&hex::encode(oid)), Some(o as u32));
}
// Absent, wrong width, and out of range are all None — not a neighbour.
assert_eq!(space.ordinal_of_raw(&[0xffu8; 20]), None);
assert_eq!(space.ordinal_of_raw(&[0u8; 19]), None);
assert_eq!(space.oid(oids.len() as u32), None);
assert_eq!(space.ordinal_of_hex("not-hex"), None);
}
/// **The view owns nothing.** `OrdinalSpace` is a `Copy` view of borrowed
/// slices, so building one at open allocates zero bytes — the reason the
/// hex `Vec<String>` and the `HashMap<String, u32>` were removed. It grew
/// from one slice to four (the fanout and the appended part came with the
/// stable live space); red if an owned field creeps in or `Copy` is lost.
#[test]
fn ordinal_space_is_a_borrowed_view() {
assert_eq!(
std::mem::size_of::<OrdinalSpace<'_>>(),
4 * std::mem::size_of::<&[u8]>() + std::mem::size_of::<usize>(),
"OrdinalSpace grew an owned field — it must stay a borrow"
);
fn assert_copy<T: Copy>() {}
assert_copy::<OrdinalSpace<'_>>();
}
// ── property tests: bitmap = graph walk, on random DAGs ─────────────────
/// A deterministic xorshift, so a failing seed is reproducible.
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
let mut x = self.0;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.0 = x;
x
}
fn below(&mut self, n: usize) -> usize {
(self.next() % n.max(1) as u64) as usize
}
}
/// A synthetic repository with a real object graph: nested trees, shared
/// blobs, merges and unrelated roots.
struct Dag {
nodes: Vec<CommitNode>,
/// Every object: oid → (kind, payload). Trees and commits carry
/// pointers; blobs are leaves.
objects: HashMap<Vec<u8>, (GitObjectKind, Vec<u8>)>,
sorted: Vec<u8>,
trees: HashMap<Vec<u8>, Vec<u8>>,
}
fn fake_oid(rng: &mut Rng) -> Vec<u8> {
let mut o = vec![0u8; 20];
for b in o.iter_mut() {
*b = rng.next() as u8;
}
o
}
fn random_dag(seed: u64, commits: usize) -> Dag {
let mut rng = Rng(seed | 1);
let mut objects: HashMap<Vec<u8>, (GitObjectKind, Vec<u8>)> = HashMap::new();
let mut blobs: Vec<Vec<u8>> = Vec::new();
let mut subtrees: Vec<Vec<u8>> = Vec::new();
let mut trees: HashMap<Vec<u8>, Vec<u8>> = HashMap::new();
let new_tree = |rng: &mut Rng,
objects: &mut HashMap<Vec<u8>, (GitObjectKind, Vec<u8>)>,
blobs: &mut Vec<Vec<u8>>,
subtrees: &[Vec<u8>],
trees: &mut HashMap<Vec<u8>, Vec<u8>>|
-> Vec<u8> {
let mut payload = Vec::new();
let entries = 1 + rng.below(4);
for e in 0..entries {
// Reuse a blob 50 % of the time, else make one.
let blob = if !blobs.is_empty() && rng.below(2) == 0 {
blobs[rng.below(blobs.len())].clone()
} else {
let b = fake_oid(rng);
objects.insert(b.clone(), (GitObjectKind::Blob, vec![e as u8]));
blobs.push(b.clone());
b
};
payload.extend_from_slice(format!("100644 f{e}\0").as_bytes());
payload.extend_from_slice(&blob);
}
if !subtrees.is_empty() && rng.below(3) == 0 {
let st = &subtrees[rng.below(subtrees.len())];
payload.extend_from_slice(b"40000 d\0");
payload.extend_from_slice(st);
}
if rng.below(7) == 0 {
// A gitlink: a commit in another repository, not in this space.
payload.extend_from_slice(b"160000 sub\0");
payload.extend_from_slice(&fake_oid(rng));
}
let t = fake_oid(rng);
objects.insert(t.clone(), (GitObjectKind::Tree, payload.clone()));
trees.insert(t.clone(), payload);
t
};
let mut nodes: Vec<CommitNode> = Vec::new();
for i in 0..commits {
let tree = new_tree(&mut rng, &mut objects, &mut blobs, &subtrees, &mut trees);
if rng.below(2) == 0 {
subtrees.push(tree.clone());
}
let mut parents = Vec::new();
if i > 0 && rng.below(5) != 0 {
parents.push(nodes[rng.below(i)].oid.clone());
if i > 1 && rng.below(4) == 0 {
parents.push(nodes[rng.below(i)].oid.clone());
}
}
let oid = fake_oid(&mut rng);
let mut payload = format!("tree {}\n", hex::encode(&tree)).into_bytes();
for p in &parents {
payload.extend_from_slice(format!("parent {p}\n").as_bytes());
}
objects.insert(oid.clone(), (GitObjectKind::Commit, payload));
nodes.push(CommitNode {
oid: hex::encode(&oid),
parents,
tree: Some(hex::encode(&tree)),
committer_time: Some(i as i64),
generation: 0,
});
}
let mut all: Vec<&Vec<u8>> = objects.keys().collect();
all.sort_unstable();
let sorted: Vec<u8> = all.iter().flat_map(|o| o.iter().copied()).collect();
Dag { nodes: assign_generations(nodes), objects, sorted, trees }
}
/// The oracle: a plain object walk from `tip`, over the object map.
fn walk_closure(dag: &Dag, tip: &[u8]) -> std::collections::BTreeSet<Vec<u8>> {
let mut seen = std::collections::BTreeSet::new();
let mut stack = vec![tip.to_vec()];
while let Some(o) = stack.pop() {
let Some((kind, payload)) = dag.objects.get(&o) else { continue };
if !seen.insert(o.clone()) {
continue;
}
match kind {
GitObjectKind::Commit => {
for line in payload.split(|b| *b == b'\n') {
if let Some(h) = line.strip_prefix(b"tree ").or_else(|| line.strip_prefix(b"parent ")) {
stack.push(hex::decode(h).unwrap());
}
}
}
GitObjectKind::Tree => {
for e in tree_entries(payload, 20) {
stack.push(e.oid.to_vec());
}
}
_ => {}
}
}
seen
}
fn bits_as_oids(bm: &RoaringBitmap, space: &OrdinalSpace<'_>) -> std::collections::BTreeSet<Vec<u8>> {
bm.iter().map(|o| space.oid(o).unwrap().to_vec()).collect()
}
/// **Every stored bitmap equals the graph walk, at every cap, on random
/// DAGs** — the full builder, and the walk-covered answer for every commit
/// with or without an entry.
#[test]
fn the_full_table_equals_a_graph_walk_on_random_dags() {
for seed in 1..=24u64 {
let n = 1 + (seed as usize * 7) % 60;
let dag = random_dag(seed, n);
let space = OrdinalSpace::new(&dag.sorted, 20);
let facts = ObjectFacts { ordinal: space, trees: &dag.trees, oid_len: 20 };
let graph = OrdGraph::from_nodes(&dag.nodes, &space);
for cap in [usize::MAX, 1, 3, 7] {
let table = build_reach_table(&graph, &facts, ReachPolicy { max_commits: cap });
let by_row = table.by_row(&graph);
let view = ReachView { table: &table, by_row: &by_row, graph: &graph };
for (i, &o) in table.commits.iter().enumerate() {
let oracle = walk_closure(&dag, space.oid(o).unwrap());
assert_eq!(bits_as_oids(&table.bitmaps[i], &space), oracle, "seed {seed} cap {cap}: stored entry {i}");
}
// Every commit, bitmapped or not, through the bounded walk.
for row in 0..graph.len() as u32 {
let mut acc = RoaringBitmap::new();
accumulate(row, &view, &facts, &mut acc);
let oracle = walk_closure(&dag, space.oid(graph.ords[row as usize]).unwrap());
assert_eq!(bits_as_oids(&acc, &space), oracle, "seed {seed} cap {cap}: walk from row {row}");
}
}
}
}
/// **A table extended after a "push" equals a table built from scratch**,
/// on random DAGs split into an old and a new part, over a stable
/// (appended) ordinal space: entries for the new tips are exact, old
/// entries are untouched, and the walk from every commit still equals the
/// oracle.
#[test]
fn an_extended_table_equals_a_graph_walk_on_random_dags() {
for seed in 1..=24u64 {
let n = 4 + (seed as usize * 11) % 70;
let dag = random_dag(seed * 7919, n);
// The old part: the first k commits (in generation order they are
// closed under parents only if we take a prefix of the ORIGINAL
// creation order, so take the objects reachable from the first k
// tips of creation order instead).
let k = 1 + (seed as usize) % (n - 1);
let old_nodes: Vec<CommitNode> = dag.nodes.iter().filter(|c| c.committer_time.unwrap() < k as i64).cloned().collect();
let mut old_objs: std::collections::BTreeSet<Vec<u8>> = std::collections::BTreeSet::new();
for c in &old_nodes {
old_objs.extend(walk_closure(&dag, &hex::decode(&c.oid).unwrap()));
}
let old_sorted: Vec<u8> = old_objs.iter().flat_map(|o| o.iter().copied()).collect();
let mut table_space = OrdinalTable::from_sorted(old_sorted, 20);
let old_graph = OrdGraph::from_nodes(&old_nodes, &table_space.view());
let facts_old = ObjectFacts { ordinal: table_space.view(), trees: &dag.trees, oid_len: 20 };
let policy = ReachPolicy { max_commits: 5 };
let old_table = build_reach_table(&old_graph, &facts_old, policy);
// The push: the rest arrives; the space appends.
let appended = table_space.follow(&dag.sorted).expect("a superset follows");
let space = table_space.view();
let graph = OrdGraph::from_nodes(&dag.nodes, &space);
let facts = ObjectFacts { ordinal: space, trees: &dag.trees, oid_len: 20 };
let new_rows: Vec<u32> = (0..graph.len() as u32).filter(|&r| graph.ords[r as usize] >= appended.start).collect();
let table = extend_reach_table(&old_table, &graph, &facts, &new_rows, policy);
// Old entries untouched (an entry may be PRUNED once the table
// outgrows twice the cap — never rewritten), new tips covered.
assert!(table.len() <= 2 * policy.max_commits, "seed {seed}: the table outgrew twice the cap");
for (i, &o) in old_table.commits.iter().enumerate() {
if let Some(j) = table.commits.iter().position(|&c| c == o) {
assert_eq!(table.bitmaps[j], old_table.bitmaps[i], "seed {seed}: old entry rewritten");
}
}
let by_row = table.by_row(&graph);
// Every new tip has an entry, unless the cap forced a prune (then
// at least `max` entries stand and the walk covers the rest).
for r in graph.tip_rows() {
if new_rows.contains(&r) && table.len() < policy.max_commits {
assert_ne!(by_row[r as usize], NONE, "seed {seed}: new tip row {r} has no entry");
}
}
let view = ReachView { table: &table, by_row: &by_row, graph: &graph };
for (i, &o) in table.commits.iter().enumerate() {
let oracle = walk_closure(&dag, space.oid(o).unwrap());
assert_eq!(bits_as_oids(&table.bitmaps[i], &space), oracle, "seed {seed}: extended entry {i}");
}
for row in 0..graph.len() as u32 {
let mut acc = RoaringBitmap::new();
accumulate(row, &view, &facts, &mut acc);
let oracle = walk_closure(&dag, space.oid(graph.ords[row as usize]).unwrap());
assert_eq!(bits_as_oids(&acc, &space), oracle, "seed {seed}: walk from row {row} after the extension");
}
// And the sealed spelling, renumbered into the sorted space, equals
// a sealed build over the same nodes.
let sorted_space = OrdinalSpace::new(&dag.sorted, 20);
let remap = table_space.remap_to(&sorted_space);
let sealed = table.to_entries(&sorted_space, Some(&remap)).expect("exact remap");
for e in &sealed {
let oracle = walk_closure(&dag, &hex::decode(&e.commit).unwrap());
assert_eq!(bits_as_oids(&e.bitmap, &sorted_space), oracle, "seed {seed}: sealed entry {}", e.commit);
}
}
}
}