crates/storage-git-gix/src/graph.rs
//! `reachable(want, have)` — the object closure a fetch must send.
//!
//! # Why this is one serial thread, on purpose
//!
//! `P-004` is decided doctrine and the gunnar-side triage records it as still
//! applying: **the serving tier stays serial**, concurrency comes from serving
//! many requests, and the batch tier (repack, gc, index building) is where a
//! fan-out belongs. `reachable` is a serving-tier call, so it does not open a
//! `std::thread::scope` and it does not fan out. That is a choice, not an
//! omission.
//!
//! # What this costs, and it is the finding the head-to-head is for
//!
//! `gunnar-bitmap`'s module doc records the root fact: **gitoxide has no bitmap
//! support at all** — no `ewah`, no bitmap reader in `gix-pack`, `gix-odb` or
//! `gix-features` — so *"a gix-based server walks the commit graph everywhere
//! real git reads a bitmap"*. This function is that walk. It is the structural
//! reason a gix backend is expected to lose a reachability head-to-head against
//! anything holding a precomputed answer, and it should be **predicted rather
//! than discovered**.
//!
//! # …and it is no longer the only path. See [`crate::bitmap`].
//!
//! The paragraph that stood here said the reader was deliberately not wired up
//! *"because nothing in this crate writes one, so the reader would have no file
//! to read"*. Since 2026-08-11 [`crate::bitmap::write_for_pack`] writes one and
//! [`crate::GixStore::gc`] calls it, so that reason has expired.
//!
//! This walk is still the whole answer whenever a bitmap cannot give an exact
//! one — no `.bitmap`, a damaged one, one describing a different pack, or a
//! `want` this pack's positions cannot express. [`crate::bitmap::select`] falls
//! back here rather than truncating, and `tests/bitmap_and_walk_agree.rs` holds
//! the two to the same **object set** on every shape it can build.
//!
//! The walk itself is shared rather than twinned (LAW 5): [`walk`] is one
//! function and the two paths differ only in the [`Seen`] they hand it — a
//! `HashSet<ObjectId>` here, a bitmap over pack positions there.
use std::collections::HashSet;
use anyhow::{anyhow, Context, Result};
use gix_hash::ObjectId;
use gix_object::{CommitRefIter, Kind, TagRefIter, TreeRefIter};
/// Everything reachable from `tips`, following commits, tags and trees.
///
/// `stop` is consulted before an object is expanded: an id already in it is
/// neither emitted nor walked through. That is what makes the `have` side of a
/// negotiation cheap on the second call and what keeps this from re-walking
/// shared history.
/// Which of the objects a walk visited were commits.
///
/// Threaded through [`closure`] rather than derived afterwards because the walk
/// has already decoded every object's kind: asking again is one header read per
/// object, and [`ReachSet::commits`](git_storage_trait::ReachSet::commits) says
/// in as many words that the store *"knows it for free"*. A caller with no use
/// for it passes [`Commits::Ignore`], which costs one match per object.
pub enum Commits<'a> {
Ignore,
Collect(&'a mut HashSet<ObjectId>),
}
impl Commits<'_> {
fn saw(&mut self, id: ObjectId) {
if let Commits::Collect(set) = self {
set.insert(id);
}
}
}
/// What a walk has already accounted for — the one thing [`walk`] is generic
/// over.
///
/// Two implementations exist and they are the two reachability paths this crate
/// has: [`SetSeen`], which records object ids into a `HashSet`, and
/// `crate::bitmap`'s `BitSeen`, which records **pack positions** into a
/// [`gunnar_bitmap::Bitmap`] and can therefore be pre-loaded with a whole
/// commit's stored bitmap before the walk starts. That pre-loading is what turns
/// a full walk into a bounded one, and it works only because both paths run the
/// same traversal — LAW 5, by construction rather than by two copies agreeing.
pub trait Seen {
/// Whether `id` is already accounted for. A pure query: it must not record.
///
/// Only an optimisation — [`Seen::insert`] is the gate — but it is the one
/// that keeps the stack from holding every edge into an object a hundred
/// trees point at.
fn seen(&self, id: &ObjectId) -> bool;
/// Record `id`. `false` means *already covered*: do not emit it and do not
/// walk through it.
fn insert(&mut self, id: &ObjectId) -> bool;
}
/// [`Seen`] over object ids: everything in `out`, minus everything in `stop`.
///
/// The `stop` set is consulted *before* `out`, so an id in both is neither
/// emitted nor walked through. That is what makes the `have` side of a
/// negotiation cheap on the second call.
pub struct SetSeen<'a> {
/// Ids that are neither emitted nor descended into.
pub stop: &'a HashSet<ObjectId>,
/// Where the walk records what it found.
pub out: &'a mut HashSet<ObjectId>,
}
impl Seen for SetSeen<'_> {
fn seen(&self, id: &ObjectId) -> bool {
self.stop.contains(id) || self.out.contains(id)
}
fn insert(&mut self, id: &ObjectId) -> bool {
if self.stop.contains(id) {
return false;
}
self.out.insert(*id)
}
}
/// The traversal itself: follow commits, tags and trees out from `tips`,
/// recording into `seen`.
///
/// Public because `crate::bitmap` runs it too, over tree roots and with a
/// bitmap-backed [`Seen`]. Nothing about the traversal changes between the two;
/// only what "already accounted for" means does.
pub fn walk(
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
tips: &[ObjectId],
seen: &mut dyn Seen,
commits: &mut Commits<'_>,
) -> Result<()> {
// One scratch buffer, reused for every object. `gix_object::Find::try_find`
// takes `&mut Vec<u8>` precisely so a walk does not allocate per object;
// this is `S-015`'s advice taken, and `S-015` itself is filed SUPERSEDED by
// a negative result, so no throughput claim is made for it here — it is just
// the shape the API asks for.
let mut buf = Vec::with_capacity(64 * 1024);
// Explicit stack rather than recursion: a deep tree or a long commit chain
// must not be a stack overflow, and a server's input is untrusted.
let mut stack: Vec<ObjectId> = tips.iter().filter(|id| !seen.seen(id)).copied().collect();
while let Some(id) = stack.pop() {
if !seen.insert(&id) {
continue;
}
let Some(data) = find
.try_find(&id, &mut buf)
.map_err(|e| anyhow!("read object {id}: {e}"))?
else {
// A tip naming an object that is not here is the caller's error, but
// a *tree entry* naming one is a broken repository. Neither is worth
// failing the whole walk over at this layer: the object is recorded
// as wanted and the pack writer will fail loudly on it.
continue;
};
let obj_kind = data.kind;
// `data` borrows `buf`; copy out the ids before the next iteration
// reuses it.
let mut children: Vec<ObjectId> = Vec::new();
match obj_kind {
Kind::Commit => {
commits.saw(id);
for token in CommitRefIter::from_bytes(data.data, hash_kind) {
match token.with_context(|| format!("parse commit {id}"))? {
gix_object::commit::ref_iter::Token::Tree { id } => children.push(id),
gix_object::commit::ref_iter::Token::Parent { id } => children.push(id),
_ => break,
}
}
}
Kind::Tree => {
for entry in TreeRefIter::from_bytes(data.data, hash_kind) {
let entry = entry.with_context(|| format!("parse tree {id}"))?;
// ── GITLINKS ARE NOT EDGES ──────────────────────────────
//
// Mode 160000 names a commit in ANOTHER repository. It is
// not missing, it is not supposed to be here, and no amount
// of walking this repository will find it. `git` does not
// follow one when it computes a pack's object set, and
// neither may this.
//
// Following one is not a harmless extra id, because the
// walk inserts into `out` BEFORE it tries to read the
// object (see below): the absent commit lands in the
// selection, `emit_pack` is then asked for an object the
// store does not hold, and the whole transfer dies with
// <oid> was selected for emission and this store does
// not hold it
// -- which reaches the client as the storage layer's
// generic "the repository is unavailable; try again".
//
// MEASURED on oden 2026-08-11: a mirror of `nornir.git`
// (12 370 objects, five `160000` entries, `git fsck --full
// --strict` clean on BOTH the source and the served store)
// could be pushed and then never cloned back. Every clone
// and fetch of it failed, deterministically, on the first
// gitlink the walk reached.
//
// `fsck` is clean in that case and stays clean, which is
// why this is not a broken-repository case and must not be
// left to the "record it and let the pack writer fail"
// path below: a repository with a submodule is ordinary.
if entry.mode.is_commit() {
continue;
}
children.push(entry.oid.to_owned());
}
}
Kind::Tag => {
let target = TagRefIter::from_bytes(data.data, hash_kind)
.target_id()
.with_context(|| format!("parse tag {id}"))?;
children.push(target);
}
// A blob has no outgoing edges.
Kind::Blob => {}
}
for c in children {
if !seen.seen(&c) {
stack.push(c);
}
}
}
Ok(())
}
/// [`walk`] with a `HashSet` [`Seen`] — the shape every caller in this module
/// wants.
fn closure(
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
tips: &[ObjectId],
stop: &HashSet<ObjectId>,
out: &mut HashSet<ObjectId>,
commits: &mut Commits<'_>,
) -> Result<()> {
walk(find, hash_kind, tips, &mut SetSeen { stop, out }, commits)
}
/// `want` minus `have`: the object ids a fetch must send.
///
/// The `have` closure is computed **in full** — commits, trees and blobs — and
/// then used as the stop set for the `want` walk. Marking only the *commits*
/// uninteresting would be cheaper and would be wrong: a tree unchanged between
/// two commits is reachable from both, and the client already has it.
pub fn reachable(
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
want: &[ObjectId],
have: &[ObjectId],
) -> Result<Vec<ObjectId>> {
Ok(select(find, hash_kind, want, have)?.objects)
}
/// The full closure of the negotiated common `have` tips — every object the
/// receiver held **before** this transfer.
///
/// This is [`select`]'s `client_has` without the `want` walk beside it: the same
/// [`closure`] over the same walker (LAW 5), exposed on its own for
/// [`GitServe::emit_pack`](git_storage_trait::GitServe::emit_pack)'s thin-pack
/// base vouching, which needs to answer "does the client hold this base" for a
/// handful of boundary deltas and has no `want` to compute. An empty `have`
/// yields an empty set — a clone vouches for nothing, which is exactly right:
/// its receiver holds nothing.
pub fn have_closure(
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
have: &[ObjectId],
) -> Result<HashSet<ObjectId>> {
let mut held = HashSet::new();
if !have.is_empty() {
let empty = HashSet::new();
closure(
find,
hash_kind,
have,
&empty,
&mut held,
&mut Commits::Ignore,
)?;
}
Ok(held)
}
/// One [`GitServe::select`](git_storage_trait::GitServe::select) answer, in gix
/// terms.
///
/// The same walk [`reachable`] runs, keeping the two facts it computes on the
/// way and then throws away: which of the objects are commits, and what the
/// `have` side closed over. The contract asks for both because *"the store knows
/// it for free"* — and here that is literally true, since the walk decoded every
/// object's kind to find its children and built the stop set to prune with.
pub struct Selection {
/// Every object to send, sorted.
pub objects: Vec<ObjectId>,
/// Which of [`Selection::objects`] are commits, sorted.
pub commits: Vec<ObjectId>,
/// The closure of `have` — what the receiver held **before** this transfer.
/// Never an object this transfer carries: it is the stop set, and the
/// `want` walk skips everything in it.
pub client_has: Vec<ObjectId>,
}
/// `want` minus `have`, plus the commit subset and the `have` closure.
pub fn select(
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
want: &[ObjectId],
have: &[ObjectId],
) -> Result<Selection> {
let mut stop = HashSet::new();
if !have.is_empty() {
let empty = HashSet::new();
closure(
find,
hash_kind,
have,
&empty,
&mut stop,
&mut Commits::Ignore,
)?;
}
let mut out = HashSet::new();
let mut commits = HashSet::new();
closure(
find,
hash_kind,
want,
&stop,
&mut out,
&mut Commits::Collect(&mut commits),
)?;
// Sorted, so the answer is a function of the graph and not of hash-map
// iteration order. A caller diffing two runs, or a test asserting an object
// set, gets a stable sequence.
let sorted = |s: HashSet<ObjectId>| {
let mut v: Vec<ObjectId> = s.into_iter().collect();
v.sort_unstable();
v
};
Ok(Selection {
objects: sorted(out),
commits: sorted(commits),
client_has: sorted(stop),
})
}
/// Everything reachable from every ref tip — the live set a `gc` keeps.
pub fn live_set(
find: &dyn gix_object::Find,
hash_kind: gix_hash::Kind,
tips: &[ObjectId],
) -> Result<HashSet<ObjectId>> {
let empty = HashSet::new();
let mut out = HashSet::new();
closure(
find,
hash_kind,
tips,
&empty,
&mut out,
&mut Commits::Ignore,
)?;
Ok(out)
}