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.
//!
//! # The bounded base set (2026-08-30)
//!
//! The table above says a base is held until its last dependent. On
//! torvalds/linux that set is **unbounded in principle** — 11.2 M deltas over
//! 13.9 M objects, and nothing in the pack format promises a base's last
//! dependent is near it. On the 16 GB appliance the indexer grew past the box
//! and the kernel panicked (see [`crate::memguard`]). So the set now has a
//! **byte ceiling** ([`ResolveLimits::base_budget`], default 25 % of
//! `MemTotal`, `ZNIPPY_GIT_BASE_BUDGET_BYTES`):
//!
//! | event | what happens |
//! |---|---|
//! | a base would push the held bytes over the ceiling | the held base whose **next dependent is farthest** in the pack is dropped (Belady — the walk already lists every dependent's position, so "next use" is known, not guessed) |
//! | the new base itself is the farthest | it is not held at all |
//! | a dependent asks for a dropped base | it is **re-inflated from the mmapped pack** — its own chain re-applied — and counted in [`ResolveReport::reinflations`] |
//! | the watchdog says the box is short | **every** held base is dropped, the sink and the row batch are flushed, and the worker waits |
//!
//! Same output, hard ceiling. The ceiling is `max(budget, largest single
//! base)`: one object bigger than the budget is held while it is needed,
//! because the alternative is re-inflating it once per dependent.
//!
//! # What is preallocated
//!
//! Two scratch buffers live across the whole pass: the delta instruction
//! stream and the payload of an object nothing deltas against. An object that
//! is a base gets its own `Vec` because it outlives the iteration; every other
//! object — the overwhelming majority — is inflated into the reused buffer,
//! hashed in place ([`GitHashKind::oid_of_object`], no canonical copy) and
//! handed to the sink from there. Per object the hot path allocates the
//! 20-byte oid of its row and nothing else.

use std::collections::HashMap;
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};

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

use crate::exploded::{NoSink, PayloadSink};
use crate::forest::{DeltaForest, EntrySet};
use crate::index_layout::{IndexEntry, ObjType};
use crate::memguard::MemWatchdog;
use crate::object::{GitHashKind, GitObjectKind};
use crate::pack_walk::{DeltaBase, PackEntry, PackWalk, walk};
use crate::progress::{IndexProgress, Phase};

/// 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: Sync {
    /// The object's type and inflated payload.
    ///
    /// `Ok(None)` means **this source does not hold that object** — the only
    /// answer [`ResolveError::missing_base`] may be built from. `Err` means the
    /// source *does* hold it and could not read it, and that is a different
    /// fact with a different owner.
    ///
    /// # 🔴 It returned a bare `Option`, and the difference was thrown away
    ///
    /// `impl BaseSource for Absorber` ended in `.ok().flatten()`: a store that
    /// failed to reconstruct a base it holds answered exactly like a store that
    /// never had it, and the resolver then refused the *pushed pack* with *"this
    /// repository genuinely does not have that object"*. MEASURED on oden
    /// 2026-08-30 (lane AI): 21 of 140 ordinary pushes refused with that
    /// sentence about an object sitting in an absorbed pack one lookup away —
    /// see [`MAX_DELTA_LINKS`] for what was actually wrong and
    /// `crate::thin_storm` for the red. A client cannot act on a diagnosis that
    /// names the wrong party; neither can an operator.
    fn content(&self, oid: &[u8]) -> Result<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]) -> Result<Option<(GitObjectKind, Vec<u8>)>> {
        Ok(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)
        )
    }

    /// The worker was told to stop (the repository is being deleted).
    pub fn cancelled() -> anyhow::Error {
        anyhow!("index work cancelled: the repository is being deleted")
    }

    /// **This box cannot index this pack**, said out loud instead of waited out.
    ///
    /// The memory watchdog paused, dropped everything droppable, and still could
    /// not get back over its floor — either for
    /// [`MemWatchdog::pause_deadline`](crate::memguard::MemWatchdog::pause_deadline)
    /// or because the flush freed nothing three times running. Lane P2's rig
    /// took the other branch, which was to wait forever: 1 pause, 0 resumes,
    /// 1h45m41s, and a client that never got an ack. A refusal by name is a
    /// worse outcome for this one push and a far better one for the operator,
    /// who can now read the row and give the box more memory.
    pub fn out_of_memory(reason: &str, available: u64, budget: u64, done: u64, total: u64) -> anyhow::Error {
        anyhow!(
            "this box cannot index this pack: the memory watchdog gave up ({reason}) with {} \
             available against a {} floor, after {done} of {total} objects. Everything droppable \
             was dropped and the floor was still breached — what holds the memory is the \
             resolver's own per-object state, which is proportional to the pack. Give the box \
             more RAM, lower ZNIPPY_GIT_MEM_BUDGET_PCT, or push a smaller pack. The pack's bytes \
             are durable and untouched; nothing partial was indexed.",
            crate::memguard::fmt_bytes(available),
            crate::memguard::fmt_bytes(budget)
        )
    }
}

/// Default share of `MemTotal` the held base set may take.
pub const DEFAULT_BASE_BUDGET_PCT: u64 = 25;
/// Default rows per batch handed to the row sink.
pub const DEFAULT_ROW_BATCH: usize = 262_144;
/// **Ceiling on how far the workers may run ahead of the ordered stream**, in
/// bytes of rows and of the payloads the sink asked to be given. Past it a
/// worker waits for the emitter instead of buffering the pack — see
/// [`ResolveLimits::lookahead_bytes`].
pub const DEFAULT_LOOKAHEAD_BYTES: u64 = 32 << 20;
/// A ceiling on the worker count no environment variable may cross. A pack is
/// resolved by the box, not by a number somebody typed.
pub const MAX_WORKERS: usize = 256;

/// The knobs and hooks the indexer hands the resolver. [`ResolveLimits::none`]
/// is the old behaviour: unbounded bases, no watchdog, no progress.
#[derive(Clone)]
pub struct ResolveLimits<'a> {
    /// Ceiling on held delta-base bytes; `0` = unbounded.
    pub base_budget: u64,
    /// Rows per batch to the row sink.
    pub row_batch: usize,
    /// **How many subtrees are walked at once.** `1` is the serial resolver and
    /// the reference every other value is compared against; the output is the
    /// same stream at any value (see `the_same_pack_resolves_to_the_same_bytes_at_1_2_and_4_workers`).
    pub workers: usize,
    /// Bytes of resolved-but-not-yet-emitted objects the workers may hold. `0`
    /// takes [`DEFAULT_LOOKAHEAD_BYTES`].
    pub lookahead_bytes: u64,
    /// Objects between two checkpoints (cancel flag, watchdog).
    pub check_every: u64,
    pub watchdog: Option<Arc<MemWatchdog>>,
    pub cancel: Option<&'a AtomicBool>,
    pub progress: Option<&'a IndexProgress>,
    /// Names the repository in log lines.
    pub label: &'a str,
    /// Called once per watchdog pause and again every re-flush: the owner drops
    /// whatever it holds that can be rebuilt (the store's caches) and returns
    /// **how much it dropped**. Zero means the owner had nothing to give, which
    /// is the fact `index.spilled` reported 627 times and nobody acted on —
    /// see [`crate::memguard::PauseEnd::NothingToGive`].
    pub on_pause: Option<&'a (dyn Fn() -> u64 + Sync)>,
}

impl<'a> ResolveLimits<'a> {
    /// Unbounded, unwatched, unreported — what a test or a one-off resolve uses.
    pub fn none() -> Self {
        Self {
            base_budget: 0,
            row_batch: DEFAULT_ROW_BATCH,
            workers: 1,
            lookahead_bytes: DEFAULT_LOOKAHEAD_BYTES,
            check_every: crate::memguard::CHECK_EVERY_OBJECTS,
            watchdog: None,
            cancel: None,
            progress: None,
            label: "",
            on_pause: None,
        }
    }

    /// The indexer's: budget and batch from the environment (once per
    /// process), the process-wide watchdog, this store's cancel flag and
    /// progress counter.
    pub fn for_indexer(
        label: &'a str,
        cancel: &'a AtomicBool,
        progress: &'a IndexProgress,
        watchdog: Arc<MemWatchdog>,
        on_pause: &'a (dyn Fn() -> u64 + Sync),
    ) -> Self {
        Self {
            base_budget: base_budget_from_env(),
            row_batch: row_batch_from_env(),
            workers: workers_from_env(),
            lookahead_bytes: lookahead_from_env(),
            check_every: crate::memguard::CHECK_EVERY_OBJECTS,
            watchdog: Some(watchdog),
            cancel: Some(cancel),
            progress: Some(progress),
            label,
            on_pause: Some(on_pause),
        }
    }
}

/// `ZNIPPY_GIT_BASE_BUDGET_BYTES`, else 25 % of `MemTotal`, else 1 GiB when
/// the box cannot be measured. Read once per process.
pub fn base_budget_from_env() -> u64 {
    use std::sync::OnceLock;
    static B: OnceLock<u64> = OnceLock::new();
    *B.get_or_init(|| {
        if let Some(b) = crate::arms::read_env(crate::arms::ENV_BASE_BUDGET_BYTES)
            .and_then(|v| v.parse::<u64>().ok())
        {
            return b;
        }
        let total = crate::memguard::mem_total();
        if total == 0 { 1 << 30 } else { total / 100 * DEFAULT_BASE_BUDGET_PCT }
    })
}

/// `ZNIPPY_GIT_INDEX_BATCH_ROWS`, else [`DEFAULT_ROW_BATCH`]. Read once per process.
pub fn row_batch_from_env() -> usize {
    use std::sync::OnceLock;
    static B: OnceLock<usize> = OnceLock::new();
    *B.get_or_init(|| {
        crate::arms::read_env(crate::arms::ENV_INDEX_BATCH_ROWS)
            .and_then(|v| v.parse::<usize>().ok())
            .filter(|n| *n > 0)
            .unwrap_or(DEFAULT_ROW_BATCH)
    })
}

/// `ZNIPPY_GIT_RESOLVE_WORKERS`, else one per core. Read once per process.
///
/// **The forest is the parallelism** ([`crate::forest`]): a base and its
/// dependents are a tree, and two trees share nothing, so N workers is N
/// independent depth-first walks over one mmapped pack. It is not N copies of
/// the pack's O(pack) structures — the walk, the forest and the oid table are
/// read-only and shared — and it is not N base budgets either: the held-base
/// ceiling is one atomic across all of them (LAW 5).
pub fn workers_from_env() -> usize {
    use std::sync::OnceLock;
    static W: OnceLock<usize> = OnceLock::new();
    *W.get_or_init(|| {
        crate::arms::read_env(crate::arms::ENV_RESOLVE_WORKERS)
            .and_then(|v| v.parse::<usize>().ok())
            .filter(|n| *n > 0)
            .unwrap_or_else(|| {
                std::thread::available_parallelism().map(|x| x.get()).unwrap_or(1)
            })
            .clamp(1, MAX_WORKERS)
    })
}

/// `ZNIPPY_GIT_RESOLVE_LOOKAHEAD_BYTES`, else [`DEFAULT_LOOKAHEAD_BYTES`].
/// Read once per process.
pub fn lookahead_from_env() -> u64 {
    use std::sync::OnceLock;
    static L: OnceLock<u64> = OnceLock::new();
    *L.get_or_init(|| {
        crate::arms::read_env(crate::arms::ENV_RESOLVE_LOOKAHEAD_BYTES)
            .and_then(|v| v.parse::<u64>().ok())
            .filter(|n| *n > 0)
            .unwrap_or(DEFAULT_LOOKAHEAD_BYTES)
    })
}

/// What one resolve did — the audit line's numbers, all applied output.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct ResolveReport {
    pub rows: u64,
    /// Bases dropped for the ceiling and inflated again for a later dependent.
    pub reinflations: u64,
    /// Bases dropped for the ceiling (each may cost 0..n re-inflations).
    pub evictions: u64,
    /// Bases dropped because the watchdog said the box was short.
    pub watchdog_drops: u64,
    /// Most bytes of bases held at once.
    pub peak_base_bytes: u64,
    /// Watchdog pauses inside this pass.
    pub pauses: u64,
    pub paused_ms: u64,
    /// Row batches handed to the sink.
    pub batches: u64,
    /// Times a worker waited for the ordered stream instead of running further
    /// ahead of it. A positive number is the lookahead ceiling doing its job;
    /// a large one beside a poor speed-up is the ceiling being the bottleneck.
    pub stalls: u64,
    /// How many subtrees were walked at once. `1` is the serial resolver.
    pub workers: u32,
    /// Times a worker gave its core back because the box was short of memory
    /// rather than pausing the whole pack. See `Round::checkpoint`.
    pub shed: u64,
    /// The watchdog gave up rather than resumed — the pass is being failed by
    /// name. See [`ResolveError::out_of_memory`].
    pub gave_up: bool,
}

impl ResolveReport {
    /// Fold one round's numbers into the pack's. Sums, and the two extremes
    /// taken as extremes — a merge that does not depend on which worker
    /// produced what, so the audit line is the same at any worker count.
    pub fn absorb(&mut self, r: ResolveReport) {
        self.rows += r.rows;
        self.reinflations += r.reinflations;
        self.evictions += r.evictions;
        self.watchdog_drops += r.watchdog_drops;
        self.peak_base_bytes = self.peak_base_bytes.max(r.peak_base_bytes);
        self.pauses += r.pauses;
        self.paused_ms += r.paused_ms;
        self.batches += r.batches;
        self.stalls += r.stalls;
        self.shed += r.shed;
        self.workers = self.workers.max(r.workers);
        self.gave_up |= r.gave_up;
    }
}

/// 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_streaming`] 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).
///
/// Rows come back in **entry order**. Unbounded bases (the old behaviour): a
/// caller that wants the ceiling, the watchdog and streaming rows is the
/// indexer, and it uses [`resolve_streaming`].
pub fn resolve_walked(
    pack: &[u8],
    w: &PackWalk,
    hash: GitHashKind,
    archive_offset: u64,
    bases: &dyn BaseSource,
    sink: &dyn PayloadSink,
) -> Result<Vec<Resolved>> {
    let mut out: Vec<Resolved> = Vec::with_capacity(w.entries.len());
    let limits = ResolveLimits {
        row_batch: w.entries.len().max(1),
        ..ResolveLimits::none()
    };
    resolve_streaming(pack, w, hash, archive_offset, bases, sink, limits, &mut |rows| {
        out.extend(rows.drain(..));
        Ok(())
    })?;
    // Resolution order is entry order except for the ref-deltas a later round
    // picked up; offsets are unique and ascending in entry order, so this is
    // exactly the order the old `out[i]` array had.
    out.sort_unstable_by_key(|r| r.offset);
    Ok(out)
}

/// **The resolver**: bounded bases, watchdog checkpoints, rows in batches.
///
/// `rows` is called with each full batch (and the final partial one) and may
/// drain the vector; the same allocation is reused for the next batch. Nothing
/// about the rows or the sink calls depends on the batch size — it is purely
/// how much the caller holds at once.
#[allow(clippy::too_many_arguments)]
pub fn resolve_streaming(
    pack: &[u8],
    w: &PackWalk,
    hash: GitHashKind,
    archive_offset: u64,
    bases: &dyn BaseSource,
    sink: &dyn PayloadSink,
    limits: ResolveLimits<'_>,
    rows: &mut (dyn FnMut(&mut Vec<Resolved>) -> Result<()> + Send),
) -> Result<ResolveReport> {
    let mut r = Resolver::new(pack, w, hash, archive_offset, bases, sink, limits)?;
    r.run(rows)?;
    Ok(r.report)
}


// ════════════════════════════════════════════════════════════════════════════
// THE FOREST DRIVER — one subtree per unit, N workers, ONE ordered stream out
// ════════════════════════════════════════════════════════════════════════════

/// How many objects one worker resolves before it hands them to the ordered
/// emitter: one lock per few thousand objects instead of one per object.
const HANDOVER_ROWS: usize = 4096;
/// …or this many bytes of them, whichever comes first.
const HANDOVER_BYTES: u64 = 1 << 20;
/// **How large a scratch buffer may stay between objects.**
///
/// `delta` and `leaf` are reused for the whole pass, which is what makes the
/// hot path allocate nothing — and a `Vec` never gives capacity back, so one
/// 90 MB blob leaves a 90 MB buffer standing for the remaining thirteen
/// million objects. Single-threaded that was one such buffer; with a worker per
/// core it is `2 x workers` of them, and on a 16 GB appliance that is the
/// difference between finishing a kernel mirror and pausing at 98 %.
const SCRATCH_KEEP_BYTES: usize = 1 << 20;
/// What one small heap block costs beyond the bytes asked for — header plus
/// size-class rounding. Deliberately generous: the lookahead ceiling is a
/// memory bound, and a memory bound that under-counts is not one.
const ALLOC_OVERHEAD: usize = 32;
/// How many objects one pass of the drain takes out of the emit buffer before
/// it lets the writers back in — the lock-hold bound.
const DRAIN_RUN: usize = 8192;

/// One frame of a worker's depth-first path: a resolved base, held **only**
/// while its own subtree is still being walked.
struct Frame {
    entry: u32,
    kind: GitObjectKind,
    /// Empty when `evicted`.
    payload: Vec<u8>,
    evicted: bool,
    next_child: u32,
}

/// One resolved object on its way out: the row always, the payload only when
/// the sink said it would read one ([`PayloadSink::wants`]).
struct Emit {
    kind: GitObjectKind,
    row: Resolved,
    payload: Option<Vec<u8>>,
}

impl Emit {
    /// What holding this costs, for the lookahead ceiling. A count of objects
    /// cannot tell one commit from one 40 MB blob, so the ceiling is in bytes —
    /// and the bytes are the ones the ALLOCATOR charges, not the ones the
    /// struct declares. `ALLOC_OVERHEAD` is the rest of what a 20-byte oid
    /// costs: the header and the size-class rounding of its own heap block,
    /// plus this row's share of the `Vec` it sits in. Undercounting it is how a
    /// 128 MiB ceiling holds half a gigabyte.
    fn weight(&self) -> u64 {
        (std::mem::size_of::<Emit>()
            + ALLOC_OVERHEAD
            + self.row.oid.len()
            + self.payload.as_ref().map_or(0, |p| p.len() + ALLOC_OVERHEAD)) as u64
    }
}

/// A worker's own scratch: never shared, never locked, reused across the
/// subtrees one thread walks.
#[derive(Default)]
struct Scratch {
    /// Which unit (root) of this round the worker is inside — the key its
    /// output is handed over under.
    unit: usize,
    delta: Vec<u8>,
    leaf: Vec<u8>,
    stack: Vec<Frame>,
    out: Vec<Emit>,
    out_bytes: u64,
    found_refs: Vec<(Vec<u8>, u64)>,
}

std::thread_local! {
    /// Per **thread**, not per subtree: a kernel-sized pack has 2.7 M roots and
    /// allocating two grown buffers for each of them is 2.7 M mallocs the walk
    /// does not need.
    static SCRATCH: std::cell::RefCell<Scratch> = std::cell::RefCell::new(Scratch::default());
}

/// What one root has produced and the drain has not yet handed on, in
/// depth-first order, and whether the walk of that root is finished.
///
/// **One `Vec`, not a queue of them.** The median subtree in a real pack is
/// ONE object (`examples/forest_stats` on torvalds/linux: p50 1, p90 5), so a
/// `VecDeque<Vec<Emit>>` per root was two heap allocations and a deque header
/// to carry a single 20-byte oid — the per-root bookkeeping cost more than the
/// object it carried, 2.7 M times.
#[derive(Default)]
struct RootOut {
    rows: Vec<Emit>,
    done: bool,
}

/// The emit buffer, keyed by **root index**.
///
/// # 🔴 It was keyed by ENTRY index, and on a real pack that was a serialiser
///
/// Emitting in entry order is the obvious way to make N workers produce the
/// stream one worker would have: the objects come out sorted by where they sit
/// in the pack, whoever resolved them. It is also unusable, and the pack says
/// why. MEASURED on `torvalds/linux` (`examples/forest_stats`), 13 948 244
/// entries, 2 732 372 roots:
///
/// | | subtree **size** | subtree **index span** |
/// |---|---:|---:|
/// | p50 | 1 | 0 |
/// | p90 | 5 | **5 251 404** |
/// | p99 | 70 | **11 511 634** |
/// | max | 11 789 | **12 434 450** |
///
/// The subtrees are tiny — perfect parallel work — but a five-object subtree
/// routinely **spans five million entries**, because `pack-objects` puts a base
/// near its first dependent and the rest of the dependents wherever they fall.
/// So an entry-ordered cursor is pinned by any subtree in flight whose span
/// reaches the top of the pack: every other worker's output buffers behind it,
/// the lookahead ceiling closes, and the workers wait. MEASURED, the kernel
/// pack at the appliance's 4-core shape: **1 worker 1454.7 s, 2 workers
/// 1572.9 s** — *slower*, at 1.24 cores of CPU, with 286 686 stalls.
///
/// Keyed by root, the cursor moves at the rate roots finish, and roots are
/// claimed in ascending order, so it follows the workers instead of pinning
/// them. The order is still fixed and still worker-count independent: roots
/// ascending, and inside a root the depth-first sequence the children lists
/// (ascending) determine.
#[derive(Default)]
struct Pending {
    map: std::collections::BTreeMap<usize, RootOut>,
    bytes: u64,
    /// **The units a worker is inside right now.** The lookahead ceiling needs
    /// it: gatling claims a unit *before* the worker runs, so "wait until the
    /// stream catches up" would otherwise be said by the very worker the stream
    /// is waiting for. See [`Round::backpressure`].
    in_flight: std::collections::BTreeSet<usize>,
    /// How many of those units belong to a worker that has **given its core
    /// back** for the memory watchdog and is waiting rather than resolving.
    /// `in_flight.len() - parked` is therefore how many cores this pack is
    /// actually using, which is the number the last worker standing needs
    /// before it decides that pausing is the only option left.
    parked: usize,
}

/// The ordered end of the pipe. One worker at a time holds it, so the sink and
/// the row callback see exactly the sequence one worker would have made.
/// `cursor` is an index into this round's **roots**.
struct Drain<'r> {
    cursor: usize,
    batch: Vec<Resolved>,
    rows: &'r mut (dyn FnMut(&mut Vec<Resolved>) -> Result<()> + Send),
}

/// A base this round was promised from outside the pack, probed **once** while
/// the round was planned so that which entries the round covers is decided
/// before a byte is inflated.
struct RoundBases<'r, 'w, 'a> {
    external: &'r HashMap<&'w [u8], (GitObjectKind, Vec<u8>)>,
    inner: &'a dyn BaseSource,
}

impl BaseSource for RoundBases<'_, '_, '_> {
    fn content(&self, oid: &[u8]) -> Result<Option<(GitObjectKind, Vec<u8>)>> {
        if let Some((k, p)) = self.external.get(oid) {
            return Ok(Some((*k, p.clone())));
        }
        self.inner.content(oid)
    }
}

/// **One round of the fixpoint, across N workers.**
///
/// Everything in here is either immutable for the length of the round or an
/// atomic/lock, because a `&Round` is what every worker holds.
struct Round<'p, 'w, 'a, 'r> {
    pack: &'p [u8],
    w: &'w PackWalk,
    forest: &'r DeltaForest,
    hash: GitHashKind,
    oid_len: usize,
    archive_offset: u64,
    bases: &'a dyn BaseSource,
    sink: &'a dyn PayloadSink,
    limits: &'r ResolveLimits<'a>,
    /// The oids some `REF_DELTA` in this pack names. Read-only here.
    ref_wanted: &'r std::collections::HashSet<&'w [u8]>,
    /// Where a named oid turned out to live, from the rounds **before** this one.
    oid_to_offset: &'r HashMap<Vec<u8>, u64>,
    external: &'r HashMap<&'w [u8], (GitObjectKind, Vec<u8>)>,
    roots: &'r [u32],
    in_round: &'r EntrySet,
    workers: usize,
    lookahead: u64,

    pend: std::sync::Mutex<Pending>,
    cv: std::sync::Condvar,
    drain: std::sync::Mutex<Drain<'r>>,
    pause_gate: std::sync::Mutex<()>,
    stop: AtomicBool,
    err: std::sync::Mutex<Option<(usize, anyhow::Error)>>,
    since_check: std::sync::atomic::AtomicU64,

    rows: std::sync::atomic::AtomicU64,
    reinflations: std::sync::atomic::AtomicU64,
    evictions: std::sync::atomic::AtomicU64,
    watchdog_drops: std::sync::atomic::AtomicU64,
    /// **The whole job's** held base bytes, across every worker — lane Q's one
    /// budget, not one per thread (LAW 5).
    live_path: std::sync::atomic::AtomicU64,
    peak_path: std::sync::atomic::AtomicU64,
    pauses: std::sync::atomic::AtomicU64,
    paused_ms: std::sync::atomic::AtomicU64,
    batches: std::sync::atomic::AtomicU64,
    stalls: std::sync::atomic::AtomicU64,
    shed: std::sync::atomic::AtomicU64,
    gave_up: AtomicBool,
    found_refs: std::sync::Mutex<Vec<(Vec<u8>, u64)>>,
}

impl<'p, 'w, 'a, 'r> Round<'p, 'w, 'a, 'r> {
    // ── one subtree ─────────────────────────────────────────────────────────

    /// The unit of work: one root, its whole subtree, in a fixed depth-first
    /// order.
    fn run_root(&self, ri: usize, s: &mut Scratch) -> Result<()> {
        // A previous unit that failed may have left a path standing; nothing
        // else can, because a finished walk pops every frame.
        if !s.stack.is_empty() {
            self.drop_path(s);
            s.stack.clear();
        }
        s.unit = ri;
        let root = self.roots[ri];
        let r = (|| {
            let (kind, payload) = self.root_content(root)?;
            self.emit(root, kind, &payload, s)?;
            if self.forest.children(root).is_empty() {
                drop(payload);
            } else {
                self.push_frame(root, kind, payload, s);
                self.walk(s)?;
            }
            Ok(())
        })();
        // **The unit is closed even when it failed**, so the drain is never
        // left waiting on a root that will never say it is finished.
        self.flush_scratch(s, true)?;
        r
    }

    /// A root's own content. `DeltaBase::None` inflates; a `REF_DELTA` root
    /// applies its delta to a base this round already promised — either an
    /// entry a previous round placed, or one the [`BaseSource`] answered for.
    fn root_content(&self, root: u32) -> Result<(GitObjectKind, Vec<u8>)> {
        let e = &self.w.entries[root as usize];
        match &e.delta_base {
            DeltaBase::None => {
                let kind = whole_kind(e.obj_type)?;
                let mut out = Vec::with_capacity(e.uncompressed_size as usize);
                inflate_into(self.pack, e, self.oid_len, &mut out)?;
                Ok((kind, out))
            }
            DeltaBase::Ref(oid) => {
                let (kind, base) = match self.oid_to_offset.get(oid.as_slice()).copied() {
                    Some(o) => {
                        let be = self
                            .w
                            .entries
                            .binary_search_by_key(&o, |x| x.offset)
                            .map_err(|_| {
                                anyhow!("no entry starts at offset {o} — the pack is corrupt")
                            })?;
                        self.materialize(be as u32)?
                    }
                    None => match self.external.get(oid.as_slice()) {
                        Some((k, p)) => (*k, p.clone()),
                        None => return Err(ResolveError::missing_base(oid)),
                    },
                };
                let mut delta = Vec::with_capacity(e.uncompressed_size as usize);
                inflate_into(self.pack, e, self.oid_len, &mut delta)?;
                let mut out = Vec::new();
                apply_delta_into(&base, &delta, &mut out)?;
                Ok((kind, out))
            }
            DeltaBase::Offset(_) => bail!(
                "the entry at offset {} deltas against an offset, so it is not a root of a \
                 resolve round — the forest is inconsistent with the walk",
                e.offset
            ),
        }
    }

    /// **The walk.** An explicit stack, not recursion: a verbatim archive grows
    /// one delta link per push ([`MAX_DELTA_LINKS`]), so a legitimate chain has
    /// no depth this code may assume.
    fn walk(&self, s: &mut Scratch) -> Result<()> {
        while !s.stack.is_empty() {
            let fi = s.stack.len() - 1;
            let entry = s.stack[fi].entry;
            let nkids = self.forest.children(entry).len();
            let nc = s.stack[fi].next_child as usize;
            if nc == nkids {
                self.pop_frame(s);
                continue;
            }
            let c = self.forest.children(entry)[nc];
            s.stack[fi].next_child += 1;
            let last = nc + 1 == nkids;
            let kind = s.stack[fi].kind;

            // The base for this child: moved out on the last one, cloned
            // otherwise, re-inflated if the ceiling took it.
            let base: Vec<u8> = if s.stack[fi].evicted {
                let (_, p) = self.materialize(entry)?;
                self.reinflations.fetch_add(1, Ordering::Relaxed);
                if let Some(pr) = self.limits.progress {
                    pr.add_reinflations(1);
                }
                if !last {
                    let n = p.len() as u64;
                    let budget = self.limits.base_budget;
                    if budget == 0 || self.live_path.load(Ordering::Relaxed) + n <= budget {
                        // Room for it now: keep the re-inflated copy for the
                        // next child rather than paying again. No eviction to
                        // make room — that would thrash.
                        s.stack[fi].payload = p.clone();
                        s.stack[fi].evicted = false;
                        let live = self.live_path.fetch_add(n, Ordering::Relaxed) + n;
                        self.peak_path.fetch_max(live, Ordering::Relaxed);
                    }
                }
                p
            } else if last {
                let p = std::mem::take(&mut s.stack[fi].payload);
                self.live_path
                    .fetch_sub(p.len() as u64, Ordering::Relaxed);
                s.stack[fi].evicted = true;
                p
            } else {
                s.stack[fi].payload.clone()
            };

            let ce = &self.w.entries[c as usize];
            // The scratch buffers are taken out of `s` for the length of the
            // call and put back on **every** path, error included: a bail that
            // leaves them behind would make the next child allocate again.
            let mut delta = std::mem::take(&mut s.delta);
            let mut leaf = std::mem::take(&mut s.leaf);
            let leafy = self.forest.children(c).is_empty();
            let mut carried: Option<Vec<u8>> = None;
            let r = (|| -> Result<()> {
                inflate_into(self.pack, ce, self.oid_len, &mut delta)?;
                if leafy {
                    // A leaf's payload outlives nothing: it is applied into the
                    // reused buffer, hashed in place and handed over from there.
                    apply_delta_into(&base, &delta, &mut leaf)?;
                    drop(base);
                    self.emit(c, kind, &leaf, s)
                } else {
                    let mut out = Vec::with_capacity(ce.uncompressed_size as usize);
                    apply_delta_into(&base, &delta, &mut out)?;
                    drop(base);
                    self.emit(c, kind, &out, s)?;
                    carried = Some(out);
                    Ok(())
                }
            })();
            // Give back what one big object borrowed: the buffers stay warm at
            // `SCRATCH_KEEP_BYTES` and never carry the largest object in the
            // pack for the rest of it.
            delta.shrink_to(SCRATCH_KEEP_BYTES);
            leaf.shrink_to(SCRATCH_KEEP_BYTES);
            s.delta = delta;
            s.leaf = leaf;
            r?;
            if let Some(out) = carried {
                self.push_frame(c, kind, out, s);
            }
        }
        Ok(())
    }

    fn push_frame(&self, entry: u32, kind: GitObjectKind, payload: Vec<u8>, s: &mut Scratch) {
        let len = payload.len() as u64;
        s.stack.push(Frame {
            entry,
            kind,
            payload,
            evicted: false,
            next_child: 0,
        });
        self.live_path.fetch_add(len, Ordering::Relaxed);
        // **The ceiling first, the high-water mark after.** Recording the peak
        // before the eviction counted the base that was about to be dropped,
        // so a one-byte budget reported two live bases and the report said the
        // ceiling had leaked when it had not.
        self.enforce_budget(s);
        self.peak_path
            .fetch_max(self.live_path.load(Ordering::Relaxed), Ordering::Relaxed);
    }

    fn pop_frame(&self, s: &mut Scratch) {
        if let Some(f) = s.stack.pop()
            && !f.evicted
        {
            self.live_path
                .fetch_sub(f.payload.len() as u64, Ordering::Relaxed);
        }
    }

    /// **Belady on a depth-first path.** The walk returns to the shallowest
    /// held frame only after every deeper subtree is finished, so the
    /// shallowest is by construction the one whose next use is farthest away —
    /// which is exactly the base the ceiling should drop. No `next_use` table
    /// is needed to know it; the shape says so.
    fn enforce_budget(&self, s: &mut Scratch) {
        let budget = self.limits.base_budget;
        if budget == 0 {
            return;
        }
        let mut i = 0usize;
        // The deepest frame is the one the next child reads from, so it is
        // never the eviction candidate — dropping it would re-inflate it on the
        // very next line.
        while i + 1 < s.stack.len() && self.live_path.load(Ordering::Relaxed) > budget {
            if !s.stack[i].evicted {
                let n = s.stack[i].payload.len() as u64;
                s.stack[i].payload = Vec::new();
                s.stack[i].evicted = true;
                self.live_path.fetch_sub(n, Ordering::Relaxed);
                self.evictions.fetch_add(1, Ordering::Relaxed);
            }
            i += 1;
        }
    }

    /// Every payload on this worker's path, dropped, and **how many bytes that
    /// freed** — the number the watchdog compares with zero.
    fn drop_path(&self, s: &mut Scratch) -> u64 {
        let mut freed = 0u64;
        for f in s.stack.iter_mut() {
            if !f.evicted {
                freed += f.payload.len() as u64;
                f.payload = Vec::new();
                f.evicted = true;
            }
        }
        self.live_path.fetch_sub(freed, Ordering::Relaxed);
        freed
    }

    /// Re-inflate an entry from the mmapped pack: its own chain, re-applied.
    /// **The one chain walker** (LAW 5) — [`materialize_entry`], with this
    /// round's promised external bases in front of the store's.
    fn materialize(&self, entry: u32) -> Result<(GitObjectKind, Vec<u8>)> {
        let rb = RoundBases {
            external: self.external,
            inner: self.bases,
        };
        let of = |oid: &[u8]| self.oid_to_offset.get(oid).copied();
        materialize_entry(self.pack, self.w, entry as usize, self.oid_len, &of, &rb)
    }

    // ── the ordered end ─────────────────────────────────────────────────────

    fn emit(&self, index: u32, kind: GitObjectKind, payload: &[u8], s: &mut Scratch) -> Result<()> {
        let e = &self.w.entries[index as usize];
        let oid = self.hash.oid_of_object(kind, payload);
        // Only now is "does a REF_DELTA name this object" answerable, because it
        // is keyed by the oid this line just computed.
        if self.ref_wanted.contains(&oid.as_slice()) {
            s.found_refs.push((oid.clone(), e.offset));
        }
        let want = self.sink.wants(kind);
        let em = Emit {
            kind,
            row: Resolved {
                oid,
                offset: e.offset + self.archive_offset,
                len: e.len,
                stored_type: e.obj_type,
                kind,
                uncompressed_size: payload.len() as u64,
                delta_base: match &e.delta_base {
                    DeltaBase::Offset(o) => o + self.archive_offset,
                    _ => 0,
                },
            },
            payload: if want { Some(payload.to_vec()) } else { None },
        };
        s.out_bytes += em.weight();
        s.out.push(em);
        self.rows.fetch_add(1, Ordering::Relaxed);
        if let Some(p) = self.limits.progress {
            p.object_done(e.len);
        }
        if s.out.len() >= HANDOVER_ROWS || s.out_bytes >= HANDOVER_BYTES {
            self.flush_scratch(s, false)?;
        }
        let n = self.since_check.fetch_add(1, Ordering::Relaxed) + 1;
        if n >= self.limits.check_every {
            self.since_check.store(0, Ordering::Relaxed);
            self.checkpoint(s)?;
        }
        Ok(())
    }

    /// Hand this worker's finished objects to the ordered emitter, then try to
    /// push the stream forward. Never blocks on the drain: whoever holds it is
    /// already doing the work. `done` closes the unit — the drain may then step
    /// past it to the next root.
    fn flush_scratch(&self, s: &mut Scratch, done: bool) -> Result<()> {
        if !s.out.is_empty() || done {
            let mut bytes = 0u64;
            for em in s.out.iter() {
                bytes += em.weight();
            }
            let unit = s.unit;
            {
                let mut p = self.lock_pend()?;
                let e = p.map.entry(unit).or_default();
                if e.rows.is_empty() {
                    e.rows = std::mem::take(&mut s.out);
                } else {
                    e.rows.append(&mut s.out);
                }
                e.done |= done;
                p.bytes += bytes;
            }
            s.out.clear();
            s.out.shrink_to(HANDOVER_ROWS);
            s.out_bytes = 0;
        }
        self.try_drain(false)
    }

    fn lock_pend(&self) -> Result<std::sync::MutexGuard<'_, Pending>> {
        self.pend
            .lock()
            .map_err(|_| anyhow!("the resolver's emit buffer is poisoned"))
    }

    /// **The stream out.** This round's roots in ascending order, and inside
    /// each root the depth-first sequence its children lists fix — to the sink
    /// first, then to the row callback.
    fn try_drain(&self, force: bool) -> Result<()> {
        let mut guard = match self.drain.try_lock() {
            Ok(g) => g,
            Err(std::sync::TryLockError::WouldBlock) => {
                if !force {
                    return Ok(());
                }
                self.drain
                    .lock()
                    .map_err(|_| anyhow!("the resolver's row drain is poisoned"))?
            }
            Err(std::sync::TryLockError::Poisoned(_)) => {
                bail!("the resolver's row drain is poisoned")
            }
        };
        let d = &mut *guard;
        loop {
            let mut run: Vec<Vec<Emit>> = Vec::new();
            let mut held = 0usize;
            let mut moved = false;
            {
                let mut p = self.lock_pend()?;
                while d.cursor < self.roots.len() {
                    let (rows, done) = match p.map.get_mut(&d.cursor) {
                        Some(ro) => (std::mem::take(&mut ro.rows), ro.done),
                        None => break,
                    };
                    if !rows.is_empty() {
                        let n: u64 = rows.iter().map(Emit::weight).sum();
                        p.bytes = p.bytes.saturating_sub(n);
                        held += rows.len();
                        run.push(rows);
                        moved = true;
                    }
                    if !done {
                        break;
                    }
                    p.map.remove(&d.cursor);
                    d.cursor += 1;
                    moved = true;
                    if held >= DRAIN_RUN {
                        break;
                    }
                }
                if moved {
                    self.cv.notify_all();
                }
            }
            if !moved {
                return Ok(());
            }
            for chunk in run {
                for em in chunk {
                    if let Some(pay) = &em.payload {
                        self.sink.explode(&em.row.oid, em.kind, pay)?;
                    }
                    d.batch.push(em.row);
                    if d.batch.len() >= self.limits.row_batch {
                        (d.rows)(&mut d.batch)?;
                        self.batches.fetch_add(1, Ordering::Relaxed);
                        d.batch.clear();
                    }
                }
            }
        }
    }

    /// Everything left, in order, at the end of a round.
    fn finish(&self) -> Result<()> {
        self.try_drain(true)?;
        let mut d = self
            .drain
            .lock()
            .map_err(|_| anyhow!("the resolver's row drain is poisoned"))?;
        if !d.batch.is_empty() {
            let d = &mut *d;
            (d.rows)(&mut d.batch)?;
            self.batches.fetch_add(1, Ordering::Relaxed);
            d.batch.clear();
        }
        let p = self.lock_pend()?;
        if !p.map.is_empty() || d.cursor != self.roots.len() {
            bail!(
                "the resolver finished a round at root {} of {} with {} roots still unemitted — \
                 the round's roots and the walk disagree",
                d.cursor,
                self.roots.len(),
                p.map.len()
            );
        }
        Ok(())
    }

    /// **The lookahead ceiling, and the one worker it may never stop.**
    ///
    /// A worker that has run far ahead of the ordered stream waits here rather
    /// than buffering the pack. The rule for *who* waits is the whole
    /// correctness argument: the worker holding the **lowest unit in flight**
    /// never waits. Gatling hands its units out in ascending order, so every
    /// lower unit is already finished, and the entry the ordered cursor is
    /// stuck on therefore belongs either to a finished unit — already in the
    /// buffer, and the drain will take it — or to the lowest unit in flight,
    /// which is running. Progress is guaranteed either way.
    ///
    /// 🔴 It said "one worker is never allowed to wait, whichever it is", and
    /// that HUNG: gatling claims a unit *before* it calls the closure, so the
    /// worker allowed to run on was frequently not the one the cursor was
    /// waiting for. It then consumed every remaining unit while the worker
    /// holding the cursor's own unit sat in `wait` forever, and the scope never
    /// joined. Caught by
    /// `the_same_pack_resolves_to_the_same_bytes_at_1_2_and_4_workers`, which
    /// ran for over 60 s and had to be killed.
    fn backpressure(&self, ri: usize) -> Result<()> {
        self.try_drain(false)?;
        let mut p = self.lock_pend()?;
        while p.bytes > self.lookahead
            && !self.stop.load(Ordering::Relaxed)
            && p.in_flight.first().is_some_and(|lowest| *lowest < ri)
        {
            self.stalls.fetch_add(1, Ordering::Relaxed);
            p = self
                .cv
                .wait(p)
                .map_err(|_| anyhow!("the resolver's emit buffer is poisoned"))?;
        }
        Ok(())
    }

    /// Enter and leave a unit. The set is what [`backpressure`](Self::backpressure)
    /// reads, and leaving one is what lets a waiting worker re-decide.
    fn enter(&self, ri: usize) -> Result<()> {
        self.lock_pend()?.in_flight.insert(ri);
        Ok(())
    }

    fn leave(&self, ri: usize) {
        if let Ok(mut p) = self.pend.lock() {
            p.in_flight.remove(&ri);
        }
        self.cv.notify_all();
    }

    // ── the checkpoints ─────────────────────────────────────────────────────

    /// Every [`crate::memguard::CHECK_EVERY_OBJECTS`] objects **of the whole
    /// job**: another worker's failure, the cancel flag, then the watchdog.
    fn checkpoint(&self, s: &mut Scratch) -> Result<()> {
        if self.stop.load(Ordering::Relaxed) {
            bail!("this pack is being failed by another worker");
        }
        if self.limits.cancel.is_some_and(|c| c.load(Ordering::Relaxed)) {
            return Err(ResolveError::cancelled());
        }
        let Some(dog) = self.limits.watchdog.clone() else {
            return Ok(());
        };
        if dog.breached().is_none() {
            return Ok(());
        }
        // My own share of the problem, dropped before anybody waits.
        let mut freed = self.drop_path(s);

        // ── GIVE THE CORE BACK BEFORE GIVING THE PACK UP ────────────────────
        //
        // **A short box wants fewer workers, not a refused pack.** MEASURED on
        // the rig, the 16 GB appliance and the 8.12 GiB kernel mirror: one
        // worker finishes it with 5.55 GiB to spare, two stop at 96 % and four
        // at 86 %. The cost is not the resolver's own structures — peak RSS at
        // four workers (13.7 GiB) is BELOW the single-threaded fixpoint's
        // (14.04 GiB) — it is that four depth-first cursors over a pack whose
        // subtrees span millions of entries keep far more of the 8.12 GiB
        // mapping resident at once, and `MemAvailable` counts half of page
        // cache.
        //
        // So a worker that finds the box short **stops being a worker**: it
        // waits until it is the lowest unit in flight, which is exactly when
        // every worker above it has drained, and the round finishes on one
        // core instead of being refused on four. It never deadlocks for the
        // same reason [`backpressure`](Self::backpressure) does not — the
        // lowest unit in flight never waits, and gatling hands units out in
        // ascending order, so the lowest always advances.
        //
        // The ordered emitter means this changes only WHEN work happens, never
        // in what order it comes out: the stream is byte-identical either way.
        {
            let mut p = self.lock_pend()?;
            let mut waited = false;
            loop {
                if self.stop.load(Ordering::Relaxed) {
                    break;
                }
                let lowest = p.in_flight.first().copied();
                if lowest.is_some_and(|l| l < s.unit) {
                    // Somebody below me is still the one the ordered stream is
                    // waiting for: I am the expendable one. Park.
                    if !waited {
                        waited = true;
                        p.parked += 1;
                        self.shed.fetch_add(1, Ordering::Relaxed);
                        if let Some(pr) = self.limits.progress {
                            pr.set_phase(Phase::Paused);
                        }
                        self.cv.notify_all();
                    }
                    p = self
                        .cv
                        .wait(p)
                        .map_err(|_| anyhow!("the resolver's emit buffer is poisoned"))?;
                    continue;
                }
                // I am the lowest unit in flight — the one that must carry on.
                // **Do not pause while other workers are still resolving**:
                // they are what the box cannot afford, and each of them will
                // park at its own next checkpoint. Pausing here instead would
                // stop the only worker that is allowed to make progress and
                // then time out on a box that was about to have room.
                if p.in_flight.len() > p.parked + 1 {
                    if waited {
                        waited = false;
                        p.parked -= 1;
                    }
                    drop(p);
                    if let Some(pr) = self.limits.progress {
                        pr.set_phase(Phase::Resolve);
                    }
                    return Ok(());
                }
                break;
            }
            if waited {
                p.parked -= 1;
            }
            drop(p);
            if waited {
                if let Some(pr) = self.limits.progress {
                    pr.set_phase(Phase::Resolve);
                }
                if self.stop.load(Ordering::Relaxed) {
                    bail!("this pack is being failed by another worker");
                }
                // The box may well be fine now that everybody above me has
                // stopped. Re-ask before waking the watchdog.
                if dog.breached().is_none() {
                    return Ok(());
                }
            }
        }

        if let Some(p) = self.limits.progress {
            p.set_phase(Phase::Paused);
            p.add_pause();
        }
        // **Only one worker drives the pause**; the others block on this gate,
        // which is the point — an indexer that keeps three threads allocating
        // through a pause is not paused. They have already dropped their own
        // bases on the way in.
        let gate = self
            .pause_gate
            .lock()
            .map_err(|_| anyhow!("the resolver's pause gate is poisoned"))?;
        // 🔴 **A give-up is the whole pack's, not one worker's.** Without this
        // line the workers queued on the gate each opened a pause of their own
        // after the first had already given up. MEASURED on the rig, two
        // workers: `gave up after 30681 ms (nothing-to-give)` at 00:59:33, then
        // a second pause opened in the same millisecond and ran the FULL
        // `PAUSE_DEADLINE` — `gave up after 300164 ms (deadline)` at 01:04:33.
        // Five minutes of a client waiting for a verdict the box had already
        // reached. One give-up stops the round.
        if self.stop.load(Ordering::Relaxed) {
            drop(gate);
            bail!("this pack is being failed by another worker");
        }
        if dog.breached().is_none() {
            drop(gate);
            if let Some(p) = self.limits.progress {
                p.set_phase(Phase::Resolve);
            }
            return Ok(());
        }
        let (cancel, on_pause, label) = (self.limits.cancel, self.limits.on_pause, self.limits.label);
        let mut flush = || -> Result<u64> {
            let mut f = std::mem::take(&mut freed);
            self.watchdog_drops.fetch_add(1, Ordering::Relaxed);
            self.sink.flush()?;
            // `false`: the unit is mid-walk, so the drain must not step past
            // this root — it is not finished, it is paused.
            self.flush_scratch(s, false)?;
            self.try_drain(true)?;
            if let Some(g) = on_pause {
                f = f.saturating_add(g());
            }
            Ok(f)
        };
        let paused = dog.pause_until_ok(label, cancel, &mut flush);
        let ms = match &paused {
            Ok(p) => p.ms,
            Err(_) => 0,
        };
        self.pauses.fetch_add(1, Ordering::Relaxed);
        self.paused_ms.fetch_add(ms, Ordering::Relaxed);
        if let Some(p) = self.limits.progress {
            p.set_phase(Phase::Resolve);
        }
        drop(gate);
        let paused = paused?;
        if self.limits.cancel.is_some_and(|c| c.load(Ordering::Relaxed)) {
            return Err(ResolveError::cancelled());
        }
        // **A give-up is not a resume.** The pack is refused by name; its bytes
        // stay durable and nothing partial is left indexed.
        if paused.end.gave_up() {
            self.gave_up.store(true, Ordering::Relaxed);
            // Before the error is even built: every worker queued behind the
            // gate must find the round already lost.
            self.stop.store(true, Ordering::Relaxed);
            if self.pend.lock().is_ok() {
                self.cv.notify_all();
            }
            let (done, total) = match self.limits.progress {
                Some(p) => {
                    let sn = p.snapshot();
                    (sn.objects_done, sn.objects_total)
                }
                None => (self.rows.load(Ordering::Relaxed), self.w.entries.len() as u64),
            };
            return Err(ResolveError::out_of_memory(
                paused.end.as_str(),
                paused.available,
                paused.budget,
                done,
                total,
            ));
        }
        Ok(())
    }

    /// The first failure by **root index**, so a pack that two workers could
    /// fail is refused with the same sentence every time.
    fn fail(&self, ri: usize, e: anyhow::Error) {
        self.stop.store(true, Ordering::Relaxed);
        if let Ok(mut g) = self.err.lock() {
            let take = match &*g {
                Some((i, _)) => ri < *i,
                None => true,
            };
            if take {
                *g = Some((ri, e));
            }
        }
        if self.pend.lock().is_ok() {
            self.cv.notify_all();
        }
    }

    fn take_err(&self) -> Option<anyhow::Error> {
        self.err.lock().ok().and_then(|mut g| g.take()).map(|(_, e)| e)
    }

    fn report(&self) -> ResolveReport {
        ResolveReport {
            rows: self.rows.load(Ordering::Relaxed),
            reinflations: self.reinflations.load(Ordering::Relaxed),
            evictions: self.evictions.load(Ordering::Relaxed),
            watchdog_drops: self.watchdog_drops.load(Ordering::Relaxed),
            peak_base_bytes: self.peak_path.load(Ordering::Relaxed),
            pauses: self.pauses.load(Ordering::Relaxed),
            paused_ms: self.paused_ms.load(Ordering::Relaxed),
            batches: self.batches.load(Ordering::Relaxed),
            stalls: self.stalls.load(Ordering::Relaxed),
            shed: self.shed.load(Ordering::Relaxed),
            workers: self.workers as u32,
            gave_up: self.gave_up.load(Ordering::Relaxed),
        }
    }
}

/// **The resolver.** One walk, one forest, one ordered stream out, and as many
/// workers as the box was told to use.
struct Resolver<'p, 'w, 'a> {
    pack: &'p [u8],
    w: &'w PackWalk,
    hash: GitHashKind,
    oid_len: usize,
    archive_offset: u64,
    bases: &'a dyn BaseSource,
    sink: &'a dyn PayloadSink,
    limits: ResolveLimits<'a>,
    forest: DeltaForest,
    /// The oids `REF_DELTA` entries in this pack name — the half of the
    /// dependent set that is not knowable from an offset.
    ref_wanted: std::collections::HashSet<&'w [u8]>,
    /// …and where they turned out to live, as the rounds place them.
    oid_to_offset: HashMap<Vec<u8>, u64>,
    report: ResolveReport,
}

impl<'p, 'w, 'a> Resolver<'p, 'w, 'a> {
    fn new(
        pack: &'p [u8],
        w: &'w PackWalk,
        hash: GitHashKind,
        archive_offset: u64,
        bases: &'a dyn BaseSource,
        sink: &'a dyn PayloadSink,
        limits: ResolveLimits<'a>,
    ) -> Result<Self> {
        // **The dependents, as the forest they always were.** Built from
        // `PackWalk::entries` and nothing else (LAW 5): `parent`, the CSR child
        // lists, and the roots.
        let forest = DeltaForest::build(w)?;
        let mut ref_wanted: std::collections::HashSet<&'w [u8]> = std::collections::HashSet::new();
        for e in w.entries.iter() {
            if let DeltaBase::Ref(oid) = &e.delta_base {
                ref_wanted.insert(oid.as_slice());
            }
        }
        Ok(Self {
            pack,
            w,
            hash,
            oid_len: hash.oid_len(),
            archive_offset,
            bases,
            sink,
            forest,
            ref_wanted,
            oid_to_offset: HashMap::new(),
            report: ResolveReport::default(),
            limits,
        })
    }

    /// The fixpoint, one round at a time — and each round is a gatling fan-out
    /// over its roots.
    ///
    /// A round is planned before a byte of it is inflated: its roots are the
    /// entries whose base is available *now*, and its entry set is the closure
    /// of those roots over the forest. That is what lets the ordered emitter
    /// know, for every index, whether to wait for it or step past it — and
    /// therefore what makes the stream out of N workers the stream out of one.
    fn run(&mut self, rows: &mut (dyn FnMut(&mut Vec<Resolved>) -> Result<()> + Send)) -> Result<()> {
        let n = self.w.entries.len();
        if let Some(p) = self.limits.progress {
            p.set_total(n as u64);
            p.set_phase(Phase::Resolve);
        }
        if n == 0 {
            return Ok(());
        }
        let w = self.w;
        let mut done = EntrySet::new(n);
        let mut round = 0usize;
        while done.len() < n {
            let mut roots: Vec<u32> = if round == 0 {
                self.forest.whole_roots().to_vec()
            } else {
                Vec::new()
            };
            // A `REF_DELTA` names a base by oid. It is resolvable this round if
            // an earlier round placed that oid inside the pack, or if the store
            // can produce it — exactly the two answers the serial fixpoint
            // asked for, asked once each, up front, so the round's membership
            // is a fact rather than a race.
            let mut external: HashMap<&'w [u8], (GitObjectKind, Vec<u8>)> = HashMap::new();
            for &r in self.forest.ref_roots() {
                if done.contains(r as usize) {
                    continue;
                }
                let DeltaBase::Ref(oid) = &w.entries[r as usize].delta_base else {
                    continue;
                };
                if self.oid_to_offset.contains_key(oid.as_slice())
                    || external.contains_key(oid.as_slice())
                {
                    roots.push(r);
                    continue;
                }
                if let Some(c) = self.bases.content(oid)? {
                    external.insert(oid.as_slice(), c);
                    roots.push(r);
                }
            }
            if roots.is_empty() {
                // Nothing can move: every remaining entry waits on a base
                // nobody can supply. Name the first one — a thin pack is the
                // ordinary reason.
                for &r in self.forest.ref_roots() {
                    if !done.contains(r as usize)
                        && let DeltaBase::Ref(oid) = &w.entries[r as usize].delta_base
                    {
                        return Err(ResolveError::missing_base(oid));
                    }
                }
                bail!(
                    "{} of {n} entries could not be resolved and none of them deltas against an \
                     oid — the pack is corrupt",
                    n - done.len()
                );
            }
            roots.sort_unstable();
            let in_round = self.forest.closure_of(&roots);
            let (rep, found) = self.run_round(&roots, &in_round, &external, rows)?;
            self.report.absorb(rep);
            for (oid, off) in found {
                self.oid_to_offset.insert(oid, off);
            }
            done.union_with(&in_round);
            round += 1;
        }
        Ok(())
    }

    /// One round: **the gatling fan-out**. NEVER rayon (LAW 3) — every thread
    /// in this constellation originates in `gatling`, and this is its fork-join
    /// shape: a fixed `0..roots` of independent units, self-dispatched from one
    /// atomic, no barrier between them.
    fn run_round(
        &self,
        roots: &[u32],
        in_round: &EntrySet,
        external: &HashMap<&'w [u8], (GitObjectKind, Vec<u8>)>,
        rows: &mut (dyn FnMut(&mut Vec<Resolved>) -> Result<()> + Send),
    ) -> Result<(ResolveReport, Vec<(Vec<u8>, u64)>)> {
        let workers = self
            .limits
            .workers
            .max(1)
            .min(roots.len().max(1))
            .min(MAX_WORKERS);
        let round = Round {
            pack: self.pack,
            w: self.w,
            forest: &self.forest,
            hash: self.hash,
            oid_len: self.oid_len,
            archive_offset: self.archive_offset,
            bases: self.bases,
            sink: self.sink,
            limits: &self.limits,
            ref_wanted: &self.ref_wanted,
            oid_to_offset: &self.oid_to_offset,
            external,
            roots,
            in_round,
            workers,
            lookahead: self.limits.lookahead_bytes.max(1 << 20),
            pend: std::sync::Mutex::new(Pending::default()),
            cv: std::sync::Condvar::new(),
            drain: std::sync::Mutex::new(Drain {
                cursor: 0,
                batch: Vec::with_capacity(self.limits.row_batch.min(1 << 20)),
                rows,
            }),
            pause_gate: std::sync::Mutex::new(()),
            stop: AtomicBool::new(false),
            err: std::sync::Mutex::new(None),
            since_check: std::sync::atomic::AtomicU64::new(0),
            rows: std::sync::atomic::AtomicU64::new(0),
            reinflations: std::sync::atomic::AtomicU64::new(0),
            evictions: std::sync::atomic::AtomicU64::new(0),
            watchdog_drops: std::sync::atomic::AtomicU64::new(0),
            live_path: std::sync::atomic::AtomicU64::new(0),
            peak_path: std::sync::atomic::AtomicU64::new(0),
            pauses: std::sync::atomic::AtomicU64::new(0),
            paused_ms: std::sync::atomic::AtomicU64::new(0),
            batches: std::sync::atomic::AtomicU64::new(0),
            stalls: std::sync::atomic::AtomicU64::new(0),
            shed: std::sync::atomic::AtomicU64::new(0),
            gave_up: AtomicBool::new(false),
            found_refs: std::sync::Mutex::new(Vec::new()),
        };
        gatling_for_each_unit(roots.len(), workers, |ri| {
            if round.stop.load(Ordering::Relaxed) {
                return;
            }
            let r = SCRATCH.with(|cell| -> Result<()> {
                let mut s = cell.borrow_mut();
                round.enter(ri)?;
                let r = (|| {
                    round.backpressure(ri)?;
                    if round.stop.load(Ordering::Relaxed) {
                        return Ok(());
                    }
                    round.run_root(ri, &mut s)
                })();
                if !s.found_refs.is_empty()
                    && let Ok(mut g) = round.found_refs.lock()
                {
                    g.append(&mut s.found_refs);
                }
                round.leave(ri);
                r
            });
            if let Err(e) = r {
                round.fail(ri, e);
            }
        });
        if let Some(e) = round.take_err() {
            // Everything this round did stays where it is; the caller refuses
            // the pack by name and nothing partial is marked indexed.
            return Err(e);
        }
        round.finish()?;
        let mut found = round
            .found_refs
            .lock()
            .map_err(|_| anyhow!("the resolver's ref table is poisoned"))?
            .split_off(0);
        // The order N workers found them in is not an order; sorting makes the
        // map the same map at any worker count.
        found.sort_unstable();
        found.dedup();
        Ok((round.report(), found))
    }
}

/// The gatling fork-join, by its own name, with the one-worker case kept off
/// the thread pool entirely: `workers == 1` runs the units on the calling
/// thread, which is what makes a 1-worker run the reference a 2- and a
/// 4-worker run are compared against.
fn gatling_for_each_unit<F: Fn(usize) + Sync>(n: usize, workers: usize, f: F) {
    znippy_zoomies::gatling_forkjoin::gatling_run(n, workers, f);
}


/// **One object's content from a pack and an entry, with only its chain
/// inflated** — the lazy read path. `offset_of_oid` answers a `REF_DELTA`
/// base that is inside the pack (its entry offset); `bases` answers one that is
/// not. Nothing is cached: a chain of depth d costs d inflates and d−1 delta
/// applications, and nothing else.
pub fn materialize_entry(
    pack: &[u8],
    w: &PackWalk,
    entry: usize,
    oid_len: usize,
    offset_of_oid: &dyn Fn(&[u8]) -> Option<u64>,
    bases: &dyn BaseSource,
) -> Result<(GitObjectKind, Vec<u8>)> {
    let e = w
        .entries
        .get(entry)
        .ok_or_else(|| anyhow!("entry {entry} is past the walk ({} entries)", w.entries.len()))?;
    match &e.delta_base {
        DeltaBase::None => {
            let mut out = Vec::with_capacity(e.uncompressed_size as usize);
            inflate_into(pack, e, oid_len, &mut out)?;
            Ok((whole_kind(e.obj_type)?, out))
        }
        DeltaBase::Offset(o) => {
            let base_entry = w
                .entries
                .binary_search_by_key(o, |x| x.offset)
                .map_err(|_| anyhow!("no entry starts at offset {o} — the pack is corrupt"))?;
            let (kind, base) = materialize_entry(pack, w, base_entry, oid_len, offset_of_oid, bases)?;
            let mut delta = Vec::with_capacity(e.uncompressed_size as usize);
            inflate_into(pack, e, oid_len, &mut delta)?;
            let mut out = Vec::new();
            apply_delta_into(&base, &delta, &mut out)?;
            Ok((kind, out))
        }
        DeltaBase::Ref(oid) => {
            let (kind, base) = match offset_of_oid(oid) {
                Some(o) => {
                    let base_entry = w
                        .entries
                        .binary_search_by_key(&o, |x| x.offset)
                        .map_err(|_| anyhow!("no entry starts at offset {o} — the pack is corrupt"))?;
                    materialize_entry(pack, w, base_entry, oid_len, offset_of_oid, bases)?
                }
                None => bases.content(oid)?.ok_or_else(|| ResolveError::missing_base(oid))?,
            };
            let mut delta = Vec::with_capacity(e.uncompressed_size as usize);
            inflate_into(pack, e, oid_len, &mut delta)?;
            let mut out = Vec::new();
            apply_delta_into(&base, &delta, &mut out)?;
            Ok((kind, out))
        }
    }
}


// ════════════════════════════════════════════════════════════════════════════
// The LAZY read path: one object, one chain, straight out of the archive
// ════════════════════════════════════════════════════════════════════════════

/// Bytes of the verbatim archive, addressed **absolutely**.
///
/// The mmap ([`crate::archive_map`]) answers without a syscall and without a
/// copy; a `pread` answers the tail a snapshot does not cover. Both are the
/// same bytes, which is why the chain walker below can take either and never
/// know which it got.
///
/// It exists so [`materialize_at`] can live here — beside the delta code it
/// reuses — without this module learning what a store is.
pub trait ArchiveBytes {
    /// Up to `len` bytes at `at`. **Short is not an error**: a probe near the
    /// end of the archive legitimately gets fewer, and the parsers below read a
    /// grammar rather than a fixed width. Empty means "there is nothing there",
    /// which every caller treats as a corrupt back-reference.
    fn at(&self, at: u64, len: u64) -> Result<std::borrow::Cow<'_, [u8]>>;
}

/// A whole `&[u8]` as an archive — what a test and a single-pack caller use.
pub struct SliceArchive<'a>(pub &'a [u8]);

impl ArchiveBytes for SliceArchive<'_> {
    fn at(&self, at: u64, len: u64) -> Result<std::borrow::Cow<'_, [u8]>> {
        let start = usize::try_from(at).unwrap_or(usize::MAX).min(self.0.len());
        let end = start.saturating_add(usize::try_from(len).unwrap_or(usize::MAX)).min(self.0.len());
        Ok(std::borrow::Cow::Borrowed(&self.0[start..end]))
    }
}

/// **What one read actually cost**, measured by the read rather than predicted.
///
/// The whole point of carrying it: the cache admission decision needs to know
/// whether an object was expensive to produce, and the reader that just
/// produced it is the only thing in the system that knows for certain. The
/// index could carry a depth column instead — git's `.idx` does not, but the
/// walk computes one — and it would still be a prediction of what a read will
/// cost, while this is the bill.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct ReadCost {
    /// Delta links followed. `0` is a whole object: one inflate of one zlib
    /// stream at one offset, which is what makes a direct read cheap enough
    /// that caching it would be a waste of somebody's quota.
    pub depth: u32,
    /// Bytes the chain produced.
    pub inflated: u64,
    /// The chain bottomed out on an object this archive does not hold, so a
    /// [`BaseSource`] paid for it. Rare, and never cheap.
    pub external_base: bool,
}

/// git's own `pack.depth` ceiling doubled. **The depth at which a chain walk
/// stops assuming it will terminate and starts proving it** — see
/// [`CycleGuard`]. It is not a refusal any more, and the 🔴 below says why.
///
/// # 🔴 It WAS a refusal, and that refusal failed ordinary pushes
///
/// MEASURED, oden, 2026-08-30 (lane AI, reproducing lane AD's rig red): 140
/// sequential single-commit pushes of one file into one repository. Push #120
/// was refused with *"this pack is thin: it deltas against 509be6a7… which is
/// not in it, and no base source could produce that object's content … so this
/// repository genuinely does not have that object"* — and every one of the 20
/// pushes after it was refused too, forever. The object was **in the store, one
/// index lookup away, in a pack that had already been absorbed**. The sentence
/// was a lie, and the same red reproduces in this crate alone at push 100 of
/// 150 (`crate::thin_storm`).
///
/// The cause is what a verbatim archive does that stock git does not.
/// `git index-pack --fix-thin` *completes* a pushed thin pack by appending the
/// resolved base into it, so a stored pack's delta chains never leave it and
/// stay under the client's own `pack.depth`. §14 stores the client's bytes
/// **verbatim** — that is what makes a clone a byte-range copy — so a
/// `REF_DELTA` keeps naming a base in an *earlier pack*, and a repository
/// pushed one commit at a time grows a chain **one link per push, without
/// bound**. At the 101st link this ceiling turned a legitimate chain into
/// "corrupt pack", and [`crate::git_ops`]'s base lookup then reported the
/// object as ABSENT rather than as unreadable, which is how a store defect
/// wore a client's clothes.
///
/// A count cannot tell a deep chain from a loop. Revisiting an offset can, and
/// that is what [`CycleGuard`] does — so a cycle is caught *sooner* (the first
/// repeat, wherever it sits) and a legitimate chain is never refused. The
/// constant keeps its name and its value; only its job changed.
pub const MAX_DELTA_LINKS: usize = 100;

/// **A termination proof for a chain walk, paid for only by the chains that
/// need one.**
///
/// Under [`MAX_DELTA_LINKS`] links it is two integer operations and no
/// allocation — the shape every ordinary read has always had. Past that depth
/// it starts recording the archive offsets it has stood on, and a repeat is a
/// cycle *by definition* rather than by a guess about how deep is too deep.
/// The set is only ever entered on chains a corrupt pack or a long push history
/// produced, so the hot path is unchanged; a legitimate chain of `d` links
/// costs `d - MAX_DELTA_LINKS` `u64` slots and nothing else.
///
/// It is one guard for both walkers (LAW 5): [`materialize_at`] here and
/// `GitStore::resolved_type_at` in [`crate::serve`], which followed the same
/// links under a hand-written copy of the same ceiling.
pub struct CycleGuard {
    links: usize,
    seen: std::collections::HashSet<u64>,
}

impl Default for CycleGuard {
    fn default() -> Self {
        Self::new()
    }
}

impl CycleGuard {
    pub fn new() -> Self {
        Self {
            links: 0,
            // Empty, so a chain shallower than the threshold allocates nothing.
            seen: std::collections::HashSet::new(),
        }
    }

    /// One link, standing at archive offset `at`. `Err` **only** when this walk
    /// has already stood there, which no acyclic chain can do.
    pub fn step(&mut self, at: u64) -> Result<()> {
        self.links += 1;
        if self.links <= MAX_DELTA_LINKS {
            return Ok(());
        }
        if !self.seen.insert(at) {
            bail!(
                "the delta chain returns to archive offset {at} after {} links — the pack's \
                 back-references form a cycle, so the entry cannot be reconstructed. This is a \
                 corrupt pack and not a deep one: depth alone is never refused here, because a \
                 verbatim archive grows one link per push (see MAX_DELTA_LINKS)",
                self.links
            );
        }
        Ok(())
    }

    /// How many links this walk has taken.
    pub fn links(&self) -> usize {
        self.links
    }
}

/// Enough of an entry to hold its type/size varint plus either an `OFS_DELTA`
/// distance or a `REF_DELTA` oid. 64 covers a sha256 oid and the widest varint.
const HEADER_PROBE: u64 = 64;

/// How much compressed stream is fetched per inflate step. The stream's length
/// is not written down anywhere the index keeps, so it is discovered by
/// inflating; a window means a 40-byte commit costs one probe rather than a
/// megabyte of page faults.
const INFLATE_WINDOW: u64 = 256 << 10;

/// One link of a delta chain, as the entry's own grammar states it.
struct Link {
    obj_type: ObjType,
    /// The size the header declares: of the delta instruction stream for a
    /// delta, of the object itself for a whole entry.
    size: u64,
    /// Where the zlib stream starts — header skipped.
    data_at: u64,
}

/// **One object's content, with only its own chain inflated, addressed by
/// archive offset.**
///
/// This is the lazy-explode read path (`ideas/lazy-explode-index-only-at-push.md`).
/// The eager tier's alternative was to read the *whole containing pack* back and
/// re-resolve it — for `torvalds/linux` an 8.12 GiB read and a 13.9 M-object
/// resolve **per object served**, which is why the exploded tier had to be built
/// eagerly at push time and why that tier reached 141.7 GiB. Reading a chain
/// instead costs `d` inflates and `d − 1` delta applications and touches nothing
/// else in the pack.
///
/// * `at` — the entry's absolute archive offset, from the `objects` table's
///   `offset` column (or from a pending pack's scan).
/// * `offset_of_oid` — resolves a `REF_DELTA`'s base oid to an archive offset;
///   the `objects` index answers it.
/// * `bases` — answers a `REF_DELTA` base the index does not hold (a thin
///   pack's external base). `None` from it is
///   [`ResolveError::missing_base`], refused by name, never guessed.
///
/// Nothing is cached and nothing is written: the caller decides whether the
/// bytes are worth keeping. That separation is what lets the write-back happen
/// off the reader's path.
pub fn materialize_at(
    archive: &dyn ArchiveBytes,
    at: u64,
    oid_len: usize,
    offset_of_oid: &dyn Fn(&[u8]) -> Option<u64>,
    bases: &dyn BaseSource,
) -> Result<(GitObjectKind, Vec<u8>, ReadCost)> {
    // ── walk the chain outward, deepest link last ──────────────────────────
    let mut chain: Vec<Link> = Vec::new();
    // Set when the chain bottoms out at an object this archive does not hold.
    let mut external: Option<Vec<u8>> = None;
    let mut cursor = at;
    let mut guard = CycleGuard::new();
    loop {
        guard.step(cursor)?;
        let head = archive.at(cursor, HEADER_PROBE)?;
        if head.is_empty() {
            bail!("the archive holds no entry at offset {cursor}");
        }
        let (t, size, n) = crate::pack_walk::type_and_size_of(&head)?;
        match t {
            ObjType::Commit | ObjType::Tree | ObjType::Blob | ObjType::Tag => {
                chain.push(Link { obj_type: t, size, data_at: cursor + n as u64 });
                break;
            }
            ObjType::OfsDelta => {
                let (distance, d) = crate::pack_walk::ofs_distance_of(head.get(n..).unwrap_or(&[]))?;
                let base = cursor.checked_sub(distance).ok_or_else(|| {
                    anyhow!(
                        "the ofs-delta at archive offset {cursor} names a base {distance} bytes \
                         back, which is before the start of the archive"
                    )
                })?;
                chain.push(Link { obj_type: t, size, data_at: cursor + (n + d) as u64 });
                cursor = base;
            }
            ObjType::RefDelta => {
                let base_oid = head
                    .get(n..n + oid_len)
                    .ok_or_else(|| {
                        anyhow!(
                            "the ref-delta entry at archive offset {cursor} has no base oid after \
                             its header"
                        )
                    })?
                    .to_vec();
                chain.push(Link { obj_type: t, size, data_at: cursor + (n + oid_len) as u64 });
                match offset_of_oid(&base_oid) {
                    Some(o) => cursor = o,
                    None => {
                        external = Some(base_oid);
                        break;
                    }
                }
            }
        }
    }
    // ── the bottom of the chain: a whole object, or somebody else's ────────
    let external_base = external.is_some();
    let (kind, mut base) = match external {
        Some(oid) => bases
            .content(&oid)?
            .ok_or_else(|| ResolveError::missing_base(&oid))?,
        None => {
            let last = chain.pop().expect("a chain that ended has a last link");
            let mut out = Vec::new();
            inflate_from(archive, last.data_at, last.size, &mut out)?;
            (whole_kind(last.obj_type)?, out)
        }
    };

    // ── apply the deltas back down to the object that was asked for ────────
    let depth = chain.len() as u32;
    let mut delta = Vec::new();
    let mut out = Vec::new();
    while let Some(link) = chain.pop() {
        inflate_from(archive, link.data_at, link.size, &mut delta)?;
        out.clear();
        apply_delta_into(&base, &delta, &mut out)?;
        std::mem::swap(&mut base, &mut out);
    }
    let cost = ReadCost {
        depth,
        inflated: base.len() as u64,
        external_base,
    };
    Ok((kind, base, cost))
}

/// Inflate `expected` bytes of zlib starting at `data_at`, a window at a time.
///
/// The compressed length is **not** knowable from the index — `objects.len` is
/// the entry's stored extent only for an entry the walk measured, and a chain
/// base reached by back-reference was not measured here. So the stream is its
/// own terminator: inflate until it says `StreamEnd` or until exactly the
/// declared number of bytes have come out, and disagree loudly if the two
/// answers differ. `out` is reserved once at the declared size and never grows.
fn inflate_from(
    archive: &dyn ArchiveBytes,
    data_at: u64,
    expected: u64,
    out: &mut Vec<u8>,
) -> Result<()> {
    let want = usize::try_from(expected).map_err(|_| anyhow!("object size overflows usize"))?;
    out.clear();
    out.reserve(want);
    let mut d = flate2::Decompress::new(true);
    let mut pos = data_at;
    while out.len() < want {
        let chunk = archive.at(pos, INFLATE_WINDOW)?;
        if chunk.is_empty() {
            bail!("the zlib stream at {data_at} runs past the end of the archive");
        }
        let before = d.total_in();
        let status = d
            .decompress_vec(&chunk, out, flate2::FlushDecompress::None)
            .map_err(|e| anyhow!("inflating the entry at {data_at}: {e}"))?;
        let consumed = d.total_in() - before;
        pos += consumed;
        if status == flate2::Status::StreamEnd {
            break;
        }
        if consumed == 0 {
            bail!(
                "the zlib stream at {data_at} stalled after {} of {expected} bytes",
                out.len()
            );
        }
    }
    if out.len() as u64 != expected {
        bail!(
            "the entry at {data_at} inflated to {} bytes, its header declared {expected}",
            out.len()
        );
    }
    Ok(())
}

/// 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 into `out` (cleared first). The walk already
/// proved the length, so this reserves exactly the declared size and never
/// grows; a reused `out` allocates nothing.
fn inflate_into(pack: &[u8], e: &PackEntry, oid_len: usize, out: &mut Vec<u8>) -> Result<()> {
    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)?;
    out.clear();
    out.reserve(e.uncompressed_size as usize);
    let mut d = flate2::Decompress::new(true);
    d.decompress_vec(&pack[start + header..end], 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(())
}

/// Inflate one entry's stream into a fresh buffer. What a test or a one-off
/// caller wants; the resolver uses [`inflate_into`].
#[cfg(test)]
fn inflate(pack: &[u8], e: &PackEntry, oid_len: usize) -> Result<Vec<u8>> {
    let mut out = Vec::new();
    inflate_into(pack, e, oid_len, &mut out)?;
    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. Fresh-buffer form of [`apply_delta_into`].
#[cfg(test)]
fn apply_delta(base: &[u8], delta: &[u8]) -> Result<Vec<u8>> {
    let mut out = Vec::new();
    apply_delta_into(base, delta, &mut out)?;
    Ok(out)
}

/// git's delta format applied into `out` (cleared first, reserved to the
/// declared target size).
fn apply_delta_into(base: &[u8], delta: &[u8], out: &mut Vec<u8>) -> Result<()> {
    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)?;
    out.clear();
    out.reserve(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(())
}

/// 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 crate::object::canonical;
    use std::path::{Path, PathBuf};

    /// A label that answers `.display()`, so a source that is a generated pack
    /// and one that is a path on disk name themselves the same way in a failure.
    struct Named<'a>(&'a str);
    impl Named<'_> {
        fn display(&self) -> &str {
            self.0
        }
    }

    /// 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
    }

    /// **Pack/index pairs to compare against, the generated corpus first.**
    ///
    /// 🔴 This used to be [`real_pairs`] alone, and that made the guard's corpus
    /// the developer's disk: it took the first six `.pack` files with an `.idx`
    /// beside them under `/home/rickard/git`, in `read_dir` order, and asserted
    /// it had found at least one. On a fresh clone, on CI, or on anyone else's
    /// machine it fails with *"no real pack found under /home/rickard/git — this
    /// guard has nothing to compare"* — proven 2026-08-25 by running the suite
    /// with a tmpfs over that directory.
    ///
    /// The corpus from [`crate::pack_fixture`] leads the list, and stock git
    /// writes its `.idx` — so the arbiter is still git and not us, but the pack
    /// it arbitrates is one this repository states in source. Real packs still
    /// follow when the machine has any: they are the only place a **thin** pack
    /// turns up, and finding those in the wild is a fact this guard records.
    fn sources() -> Vec<(String, Vec<u8>, Vec<u8>)> {
        let mut out = Vec::new();
        if std::process::Command::new("git")
            .arg("--version")
            .output()
            .is_ok()
        {
            let pack = crate::pack_fixture::corpus().pack.clone();
            let scratch = crate::store::tests::tmpdir("resolve-idx-oracle");
            let idx = crate::git_oracle::git_idx_for(&scratch, "corpus.git", &pack)
                .expect("stock git indexes the generated corpus");
            out.push(("the generated corpus".to_string(), pack, idx));
        }
        for (pack_path, idx_path) in real_pairs(6) {
            let (Ok(pack), Ok(idx)) = (std::fs::read(&pack_path), std::fs::read(&idx_path)) else {
                continue;
            };
            out.push((pack_path.display().to_string(), pack, idx));
        }
        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 = sources();
        assert!(
            !pairs.is_empty(),
            "neither stock git nor a real pack is available, so 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, pack, idx_bytes) in pairs {
            let pack_path = Named(&pack_path);
            let idx = read_idx(&idx_bytes);
            // 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 compared 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 = crate::pack_fixture::corpus().pack.clone();
        let pack_path = Named("the generated corpus");
        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]) -> Result<Option<(GitObjectKind, Vec<u8>)>> {
                Ok((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_over_the_corpus() {
        use crate::index_layout::{
            FourTables, IndexEntry, ObjType, ObjectIndex, OneTableFourColumns, PackedPayload,
        };
        use crate::read_stack::{ObjectReadStack, RebuildTriggers};

        let pack = crate::pack_fixture::corpus().pack.clone();
        // 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,
            "the corpus carries only {ofs_deltas} ofs-deltas — too few to prove anything"
        );
        eprintln!(
            "{ofs_deltas} ofs-delta base offsets located their base entry in all four layouts"
        );
    }

    /// **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;
        let mut corpora: Vec<(String, Vec<u8>)> =
            vec![("the generated corpus".to_string(), crate::pack_fixture::corpus().pack.clone())];
        for (pack_path, _) in real_pairs(4) {
            if let Ok(bytes) = std::fs::read(&pack_path) {
                corpora.push((pack_path.display().to_string(), bytes));
            }
        }
        for (pack_path, pack) in corpora {
            let pack_path = Named(&pack_path);
            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 compared 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"
        );
    }

    /// The corpus plus whatever real packs the box has, as `(name, bytes)`.
    fn corpora(cap: usize) -> Vec<(String, Vec<u8>)> {
        let mut out: Vec<(String, Vec<u8>)> =
            vec![("the generated corpus".to_string(), crate::pack_fixture::corpus().pack.clone())];
        for (pack_path, _) in real_pairs(cap) {
            if let Ok(bytes) = std::fs::read(&pack_path) {
                out.push((pack_path.display().to_string(), bytes));
            }
        }
        out
    }

    /// Every `(oid, offset, size, delta_base)` the resolver produced, sorted.
    fn rows_of(rows: &[Resolved]) -> Vec<(Vec<u8>, u64, u64, u64)> {
        let mut v: Vec<_> = rows
            .iter()
            .map(|r| (r.oid.clone(), r.offset, r.uncompressed_size, r.delta_base))
            .collect();
        v.sort();
        v
    }

    fn stream(pack: &[u8], limits: ResolveLimits<'_>) -> (Vec<Resolved>, ResolveReport, u64) {
        let w = walk(pack, 20).unwrap();
        let mut out = Vec::new();
        let mut calls = 0u64;
        let report = resolve_streaming(
            pack,
            &w,
            GitHashKind::Sha1,
            0,
            &NoBases,
            &NoSink,
            limits,
            &mut |rows| {
                calls += 1;
                out.extend(rows.drain(..));
                Ok(())
            },
        )
        .unwrap();
        (out, report, calls)
    }

    /// **The bounded base set: same rows, hard ceiling, re-inflations counted.**
    ///
    /// A budget of one byte is the harshest ceiling the walk can be given: only
    /// the base the very next delta reads is held, and every shallower one on
    /// the path is dropped and inflated again from the pack. The oids, sizes
    /// and delta bases must come out identical to the unbounded pass, the peak
    /// must never exceed one base, and the count of re-inflations must be
    /// positive — otherwise the ceiling was never hit and the test proved
    /// nothing.
    ///
    /// # What "the ceiling can bite here" means, and why the predicate changed
    ///
    /// It used to be "some base has more than one dependent", which was the
    /// shape the **fixpoint** evicted on: it held every base from its own entry
    /// until its last dependent's, so two live bases needed only two bases.
    /// The forest walk holds the *path*, so a second live base needs a path two
    /// deep with work still to do above it — a node with at least two children
    /// one of which is itself a base. A pack without that shape now genuinely
    /// never evicts, and asserting that it does would be asserting the old
    /// algorithm.
    #[test]
    fn a_bounded_base_set_yields_the_same_rows_under_a_hard_ceiling_and_counts_reinflations() {
        let mut checked = 0;
        for (name, pack) in corpora(4) {
            let w = walk(&pack, 20).unwrap();
            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 forest = crate::forest::DeltaForest::build(&w).unwrap();
            let two_deep = (0..w.entries.len() as u32).any(|i| {
                let kids = forest.children(i);
                kids.len() > 1 && kids[..kids.len() - 1].iter().any(|c| !forest.children(*c).is_empty())
            });
            if !uses.values().any(|n| *n > 1) || !two_deep {
                continue;
            }
            let (free, free_report, _) = stream(&pack, ResolveLimits::none());
            assert_eq!(free_report.reinflations, 0, "{name}: unbounded must never re-inflate");
            assert_eq!(free_report.evictions, 0);
            let largest_base = free
                .iter()
                .filter(|r| uses.contains_key(&r.offset))
                .map(|r| r.uncompressed_size)
                .max()
                .unwrap();
            let tight = ResolveLimits { base_budget: 1, ..ResolveLimits::none() };
            let (bounded, report, _) = stream(&pack, tight);
            assert_eq!(rows_of(&free), rows_of(&bounded), "{name}: the ceiling changed the output");
            assert!(report.reinflations > 0, "{name}: no re-inflation — the ceiling never bit");
            assert!(report.evictions > 0, "{name}: nothing evicted");
            assert!(
                report.peak_base_bytes <= largest_base,
                "{name}: peak held {} > the largest single base {largest_base} — the ceiling leaked",
                report.peak_base_bytes
            );
            assert!(
                free_report.peak_base_bytes >= report.peak_base_bytes,
                "{name}: the unbounded pass held less ({}) than the bounded one ({})",
                free_report.peak_base_bytes,
                report.peak_base_bytes
            );
            // A generous budget: same rows, fewer re-inflations than the
            // harsh one — the eviction is Belady, so more room is never worse.
            let mid = ResolveLimits { base_budget: largest_base * 3, ..ResolveLimits::none() };
            let (mid_rows, mid_report, _) = stream(&pack, mid);
            assert_eq!(rows_of(&free), rows_of(&mid_rows), "{name}: mid budget changed the output");
            assert!(
                mid_report.reinflations <= report.reinflations,
                "{name}: more room, more re-inflations ({} > {})",
                mid_report.reinflations,
                report.reinflations
            );
            assert!(mid_report.peak_base_bytes <= largest_base * 3);
            eprintln!(
                "{name}: {} objects, unbounded peak {} B; budget 1 B → peak {} B, {} evictions, {} re-inflations; budget {} B → {} re-inflations",
                free.len(),
                free_report.peak_base_bytes,
                report.peak_base_bytes,
                report.evictions,
                report.reinflations,
                largest_base * 3,
                mid_report.reinflations
            );
            checked += 1;
        }
        assert!(
            checked > 0,
            "no pack in the corpus has a path the ceiling can bite on — nothing was proven"
        );
    }

    /// Rows arrive in batches of the size asked for, the last one partial, and
    /// nothing is lost or doubled across the batch boundary.
    #[test]
    fn rows_are_handed_over_in_batches_and_the_union_is_the_whole_pack() {
        let pack = crate::pack_fixture::corpus().pack.clone();
        let n = walk(&pack, 20).unwrap().entries.len();
        assert!(n > 7);
        let (all, report, calls) = stream(&pack, ResolveLimits { row_batch: 7, ..ResolveLimits::none() });
        assert_eq!(all.len(), n);
        assert_eq!(calls, n.div_ceil(7) as u64, "batches of 7 over {n} rows");
        assert_eq!(report.batches, calls);
        assert_eq!(report.rows, n as u64);
        let (one, _, calls1) = stream(&pack, ResolveLimits { row_batch: usize::MAX, ..ResolveLimits::none() });
        assert_eq!(calls1, 1);
        assert_eq!(rows_of(&all), rows_of(&one));
        let mut oids: Vec<_> = all.iter().map(|r| r.oid.clone()).collect();
        oids.sort();
        oids.dedup();
        assert_eq!(oids.len(), n, "a row was doubled across a batch boundary");
    }

    /// **The watchdog inside a pack**: with a fake meminfo under the floor the
    /// resolver drops every held base, flushes, and waits until the fake says
    /// memory is back — then finishes with identical rows.
    #[test]
    fn the_watchdog_pauses_a_resolve_mid_pack_drops_the_bases_and_the_rows_are_unchanged() {
        use std::sync::Arc;
        use std::time::Duration;
        let dir = crate::store::tests::tmpdir("resolve-watchdog");
        let meminfo = dir.join("meminfo");
        let write = |avail_kib: u64| {
            std::fs::write(
                &meminfo,
                format!("MemTotal:       16000000 kB\nMemAvailable:   {avail_kib} kB\n"),
            )
            .unwrap()
        };
        write(1_000_000);
        let dog = Arc::new(MemWatchdog::with(&meminfo, 3_200_000 * 1024, Duration::from_millis(5)));
        let pack = crate::pack_fixture::corpus().pack.clone();
        let (free, _, _) = stream(&pack, ResolveLimits::none());
        let m2 = meminfo.clone();
        // **Raise only once the pause is actually open.** Sleeping a flat 150 ms
        // and hoping the resolver got there first is a race the loaded box
        // loses: under a full parallel suite the first checkpoint can land at
        // 140 ms, and the assertion below then reads a 10 ms pause. Wait for
        // `is_paused`, then hold for the interval the assertion is about.
        let d2 = dog.clone();
        let raiser = std::thread::spawn(move || {
            let deadline = std::time::Instant::now() + Duration::from_secs(30);
            while !d2.is_paused() && std::time::Instant::now() < deadline {
                std::thread::sleep(Duration::from_millis(2));
            }
            std::thread::sleep(Duration::from_millis(150));
            std::fs::write(&m2, "MemTotal:       16000000 kB\nMemAvailable:   9000000 kB\n").unwrap();
        });
        let limits = ResolveLimits {
            check_every: 3,
            watchdog: Some(dog.clone()),
            ..ResolveLimits::none()
        };
        let (rows, report, _) = stream(&pack, limits);
        raiser.join().unwrap();
        assert_eq!(rows_of(&free), rows_of(&rows), "the pause changed the output");
        assert_eq!(report.pauses, 1, "one pause: the floor was breached once and the raise ended it");
        assert!(report.watchdog_drops >= 1, "the pause must drop the held bases");
        assert!(report.paused_ms >= 100, "waited {} ms; must have waited for the raise", report.paused_ms);
        assert_eq!(dog.pauses(), 1);
    }

    /// **A short box loses workers, not the pack.**
    ///
    /// The watchdog says the floor is breached and never un-says it. With one
    /// worker that is a pause and then a refusal by name. With four it must
    /// first be a *shed*: every worker above the lowest unit in flight gives
    /// its core back and waits, the round drains onto one core, and the pack
    /// still comes out — byte for byte the same stream a one-worker run makes.
    ///
    /// MEASURED on the rig and this is what it is for: the 16 GB appliance
    /// finishes the 8.12 GiB kernel mirror at one worker with 5.55 GiB to
    /// spare, and refuses it at 96 % with two and 86 % with four.
    #[test]
    fn a_short_box_sheds_its_workers_before_it_refuses_the_pack() {
        use std::sync::Arc;
        use std::time::Duration;
        let dir = crate::store::tests::tmpdir("resolve-shed");
        let meminfo = dir.join("meminfo");
        // Breached from the first checkpoint, and raised only once the LAST
        // worker standing has run out of others to shed and opened a pause —
        // which is the shape the rig measured: the box was short because of
        // the extra workers, and giving them back is what makes room.
        std::fs::write(&meminfo, "MemTotal:       16000000 kB\nMemAvailable:   1000000 kB\n").unwrap();
        let pack = crate::pack_fixture::corpus().pack.clone();
        let one = tape_of(&pack, 1, false).0;
        let dog = Arc::new(
            MemWatchdog::with(&meminfo, 3_200_000 * 1024, Duration::from_millis(2))
                .bounded(1 << 20, Duration::from_secs(30)),
        );
        let (m2, d2) = (meminfo.clone(), dog.clone());
        let raiser = std::thread::spawn(move || {
            let deadline = std::time::Instant::now() + Duration::from_secs(30);
            while !d2.is_paused() && std::time::Instant::now() < deadline {
                std::thread::sleep(Duration::from_millis(2));
            }
            std::fs::write(&m2, "MemTotal:       16000000 kB\nMemAvailable:   9000000 kB\n").unwrap();
        });
        let w = walk(&pack, 20).unwrap();
        let tape = Tape::default();
        let sink = TapeSink { tape: &tape, only_commits: false };
        let limits = ResolveLimits {
            workers: 4,
            row_batch: 64,
            lookahead_bytes: 1 << 16,
            check_every: 2,
            watchdog: Some(dog.clone()),
            ..ResolveLimits::none()
        };
        let report = resolve_streaming(
            &pack,
            &w,
            GitHashKind::Sha1,
            0,
            &NoBases,
            &sink,
            limits,
            &mut |rows| {
                tape.put(b'B', &[&(rows.len() as u64).to_le_bytes()]);
                for r in rows.iter() {
                    tape.put(
                        b'R',
                        &[
                            &r.oid,
                            &r.offset.to_le_bytes(),
                            &r.len.to_le_bytes(),
                            &[r.stored_type as u8, r.kind as u8],
                            &r.uncompressed_size.to_le_bytes(),
                            &r.delta_base.to_le_bytes(),
                        ],
                    );
                }
                rows.clear();
                Ok(())
            },
        );
        raiser.join().unwrap();
        let report = report.expect("a shed must not refuse the pack");
        assert!(
            report.shed > 0,
            "the box was short from the first checkpoint and NOTHING was shed — the guard \
             proved nothing (workers {}, pauses {})",
            report.workers,
            report.pauses
        );
        assert_eq!(report.rows, w.entries.len() as u64, "every entry is still a row");
        assert!(tape.take() == one, "the shed changed the stream");
    }

    /// A cancel flag set mid-pack aborts at the next checkpoint with the named
    /// error — the pack is not finished and nothing pretends it was.
    #[test]
    fn a_cancel_aborts_the_pack_at_the_next_checkpoint() {
        let cancel = AtomicBool::new(true);
        let pack = crate::pack_fixture::corpus().pack.clone();
        let w = walk(&pack, 20).unwrap();
        let limits = ResolveLimits { check_every: 2, cancel: Some(&cancel), ..ResolveLimits::none() };
        let mut got = 0usize;
        let err = resolve_streaming(&pack, &w, GitHashKind::Sha1, 0, &NoBases, &NoSink, limits, &mut |rows| {
            got += rows.len();
            rows.clear();
            Ok(())
        })
        .unwrap_err();
        assert!(err.to_string().contains("cancelled"), "{err:#}");
        assert!(got < w.entries.len(), "the cancel did not stop the pack ({got} rows)");
    }

    // ════════════════════════════════════════════════════════════════════════
    // THE PARALLEL RESOLVER — one stream out, whatever the worker count
    // ════════════════════════════════════════════════════════════════════════

    /// **Everything the resolver hands out, as bytes.**
    ///
    /// Not a set and not a sorted digest: the *sequence*, with the sink's calls
    /// and the row callback's batches interleaved exactly as they happened. A
    /// comparison over sorted rows would pass on any ordering at all, and
    /// ordering is the whole thing a worker count could change.
    #[derive(Default)]
    struct Tape {
        bytes: std::sync::Mutex<Vec<u8>>,
    }

    impl Tape {
        fn put(&self, tag: u8, parts: &[&[u8]]) {
            let mut b = self.bytes.lock().unwrap_or_else(|e| e.into_inner());
            b.push(tag);
            for p in parts {
                b.extend_from_slice(&(p.len() as u64).to_le_bytes());
                b.extend_from_slice(p);
            }
        }
        fn take(&self) -> Vec<u8> {
            std::mem::take(&mut self.bytes.lock().unwrap_or_else(|e| e.into_inner()))
        }
    }

    /// A sink that records every call — and, on the second arm, one that says it
    /// wants only commits, which is the shipped `ExplodePolicy::Commits` shape.
    struct TapeSink<'t> {
        tape: &'t Tape,
        only_commits: bool,
    }

    impl crate::exploded::PayloadSink for TapeSink<'_> {
        fn explode(&self, oid: &[u8], kind: GitObjectKind, payload: &[u8]) -> Result<()> {
            self.tape.put(b'E', &[oid, &[kind as u8], payload]);
            Ok(())
        }
        fn wants(&self, kind: GitObjectKind) -> bool {
            !self.only_commits || matches!(kind, GitObjectKind::Commit | GitObjectKind::Tag)
        }
    }

    /// One resolve, recorded. `workers` is the only thing that varies.
    fn tape_of(pack: &[u8], workers: usize, only_commits: bool) -> (Vec<u8>, ResolveReport) {
        let w = walk(pack, 20).unwrap();
        let tape = Tape::default();
        let sink = TapeSink { tape: &tape, only_commits };
        let limits = ResolveLimits {
            workers,
            // Small enough that a real pack crosses it many times, so the
            // batch boundaries are part of what is being compared.
            row_batch: 64,
            // …and small enough that the lookahead ceiling is actually reached,
            // so the backpressure path is on the tape too.
            lookahead_bytes: 1 << 16,
            ..ResolveLimits::none()
        };
        let report = resolve_streaming(
            pack,
            &w,
            GitHashKind::Sha1,
            0,
            &NoBases,
            &sink,
            limits,
            &mut |rows| {
                tape.put(b'B', &[&(rows.len() as u64).to_le_bytes()]);
                for r in rows.iter() {
                    tape.put(
                        b'R',
                        &[
                            &r.oid,
                            &r.offset.to_le_bytes(),
                            &r.len.to_le_bytes(),
                            &[r.stored_type as u8, r.kind as u8],
                            &r.uncompressed_size.to_le_bytes(),
                            &r.delta_base.to_le_bytes(),
                        ],
                    );
                }
                rows.clear();
                Ok(())
            },
        )
        .expect("resolve");
        (tape.take(), report)
    }

    /// **The determinism proof.** The same pack, resolved at 1, 2 and 4
    /// workers, produces byte-identical output — the same rows, in the same
    /// order, in the same batches, with the same sink calls between them.
    #[test]
    fn the_same_pack_resolves_to_the_same_bytes_at_1_2_and_4_workers() {
        let mut proved = 0usize;
        for (name, pack) in corpora(4) {
            for only_commits in [false, true] {
                let (one, r1) = tape_of(&pack, 1, only_commits);
                let (two, r2) = tape_of(&pack, 2, only_commits);
                let (four, r4) = tape_of(&pack, 4, only_commits);
                assert!(!one.is_empty(), "{name}: the tape is empty, so it proves nothing");
                assert_eq!(one.len(), two.len(), "{name}: 1 vs 2 workers, tape length");
                assert!(one == two, "{name}: 1 vs 2 workers, byte for byte");
                assert!(one == four, "{name}: 1 vs 4 workers, byte for byte");
                assert_eq!(r1.rows, r2.rows, "{name}");
                assert_eq!(r1.rows, r4.rows, "{name}");
                assert_eq!(r1.batches, r4.batches, "{name}");
                assert_eq!(r1.workers, 1, "{name}");
                proved += 1;
            }
        }
        assert!(proved >= 2, "no pack was compared — this guard proved nothing");
    }

    /// 🔴 **LAW 2: the comparison above can fail.** If the tape were blind to
    /// order — a sorted digest, a set of oids, a row count — every one of those
    /// assertions would pass on a resolver that emitted its objects in any
    /// order at all. So: take the real 4-worker tape, move ONE row later in it,
    /// and prove the comparison rejects it.
    #[test]
    fn the_determinism_tape_rejects_a_stream_whose_order_moved() {
        let pack = corpora(2).into_iter().next().expect("a pack").1;
        let (good, _) = tape_of(&pack, 4, false);
        // Find the two `R` records the tape starts with and swap them. Nothing
        // about the *contents* changes; only the order does.
        let a = good.iter().position(|b| *b == b'R').expect("a row record");
        let rec = 1 + 6 * 8 + 20 + 8 + 8 + 2 + 8 + 8; // tag + 6 lengths + fields
        assert!(good.len() > a + 2 * rec, "the tape is too short to reorder");
        let mut bad = good.clone();
        for i in 0..rec {
            bad.swap(a + i, a + rec + i);
        }
        assert_ne!(good, bad, "the two rows were identical — swapping them proved nothing");
        assert!(good != bad, "an order-blind comparison would have called these equal");
    }

    /// A sink that answers `wants = false` is **not called** for that kind, and
    /// the resolver still produces every row. This is what keeps the ordered
    /// hand-over from buffering 90 % of a pack's bytes.
    #[test]
    fn a_sink_that_wants_nothing_is_never_handed_a_payload() {
        for (name, pack) in corpora(3) {
            let w = walk(&pack, 20).unwrap();
            let tape = Tape::default();
            let sink = TapeSink { tape: &tape, only_commits: true };
            let mut rows = 0u64;
            let report = resolve_streaming(
                &pack,
                &w,
                GitHashKind::Sha1,
                0,
                &NoBases,
                &sink,
                ResolveLimits { workers: 4, ..ResolveLimits::none() },
                &mut |r| {
                    rows += r.len() as u64;
                    r.clear();
                    Ok(())
                },
            )
            .expect("resolve");
            assert_eq!(rows, w.entries.len() as u64, "{name}: every entry is a row");
            assert_eq!(report.rows, rows, "{name}");
            let calls = tape
                .take()
                .chunks(1)
                .filter(|c| c[0] == b'E')
                .count();
            // Every explode the sink DID get is a commit or a tag; and a pack
            // with any blob or tree at all must have been spared some.
            let non_commit = w
                .entries
                .iter()
                .filter(|e| matches!(e.obj_type, ObjType::Blob | ObjType::Tree))
                .count();
            if non_commit > 0 {
                assert!(
                    calls < w.entries.len(),
                    "{name}: the sink was handed all {} objects although it wanted only commits",
                    w.entries.len()
                );
            }
        }
    }

    /// **A pack whose delta shape is CHOSEN, not found.** `roots` independent
    /// whole blobs, each the root of a binary tree of `depth` levels of
    /// `OFS_DELTA`s, every object exactly `body_bytes` long.
    ///
    /// The shape is the whole point of the guard below: `roots` roots is what
    /// gives the gatling fan-out `roots` independent units to hand four workers
    /// (`run_round` takes `min(workers, roots)`), the branching is what keeps a
    /// frame live while a deeper subtree runs — a base whose last child has not
    /// been reached yet is held — and one uniform object size is what makes
    /// "the largest single base" a number this source states rather than one a
    /// found pack happens to have.
    fn base_ceiling_pack(roots: usize, depth: u32, body_bytes: usize) -> Vec<u8> {
        use crate::pack_fixture::{build_pack, Item};
        // splitmix64, four lines, so the pack is byte-identical on every box:
        // incompressible bodies, so the pack's shape is the constants above and
        // not deflate's opinion of them.
        let mut state = 0x5eed_0000_0000_0001u64;
        let mut body = |n: usize| -> Vec<u8> {
            let mut v = Vec::with_capacity(n + 8);
            while v.len() < n {
                state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
                let mut z = state;
                z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
                z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
                v.extend_from_slice(&(z ^ (z >> 31)).to_le_bytes());
            }
            v.truncate(n);
            v
        };
        let mut items: Vec<Item> = Vec::new();
        for _ in 0..roots {
            let mut level = vec![items.len()];
            items.push(Item::Whole(GitObjectKind::Blob, body(body_bytes)));
            for _ in 1..depth {
                let mut next = Vec::with_capacity(level.len() * 2);
                for base in level {
                    for _ in 0..2 {
                        next.push(items.len());
                        items.push(Item::OfsDelta { base, body: body(body_bytes) });
                    }
                }
                level = next;
            }
        }
        build_pack(&items)
    }

    /// **N workers get N walks, not N budgets.** The held-base ceiling is one
    /// atomic across every worker ([`workers_from_env`]'s doc says so in as many
    /// words: *"it is not N base budgets either"*), so four workers on the same
    /// pack hold what one budget allows plus what the walk structurally cannot
    /// drop — and nowhere near the four budgets a per-thread ceiling would give
    /// them.
    ///
    /// # 🔴 The two defects this replaces, both measured 2026-09-08
    ///
    /// It read `corpora(4)`, i.e. **whatever `.pack` files sat under
    /// `/home/rickard/git` in `read_dir` order**, and asserted
    /// `peak <= budget + biggest` with
    ///
    /// ```text
    /// let biggest = w.entries.iter().map(|e| e.uncompressed_size).max()
    /// ```
    ///
    /// ```text
    /// /home/rickard/git/Njord/.git/objects/pack/pack-7edf01cd….pack:
    ///   arm 1 held 267014 bytes against a 65536 budget and a 176423-byte largest object
    /// ```
    ///
    /// * **`biggest` was not the largest base.** `PackEntry::uncompressed_size`
    ///   is the size field of the *pack entry*, and for an `OFS_DELTA` that is
    ///   the length of the **delta stream**, not of the object it reconstructs.
    ///   The peak is a sum of *resolved base payloads*, so the old assertion
    ///   compared a peak in one unit against a maximum in another and was
    ///   simply not about the same bytes. The sibling guard
    ///   [`a_bounded_base_set_costs_re_inflations_not_rows`] already had this
    ///   right: it takes the maximum over the **resolved rows** whose offset is
    ///   used as a base, and that is what this one takes now.
    /// * **One base per worker, not one per pack.** `enforce_budget` never
    ///   drops a worker's *deepest* frame — it is the base the very next child
    ///   reads, and dropping it would re-inflate it on the following line — so
    ///   the floor under the ceiling is one held base **per walk**, and there
    ///   are `workers` walks. `budget + 1 × largest` was the serial arm's bound
    ///   applied to a four-worker arm. The bound that is actually promised is
    ///   `budget + workers × largest`: the shared ceiling, plus at most one
    ///   undroppable base per worker (which also absorbs the only race there
    ///   is — `live_path` is a relaxed atomic, so the peak one worker records
    ///   may include another worker's push that has not reached its own
    ///   `enforce_budget` yet).
    ///
    /// Neither correction weakens the guard, because the guard's *point* is the
    /// last assertion: `budget + workers × largest` is far below `workers ×
    /// budget`, which is what a per-thread ceiling would have allowed. The
    /// external corpus is gone with them — a test that needs another checkout
    /// on the same disk is not a test, and the pack is built here instead, sized
    /// so the ceiling demonstrably bites (`evictions > 0`, and the unbounded
    /// pass holds more than the bounded one).
    #[test]
    fn four_workers_hold_no_more_bases_than_the_one_budget_allows() {
        const ROOTS: usize = 4;
        const DEPTH: u32 = 8;
        const OBJECT: usize = 4 * 1024;
        // 4 roots × (2^8 − 1) = 1020 objects of 4 KiB. One walk holds at most
        // the seven bases above a leaf, so it wants 28 KiB and four walks want
        // 112 KiB — while the budget is 20 KiB: more than `workers × largest`
        // (16 KiB, so what binds is the ceiling and not the floor the walk
        // cannot drop) and less than even ONE walk wants (so it binds on the
        // serial arm too, and that arm is not a free pass).
        const BUDGET: u64 = 20 * 1024;
        let pack = base_ceiling_pack(ROOTS, DEPTH, OBJECT);
        let w = walk(&pack, 20).unwrap();

        // Which offsets are used as a base, so "the largest base" is a maximum
        // over the objects the ceiling actually holds — resolved sizes, off the
        // rows, not pack-entry size fields.
        let mut is_base: std::collections::HashSet<u64> = std::collections::HashSet::new();
        for e in &w.entries {
            if let DeltaBase::Offset(o) = e.delta_base {
                is_base.insert(o);
            }
        }

        let mut four_worker_peak = 0u64;
        for workers in [1usize, 4] {
            // The unbounded pass **at the same worker count**, because that is
            // the only thing the bounded one is comparable with: N walks hold N
            // paths whether or not there is a ceiling, so a one-worker baseline
            // would make the four-worker arm look like a leak.
            let free_limits = ResolveLimits { workers, ..ResolveLimits::none() };
            let (free, free_report, _) = stream(&pack, free_limits);
            assert_eq!(free_report.evictions, 0, "{workers} workers: the unbounded pass evicted");
            let largest = free
                .iter()
                .filter(|r| is_base.contains(&r.offset))
                .map(|r| r.uncompressed_size)
                .max()
                .expect("the pack has bases");
            assert_eq!(largest, OBJECT as u64, "every object in this pack is one size");

            let limits = ResolveLimits { workers, base_budget: BUDGET, ..ResolveLimits::none() };
            let mut rows = Vec::new();
            let report = resolve_streaming(
                &pack,
                &w,
                GitHashKind::Sha1,
                0,
                &NoBases,
                &NoSink,
                limits,
                &mut |r| {
                    rows.extend(r.drain(..));
                    Ok(())
                },
            )
            .expect("resolve");
            assert_eq!(report.workers as usize, workers, "the fan-out took the worker count");
            assert_eq!(
                rows_of(&free),
                rows_of(&rows),
                "{workers} workers: the ceiling changed the output"
            );
            assert!(
                report.evictions > 0,
                "{workers} workers: nothing was evicted, so the ceiling never bit and this \
                 guard proves nothing"
            );
            assert!(
                free_report.peak_base_bytes > report.peak_base_bytes,
                "{workers} workers: unbounded held {} and bounded {} — the ceiling did nothing",
                free_report.peak_base_bytes,
                report.peak_base_bytes
            );
            let allowed = BUDGET + workers as u64 * largest;
            assert!(
                report.peak_base_bytes <= allowed,
                "{workers} workers: held {} bytes against a {BUDGET}-byte budget plus {workers} × \
                 the {largest}-byte largest base = {allowed}",
                report.peak_base_bytes
            );
            if workers == 4 {
                four_worker_peak = report.peak_base_bytes;
                // The whole claim, stated as the number a PER-THREAD ceiling
                // would have produced: four walks each allowed the budget plus
                // their own undroppable base.
                let per_thread = workers as u64 * (BUDGET + largest);
                assert!(
                    four_worker_peak < per_thread,
                    "four workers held {four_worker_peak} bytes, which is four ceilings of \
                     {BUDGET} + {largest} = {per_thread}: the budget is per thread, not per pack"
                );
            }
            eprintln!(
                "{workers} worker(s): peak {} B (unbounded {} B), budget {BUDGET} B, largest base \
                 {largest} B, {} evictions, {} re-inflations",
                report.peak_base_bytes,
                free_report.peak_base_bytes,
                report.evictions,
                report.reinflations
            );
        }
    }
}