crates/gunnar-bitmap/tests/stock_git.rs
//! The judge is stock git, not this crate.
//!
//! A decoder tested against its own encoder is the exact shape of a hollow
//! guard: it agrees with itself no matter what it believes the format to be. So
//! every assertion here is against a `.bitmap` that `git repack -adb` wrote, or
//! against an object set that `git rev-list --objects` produced by walking the
//! graph.
//!
//! # `--test-bitmap` alone is not enough, and here is the measurement
//!
//! `git rev-list --test-bitmap <commit>` compares the stored bitmap for **that
//! one commit** against a real traversal. It says nothing about any other entry.
//! Measured on 2026-08-04, git 2.53: flipping byte 5000 of a 28 520-byte
//! `.bitmap` — a byte inside the entry region — still produced `OK!` and exit 0,
//! because the corrupted entry was not the one being tested.
//!
//! A single `--test-bitmap` call is therefore a probe that passes through real
//! corruption. Every test below that uses it runs it over *every* bitmapped
//! commit, and [`writer_output_goes_red_when_one_object_is_dropped`] proves it
//! can still go red once the damage is aimed at the commit under test.
mod support;
use gunnar_bitmap::{Bitmap, Index, Reachability, Writer, XorPolicy};
use support::{git, git_try, rev_list_objects, Fixture};
/// Map a bitmap over PACK positions to sorted object id hex strings.
///
/// The `PackOrder` step is the whole point: the bits are ranks by offset in the
/// `.pack`, and feeding them to `oid_at_index` directly yields the
/// lexicographically smallest object ids instead — a set of exactly the right
/// size made of entirely the wrong objects.
fn positions_to_oids(
idx: &gix_pack::index::File,
order: &gunnar_bitmap::PackOrder,
set: &Bitmap,
) -> Vec<String> {
let mut ids: Vec<String> = order
.index_positions(set)
.map(|pos| idx.oid_at_index(pos).to_string())
.collect();
ids.sort();
ids
}
/// A compact description of how two object sets differ.
///
/// Printing two 4000-element vectors buries the finding; the interesting part is
/// always which handful of objects moved and in which direction.
fn diff_summary(ours: &[String], theirs: &[String]) -> String {
let o: std::collections::BTreeSet<&String> = ours.iter().collect();
let t: std::collections::BTreeSet<&String> = theirs.iter().collect();
let only_ours: Vec<&&String> = o.difference(&t).take(6).collect();
let only_theirs: Vec<&&String> = t.difference(&o).take(6).collect();
format!(
"ours={} theirs={}; {} only in ours (first: {:?}); {} only in git's (first: {:?})",
ours.len(),
theirs.len(),
o.difference(&t).count(),
only_ours,
t.difference(&o).count(),
only_theirs
)
}
/// A commit's object id from the `.idx` position stored in its entry header.
///
/// No `PackOrder` here, and that asymmetry is the point: the bits inside a
/// bitmap are pack positions, but an entry's `commit_index_pos` is an `.idx`
/// position. Running this one through `PackOrder` yields a valid object id of
/// the wrong object, and `git rev-list --objects` on it returns a set of size 1
/// rather than an error.
fn oid_at_index_pos(idx: &gix_pack::index::File, index_pos: u32) -> String {
idx.oid_at_index(index_pos).to_string()
}
fn fixture() -> (Fixture, Index) {
let fx = Fixture::build(120, gix_hash::Kind::Sha1);
let index = Index::at(fx.bitmap_path(), fx.object_hash).expect("parse git's own bitmap");
(fx, index)
}
#[test]
fn every_stored_bitmap_equals_what_stock_git_walks_to() {
let (fx, index) = fixture();
let idx = fx.index();
let order = fx.pack_order(&idx);
assert!(
index.entries().len() >= 5,
"fixture produced too few bitmaps to be a test"
);
let mut compared = 0usize;
let mut sets = Vec::new();
for (i, entry) in index.entries().iter().enumerate() {
let resolved = index.resolve(i).expect("entry resolves");
let ours = positions_to_oids(&idx, &order, &resolved);
let commit = oid_at_index_pos(&idx, entry.commit_index_pos);
let theirs = rev_list_objects(&fx.repo, &[&commit]);
assert!(
ours == theirs,
"entry {i} (commit {commit}, xor_offset {}) decoded to a different object set than \
`git rev-list --objects` walked to: {}",
entry.xor_offset,
diff_summary(&ours, &theirs)
);
sets.push(ours);
compared += 1;
}
assert!(compared >= 5, "only {compared} bitmaps were compared");
// Negative control for the comparison itself. If every commit in the
// fixture reached the same objects, the assertion above would hold for a
// decoder that ignored its input entirely and returned a constant.
let distinct = {
let mut s = sets.clone();
s.sort();
s.dedup();
s.len()
};
assert!(
distinct > 1,
"all {compared} bitmaps decoded to the same object set, so the comparison above \
could not have detected a decoder that ignores which commit it was asked about"
);
// And the object sets must actually differ between two specific commits, or
// `rev-list` is the thing being constant rather than us.
assert_ne!(
sets.first().expect("at least one"),
sets.last().expect("at least one"),
"the first and last bitmapped commit reached identical object sets"
);
}
#[test]
fn xor_compressed_entries_are_present_and_resolve() {
let (_fx, index) = fixture();
let xored = index.entries().iter().filter(|e| e.xor_offset != 0).count();
// If git happened to store everything whole, the resolution path above was
// never exercised and `every_stored_bitmap_equals_what_stock_git_walks_to`
// proved nothing about XOR at all. Say so rather than pass quietly.
assert!(
xored > 0,
"git stored no XOR-compressed entries in this fixture, so nothing here tested \
XOR resolution"
);
// A stored XOR bitmap must differ from its resolved form, otherwise
// "resolution" could be the identity function.
let (i, _) = index
.entries()
.iter()
.enumerate()
.find(|(_, e)| e.xor_offset != 0)
.expect("checked above");
let stored = Bitmap::from_ewah(&index.entries()[i].bitmap);
let resolved = index.resolve(i).expect("resolves");
assert_ne!(
stored, resolved,
"resolving entry {i} changed nothing, so XOR resolution may be a no-op"
);
}
#[test]
fn want_minus_have_equals_stock_gits_exclusion() {
let (fx, index) = fixture();
let idx = fx.index();
let order = fx.pack_order(&idx);
let entries = index.entries();
assert!(entries.len() >= 4);
// Pick a want and a have that are genuinely different points in history,
// and check several pairings rather than one lucky one.
let mut checked = 0;
let mut non_trivial = 0;
for (wi, hi) in [(0usize, entries.len() - 1), (1, entries.len() - 2), (0, 2)] {
let want_pos = entries[wi].commit_index_pos;
let have_pos = entries[hi].commit_index_pos;
let want = oid_at_index_pos(&idx, want_pos);
let have = oid_at_index_pos(&idx, have_pos);
if want == have {
continue;
}
let selection = Reachability::new(&index).objects_to_send([want_pos], [have_pos]);
assert!(
selection.is_complete(),
"both commits are bitmapped, so the selection must be complete: {selection:?}"
);
let ours = positions_to_oids(&idx, &order, &selection.objects);
let theirs = rev_list_objects(&fx.repo, &[&want, "--not", &have]);
assert!(
ours == theirs,
"want {want} minus have {have} disagreed with `git rev-list --objects --not`: {}",
diff_summary(&ours, &theirs)
);
// An exclusion that removed nothing would make the AND-NOT untested.
let full = rev_list_objects(&fx.repo, &[&want]);
if full.len() != ours.len() {
non_trivial += 1;
}
checked += 1;
}
assert!(checked >= 2, "only {checked} want/have pairs were checked");
assert!(
non_trivial >= 1,
"no pairing actually excluded anything, so AND-NOT was never exercised"
);
}
#[test]
fn the_type_bitmaps_agree_with_stock_git() {
let (fx, index) = fixture();
let idx = fx.index();
let order = fx.pack_order(&idx);
let mut commits = Bitmap::new();
commits.or_ewah(index.type_bitmap(gunnar_bitmap::Kind::Commit));
let ours = positions_to_oids(&idx, &order, &commits);
let mut theirs: Vec<String> = git(&fx.repo, &["rev-list", "--all"])
.lines()
.map(|l| l.to_owned())
.collect();
theirs.sort();
assert!(
ours == theirs,
"the commit type index disagrees with `git rev-list --all`: {}",
diff_summary(&ours, &theirs)
);
let mut tags = Bitmap::new();
tags.or_ewah(index.type_bitmap(gunnar_bitmap::Kind::Tag));
let our_tags = positions_to_oids(&idx, &order, &tags);
let their_tag = git(&fx.repo, &["rev-parse", "v1"]).trim().to_owned();
assert_eq!(
our_tags,
vec![their_tag],
"the tag type index should hold exactly the one annotated tag the fixture creates"
);
// The four types must partition the pack. A type bitmap that was decoded as
// empty would still pass a "subset" check, so assert the total.
let counts = Reachability::new(&index).counts_by_type(&{
let mut all = Bitmap::new();
for kind in [
gunnar_bitmap::Kind::Commit,
gunnar_bitmap::Kind::Tree,
gunnar_bitmap::Kind::Blob,
gunnar_bitmap::Kind::Tag,
] {
all.or_ewah(index.type_bitmap(kind));
}
all
});
let total: u64 = counts.iter().sum();
assert_eq!(
total,
u64::from(
index
.num_objects()
.expect("hash cache gives the object count")
),
"commits+trees+blobs+tags must add up to every object in the pack, got {counts:?}"
);
}
#[test]
fn the_whole_file_re_encodes_byte_for_byte() {
for kind in [gix_hash::Kind::Sha1, gix_hash::Kind::Sha256] {
let fx = Fixture::build(120, kind);
let original = fx.bitmap_bytes();
let index = Index::at(fx.bitmap_path(), kind).expect("parse");
let mut writer = Writer::new(kind, index.pack_checksum().to_owned());
for (slot, k) in [
gunnar_bitmap::Kind::Commit,
gunnar_bitmap::Kind::Tree,
gunnar_bitmap::Kind::Blob,
gunnar_bitmap::Kind::Tag,
]
.into_iter()
.enumerate()
{
writer.type_bitmap_encoded(k, index.type_bitmaps()[slot].clone());
}
// Feed the writer the *resolved* bitmaps, so the XOR compression is
// redone from scratch rather than copied. Only the offsets are
// preserved, which is what makes this a test of the encoder.
let offsets: Vec<u8> = index.entries().iter().map(|e| e.xor_offset).collect();
for (i, entry) in index.entries().iter().enumerate() {
writer.push_commit(
entry.commit_index_pos,
entry.flags,
index.resolve(i).expect("resolve"),
);
}
writer.xor_policy(XorPolicy::Explicit(offsets));
writer.name_hashes(
index
.name_hashes()
.expect("git writes a hash cache")
.to_vec(),
);
let ours = writer.to_vec().expect("write");
assert_eq!(
ours.len(),
original.len(),
"{kind:?}: re-encoded length differs from git's file"
);
let first_diff = ours.iter().zip(&original).position(|(a, b)| a != b);
assert_eq!(
first_diff, None,
"{kind:?}: re-encoded bytes diverge from git's file at offset {first_diff:?}"
);
}
}
#[test]
fn stock_git_reads_a_bitmap_this_crate_wrote() {
let fx = Fixture::build(120, gix_hash::Kind::Sha1);
let index = Index::at(fx.bitmap_path(), fx.object_hash).expect("parse");
let idx = fx.index();
let rewritten = rewrite(&index, fx.object_hash, None);
// Written with our own XOR choices, not git's, so this is our encoder end to
// end rather than a copy of git's framing.
install(&fx, &rewritten);
let commits: Vec<String> = index
.entries()
.iter()
.map(|e| oid_at_index_pos(&idx, e.commit_index_pos))
.collect();
assert!(commits.len() >= 5);
for commit in &commits {
let (ok, out) = git_try(&fx.repo, &["rev-list", "--test-bitmap", commit]);
assert!(
ok && out.contains("OK!"),
"git rejected our bitmap for {commit}:\n{out}"
);
}
// And the object sets agree with and without the bitmap.
let with = rev_list_objects(&fx.repo, &["--use-bitmap-index", "--all"]);
let without = rev_list_objects(&fx.repo, &["--all"]);
assert!(
with == without,
"traversal with our bitmap differs from traversal without it: {}",
diff_summary(&with, &without)
);
assert!(
!with.is_empty(),
"both object sets were empty, which would make the above vacuous"
);
let (ok, out) = git_try(&fx.repo, &["fsck", "--full", "--strict"]);
assert!(
ok,
"git fsck --full --strict rejected the repository:\n{out}"
);
}
#[test]
fn writer_output_goes_red_when_one_object_is_dropped() {
// The negative control for the test above, and the reason it loops over
// every commit instead of calling `--test-bitmap` once: a byte flip
// elsewhere in the file does NOT make `--test-bitmap` fail (measured
// 2026-08-04, git 2.53). Damage aimed at the commit being tested does.
let fx = Fixture::build(120, gix_hash::Kind::Sha1);
let index = Index::at(fx.bitmap_path(), fx.object_hash).expect("parse");
let idx = fx.index();
// Drop a single object from the bitmap of the last entry, which is a real
// under-reporting bug of exactly the kind that ships a broken pack.
let victim = index.entries().len() - 1;
let victim_commit = oid_at_index_pos(&idx, index.entries()[victim].commit_index_pos);
let rewritten = rewrite(&index, fx.object_hash, Some(victim));
install(&fx, &rewritten);
let (ok, out) = git_try(&fx.repo, &["rev-list", "--test-bitmap", &victim_commit]);
assert!(
!ok,
"git accepted a bitmap that is missing an object for {victim_commit}. \
That means `--test-bitmap` cannot see this class of bug and every green \
from it in this file is worthless:\n{out}"
);
assert!(
out.contains("mismatch") || out.contains("error") || out.contains("fatal"),
"git failed but not because of a bitmap mismatch, so the red above may be \
for an unrelated reason:\n{out}"
);
}
/// Re-encode `index` with this crate's writer, optionally dropping one set bit
/// from entry `sabotage` so the result is wrong in a specific, checkable way.
fn rewrite(index: &Index, kind: gix_hash::Kind, sabotage: Option<usize>) -> Vec<u8> {
let mut writer = Writer::new(kind, index.pack_checksum().to_owned());
for (slot, k) in [
gunnar_bitmap::Kind::Commit,
gunnar_bitmap::Kind::Tree,
gunnar_bitmap::Kind::Blob,
gunnar_bitmap::Kind::Tag,
]
.into_iter()
.enumerate()
{
writer.type_bitmap_encoded(k, index.type_bitmaps()[slot].clone());
}
for (i, entry) in index.entries().iter().enumerate() {
let mut bitmap = index.resolve(i).expect("resolve");
if sabotage == Some(i) {
// Drop the highest set bit. git writes commits first in a pack, so
// the highest pack position in a reachability bitmap is always a
// tree or a blob and never the commit itself — which keeps the
// sabotage a pure "one object went missing" and not an unrelated
// "the commit is absent from its own bitmap".
let victim = bitmap
.iter_set_bits()
.last()
.expect("a bitmapped commit reaches more than nothing");
bitmap.unset(victim);
}
writer.push_commit(entry.commit_index_pos, entry.flags, bitmap);
}
writer.xor_policy(XorPolicy::PreviousIfSmaller);
writer.name_hashes(index.name_hashes().expect("hash cache").to_vec());
writer.to_vec().expect("write")
}
/// Replace the repository's `.bitmap` with `bytes`.
fn install(fx: &Fixture, bytes: &[u8]) {
let path = fx.bitmap_path();
// Pack files are written read-only by git.
let mut perms = std::fs::metadata(&path).expect("stat").permissions();
#[cfg(unix)]
{
use std::os::unix::fs::PermissionsExt;
perms.set_mode(0o644);
}
#[cfg(not(unix))]
perms.set_readonly(false);
std::fs::set_permissions(&path, perms).expect("chmod");
std::fs::write(&path, bytes).expect("write bitmap");
}