znippy_plugin_git/

pack_walk.rs

//! The split: one pass over a pushed packfile's entries, and nothing else.
//!
//! This is what [`crate::store`]'s `put_pack` walks before it stores a byte, and
//! it is the reason the **closure check costs nothing extra** (§13.7): the walk
//! has to visit every entry anyway to find where the next one starts, so the set
//! of entry boundaries and the set of delta bases fall out of it for free. No
//! index is consulted to answer *is this pack self-contained*.
//!
//! # What it does NOT do
//!
//! **It does not compute oids.** An entry's oid is
//! `sha1("<type> <size>\0" ‖ inflated content)`, and for a delta that content
//! only exists after the chain is resolved — that is `git index-pack`'s job, it
//! is the *indexer's* work by §13.9 ("the index is built after the ack, over a
//! channel"), and it is deliberately not on the ack path. So a [`PackEntry`]
//! carries the five facts the pack itself states — extent, type, declared
//! size and delta base — and no more.
//!
//! # Why the bytes are inflated but the output is thrown away
//!
//! A pack entry has no length field. The only way to find entry *n+1* is to run
//! the zlib stream of entry *n* to its end and ask the decompressor how many
//! **input** bytes it consumed. So the walk pays one inflate over the pack — but
//! it never materialises an object: the output goes into one reusable
//! [`SCRATCH`]-sized buffer and is discarded, so peak memory is the scratch
//! buffer and not the repository. `total_out` is still checked against the
//! declared size, because a stream that inflates to a different length than its
//! header claims is a corrupt pack and the honest answer is an error.
//!
//! # Whose grammar is this
//!
//! Ours, and §18 is the reason it is allowed to be: the plan records the choice
//! between keeping gix as a grammar library and writing the two parsers
//! ourselves as **open**, and it prescribes exactly how to settle it — "write the
//! two parsers, and gate them behind a test that runs both ours and gix's over a
//! real corpus and requires byte-identical output on every entry". That gate is
//! [`tests::ours_and_gix_agree_on_every_entry_of_every_pack`], which drives
//! `gix_pack::data::input::BytesToEntriesIter` (a **dev**-dependency, so no gix
//! crate enters a shipped archiver) over the same bytes and requires the five
//! facts to match entry for entry. Writing the parser is therefore executing the
//! plan's decision procedure, not pre-empting its decision: if the gate ever
//! fails, gix is the arbiter and this module is wrong.
//!
//! The one dependency it adds is `flate2` on its pure-Rust `zlib-rs` backend —
//! the same crate and the same backend `ldeflate` already pulls in
//! non-optionally through `znippy-common`, so the build graph is unchanged: no
//! C, no cmake, no build-script network, and `--no-default-features` still
//! builds in seconds.

use anyhow::{anyhow, bail, Context as _, Result};
use flate2::{Decompress, FlushDecompress, Status};

use crate::index_layout::ObjType;
use crate::object::GitHashKind;

/// Bytes of inflated output the walk keeps around at once. The output is
/// discarded, so this bounds the walk's memory over any pack of any size.
const SCRATCH: usize = 64 * 1024;

/// A pack header is `PACK`, a version and an object count.
const HEADER_LEN: usize = 12;

/// Where a delta entry's base is.
///
/// **The stored form is an OFFSET, never an ordinal** (§13, decided): an ordinal
/// indexes the derived objects table, that table is rebuilt whenever the
/// projection is rebuilt, and a rebuild re-derives every ordinal as the new
/// oid-lexicographic rank. An ordinal written down before a rebuild therefore
/// points at a different row afterwards — silently. An offset addresses the
/// bytes, which append-only storage never moves.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DeltaBase {
    /// A whole object: no base.
    None,
    /// `OFS_DELTA` — the base is another entry, at this **absolute** offset.
    /// Absolute in whatever coordinate space the walk was rebased into: within
    /// the pack after [`walk`], within the archive after [`PackWalk::rebased`].
    Offset(u64),
    /// `REF_DELTA` — the base is named by oid and is usually *outside* the pack
    /// (that is what a thin pack is). Resolving it is the one part of the check
    /// that reads `objects.oid`, exactly as §13's table says receive-pack does.
    Ref(Vec<u8>),
}

impl DeltaBase {
    /// The offset form for the `objects.delta_base` column.
    ///
    /// `0` means *no offset base* and is a safe sentinel rather than a lie:
    /// archive offset 0 is the first pack's `PACK` magic, so no object entry can
    /// ever legitimately start there. A `Ref` base has no offset until the
    /// indexer resolves its oid, and reports `0` for the same reason.
    pub fn as_offset(&self) -> u64 {
        match self {
            DeltaBase::Offset(o) => *o,
            DeltaBase::None | DeltaBase::Ref(_) => 0,
        }
    }
}

/// One entry, as the pack itself states it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PackEntry {
    /// Start of the entry — its type/size header, not its zlib stream.
    pub offset: u64,
    /// Header **plus** compressed stream. `offset + len` is where the next entry
    /// starts, which is what makes this the byte extent to store verbatim.
    pub len: u64,
    pub obj_type: ObjType,
    /// The size the entry's header declares, and what its zlib stream really
    /// inflated to — the walk checks the two agree.
    ///
    /// For `OfsDelta` / `RefDelta` this is the size of the **delta instruction
    /// stream**, not of the object the chain resolves to. The resolved size is
    /// unknowable without applying the chain and is the indexer's output; the
    /// type column is what stops a caller mistaking one for the other.
    pub uncompressed_size: u64,
    pub delta_base: DeltaBase,
}

/// What one pass over a pack found.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PackWalk {
    /// `2` or `3`.
    pub version: u32,
    /// Entries in pack order — which is also ascending offset order.
    pub entries: Vec<PackEntry>,
    /// The pack's own trailing checksum, as stored. Not verified here: this walk
    /// reports what the bytes say, and the checksum of *what was stored* is
    /// [`crate::indexer`]'s row.
    pub trailer: Vec<u8>,
}

/// What the closure check found. **Derived from the walk alone** — no index, no
/// disk, no oid resolution.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct Closure {
    /// `OFS_DELTA` bases that do not land on an entry boundary inside this pack.
    /// A non-empty list is a corrupt pack, not a thin one.
    pub broken_offsets: Vec<u64>,
    /// `REF_DELTA` base oids. Each has to exist *somewhere* — in this pack under
    /// an oid the walk cannot compute, or already in the store. Only these need
    /// `objects.oid`, and there are usually very few.
    pub external_refs: Vec<Vec<u8>>,
}

impl Closure {
    /// Nothing to ask anybody about: every delta base is an offset inside this
    /// pack.
    pub fn is_self_contained(&self) -> bool {
        self.broken_offsets.is_empty() && self.external_refs.is_empty()
    }
}

impl PackWalk {
    /// The same walk with every offset moved into the archive's coordinate
    /// space, which is what the `objects` table stores.
    ///
    /// A delta base moves with it — that is the whole reason it is an offset and
    /// not an ordinal: the shift is arithmetic on a known quantity, with no
    /// table to consult and nothing to keep in step.
    pub fn rebased(mut self, archive_offset: u64) -> Self {
        for e in &mut self.entries {
            e.offset += archive_offset;
            if let DeltaBase::Offset(o) = &mut e.delta_base {
                *o += archive_offset;
            }
        }
        self
    }

    /// The closure check, out of the walk we already did.
    pub fn closure(&self) -> Closure {
        let boundaries: std::collections::HashSet<u64> =
            self.entries.iter().map(|e| e.offset).collect();
        let mut c = Closure::default();
        for e in &self.entries {
            match &e.delta_base {
                DeltaBase::None => {}
                DeltaBase::Offset(o) => {
                    if !boundaries.contains(o) {
                        c.broken_offsets.push(*o);
                    }
                }
                DeltaBase::Ref(oid) => c.external_refs.push(oid.clone()),
            }
        }
        c
    }

    /// Total inflated bytes the entries declare. Not the pack's own length.
    pub fn declared_bytes(&self) -> u64 {
        self.entries.iter().map(|e| e.uncompressed_size).sum()
    }
}

/// Walk a pushed pack's entries.
///
/// `oid_len` is 20 for sha1 and 32 for sha256 — a `REF_DELTA`'s base oid is raw
/// bytes with no length prefix, so the width has to be known from outside the
/// pack. That is git's own situation.
///
/// **P-4: a malformed or hostile pack returns `Err`, never a panic and never a
/// half-truth.** Every arithmetic step is checked against the buffer's end.
pub fn walk(pack: &[u8], oid_len: usize) -> Result<PackWalk> {
    if oid_len != 20 && oid_len != 32 {
        bail!("oid width {oid_len} is neither sha1 (20) nor sha256 (32)");
    }
    if pack.len() < HEADER_LEN + oid_len {
        bail!(
            "a pack is at least {} bytes (header + trailer), this one is {}",
            HEADER_LEN + oid_len,
            pack.len()
        );
    }
    if &pack[0..4] != b"PACK" {
        bail!("not a packfile: it does not start with `PACK`");
    }
    let version = u32::from_be_bytes([pack[4], pack[5], pack[6], pack[7]]);
    if version != 2 && version != 3 {
        bail!("pack version {version} is not 2 or 3");
    }
    let count = u32::from_be_bytes([pack[8], pack[9], pack[10], pack[11]]) as usize;

    let body_end = pack.len() - oid_len;
    let mut pos = HEADER_LEN;
    let mut entries = Vec::with_capacity(count);
    let mut scratch = vec![0u8; SCRATCH];

    for i in 0..count {
        if pos >= body_end {
            bail!(
                "the pack header claims {count} objects but the bytes ran out after {i} — {} of \
                 {} bytes consumed",
                pos,
                pack.len()
            );
        }
        let start = pos;
        let (obj_type, size, n) = type_and_size(&pack[pos..body_end])
            .map_err(|e| anyhow!("entry {i} at offset {start}: {e}"))?;
        pos += n;

        let delta_base = match obj_type {
            ObjType::OfsDelta => {
                let (distance, n) = ofs_distance(&pack[pos..body_end])
                    .map_err(|e| anyhow!("entry {i} at offset {start}: {e}"))?;
                pos += n;
                let start_u64 = start as u64;
                if distance == 0 || distance > start_u64 {
                    bail!(
                        "entry {i} at offset {start} is an ofs-delta whose base is {distance} \
                         bytes back, which is outside the pack"
                    );
                }
                DeltaBase::Offset(start_u64 - distance)
            }
            ObjType::RefDelta => {
                if pos + oid_len > body_end {
                    bail!("entry {i} at offset {start}: a ref-delta base oid runs off the pack");
                }
                let oid = pack[pos..pos + oid_len].to_vec();
                pos += oid_len;
                DeltaBase::Ref(oid)
            }
            _ => DeltaBase::None,
        };

        let consumed = inflate_and_discard(&pack[pos..body_end], size, &mut scratch)
            .map_err(|e| anyhow!("entry {i} at offset {start}: {e}"))?;
        pos += consumed;

        entries.push(PackEntry {
            offset: start as u64,
            len: (pos - start) as u64,
            obj_type,
            uncompressed_size: size,
            delta_base,
        });
    }

    if pos != body_end {
        bail!(
            "the pack's {count} entries end at {pos} but its trailer starts at {body_end} — \
             {} bytes are unaccounted for",
            body_end - pos.min(body_end)
        );
    }

    Ok(PackWalk {
        version,
        entries,
        trailer: pack[body_end..].to_vec(),
    })
}

/// The type/size varint. `(type, uncompressed size, bytes consumed)`.
///
/// Byte 0 is `[continue:1][type:3][size low nibble:4]`; each continuation byte
/// adds 7 more size bits, least significant group first.
fn type_and_size(b: &[u8]) -> Result<(ObjType, u64, usize)> {
    let first = *b.first().ok_or_else(|| anyhow!("no type/size header"))?;
    let code = (first >> 4) & 0b111;
    let obj_type = ObjType::from_code(code).ok_or_else(|| {
        anyhow!("object type code {code} is not one git writes — refusing to guess it")
    })?;
    let mut size = u64::from(first & 0x0f);
    let mut shift = 4u32;
    let mut i = 1usize;
    let mut cont = first & 0x80 != 0;
    while cont {
        let byte = *b
            .get(i)
            .ok_or_else(|| anyhow!("the type/size varint runs off the pack"))?;
        if shift >= 64 {
            bail!("the type/size varint is longer than a u64 can hold");
        }
        size |= u64::from(byte & 0x7f) << shift;
        shift += 7;
        cont = byte & 0x80 != 0;
        i += 1;
    }
    Ok((obj_type, size, i))
}

/// The `OFS_DELTA` backwards distance. Git's own encoding, which is **not** the
/// same varint as above: each continuation adds one before shifting, so the
/// encoding has no redundant representations.
fn ofs_distance(b: &[u8]) -> Result<(u64, usize)> {
    let mut i = 0usize;
    let mut byte = *b
        .first()
        .ok_or_else(|| anyhow!("no ofs-delta distance varint"))?;
    i += 1;
    let mut d = u64::from(byte & 0x7f);
    while byte & 0x80 != 0 {
        byte = *b
            .get(i)
            .ok_or_else(|| anyhow!("the ofs-delta distance varint runs off the pack"))?;
        i += 1;
        d = d
            .checked_add(1)
            .and_then(|d| d.checked_shl(7))
            .ok_or_else(|| anyhow!("the ofs-delta distance overflows a u64"))?
            | u64::from(byte & 0x7f);
    }
    Ok((d, i))
}

/// Run one zlib stream to its end, throwing the output away, and report how many
/// **input** bytes it took. Checks the inflated length against `declared`.
fn inflate_and_discard(input: &[u8], declared: u64, scratch: &mut [u8]) -> Result<usize> {
    let mut d = Decompress::new(true);
    loop {
        let before_in = d.total_in();
        let before_out = d.total_out();
        let status = d
            .decompress(&input[before_in as usize..], scratch, FlushDecompress::None)
            .map_err(|e| anyhow!("zlib: {e}"))?;
        match status {
            Status::StreamEnd => break,
            Status::Ok | Status::BufError => {
                // No progress on either side and not at the end: the stream is
                // truncated. Without this the loop would spin forever on a
                // hostile pack.
                if d.total_in() == before_in && d.total_out() == before_out {
                    bail!("the zlib stream is truncated after {} bytes", d.total_in());
                }
            }
        }
    }
    if d.total_out() != declared {
        bail!(
            "the entry header declares {declared} bytes but its stream inflates to {}",
            d.total_out()
        );
    }
    Ok(d.total_in() as usize)
}

#[cfg(test)]
mod tests {
    use super::*;
    use flate2::{write::ZlibEncoder, Compression};
    use std::io::Write;

    fn deflate(bytes: &[u8]) -> Vec<u8> {
        let mut e = ZlibEncoder::new(Vec::new(), Compression::default());
        e.write_all(bytes).unwrap();
        e.finish().unwrap()
    }

    /// The type/size header git would write.
    fn header(code: u8, mut size: u64) -> Vec<u8> {
        let mut out = vec![(code << 4) | (size as u8 & 0x0f)];
        size >>= 4;
        while size > 0 {
            let last = out.len() - 1;
            out[last] |= 0x80;
            out.push((size & 0x7f) as u8);
            size >>= 7;
        }
        out
    }

    /// git's backwards-distance encoding.
    fn ofs(mut d: u64) -> Vec<u8> {
        let mut out = vec![(d & 0x7f) as u8];
        d >>= 7;
        while d > 0 {
            d -= 1;
            out.insert(0, 0x80 | (d & 0x7f) as u8);
            d >>= 7;
        }
        out
    }

    /// A pack of three entries: a blob, a second blob, and an ofs-delta whose
    /// base is the first. Returns `(bytes, expected entry offsets)`.
    fn three_entry_pack() -> (Vec<u8>, Vec<u64>) {
        let a = b"the quick brown fox jumps over the lazy dog".to_vec();
        let b = vec![b'x'; 300];
        // A delta stream's *content* is never parsed by the walk, so any bytes
        // will do — but the declared size must be its real inflated length,
        // because the walk checks that.
        let delta = b"\x2b\x2b\x90\x01\x00".to_vec();

        let mut pack = b"PACK".to_vec();
        pack.extend_from_slice(&2u32.to_be_bytes());
        pack.extend_from_slice(&3u32.to_be_bytes());

        let mut offsets = Vec::new();
        offsets.push(pack.len() as u64);
        pack.extend_from_slice(&header(3, a.len() as u64));
        pack.extend_from_slice(&deflate(&a));

        offsets.push(pack.len() as u64);
        pack.extend_from_slice(&header(3, b.len() as u64));
        pack.extend_from_slice(&deflate(&b));

        let third = pack.len() as u64;
        offsets.push(third);
        pack.extend_from_slice(&header(6, delta.len() as u64));
        pack.extend_from_slice(&ofs(third - offsets[0]));
        pack.extend_from_slice(&deflate(&delta));

        pack.extend_from_slice(&[0u8; 20]); // trailer
        (pack, offsets)
    }

    /// A pack with one `REF_DELTA` whose base is not in the pack — a thin pack.
    fn thin_pack(base_oid: &[u8]) -> Vec<u8> {
        let delta = b"\x0a\x0a\x91\x00\x0a".to_vec();
        let mut pack = b"PACK".to_vec();
        pack.extend_from_slice(&2u32.to_be_bytes());
        pack.extend_from_slice(&1u32.to_be_bytes());
        pack.extend_from_slice(&header(7, delta.len() as u64));
        pack.extend_from_slice(base_oid);
        pack.extend_from_slice(&deflate(&delta));
        pack.extend_from_slice(&[0u8; 20]);
        pack
    }

    /// The walk's whole output, asserted as **applied bytes**: every entry's
    /// offset is where the previous one ended, every `len` covers header plus
    /// stream, and `offset + len` of the last entry is exactly where the trailer
    /// starts. A walk that got any length wrong cannot satisfy all three.
    ///
    /// Seen RED by changing `pos += consumed` to `pos += consumed + 1` in
    /// [`walk`]: "a well-formed pack walks: entry 1 at offset 66: the entry
    /// header declares 2 bytes but its stream inflates to 300" — one byte of
    /// desync and the *next* entry's header is read out of the middle of a
    /// deflate stream, which is why nothing downstream has to trust the length.
    #[test]
    fn every_entry_boundary_is_where_the_bytes_say_it_is() {
        let (pack, expected) = three_entry_pack();
        let w = walk(&pack, 20).expect("a well-formed pack walks");
        assert_eq!(w.version, 2);
        assert_eq!(w.entries.len(), 3);

        let got: Vec<u64> = w.entries.iter().map(|e| e.offset).collect();
        assert_eq!(got, expected, "entry offsets");

        // Boundaries chain, and the last one ends at the trailer.
        for (i, e) in w.entries.iter().enumerate() {
            let next = w
                .entries
                .get(i + 1)
                .map(|n| n.offset)
                .unwrap_or((pack.len() - 20) as u64);
            assert_eq!(
                e.offset + e.len,
                next,
                "entry {i} claims to end at {} but the next starts at {next}",
                e.offset + e.len
            );
        }

        assert_eq!(w.entries[0].obj_type, ObjType::Blob);
        assert_eq!(w.entries[0].uncompressed_size, 43);
        assert_eq!(w.entries[1].uncompressed_size, 300);
        assert_eq!(w.entries[2].obj_type, ObjType::OfsDelta);
        assert_eq!(
            w.entries[2].delta_base,
            DeltaBase::Offset(expected[0]),
            "the ofs-delta base must resolve to the first entry's offset"
        );
        assert_eq!(w.trailer.len(), 20);
    }

    /// The closure check, and that it is answered without an index: a
    /// self-contained pack asks nobody anything, a thin one names exactly the
    /// oid it needs, and a corrupt base offset is reported as corrupt rather
    /// than as external.
    ///
    /// Seen RED by making `closure()` insert `e.offset + 1` into `boundaries`:
    /// "a pack whose only delta is an ofs-delta into itself needs nobody:
    /// Closure { broken_offsets: [12], external_refs: [] }".
    #[test]
    fn the_closure_check_falls_out_of_the_walk_and_consults_nothing() {
        let (pack, offsets) = three_entry_pack();
        let c = walk(&pack, 20).unwrap().closure();
        assert!(
            c.is_self_contained(),
            "a pack whose only delta is an ofs-delta into itself needs nobody: {c:?}"
        );
        assert!(c.external_refs.is_empty());

        let base = vec![0xab; 20];
        let c = walk(&thin_pack(&base), 20).unwrap().closure();
        assert!(!c.is_self_contained(), "a thin pack is not self-contained");
        assert_eq!(c.external_refs, vec![base], "the one oid to ask about");
        assert!(c.broken_offsets.is_empty(), "a thin pack is not corrupt");

        // A base offset that lands mid-entry is corruption, and is named.
        let mut w = walk(&pack, 20).unwrap();
        w.entries[2].delta_base = DeltaBase::Offset(offsets[0] + 1);
        let c = w.closure();
        assert_eq!(c.broken_offsets, vec![offsets[0] + 1]);
        assert!(c.external_refs.is_empty());
    }

    /// Rebasing moves the entry and its base together. This is the property that
    /// makes `delta_base` an offset rather than an ordinal: one addition, no
    /// table.
    ///
    /// Seen RED by leaving the `DeltaBase::Offset` arm out of
    /// [`PackWalk::rebased`]: `left: Offset(12)`, `right: Offset(1000012)` — the
    /// entry moved and its base did not, which is precisely the silent
    /// mis-addressing the offset form exists to make impossible.
    #[test]
    fn rebasing_moves_an_entry_and_its_base_by_the_same_amount() {
        let (pack, offsets) = three_entry_pack();
        let base = 1_000_000u64;
        let w = walk(&pack, 20).unwrap().rebased(base);
        assert_eq!(w.entries[0].offset, offsets[0] + base);
        assert_eq!(
            w.entries[2].delta_base,
            DeltaBase::Offset(offsets[0] + base)
        );
        assert!(
            w.closure().is_self_contained(),
            "a rebased pack is still self-contained — that is the point"
        );
        assert_eq!(DeltaBase::None.as_offset(), 0);
        assert_eq!(DeltaBase::Ref(vec![1; 20]).as_offset(), 0);
    }

    /// P-4, on the shapes a hostile client can actually send. Every one is an
    /// `Err` with a reason, and none of them panics or loops.
    ///
    /// Seen RED by replacing `if d.total_out() != declared` with `if false`:
    /// "lies about its size must be refused, got Ok(PackWalk { version: 2,
    /// entries: [PackEntry { offset: 12, len: 15, obj_type: Blob,
    /// uncompressed_size: 999, delta_base: None }] … })" — a walk that believed
    /// a header over the bytes.
    #[test]
    fn a_hostile_pack_is_an_error_with_a_reason_never_a_panic() {
        let (good, _) = three_entry_pack();

        let mut wrong_magic = good.clone();
        wrong_magic[0] = b'N';

        let mut wrong_version = good.clone();
        wrong_version[7] = 9;

        let mut too_many = good.clone();
        too_many[11] = 99;

        let truncated = good[..good.len() / 2].to_vec();

        // An entry whose declared size is not what its stream inflates to.
        let mut liar = b"PACK".to_vec();
        liar.extend_from_slice(&2u32.to_be_bytes());
        liar.extend_from_slice(&1u32.to_be_bytes());
        liar.extend_from_slice(&header(3, 999));
        liar.extend_from_slice(&deflate(b"short"));
        liar.extend_from_slice(&[0u8; 20]);

        // Type code 5, which git does not use.
        let mut bad_type = b"PACK".to_vec();
        bad_type.extend_from_slice(&2u32.to_be_bytes());
        bad_type.extend_from_slice(&1u32.to_be_bytes());
        bad_type.extend_from_slice(&header(5, 5));
        bad_type.extend_from_slice(&deflate(b"hello"));
        bad_type.extend_from_slice(&[0u8; 20]);

        // An ofs-delta pointing before the start of the pack.
        let mut bad_ofs = b"PACK".to_vec();
        bad_ofs.extend_from_slice(&2u32.to_be_bytes());
        bad_ofs.extend_from_slice(&1u32.to_be_bytes());
        bad_ofs.extend_from_slice(&header(6, 5));
        bad_ofs.extend_from_slice(&ofs(1_000_000));
        bad_ofs.extend_from_slice(&deflate(b"delta"));
        bad_ofs.extend_from_slice(&[0u8; 20]);

        for (what, bytes) in [
            ("wrong magic", wrong_magic),
            ("wrong version", wrong_version),
            ("more objects than bytes", too_many),
            ("truncated", truncated),
            ("lies about its size", liar),
            ("unused type code", bad_type),
            ("base before the pack", bad_ofs),
            ("empty", Vec::new()),
            ("header only", b"PACK\0\0\0\x02\0\0\0\x01".to_vec()),
        ] {
            let r = walk(&bytes, 20);
            assert!(r.is_err(), "{what} must be refused, got {r:?}");
        }

        assert!(walk(&good, 21).is_err(), "an oid width of 21 is nonsense");
    }

    /// §18's decision procedure, run as a test: **ours against gix's, entry for
    /// entry, on every pack we can find.**
    ///
    /// gix is a dev-dependency, so this costs a shipped archiver nothing. The
    /// synthetic packs always run; the real ones are whatever `.pack` files this
    /// machine happens to carry under `/home/rickard/git`, capped so the test
    /// stays a test. The count of both is printed, because a differential test
    /// that silently compared nothing is exactly the hollow guard LAW 2 is
    /// about.
    ///
    /// Seen RED by changing `shift += 7` to `shift += 8` in [`type_and_size`]:
    /// "ours walks it: entry 18 at offset 10265: the entry header declares 4133
    /// bytes but its stream inflates to 2085".
    ///
    /// **And that red proof is the argument for the real corpus.** `shift` is
    /// first *used* at 4 and only then advanced, so the broken version still
    /// decodes every two-byte varint correctly — every object under 2048 bytes.
    /// Both synthetic packs passed it. It took entry 18 of a real repository's
    /// pack to expose it, which is exactly why §18 says the gate has to run over
    /// a corpus and not over a fixture.
    #[test]
    fn ours_and_gix_agree_on_every_entry_of_every_pack() {
        let mut compared = 0usize;
        let mut packs = 0usize;

        let (synthetic, _) = three_entry_pack();
        for p in [synthetic, thin_pack(&[0x7f; 20])] {
            compared += agree(&p);
            packs += 1;
        }
        assert!(
            packs == 2 && compared >= 4,
            "the synthetic packs must compare"
        );

        let mut real = 0usize;
        for pack in real_packs(8) {
            let bytes = std::fs::read(&pack).expect("reading a real pack");
            let n = agree(&bytes);
            eprintln!("{}: {n} entries agree", pack.display());
            compared += n;
            real += 1;
        }
        eprintln!(
            "compared {compared} entries over {} packs ({real} real)",
            packs + real
        );
    }

    /// Both parsers over one pack; asserts the five facts and returns the entry
    /// count.
    fn agree(pack: &[u8]) -> usize {
        let ours = walk(pack, 20).expect("ours walks it");
        let theirs = gix_pack::data::input::BytesToEntriesIter::new_from_header(
            std::io::BufReader::new(pack),
            gix_pack::data::input::Mode::AsIs,
            gix_pack::data::input::EntryDataMode::Ignore,
            gix_hash::Kind::Sha1,
        )
        .expect("gix reads the header");

        let mut n = 0usize;
        for (i, entry) in theirs.enumerate() {
            let g = entry.expect("gix walks it");
            let o = &ours.entries[i];
            assert_eq!(o.offset, g.pack_offset, "entry {i} offset");
            assert_eq!(
                o.len,
                g.bytes_in_pack(),
                "entry {i} length: ours {} vs gix {}",
                o.len,
                g.bytes_in_pack()
            );
            assert_eq!(
                o.uncompressed_size, g.decompressed_size,
                "entry {i} decompressed size"
            );
            let (gt, gbase) = match g.header {
                gix_pack::data::entry::Header::Commit => (ObjType::Commit, DeltaBase::None),
                gix_pack::data::entry::Header::Tree => (ObjType::Tree, DeltaBase::None),
                gix_pack::data::entry::Header::Blob => (ObjType::Blob, DeltaBase::None),
                gix_pack::data::entry::Header::Tag => (ObjType::Tag, DeltaBase::None),
                gix_pack::data::entry::Header::OfsDelta { base_distance } => (
                    ObjType::OfsDelta,
                    DeltaBase::Offset(g.pack_offset - base_distance),
                ),
                gix_pack::data::entry::Header::RefDelta { base_id } => (
                    ObjType::RefDelta,
                    DeltaBase::Ref(base_id.as_slice().to_vec()),
                ),
            };
            assert_eq!(o.obj_type, gt, "entry {i} type");
            assert_eq!(o.delta_base, gbase, "entry {i} delta base");
            n += 1;
        }
        assert_eq!(
            n,
            ours.entries.len(),
            "gix found a different number of entries"
        );
        n
    }

    /// Up to `cap` real `.pack` files from this machine's own repositories.
    fn real_packs(cap: usize) -> Vec<std::path::PathBuf> {
        let mut out = Vec::new();
        let root = std::path::Path::new("/home/rickard/git");
        let Ok(repos) = std::fs::read_dir(root) 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();
                // Small ones only: this is a correctness gate, not a benchmark.
                let small = f.metadata().map(|m| m.len() < 64 << 20).unwrap_or(false);
                if small && p.extension().is_some_and(|e| e == "pack") {
                    out.push(p);
                    if out.len() >= cap {
                        return out;
                    }
                }
            }
        }
        out
    }
}

// ── the inverses, for emitting a pack ────────────────────────────────────────
//
// Reading this grammar is what the walk above does. Writing it is what emitting
// a pack for a selected object set needs, and it needs *only* this: a pack
// entry's compressed payload is position-independent, so a subset of a pack is
// the stored payloads byte for byte with their headers re-encoded. Nothing is
// re-compressed and no delta is recomputed.
//
// These are deliberately in the same file as their decoders. The two must agree
// bit for bit, and the way to keep them agreeing is to make disagreement
// obvious to whoever edits one.

/// The type/size varint, for a caller outside this module that needs to find
/// where an entry's header ends — reading the grammar rather than assuming a
/// width.
pub fn type_and_size_of(b: &[u8]) -> Result<(ObjType, u64, usize)> {
    type_and_size(b)
}

/// An `OFS_DELTA`'s **backwards distance** to its base, and how many bytes it
/// occupied. `b` starts immediately after the type/size varint.
///
/// The pair to [`type_and_size_of`], exported for the same reason: a caller
/// walking a delta chain by entry header — [`crate::serve`]'s type probe is the
/// one — must read the grammar rather than re-derive it, or the two spellings
/// drift and the second one is wrong somewhere nothing checks.
pub fn ofs_distance_of(b: &[u8]) -> Result<(u64, usize)> {
    ofs_distance(b)
}

/// Encode the type/size header — the inverse of [`type_and_size`].
///
/// Byte 0 is `[continue:1][type:3][size low nibble:4]`; each continuation byte
/// carries 7 more size bits, least significant group first.
pub fn encode_type_and_size(out: &mut Vec<u8>, obj_type: ObjType, size: u64) {
    let mut byte = (obj_type.code() << 4) | ((size & 0x0f) as u8);
    let mut rest = size >> 4;
    while rest > 0 {
        out.push(byte | 0x80);
        byte = (rest & 0x7f) as u8;
        rest >>= 7;
    }
    out.push(byte);
}

/// Encode an `OFS_DELTA` backwards distance — the inverse of [`ofs_distance`].
///
/// **Not the same varint as the one above**, and that is the whole reason this
/// is written out rather than shared: each continuation subtracts one before
/// shifting, so the encoding has no redundant representations. Getting this
/// wrong by one produces a pack `git index-pack --strict` rejects — or worse,
/// one it accepts and mis-reads, because a delta would then be applied against
/// the wrong base.
///
/// The distance is emitted most-significant group first, which is why it is
/// built backwards into a scratch buffer.
pub fn encode_ofs_distance(out: &mut Vec<u8>, distance: u64) {
    let mut buf = [0u8; 10];
    let mut i = buf.len() - 1;
    let mut d = distance;
    buf[i] = (d & 0x7f) as u8;
    while d >= 0x80 {
        d >>= 7;
        d -= 1;
        i -= 1;
        buf[i] = 0x80 | (d & 0x7f) as u8;
    }
    out.extend_from_slice(&buf[i..]);
}

#[cfg(test)]
mod encode_tests {
    use super::*;

    /// **Every encoder here is checked against the decoder beside it**, over
    /// the boundaries the varints actually turn on rather than a handful of
    /// round numbers.
    ///
    /// The sizes are the ones where a group boundary falls: the 4-bit nibble in
    /// byte 0, then every 7 bits after it. The distances are the ones where the
    /// subtract-one encoding changes length, which is where an off-by-one in
    /// either direction shows up and nowhere else.
    #[test]
    fn the_encoders_are_the_inverses_of_the_decoders() {
        let sizes = [
            0u64,
            1,
            15,
            16,
            17,
            2047,
            2048,
            2049,
            262_143,
            262_144,
            1 << 20,
            1 << 31,
            (1u64 << 57) - 1,
        ];
        for &size in &sizes {
            for t in [
                ObjType::Commit,
                ObjType::Tree,
                ObjType::Blob,
                ObjType::Tag,
                ObjType::OfsDelta,
                ObjType::RefDelta,
            ] {
                let mut buf = Vec::new();
                encode_type_and_size(&mut buf, t, size);
                let (got_t, got_size, n) =
                    type_and_size(&buf).expect("what we wrote must parse back");
                assert_eq!(got_t, t, "type round trip at size {size}");
                assert_eq!(got_size, size, "size round trip for {t:?}");
                assert_eq!(
                    n,
                    buf.len(),
                    "the decoder must consume exactly what was written"
                );
            }
        }

        // The subtract-one encoding: 127/128 and 16511/16512 are where the
        // length changes, and are exactly where an off-by-one hides.
        let distances = [
            0u64,
            1,
            126,
            127,
            128,
            129,
            16_383,
            16_511,
            16_512,
            16_513,
            1 << 20,
            1 << 40,
            u32::MAX as u64,
        ];
        for &d in &distances {
            let mut buf = Vec::new();
            encode_ofs_distance(&mut buf, d);
            let (got, n) = ofs_distance(&buf).expect("what we wrote must parse back");
            assert_eq!(got, d, "distance round trip");
            assert_eq!(
                n,
                buf.len(),
                "the decoder must consume exactly what was written"
            );
        }
    }
}

// ── emitting a subset as a packfile ──────────────────────────────────────────

/// **Where an entry's bytes are** — an address into the archive, or bytes that
/// exist nowhere else.
///
/// # Why this is not a `Vec<u8>`
///
/// It was one until 2026-08-14, and that single field is what made a clone hold
/// the whole repository. [`crate::git_ops::GitStore::emit_set`] filled it with a
/// `pread` into a fresh `Vec::with_capacity(len)` — one syscall, one allocation
/// and one kernel→user copy **per object** — and every one of those `Vec`s was
/// live at once, because the entries are all built before
/// [`emit_pack`] writes a byte. On a `linux.git` clone: ~13.8 M syscalls, ~27.6 M
/// allocations, 6.4 GB copied and held, and a peak RSS of **2314 MB** against
/// gitea's 122 MB on the identical clone
/// (`gunnar/.nornir/forge-bakeoff-benchmarks.md`, `vs_forge_clone`).
///
/// An [`Extent`](Self::Extent) is 16 bytes and addresses bytes that are already
/// in the page cache. Resolving it is [`crate::archive_map::Mapped::get`] —
/// pointer arithmetic and a bounds check — with a `pread` fallback for the one
/// case a mapping cannot answer.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum EntryBytes {
    /// The stored entry **exactly as received**, addressed in the archive's
    /// coordinate space. Header and all: `offset` is the entry's type/size
    /// varint and `len` runs to where the next entry starts.
    ///
    /// This is what a full clone is made of, end to end. Nothing copies it until
    /// [`emit_pack`] writes it to the wire.
    Extent { offset: u64, len: u64 },
    /// **The exception: bytes that are on no disk.**
    ///
    /// Three shapes reach here, and every one of them genuinely computed bytes
    /// that no extent addresses:
    ///
    ///  * a delta whose base the request does not carry, rebuilt whole or
    ///    re-deltified against a base it does carry ([`Self::recompressed`] —
    ///    `crate::delta`);
    ///  * an `OFS_DELTA` re-headed as a `REF_DELTA` for a client with no
    ///    `ofs-delta` capability, or for a thin fetch — the *payload* is a copy
    ///    but the header in front of it is new, so the concatenation is new;
    ///  * a fixture built by hand in a test.
    ///
    /// It is **zero for a whole-repository clone**, which is the measurement the
    /// extent form exists to make true rather than a promise this makes.
    Owned(Vec<u8>),
}

impl EntryBytes {
    /// How many bytes this entry contributes, without resolving it.
    ///
    /// Free for an [`Extent`](Self::Extent) — the length is the address — which
    /// is what lets a caller size or account for a pack it has not read.
    pub fn len(&self) -> u64 {
        match self {
            EntryBytes::Extent { len, .. } => *len,
            EntryBytes::Owned(v) => v.len() as u64,
        }
    }

    /// Whether this entry contributes nothing. Only a hand-built fixture can.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// The bytes, when this entry carries them itself. `None` for an extent,
    /// which has to be resolved against the archive.
    pub fn owned(&self) -> Option<&[u8]> {
        match self {
            EntryBytes::Owned(v) => Some(v),
            EntryBytes::Extent { .. } => None,
        }
    }
}

/// One entry's bytes, resolved against a buffer that spans the archive's
/// coordinate space — **the in-memory resolver**, and the one
/// [`emit_pack`]'s callers use when the archive is a `&[u8]` rather than a
/// mapping.
///
/// The mapped path is [`crate::git_ops::GitStore::resolve_emit_payloads`]; this
/// is the same two-arm decision over a slice, written once so that a test
/// fixture and a hand-built pack cannot drift from what a served clone does
/// (LAW 5). An extent that runs off the buffer is an error and never a short
/// slice, for the reason [`crate::archive_map::Mapped::get`] gives: a truncated
/// entry spliced into a pack is data the client will only reject much later.
pub fn resolve_against<'b>(e: &'b EmitEntry, archive: &'b [u8]) -> Result<&'b [u8]> {
    match &e.stored {
        EntryBytes::Owned(v) => Ok(v),
        EntryBytes::Extent { offset, len } => {
            let (a, b) = (*offset as usize, (*offset + *len) as usize);
            archive.get(a..b).ok_or_else(|| {
                anyhow!(
                    "the entry at archive offset {offset} spans ({offset}, {len}), which runs off \
                     the end of a {}-byte buffer",
                    archive.len()
                )
            })
        }
    }
}

/// One object to emit: where its stored entry is, and what it deltas against.
#[derive(Debug, Clone)]
pub struct EmitEntry {
    /// The object id, for `REF_DELTA` rewriting and for reporting.
    pub oid: Vec<u8>,
    /// The bytes this entry contributes — header and all.
    ///
    /// Normally an [`EntryBytes::Extent`]: the stored entry **exactly as
    /// received**, addressed and not copied. For the entry shapes that cannot be
    /// shipped verbatim — chiefly a delta whose base the caller is not sending —
    /// [`crate::git_ops::GitStore::emit_set`] rebuilds the bytes from the
    /// resolved object, hands them over as [`EntryBytes::Owned`], and says so in
    /// [`Self::recompressed`].
    pub stored: EntryBytes,
    /// The entry type **of `stored`**, so a copied delta is
    /// `OfsDelta`/`RefDelta` and a rebuilt one is the resolved type.
    pub obj_type: ObjType,
    /// Post-resolution size, which is what the entry header carries.
    pub uncompressed_size: u64,
    /// The base's archive offset, `0` for none.
    pub delta_base: u64,
    /// This entry's own archive offset — the key other entries name it by.
    pub offset: u64,
    /// **`stored` was rebuilt rather than copied**, so its payload was inflated
    /// and re-deflated.
    ///
    /// Carried on the entry rather than inferred at emission because nothing
    /// downstream can tell one zlib stream from another: a re-deflate and a copy
    /// produce packs that both pass `git index-pack --strict` and differ only in
    /// the CPU they cost. This flag is what makes [`EmitReport::recompressed`] a
    /// count of what happened instead of a hopeful zero.
    pub recompressed: bool,
    /// **`stored` is a delta this server COMPUTED**, against a base the request
    /// does carry — rather than the whole object.
    ///
    /// A strict refinement of [`Self::recompressed`], never set without it: such
    /// an entry really was inflated and re-deflated, so it is not `copied` and
    /// must not be counted as one. What it adds is *which* rebuild happened,
    /// because the two differ by ~4× on the wire and the receipt is the only
    /// place that difference is visible — a whole rebuild and a computed delta
    /// both pass `index-pack --strict` and `fsck`.
    ///
    /// Zero for a full clone, for the same reason `recompressed` is: a
    /// whole-repository request contains every base, so nothing is rebuilt at
    /// all. See [`crate::delta`].
    pub deltified: bool,
}

/// Order `entries` so that every delta follows the base it names.
///
/// # Why a topological order and not the input order
///
/// `OFS_DELTA` names its base by **backwards** distance. A base that has not
/// been written yet has no distance to name, so an order that puts a delta first
/// is not merely inefficient — it cannot be encoded at all.
///
/// The edges are already data: `delta_base` is an absolute archive offset, and
/// `offset` is what an entry is named by. So this is a sort over facts the index
/// holds, not a graph anyone has to build.
///
/// # An entry whose base is not in the set
///
/// Left where it is, and reported. The caller decides: add the base (right for a
/// clone, where the base is reachable anyway) or rewrite the entry as a
/// `REF_DELTA` naming the base by oid (right for a thin fetch, where the client
/// consented and already holds it). Deciding here would make one of those two
/// impossible.
///
/// Returns the ordered entries and the offsets that were named but absent.
pub fn topological_order(entries: Vec<EmitEntry>) -> (Vec<EmitEntry>, Vec<u64>) {
    use std::collections::{HashMap, HashSet};

    let present: HashMap<u64, usize> = entries
        .iter()
        .enumerate()
        .map(|(i, e)| (e.offset, i))
        .collect();

    let mut missing = Vec::new();
    let mut done: HashSet<usize> = HashSet::new();
    // The ORDER, not the entries: the traversal used to push
    // `entries[i].clone()`, and an `EmitEntry` owns its stored bytes — so
    // ordering a pack cloned every payload in it, a full second copy of the
    // emission. Profiled on oden 2026-08-12 as part of the ~44 % of serve CPU
    // spent copying/zeroing at 32 concurrent clones. The entries are moved out
    // by slot once the order is known; not one payload byte is copied here.
    let mut order: Vec<usize> = Vec::with_capacity(entries.len());

    // Iterative rather than recursive: a delta chain is allowed to be 50 deep by
    // default and nothing forbids a pathological one, so the depth belongs on
    // the heap where it cannot take the thread's stack with it.
    for start in 0..entries.len() {
        if done.contains(&start) {
            continue;
        }
        let mut stack = vec![start];
        let mut on_path: HashSet<usize> = HashSet::new();
        while let Some(&i) = stack.last() {
            if done.contains(&i) {
                stack.pop();
                continue;
            }
            let base = entries[i].delta_base;
            let pending = if base == 0 {
                None
            } else {
                match present.get(&base) {
                    Some(&b) if !done.contains(&b) => {
                        // A cycle is impossible in a well-formed pack — a base
                        // always precedes its delta, so the offsets strictly
                        // decrease — but a corrupt one could claim otherwise,
                        // and looping for ever is a worse answer than emitting
                        // in an order the encoder will then refuse.
                        if on_path.contains(&b) {
                            None
                        } else {
                            Some(b)
                        }
                    }
                    Some(_) => None,
                    None => {
                        missing.push(base);
                        None
                    }
                }
            };
            match pending {
                Some(b) => {
                    on_path.insert(i);
                    stack.push(b);
                }
                None => {
                    stack.pop();
                    on_path.remove(&i);
                    done.insert(i);
                    order.push(i);
                }
            }
        }
    }

    missing.sort_unstable();
    missing.dedup();
    // Materialise by MOVING each entry into its ordered place. Every index is
    // in `order` exactly once (`done` gates the push), so every slot is taken
    // exactly once.
    let mut slots: Vec<Option<EmitEntry>> = entries.into_iter().map(Some).collect();
    let out: Vec<EmitEntry> = order
        .into_iter()
        .map(|i| {
            slots[i]
                .take()
                .expect("topological_order emitted an index twice")
        })
        .collect();
    (out, missing)
}

#[cfg(test)]
mod order_tests {
    use super::*;

    fn e(offset: u64, delta_base: u64) -> EmitEntry {
        EmitEntry {
            oid: vec![offset as u8],
            stored: EntryBytes::Owned(Vec::new()),
            obj_type: if delta_base == 0 {
                ObjType::Blob
            } else {
                ObjType::OfsDelta
            },
            uncompressed_size: 0,
            delta_base,
            offset,
            recompressed: false,
            deltified: false,
        }
    }

    /// **Every base precedes every delta that names it**, asserted as a
    /// position comparison rather than by eyeballing the sequence.
    ///
    /// The input is deliberately worst-case: a chain handed in exactly
    /// backwards, so an implementation that returned its input — or that sorted
    /// by offset, which looks right and is not — fails. Sorting by offset
    /// happens to work here only because the chain is linear, so a fork is in
    /// the fixture too.
    #[test]
    fn a_base_always_precedes_the_delta_that_names_it() {
        // 100 <- 200 <- 300, plus 400 forking off 200, handed in reverse.
        let entries = vec![e(400, 200), e(300, 200), e(200, 100), e(100, 0)];
        let (ordered, missing) = topological_order(entries);

        assert!(missing.is_empty(), "nothing was absent: {missing:?}");
        assert_eq!(ordered.len(), 4, "every entry must be emitted exactly once");

        let at = |off: u64| ordered.iter().position(|x| x.offset == off).unwrap();
        for (delta, base) in [(200u64, 100u64), (300, 200), (400, 200)] {
            assert!(
                at(base) < at(delta),
                "base {base} at {} must precede delta {delta} at {}",
                at(base),
                at(delta)
            );
        }
    }

    /// A base outside the set is **reported, not invented**.
    ///
    /// The caller has two correct answers — add the base, or rewrite as
    /// `REF_DELTA` — and both need to know which offset was missing. Silently
    /// dropping the entry would produce a pack whose closure does not hold, and
    /// `index-pack --strict` would be the first thing to say so, a long way from
    /// here.
    #[test]
    fn a_base_outside_the_set_is_reported_rather_than_dropped() {
        let (ordered, missing) = topological_order(vec![e(300, 999), e(100, 0)]);
        assert_eq!(missing, vec![999], "the absent base must be named");
        assert_eq!(ordered.len(), 2, "the entry stays; the caller decides");
    }

    /// A cycle cannot happen in a well-formed pack — offsets strictly decrease
    /// along a chain — but a corrupt one may claim it, and looping for ever is
    /// the worst possible answer.
    #[test]
    fn a_cycle_terminates_instead_of_hanging() {
        let (ordered, _) = topological_order(vec![e(100, 200), e(200, 100)]);
        assert_eq!(ordered.len(), 2, "both entries must still be emitted");
    }
}

/// What emitting produced, in facts a caller can assert on.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct EmitReport {
    /// Entries written.
    pub written: u32,
    /// Entries whose stored payload was copied unchanged. It is counted rather
    /// than assumed because "correct but slow" is the failure `index-pack
    /// --strict` and `fsck` both pass.
    pub copied: u32,
    /// Entries whose payload was **inflated and re-deflated** because the caller
    /// could not ship the stored bytes — a delta whose base is outside the
    /// request. `copied + recompressed == written`, always.
    ///
    /// Zero for a whole-repository clone, which is why the copy claim survives:
    /// a full clone's selection contains every base, so no entry ever needs
    /// rebuilding. It is non-zero exactly at the boundary a narrowed request
    /// cuts through, and that is the number worth watching.
    pub recompressed: u32,
    /// Of the [`Self::recompressed`], how many went out as a **computed delta**
    /// against a base the pack carries rather than as a whole object.
    /// `deltified <= recompressed`, always.
    ///
    /// The two rebuilds cost the same receipt and very different bytes, so
    /// without this column a boundary-heavy request looks identical whether the
    /// re-delta ran or not. Measured on `h2h-linear-sha1-2048c-1024f-16k`'s
    /// narrowed clone: **961 recompressed, of which 859 deltified**, and the
    /// pack fell from 11 613 666 bytes to 6 424 726 for the identical 31 805
    /// objects.
    pub deltified: u32,
    /// Entries whose `OFS_DELTA` distance had to be re-encoded because the gap
    /// to their base changed. Zero only if the subset happened to preserve every
    /// gap, which for anything but a whole pack it will not.
    pub rebased: u32,
    /// Bytes on the wire, trailer included.
    pub bytes: u64,
}

/// Assemble ordered entries into a packfile.
///
/// # What this does and does not do
///
/// It copies. Every entry's compressed payload goes out **byte for byte** as
/// `payload_of` hands it over; nothing here inflates, deflates or computes a
/// delta. The only thing rewritten is the entry header, and only because
/// `OFS_DELTA` carries a distance that is relative to a position in the *input*
/// pack. An entry whose payload the *caller* rebuilt says so in
/// [`EmitEntry::recompressed`] and is counted apart, so the receipt names which
/// of the two happened rather than assuming.
///
/// `entries` must already be in [`topological_order`] and must be closed —
/// every `OFS_DELTA` base present. A base that is absent is an error here
/// rather than a silently dropped back-reference, because the alternative is a
/// pack whose closure does not hold and a client that discovers it.
///
/// The caller supplies `stored_of`, which **borrows** entry `i`'s whole stored
/// bytes — header included. Splitting it that way keeps this function free of
/// any opinion about where bytes live: they may be a slice of a mapping of the
/// archive, a slice of an owned buffer the caller rebuilt, or anything else that
/// outlives the call.
///
/// # Why the WHOLE entry and not the payload
///
/// It used to be `payload_of`, handing over `stored[header_len..]`, and the
/// header the caller had just stripped was then re-parsed **here** anyway — for
/// the stated size, and for a `REF_DELTA`'s base oid. Three readings of one
/// varint across two files, and the caller's `header_len` had to agree with this
/// function's `type_and_size` or a ref-delta went out with its base named twice
/// (which it once did: `git index-pack --strict` answered `inflate returned 1`).
/// One reading, in one place, is LAW 5's fix by construction.
///
/// # It streams, and it borrows — `P-018` and `P-025`
///
/// Two properties, both deliberate, both previously absent:
///
/// * **`stored_of` returns `&[u8]`, not `Vec<u8>`.** It used to return an owned
///   buffer, which is `P-025` in its exact form: `data.to_owned()`, **one heap
///   allocation per object served**, on a path whose entire claim is that it
///   copies stored bytes without touching them. It is indexed by entry rather
///   than handed an `&EmitEntry` so that the bytes may live *outside* the entry —
///   which since 2026-08-14 they do: an [`EntryBytes::Extent`] is an address, and
///   the bytes it names are a slice of the mapped archive.
/// * **The pack goes to `out` as it is built, and the trailer is hashed
///   incrementally.** It used to accumulate the whole pack in a `Vec<u8>` and
///   hash it at the end, so serving a 2 GiB clone meant holding 2 GiB. The one
///   fact the old shape got for free — the output offset an `OFS_DELTA` distance
///   is measured against — is counted here instead, which is cheaper than the
///   buffer that was carrying it.
///
/// What is emphatically **not** here is gix's pack pipeline: no counting pass
/// with a serial reduce, no `sort_by` over counts, no `BTreeMap` reorder, no
/// hashing of every byte on a consuming thread. Those are `P-018`'s serial tail,
/// and this function is the reason none of it is needed — the bytes are already
/// deflated and already delta-encoded, so emitting is a copy and an addition.
pub fn emit_pack<'p>(
    entries: &'p [EmitEntry],
    hash: GitHashKind,
    out: &mut dyn std::io::Write,
    stored_of: &dyn Fn(usize) -> Result<&'p [u8]>,
) -> Result<EmitReport> {
    use std::collections::HashMap;

    let count = u32::try_from(entries.len()).map_err(|_| {
        anyhow!(
            "a pack holds at most u32::MAX entries, was given {}",
            entries.len()
        )
    })?;

    let mut out = Trailing::new(out, hash);
    out.put(b"PACK")?;
    out.put(&2u32.to_be_bytes())?;
    out.put(&count.to_be_bytes())?;
    // One scratch buffer for entry headers, reused for every entry. A header is
    // a handful of bytes and there is one per object, so allocating it per entry
    // would be the same defect `payload_of` above just stopped committing.
    let mut hdr: Vec<u8> = Vec::with_capacity(32);

    // Where each input offset landed in the output. Built as we go, which is
    // exactly why the order has to be topological: a delta's base must already
    // be in here when the delta is written.
    let mut placed: HashMap<u64, u64> = HashMap::with_capacity(entries.len());
    let mut report = EmitReport::default();

    for (i, e) in entries.iter().enumerate() {
        let here = out.written();

        // The entry's whole stored bytes — a slice of the mapped archive for
        // everything a clone sends, a slice of a rebuilt buffer for the
        // exceptions. Resolved once and read three times below; asking for it
        // per use would be three bounds checks or three preads.
        let stored = stored_of(i)?;

        // **The size in the header is the one the ENTRY states, not the one the
        // index holds.** For a delta they are different numbers: the header
        // carries the length of the delta stream, and `uncompressed_size` is the
        // size after the chain is applied. Re-encoding a delta header with the
        // resolved size produces a stream `git index-pack --strict` calls
        // `inflate returned 1`, which is what it did. Re-reading the grammar
        // rather than trusting a neighbouring column is the same discipline
        // `header_len` follows, and for the same reason.
        let (_, stated_size, varint_len) = type_and_size(stored)?;

        match e.obj_type {
            ObjType::OfsDelta => {
                let base_at = *placed.get(&e.delta_base).ok_or_else(|| {
                    anyhow!(
                        "entry at {} deltas against archive offset {}, which is not in this pack \
                         — the set is not closed and was not ordered by `topological_order`",
                        e.offset,
                        e.delta_base
                    )
                })?;
                // Backwards distance in OUTPUT coordinates. `here` is always
                // greater, because the base was written first.
                let distance = here - base_at;
                hdr.clear();
                encode_type_and_size(&mut hdr, ObjType::OfsDelta, stated_size);
                encode_ofs_distance(&mut hdr, distance);
                out.put(&hdr)?;
                report.rebased += 1;
            }
            ObjType::RefDelta => {
                hdr.clear();
                encode_type_and_size(&mut hdr, ObjType::RefDelta, stated_size);
                // The base oid follows the header verbatim; it names an object
                // rather than a position, so a subset never invalidates it.
                let oid_len = hash.oid_len();
                // The oid sits directly after the type/size varint — NOT after
                // `header_len`, which now includes the oid itself.
                let base = stored.get(varint_len..).and_then(|r| r.get(..oid_len));
                let base = base.ok_or_else(|| {
                    anyhow!(
                        "a ref-delta entry at {} has no base oid after its header",
                        e.offset
                    )
                })?;
                hdr.extend_from_slice(base);
                out.put(&hdr)?;
            }
            t => {
                hdr.clear();
                encode_type_and_size(&mut hdr, t, stated_size);
                out.put(&hdr)?;
            }
        }

        // The payload is what follows the header the loop above just re-encoded,
        // and `header_len` is the one reading of that grammar. **This is the only
        // place a stored byte is touched** — a page fault on the mapping, a hash
        // update and a write, with no buffer in between.
        out.put(&stored[header_len(stored, hash)?..])?;
        if e.recompressed {
            report.recompressed += 1;
            if e.deltified {
                report.deltified += 1;
            }
        } else {
            report.copied += 1;
            debug_assert!(
                !e.deltified,
                "a computed delta was inflated and re-deflated to produce it; counting it as a \
                 copy would make the receipt a claim rather than a measurement"
            );
        }
        report.written += 1;
        placed.insert(e.offset, here);
    }

    // The trailer is over everything written, which is what a reader checks.
    report.bytes = out.finish()?;
    Ok(report)
}

/// `out`, plus the running pack checksum and the byte count `OFS_DELTA`
/// distances are measured against.
///
/// The two facts the old `Vec<u8>` accumulator was really being kept for. Held
/// as three fields instead, so a clone streams and nothing sizes an allocation
/// by the repository.
struct Trailing<'a> {
    inner: &'a mut dyn std::io::Write,
    digest: Digest,
    written: u64,
}

/// The pack trailer's hash, fed as the pack is written.
///
/// An enum and not a `Box<dyn Digest>`: there are exactly two, both are
/// already direct dependencies of this crate, and a vtable per `update` on the
/// one path that touches every emitted byte is not a cost this takes for two
/// variants.
enum Digest {
    Sha1(sha1::Sha1),
    Sha256(sha2::Sha256),
}

impl<'a> Trailing<'a> {
    fn new(inner: &'a mut dyn std::io::Write, hash: GitHashKind) -> Self {
        use sha1::Digest as _;
        Trailing {
            inner,
            digest: match hash {
                GitHashKind::Sha1 => Digest::Sha1(sha1::Sha1::new()),
                GitHashKind::Sha256 => Digest::Sha256(sha2::Sha256::new()),
            },
            written: 0,
        }
    }

    /// Bytes written so far — the output coordinate an `OFS_DELTA` distance is
    /// relative to.
    fn written(&self) -> u64 {
        self.written
    }

    fn put(&mut self, bytes: &[u8]) -> Result<()> {
        use sha1::Digest as _;
        match &mut self.digest {
            Digest::Sha1(d) => d.update(bytes),
            Digest::Sha256(d) => d.update(bytes),
        }
        self.inner
            .write_all(bytes)
            .context("writing an emitted pack")?;
        self.written += bytes.len() as u64;
        Ok(())
    }

    /// Append the trailer and report the total, trailer included.
    fn finish(self) -> Result<u64> {
        use sha1::Digest as _;
        let digest: Vec<u8> = match self.digest {
            Digest::Sha1(d) => d.finalize().to_vec(),
            Digest::Sha256(d) => d.finalize().to_vec(),
        };
        self.inner
            .write_all(&digest)
            .context("writing the pack trailer")?;
        self.inner.flush().context("flushing an emitted pack")?;
        Ok(self.written + digest.len() as u64)
    }
}

/// How many bytes of a stored entry are header — everything before the
/// compressed payload.
///
/// For a delta that includes the back-reference: the `OFS_DELTA` distance or the
/// `REF_DELTA` oid. This is what a caller strips to get the payload, and it is
/// derived by re-reading the grammar rather than remembered, so it cannot drift
/// from what the walk parses.
pub fn header_len(stored: &[u8], hash: GitHashKind) -> Result<usize> {
    let (t, _, n) = type_and_size(stored)?;
    Ok(match t {
        ObjType::OfsDelta => {
            let (_, d) = ofs_distance(stored.get(n..).unwrap_or(&[]))?;
            n + d
        }
        // **The base oid is part of the header, not of the payload.** It was
        // excluded here once, on the reasoning that its width is the caller's to
        // know. That made `stored[header_len..]` still contain the oid, and
        // `emit_pack` writes the oid itself — so every ref-delta went out with
        // its base named twice and `git index-pack --strict` answered
        // `inflate returned 1`. The hash kind is a parameter now, and the
        // ambiguity is gone rather than documented.
        ObjType::RefDelta => n + hash.oid_len(),
        _ => n,
    })
}

#[cfg(test)]
mod emit_tests {
    use super::*;

    /// **A pack this emits is one `git index-pack --strict` accepts.**
    ///
    /// The arbiter is stock git and nothing else. Our own parser reading back
    /// what our own writer produced proves the two agree with each other, which
    /// is exactly the circularity that lets a wrong varint through — both halves
    /// would be wrong the same way. `index-pack --strict` shares no code with
    /// this file.
    ///
    /// The corpus is a real pack off this machine, re-emitted whole. Whole
    /// rather than a subset for the first assertion, because a whole pack is the
    /// case where every delta base is present by construction, so a failure here
    /// is the encoder and cannot be the closure.
    #[test]
    fn stock_git_accepts_a_pack_we_emitted() {
        if std::process::Command::new("git")
            .arg("--version")
            .output()
            .is_err()
        {
            eprintln!("skipping: no git on PATH");
            return;
        }
        let (pack, _) = crate::store::tests::real_pack();
        let walk = walk(&pack, GitHashKind::Sha1.oid_len()).expect("the corpus pack walks");

        let entries: Vec<EmitEntry> = walk
            .entries
            .iter()
            .map(|e| EmitEntry {
                oid: Vec::new(),
                // The corpus pack is in memory here, so the extent IS the pack's
                // own offset and the resolver below slices it. That is exactly
                // the shape a store uses, with the mapping in place of `pack`.
                stored: EntryBytes::Extent {
                    offset: e.offset,
                    len: e.len,
                },
                obj_type: e.obj_type,
                uncompressed_size: e.uncompressed_size,
                delta_base: e.delta_base.as_offset(),
                offset: e.offset,
                recompressed: false,
                deltified: false,
            })
            .collect();
        let n = entries.len();
        assert!(
            n > 0,
            "the corpus pack has no entries; nothing is being tested"
        );

        let (ordered, missing) = topological_order(entries);
        assert!(
            missing.is_empty(),
            "a whole pack must be closed: {missing:?}"
        );

        let mut bytes = Vec::new();
        let report = emit_pack(&ordered, GitHashKind::Sha1, &mut bytes, &|i| {
            resolve_against(&ordered[i], &pack)
        })
        .expect("emitting");
        assert_eq!(
            report.bytes as usize,
            bytes.len(),
            "the report's byte count must be what was actually written"
        );

        assert_eq!(report.written as usize, n, "every entry must be written");
        assert_eq!(
            report.copied, report.written,
            "every payload must be COPIED"
        );

        // 🔴 Through [`crate::git_oracle`], and that is the 2026-08-11 fix here:
        // this ran `index-pack --strict` in a plain `tempfile::tempdir()`, and
        // outside a repository that command **segfaults** on any pack it would
        // have rejected — silently, with no output. The oracle now runs inside a
        // fresh bare repo and refuses to read a signal death as a verdict.
        let dir = tempfile::tempdir().expect("tempdir");
        crate::git_oracle::assert_git_accepts(
            dir.path(),
            "emitted.git",
            &bytes,
            crate::git_oracle::Strictness::Connected,
        );
    }
}