crates/storage-git-gix/parked-gix-2/gunnar-wire-gix/bitmap.rs
//! Answering `want`/`have` from a `.bitmap` instead of walking twice.
//!
//! `crates/gunnar-bitmap` reads the file and does the set algebra;
//! `gunnar_store::PackBitmap` pairs it with the `.idx` that gives its bits
//! names. This module is the third piece: the part that needs an object
//! database, and therefore the part neither of those may contain.
//!
//! ```text
//! send = (bitmap(w) | walked(w)) & !(bitmap(h) | walked(h))
//! ```
//!
//! # The miss is a bounded walk, not a full one
//!
//! A `want` whose commit has no stored bitmap is the case every description of
//! this feature waves at, usually as a choice between "walk everything" and
//! some cleverness with XOR chains. It is neither. Git's `add_to_include_set`
//! walks down from the unbitmapped commit and **stops at the first commit that
//! has a bitmap**, ORs that bitmap in, and returns — because a stored bitmap is
//! closed under reachability, so reaching one means the entire history behind
//! it is already accounted for. The walk therefore covers only what has been
//! pushed since the last repack, whatever the size of the repository.
//!
//! (XOR chaining is `compute_xor_offsets`, a storage codec for making the file
//! smaller. `gunnar_bitmap::Index::resolve` already undoes it. It has nothing
//! to do with misses.)
//!
//! # Objects, not only commits
//!
//! Git applies the same rule one level down, in `should_include_obj`: a tree
//! whose bit is already set is not descended into. Without it the *first*
//! unbitmapped commit costs a walk of every tree and blob in the repository,
//! and the bounded commit walk above buys nothing.
//!
//! This module gets that ordering right by construction rather than by luck:
//! the commit walk runs to completion first, so every stored bitmap this
//! request will ever OR in is in place before a single tree is opened.
//! [`BitSeen`] is what makes `Graph::tree_closure` obey it — the same one tree
//! walk the rest of gunnar uses (LAW 5), recording into bits instead of into a
//! set of ids.
//!
//! # The extended index
//!
//! A bitmap position names an object **in one pack**. A fetch can perfectly
//! well involve objects that are not in it: anything pushed since the repack,
//! or a loose object. Git's answer is `ext_index_add_object` — hand those a
//! position past the end of the pack — and it is the right one, because it
//! keeps *everything* in one position space and so keeps the final subtraction
//! a single `AND NOT`. [`Positions`] is that index. Without it the exclusion
//! would need a set of object ids after all, which is the cost this whole path
//! exists to remove.
//!
//! # It does not fight [`Exclusion`], it settles it
//!
//! [`Exclusion`] is how much of the client's history the *walk* opens up to
//! find objects it need not send, and it exists because opening all of it is
//! expensive: `P-010` measured `Full` faulting in 377.23 MiB of pack against
//! `Edges`' 10.17 MiB, so `Edges` ships and knowingly sends a few objects the
//! client already has.
//!
//! A bitmap has the client's whole closure as one word-aligned OR. There is no
//! cheap-and-approximate to choose, so this path ignores the knob and always
//! gives the answer `Exclusion::Full` gives — at `Exclusion::Edges`' cost.
//!
//! MEASURED, and found by the tests below going red on their first run: against
//! `Exclusion::Edges` the bitmap's answer is a strict **subset**. On the
//! 130-commit fixture, a fetch 5 commits deep, the walk sent 4 blobs the client
//! demonstrably held. Set equality therefore holds against `Exclusion::Full`,
//! and that is what `tests::assert_same` asserts; asserting it against `Edges`
//! would be asserting that this path reproduces a known approximation.
//!
//! `GUNNAR_EXCLUSION=full` still does exactly what it says on the walk path,
//! which is where it is a lever. Here it is a no-op, because there is nothing
//! left for it to buy.
//!
//! # What it declines
//!
//! Rather than approximate. Each of these is a request shape whose answer a
//! bitmap cannot give exactly, and an inexact answer here is a pack the client
//! cannot use or a pack missing objects it asked for:
//!
//! * a **partial-clone filter**, which decides membership per object by size or
//! depth — facts the bitmap does not carry;
//! * a **shallow boundary** in either direction, which is a walk that must stop
//! somewhere a bitmap's closure does not;
//! * a **deepening**'s `restrict` set, same reason.
//!
//! Every one of them falls through to `select_objects`' walk and is served
//! exactly as it was before this module existed.
//!
//! # What it does **not** decline, and the day that cost
//!
//! The object ceiling was on that list, on the reasoning that it needs a size
//! per blob and a bitmap carries none. That was wrong in the only way that
//! matters: `Limits::object_bytes` is `Some` by default, so declining on it
//! turned the whole path off **on every serve path there is**, while four
//! end-to-end cases against stock git reported green — because the walk
//! answered and the walk is correct.
//!
//! It was found by deliberately breaking the reader: under a bounded walk that
//! terminated without ORing, the unit tests went red by up to 395 objects out
//! of ~400 and the end-to-end cases did not move. A guard that cannot see a
//! reader that under-sends by 99% is not guarding the reader.
//!
//! So the ceiling is **enforced here** instead, by [`enforce_object_ceiling`],
//! and [`Selection::answered_from_bitmap`] exists so a test can assert which
//! path answered rather than inferring it.
use std::collections::HashMap;
use gix_hash::ObjectId;
use gunnar_bitmap::Bitmap;
use gunnar_store::PackBitmap;
use crate::error::{Error, Result};
use crate::graph::{ClientHas, Emit, Graph, Missing, Seen, SelectOptions, Selection};
/// The position space a bitmap selection works in.
///
/// The pack's own positions, `0..num_objects`, extended with one position per
/// object the request touched that is not in the pack. Git calls the second
/// half `ext_index`.
#[derive(Debug)]
pub(crate) struct Positions {
bitmap: std::sync::Arc<PackBitmap>,
/// First position handed out to an object outside the pack.
base: u32,
/// `extra[i]` is the object at position `base + i`.
extra: Vec<ObjectId>,
of: HashMap<ObjectId, u32>,
/// Set if the extended index ran out of `u32`. See [`Positions::intern`].
overflowed: bool,
}
impl Positions {
fn new(bitmap: std::sync::Arc<PackBitmap>) -> Self {
let base = bitmap.num_objects();
Positions {
bitmap,
base,
extra: Vec::new(),
of: HashMap::new(),
overflowed: false,
}
}
/// The position of `id`, without giving it one.
fn get(&self, id: &gix_hash::oid) -> Option<u32> {
self.bitmap
.pack_position(id)
.or_else(|| self.of.get(&id.to_owned()).copied())
}
/// The position of `id`, giving it one past the end of the pack if it has
/// none.
///
/// A position is a `u32` because a bitmap bit is, so an extended index that
/// walked past `u32::MAX` would silently alias two objects onto one bit —
/// a pack of the right size made of the wrong objects, the failure mode
/// this whole area is prone to. It cannot happen with a `.idx` that already
/// counts its objects in a `u32`, so this records the impossible rather
/// than erroring in the hot path; [`select`] abandons the whole selection
/// if it is ever set, and the walk answers instead.
fn intern(&mut self, id: &ObjectId) -> u32 {
if let Some(pos) = self.get(id) {
return pos;
}
match u32::try_from(self.base as u64 + self.extra.len() as u64) {
Ok(pos) => {
self.extra.push(*id);
self.of.insert(*id, pos);
pos
}
Err(_) => {
self.overflowed = true;
u32::MAX
}
}
}
/// The object at `pos`, or `None` for a bit that names nothing.
///
/// A bitmap's last word can carry trailing bits past the end of the pack
/// and short of the extended index; those address no object and are
/// dropped.
fn oid(&self, pos: u32) -> Option<ObjectId> {
if pos < self.base {
self.bitmap.oid_at_pack_position(pos)
} else {
self.extra.get((pos - self.base) as usize).copied()
}
}
}
/// [`ClientHas`] in its bitmap spelling: what the client holds and what this
/// transfer carries, as one bitmap plus the positions that name it.
///
/// The consumer asks one question per delta base — *may this be named rather
/// than shipped?* — and both spellings answer it with a hash lookup and a bit
/// test. What this one does **not** do is build a set of every object id in the
/// client's history, which on the walk path is the largest allocation a fetch
/// makes.
#[derive(Debug)]
pub(crate) struct Vouch {
positions: Positions,
bits: Bitmap,
}
impl Vouch {
/// Whether `id` is one this transfer may point a delta at.
pub(crate) fn contains(&self, id: &gix_hash::oid) -> bool {
self.positions.get(id).is_some_and(|pos| self.bits.get(pos))
}
/// How many objects are vouched for.
pub(crate) fn len(&self) -> usize {
self.bits.count_ones() as usize
}
}
/// A tree walk that records into a bitmap and stops at anything already covered.
///
/// The `false` return is doing two different jobs, and both matter:
///
/// * *already in this side's set* — the ordinary "visited once" duty every tree
/// walk has, except that here the bit may have been set not by this walk but
/// by a whole commit bitmap OR'd in earlier. That is what bounds the walk.
/// * *in the other side's set* — the client already holds it, so neither send
/// it nor open it. Git's `should_include_obj`, and the reason a fetch does
/// not re-walk shared history.
struct BitSeen<'a> {
positions: &'a mut Positions,
base: &'a mut Bitmap,
/// The `have` side, when this is the `want` side. Git's `include_data.seen`.
other: Option<&'a Bitmap>,
}
impl Seen for BitSeen<'_> {
fn insert(&mut self, id: &ObjectId) -> bool {
let pos = self.positions.intern(id);
if self.base.get(pos) {
return false;
}
if self.other.is_some_and(|other| other.get(pos)) {
return false;
}
self.base.set(pos);
true
}
}
/// One side of the query — the wants, or the haves — as a bitmap.
struct Side {
/// Every position reachable from the roots.
bits: Bitmap,
/// The commits this side had to walk because they had no stored bitmap, in
/// discovery order. Commits *inside* an OR'd bitmap are not here and do not
/// need to be: they are bits, and their type is in the pack's type index.
walked_commits: Vec<ObjectId>,
}
/// `select_objects`, answered from a bitmap.
///
/// `Ok(None)` means "this request is not one a bitmap can answer exactly";
/// the caller walks. See the module documentation for the list, which is short
/// and every entry is a correctness condition rather than a tuning choice.
pub(crate) fn select(
graph: &Graph<'_>,
bitmap: &std::sync::Arc<PackBitmap>,
tips: &[ObjectId],
excludes: &[ObjectId],
options: &SelectOptions<'_>,
) -> Result<Option<Selection>> {
if options.filter.is_some()
|| options.restrict.is_some()
|| !options.boundary.is_empty()
|| !options.have_boundary.is_empty()
{
return Ok(None);
}
let mut positions = Positions::new(std::sync::Arc::clone(bitmap));
let mut selection = Selection::default();
// 1. Peel the tips, exactly as the walk does. A `want` may name a tag, a
// tree or a blob, and the tag objects along the way are part of the
// answer — they are in no commit's bitmap, because a bitmap is built by
// walking trees and a tree never points at a tag.
let mut commit_tips = Vec::new();
let mut direct: Vec<(ObjectId, gix_object::Kind)> = Vec::new();
let mut tags: Vec<ObjectId> = Vec::new();
let mut tagged = std::collections::HashSet::new();
for tip in tips {
let peeled = graph.peel(tip)?;
for tag in peeled.tags {
if tagged.insert(tag) {
tags.push(tag);
}
}
match peeled.kind {
gix_object::Kind::Commit => commit_tips.push(peeled.id),
other => direct.push((peeled.id, other)),
}
}
// 2. The same for the excludes, tolerating gaps for the same reason: a
// `have` from a shallow client can name a commit whose ancestry that
// client does not hold.
let mut exclude_commits = Vec::new();
for id in excludes {
if !graph.contains(id) {
continue;
}
match graph.peel(id) {
Ok(peeled) if peeled.kind == gix_object::Kind::Commit => {
exclude_commits.push(peeled.id)
}
Ok(_) => {}
Err(Error::ObjectMissing { .. }) => {}
Err(err) => return Err(err),
}
}
// 3. What the client already has. This is the half the README's
// "exclusion is O(client history)" was about: with a bitmap it is one
// OR per `have` and no object read at all.
let have = accumulate(graph, &mut positions, &exclude_commits, None, Missing::Skip)?;
// 4. What it is about to be sent, with the haves in hand so the bounded
// walk stops at shared history rather than rediscovering it.
let want = accumulate(
graph,
&mut positions,
&commit_tips,
Some(&have.bits),
options.missing,
)?;
// 5. A `want` that named a tree or a blob outright — a partial clone's lazy
// fetch does exactly this.
let walked = have.walked_commits.len() + want.walked_commits.len();
let mut want_bits = want.bits;
for (id, kind) in &direct {
let mut seen = BitSeen {
positions: &mut positions,
base: &mut want_bits,
other: Some(&have.bits),
};
match kind {
gix_object::Kind::Tree => graph.tree_closure(
*id,
&mut seen,
&std::collections::HashSet::new(),
None,
options.missing,
None,
&mut Emit::Tally(0),
)?,
_ => {
seen.insert(id);
}
}
}
if positions.overflowed {
// Recorded rather than trusted. See `Positions::intern`.
tracing::warn!("the extended bitmap index ran out of positions; serving by walking");
return Ok(None);
}
// 6. The subtraction the whole path exists for: one `AND NOT` over two
// bitmaps, where the walk needs a set of every object id the client
// holds.
let mut send = want_bits;
send.and_not_with(&have.bits);
// 7. Names for the bits. Tags first, then the pack's own objects in **pack
// order** — which is the order their entries appear in the `.pack`, so a
// delta's base precedes it and `write_pack_copy` can reuse it — then
// whatever the bounded walk found outside the pack.
selection.objects = tags;
let mut sent_commits: Vec<ObjectId> = Vec::new();
for pos in send.iter_set_bits() {
let Some(id) = positions.oid(pos) else {
continue;
};
selection.objects.push(id);
}
for id in &want.walked_commits {
if positions.get(id).is_some_and(|pos| send.get(pos)) {
sent_commits.push(*id);
}
}
// Commits inside an OR'd bitmap, which the walk never enumerated. The type
// index answers this without opening one object.
for id in bitmap.of_type(&send, gix_object::Kind::Commit) {
if !want.walked_commits.contains(&id) {
sent_commits.push(id);
}
}
selection.commits = sent_commits;
// 8. The object ceiling, which the walk applies per blob as it goes and
// this has to apply to the answer. See `enforce_object_ceiling`.
if let Some(limit) = options.max_blob_bytes {
enforce_object_ceiling(graph, bitmap, &positions, &send, limit)?;
}
selection.answered_from_bitmap = true;
selection.bitmap_commits_walked = walked;
// 9. The voucher: `have`, and **only** `have`.
//
// It used to be `have | send`, plus every id in `selection.objects`, for
// parity with the walk path — which handed over the objects it was
// sending on the argument that "a delta base inside this same transfer
// is an `OBJ_REF_DELTA` the receiver can resolve". `gunnar.year` refuted
// that on 2026-08-05; the argument, the object and the receiver that
// disagrees are on `Selection::client_has`. Parity with the walk path is
// still the bar, and the walk path is now this: what the receiver held
// **before** the transfer.
//
// `send` is `want AND NOT have`, so ORing it in could only ever have
// *added* objects the client does not hold. Dropping it can only narrow
// the voucher, and a narrower voucher costs an object its delta and
// nothing else.
selection.client_has = ClientHas::Bits(Vouch {
positions,
bits: have.bits,
});
Ok(Some(selection))
}
/// Refuse the fetch if it selected a blob over the server's ceiling.
///
/// # Why this is not simply skipped when a bitmap answers
///
/// Because a guard that is off is not a guard, and `Limits::object_bytes` is on
/// by default. The walk applies it inside `Graph::keeps_blob`, where the header
/// read *replaces* an existence probe it was making anyway. Here there is no
/// such probe to replace, so this is a real added cost — and it is the honest
/// one: the alternative on the table was to decline every request that has a
/// ceiling, which is every request, which is the feature switched off.
///
/// # What keeps it `O(sent blobs)` and not `O(repository)`
///
/// The type index. A `.bitmap` already says which positions are blobs, so this
/// asks the store about the blobs in **this answer** and about nothing else —
/// never about the client's history, which is the cost the whole path exists to
/// remove. Objects outside the pack have no type index entry, so their headers
/// answer both questions at once.
fn enforce_object_ceiling(
graph: &Graph<'_>,
bitmap: &std::sync::Arc<PackBitmap>,
positions: &Positions,
send: &Bitmap,
limit: u64,
) -> Result<()> {
let check = |id: &ObjectId, known_blob: bool| -> Result<()> {
let Some(header) = graph.store().header(id)? else {
return Ok(());
};
if !known_blob && header.kind != gix_object::Kind::Blob {
return Ok(());
}
if header.size > limit {
return Err(Error::ObjectTooLarge {
oid: *id,
size: header.size,
limit,
});
}
Ok(())
};
for id in bitmap.of_type(send, gix_object::Kind::Blob) {
check(&id, true)?;
}
// The extended index: everything the bounded walk found outside the pack.
// The type index says nothing about these, so their headers do.
for pos in send.iter_set_bits() {
if pos < positions.base {
continue;
}
let Some(id) = positions.oid(pos) else {
continue;
};
check(&id, false)?;
}
Ok(())
}
/// Everything reachable from `roots`, as bits.
///
/// The two phases are the whole algorithm and their **order** is what makes it
/// bounded:
///
/// 1. walk commits, stopping at every commit that has a stored bitmap and
/// ORing that bitmap in. Nothing but commit objects is read.
/// 2. only then, walk the trees of the commits phase 1 actually had to open.
/// By now every bit any stored bitmap contributes is set, so
/// [`BitSeen::insert`] can turn a whole subtree away at its root.
///
/// Interleaving them — walking each commit's tree as the commit is reached —
/// would leave phase 2 opening trees that a bitmap OR'd in one commit later
/// would have covered, which on the first unbitmapped commit is the entire
/// repository.
fn accumulate(
graph: &Graph<'_>,
positions: &mut Positions,
roots: &[ObjectId],
other: Option<&Bitmap>,
missing: Missing,
) -> Result<Side> {
let mut bits = Bitmap::new();
let mut walked_commits = Vec::new();
let mut trees: Vec<ObjectId> = Vec::new();
let mut buf = Vec::new();
let mut parents = Vec::new();
let mut stack: Vec<ObjectId> = roots.to_vec();
while let Some(id) = stack.pop() {
let pos = positions.intern(&id);
if bits.get(pos) || other.is_some_and(|o| o.get(pos)) {
continue;
}
// The termination that makes this bounded rather than a full walk.
if let Some(stored) = positions.bitmap.bitmap_for_commit(&id) {
bits.or_with(&stored);
continue;
}
bits.set(pos);
let tree = match graph.commit_links(&id, &mut buf, &mut parents) {
Ok(tree) => tree,
Err(Error::ObjectMissing { .. }) if missing == Missing::Skip => continue,
Err(err) => return Err(err),
};
walked_commits.push(id);
trees.push(tree);
stack.extend(parents.iter().copied());
}
for tree in trees {
let mut seen = BitSeen {
positions,
base: &mut bits,
other,
};
graph.tree_closure(
tree,
&mut seen,
&std::collections::HashSet::new(),
None,
missing,
None,
&mut Emit::Tally(0),
)?;
}
Ok(Side {
bits,
walked_commits,
})
}
#[cfg(test)]
mod tests {
//! The bar is **set equality with the walk**, on real repositories.
//!
//! Not counts. A bitmap path that returns the right number of objects and
//! the wrong ones produces a pack that indexes, `fsck`s and applies — and a
//! client whose working tree is wrong. `pack_order`'s module documentation
//! records exactly that failure being found only because the tests compared
//! against `git rev-list --objects` rather than against gunnar's own
//! encoder.
//!
//! These are unit tests rather than an integration test because
//! `select_objects` is crate-private and comparing the **two selections**
//! is the whole point: driving a whole server twice would compare two
//! packs, which is a weaker statement one indirection further away.
use std::collections::HashSet;
use std::path::{Path, PathBuf};
use gix_hash::{Kind, ObjectId};
use gunnar_store::fs::FsStore;
use gunnar_store::{ObjectStore, RefStore, RepackOptions};
use crate::graph::{select_objects, Bitmaps, Exclusion, Graph, SelectOptions};
use crate::limits::Limits;
fn git(dir: &Path, args: &[&str]) -> String {
let out = std::process::Command::new("git")
.current_dir(dir)
.args(args)
.env("GIT_CONFIG_GLOBAL", "/dev/null")
.env("GIT_CONFIG_SYSTEM", "/dev/null")
.output()
.expect("run git");
assert!(
out.status.success(),
"git {args:?} in {}: {}",
dir.display(),
String::from_utf8_lossy(&out.stderr)
);
String::from_utf8_lossy(&out.stdout).into_owned()
}
/// The options the **server** serves with, not a hand-rolled subset.
///
/// `SelectOptions::for_serving` and nothing else, because building this
/// struct by hand is what hid the defect these tests exist to catch: with
/// `..Default::default()` the object ceiling is `None`, the bitmap path
/// accepted the request, and the tests were green about a configuration the
/// server never runs in. Under the real defaults the ceiling is `Some` and
/// the path had declined every single request.
fn options(bitmaps: Bitmaps, exclusion: Exclusion) -> SelectOptions<'static> {
SelectOptions {
exclusion,
bitmaps,
..SelectOptions::for_serving(&Limits::default())
}
}
fn selection(
store: &dyn ObjectStore,
wants: &[ObjectId],
haves: &[ObjectId],
bitmaps: Bitmaps,
exclusion: Exclusion,
) -> crate::graph::Selection {
let graph = Graph::new(store);
select_objects(&graph, wants, haves, &options(bitmaps, exclusion)).expect("a selection")
}
fn select(
store: &dyn ObjectStore,
wants: &[ObjectId],
haves: &[ObjectId],
bitmaps: Bitmaps,
exclusion: Exclusion,
) -> HashSet<ObjectId> {
selection(store, wants, haves, bitmaps, exclusion)
.objects
.into_iter()
.collect()
}
/// The bitmap answers **exactly** what the exact walk answers, and never
/// more than the shipping walk.
///
/// # Why the exact walk is the reference and `Exclusion::Edges` is not
///
/// This is what the first run of these tests found, and it is a property of
/// the walk rather than a bug in either. `Exclusion::Edges` is a deliberate
/// **under**-approximation of what the client holds — it opens up the
/// client's tips and the edge and nothing deeper, because opening the whole
/// of the client's history faulted in 377.23 MiB of pack against 10.17 MiB
/// (`P-010`). It therefore sends a handful of objects the client already
/// has. A bitmap has the client's whole closure for free, so it gives the
/// answer `Exclusion::Full` gives, at `Exclusion::Edges`' cost.
///
/// So there are two assertions, and they fail for different reasons:
///
/// * **equal to `Full`** — the correctness bar. Either direction is a bug:
/// an object short is a pack the client cannot use, an object over is
/// waste that used to be bounded.
/// * **a subset of `Edges`** — that nothing *new* is being sent. `Full` and
/// `Edges` differ only in what they subtract, so a bitmap that agreed
/// with `Full` by accident while adding objects of its own would pass the
/// first check and fail this one.
fn assert_same(
label: &str,
store: &dyn ObjectStore,
wants: &[ObjectId],
haves: &[ObjectId],
) -> usize {
let answer = selection(store, wants, haves, Bitmaps::Read, Exclusion::Edges);
// Before comparing anything: **which path answered?** Every assertion
// below is equally true of the walk, so without this the whole file is
// green with the reader switched off — which is what it was for the
// first three hours of its existence.
assert!(
answer.answered_from_bitmap,
"{label}: the walk answered, so nothing below tests the bitmap path"
);
let with: HashSet<ObjectId> = answer.objects.into_iter().collect();
let exact = select(store, wants, haves, Bitmaps::Off, Exclusion::Full);
let shipping = select(store, wants, haves, Bitmaps::Off, Exclusion::Edges);
let only_bitmap: Vec<_> = with.difference(&exact).take(5).collect();
let only_walk: Vec<_> = exact.difference(&with).take(5).collect();
assert_eq!(
with,
exact,
"{label}: the bitmap and the exact walk disagree. \
{} only from the bitmap (e.g. {only_bitmap:?}), \
{} only from the walk (e.g. {only_walk:?})",
with.difference(&exact).count(),
exact.difference(&with).count(),
);
let extra: Vec<_> = with.difference(&shipping).take(5).collect();
assert!(
extra.is_empty(),
"{label}: the bitmap sends {:?} which even the under-excluding walk does not",
extra
);
with.len()
}
/// A bare repository with `commits` commits, a merge, and a `.bitmap`.
///
/// 130 rather than a handful, because git stores every one of the newest
/// 100 commits unconditionally: under that threshold *every* commit has a
/// bitmap and the bounded walk in [`super::accumulate`] never runs, so a
/// small fixture would pass whatever that walk did.
struct Fixture {
_dir: tempfile::TempDir,
git_dir: PathBuf,
/// Newest first.
commits: Vec<ObjectId>,
merge: ObjectId,
}
fn fixture(commits: usize) -> Fixture {
let dir = tempfile::tempdir().expect("tempdir");
let work = dir.path().join("work");
std::fs::create_dir_all(&work).expect("mkdir");
git(&work, &["init", "--quiet", "--initial-branch=main"]);
git(&work, &["config", "user.email", "t@example.invalid"]);
git(&work, &["config", "user.name", "t"]);
for i in 0..commits {
std::fs::write(work.join(format!("f{}", i % 7)), format!("{i}\n")).expect("write");
std::fs::write(work.join("shared"), format!("{i}\n")).expect("write");
git(&work, &["add", "-A"]);
git(&work, &["commit", "--quiet", "-m", &format!("c{i}")]);
}
// A side branch and a real merge: a linear fixture never exercises the
// union of two parents' bitmaps, which is where a wrong OR hides.
git(&work, &["checkout", "--quiet", "-b", "side", "HEAD~20"]);
std::fs::write(work.join("sideways"), "side\n").expect("write");
git(&work, &["add", "-A"]);
git(&work, &["commit", "--quiet", "-m", "side"]);
git(&work, &["checkout", "--quiet", "main"]);
git(
&work,
&["merge", "--quiet", "--no-ff", "-m", "merge", "side"],
);
let git_dir = dir.path().join("repo.git");
git(
dir.path(),
&[
"clone",
"--quiet",
"--bare",
work.to_str().unwrap(),
git_dir.to_str().unwrap(),
],
);
let store = FsStore::open_or_init(&git_dir, Kind::Sha1).expect("open");
let outcome = store.repack(&RepackOptions::new()).expect("repack");
assert!(
outcome.bitmap.is_some(),
"the fixture got no .bitmap, so nothing below tests the bitmap path"
);
drop(store);
let merge = ObjectId::from_hex(git(&git_dir, &["rev-parse", "HEAD"]).trim().as_bytes())
.expect("oid");
let commits: Vec<ObjectId> = git(&git_dir, &["rev-list", "HEAD"])
.lines()
.map(|l| ObjectId::from_hex(l.trim().as_bytes()).expect("oid"))
.collect();
Fixture {
_dir: dir,
git_dir,
commits,
merge,
}
}
/// The fixture really is answering from the bitmap.
///
/// Without this every assertion below could be comparing the walk against
/// itself and would pass with the whole module deleted. It is the same trap
/// `repack_writes_a_bitmap.rs` records: a green that cannot go red.
#[test]
fn the_fixture_actually_has_a_bitmap_the_selection_uses() {
let f = fixture(130);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
let objects = store.objects();
let bitmap = objects
.bitmap()
.expect("the repack wrote a .bitmap and the store finds it");
assert!(
bitmap.stored_bitmaps() > 0,
"the .bitmap stores no commit bitmaps, so every want would take the walk"
);
// ...and the newest commit is one of the stored ones, which is what
// makes the clone arm below an OR rather than a walk.
assert!(
bitmap.bitmap_for_commit(&f.merge).is_some(),
"HEAD has no stored bitmap; git stores every one of the newest 100"
);
}
/// A clone: one want, no haves.
#[test]
fn a_clone_selects_the_same_objects_either_way() {
let f = fixture(130);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
let n = assert_same("clone", &store.objects(), &[f.merge], &[]);
assert!(
n > 200,
"a fixture of {n} objects is too small to be evidence"
);
}
/// A shallow-ish fetch: the client is 5 commits behind.
#[test]
fn a_short_fetch_selects_the_same_objects_either_way() {
let f = fixture(130);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
assert_same("fetch-5", &store.objects(), &[f.merge], &[f.commits[5]]);
}
/// A deep divergence: the client is 100 commits behind, so the exclusion
/// side is the expensive half and the one the bitmap is supposed to move.
#[test]
fn a_deep_fetch_selects_the_same_objects_either_way() {
let f = fixture(130);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
assert_same("fetch-100", &store.objects(), &[f.merge], &[f.commits[100]]);
}
/// A fetch across the merge, with a `have` on each side of it.
#[test]
fn a_fetch_across_a_merge_selects_the_same_objects_either_way() {
let f = fixture(130);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
let side = ObjectId::from_hex(git(&f.git_dir, &["rev-parse", "side"]).trim().as_bytes())
.expect("oid");
assert_same(
"merge",
&store.objects(),
&[f.merge],
&[side, f.commits[30]],
);
}
/// A `want` with **no stored bitmap**, which is the bounded walk.
///
/// Built by pushing new commits after the repack: they land in a second
/// pack, so their commits are not in the bitmapped pack at all, every one
/// of them is walked, and the walk has to terminate on the bitmapped
/// ancestor underneath. This is the arm that goes red if
/// [`super::accumulate`]'s termination is wrong in either direction.
#[test]
fn a_want_with_no_bitmap_takes_the_bounded_walk_and_still_agrees() {
let f = fixture(130);
let work = f.git_dir.parent().unwrap().join("work");
for i in 0..4 {
std::fs::write(work.join("after"), format!("{i}\n")).expect("write");
git(&work, &["add", "-A"]);
git(&work, &["commit", "--quiet", "-m", &format!("after{i}")]);
}
git(
&work,
&["push", "--quiet", f.git_dir.to_str().unwrap(), "main"],
);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
let objects = store.objects();
let head = ObjectId::from_hex(git(&f.git_dir, &["rev-parse", "main"]).trim().as_bytes())
.expect("oid");
let bitmap = objects
.bitmap()
.expect("the pushed pack has no .bitmap of its own, so the old one still stands alone");
assert!(
bitmap.bitmap_for_commit(&head).is_none(),
"the new HEAD has a stored bitmap, so this arm never runs the bounded walk"
);
assert_same("no-bitmap-want", &objects, &[head], &[]);
assert_same("no-bitmap-fetch", &objects, &[head], &[f.commits[10]]);
}
/// A `want` naming an **annotated tag**, whose tag object is in no commit's
/// bitmap.
#[test]
fn a_tag_want_selects_the_same_objects_either_way() {
let f = fixture(130);
let work = f.git_dir.parent().unwrap().join("work");
git(&work, &["tag", "-a", "-m", "v1", "v1"]);
git(
&work,
&["push", "--quiet", f.git_dir.to_str().unwrap(), "v1"],
);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
let tag = ObjectId::from_hex(
git(&f.git_dir, &["rev-parse", "refs/tags/v1"])
.trim()
.as_bytes(),
)
.expect("oid");
assert_same("tag-want", &store.objects(), &[tag], &[]);
}
/// A store with a bitmap must still hand every `.idx` position back as the
/// object the `.idx` says it is.
///
/// The red this exists for: `PackBitmap` mixes pack positions and `.idx`
/// positions, and swapping them yields a set of the right size made of the
/// wrong objects. The set-equality arms above would catch it, but only as
/// "the two disagree"; this says which half is lying.
#[test]
fn positions_name_the_objects_the_index_names() {
let f = fixture(130);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
let objects = store.objects();
let bitmap = objects.bitmap().expect("a bitmap");
let mut checked = 0usize;
for id in &f.commits {
let pos = bitmap.pack_position(id).expect("a commit in the pack");
assert_eq!(
bitmap.oid_at_pack_position(pos).as_ref(),
Some(id),
"position {pos} round-tripped to a different object"
);
checked += 1;
}
assert!(checked > 100, "only {checked} positions were checked");
}
/// The bounded walk is **bounded**, and this is the only guard that can say
/// so.
///
/// # The probe this exists for
///
/// ORing a commit's stored bitmap in and then walking its parents anyway
/// changes no answer: a bitmap is closed under reachability, so everything
/// the extra walk finds is already set. MEASURED 2026-08-04 with the
/// `continue` deliberately removed: **9 of 9 set-equality tests and 25 of
/// 25 end-to-end cases against stock git stayed green**. A correctness
/// guard cannot see it. A count can, and this is the count — it caught the
/// probe at **1 commit opened against 0**.
///
/// One, not the whole repository, and that is worth knowing: the OR sets
/// every ancestor's bit, so the very next parent is turned away by
/// `bits.get(pos)`. The regression a missing `continue` buys is one commit
/// read per bitmapped tip, not a full walk. Small, invisible, and exactly
/// the size of thing that survives four sessions.
#[test]
fn the_bounded_walk_stops_at_the_first_bitmapped_ancestor() {
let f = fixture(130);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
let objects = store.objects();
// Every want already has a bitmap, so nothing is opened at all.
let clone = selection(&objects, &[f.merge], &[], Bitmaps::Read, Exclusion::Edges);
assert!(clone.answered_from_bitmap, "the walk answered");
assert_eq!(
clone.bitmap_commits_walked, 0,
"a clone off a fully bitmapped repository opened {} commits; it should open none",
clone.bitmap_commits_walked
);
// Four commits pushed after the repack, none of them bitmapped. The
// walk must open exactly those four and then stop: the fifth step down
// reaches a commit that has a bitmap.
let work = f.git_dir.parent().unwrap().join("work");
for i in 0..4 {
std::fs::write(work.join("after"), format!("{i}\n")).expect("write");
git(&work, &["add", "-A"]);
git(&work, &["commit", "--quiet", "-m", &format!("after{i}")]);
}
git(
&work,
&["push", "--quiet", f.git_dir.to_str().unwrap(), "main"],
);
let head = ObjectId::from_hex(git(&f.git_dir, &["rev-parse", "main"]).trim().as_bytes())
.expect("oid");
let after = selection(&objects, &[head], &[], Bitmaps::Read, Exclusion::Edges);
assert!(after.answered_from_bitmap, "the walk answered");
assert_eq!(
after.bitmap_commits_walked, 4,
"the bounded walk opened {} commits where exactly 4 lack a bitmap; \
more means it walked past a bitmapped ancestor instead of stopping at it",
after.bitmap_commits_walked
);
}
/// The bitmap never sends **more** than the walk it replaces.
///
/// # The probe this exists for
///
/// Dropping the `AND NOT` — serving the wants and subtracting nothing — is
/// invisible to every end-to-end case there is: the pack is bigger, valid,
/// `fsck`s clean, and lands exactly the same objects in the client's
/// repository, because the client already had the surplus. MEASURED
/// 2026-08-04 with the subtraction removed: **25 of 25 cases against stock
/// git stayed green** while the fixture's fetch sent 384 objects instead of
/// 11. Only a count of what was selected can fail on it, and that is what
/// this is.
#[test]
fn the_exclusion_actually_subtracts() {
let f = fixture(130);
let store = FsStore::open_or_init(&f.git_dir, Kind::Sha1).expect("open");
let objects = store.objects();
let clone = select(&objects, &[f.merge], &[], Bitmaps::Read, Exclusion::Edges);
let fetch = select(
&objects,
&[f.merge],
&[f.commits[5]],
Bitmaps::Read,
Exclusion::Edges,
);
assert!(
fetch.len() * 4 < clone.len(),
"a fetch 5 commits deep selected {} objects against a clone's {}; \
the haves were not subtracted",
fetch.len(),
clone.len()
);
// ...and never more than the shipping walk, which is the direction a
// broken subtraction fails in.
let walk = select(
&objects,
&[f.merge],
&[f.commits[5]],
Bitmaps::Off,
Exclusion::Edges,
);
assert!(
fetch.len() <= walk.len(),
"the bitmap selected {} objects where the walk selected {}",
fetch.len(),
walk.len()
);
}
/// The same, against **real repositories**.
///
/// Point `GUNNAR_BITMAP_REAL_REPOS` at a colon-separated list. Skipped when
/// unset, and the skip is printed, because the corpus lives outside this
/// repository — but a fixture is not evidence on its own: the previous lane
/// shipped a feature broken on 18 of 19 real repositories with every
/// fixture green, because every fixture happened to take the other branch.
#[test]
fn real_repositories_select_the_same_objects_either_way() {
let Ok(list) = std::env::var("GUNNAR_BITMAP_REAL_REPOS") else {
eprintln!("SKIPPED: set GUNNAR_BITMAP_REAL_REPOS to a colon-separated list of repos");
return;
};
let scratch = tempfile::tempdir().expect("tempdir");
let mut with_bitmap = 0usize;
let mut arms = 0usize;
for src in list.split(':').filter(|s| !s.is_empty()) {
let name = Path::new(src)
.file_name()
.unwrap()
.to_string_lossy()
.into_owned();
let mirror = scratch.path().join(format!("{name}.git"));
let cloned = std::process::Command::new("git")
.current_dir(scratch.path())
.args([
"clone",
"--quiet",
"--mirror",
&format!("file://{src}"),
mirror.to_str().unwrap(),
])
.env("GIT_CONFIG_GLOBAL", "/dev/null")
.output()
.expect("run git");
if !cloned.status.success() {
eprintln!("skipping {name}: clone failed");
continue;
}
let fmt = git(&mirror, &["rev-parse", "--show-object-format"]);
let hash = if fmt.trim() == "sha256" {
Kind::Sha256
} else {
Kind::Sha1
};
let store = FsStore::open_or_init(&mirror, hash).expect("open");
let outcome = store.repack(&RepackOptions::new()).expect("repack");
if outcome.bitmap.is_none() {
eprintln!("{name}: no bitmap, nothing to compare");
continue;
}
with_bitmap += 1;
let objects = store.objects();
assert!(
objects.bitmap().is_some(),
"{name}: repack wrote a bitmap the store cannot find"
);
// Every branch tip is a want. The haves walk back from the first
// one at a spread of depths, so a repository contributes a clone,
// a short fetch and a deep one.
let tips: Vec<ObjectId> = store
.refs()
.iter(Some("refs/heads/"))
.expect("refs")
.into_iter()
.filter_map(|(_, t)| match t {
gunnar_store::Target::Object(id) => Some(id),
_ => None,
})
.collect();
if tips.is_empty() {
eprintln!("skipping {name}: no branches");
continue;
}
let history: Vec<ObjectId> = git(&mirror, &["rev-list", "--all"])
.lines()
.filter_map(|l| ObjectId::from_hex(l.trim().as_bytes()).ok())
.collect();
if history.len() < 50 {
eprintln!("skipping {name}: only {} commits", history.len());
continue;
}
let n = assert_same(&format!("{name}/clone"), &objects, &tips, &[]);
arms += 1;
for depth in [1usize, 10, 50, history.len() / 2] {
let Some(have) = history.get(depth) else {
continue;
};
assert_same(&format!("{name}/fetch@{depth}"), &objects, &tips, &[*have]);
arms += 1;
}
eprintln!("{name} ({}): {n} objects, {} arms agree", fmt.trim(), arms);
}
assert!(
with_bitmap > 0,
"not one repository in the list got a bitmap, so nothing was compared"
);
assert!(
arms >= with_bitmap * 2,
"only {arms} comparisons over {with_bitmap} repositories"
);
}
}