crates/storage-git-gix/tests/fanout16_finds_what_git_finds.rs
//! The 16-bit fanout resolves **every** oid to the offset **stock git** says it
//! has, and a structure that does not must be provably visible.
//!
//! Adapted from `parked-gix-2/gunnar-store-gix/tests/fanout16_finds_what_git_finds.rs`.
//! The assertions are the original's; the fixture is rebuilt on `GixStore` and
//! `GitOps::put_pack`, because the original's `FsStore` + `RepackOptions` +
//! `PackBitmap` do not exist in this crate and are not being revived.
//!
//! # Why `git verify-pack` and not `.idx.lookup`
//!
//! [`storage_git_gix::fanout::equivalent`] compares the two searches against
//! each other, and that is worth doing — but both read the same `.idx` through
//! the same `gix_pack::index::File`, so a reader that is wrong about what the
//! file holds makes them agree beautifully about garbage. That is not
//! hypothetical: the lane that measured this area first solved the hash width
//! from the file length, which admits sha1 for a sha256 index, and every arm in
//! its suite then agreed on nonsense until `git verify-pack -v` — the one check
//! that did not go through the reader — found it.
//!
//! So the bar here is **`git verify-pack -v`'s own oid → offset table**,
//! compared against `pack_offset_at_index(fanout.lookup(oid))` for every object
//! in the pack. This crate's reader appears on one side of that comparison only.
//!
//! # Why the fixture is 4 200 blobs and not 3 commits
//!
//! `Fanout16::MIN_OBJECTS` is 4 096, and below it `build` returns `None` on
//! purpose. A fixture under the floor would exercise the fallback and nothing
//! else, and would pass with the fanout deleted. Both sides of the floor are
//! tested, and the over-floor one asserts `uses_fanout16()` rather than
//! inferring it: the two searches are defined to return the same index, so
//! nothing else in this file could tell them apart.
//!
//! # Never skips
//!
//! `S-026`: *"the real-git interop suites self-skip and report green"*. These
//! fail when `git` is missing.
use std::collections::BTreeMap;
use std::path::{Path, PathBuf};
use std::process::{Command, Stdio};
use git_storage_trait::GitOps;
use gix_hash::Kind;
use storage_git_gix::fanout::{equivalent, Fanout16};
use storage_git_gix::packs::PackSet;
use storage_git_gix::GixStore;
fn git(dir: &Path, args: &[&str]) -> String {
let out = Command::new("git")
.current_dir(dir)
.args(args)
.env("GIT_CONFIG_GLOBAL", "/dev/null")
.env("GIT_CONFIG_SYSTEM", "/dev/null")
.output()
.unwrap_or_else(|e| panic!("`git {}` could not be run: {e}", args.join(" ")));
assert!(
out.status.success(),
"git {args:?} failed: {}\n{}",
String::from_utf8_lossy(&out.stderr),
String::from_utf8_lossy(&out.stdout),
);
String::from_utf8_lossy(&out.stdout).into_owned()
}
struct Fixture {
_dir: tempfile::TempDir,
git_dir: PathBuf,
}
/// A bare `GixStore` holding `files` blobs in one commit, as **one** pack.
///
/// One commit rather than many, because what this file needs is **objects**,
/// and 4 200 blobs in one tree cost two `git` invocations where 4 200 commits
/// would cost 8 400.
fn fixture(hash: Kind, files: usize) -> Fixture {
let dir = tempfile::tempdir().expect("temporary directory");
let git_dir = dir.path().join("repo.git");
let work = dir.path().join("work");
std::fs::create_dir_all(&work).expect("create the working tree");
let fmt = match hash {
Kind::Sha1 => "sha1",
_ => "sha256",
};
git(
&work,
&[
"init",
"--quiet",
&format!("--object-format={fmt}"),
"--initial-branch=main",
".",
],
);
git(&work, &["config", "user.email", "b@example.invalid"]);
git(&work, &["config", "user.name", "B"]);
// Spread over subdirectories, so the pack holds trees as well as blobs and
// the oid distribution is not one directory's worth of adjacent names.
for i in 0..files {
let d = work.join(format!("d{:03}", i % 64));
std::fs::create_dir_all(&d).expect("mkdir");
std::fs::write(d.join(format!("f{i}.txt")), format!("content {i}\n")).expect("write");
}
git(&work, &["add", "-A"]);
let out = Command::new("git")
.current_dir(&work)
.args(["commit", "--quiet", "-m", "one"])
.env("GIT_CONFIG_GLOBAL", "/dev/null")
.env("GIT_CONFIG_SYSTEM", "/dev/null")
.env("GIT_AUTHOR_DATE", "1600000000 +0000")
.env("GIT_COMMITTER_DATE", "1600000000 +0000")
.output()
.expect("run git");
assert!(
out.status.success(),
"commit: {}",
String::from_utf8_lossy(&out.stderr)
);
// `--delta-base-offset`, for the reason `round_trip.rs` gives at length:
// gitoxide cannot index a pack whose ref-delta bases are inside that same
// pack, and it is also what every modern client actually sends.
let out = Command::new("git")
.current_dir(&work)
.args(["pack-objects", "--revs", "--delta-base-offset", "--stdout"])
.stdin(Stdio::piped())
.stdout(Stdio::piped())
.stderr(Stdio::piped())
.spawn()
.and_then(|mut c| {
use std::io::Write;
c.stdin.take().unwrap().write_all(b"HEAD\n")?;
c.wait_with_output()
})
.expect("git pack-objects");
assert!(out.status.success(), "pack-objects failed");
let store = GixStore::open_or_init(&git_dir, hash).expect("create the bare repository");
store.put_pack(&out.stdout).expect("index the pack");
Fixture { _dir: dir, git_dir }
}
/// The one `.idx` in this repository's pack directory.
fn index_path(git_dir: &Path) -> PathBuf {
let mut found: Vec<PathBuf> = std::fs::read_dir(git_dir.join("objects").join("pack"))
.expect("read the pack directory")
.flatten()
.map(|e| e.path())
.filter(|p| p.extension().is_some_and(|x| x == "idx"))
.collect();
assert_eq!(
found.len(),
1,
"expected exactly one pack index, found {found:?}"
);
found.pop().expect("the index")
}
/// **Stock git's** oid → pack offset table for this index.
///
/// `git verify-pack -v` prints `<oid> <type> <size> <size-in-pack> <offset>`
/// per object, plus indented delta-chain lines and a trailing histogram, and
/// the parse is asserted non-empty because an unparsed listing and a clean one
/// look identical downstream.
fn git_offsets(git_dir: &Path, idx: &Path) -> BTreeMap<String, u64> {
let listing = git(
git_dir,
&["verify-pack", "-v", idx.to_str().expect("utf-8 path")],
);
let mut out = BTreeMap::new();
for line in listing.lines() {
// Delta-chain histogram lines are indented; object lines are not.
if line.starts_with(char::is_whitespace) {
continue;
}
let mut f = line.split_whitespace();
let (Some(oid), Some(kind), Some(_size), Some(_in_pack), Some(offset)) =
(f.next(), f.next(), f.next(), f.next(), f.next())
else {
continue;
};
if !matches!(kind, "commit" | "tree" | "blob" | "tag") {
continue;
}
let Ok(offset) = offset.parse::<u64>() else {
continue;
};
out.insert(oid.to_owned(), offset);
}
assert!(
out.len() > 1000,
"git verify-pack -v yielded {} objects; a comparison against an unparsed listing is a \
comparison against nothing",
out.len()
);
out
}
/// The headline, both hash kinds: every object git names resolves through the
/// 16-bit fanout to the offset git gave it.
#[test]
fn every_object_resolves_to_the_offset_stock_git_reports() {
for hash in [Kind::Sha1, Kind::Sha256] {
let f = fixture(hash, 4200);
let idx_path = index_path(&f.git_dir);
let expected = git_offsets(&f.git_dir, &idx_path);
let idx = gix_pack::index::File::at(&idx_path, hash).expect("open the .idx");
let fanout = Fanout16::build(&idx).unwrap_or_else(|| {
panic!(
"{hash:?}: the fixture holds {} objects, under Fanout16::MIN_OBJECTS ({}), so the \
fanout was never built and this test would pass with it deleted",
idx.num_objects(),
Fanout16::MIN_OBJECTS
)
});
let mut checked = 0usize;
for (oid_hex, offset) in &expected {
let id = gix_hash::ObjectId::from_hex(oid_hex.as_bytes()).expect("git printed an oid");
let at = fanout
.lookup(&idx, &id)
.unwrap_or_else(|| panic!("{hash:?}: {oid_hex} is in the pack and was not found"));
assert_eq!(
idx.pack_offset_at_index(at),
*offset,
"{hash:?}: {oid_hex} resolved to entry {at}, whose offset is not git's"
);
checked += 1;
}
assert_eq!(
checked,
idx.num_objects() as usize,
"{hash:?}: git listed {checked} objects and the .idx holds {}",
idx.num_objects()
);
}
}
/// The two searches agree on every oid in the pack, and on a mutation of each.
///
/// `O(n)`, and the mutation is of the **second** byte on purpose — that is the
/// byte the wider fanout added.
#[test]
fn the_two_searches_agree_on_every_object_and_every_mutation() {
let f = fixture(Kind::Sha1, 4200);
let idx_path = index_path(&f.git_dir);
let idx = gix_pack::index::File::at(&idx_path, Kind::Sha1).expect("open the .idx");
let fanout = Fanout16::build(&idx).expect("the fixture is over the floor");
let n = equivalent(&idx, &fanout).expect("the searches must agree");
assert_eq!(n, idx.num_objects());
assert!(n >= Fanout16::MIN_OBJECTS, "{n} objects is under the floor");
}
/// RED: the cumulative sum shifted by one bucket.
///
/// Every query whose first two bytes fall on a boundary is then sent to a slice
/// that does not contain it, and `equivalent` must say which oid first.
#[test]
fn red_a_table_off_by_one_bucket_is_caught() {
let f = fixture(Kind::Sha1, 4200);
let idx_path = index_path(&f.git_dir);
let idx = gix_pack::index::File::at(&idx_path, Kind::Sha1).expect("open the .idx");
let fanout = build_red(&idx, "shift");
let err = equivalent(&idx, &fanout).expect_err("a shifted fanout must not agree with the .idx");
// WHY it fired, not merely that it did: a shifted table sends a query to a
// slice its oid is not in, so the failure is a MISS on an object that is
// present — not a wrong index, and not a spurious hit.
assert!(
err.contains("fanout16 says None") || err.contains("resolved to None"),
"the shifted table failed for the wrong reason: {err}"
);
}
/// RED: the table indexed on the oid's bytes in the wrong order.
///
/// The trap this whole structure exists to avoid, and the one a first-byte-only
/// check cannot see: `(b1 << 8) | b0` is a perfectly valid 16-bit fanout over a
/// permutation of the oid space, so it is self-consistent and total, and it
/// resolves almost every query to the wrong slice.
#[test]
fn red_a_table_indexed_on_swapped_bytes_is_caught() {
let f = fixture(Kind::Sha1, 4200);
let idx_path = index_path(&f.git_dir);
let idx = gix_pack::index::File::at(&idx_path, Kind::Sha1).expect("open the .idx");
let fanout = build_red(&idx, "swap");
let err =
equivalent(&idx, &fanout).expect_err("a byte-swapped fanout must not agree with the .idx");
assert!(
err.contains("fanout16 says None") || err.contains("resolved to None"),
"the swapped table failed for the wrong reason: {err}"
);
}
/// RED: the outside check itself.
///
/// `every_object_resolves_to_the_offset_stock_git_reports` compares against
/// `git verify-pack -v`, and that comparison is worthless if a wrong entry index
/// still yields the right offset. It cannot — offsets are distinct — but
/// *asserting* it is what distinguishes this from a check nobody has watched
/// fail: every object is looked up one entry along, and every one must
/// disagree with git.
#[test]
fn red_the_git_verify_pack_comparison_can_fail() {
let f = fixture(Kind::Sha1, 4200);
let idx_path = index_path(&f.git_dir);
let expected = git_offsets(&f.git_dir, &idx_path);
let idx = gix_pack::index::File::at(&idx_path, Kind::Sha1).expect("open the .idx");
let fanout = Fanout16::build(&idx).expect("the fixture is over the floor");
let mut agreed = 0usize;
let mut disagreed = 0usize;
for (oid_hex, offset) in &expected {
let id = gix_hash::ObjectId::from_hex(oid_hex.as_bytes()).expect("git printed an oid");
let at = fanout.lookup(&idx, &id).expect("present");
let displaced = (at + 1) % idx.num_objects();
if idx.pack_offset_at_index(displaced) == *offset {
agreed += 1;
} else {
disagreed += 1;
}
}
assert_eq!(
agreed, 0,
"{agreed} objects kept git's offset when looked up one entry along, so the outside \
comparison can pass on a wrong index"
);
assert_eq!(disagreed, expected.len());
}
/// The floor is a real answer, and the fallback is the real search.
///
/// A pack under [`Fanout16::MIN_OBJECTS`] gets no table — asserted, because
/// "the fanout is on" is invisible in every other output — and the `PackSet`
/// still resolves every object through git's own 8-bit fanout.
#[test]
fn a_small_pack_gets_no_table_and_is_served_anyway() {
let f = fixture(Kind::Sha1, 200);
let idx_path = index_path(&f.git_dir);
let idx = gix_pack::index::File::at(&idx_path, Kind::Sha1).expect("open the .idx");
assert!(
idx.num_objects() < Fanout16::MIN_OBJECTS,
"the small fixture holds {} objects, at or over the floor",
idx.num_objects()
);
assert!(
Fanout16::build(&idx).is_none(),
"a pack of {} objects was given a 256 KiB table",
idx.num_objects()
);
// …and asking for the fanout on a set of small packs still builds none.
let set = PackSet::load_with(&f.git_dir.join("objects").join("pack"), Kind::Sha1, true)
.expect("load the pack set");
assert_eq!(set.fanout16_footprint(), (0, 0));
for i in 0..idx.num_objects() {
let id = idx.oid_at_index(i).to_owned();
assert!(
set.find(&id).is_some(),
"{id} is in the pack and was not found"
);
}
}
/// The switch really does move the structure, and really does not move the
/// answers.
///
/// The A/B every measurement of this change rests on. A switch that does
/// nothing produces two identical rows and looks like a result, and here
/// nothing *but* `uses_fanout16` and the probe counter can tell the arms apart:
/// the object set and every entry index are defined to be the same.
#[test]
fn the_switch_moves_the_structure_and_not_the_answers() {
let f = fixture(Kind::Sha1, 4200);
let pack_dir = f.git_dir.join("objects").join("pack");
let on = PackSet::load_with(&pack_dir, Kind::Sha1, true).expect("load on");
let off = PackSet::load_with(&pack_dir, Kind::Sha1, false).expect("load off");
assert_eq!(
on.fanout16_footprint(),
(1, 256 * 1024),
"asking for the fanout did not build one"
);
assert_eq!(
off.fanout16_footprint(),
(0, 0),
"declining the fanout still built one"
);
// Same answers, every object, both ways round.
let idx_path = index_path(&f.git_dir);
let idx = gix_pack::index::File::at(&idx_path, Kind::Sha1).expect("open the .idx");
let mut positioned = 0usize;
for i in 0..idx.num_objects() {
let id = idx.oid_at_index(i).to_owned();
let a = on.packs[0].entry_index(&id);
let b = off.packs[0].entry_index(&id);
assert_eq!(a, b, "{id}");
assert_eq!(a, Some(i), "{id} is entry {i}");
positioned += 1;
}
assert_eq!(positioned, idx.num_objects() as usize);
// ── and the table built at open is the one the lookup path read ─────────
//
// Everything above passes with `Pack::entry_index` changed to ignore the
// fanout it holds — that is the identity trap, and it is why the counter
// exists. `uses_fanout16` says a table exists; only the probe count says it
// was consulted, and consulted the right number of times.
//
// One call per object above, and none at all in a release build, where the
// counter is compiled out.
if cfg!(debug_assertions) {
assert_eq!(
on.packs[0].fanout16_probes(),
positioned as u64,
"the fanout answered {} of {} lookups made through it",
on.packs[0].fanout16_probes(),
positioned
);
assert_eq!(
off.packs[0].fanout16_probes(),
0,
"the arm with no table answered lookups with one"
);
}
}
/// A [`Fanout16`] built wrong on purpose.
///
/// Not an env switch inside `Fanout16::build`: a red that lives in the shipping
/// path is a branch production can take. This rebuilds the table here, from the
/// same `.idx`, with the one line under test changed — which is also what makes
/// it a statement about *this* table and not about a different corpus.
fn build_red(idx: &gix_pack::index::File, how: &str) -> Fanout16 {
let n = idx.num_objects();
let mut table = vec![0u32; 65_536];
for i in 0..n {
let bytes = idx.oid_at_index(i).as_bytes();
let b = match how {
"swap" => (usize::from(bytes[1]) << 8) | usize::from(bytes[0]),
_ => (usize::from(bytes[0]) << 8) | usize::from(bytes[1]),
};
table[b] += 1;
}
let mut acc = 0u32;
for c in table.iter_mut() {
acc += *c;
*c = acc;
}
if how == "shift" {
// The classic: `table[b]` now holds the count through `b-1`, so every
// bucket's slice is the previous bucket's.
table.rotate_right(1);
table[0] = 0;
}
Fanout16::from_table_for_tests(table)
}