plugins/native/znippy-plugin-git/src/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> {
walk_observed(pack, oid_len, &mut |_done, _total| {})
}
/// [`walk`], **telling somebody how far it has got, entry by entry.**
///
/// # This is the walk, not a second one
///
/// There is exactly one place on this system that knows how many objects of a
/// pack have been taken in *while the taking is still happening*, and it is the
/// loop below: a pack entry carries no length, so finding the boundaries **is**
/// how the pack gets split at all, and the loop already inflates every entry to
/// find where the next one starts. Counting the entries as they go past is
/// therefore free — no extra pass, no extra inflate, not one byte decompressed
/// that was not already being decompressed. Any other way of learning the same
/// number would be a second pack decoder, which LAW 5 forbids and which
/// `gunnar-wire`'s `fetch_pack` refuses for the same reason.
///
/// `on_entry` is called **once per entry**, after that entry is accounted for,
/// with `(entries so far, the count the header declared)`. Per entry and not
/// per batch because the loop is per entry: batching here would be inventing a
/// coarseness the code does not have.
///
/// # `&mut dyn FnMut` and not a generic
///
/// [`walk`] and this are one function, and a generic parameter would
/// monomorphise the whole 70-line body a second time for the no-op closure —
/// the same machine code twice, on the push hot path, so that a call that
/// publishes nothing can skip an indirect call it makes once per object. The
/// dyn call is dwarfed by the inflate on the line above it.
pub fn walk_observed(
pack: &[u8],
oid_len: usize,
on_entry: &mut dyn FnMut(u64, u64),
) -> 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,
});
// After the push, so the number published is the number of entries that
// are actually accounted for — never `i`, which would report an entry
// as done at the moment it was started.
on_entry(entries.len() as u64, count as u64);
}
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 `~/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"
);
// 🔴 **And the generated corpus, which is what makes the red proof above
// reproducible off this box.** `shift += 8` decodes every two-byte
// varint correctly — every object under 2048 bytes — so both synthetic
// packs pass it, and the argument in this test's docs was that only a
// real repository's pack has entries big enough to expose it. That made
// the coverage a property of the machine. [`crate::pack_fixture`]'s
// blobs are 2048 bytes exactly and its trees are larger, so every entry
// in it carries a three-byte type/size varint and the same red is
// available on a fresh clone.
let corpus = crate::pack_fixture::corpus().pack.clone();
let n = agree(&corpus);
assert!(
n > 1000,
"the generated corpus compared only {n} entries"
);
compared += n;
packs += 1;
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_buf = std::path::PathBuf::from(std::env::var_os("HOME").unwrap_or_default()).join("git");
let root = root_buf.as_path();
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::corpus_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,
);
}
}