znippy_plugin_git/

resolve.rs

//! Pack entries → **oids**, which is the one thing [`crate::pack_walk`] cannot
//! tell you and the `objects` table is keyed by.
//!
//! This is the **indexer's** work, not the ack path's (§13.9: "the index is built
//! after the ack, over a channel"). It inflates every entry, applies every delta
//! chain and hashes the result, which is what `git index-pack` does and what
//! makes it the expensive half of a push. Nothing here is called before a client
//! is told its push landed.
//!
//! # What it keeps and what it throws away
//!
//! Peak memory is deliberately not "the whole history inflated". **An object is
//! held only while an unresolved entry still has to read it**, and for nothing
//! else:
//!
//! | object | held | until |
//! |---|---|---|
//! | a delta base | yes | its **last** dependent has consumed it |
//! | everything else — blob, commit, tree, tag | **no** | it leaves through the [`PayloadSink`] and is dropped |
//!
//! The base set and, more to the point, **how many entries read each base** are
//! known before a byte is inflated: the walk already collected every delta base,
//! so the resolver starts with an exact reference count per base and drops a
//! payload the moment that count reaches zero. The last dependent gets the base
//! **moved** into it rather than cloned, so a linear delta chain — one base, one
//! dependent, the ordinary shape of real history — copies no payload at all.
//!
//! ## What this table said before 2026-08-11, and what it cost
//!
//! It said commits, trees and tags were kept "because the `graph` and `reach`
//! tables are built from them". They are not, and had not been since §14's
//! exploded table became the fold's input — `absorb_one` reads
//! `Resolved::index_entry()` and nothing else. Two copies of the object set were
//! being held for a reader that no longer existed:
//!
//! * `content` kept every base **and** every typed object for the whole call.
//!   Nothing ever removed a row, so "held only while something still needs them"
//!   described an intention, not the code.
//! * `Resolved::payload` kept a second copy of the same bytes, cloned in.
//!
//! MEASURED on oden 2026-08-11, `tests/resolve_peak_memory.rs`, peak **live**
//! heap over `resolve_walked` against the pack's own inflated payload:
//!
//! | pack | before | after |
//! |---|---:|---:|
//! | forge-year-8a-240b-12c, 28 893 objects, 111.0 MB | 2.03x | **0.03x** |
//! | stage-red-nobitmap, 12 328 objects, 343.5 MB | 1.34x (461.2 MB) | **0.02x** (5.9 MB) |
//! | facett, 7 232 objects, 72.8 MB | 1.20x | **0.42x** |
//! | znippy's own, 5 388 objects, 84.4 MB | 0.75x | **0.14x** |
//!
//! The worst pack in the corpus went 2.03x → 0.42x. It is `facett`, whose
//! delta chains fan out widely enough that a real base working set is genuinely
//! live at once — which is the bound behaving as intended rather than a residue.
//!
//! End to end, one `gunnar-server`, one `push --mirror`, anonymous RSS held
//! afterwards (not peak — this memory was never given back):
//!
//! | fixture | before | after |
//! |---|---:|---:|
//! | 36 172 objects, 290 MB inflated, 5.9 MB pack | 575.7 MB | **185.1 MB** |
//! | 352 396 objects, 2.89 GB inflated, 61.8 MB pack | 4480.1 MB | **439.9 MB** |
//!
//! The second row is the one that mattered: 10x the repository cost 10x the
//! memory before and 2.4x after, so the resolver's footprint stopped tracking
//! the history. What is left is bounded and named — redb's page cache
//! (`ZNIPPY_GIT_REDB_CACHE_BYTES`, 64 MiB by default, measured at 129.3 MB held
//! with an 8 MiB ceiling and 303.9 MB with 256 MiB), the exploded table's
//! [`FLUSH_BYTES`](crate::exploded::FLUSH_BYTES) write buffer, and
//! `Derived`'s in-memory graph, which is genuinely O(repository).
//!
//! # ⚠ The clone that got slower, and why it is not this code
//!
//! **Read this before "fixing" the reference counting.** `vs_forge_clone` on the
//! 352 396-object fixture reported this change as a **+78 % CPU regression on
//! every znippy arm**, and the natural reading — a base dropped at its "last
//! use" has to be re-resolved when something later wants it again — is wrong. It
//! is not even mechanically possible: an undercount cannot cause a re-resolve
//! here, because there is no re-resolve to fall into. `resolve_walked` fails the
//! whole pack by name.
//!
//! What it actually is, MEASURED on oden 2026-08-11, one gunnar-server, seed the
//! fixture then clone it, steady state (clones 2-3), quiet box, only the
//! allocator and this file varying:
//!
//! | resolver | allocator | clone CPU | anon after seed |
//! |---|---|---:|---:|
//! | before | glibc | 1.47 s | 4481 MB |
//! | **after** | glibc | **2.62 s** | **438 MB** |
//! | before | mimalloc | 1.18 s | 1767 MB |
//! | **after** | **mimalloc** | **1.17 s** | **701 MB** |
//!
//! With a competent allocator the two resolvers are **identical** (1.18 against
//! 1.17). The regression is entirely glibc `malloc`: the old resolver's retained
//! 4.5 GB was accidentally acting as a **pre-warmed pool**, so the clone's own
//! ~2 GB of allocations came off a free list instead of out of the kernel. Take
//! the leak away and glibc charges for the memory it should have been charging
//! for all along.
//!
//! Three independent measurements say the same thing, and none of them involve
//! this file being slower:
//!
//! 1. **Bisect.** A build with *only* `Resolved::payload` removed — the
//!    reference counting NOT applied, `content` still never pruned — reproduces
//!    the whole regression (2.56–2.62 s). Adding the reference counting on top
//!    then costs **nothing** (2.55–2.65 s) and takes anon-after-seed from
//!    2350 MB to 438 MB. The counting is free; the *not leaking* is what glibc
//!    punishes.
//! 2. **Restart.** Restart the server after seeding, so the derived tables are
//!    folded onto a fresh heap: before 2.20–2.22 s, after 2.20–2.24 s —
//!    identical to within 1 %. The old resolver's 1.47 s is the outlier, not the
//!    new one's 2.62 s.
//! 3. **The resolver itself.** Over the same 6 real packs both revisions accept,
//!    1.058 s before against 0.975 s after: this code is ~8 % *faster*.
//!
//! So there is no cheaper trade to find inside this module, and an LRU over
//! bases would buy nothing. The lever, if the CPU is wanted back, is the
//! allocator — and `LD_PRELOAD=libmimalloc.so.3` is enough to get it with no
//! code change at all.
//!
//! # Where the payloads it throws away now go
//!
//! §14's exploded table is **eager** (decided 2026-08-08), so every object this
//! module resolves has to reach [`crate::exploded::ExplodedTable`] — including
//! the blobs the table above says are dropped. They still are: the payload
//! leaves through a [`PayloadSink`] as it is produced, rather than being
//! accumulated into the returned `Vec`. That is the difference between a peak
//! footprint of "the bases plus the typed objects" and one of "the whole pack
//! inflated at once", and eager resolution does not get to change it.
//!
//! A **thin** pack's `REF_DELTA` base is an object the client knows the server
//! already has, and it is usually a blob. Resolving it needs that blob's
//! *content*, which is exactly what the exploded table now holds — so the
//! [`BaseSource`] can answer from it in one point lookup instead of re-resolving
//! a whole pack. A thin pack whose external base is **still** not re-derivable
//! is refused by name ([`ResolveError::MissingBase`]) rather than resolved by
//! guesswork, unchanged.

use std::collections::HashMap;

use anyhow::{Result, anyhow, bail};

use crate::exploded::{NoSink, PayloadSink};
use crate::index_layout::{IndexEntry, ObjType};
use crate::object::{GitHashKind, GitObjectKind, canonical};
use crate::pack_walk::{DeltaBase, PackEntry, PackWalk, walk};

/// Where an entry that deltas against something outside the pack gets its base.
///
/// Implemented by the store, which may or may not be able to answer — see the
/// module docs on §14.
pub trait BaseSource {
    /// The object's type and inflated payload, or `None` if this source cannot
    /// produce it.
    fn content(&self, oid: &[u8]) -> Option<(GitObjectKind, Vec<u8>)>;
}

/// A source that has nothing. The right one for a self-contained pack, and it
/// makes "this pack was thin" an error rather than a silent success.
pub struct NoBases;

impl BaseSource for NoBases {
    fn content(&self, _oid: &[u8]) -> Option<(GitObjectKind, Vec<u8>)> {
        None
    }
}

/// One resolved object: **exactly what the `objects` table stores**, and no
/// payload.
///
/// It carried an `Option<Vec<u8>>` payload until 2026-08-11, for a reader that
/// stopped existing when §14's exploded table became the fold's input. Every
/// production caller uses [`index_entry`](Self::index_entry) and nothing else —
/// `absorb_one` builds index rows, and the one other caller discards the vector
/// entirely and reads its sink. Content has one home now
/// ([`PayloadSink`], LAW 5) and this struct is the row, so a 343 MB pack's rows
/// cost the length of the pack's entry list rather than the length of its
/// history.
#[derive(Debug, Clone)]
pub struct Resolved {
    pub oid: Vec<u8>,
    /// Byte extent of the **stored, verbatim** entry.
    pub offset: u64,
    pub len: u64,
    /// The type the entry carries in the pack — which for a delta is
    /// `OfsDelta` / `RefDelta`, exactly as `.idx` cannot tell you and this index
    /// exists to record.
    pub stored_type: ObjType,
    /// The type the chain resolves to. Always one of the four real git types.
    pub kind: GitObjectKind,
    /// Inflated, **post-delta-resolution** size — the fact `.idx` and `.rev`
    /// together still cannot answer.
    pub uncompressed_size: u64,
    /// The `objects.delta_base` column: an archive **offset**, `0` for none.
    pub delta_base: u64,
}

impl Resolved {
    /// The row [`crate::read_stack::ObjectReadStack::append`] takes.
    ///
    /// `delta_base` now has a column of its own in [`IndexEntry`] and rides
    /// across in it — it was carried on this struct alone until that column
    /// existed, and was deliberately never smuggled into `uncompressed_size` or
    /// any other field on the way. **This is the only place it is written into
    /// an index row** (LAW 5): [`resolve_walked`] computes it once, in the
    /// archive's coordinate space, and nothing downstream recomputes it from the
    /// walk.
    pub fn index_entry(&self) -> IndexEntry {
        IndexEntry {
            oid: self.oid.clone(),
            offset: self.offset,
            len: self.len,
            obj_type: self.stored_type,
            uncompressed_size: self.uncompressed_size,
            delta_base: self.delta_base,
        }
    }
}

/// The one failure that is a *decision* rather than a corrupt pack.
#[derive(Debug)]
pub struct ResolveError;

impl ResolveError {
    /// A thin pack's external base, named.
    pub fn missing_base(oid: &[u8]) -> anyhow::Error {
        anyhow!(
            "this pack is thin: it deltas against {} which is not in it, and no base source could \
             produce that object's content — §14's exploded table does not hold it and it could \
             not be re-derived from the verbatim packs either, so this repository genuinely does \
             not have that object. The pack is refused by name rather than half-resolved",
            hex::encode(oid)
        )
    }
}

/// Resolve every entry of `pack` to an oid, **keeping no payloads**.
///
/// `archive_offset` is where the pack's first byte lives in the archive, so the
/// offsets and `delta_base`s that come back are already in the archive's
/// coordinate space and no caller has to remember to shift them.
///
/// The indexer does **not** come through here — it calls
/// [`resolve_walked`] with the exploded table as its sink, which is what makes
/// §14's side table fall out of the same pass rather than out of a second walk.
pub fn resolve(
    pack: &[u8],
    hash: GitHashKind,
    archive_offset: u64,
    bases: &dyn BaseSource,
) -> Result<Vec<Resolved>> {
    let w = walk(pack, hash.oid_len())?;
    resolve_walked(pack, &w, hash, archive_offset, bases, &NoSink)
}

/// Same, for a caller that already walked the pack (`put` does, for the closure
/// check) and must not walk it twice — and for the one that wants the payloads.
///
/// `sink` is handed **every** object exactly once, in resolution order, with the
/// payload its chain resolves to. Pass [`NoSink`] to keep nothing. This is the
/// one pass §14's exploded table is built from: no second walk, no second
/// inflate, no second resolver (LAW 5).
pub fn resolve_walked(
    pack: &[u8],
    w: &PackWalk,
    hash: GitHashKind,
    archive_offset: u64,
    bases: &dyn BaseSource,
    sink: &dyn PayloadSink,
) -> Result<Vec<Resolved>> {
    // **How many entries have to read each base**, known before a byte is
    // inflated. A count and not a set: the set says "keep this", the count says
    // "keep this until exactly here", and only the second one lets a payload be
    // dropped mid-pass. An entry is resolved at most once (the fixpoint removes
    // it from `remaining` the round it succeeds), so one dependent is one
    // decrement and the count is exact rather than conservative.
    let mut ofs_uses: HashMap<u64, usize> = HashMap::new();
    let mut ref_uses: HashMap<&[u8], usize> = HashMap::new();
    for e in &w.entries {
        match &e.delta_base {
            DeltaBase::Offset(o) => *ofs_uses.entry(*o).or_default() += 1,
            DeltaBase::Ref(oid) => *ref_uses.entry(oid.as_slice()).or_default() += 1,
            DeltaBase::None => {}
        }
    }

    let mut out: Vec<Option<Resolved>> = vec![None; w.entries.len()];
    // Payloads held only while something still needs them — and now that is
    // true of the code and not only of this comment. The `usize` is the number
    // of dependents that have yet to consume the row; at zero the row goes.
    let mut content: HashMap<u64, (GitObjectKind, Vec<u8>, usize)> = HashMap::new();
    // Only for the payloads a `REF_DELTA` in this pack actually names. An oid
    // nothing ref-deltas against is never looked up here, so recording it would
    // be 20 bytes and a hash per object of the repository for no reader.
    let mut oid_to_offset: HashMap<Vec<u8>, u64> = HashMap::new();

    // A fixpoint rather than one pass: a `REF_DELTA` may name a base that is in
    // this pack but *later* in it, and that is legal. Every round resolves at
    // least one entry or the pack cannot be resolved at all, so this terminates
    // in at most `entries` rounds.
    let mut remaining: Vec<usize> = (0..w.entries.len()).collect();
    while !remaining.is_empty() {
        let mut progressed = false;
        let mut stuck: Vec<usize> = Vec::new();
        for &i in &remaining {
            let e = &w.entries[i];
            let base: Option<(GitObjectKind, Vec<u8>)> = match &e.delta_base {
                DeltaBase::None => None,
                DeltaBase::Offset(o) => match consume(&mut content, *o) {
                    Some(c) => Some(c),
                    None => {
                        // Not yet resolved. It cannot be resolved-and-dropped:
                        // this entry's own use is part of the base's count, so
                        // the count cannot have reached zero before this line.
                        stuck.push(i);
                        continue;
                    }
                },
                DeltaBase::Ref(oid) => match oid_to_offset
                    .get(oid.as_slice())
                    .copied()
                    .and_then(|o| consume(&mut content, o))
                {
                    Some(c) => Some(c),
                    None => match bases.content(oid) {
                        Some(c) => Some(c),
                        None => {
                            stuck.push(i);
                            continue;
                        }
                    },
                },
            };

            let (kind, payload) = match base {
                None => {
                    let kind = whole_kind(e.obj_type)?;
                    (kind, inflate(pack, e, hash.oid_len())?)
                }
                Some((base_kind, base_payload)) => {
                    let delta = inflate(pack, e, hash.oid_len())?;
                    (base_kind, apply_delta(&base_payload, &delta)?)
                }
            };

            let oid = hash.oid_of(&canonical(kind, &payload));
            // **Every object, before anything is dropped.** §14's exploded table
            // is eager, so the sink sees the blob whose payload the next lines
            // are about to throw away as well as the ones they keep.
            sink.explode(&oid, kind, &payload)?;
            let size = payload.len() as u64;

            // Held only if something still has to read it, and then only for as
            // many reads as the walk counted. `ref_uses` is consulted by oid
            // because that is how a `REF_DELTA` names its base; the two counts
            // add, because one object can be both kinds of base.
            let by_ref = ref_uses.get(oid.as_slice()).copied().unwrap_or(0);
            let uses = ofs_uses.get(&e.offset).copied().unwrap_or(0) + by_ref;
            if uses > 0 {
                if by_ref > 0 {
                    oid_to_offset.insert(oid.clone(), e.offset);
                }
                content.insert(e.offset, (kind, payload, uses));
            }
            // `payload` is gone by here unless a dependent needs it. Nothing
            // below reads it: the row is the index entry.

            out[i] = Some(Resolved {
                oid,
                offset: e.offset + archive_offset,
                len: e.len,
                stored_type: e.obj_type,
                kind,
                uncompressed_size: size,
                delta_base: match &e.delta_base {
                    DeltaBase::Offset(o) => o + archive_offset,
                    _ => 0,
                },
            });
            progressed = true;
        }
        if !progressed {
            // Nothing moved: every remaining entry waits on a base nobody can
            // supply. Name the first one — a thin pack is the ordinary reason.
            let i = stuck[0];
            if let DeltaBase::Ref(oid) = &w.entries[i].delta_base {
                return Err(ResolveError::missing_base(oid));
            }
            bail!(
                "entry at offset {} deltas against offset {} which no entry starts at — the pack \
                 is corrupt",
                w.entries[i].offset,
                w.entries[i].delta_base.as_offset()
            );
        }
        remaining = stuck;
    }

    // `content` is empty here for any pack whose bases were all resolved from
    // inside it. What can survive is the one case the fixpoint cannot count: a
    // `REF_DELTA` whose in-pack base had not been reached yet, which
    // `bases.content` answered from the store instead — that dependent's use is
    // then never decremented off the in-pack copy. Bounded by the number of
    // ref-deltas, and it goes out of scope on the next line.
    Ok(out
        .into_iter()
        .map(|r| r.expect("the fixpoint only exits when every slot is filled"))
        .collect())
}

/// Take one use off a held base, **moving** the payload out on the last one.
///
/// The move is the point. A base with a single dependent — a linear delta
/// chain, which is what real history is mostly made of — is handed straight to
/// `apply_delta` with no copy at all, where the previous code cloned every base
/// on every application. Only a base with more dependents still to come is
/// cloned, and only for the ones that are not last.
fn consume(
    content: &mut HashMap<u64, (GitObjectKind, Vec<u8>, usize)>,
    at: u64,
) -> Option<(GitObjectKind, Vec<u8>)> {
    let (kind, payload, left) = content.get_mut(&at)?;
    *left -= 1;
    if *left > 0 {
        return Some((*kind, payload.clone()));
    }
    let (kind, payload, _) = content.remove(&at).expect("just borrowed it");
    Some((kind, payload))
}

/// The real git type of a non-delta entry.
fn whole_kind(t: ObjType) -> Result<GitObjectKind> {
    Ok(match t {
        ObjType::Commit => GitObjectKind::Commit,
        ObjType::Tree => GitObjectKind::Tree,
        ObjType::Blob => GitObjectKind::Blob,
        ObjType::Tag => GitObjectKind::Tag,
        ObjType::OfsDelta | ObjType::RefDelta => {
            bail!("a delta entry has no type of its own — its base's type is the answer")
        }
    })
}

/// Inflate one entry's stream. The walk already proved the length, so this
/// allocates exactly the declared size and never grows.
fn inflate(pack: &[u8], e: &PackEntry, oid_len: usize) -> Result<Vec<u8>> {
    let start = e.offset as usize;
    let end = start + e.len as usize;
    if end > pack.len() {
        bail!("entry at {start} runs past the end of the pack");
    }
    // Skip the header the walk already parsed: the zlib stream is what is left
    // after the type/size varint and any base reference.
    let header = header_len(&pack[start..end], e, oid_len)?;
    let mut out = Vec::with_capacity(e.uncompressed_size as usize);
    let mut d = flate2::Decompress::new(true);
    d.decompress_vec(
        &pack[start + header..end],
        &mut out,
        flate2::FlushDecompress::Finish,
    )
    .map_err(|err| anyhow!("inflating the entry at {start}: {err}"))?;
    if out.len() as u64 != e.uncompressed_size {
        bail!(
            "the entry at {start} inflated to {} bytes, the walk measured {}",
            out.len(),
            e.uncompressed_size
        );
    }
    Ok(out)
}

/// How many bytes of an entry are header rather than zlib stream. Recomputed
/// from the bytes rather than remembered, so it cannot drift from the walk's own
/// reading of them — and the walk's `len` is what bounds it.
fn header_len(entry: &[u8], e: &PackEntry, oid_len: usize) -> Result<usize> {
    let mut i = 0usize;
    let mut cont = true;
    while cont {
        let b = *entry
            .get(i)
            .ok_or_else(|| anyhow!("the type/size header runs off the entry"))?;
        cont = b & 0x80 != 0;
        i += 1;
    }
    match e.obj_type {
        ObjType::OfsDelta => {
            let mut cont = true;
            while cont {
                let b = *entry
                    .get(i)
                    .ok_or_else(|| anyhow!("the ofs-delta distance runs off the entry"))?;
                cont = b & 0x80 != 0;
                i += 1;
            }
        }
        ObjType::RefDelta => i += oid_len,
        _ => {}
    }
    if i >= entry.len() {
        bail!("the entry's header consumes all of it, leaving no stream");
    }
    Ok(i)
}

/// git's delta format: two sizes, then copy-from-base and insert-literal
/// instructions.
fn apply_delta(base: &[u8], delta: &[u8]) -> Result<Vec<u8>> {
    let mut i = 0usize;
    let base_size = delta_varint(delta, &mut i)?;
    if base_size != base.len() as u64 {
        bail!(
            "the delta expects a base of {base_size} bytes, its base is {}",
            base.len()
        );
    }
    let target_size = delta_varint(delta, &mut i)?;
    let mut out = Vec::with_capacity(target_size as usize);

    while i < delta.len() {
        let op = delta[i];
        i += 1;
        if op & 0x80 != 0 {
            // Copy from the base. Offset in up to 4 bytes, size in up to 3;
            // a zero size means 0x10000, which is git's own special case.
            let mut off = 0u64;
            for bit in 0..4 {
                if op & (1 << bit) != 0 {
                    off |= u64::from(*delta.get(i).ok_or_else(|| anyhow!("delta ends mid-copy"))?)
                        << (bit * 8);
                    i += 1;
                }
            }
            let mut size = 0u64;
            for bit in 0..3 {
                if op & (0x10 << bit) != 0 {
                    size |= u64::from(*delta.get(i).ok_or_else(|| anyhow!("delta ends mid-copy"))?)
                        << (bit * 8);
                    i += 1;
                }
            }
            if size == 0 {
                size = 0x1_0000;
            }
            let from = off as usize;
            let to = from
                .checked_add(size as usize)
                .ok_or_else(|| anyhow!("a delta copy range overflows"))?;
            if to > base.len() {
                bail!(
                    "a delta copies base[{from}..{to}] out of a {}-byte base",
                    base.len()
                );
            }
            out.extend_from_slice(&base[from..to]);
        } else {
            // Insert literal. A zero-length insert is not a valid instruction.
            let n = op as usize;
            if n == 0 {
                bail!("a delta carries a zero-length insert instruction");
            }
            let end = i
                .checked_add(n)
                .ok_or_else(|| anyhow!("a delta insert overflows"))?;
            if end > delta.len() {
                bail!("a delta insert of {n} bytes runs off the end");
            }
            out.extend_from_slice(&delta[i..end]);
            i = end;
        }
    }

    if out.len() as u64 != target_size {
        bail!(
            "the delta declares a {target_size}-byte result and produced {}",
            out.len()
        );
    }
    Ok(out)
}

/// The delta header's little-endian 7-bit varint. Not the pack entry's varint.
fn delta_varint(b: &[u8], i: &mut usize) -> Result<u64> {
    let mut v = 0u64;
    let mut shift = 0u32;
    loop {
        let byte = *b
            .get(*i)
            .ok_or_else(|| anyhow!("a delta size varint runs off the end"))?;
        *i += 1;
        if shift >= 64 {
            bail!("a delta size varint is longer than a u64");
        }
        v |= u64::from(byte & 0x7f) << shift;
        shift += 7;
        if byte & 0x80 == 0 {
            return Ok(v);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::path::{Path, PathBuf};

    /// Parse a real `.idx` (v2) into `(oid, pack offset)` pairs. Twenty lines of
    /// a frozen format, and it is git's own answer to the question this module
    /// computes — which is what makes it a differential guard and not a
    /// restatement of our own code.
    fn read_idx(bytes: &[u8]) -> Vec<(Vec<u8>, u64)> {
        assert_eq!(&bytes[0..4], b"\xfftOc", "not an idx v2");
        assert_eq!(u32::from_be_bytes(bytes[4..8].try_into().unwrap()), 2);
        let fanout_end = 8 + 256 * 4;
        let n = u32::from_be_bytes(bytes[fanout_end - 4..fanout_end].try_into().unwrap()) as usize;
        let oids = fanout_end;
        let crcs = oids + n * 20;
        let offs = crcs + n * 4;
        let big = offs + n * 4;
        let mut out = Vec::with_capacity(n);
        for i in 0..n {
            let oid = bytes[oids + i * 20..oids + i * 20 + 20].to_vec();
            let raw = u32::from_be_bytes(bytes[offs + i * 4..offs + i * 4 + 4].try_into().unwrap());
            let offset = if raw & 0x8000_0000 != 0 {
                let j = (raw & 0x7fff_ffff) as usize;
                u64::from_be_bytes(bytes[big + j * 8..big + j * 8 + 8].try_into().unwrap())
            } else {
                u64::from(raw)
            };
            out.push((oid, offset));
        }
        out
    }

    /// Real packs with their real indexes, from this machine's repositories.
    fn real_pairs(cap: usize) -> Vec<(PathBuf, PathBuf)> {
        let mut out = Vec::new();
        let Ok(repos) = std::fs::read_dir(Path::new("/home/rickard/git")) else {
            return out;
        };
        for repo in repos.flatten() {
            let dir = repo.path().join(".git/objects/pack");
            let Ok(files) = std::fs::read_dir(&dir) else {
                continue;
            };
            for f in files.flatten() {
                let p = f.path();
                if p.extension().is_some_and(|e| e == "pack")
                    && f.metadata().map(|m| m.len() < 32 << 20).unwrap_or(false)
                {
                    let idx = p.with_extension("idx");
                    if idx.exists() {
                        out.push((p, idx));
                        if out.len() >= cap {
                            return out;
                        }
                    }
                }
            }
        }
        out
    }

    /// **git's own `.idx` is the arbiter.** For every real pack on this machine,
    /// every oid we compute and the offset we computed it at must appear in
    /// git's index, and the two sets must have the same size. A delta applier
    /// that is subtly wrong produces a different hash and cannot pass this.
    ///
    /// Seen RED by changing `size = 0x1_0000` to `size = 0x1_000` in
    /// [`apply_delta`] — git's zero-size copy special case:
    /// ".../facett/...pack-62582dd0…: the delta declares a 149392-byte result and
    /// produced 87952". A single wrong constant in the delta applier and a real
    /// repository's pack stops resolving.
    ///
    /// MEASURED while writing it: **10 899 objects over 3 packs** match git's own
    /// `.idx` oid for oid and offset for offset, and **3 of the 6 real packs on
    /// this machine are thin** — they delta against objects that are not in them,
    /// which is the §14 hole showing up in the wild rather than in theory.
    #[test]
    fn every_oid_we_compute_is_the_oid_git_wrote_in_its_idx() {
        let pairs = real_pairs(6);
        assert!(
            !pairs.is_empty(),
            "no real pack found under /home/rickard/git — this guard has nothing to compare and \
             must not pass silently"
        );
        let mut objects = 0usize;
        let mut full = 0usize;
        let mut thin = 0usize;
        for (pack_path, idx_path) in pairs {
            let pack = std::fs::read(&pack_path).unwrap();
            let idx = read_idx(&std::fs::read(&idx_path).unwrap());
            // MEASURED, and a surprise worth recording: real packs on this
            // machine DO delta against objects outside themselves. Such a pack
            // cannot be compared here — resolving it is exactly what §14 leaves
            // open — but it must not make the guard pass vacuously either, so it
            // is counted and named and at least one pack has to compare in full.
            let ours = match resolve(&pack, GitHashKind::Sha1, 0, &NoBases) {
                Ok(r) => r,
                Err(e) => {
                    assert!(
                        e.to_string().contains("thin"),
                        "{}: {e}",
                        pack_path.display()
                    );
                    eprintln!("{}: THIN, external base — skipped", pack_path.display());
                    thin += 1;
                    continue;
                }
            };
            full += 1;

            assert_eq!(
                ours.len(),
                idx.len(),
                "{}: we resolved {} objects, git indexed {}",
                pack_path.display(),
                ours.len(),
                idx.len()
            );
            let theirs: HashMap<Vec<u8>, u64> = idx.into_iter().collect();
            for r in &ours {
                match theirs.get(&r.oid) {
                    Some(&off) => assert_eq!(
                        off,
                        r.offset,
                        "{}: {} is at {} in git's idx and we put it at {}",
                        pack_path.display(),
                        hex::encode(&r.oid),
                        off,
                        r.offset
                    ),
                    None => panic!(
                        "{}: we computed {} at offset {}, which git's idx does not contain — the \
                         resolution is wrong",
                        pack_path.display(),
                        hex::encode(&r.oid),
                        r.offset
                    ),
                }
            }
            eprintln!("{}: {} objects agree with git", pack_path.display(), ours.len());
            objects += ours.len();
        }
        eprintln!("{objects} objects over {full} packs agree with git's own .idx; {thin} thin");
        assert!(full > 0, "every pack on this machine was thin — nothing was compared");
        assert!(objects > 1000, "only {objects} objects compared");
    }

    /// The three facts the objects table needs and `.idx` cannot supply: the
    /// **stored** type (delta or not), the **resolved** type, and the
    /// post-resolution size. Asserted against the pack's own delta structure, on
    /// a real pack, so it cannot be satisfied by a store-and-echo.
    ///
    /// Seen RED by resolving a delta to `GitObjectKind::Blob` instead of to its
    /// base's kind: "a delta resolves to its base's type:
    /// c6d50e761d025c179ffef1c3d68c56aae0a53270 vs base
    /// 8e15741296ebe3a0508522b76fe2ec4982396b6d — left: Blob, right: Commit".
    ///
    /// MEASURED on that pack: 4292 deltas, 2715 of them resolving to something
    /// other than a blob, and **all 4292** carrying a resolved size unlike their
    /// delta-stream size.
    #[test]
    fn a_delta_carries_its_stored_type_and_its_resolved_type_and_size() {
        let (pack_path, _) = real_pairs(1).pop().expect("a real pack");
        let pack = std::fs::read(&pack_path).unwrap();
        let ours = resolve(&pack, GitHashKind::Sha1, 0, &NoBases).unwrap();
        // One walk, reused. Walking per entry turns this guard into an O(n^2)
        // pass over a 7000-object pack and it stops finishing.
        let stream_size: HashMap<u64, u64> = walk(&pack, 20)
            .unwrap()
            .entries
            .iter()
            .map(|e| (e.offset, e.uncompressed_size))
            .collect();

        let deltas: Vec<&Resolved> = ours
            .iter()
            .filter(|r| matches!(r.stored_type, ObjType::OfsDelta | ObjType::RefDelta))
            .collect();
        assert!(
            !deltas.is_empty(),
            "{} carries no deltas, so it proves nothing about resolution",
            pack_path.display()
        );

        // A delta's resolved type is a real git type, never a delta code, and it
        // matches its base's.
        let by_offset: HashMap<u64, &Resolved> = ours.iter().map(|r| (r.offset, r)).collect();
        let mut non_blob = 0usize;
        for d in &deltas {
            assert!(
                matches!(
                    d.kind,
                    GitObjectKind::Blob
                        | GitObjectKind::Tree
                        | GitObjectKind::Commit
                        | GitObjectKind::Tag
                ),
                "a resolved type must be a real git type"
            );
            if d.kind != GitObjectKind::Blob {
                non_blob += 1;
            }
            if d.delta_base != 0 {
                let base = by_offset[&d.delta_base];
                assert_eq!(
                    d.kind,
                    base.kind,
                    "a delta resolves to its base's type: {} vs base {}",
                    hex::encode(&d.oid),
                    hex::encode(&base.oid)
                );
                // The delta_base column addresses BYTES, and those bytes are an
                // entry we also resolved. An ordinal could not be checked like
                // this at all.
                assert!(
                    base.offset < d.offset,
                    "an ofs-delta base is always earlier in the pack"
                );
            }
        }
        assert!(
            non_blob > 0,
            "{} deltas and not one resolved to a tree/commit/tag — the resolved type is not being \
             taken from the base",
            deltas.len()
        );

        // The post-resolution size is the payload's real length, not the delta
        // stream's. For a delta the two are almost never equal.
        let differing = deltas
            .iter()
            .filter(|d| stream_size[&d.offset] != d.uncompressed_size)
            .count();
        assert!(
            differing > 0,
            "not one delta's resolved size differs from its delta-stream size, which cannot be \
             true of a real pack — the resolved size is being copied from the header"
        );
        eprintln!(
            "{}: {} deltas, {non_blob} non-blob, {differing} with a resolved size unlike the \
             stream size",
            pack_path.display(),
            deltas.len()
        );
    }

    /// A thin pack is refused **by name**, and the refusal says what decision is
    /// missing. It is not resolved to a wrong oid and it is not silently dropped.
    ///
    /// Seen RED by making the no-progress arm `bail!("stuck")` instead of
    /// `ResolveError::missing_base`: "names the base: stuck".
    #[test]
    fn a_thin_pack_is_refused_by_name_and_says_what_is_missing() {
        // One ref-delta against an oid nothing can supply.
        let base_oid = vec![0x5a; 20];
        let mut pack = b"PACK".to_vec();
        pack.extend_from_slice(&2u32.to_be_bytes());
        pack.extend_from_slice(&1u32.to_be_bytes());
        // A delta whose base is 4 bytes and whose target is 4 bytes: copy all.
        let delta = vec![0x04, 0x04, 0x90, 0x04];
        pack.push(0x70 | (delta.len() as u8 & 0x0f)); // type 7, size 4
        pack.extend_from_slice(&base_oid);
        pack.extend_from_slice(&{
            use std::io::Write;
            let mut e = flate2::write::ZlibEncoder::new(Vec::new(), flate2::Compression::default());
            e.write_all(&delta).unwrap();
            e.finish().unwrap()
        });
        pack.extend_from_slice(&[0u8; 20]);

        let err = resolve(&pack, GitHashKind::Sha1, 0, &NoBases)
            .expect_err("a thin pack with no base source cannot resolve");
        let msg = err.to_string();
        assert!(msg.contains(&hex::encode(&base_oid)), "names the base: {msg}");
        assert!(msg.contains("§14"), "says which decision is missing: {msg}");

        // With a source that CAN supply it, the same pack resolves — so the
        // refusal is about the missing content, not about ref-deltas.
        struct One(Vec<u8>);
        impl BaseSource for One {
            fn content(&self, oid: &[u8]) -> Option<(GitObjectKind, Vec<u8>)> {
                (oid == self.0.as_slice()).then(|| (GitObjectKind::Blob, b"abcd".to_vec()))
            }
        }
        let ok = resolve(&pack, GitHashKind::Sha1, 0, &One(base_oid)).expect("with a base it works");
        assert_eq!(ok.len(), 1);
        assert_eq!(ok[0].kind, GitObjectKind::Blob);
        assert_eq!(ok[0].uncompressed_size, 4);
        assert_eq!(
            ok[0].oid,
            GitHashKind::Sha1.oid_of(&canonical(GitObjectKind::Blob, b"abcd")),
            "the resolved object is the base copied whole, so it hashes as `abcd`"
        );
    }

    /// **The `delta_base` column, materialised — from a real pack, through all
    /// three index layouts and the read stack, and back out again.**
    ///
    /// This is the guard the column was added for. It asserts *applied output*:
    /// resolve a real pack, build every arm over the rows, and for every
    /// `OFS_DELTA` read the base offset **back out of the index** and require it
    /// to land on an object the same index holds — earlier in the archive, and
    /// with a byte extent that contains it. An ordinal in that column could not
    /// satisfy this at all, which is §13's decision checked rather than quoted.
    ///
    /// The three arms are compared row for row, because that is what caught a
    /// swapped `len`/`size` write in the previous sweep while two of the three
    /// stayed green.
    ///
    /// Seen RED three times, each for a different way the column can be wrong
    /// while every other fact stays right:
    ///
    /// 1. **Never written.** `Resolved::index_entry` returning `delta_base: 0`:
    ///    "FourTables: b76687fbb34020672608bcb1a5e027c2d8b0346a is an ofs-delta
    ///    with no recorded base".
    /// 2. **Written from the wrong field.** `delta_base: self.offset` — a
    ///    plausible archive offset that is non-zero, inside the pack, and lands
    ///    on a real entry boundary, so only the identity check catches it:
    ///    "FourTables: b76687fb… records base 91272 which is its own offset,
    ///    not its base's".
    /// 3. **Written in the wrong coordinate space.** `resolve_walked` yielding
    ///    `*o` instead of `o + archive_offset`, i.e. pack-relative rather than
    ///    archive-relative — the bug that an *ordinal* column would have had no
    ///    way to express and no way to detect: "FourTables: b76687fb… records
    ///    base offset 86534, which starts no object in this index". This is why
    ///    the fixture resolves at `AT = 4096` rather than at 0; at 0 the two
    ///    spaces coincide and the guard would be blind.
    ///
    /// All three restored.
    #[test]
    fn the_delta_base_column_survives_all_three_arms_from_a_real_pack() {
        use crate::index_layout::{
            FourTables, IndexEntry, ObjType, ObjectIndex, OneTableFourColumns, PackedPayload,
        };
        use crate::read_stack::{ObjectReadStack, RebuildTriggers};

        let (pack_path, _) = real_pairs(1).pop().expect("a real pack");
        let pack = std::fs::read(&pack_path).unwrap();
        // A non-zero archive offset on purpose: `delta_base` is in the archive's
        // coordinate space, so a resolver that forgot to rebase it would give
        // pack-relative values that no longer locate anything.
        const AT: u64 = 4096;
        let rows = resolve(&pack, GitHashKind::Sha1, AT, &NoBases).unwrap();
        let entries: Vec<IndexEntry> = rows.iter().map(|r| r.index_entry()).collect();

        let a = FourTables::build(&entries).unwrap();
        let b = OneTableFourColumns::build(&entries).unwrap();
        let c = PackedPayload::build(&entries).unwrap();
        let stack = ObjectReadStack::<OneTableFourColumns>::in_memory(RebuildTriggers::manual())
            .unwrap();
        stack.append(&entries).unwrap();
        stack.rebuild().unwrap();

        // Every extent this pack's objects occupy, read back out of the index.
        let extents: HashMap<u64, u64> = entries
            .iter()
            .map(|e| {
                let r = a.lookup(&e.oid).expect("a stored oid resolves");
                (r.offset, r.len)
            })
            .collect();
        assert_eq!(extents.len(), entries.len(), "two objects share an offset");

        let named: [(&str, &dyn ObjectIndex); 4] =
            [("FourTables", &a), ("OneTableFourColumns", &b), ("PackedPayload", &c), ("ObjectReadStack", &stack)];
        let mut ofs_deltas = 0usize;
        for (name, idx) in named {
            let mut with_base = 0usize;
            for e in &entries {
                let row = idx.lookup(&e.oid).expect("a stored oid resolves");
                // All four layouts, row for row, on every fact.
                assert_eq!(
                    row,
                    a.lookup(&e.oid).unwrap(),
                    "{name} disagrees with FourTables on {}",
                    hex::encode(&e.oid)
                );
                if row.obj_type != ObjType::OfsDelta {
                    continue;
                }
                with_base += 1;
                assert_ne!(
                    row.delta_base, 0,
                    "{name}: {} is an ofs-delta with no recorded base",
                    hex::encode(&e.oid)
                );
                assert_ne!(
                    row.delta_base,
                    row.offset,
                    "{name}: {} records base {} which is its own offset, not its base's",
                    hex::encode(&e.oid),
                    row.delta_base
                );
                assert!(
                    row.delta_base >= AT,
                    "{name}: base {} is below the archive offset {AT} — it was never rebased",
                    row.delta_base
                );
                // The whole claim: it addresses an entry this index holds.
                let base_len = extents.get(&row.delta_base).unwrap_or_else(|| {
                    panic!(
                        "{name}: {} records base offset {}, which starts no object in this index",
                        hex::encode(&e.oid),
                        row.delta_base
                    )
                });
                assert!(
                    row.delta_base + base_len <= row.offset,
                    "{name}: the base at {} (+{base_len}) overlaps the delta at {}",
                    row.delta_base,
                    row.offset
                );
            }
            assert!(
                with_base > 0,
                "{name}: {} ofs-deltas resolved and 0 of them carry a base offset — the column \
                 is not being written",
                entries
                    .iter()
                    .filter(|e| e.obj_type == ObjType::OfsDelta)
                    .count()
            );
            ofs_deltas = with_base;
        }
        assert!(
            ofs_deltas > 100,
            "{} carries only {ofs_deltas} ofs-deltas — too few to prove anything",
            pack_path.display()
        );
        eprintln!(
            "{}: {ofs_deltas} ofs-delta base offsets located their base entry in all four layouts",
            pack_path.display()
        );
    }

    /// **A base that several entries delta against survives until the last one
    /// has had it.**
    ///
    /// This replaces `a_blob_that_is_nobodys_base_is_hashed_and_dropped`, which
    /// read the retention policy off `Resolved::payload`. That field is gone
    /// (see the struct's docs), and the property it stood for — peak memory is
    /// the live base set, not the object set — is measured in bytes now by
    /// `tests/resolve_peak_memory.rs` rather than inferred from a flag.
    ///
    /// What is left here is the *risk* the reference counting introduced, and it
    /// is the one that matters: an off-by-one that frees a base while a
    /// dependent still needs it. That cannot be a silent wrong answer —
    /// `resolve_walked` fails the whole pack by name — so the assertion is that
    /// a pack full of shared bases resolves at all.
    ///
    /// **The test refuses to run on a pack that could not expose the bug.** A
    /// corpus of only single-dependent chains would pass this with the counting
    /// deleted entirely, which is the blind-guard shape LAW 2 is about, so the
    /// fan-out is asserted before the resolution is.
    ///
    /// Seen RED by `*left -= 1;` → `*left = 0;` in [`consume`] (drop every base
    /// on first use): "entry at offset 3141 deltas against offset 2724 which no
    /// entry starts at — the pack is corrupt", on the first pack tried.
    #[test]
    fn a_base_many_entries_share_outlives_all_of_them() {
        let mut checked = 0usize;
        let mut widest = 0usize;
        for (pack_path, _) in real_pairs(4) {
            let pack = std::fs::read(&pack_path).unwrap();
            let w = walk(&pack, 20).unwrap();

            // How many entries name each base. Anything above 1 is a base the
            // counting has to hold across more than one consumer.
            let mut uses: HashMap<u64, usize> = HashMap::new();
            for e in &w.entries {
                if let DeltaBase::Offset(o) = e.delta_base {
                    *uses.entry(o).or_default() += 1;
                }
            }
            let shared = uses.values().filter(|n| **n > 1).count();
            let fan_out = uses.values().copied().max().unwrap_or(0);
            if shared == 0 {
                continue;
            }
            widest = widest.max(fan_out);

            let rows = resolve(&pack, GitHashKind::Sha1, 0, &NoBases)
                .unwrap_or_else(|e| panic!("{}: {e}", pack_path.display()));
            assert_eq!(
                rows.len(),
                w.entries.len(),
                "{}: {} of {} entries resolved",
                pack_path.display(),
                rows.len(),
                w.entries.len()
            );
            eprintln!(
                "{}: {shared} bases shared by more than one entry, widest fan-out {fan_out}, all \
                 {} entries resolved",
                pack_path.display(),
                rows.len()
            );
            checked += 1;
        }
        assert!(
            checked > 0 && widest > 2,
            "no pack in the corpus had a base shared by more than two entries (checked \
             {checked}, widest {widest}) — this test cannot see an early free and must not \
             report a pass"
        );
    }
}