znippy-plugin-git 0.1.9

//! **The corpus these tests run on — built here, out of objects this file
//! names, instead of found on whatever machine happens to run them.**
//!
//! # 🔴 The defect this module exists for
//!
//! `store::tests::real_pack` read `~/git`, walked it in `read_dir`
//! order, and took **the first `.pack` under 8 MiB that resolved standalone to
//! more than 100 objects**. Thirty-five tests took their corpus from it. That
//! made the subject of those tests *whichever repository the filesystem
//! happened to hand back first on the developer's box*, and it drifted the
//! moment anything cloned or removed a repository beside it.
//!
//! MEASURED 2026-08-25 on this box, `cargo test -p znippy-plugin-git --lib`:
//! **197 passed, 8 failed**, and every one of the eight was a property of the
//! found pack rather than of this crate:
//!
//! ```text
//!   pack_walk::emit_tests::stock_git_accepts_a_pack_we_emitted
//!   serve::tests::an_emitted_pack_is_copied_not_recompressed_and_stock_git_accepts_it
//!   serve::tests::a_client_that_cannot_read_ofs_delta_is_served_ref_deltas_instead
//!       → "fatal: did not receive expected object 0bd02d3d…" — the found pack
//!         is not reachability-closed, so `--check-self-contained-and-connected`
//!         refuses it. Nothing was wrong with the emitter.
//!   store::emit_set_tests::a_subset_emits_exactly_the_subset_and_stock_git_accepts_it
//!   store::zero_copy_tests::a_rebuilt_delta_still_carries_its_own_bytes_and_emits_beside_extents
//!       → 199 rebuilt against 146 expected. The found pack carries REF_DELTAs
//!         (`index-pack --fix-thin` leaves them behind on any repository pushed
//!         to twice) and the test's own `boundary` count cannot see one: a
//!         ref-delta's `delta_base` column is 0 by construction.
//!   store::zero_copy_tests::a_full_clone_emits_the_identical_pack_from_extents_and_from_owned_bytes
//!       → "179 of 1219 were owned" — the same REF_DELTAs, which `emit_set`
//!         re-heads as OFS_DELTAs and must therefore own rather than address.
//!   store::tests::reachable_is_want_minus_have_over_objects
//!       → a want the store does not hold, again because the pack is not closed.
//!   store::zero_copy_tests::an_emit_set_holds_no_payload_bytes_of_the_pack_it_will_write
//!       → "the corpus emits 933789 bytes, too few to distinguish held from
//!         addressed" — the found pack was simply smaller than the one the
//!         bound was written against.
//! ```
//!
//! And with the corpus root merely **absent**, which is what a CI box and every
//! other developer's machine looks like, all thirty-five died in the fixture
//! before reaching an assertion:
//!
//! ```text
//! panicked at src/store.rs:763: called `Result::unwrap()` on an `Err` value:
//!   Os { code: 2, kind: NotFound, message: "No such file or directory" }
//! ```
//!
//! # Generated and not committed, and why that is the stronger answer
//!
//! A committed `.pack` would have been hermetic too. It would also have been
//! binary content whose shape nobody can read out of the diff, and the shape is
//! exactly what these tests turn on — how many deltas, whose base is where,
//! whether a ref-delta is in there at all. [`corpus`] states its inputs in
//! source: the file count, the history length, how much each commit changes,
//! and which entries are stored as deltas. A reader can tell what the tests are
//! standing on without a hex dump, and a fresh clone needs no LFS filter to
//! have it. (This repository carries no `.gitattributes` and no LFS
//! configuration at all — checked — so a committed pack would have landed as
//! real bytes; the point is not that LFS would have eaten it, the point is that
//! the shape would have been unreadable either way.)
//!
//! # What it deliberately is NOT
//!
//! **It is not a substitute for a real repository's delta shape.** The two
//! peak-memory integration tests (`tests/resolve_peak_memory.rs`,
//! `tests/emit_peak_memory.rs`) assert a ratio against a pack's *payload*, and
//! that ratio is a property of how a real `pack-objects` chose its bases. They
//! keep reading real packs and they already degrade to "nothing to measure"
//! when there are none. Nothing here replaces them.
//!
//! **It carries no REF_DELTA.** A pack `git clone` hands out never does; only
//! `index-pack --fix-thin` makes them. Every guard here that says "all extents"
//! or counts boundary rebuilds is stating a property of a *clone* pack, so a
//! clone pack is what the corpus is. The ref-delta paths in
//! [`crate::git_ops::GitStore::emit_set`] have their own hand-built fixtures in
//! [`crate::serve`]; what the found corpus did was reach them by accident and
//! then be counted wrong.

use crate::index_layout::ObjType;
use crate::object::{canonical, GitHashKind, GitObjectKind};
use crate::serve::resolved_type;

// ── the assembler ────────────────────────────────────────────────────────────

/// One entry of a hand-built pack.
///
/// `one_blob_pack` cannot express a graph and a pack found on disk is whatever
/// the machine had. Several guards need a pack whose **exact** shape is chosen
/// rather than found: which objects point at which, and which entry is stored
/// as a delta against which other entry.
pub(crate) enum Item {
    Whole(GitObjectKind, Vec<u8>),
    /// An `OFS_DELTA` against the item at index `base`, reconstructing `body`.
    OfsDelta { base: usize, body: Vec<u8> },
}

impl Item {
    /// The resolved body, which is what a delta against this item states as its
    /// source size.
    pub(crate) fn body(&self) -> &[u8] {
        match self {
            Item::Whole(_, b) | Item::OfsDelta { body: b, .. } => b,
        }
    }
}

pub(crate) fn deflate(bytes: &[u8]) -> Vec<u8> {
    use std::io::Write;
    let mut e = flate2::write::ZlibEncoder::new(Vec::new(), flate2::Compression::default());
    e.write_all(bytes).unwrap();
    e.finish().unwrap()
}

/// git's delta-header varint — LEB128, unlike the `OFS_DELTA` distance.
fn delta_varint(out: &mut Vec<u8>, mut n: u64) {
    loop {
        let mut b = (n & 0x7f) as u8;
        n >>= 7;
        if n > 0 {
            b |= 0x80;
        }
        out.push(b);
        if n == 0 {
            return;
        }
    }
}

/// A delta stream that rebuilds `target` by **pure insertion**.
///
/// Legal git delta encoding, and the reason it is used here rather than a
/// copy-based one: the base's *content* becomes irrelevant while its *identity*
/// stays load-bearing, so a fixture can name any base it likes and still
/// produce a target of its own choosing. `source_size` must still match the
/// base exactly — git checks it and refuses otherwise.
pub(crate) fn insert_only_delta(base_len: usize, target: &[u8]) -> Vec<u8> {
    let mut d = Vec::new();
    delta_varint(&mut d, base_len as u64);
    delta_varint(&mut d, target.len() as u64);
    for chunk in target.chunks(0x7f) {
        d.push(chunk.len() as u8);
        d.extend_from_slice(chunk);
    }
    d
}

/// Assemble `items` into a packfile, in the order given.
///
/// The trailer is the **real** sha1 over everything before it, not the zeroes
/// this used to write. It costs one hash of bytes that are already in hand, and
/// it means the fixture is a pack `git index-pack` would take directly rather
/// than one that only survives because nothing on the absorb path checks the
/// trailer.
pub(crate) fn build_pack(items: &[Item]) -> Vec<u8> {
    let mut pack = b"PACK".to_vec();
    pack.extend_from_slice(&2u32.to_be_bytes());
    pack.extend_from_slice(&(items.len() as u32).to_be_bytes());
    let mut offsets: Vec<u64> = Vec::with_capacity(items.len());
    for (i, item) in items.iter().enumerate() {
        offsets.push(pack.len() as u64);
        match item {
            Item::Whole(kind, body) => {
                crate::pack_walk::encode_type_and_size(
                    &mut pack,
                    resolved_type(*kind),
                    body.len() as u64,
                );
                pack.extend_from_slice(&deflate(body));
            }
            Item::OfsDelta { base, body } => {
                assert!(*base < i, "an OFS_DELTA names a base BEHIND it in the pack");
                let delta = insert_only_delta(items[*base].body().len(), body);
                crate::pack_walk::encode_type_and_size(
                    &mut pack,
                    ObjType::OfsDelta,
                    delta.len() as u64,
                );
                crate::pack_walk::encode_ofs_distance(&mut pack, offsets[i] - offsets[*base]);
                pack.extend_from_slice(&deflate(&delta));
            }
        }
    }
    let trailer = GitHashKind::Sha1.oid_of(&pack);
    pack.extend_from_slice(&trailer);
    pack
}

/// **A one-entry THIN pack**: a single `REF_DELTA` against `base_oid`, whose
/// delta replaces the whole object with `body`.
///
/// This is the shape a `git push` of one commit on top of the ref the server
/// just advertised sends, and therefore the shape that grows a verbatim
/// archive's delta chain one link per push (`crate::thin_storm`).
///
/// `base_size` must be the base's real inflated size — the delta grammar
/// declares it and every resolver checks it, so a made-up number fails for a
/// reason that has nothing to do with what a caller is testing.
///
/// It is here and not in a test module because two of them wanted it (LAW 5):
/// `git_ops`'s lane-Q read-window guard and `thin_storm`'s push storm.
pub(crate) fn thin_ref_delta_pack(base_oid: &[u8], base_size: u64, body: &[u8]) -> Vec<u8> {
    let delta = insert_only_delta(base_size as usize, body);
    let mut pack = b"PACK".to_vec();
    pack.extend_from_slice(&2u32.to_be_bytes());
    pack.extend_from_slice(&1u32.to_be_bytes());
    crate::pack_walk::encode_type_and_size(&mut pack, ObjType::RefDelta, delta.len() as u64);
    pack.extend_from_slice(base_oid);
    pack.extend_from_slice(&deflate(&delta));
    let trailer = GitHashKind::Sha1.oid_of(&pack);
    pack.extend_from_slice(&trailer);
    pack
}

/// A whole-object pack: every entry whole — no `OFS_DELTA`, no `REF_DELTA` —
/// which is what makes "the emitted count equals the requested count" a
/// statement about reachability closure and not about delta-base handling.
pub(crate) fn whole_object_pack(objects: &[(GitObjectKind, Vec<u8>)]) -> Vec<u8> {
    let items: Vec<Item> = objects
        .iter()
        .map(|(k, b)| Item::Whole(*k, b.clone()))
        .collect();
    build_pack(&items)
}

// ── the corpus ───────────────────────────────────────────────────────────────

/// Files in the tree of every commit.
const FILES: usize = 128;
/// Commits in the history. Linear — each names the one before it as its parent.
const COMMITS: usize = 48;
/// How many of the [`FILES`] each commit rewrites. The rest keep the blob they
/// had, which is what makes the object count `FILES + (COMMITS-1)*CHANGED`
/// rather than `FILES * COMMITS` and what a real repository's pack looks like.
const CHANGED: usize = 24;
/// Bytes per blob. **Pseudo-random on purpose**: deflate cannot shrink them, so
/// the corpus's emitted size is predictable from these four constants and the
/// `will_emit > 1_000_000` / `held < will_emit/8` bounds in
/// [`crate::store`]'s zero-copy guards are satisfied by arithmetic rather than
/// by luck.
///
/// MEASURED with the four constants above: **1352 objects, ~2.8 MB emitted**
/// against ~146 KB of `EmitEntry` slots and oids — 2.8x the `> 1_000_000` floor
/// and 2.4x under the `/8` ceiling. The object count also has to clear
/// `ordered.len() > 1000`, which is what the gatling fan-out guard in
/// [`crate::store`] needs to spread over workers at all, and 2687 was the found
/// pack it was written against.
const BLOB_BYTES: usize = 2048;

/// splitmix64 — a whole PRNG in four lines, so the corpus is byte-identical on
/// every box and in every run without a dependency or a committed file.
fn splitmix(state: &mut u64) -> u64 {
    *state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
    let mut z = *state;
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
    z ^ (z >> 31)
}

/// The content of file `file` at version `version`, deterministically.
fn blob_body(file: usize, version: usize) -> Vec<u8> {
    let mut s = (file as u64) << 32 | version as u64;
    let mut out = Vec::with_capacity(BLOB_BYTES);
    while out.len() < BLOB_BYTES {
        out.extend_from_slice(&splitmix(&mut s).to_le_bytes());
    }
    out.truncate(BLOB_BYTES);
    out
}

/// Everything a test might want to know about [`corpus`] without re-deriving it.
pub(crate) struct Corpus {
    pub(crate) pack: Vec<u8>,
    /// Commit oids, oldest first. `commits[i+1]`'s only parent is `commits[i]`.
    pub(crate) commits: Vec<Vec<u8>>,
}

/// **A linear repository history, as a clone pack: connected, delta'd, and the
/// same bytes everywhere.**
///
/// [`COMMITS`] commits over [`FILES`] files, each commit rewriting [`CHANGED`]
/// of them. Every blob version after a file's first is stored as an
/// `OFS_DELTA` against the version before it, and so is every tree and every
/// commit after the first — so the pack carries deltas that resolve to all
/// three of blob, tree and commit, which is what
/// [`crate::serve`]'s `header` guard needs and what a corpus of whole objects
/// could not give it.
///
/// **Closed by construction**: every tree entry names a blob in the pack, every
/// commit names its own tree and its parent, and nothing names anything else.
/// That is the property the found corpus did not have and the property
/// `git index-pack --strict --check-self-contained-and-connected` is asserting
/// three times over.
pub(crate) fn corpus() -> &'static Corpus {
    static ONCE: std::sync::OnceLock<Corpus> = std::sync::OnceLock::new();
    ONCE.get_or_init(build)
}

/// The corpus itself. Called once, through [`corpus`] — 2.8 MB of deflate and
/// sha1 is not something thirty-five call sites should each pay.
fn build() -> Corpus {
    let hash = GitHashKind::Sha1;
    let mut items: Vec<Item> = Vec::new();
    // For each file: (its current oid, the index in `items` of the entry that
    // stores its current version). The second is what the next version deltas
    // against.
    let mut current: Vec<(Vec<u8>, usize)> = Vec::with_capacity(FILES);
    // Where each file's FIRST version sits in `items`, for the star half of the
    // delta shapes below.
    let mut first: Vec<usize> = Vec::with_capacity(FILES);
    let mut version = vec![0usize; FILES];
    let mut commits: Vec<Vec<u8>> = Vec::with_capacity(COMMITS);
    let mut prev_tree: Option<(Vec<u8>, usize)> = None;
    let mut prev_commit: Option<(Vec<u8>, usize)> = None;

    for c in 0..COMMITS {
        // Which files this commit rewrites. A stride rather than a random draw,
        // so every file is touched and the delta chains are all the same depth.
        let touched: Vec<usize> = if c == 0 {
            (0..FILES).collect()
        } else {
            (0..CHANGED).map(|k| (c * CHANGED + k) % FILES).collect()
        };
        for f in touched {
            let body = blob_body(f, version[f]);
            let oid = hash.oid_of(&canonical(GitObjectKind::Blob, &body));
            let at = items.len();
            if version[f] == 0 {
                items.push(Item::Whole(GitObjectKind::Blob, body));
                first.push(at);
                current.push((oid, at));
            } else {
                // **Two delta shapes, and the second one is not decoration.**
                //
                // An odd-numbered file deltas against the version before it — a
                // CHAIN, which is what a repository's own history mostly is. An
                // even-numbered one deltas against its very first version — a
                // STAR, so that base is named by every later version of the
                // file at once.
                //
                // `resolve_walked` holds a base until its last dependent has
                // consumed it, counted rather than set-membership, and the way
                // that goes wrong is freeing a base one dependent early. A
                // corpus of chains alone cannot see it: every base there has
                // exactly one dependent, so "free on first use" and "free on
                // last use" are the same instruction.
                // `resolve::tests::a_base_many_entries_share_outlives_all_of_them`
                // refuses to pass without a fan-out above two, and this is where
                // it comes from.
                let base = if f % 2 == 0 { first[f] } else { current[f].1 };
                items.push(Item::OfsDelta { base, body });
                current[f] = (oid, at);
            }
            version[f] += 1;
        }

        // The tree. Entries sorted by name, which is what fsck requires and
        // what `f000.bin`…`f127.bin` gives for free.
        let mut payload = Vec::new();
        for (f, (oid, _)) in current.iter().enumerate() {
            payload.extend_from_slice(format!("100644 f{f:03}.bin\0").as_bytes());
            payload.extend_from_slice(oid);
        }
        let tree_oid = hash.oid_of(&canonical(GitObjectKind::Tree, &payload));
        let tree_at = items.len();
        match &prev_tree {
            Some((_, base)) => items.push(Item::OfsDelta {
                base: *base,
                body: payload,
            }),
            None => items.push(Item::Whole(GitObjectKind::Tree, payload)),
        }
        prev_tree = Some((tree_oid.clone(), tree_at));

        // The commit.
        let mut body = format!("tree {}\n", hex::encode(&tree_oid));
        if let Some((parent, _)) = &prev_commit {
            body.push_str(&format!("parent {}\n", hex::encode(parent)));
        }
        body.push_str(
            "author A U Thor <author@example.com> 1700000000 +0000\n\
             committer A U Thor <author@example.com> 1700000000 +0000\n\n",
        );
        body.push_str(&format!("commit {c} of the generated corpus\n"));
        let body = body.into_bytes();
        let commit_oid = hash.oid_of(&canonical(GitObjectKind::Commit, &body));
        let commit_at = items.len();
        match &prev_commit {
            Some((_, base)) => items.push(Item::OfsDelta {
                base: *base,
                body,
            }),
            None => items.push(Item::Whole(GitObjectKind::Commit, body)),
        }
        prev_commit = Some((commit_oid.clone(), commit_at));
        commits.push(commit_oid);
    }

    Corpus {
        pack: build_pack(&items),
        commits,
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::resolve::{resolve, NoBases};

    /// **The corpus is the shape every guard that takes it assumes**, asserted
    /// here once instead of re-derived in thirty-five places — and asserted at
    /// all because a fixture whose premises nobody checks is a fixture that
    /// stops holding them silently.
    #[test]
    fn the_generated_corpus_has_the_shape_its_consumers_require() {
        let c = corpus();
        let rows = resolve(&c.pack, GitHashKind::Sha1, 0, &NoBases)
            .expect("the corpus resolves standalone — it is not thin");

        assert_eq!(
            rows.len(),
            FILES + (COMMITS - 1) * CHANGED + 2 * COMMITS,
            "the object count is the arithmetic of the four constants"
        );
        assert!(rows.len() > 100, "consumers assert `all.len() > 100`");

        let deltas = rows
            .iter()
            .filter(|r| matches!(r.stored_type, ObjType::OfsDelta))
            .count();
        assert_eq!(
            deltas,
            (COMMITS - 1) * CHANGED + 2 * (COMMITS - 1),
            "every version after the first, of a blob, a tree or a commit"
        );
        assert_eq!(
            rows.iter()
                .filter(|r| matches!(r.stored_type, ObjType::RefDelta))
                .count(),
            0,
            "a clone pack carries no REF_DELTA, and three guards assert that"
        );

        // Deltas that resolve to all three kinds — the distinction
        // `serve::header` exists to get right.
        for want in [GitObjectKind::Blob, GitObjectKind::Tree, GitObjectKind::Commit] {
            assert!(
                rows.iter()
                    .any(|r| r.stored_type == ObjType::OfsDelta && r.kind == want),
                "no delta resolves to {want:?}"
            );
        }

        let emitted: u64 = rows.iter().map(|r| r.len).sum();
        assert!(
            emitted > 1_000_000,
            "the zero-copy guard needs a corpus over 1 MB; this one emits {emitted}"
        );
        assert!(
            rows.len() > 1000,
            "the gatling fan-out guard needs over 1000 entries to spread over workers; this \
             corpus holds {}",
            rows.len()
        );

        // A base shared by more than two entries — the star half of the delta
        // shapes. Without one,
        // `resolve::tests::a_base_many_entries_share_outlives_all_of_them`
        // cannot tell "free on first use" from "free on last use" and refuses
        // to report a pass.
        let mut uses: std::collections::HashMap<u64, usize> = Default::default();
        for r in rows.iter().filter(|r| r.delta_base != 0) {
            *uses.entry(r.delta_base).or_default() += 1;
        }
        let widest = uses.values().copied().max().unwrap_or(0);
        assert!(
            widest > 2,
            "the widest delta fan-out is {widest}; the reference-counting guard needs above 2"
        );
        assert!(
            uses.values().any(|n| *n == 1),
            "every base is shared, so the chain half of the delta shapes is gone"
        );

        // Closed: every oid a tree or a commit names is in the pack.
        let held: std::collections::HashSet<&[u8]> =
            rows.iter().map(|r| r.oid.as_slice()).collect();
        assert_eq!(held.len(), rows.len(), "two objects share an oid");
        assert_eq!(c.commits.len(), COMMITS);
        for oid in &c.commits {
            assert!(held.contains(oid.as_slice()), "a commit is not in its pack");
        }

        // Byte-identical between calls, which is the whole claim over a found
        // pack.
        assert_eq!(c.pack, build().pack, "the corpus is not deterministic");
    }
}