crates/storage-git-gix/parked-gix-2/gunnar-store-gix/src/pathwalk.rs
//! **Which objects the delta window is allowed to see each other.**
//!
//! An encoder can only find a base it is shown. `gunnar-delta` shows each object
//! the `window` objects nearest it in sort order, and until this module existed
//! that order was `(kind, size descending, id)` — so the previous revision of a
//! file was a candidate only if it happened to be within ten objects of it *by
//! size*, across the entire repository. git has not done that since 2006: it
//! sorts by a hash of the object's **path** first, which is what puts one file's
//! own history in one window.
//!
//! # What the key is worth, measured by the people who changed it
//!
//! `git repack -adf`, same repository, nothing changed but the ordering:
//!
//! | change | repository | before | after |
//! |---|---|---:|---:|
//! | `--name-hash-version=2` | microsoft/fluentui | 439 MiB | **160 MiB**, and 96 s → **34 s** |
//! | `--path-walk` | microsoft/fluentui | 438 MB | **148 MB** |
//! | `--path-walk` | a private monorepo | 130 049 MB | **4 432 MB** |
//!
//! MEASURED BY Jonathan Blau and Derrick Stolee respectively; quoted, not
//! reproduced. `.nornir/git-research-reasoning.md` carries the citations. What
//! gunnar gets from it is not a guess either way — the bench rows in this
//! change's report are gunnar's own.
//!
//! **Why it transfers to the wire.** gunnar's serve path copies pack entries
//! verbatim (`P-001`): it never computes a delta and never will. So the deltas
//! in the repository's pack *are* the deltas on the wire, for every clone and
//! every fetch, for as long as that pack lives. The repacker's ordering is
//! therefore not a storage optimisation with a serving side-effect; it is the
//! only place gunnar's wire compression is ever decided.
//!
//! # This is a walk, and it has to be
//!
//! A hash of a path needs a path, and a git object does not carry one: the same
//! blob is `README.md` in one tree and `docs/README.md` in another. The path
//! comes from the trees that name it, so this module walks refs → commits →
//! trees → entries and records, for each object, **the first path it was seen
//! at**. That is git's rule too (`add_object_entry` keeps the name it was
//! created with) and it is the only one that terminates: a blob reachable at a
//! thousand paths is visited once.
//!
//! The walk is linear in *distinct* objects, not in commits × tree size,
//! because a tree already visited is not descended into again. That is the
//! whole cost model: one decode per tree, one map insert per entry.
//!
//! # Commits and tags get nothing, on purpose
//!
//! They have no path. They hash to `0`, which is `gunnar_delta::Object`'s
//! documented "no information" value, and objects carrying `0` fall back to the
//! size ordering among themselves — exactly the search that existed before.
//! git does the same. A commit deltas well against another commit anyway,
//! because commits are near-identical in shape.
use std::collections::{HashMap, HashSet};
use gix_hash::ObjectId;
use gix_object::{CommitRefIter, Kind, TagRefIter, TreeRefIter};
use crate::error::Result;
use crate::object::ObjectStore;
use crate::repack::DeltaOrder;
/// What the walk produced: one number per object, and how it was reached.
///
/// A struct rather than a bare map because the counts are what a caller reports
/// and a test asserts on. A walk that visited nothing returns zeroes rather than
/// an empty silence, and `paths` distinguishes "every object hashed to 0
/// because there were no trees" from "the walk was not run".
#[derive(Debug, Default)]
pub struct Grouping {
/// Object id → sort key. An object absent from this map sorts as `0`.
hashes: HashMap<ObjectId, u32>,
/// Object id → how new it is, larger being newer. Empty for every order
/// that does not ask for it, and an object absent from it sorts as `0`,
/// which is `gunnar_delta::Object::epoch`'s documented "no information".
epochs: HashMap<ObjectId, u32>,
/// Distinct paths seen. `0` for [`DeltaOrder::Size`].
pub paths: usize,
/// Objects that came out with a non-zero key, i.e. that the ordering can
/// actually group. This is the applied output: a walk that ran, found the
/// trees undecodable and silently grouped nothing would report `0` here
/// while every other number looked healthy.
pub grouped: usize,
/// Root trees the walk descended, i.e. **how much history there was to
/// date**.
///
/// It separates the two ways [`Self::aged`] can be `0`, and they are not
/// the same situation at all:
///
/// * `roots == 0` — no reference reached a commit or a tree. There is
/// nothing to date and nothing to name, so *every* ordering degenerates
/// to size-descending, `NameHashV2` included. That is this crate's
/// documented contract for "no information" and it is what a repository
/// holding loose objects and no reference legitimately is.
/// * `roots > 0 && aged() == 0` — there was history and the walk did not
/// date it. That is a broken walk, and it is the state
/// [`crate::repack`] refuses on.
///
/// Without this number the two are indistinguishable, and the refusal fires
/// on the first — which made `gunnar gc` fail on three legitimate fixtures
/// the moment `TransferV2` became the default on 2026-08-04.
pub roots: usize,
}
impl Grouping {
/// Both numbers for one object; `0` for either when the walk never reached
/// it, or when this ordering does not compute it.
pub fn get(&self, id: &ObjectId) -> gunnar_pack::OrderKey {
gunnar_pack::OrderKey {
name_hash: self.hashes.get(id).copied().unwrap_or(0),
epoch: self.epochs.get(id).copied().unwrap_or(0),
}
}
/// Objects that came out with a non-zero epoch. The applied output for the
/// half of the walk that is about *time* rather than about paths: a
/// repository whose commits carry no usable dates would report a healthy
/// `grouped` and a zero here, and the ordering would silently degrade to
/// the one it was meant to replace.
pub fn aged(&self) -> usize {
self.epochs.len()
}
/// Nothing was walked. Every object sorts by size, as before.
pub fn none() -> Self {
Self::default()
}
}
/// Walk `tips` and give every tree and blob under them a sort key.
///
/// # Errors
///
/// Never for a missing object. A repack must not be refused because one
/// reference dangles: reachability is [`crate::connectivity`]'s job and it has
/// its own error for exactly that, with the referrer attached. Here a missing
/// or undecodable object simply contributes no key, so the objects under it
/// sort by size and the repack proceeds. The only error returned is a store
/// failure that is not about a particular object.
pub fn group<S>(objects: &S, tips: &[ObjectId], order: DeltaOrder) -> Result<Grouping>
where
S: ObjectStore + ?Sized,
{
if !order.needs_paths() {
return Ok(Grouping::none());
}
let mut out = Grouping::default();
// Interning table, only for `PathWalk`: path bytes → dense id. Ids start at
// 1, because 0 is the "no information" value and the root tree's own path
// is the empty string.
let mut intern: HashMap<Vec<u8>, u32> = HashMap::new();
// Trees already descended into. A tree reachable from a thousand commits is
// decoded once; without this the walk is commits × tree size and would be
// slower than the delta search it feeds.
let mut seen_trees: HashSet<ObjectId> = HashSet::new();
// Commits and tags already followed.
let mut seen_commits: HashSet<ObjectId> = HashSet::new();
// Root trees to descend, each with the committer time of the commit that
// named it. The time is `0` for every order that does not want epochs, and
// those orders never sort on it, so their walk order is exactly what it was.
let mut roots: Vec<(i64, ObjectId)> = Vec::new();
let mut pending: Vec<ObjectId> = tips.to_vec();
let mut buf = Vec::with_capacity(8 * 1024);
while let Some(id) = pending.pop() {
if !seen_commits.insert(id) {
continue;
}
let Some(data) = objects.read(&id, &mut buf)? else {
continue;
};
match data.kind {
Kind::Commit => {
let when = if order.needs_epochs() {
// The committer line, and only of commits. Commits are a
// small fraction of a repository's objects and the trees
// under them are decoded anyway. A commit whose signature
// does not parse dates to `0`, which sorts it first: it can
// then be a base for anything and a delta of nothing, which
// is the direction that cannot make a fetch worse.
CommitRefIter::from_bytes(data.data, data.object_hash)
.committer()
.map(|c| c.time().map(|t| t.seconds).unwrap_or(0))
.unwrap_or(0)
} else {
0
};
let mut iter = CommitRefIter::from_bytes(data.data, data.object_hash);
let Ok(tree) = iter.tree_id() else { continue };
roots.push((when, tree));
for token in iter {
match token {
Ok(gix_object::commit::ref_iter::Token::Parent { id: parent }) => {
pending.push(parent)
}
Ok(_) => break,
Err(_) => break,
}
}
}
Kind::Tag => {
if let Ok(target) = TagRefIter::from_bytes(data.data, data.object_hash).target_id()
{
pending.push(target);
}
}
// A ref pointing straight at a tree or a blob. Rare, legal, and the
// tree still names paths. It has no commit and so no date; `0` puts
// it first, which is the conservative end -- it can be a base for
// anything and a delta of nothing.
Kind::Tree => roots.push((0, id)),
Kind::Blob => {}
}
}
// OLDEST FIRST, and this is the whole of the transfer ordering.
//
// `assign` is first-path-wins, so whichever root reaches an object first is
// the one that dates it. Descending in ascending commit time therefore
// stamps every object with the OLDEST commit that contains it, and the
// encoder's ascending epoch key then makes the older revision of a file the
// base and the newer one the delta -- which is the direction a fetch is
// sent in. `sort_by_key` is stable, so ties keep the walk's own order and
// an unchanged repository still repacks reproducibly.
if order.needs_epochs() {
roots.sort_by_key(|(when, _)| *when);
}
out.roots = roots.len();
for (rank, (_, root)) in roots.into_iter().enumerate() {
// The rank, not the timestamp. A timestamp is attacker-supplied, can
// run backwards across a rebase and does not fit a `u32` past 2106;
// the rank is dense, monotone in the order actually walked, and is what
// the sort key compares.
let epoch = if order.needs_epochs() {
(rank as u32).saturating_add(1)
} else {
0
};
descend(
objects,
root,
order,
epoch,
&mut intern,
&mut seen_trees,
&mut out,
&mut buf,
)?;
}
out.paths = match order {
DeltaOrder::PathWalk => intern.len(),
_ => out.grouped,
};
Ok(out)
}
/// Descend one tree, naming everything under it.
///
/// Iterative rather than recursive: a hand-built repository can nest trees
/// arbitrarily deep, and a stack overflow inside a `gc` is a crash in the one
/// operation that is holding the store's writer lock.
#[allow(clippy::too_many_arguments)]
fn descend<S>(
objects: &S,
root: ObjectId,
order: DeltaOrder,
epoch: u32,
intern: &mut HashMap<Vec<u8>, u32>,
seen_trees: &mut HashSet<ObjectId>,
out: &mut Grouping,
buf: &mut Vec<u8>,
) -> Result<()>
where
S: ObjectStore + ?Sized,
{
// (tree id, the path it is at). Owned paths, because the tree's own bytes
// are re-read into `buf` at every level and cannot be borrowed across one.
let mut stack: Vec<(ObjectId, Vec<u8>)> = vec![(root, Vec::new())];
while let Some((id, path)) = stack.pop() {
if !seen_trees.insert(id) {
continue;
}
let Some(data) = objects.read(&id, buf)? else {
continue;
};
if data.kind != Kind::Tree {
continue;
}
// The tree itself is named too, and by its own path: two revisions of
// one directory are as deltifiable as two revisions of one file, and
// in a repository with deep history the trees are most of the objects.
assign(out, intern, order, epoch, &id, &path);
let mut entries = Vec::new();
for entry in TreeRefIter::from_bytes(data.data, data.object_hash) {
let Ok(entry) = entry else { break };
entries.push((entry.mode, entry.filename.to_vec(), entry.oid.to_owned()));
}
// `buf` is free again from here.
for (mode, filename, oid) in entries {
// A gitlink names a commit in another repository, which this one is
// not expected to hold. `connectivity` does not follow them either.
if mode.is_commit() {
continue;
}
let mut child = path.clone();
if !child.is_empty() {
child.push(b'/');
}
child.extend_from_slice(&filename);
if mode.is_tree() {
stack.push((oid, child));
} else {
assign(out, intern, order, epoch, &oid, &child);
}
}
}
Ok(())
}
/// Record one object's key, **first path wins**.
///
/// First rather than last, and it matters: last-wins would make the key depend
/// on the order the reference set happens to be walked in, so two repacks of an
/// unchanged repository could produce different packs. It is also git's rule.
fn assign(
out: &mut Grouping,
intern: &mut HashMap<Vec<u8>, u32>,
order: DeltaOrder,
epoch: u32,
id: &ObjectId,
path: &[u8],
) {
if out.hashes.contains_key(id) {
return;
}
if epoch != 0 {
out.epochs.insert(*id, epoch);
}
let key = match order {
DeltaOrder::Size => return,
DeltaOrder::NameHashV1 => gunnar_pack::name_hash::v1(path),
DeltaOrder::NameHashV2 | DeltaOrder::TransferV2 => gunnar_pack::name_hash::v2(path),
DeltaOrder::PathWalk => {
// Dense ids, assigned in walk order, starting at 1. Deterministic
// for a fixed repository because the walk is.
let next = intern.len() as u32 + 1;
*intern.entry(path.to_vec()).or_insert(next)
}
};
if key != 0 {
out.grouped += 1;
}
out.hashes.insert(*id, key);
}
#[cfg(test)]
mod tests {
use super::*;
use crate::mem::MemObjectStore;
const HASH: gix_hash::Kind = gix_hash::Kind::Sha1;
/// Build `dir/a.txt`, `dir/b.txt` and `other/a.txt` in one commit and check
/// the walk names all three, and names them differently where it should.
///
/// This is the assertion the whole lever rests on: if two revisions of one
/// file do not come out with the same key, nothing downstream can group
/// them, and every byte of the published measurement is unavailable.
#[test]
fn the_walk_names_a_blob_by_the_path_that_reaches_it() {
let store = MemObjectStore::new(HASH);
let a = store.write(Kind::Blob, b"aaaa").unwrap();
let b = store.write(Kind::Blob, b"bbbb").unwrap();
let dir = tree(
&store,
&[(b"100644", b"a.txt", a), (b"100644", b"b.txt", b)],
);
let root = tree(&store, &[(b"40000", b"dir", dir)]);
let commit = commit(&store, root);
let g = group(&store, &[commit], DeltaOrder::NameHashV2).unwrap();
assert_eq!(
g.get(&a).name_hash,
gunnar_pack::name_hash::v2(b"dir/a.txt"),
"the key must be the hash of the real path, not of the file name \
alone and not of nothing"
);
assert_eq!(
g.get(&b).name_hash,
gunnar_pack::name_hash::v2(b"dir/b.txt")
);
assert_ne!(
g.get(&a).name_hash,
g.get(&b).name_hash,
"different names, different groups"
);
assert_eq!(g.get(&dir).name_hash, gunnar_pack::name_hash::v2(b"dir"));
assert_eq!(g.get(&commit).name_hash, 0, "a commit has no path");
assert_eq!(
g.get(&root).name_hash,
0,
"the root tree's path is the empty string"
);
assert_eq!(g.grouped, 3, "two blobs and the one named tree");
}
/// Two revisions of one file must come out with the **same** key, or
/// nothing downstream can put them in one window and the whole lever is
/// worth nothing. This is the assertion that fails if `assign` ever starts
/// mixing the object id into the key.
#[test]
fn the_same_path_at_two_revisions_shares_a_key() {
let store = MemObjectStore::new(HASH);
let old = store.write(Kind::Blob, b"version one").unwrap();
let new = store.write(Kind::Blob, b"version two").unwrap();
let t_old = tree(&store, &[(b"100644", b"f.rs", old)]);
let t_new = tree(&store, &[(b"100644", b"f.rs", new)]);
let c_old = commit(&store, t_old);
let c_new = commit_with_parent(&store, t_new, c_old);
let g = group(&store, &[c_new], DeltaOrder::NameHashV2).unwrap();
assert_ne!(g.get(&old).name_hash, 0);
assert_eq!(g.get(&old).name_hash, g.get(&new).name_hash);
}
/// `Size` must not walk. A key that cost a full tree traversal and then
/// grouped nothing would be the worst of both.
#[test]
fn the_size_order_walks_nothing() {
let store = MemObjectStore::new(HASH);
let a = store.write(Kind::Blob, b"aaaa").unwrap();
let root = tree(&store, &[(b"100644", b"a.txt", a)]);
let commit = commit(&store, root);
let g = group(&store, &[commit], DeltaOrder::Size).unwrap();
assert_eq!(g.grouped, 0);
assert_eq!(g.get(&a).name_hash, 0);
}
/// Distinct paths get distinct dense ids, and the same path gets the same
/// one. Without the second half `PathWalk` would group nothing at all.
#[test]
fn path_walk_ids_are_dense_and_distinct() {
let store = MemObjectStore::new(HASH);
let a = store.write(Kind::Blob, b"aaaa").unwrap();
let b = store.write(Kind::Blob, b"bbbb").unwrap();
let root = tree(
&store,
&[(b"100644", b"a.txt", a), (b"100644", b"b.txt", b)],
);
let commit = commit(&store, root);
let g = group(&store, &[commit], DeltaOrder::PathWalk).unwrap();
assert_ne!(g.get(&a).name_hash, g.get(&b).name_hash);
assert_ne!(g.get(&a).name_hash, 0);
assert_ne!(g.get(&b).name_hash, 0);
// "" (the root tree), "a.txt", "b.txt".
assert_eq!(g.paths, 3);
}
/// The whole of the transfer ordering: the OLDER revision of a file must
/// come out with the SMALLER epoch, so that the encoder's ascending key
/// makes it the base and the newer revision its delta.
///
/// The tips are given newest-first, which is the order a real ref set
/// arrives in and the order the walk would otherwise keep — so a walk that
/// forgot to sort by date would date the NEW blob first and this fails.
///
/// **Red-first**: delete the `roots.sort_by_key` in [`group`] and the
/// epochs come out the other way round. Proven on 2026-08-04.
#[test]
fn the_transfer_order_dates_the_older_revision_first() {
let store = MemObjectStore::new(HASH);
let old = store.write(Kind::Blob, b"version one").unwrap();
let new = store.write(Kind::Blob, b"version two").unwrap();
let t_old = tree(&store, &[(b"100644", b"f.rs", old)]);
let t_new = tree(&store, &[(b"100644", b"f.rs", new)]);
let c_old = commit_at(&store, t_old, None, 1_700_000_000);
let c_new = commit_at(&store, t_new, Some(c_old), 1_700_009_999);
let g = group(&store, &[c_new], DeltaOrder::TransferV2).unwrap();
assert_ne!(g.get(&old).epoch, 0, "the older blob was never dated");
assert_ne!(g.get(&new).epoch, 0, "the newer blob was never dated");
assert!(
g.get(&old).epoch < g.get(&new).epoch,
"the older revision must carry the smaller epoch: old={} new={}",
g.get(&old).epoch,
g.get(&new).epoch
);
assert!(
g.aged() >= 2,
"aged() must count what was dated, got {}",
g.aged()
);
// The grouping half is untouched: both revisions still share a window.
assert_eq!(g.get(&old).name_hash, g.get(&new).name_hash);
}
/// Every other ordering must leave the epoch at `0`, which is the value the
/// encoder reads as "no information" and which reduces its key to exactly
/// what it was. Without this, adding the field would silently change
/// `NameHashV2`'s output and this change's numbers would not be about the
/// thing they name.
#[test]
fn only_the_transfer_order_dates_anything() {
let store = MemObjectStore::new(HASH);
let a = store.write(Kind::Blob, b"aaaa").unwrap();
let root = tree(&store, &[(b"100644", b"a.txt", a)]);
let c = commit_at(&store, root, None, 1_700_000_000);
for order in [
DeltaOrder::Size,
DeltaOrder::NameHashV1,
DeltaOrder::NameHashV2,
DeltaOrder::PathWalk,
] {
let g = group(&store, &[c], order).unwrap();
assert_eq!(g.aged(), 0, "{order:?} dated objects it will never read");
assert_eq!(
g.get(&a).epoch,
0,
"{order:?} put a non-zero epoch on an object"
);
}
let g = group(&store, &[c], DeltaOrder::TransferV2).unwrap();
assert_ne!(
g.aged(),
0,
"the transfer order dated nothing, so its key is dead"
);
}
/// `roots` counts the history there was to date, and it is what separates
/// "this repository has no commits" from "the walk failed to date the
/// commits it had".
///
/// Those are the two ways `aged()` can be `0`, and [`crate::repack`]
/// refuses on one and proceeds on the other. Before this number existed
/// they were indistinguishable, and the refusal fired on the legitimate one
/// — which broke `gunnar gc` on three fixtures the day `TransferV2` became
/// the default.
///
/// **Seen red on 2026-08-04**: return `Ok(out)` before the `out.roots =`
/// line and the reference-less case and the commit-bearing case report the
/// same `roots = 0`, which fails the second assertion here.
#[test]
fn roots_separates_an_empty_repository_from_a_failed_walk() {
let store = MemObjectStore::new(HASH);
let a = store.write(Kind::Blob, b"aaaa").unwrap();
// No tip at all: a repository holding loose objects and no reference.
// Nothing to date, nothing to name, every ordering degenerate — and
// that is legitimate, not a fault.
let empty = group(&store, &[], DeltaOrder::TransferV2).unwrap();
assert_eq!(empty.roots, 0, "a walk with no tips descended a root tree");
assert_eq!(empty.aged(), 0);
assert_eq!(empty.grouped, 0);
// One commit: there IS history, and the walk dated it.
let root = tree(&store, &[(b"100644", b"a.txt", a)]);
let c = commit_at(&store, root, None, 1_700_000_000);
let full = group(&store, &[c], DeltaOrder::TransferV2).unwrap();
assert_eq!(full.roots, 1, "the commit's root tree was not counted");
assert_ne!(
full.aged(),
0,
"roots were descended and nothing was dated, which is the state \
repack refuses on — if this ever fires, the refusal is doing its job"
);
// The invariant the refusal rests on, stated as an implication rather
// than an equality: `aged()` and `grouped` are NOT the same count and
// must not be asserted equal — the root tree's own path is the empty
// string, so it hashes to `0` and is dated but not named, and this
// fixture reports `aged() == 2` against `grouped == 1`. What holds is
// that a walk which descended a root dated at least that root.
assert!(
full.roots == 0 || full.aged() >= full.roots,
"the walk descended {} roots and dated {} objects, so \
`roots > 0 && aged() == 0` — the state repack refuses on — is \
reachable from a healthy walk and the refusal would fire on \
correct input",
full.roots,
full.aged()
);
}
/// A gitlink names a commit in another repository. Descending into it would
/// report a missing object on every repository with a submodule.
#[test]
fn a_submodule_entry_is_not_followed() {
let store = MemObjectStore::new(HASH);
let absent = gix_hash::ObjectId::empty_tree(HASH);
let root = tree(&store, &[(b"160000", b"sub", absent)]);
let commit = commit(&store, root);
let g = group(&store, &[commit], DeltaOrder::NameHashV2).unwrap();
assert_eq!(g.grouped, 0, "the gitlink itself is not named either");
}
// ── fixture helpers, raw bytes as `connectivity`'s own tests do ─────────
fn tree(store: &MemObjectStore, entries: &[(&[u8], &[u8], ObjectId)]) -> ObjectId {
let mut out = Vec::new();
for (mode, name, oid) in entries {
out.extend_from_slice(mode);
out.push(b' ');
out.extend_from_slice(name);
out.push(0);
out.extend_from_slice(oid.as_bytes());
}
store.write(Kind::Tree, &out).unwrap()
}
fn commit(store: &MemObjectStore, tree: ObjectId) -> ObjectId {
commit_bytes(store, tree, None)
}
fn commit_with_parent(store: &MemObjectStore, tree: ObjectId, parent: ObjectId) -> ObjectId {
commit_bytes(store, tree, Some(parent))
}
fn commit_at(
store: &MemObjectStore,
tree: ObjectId,
parent: Option<ObjectId>,
when: i64,
) -> ObjectId {
let parent = match parent {
Some(p) => format!("parent {}\n", p.to_hex()),
None => String::new(),
};
let text = format!(
"tree {}\n{parent}author A <a@example.invalid> {when} +0000\n\
committer A <a@example.invalid> {when} +0000\n\nc\n",
tree.to_hex()
);
store.write(Kind::Commit, text.as_bytes()).unwrap()
}
fn commit_bytes(store: &MemObjectStore, tree: ObjectId, parent: Option<ObjectId>) -> ObjectId {
let parent = match parent {
Some(p) => format!("parent {}\n", p.to_hex()),
None => String::new(),
};
let text = format!(
"tree {}\n{parent}author A <a@example.invalid> 1700000000 +0000\n\
committer A <a@example.invalid> 1700000000 +0000\n\nc\n",
tree.to_hex()
);
store.write(Kind::Commit, text.as_bytes()).unwrap()
}
}