crates/storage-git-gix/parked-gix-2/coldtier-archive/refstore.rs
//! `ls-remote` answered from the archive: `__gunnar_refs__` behind an `STree32`.
//!
//! Until this module, `__gunnar_refs__` was a **write-only sidecar**. `seal()`
//! wrote it (`crate::refs_reserved_builder`, the one composition point), the two
//! seals read it straight back to verify, and [`crate::unfold`] read it to
//! reconstitute a repository. **Nothing answered a client request from it.**
//! This is the reader that does, and it implements [`gunnar_store::RefStore`],
//! so the advertisement path in `gunnar-wire` cannot tell it from the `gix-ref`
//! one.
//!
//! No `gix-ref`. No filesystem. One archive, opened once.
//!
//! # What `ls-remote` actually asks for, which is not what one would guess
//!
//! A ref advertisement is a **full ordered scan**, not a point lookup:
//! `gunnar-wire`'s `write_ref_advertisement` calls `head()` once and
//! `iter(None)` once, and emits every ref in byte-sorted name order. So the
//! honest accounting is:
//!
//! - The **scan** is made cheap by folding and sorting **at seal**, where it is
//! free — `seal()` already holds every ref in hand. It is not made cheap by
//! the tree, and this module does not pretend otherwise.
//! - The **tree** pays for `read(name)`, the single-ref lookup. `ls-remote`
//! itself spends only a symref chase there (`HEAD` → `refs/heads/main`), but
//! `read()` is what `fetch` and `push` hammer — every push reads its own ref
//! to check the old value — and it is the operation whose cost would otherwise
//! grow with the number of pushes rather than with the number of refs.
//!
//! Reporting this the other way round — "the index made `ls-remote` fast" —
//! would be a claim the measurement does not support (LAW 7).
//!
//! # Keying variable-length ref names in 32 bits
//!
//! The `STree32` work that preceded this indexed **oids**, where the tree holds
//! a 32-bit prefix of a uniformly random key and the full oid is compared at the
//! landing position. Ref names are neither fixed-length nor uniform, so the key
//! had to be decided rather than inherited. Three candidates:
//!
//! **1. The first four bytes of the name, big-endian.** Order-preserving, so one
//! sorted array would serve both the scan and the lookup, with no permutation.
//! It is also **useless here, and measurably so**: every ref in a bare
//! repository begins `refs/`, so the key is the constant `b"refs"` =
//! `0x72656673` for *every* row. [`tests::the_prefix_key_collapses_and_the_hash_does_not`] asserts it
//! on the real corpus. The tree would degenerate to a linear scan of the whole
//! namespace on every lookup. **This is the one real difference from the oid
//! workload**: oids are uniformly random, ref names share a long prefix by
//! construction. An order-preserving 32-bit digest of a ref namespace does not
//! exist, because the order is carried almost entirely in the bytes *after* the
//! shared prefix.
//!
//! **2. Four bytes taken from after the common prefix.** Recovers distribution
//! only until two ref hierarchies diverge at different depths, and makes the key
//! depend on the corpus. Rejected as brittle: the key would change meaning the
//! day a repository gains its first `refs/remotes/`.
//!
//! **3. A 32-bit hash of the full name — chosen.** Distribution is independent
//! of the namespace's shape, which is exactly the property (1) and (2) lack. It
//! gives up order, so the index is a **separate permutation** rather than the
//! storage order: rows stay sorted by name for the scan, and `(hash, row)` pairs
//! sorted by hash feed the tree.
//!
//! ## Collision resolution
//!
//! Equal hashes form a **contiguous run** in `hkey`, because `hkey` is sorted.
//! [`STree32::lower_bound`] lands on the first element of that run; the lookup
//! then walks forward while the hash still matches and compares the **full ref
//! name** at each position. So a collision costs one extra string comparison,
//! never a wrong answer — the hash is a filter, the name is the truth. Same
//! shape as the oid lane's "compare the full oid at the landing position", with
//! the name playing the oid's part.
//!
//! Expected extra comparisons per query is `n / 2^32`: 2·10⁻⁴ at a million refs,
//! 2·10⁻⁷ at the 848 this corpus actually holds.
//! [`tests::a_real_hash_collision_still_answers`] does not rely on that being
//! rare — it **forces** a collision and asserts both colliding names still
//! resolve correctly, because a path taken 2·10⁻⁴ of the time is a path no
//! corpus test will ever reach on its own (LAW 2).
//!
//! `u32::MAX` is `STree32`'s sentinel for an unused slot, so the hash is folded
//! away from it. That costs a 2⁻³² increase in collision probability and removes
//! a class of bug that would only ever appear on one ref name in four billion.
//!
//! # Where the index is built, and why not on disk
//!
//! At **open**, in memory, from the already-name-sorted rows — an O(n) hash pass
//! plus a sort of `n` `u64`s, never a string sort. **Never on the push path**:
//! pushes do not write `__gunnar_refs__` at all (`cold_tier.rs` keeps
//! `refs_reserved_builder` the only writer, and `cold_tier_wired.rs` asserts
//! it), so there is nothing here for a push to rebuild. An append that had to
//! rebuild an index over every ref would make push O(repo) instead of O(push),
//! which is the mistake this deliberately does not make.
//!
//! It is deliberately **not** persisted as a reserved section, and that is a
//! reasoned decision rather than a shortcut. Persisting would mean a new
//! `__gunnar_*` module in `znippy-common`, and `meta_sink_append.rs`'s
//! `open_existing` carries **no generic carry-forward**: it rewinds to the
//! lowest `index_offset` and rebuilds the tail, recovering data rows and
//! `META_MODULE` **by hand**, so every other reserved section not re-supplied on
//! append is silently dropped. A persisted index would therefore be a second
//! thing that can disagree with `__gunnar_refs__`, and the disagreement would be
//! *silent* — a stale index answering confidently. Rebuilding costs one linear
//! pass over data the open already read.
use std::collections::BTreeMap;
use std::path::Path;
use anyhow::{anyhow, Result};
use gunnar_store::refs::{FullName, RefEdit, RefStore, Target};
use znippy_plugin_git::{read_refs, RefState};
use znippy_zoomies::stree32::STree32;
/// `STree32`'s sentinel for an unused slot. A key equal to it is folded down.
const SENTINEL: u32 = u32::MAX;
/// Below this many refs the tree is not built at all and lookups binary-search
/// the name-sorted rows instead.
///
/// **This threshold is a measurement, not a taste.** `gunnar.coldtier_refs_index`
/// (oden, 2026-08-04, pinned to 4 cores, load1 19.55) against the same lookup
/// answered from a `BTreeMap<String, RefState>`:
///
/// | refs | indexed | BTreeMap | tree is |
/// |---:|---:|---:|---|
/// | 4 | 40.9 ns | 18.1 ns | **0.44× — a loss** |
/// | 100 | 60.3 ns | 43.1 ns | **0.71× — a loss** |
/// | 1 000 | 62.9 ns | 100.9 ns | 1.60× |
/// | 10 000 | 83.3 ns | 162.4 ns | 1.95× |
/// | 100 000 | 245.8 ns | 347.3 ns | 1.41× |
/// | 866 000 | 434.8 ns | 601.0 ns | 1.38× |
///
/// The reason is structural rather than incidental: a lookup must hash the whole
/// name (O(len)) *and* compare the whole name at the landing position (O(len)),
/// so the tree only removes the `log n` string comparisons in between. When
/// there are only a handful of those, it has removed nothing and added a hash.
///
/// **The 19 `workspace_nordisk` repositories hold 4 to 125 refs.** So at the
/// sizes gunnar actually serves, building the tree would make `ls-remote`
/// *slower* and cost 12.25 B/ref of resident memory for the privilege. The bar
/// for this lane was "at least as fast", and a threshold is how it is met
/// honestly rather than by quoting the 10 000-ref cell.
///
/// 512 sits inside the measured crossover (between the 100 and 1 000 rungs) and
/// is a power of two for no better reason than that it is easy to reason about.
const TREE_THRESHOLD: usize = 512;
/// One ref as the archive holds it, already decoded.
#[derive(Debug, Clone)]
struct Row {
name: FullName,
target: Target,
/// The peeled target of an annotated tag, when the seal recorded one.
peeled: Option<gix_hash::ObjectId>,
}
/// The ref namespace of one repository, read out of its znippy archive.
///
/// Read-only by construction: an archive is the **batch** tier, sealed by `gc`.
/// [`RefStore::transaction`] and [`RefStore::set_head`] therefore refuse rather
/// than pretend, because a write that silently went nowhere would look exactly
/// like a successful push.
pub struct ArchiveRefStore {
/// Sorted by name, `HEAD` excluded. **This is the advertisement's scan
/// order**, established at seal and asserted at open by `assert_sorted`.
rows: Vec<Row>,
/// `hkey[i] == hash_ref_name(rows[perm[i]].name)`, ascending. Tree input.
hkey: Vec<u32>,
/// `perm[i]` indexes [`Self::rows`].
perm: Vec<u32>,
/// `None` for an empty namespace — `STree32::new` rejects an empty slice.
tree: Option<STree32>,
/// `HEAD`, which is not under `refs/` and so is not in [`Self::rows`].
head: Option<Target>,
/// Bumped by every lookup that went through the tree.
///
/// **This exists because of a real incident** (2026-08-04): a lane's
/// fidelity check compared two outputs that agreed *by design*, so it stayed
/// green while measuring the wrong path for a whole round. Comparing bytes
/// cannot tell you which code produced them. [`Self::probes`] lets a test
/// assert that the path it believes answered is the path that answered.
probes: std::sync::atomic::AtomicU64,
/// Bumped by every `RefStore` call this store answered, of any kind.
///
/// [`Self::probes`] only counts lookups that reached the tree, and the
/// advertisement's hot path is `head()` + `iter()`, neither of which does.
/// So a fidelity test that asserted only `probes() > 0` would be asserting
/// something about the symref chase and nothing about the scan — a guard
/// that is green for the wrong reason. This counts the scan too.
served: std::sync::atomic::AtomicU64,
}
impl std::fmt::Debug for ArchiveRefStore {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("ArchiveRefStore")
.field("refs", &self.rows.len())
.field("head", &self.head.is_some())
.finish()
}
}
/// A 32-bit hash of a ref name.
///
/// FNV-1a over the bytes, then a `splitmix64` finalizer, then the high 32 bits.
/// Written out rather than pulled in: a hashing crate would be a third-party
/// package on a graph the dependency guard counts in packages, for eleven lines
/// of arithmetic.
///
/// The finalizer is the load-bearing half. FNV-1a alone avalanches poorly in its
/// high bits, and ref names differ mostly in their **last** bytes
/// (`refs/heads/main` vs `refs/heads/mine`), which is precisely the case where a
/// weak final mix leaves neighbours adjacent.
#[inline]
pub fn hash_ref_name(name: &[u8]) -> u32 {
let mut h: u64 = 0xcbf2_9ce4_8422_2325;
for &b in name {
h ^= b as u64;
h = h.wrapping_mul(0x0000_0100_0000_01b3);
}
h ^= h >> 30;
h = h.wrapping_mul(0xbf58_476d_1ce4_e5b9);
h ^= h >> 27;
h = h.wrapping_mul(0x94d0_49bb_1331_11eb);
h ^= h >> 31;
let k = (h >> 32) as u32;
// Never hand the tree its own sentinel.
if k == SENTINEL {
SENTINEL - 1
} else {
k
}
}
impl ArchiveRefStore {
/// Open the ref namespace sealed in `archive`.
///
/// `Ok(None)` when the archive carries no `__gunnar_refs__` section at all —
/// distinct from an archive whose namespace is empty, which is
/// `Ok(Some(store))` with no rows. `unfold` draws the same distinction and
/// for the same reason: "this repository has no refs" and "this archive
/// predates refs being sealed" call for different handling.
pub fn open(archive: &Path) -> Result<Option<Self>> {
match read_refs(archive)? {
None => Ok(None),
Some(folded) => Ok(Some(Self::from_folded(folded)?)),
}
}
/// Build from an already-folded namespace.
///
/// Split out so a test can drive the index over a namespace it built itself,
/// and so [`open`](Self::open) has exactly one body.
pub fn from_folded(folded: BTreeMap<String, RefState>) -> Result<Self> {
let mut head = None;
let mut rows: Vec<Row> = Vec::with_capacity(folded.len());
for (name, state) in folded {
let target = match (&state.target, &state.symref_target) {
(_, Some(sym)) => {
Target::Symbolic(FullName::new(sym.as_bytes()).map_err(|e| {
anyhow!("sealed symref target '{sym}' is not a ref name: {e}")
})?)
}
(Some(oid), None) => {
Target::Object(oid.parse::<gix_hash::ObjectId>().map_err(|e| {
anyhow!("sealed target '{oid}' for '{name}' is not an oid: {e}")
})?)
}
// `fold` removes a row that is neither, so this is unreachable
// through `read_refs`. Refused rather than skipped: a ref that is
// present and points nowhere is corruption, and dropping it
// silently would turn corruption into a merely missing branch.
(None, None) => {
return Err(anyhow!(
"'{name}' was sealed with neither a target nor a symref target"
))
}
};
let peeled = match &state.peeled {
None => None,
Some(p) => Some(p.parse::<gix_hash::ObjectId>().map_err(|e| {
anyhow!("sealed peeled oid '{p}' for '{name}' is not an oid: {e}")
})?),
};
if name == gunnar_store::refs::HEAD {
head = Some(target);
continue;
}
let full = FullName::new(name.as_bytes())
.map_err(|e| anyhow!("sealed ref name '{name}' is not a ref name: {e}"))?;
rows.push(Row {
name: full,
target,
peeled,
});
}
// `folded` is a `BTreeMap<String, _>`, so it arrived in byte-lexicographic
// order and removing `HEAD` cannot disturb that. Asserted rather than
// assumed: the advertisement's byte-identity rests entirely on this
// order, and nothing downstream re-sorts — `gunnar-wire`'s `collect_refs`
// appends `iter()` verbatim.
Self::assert_sorted(&rows)?;
let (hkey, perm, tree) = Self::build_index(&rows);
Ok(Self {
rows,
hkey,
perm,
tree,
head,
probes: std::sync::atomic::AtomicU64::new(0),
served: std::sync::atomic::AtomicU64::new(0),
})
}
fn assert_sorted(rows: &[Row]) -> Result<()> {
for w in rows.windows(2) {
if w[0].name.as_bytes() >= w[1].name.as_bytes() {
return Err(anyhow!(
"the sealed ref namespace is not in ascending name order at '{}' / '{}'; the \
advertisement would diverge from the gix-ref one",
w[0].name.to_str_lossy(),
w[1].name.to_str_lossy()
));
}
}
Ok(())
}
/// The O(n) half: hash every name, sort the `(hash, row)` pairs, build the
/// tree. No string sort — `rows` is already in name order.
fn build_index(rows: &[Row]) -> (Vec<u32>, Vec<u32>, Option<STree32>) {
// Below the threshold the rows ARE the index: they are already sorted by
// name, so a binary search over them costs nothing to build and nothing
// to hold. See [`TREE_THRESHOLD`] for the measurement that put it here.
if rows.len() < TREE_THRESHOLD {
return (Vec::new(), Vec::new(), None);
}
let mut pairs: Vec<(u32, u32)> = rows
.iter()
.enumerate()
.map(|(i, r)| (hash_ref_name(r.name.as_bytes()), i as u32))
.collect();
// Ties broken by row, so a rebuild produces byte-identical arrays.
pairs.sort_unstable();
let hkey: Vec<u32> = pairs.iter().map(|(h, _)| *h).collect();
let perm: Vec<u32> = pairs.iter().map(|(_, i)| *i).collect();
let tree = STree32::new(&hkey);
(hkey, perm, Some(tree))
}
/// The row index for `name`, through the tree.
///
/// `lower_bound` lands on the first key `>= h`; the walk forward over the run
/// of equal hashes is the collision resolution, and the **name** decides.
fn find(&self, name: &FullName) -> Option<usize> {
let Some(tree) = self.tree.as_ref() else {
// No tree: binary-search the name-sorted rows. Correctness is
// identical — `a_small_and_a_large_namespace_answer_identically`
// drives the same namespace either side of the threshold and
// compares every answer.
return self
.rows
.binary_search_by(|r| r.name.as_bytes().cmp(name.as_bytes()))
.ok();
};
self.probes
.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
let h = hash_ref_name(name.as_bytes());
let mut i = tree.lower_bound(h);
while i < self.hkey.len() && self.hkey[i] == h {
let row = self.perm[i] as usize;
if self.rows[row].name.as_bytes() == name.as_bytes() {
return Some(row);
}
i += 1;
}
None
}
/// How many lookups went through the tree.
///
/// The anti-blindness counter; see the field's own docs. A byte comparison
/// cannot tell which backend produced the bytes, so a fidelity test asserts
/// this moved.
pub fn probes(&self) -> u64 {
self.probes.load(std::sync::atomic::Ordering::Relaxed)
}
/// How many `RefStore` calls this store answered, of any kind.
///
/// The counter a fidelity test should assert on: it moves for the scan as
/// well as for the lookups. See the field's docs.
pub fn served(&self) -> u64 {
self.served.load(std::sync::atomic::Ordering::Relaxed)
}
#[inline]
fn serve(&self) {
self.served
.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
}
/// The peeled target the seal recorded for `name`, if any.
///
/// **Only ever `Some` for an archive sealed by a gunnar that fills the
/// column.** `peeled` has been in `refs_schema()` since the section was
/// defined and `ref_update` never wrote it, so an archive sealed before this
/// lane answers `None` here — which is why `gunnar-wire` peels through the
/// object database and this is an accelerator rather than the source of
/// truth. A `None` therefore means "not recorded", never "not a tag", and a
/// caller that treated it as the latter would drop `^{}` lines from the
/// advertisement of every older archive.
pub fn peeled(&self, name: &FullName) -> Option<gix_hash::ObjectId> {
self.find(name).and_then(|i| self.rows[i].peeled)
}
/// The sealed value of `name`, **without touching the counters**.
///
/// The overlay's chain validation asks this for every reference in its
/// delta, and those are not requests anyone served — counting them would
/// make `served()` report work the advertisement did not do, which is the
/// exact failure the counter exists to prevent.
pub(crate) fn peek(&self, name: &FullName) -> Option<Target> {
if name.is_head() {
return self.head.clone();
}
self.find(name).map(|i| self.rows[i].target.clone())
}
/// Number of refs under `refs/`, `HEAD` excluded.
pub fn len(&self) -> usize {
self.rows.len()
}
pub fn is_empty(&self) -> bool {
self.rows.is_empty()
}
/// Resident size of the index alone, in bytes — tree nodes plus both arrays.
///
/// The `rows` are the data, not the index, and are excluded on purpose: the
/// question a bench asks is what the *index* costs on top of holding the
/// refs at all. **Zero below [`TREE_THRESHOLD`]**, which is every repository
/// in the corpus this was measured on.
pub fn index_bytes(&self) -> usize {
let tree = self
.tree
.as_ref()
.map_or(0, |_| Self::tree_bytes(self.hkey.len()));
tree + self.hkey.len() * 4 + self.perm.len() * 4
}
/// `STree32`'s node array for `n` keys: a 16-ary tree of 64-byte nodes.
fn tree_bytes(n: usize) -> usize {
const B: usize = 16;
let mut nodes = 0usize;
let mut level = n.div_ceil(B);
while level > 1 {
nodes += level;
level = level.div_ceil(B + 1);
}
nodes += 1;
nodes * B * 4
}
}
impl RefStore for ArchiveRefStore {
fn read(&self, name: &FullName) -> gunnar_store::Result<Option<Target>> {
self.serve();
if name.is_head() {
return Ok(self.head.clone());
}
Ok(self.find(name).map(|i| self.rows[i].target.clone()))
}
fn iter(&self, prefix: Option<&str>) -> gunnar_store::Result<Vec<(FullName, Target)>> {
self.serve();
// Sorted by construction, so a prefix is a contiguous range and the scan
// is a slice. No sort here, and none downstream — see `assert_sorted`.
let range: &[Row] = match prefix {
None => &self.rows,
Some(p) => {
let pb = p.as_bytes();
let lo = self.rows.partition_point(|r| r.name.as_bytes() < pb);
let hi =
lo + self.rows[lo..].partition_point(|r| r.name.as_bytes().starts_with(pb));
&self.rows[lo..hi]
}
};
Ok(range
.iter()
.map(|r| (r.name.clone(), r.target.clone()))
.collect())
}
fn head(&self) -> gunnar_store::Result<Option<Target>> {
self.serve();
Ok(self.head.clone())
}
fn transaction(&self, _edits: Vec<RefEdit>) -> gunnar_store::Result<Vec<RefEdit>> {
Err(read_only("a reference transaction"))
}
fn set_head(&self, _target: Target) -> gunnar_store::Result<()> {
Err(read_only("setting HEAD"))
}
}
/// One refusal, worded once.
fn read_only(what: &str) -> gunnar_store::Error {
gunnar_store::Error::Backend(anyhow!(
"{what} was attempted against a sealed archive, which is the batch tier and is read-only; \
the write path is the live store, and `gunnar gc` is what folds it back into an archive"
))
}
#[cfg(test)]
mod tests {
use super::*;
use znippy_plugin_git::pushlog::truncate_for_test;
use znippy_plugin_git::{RefLog, RefUpdate};
fn tmpdir(tag: &str) -> std::path::PathBuf {
let ns = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.unwrap()
.as_nanos();
// Scratch on md1, never /tmp — /tmp is RAM on this box.
let base = std::env::var("GUNNAR_TEST_SCRATCH")
.unwrap_or_else(|_| "/home/rickard/scratch/cargo/gunnar-refs/t".to_string());
let d = std::path::PathBuf::from(base).join(format!("refstore_{tag}_{ns}"));
std::fs::create_dir_all(&d).unwrap();
d
}
fn oid(c: char) -> String {
std::iter::repeat_n(c, 40).collect()
}
fn store_of(log: &RefLog) -> ArchiveRefStore {
ArchiveRefStore::from_folded(log.current().unwrap()).unwrap()
}
fn name(s: &str) -> FullName {
FullName::new(s.as_bytes()).unwrap()
}
/// **The single most likely correctness bug in a log-structured ref store.**
///
/// A ref deleted in push N+1 must not come back when push N is replayed.
/// Multi-frame on purpose: gunnar's own `seal` writes one snapshot frame, so
/// a single-frame test would pass against a store that ignored ordering
/// entirely and could never see this.
#[test]
fn a_deletion_is_not_resurrected_by_replaying_the_earlier_push() {
let dir = tmpdir("delete");
let log = RefLog::new(dir.join("refs.log"));
log.push(&[
RefUpdate::set("refs/heads/main", oid('a')),
RefUpdate::set("refs/heads/doomed", oid('b')),
])
.unwrap();
log.push(&[RefUpdate::delete("refs/heads/doomed")]).unwrap();
let store = store_of(&log);
// Through the tree, which is the path a real lookup takes.
assert_eq!(
store.read(&name("refs/heads/doomed")).unwrap(),
None,
"a ref deleted in a later push was resurrected by replaying the earlier one"
);
assert!(
store.served() > 0,
"the lookup did not go through the archive store at all"
);
// And through the scan, which is the path the advertisement takes. Both,
// because an index and a scan that disagree is exactly the failure a
// single-path test cannot see.
let names: Vec<String> = store
.iter(None)
.unwrap()
.into_iter()
.map(|(n, _)| n.to_str_lossy().into_owned())
.collect();
assert_eq!(
names,
vec!["refs/heads/main".to_string()],
"the scan disagrees with the index"
);
}
/// A force-update takes the later value, not the larger or the first one.
#[test]
fn a_force_update_takes_the_later_push() {
let dir = tmpdir("force");
let log = RefLog::new(dir.join("refs.log"));
// 'f' > '0', so a store that compared oids rather than push order would
// still pass if the values only ever grew. They do not here: the second
// push moves main BACKWARDS, which is what a force-push does.
log.push(&[RefUpdate::set("refs/heads/main", oid('f'))])
.unwrap();
log.push(&[RefUpdate::set("refs/heads/main", oid('0'))])
.unwrap();
let store = store_of(&log);
assert_eq!(
store.read(&name("refs/heads/main")).unwrap(),
Some(Target::Object(oid('0').parse().unwrap())),
"a force-update that moved the ref backwards was ignored"
);
}
/// A ref deleted and then re-created must exist, with the new value. The
/// mirror of the resurrection test — a store that fixed resurrection by
/// making deletion sticky would pass that one and fail this.
#[test]
fn a_recreated_ref_comes_back() {
let dir = tmpdir("recreate");
let log = RefLog::new(dir.join("refs.log"));
log.push(&[RefUpdate::set("refs/heads/x", oid('a'))])
.unwrap();
log.push(&[RefUpdate::delete("refs/heads/x")]).unwrap();
log.push(&[RefUpdate::set("refs/heads/x", oid('c'))])
.unwrap();
let store = store_of(&log);
assert_eq!(
store.read(&name("refs/heads/x")).unwrap(),
Some(Target::Object(oid('c').parse().unwrap())),
"a deleted-then-recreated ref stayed deleted"
);
}
/// Truncate mid-frame at **every** byte offset of the last push and assert
/// recovery stops at the last complete frame: the namespace is the one as of
/// push N, never half of push N+1, and never an error.
#[test]
fn a_torn_frame_recovers_to_the_last_complete_push() {
let dir = tmpdir("torn");
let path = dir.join("refs.log");
let log = RefLog::new(&path);
log.push(&[RefUpdate::set("refs/heads/main", oid('a'))])
.unwrap();
let before = std::fs::metadata(&path).unwrap().len();
log.push(&[
RefUpdate::set("refs/heads/main", oid('9')),
RefUpdate::set("refs/heads/late", oid('1')),
])
.unwrap();
let after = std::fs::metadata(&path).unwrap().len();
let intact = std::fs::read(&path).unwrap();
assert!(
after > before + 1,
"the second push wrote nothing to cut into"
);
for cut in (before + 1)..after {
std::fs::write(&path, &intact).unwrap();
truncate_for_test(&path, cut).unwrap();
let store = store_of(&log);
assert_eq!(
store.read(&name("refs/heads/main")).unwrap(),
Some(Target::Object(oid('a').parse().unwrap())),
"cut at {cut}: main must still hold the value from the last COMPLETE push"
);
assert_eq!(
store.read(&name("refs/heads/late")).unwrap(),
None,
"cut at {cut}: a torn push leaked one of its refs"
);
assert_eq!(store.len(), 1, "cut at {cut}: wrong namespace size");
}
// Intact again: the whole push lands, which proves the loop above was
// rejecting torn frames rather than rejecting everything.
std::fs::write(&path, &intact).unwrap();
let store = store_of(&log);
assert_eq!(store.len(), 2, "the complete push must publish both refs");
assert_eq!(
store.read(&name("refs/heads/main")).unwrap(),
Some(Target::Object(oid('9').parse().unwrap()))
);
}
/// The argument for hashing, made as a measurement rather than a claim.
///
/// A 32-bit key taken as the first four bytes of the name collapses to ONE
/// distinct value across a realistic namespace, because every ref begins
/// `refs/`. The hash does not.
#[test]
fn the_prefix_key_collapses_and_the_hash_does_not() {
let names: Vec<String> = (0..500)
.map(|i| {
if i % 3 == 0 {
format!("refs/heads/branch-{i}")
} else if i % 3 == 1 {
format!("refs/tags/v{i}")
} else {
format!("refs/remotes/origin/topic-{i}")
}
})
.collect();
let prefix_keys: std::collections::HashSet<u32> = names
.iter()
.map(|n| {
let b = n.as_bytes();
u32::from_be_bytes([b[0], b[1], b[2], b[3]])
})
.collect();
assert_eq!(
prefix_keys.len(),
1,
"the first-four-bytes key was expected to collapse to the single constant b\"refs\"; \
if this ever reports more than 1 the corpus stopped being ref names"
);
assert_eq!(
prefix_keys.into_iter().next().unwrap(),
u32::from_be_bytes(*b"refs")
);
let hash_keys: std::collections::HashSet<u32> =
names.iter().map(|n| hash_ref_name(n.as_bytes())).collect();
assert_eq!(
hash_keys.len(),
names.len(),
"the hash collided on a 500-name corpus, which at 500/2^32 should not happen"
);
}
/// Collision resolution, driven through the **real** lookup path.
///
/// These two names genuinely collide under [`hash_ref_name`] — both hash to
/// `0xe0ba3b6a`, found by exhaustive search over `refs/heads/b<n>` and
/// asserted below so the test fails loudly if the hash is ever retuned
/// rather than silently becoming a test of nothing.
///
/// The first version of this test built the run scan inline instead of
/// calling [`ArchiveRefStore::read`], which made it a test of a *copy* of the
/// logic — a hollow guard that would stay green while the real path was
/// broken. It now goes through `read`, and `probes()` proves it.
#[test]
fn a_real_hash_collision_still_answers() {
const A: &str = "refs/heads/b31361";
const B: &str = "refs/heads/b85140";
assert_eq!(
hash_ref_name(A.as_bytes()),
hash_ref_name(B.as_bytes()),
"these names no longer collide, so this test would no longer exercise the run scan"
);
let dir = tmpdir("collide");
let log = RefLog::new(dir.join("refs.log"));
// Padded past `TREE_THRESHOLD` on purpose: below it there is no tree and
// no run scan, so a three-ref version of this test would exercise binary
// search and prove nothing about collision handling.
let mut updates = vec![RefUpdate::set(A, oid('a')), RefUpdate::set(B, oid('b'))];
for i in 0..TREE_THRESHOLD + 100 {
updates.push(RefUpdate::set(format!("refs/heads/pad-{i:05}"), oid_n(i)));
}
log.push(&updates).unwrap();
let store = store_of(&log);
let before = store.probes();
// Both colliding names must resolve to their OWN target. A run scan that
// stopped at the first match would give one of them the other's oid.
assert_eq!(
store.read(&name(A)).unwrap(),
Some(Target::Object(oid('a').parse().unwrap())),
"{A} got the wrong target out of a real hash-collision run"
);
assert_eq!(
store.read(&name(B)).unwrap(),
Some(Target::Object(oid('b').parse().unwrap())),
"{B} got the wrong target out of a real hash-collision run"
);
// An absent name that lands in the SAME colliding run must still miss,
// rather than returning whichever row the scan stopped on.
let ghost = FullName::new(b"refs/heads/b99999999").unwrap();
assert_eq!(
store.read(&ghost).unwrap(),
None,
"an absent name matched inside the run"
);
assert!(
store.len() >= TREE_THRESHOLD,
"the namespace must be big enough to build a tree"
);
assert_eq!(store.probes() - before, 3, "a lookup bypassed the tree");
}
/// `HEAD` is sealed under its own name and must leave `iter()` — the trait
/// contract is that `iter` yields only names under `refs/`. A `HEAD` leaking
/// into the scan would put an extra line in the advertisement.
#[test]
fn head_is_answered_but_never_iterated() {
let dir = tmpdir("head");
let log = RefLog::new(dir.join("refs.log"));
log.push(&[
RefUpdate::symbolic("HEAD", "refs/heads/main"),
RefUpdate::set("refs/heads/main", oid('a')),
])
.unwrap();
let store = store_of(&log);
assert_eq!(
store.head().unwrap(),
Some(Target::Symbolic(name("refs/heads/main"))),
"HEAD was not answered from the archive"
);
assert!(
store.iter(None).unwrap().iter().all(|(n, _)| !n.is_head()),
"HEAD leaked into iter(), which would add a line to the advertisement"
);
// The symref chase the advertisement actually performs.
assert_eq!(
store.resolve(&name("HEAD")).unwrap(),
Some(oid('a').parse().unwrap()),
"the HEAD symref did not resolve through the archive"
);
}
/// `iter(prefix)` must return a contiguous, correctly-bounded range.
#[test]
fn a_prefix_scan_is_bounded_on_both_sides() {
let dir = tmpdir("prefix");
let log = RefLog::new(dir.join("refs.log"));
log.push(&[
RefUpdate::set("refs/heads/a", oid('1')),
RefUpdate::set("refs/heads/b", oid('2')),
RefUpdate::set("refs/tags/v1", oid('3')),
RefUpdate::set("refs/remotes/origin/a", oid('4')),
])
.unwrap();
let store = store_of(&log);
let heads: Vec<String> = store
.iter(Some("refs/heads/"))
.unwrap()
.into_iter()
.map(|(n, _)| n.to_str_lossy().into_owned())
.collect();
assert_eq!(
heads,
vec!["refs/heads/a".to_string(), "refs/heads/b".to_string()]
);
let tags: Vec<String> = store
.iter(Some("refs/tags/"))
.unwrap()
.into_iter()
.map(|(n, _)| n.to_str_lossy().into_owned())
.collect();
assert_eq!(tags, vec!["refs/tags/v1".to_string()]);
assert_eq!(store.iter(Some("refs/nope/")).unwrap().len(), 0);
assert_eq!(store.iter(None).unwrap().len(), 4);
}
/// The archive is the batch tier. A write must be refused, not swallowed.
#[test]
fn writes_are_refused_rather_than_silently_dropped() {
let dir = tmpdir("ro");
let log = RefLog::new(dir.join("refs.log"));
log.push(&[RefUpdate::set("refs/heads/main", oid('a'))])
.unwrap();
let store = store_of(&log);
assert!(
store.transaction(vec![]).is_err(),
"a transaction against an archive was accepted"
);
assert!(
store
.set_head(Target::Symbolic(name("refs/heads/main")))
.is_err(),
"set_head against an archive was accepted"
);
}
/// An out-of-order namespace must be refused at open, because the
/// advertisement's byte-identity rests entirely on the scan order and
/// nothing downstream re-sorts.
#[test]
fn an_unsorted_namespace_is_refused() {
let rows = vec![
Row {
name: name("refs/heads/zebra"),
target: Target::Object(oid('a').parse().unwrap()),
peeled: None,
},
Row {
name: name("refs/heads/aardvark"),
target: Target::Object(oid('b').parse().unwrap()),
peeled: None,
},
];
assert!(
ArchiveRefStore::assert_sorted(&rows).is_err(),
"the sort guard accepted a descending namespace; it can never report red"
);
let mut sorted = rows;
sorted.sort_by(|a, b| a.name.as_bytes().cmp(b.name.as_bytes()));
assert!(
ArchiveRefStore::assert_sorted(&sorted).is_ok(),
"the guard rejects a sorted one"
);
}
/// The same namespace answered either side of [`TREE_THRESHOLD`], compared
/// answer by answer.
///
/// The threshold means there are **two** lookup implementations, and two
/// implementations of one thing is exactly how a store starts answering
/// differently depending on how many refs it happens to hold. This drives a
/// namespace big enough for a tree, then the same names again with the tree
/// suppressed, and requires every answer — hit and miss — to agree.
#[test]
fn a_small_and_a_large_namespace_answer_identically() {
let n = TREE_THRESHOLD + 200;
let mut folded = BTreeMap::new();
for i in 0..n {
folded.insert(
format!("refs/heads/b{i:06}"),
RefState {
target: Some(oid_n(i)),
peeled: None,
symref_target: None,
push_seq: 0,
updated_ms: 0,
},
);
}
let with_tree = ArchiveRefStore::from_folded(folded.clone()).unwrap();
assert!(
with_tree.tree.is_some(),
"the large namespace built no tree"
);
// The same rows with the tree taken away — the small-namespace path.
let mut without_tree = ArchiveRefStore::from_folded(folded).unwrap();
without_tree.tree = None;
without_tree.hkey = Vec::new();
without_tree.perm = Vec::new();
for i in 0..n {
let q = name(&format!("refs/heads/b{i:06}"));
assert_eq!(
with_tree.read(&q).unwrap(),
without_tree.read(&q).unwrap(),
"the two lookup paths disagree on refs/heads/b{i:06}"
);
}
// Misses too: a binary search that returned `Ok` on a near-miss would
// only ever show up here.
for q in [
"refs/heads/b",
"refs/heads/b000000x",
"refs/heads/c000000",
"refs/tags/v1",
] {
let q = name(q);
assert_eq!(with_tree.read(&q).unwrap(), None, "{q:?} should miss");
assert_eq!(without_tree.read(&q).unwrap(), None, "{q:?} should miss");
}
assert!(with_tree.probes() > 0, "the tree path never used the tree");
assert_eq!(without_tree.probes(), 0, "the no-tree path used a tree");
}
/// Companion to [`a_deletion_is_not_resurrected_by_replaying_the_earlier_push`]:
/// proof that its assertions are **discriminating**.
///
/// It hands the store exactly the namespace a broken fold would produce —
/// the one where the delete was ignored — and asserts the store reports the
/// doomed ref as present, through both the index and the scan. A test that
/// could not tell those two namespaces apart would be worth nothing, and
/// there is no way to break `fold` from this crate to find out.
#[test]
fn the_deletion_guard_can_see_a_resurrected_ref() {
let mut folded = BTreeMap::new();
for (n, c) in [("refs/heads/main", 'a'), ("refs/heads/doomed", 'b')] {
folded.insert(
n.to_string(),
RefState {
target: Some(oid(c)),
peeled: None,
symref_target: None,
push_seq: 0,
updated_ms: 0,
},
);
}
let store = ArchiveRefStore::from_folded(folded).unwrap();
assert!(
store.read(&name("refs/heads/doomed")).unwrap().is_some(),
"the index cannot see a resurrected ref, so the deletion test proves nothing"
);
assert_eq!(
store.iter(None).unwrap().len(),
2,
"the scan cannot see a resurrected ref, so the deletion test proves nothing"
);
}
/// An empty namespace has no tree, and must answer rather than panic —
/// `STree32::new` asserts on an empty slice.
#[test]
fn an_empty_namespace_answers_without_a_tree() {
let store = ArchiveRefStore::from_folded(BTreeMap::new()).unwrap();
assert!(store.is_empty());
assert_eq!(store.read(&name("refs/heads/main")).unwrap(), None);
assert_eq!(store.iter(None).unwrap().len(), 0);
assert_eq!(store.head().unwrap(), None);
assert_eq!(store.index_bytes(), 0);
}
/// Every name in a realistic namespace resolves to its own target, and a
/// near-miss neighbour does not. Sized past one `STree32` node (B=16) and
/// past one level, so the tree actually has to route.
#[test]
fn every_name_resolves_to_its_own_target_at_depth() {
let dir = tmpdir("depth");
let log = RefLog::new(dir.join("refs.log"));
let updates: Vec<RefUpdate> = (0..1000)
.map(|i| RefUpdate::set(format!("refs/heads/b{i:04}"), oid_n(i)))
.collect();
log.push(&updates).unwrap();
let store = store_of(&log);
assert_eq!(store.len(), 1000);
for i in 0..1000 {
let n = name(&format!("refs/heads/b{i:04}"));
assert_eq!(
store.read(&n).unwrap(),
Some(Target::Object(oid_n(i).parse().unwrap())),
"b{i:04} resolved to the wrong target"
);
}
// Absent names that are lexicographic neighbours of present ones.
for n in [
"refs/heads/b0000x",
"refs/heads/b999",
"refs/heads/a0000",
"refs/heads/c0000",
] {
assert_eq!(store.read(&name(n)).unwrap(), None, "{n} matched something");
}
assert_eq!(store.probes(), 1004, "some lookup bypassed the tree");
}
fn oid_n(i: usize) -> String {
format!("{i:040x}")
}
}