gunnar-store 1.6.0

//! **The fixture packfile**, written by the suite so the suite knows its bytes.
//!
//! [`GitOps::put_pack`](git_storage_trait::GitOps::put_pack) takes a packfile and
//! nothing else, so a conformance suite for that contract has to produce one.
//! Producing it *here* rather than borrowing a writer is what makes three of the
//! contract's promises checkable at all:
//!
//! * [`Stored::bytes`](git_storage_trait::Stored) is *"the pack entry, header
//!   and all, byte for byte as the client sent them"*. Only a caller that knows
//!   which byte range it wrote can assert that.
//! * [`Stored::uncompressed_size`](git_storage_trait::Stored) is the
//!   **post-resolution** size, *"not `bytes.len()` for a delta"*. Only a fixture
//!   that deliberately contains a delta whose stored length differs from its
//!   resolved length can catch a backend that returns the wrong one — and that
//!   is a bug which passes every wire-byte and object-count test, because the
//!   number is only consulted by a quota gate.
//! * [`ObjType`] is the type *in the pack*, so an entry may be `OfsDelta`. A
//!   fixture of four plain objects can never see a backend that resolves and
//!   relabels.
//!
//! # What this writer deliberately is not
//!
//! It is not a general packfile writer and must never grow into one. It emits
//! **base entries and `OFS_DELTA` entries only** — no `REF_DELTA` (which
//! `gunnar_pack::index_pack` refuses and gitoxide's thin-pack resolver cannot
//! close in-pack), no thin packs, no delta
//! *compression* worth the name: every delta here is one insert instruction over
//! the whole result. The delta exists to make the entry's stored length differ
//! from its resolved length, which is the only property the contract talks about.
//!
//! # One implementation: this writer and the in-crate reader agree by construction
//!
//! [`crate::mem::MemGitOps`] parses what this writes, and both were written in
//! the same sitting by the same hand, so their agreeing is worth nothing on its
//! own. The outside oracle is `gunnar_pack::index_pack`, a dev-dependency with
//! no stake in either, driven over these exact bytes by
//! `the_fixture_pack_is_a_real_packfile` in `tests/conformance.rs`. That test
//! going red means this module has stopped emitting git's format, whatever the
//! rest of the suite says.

use std::io::Write;

use flate2::write::ZlibEncoder;
use flate2::Compression;
use git_storage_trait::{Extent, ObjType};
use gix_hash::ObjectId;
use gix_object::Kind;

use crate::error::{Error, Result};

/// One entry of a fixture pack, and everything the suite must be able to assert
/// about it.
#[derive(Debug, Clone)]
pub struct Entry {
    /// The object's id — the id git would give it, computed by `gix-object` so
    /// that no part of gunnar invents one (one implementation).
    pub id: ObjectId,
    /// The object's git kind, after any delta is resolved.
    pub kind: Kind,
    /// The entry's type **in the pack**. `OfsDelta` for a delta entry, so a
    /// backend that hands back a resolved type is caught.
    pub obj_type: ObjType,
    /// The object's content, delta chain applied. This is what a git object of
    /// [`Entry::kind`] holds, without the `<kind> <len>\0` loose header.
    pub content: Vec<u8>,
    /// Where this entry's bytes are in the pack: `(offset, len)`.
    ///
    /// **Not** what [`GitOps::extents`](git_storage_trait::GitOps::extents) must
    /// return. The contract says an extent's unit is *"wherever this backend
    /// keeps the bytes"* and promises only that the pair is stable, so the suite
    /// never compares a backend's extent against this one.
    pub extent: Extent,
}

impl Entry {
    /// The verbatim entry bytes, sliced out of the pack that carries them.
    ///
    /// This is what `Stored::bytes` promises back.
    pub fn bytes<'a>(&self, pack: &'a [u8]) -> &'a [u8] {
        let (offset, len) = self.extent;
        &pack[offset as usize..(offset + len) as usize]
    }
}

/// A packfile and the ground truth about what is inside it.
#[derive(Debug, Clone)]
pub struct Fixture {
    /// The pack, ready for `put_pack`.
    pub bytes: Vec<u8>,
    /// Its entries, in pack order.
    pub entries: Vec<Entry>,
}

impl Fixture {
    /// The entry for `id`, if this pack carries it.
    pub fn entry(&self, id: &gix_hash::oid) -> Option<&Entry> {
        self.entries.iter().find(|e| e.id == id)
    }

    /// Every object id in the pack, in pack order.
    pub fn ids(&self) -> Vec<ObjectId> {
        self.entries.iter().map(|e| e.id).collect()
    }
}

enum Item {
    Base {
        kind: Kind,
        content: Vec<u8>,
    },
    /// A delta whose base is the item at this index. The content is the
    /// **result** — the delta instructions are derived from it.
    Delta {
        base: usize,
        content: Vec<u8>,
    },
}

/// Builds a [`Fixture`].
pub struct PackBuilder {
    hash_kind: gix_hash::Kind,
    items: Vec<Item>,
    level: Compression,
}

impl PackBuilder {
    /// A builder for a pack of `hash_kind`.
    pub fn new(hash_kind: gix_hash::Kind) -> Self {
        PackBuilder {
            hash_kind,
            items: Vec::new(),
            level: Compression::default(),
        }
    }

    /// **The zlib level every entry is written at** — `Compression::default()` unless a caller
    /// says otherwise, so every existing fixture is byte-for-byte what it was.
    ///
    /// For a fixture of incompressible bytes, where the level buys nothing and costs
    /// everything: MEASURED in `gunnar-server/tests/twin_snapshot_memory.rs`, deflating 512 MiB
    /// of random blobs at the default level took ~250 s of a debug test binary's 376, and
    /// produced a pack no smaller. `Compression::none()` writes stored blocks — a legal pack
    /// that every reader inflates like any other.
    #[must_use]
    pub fn compression(mut self, level: Compression) -> Self {
        self.level = level;
        self
    }

    /// Append a whole object. Returns its index, for [`PackBuilder::delta`].
    pub fn object(&mut self, kind: Kind, content: impl Into<Vec<u8>>) -> usize {
        self.items.push(Item::Base {
            kind,
            content: content.into(),
        });
        self.items.len() - 1
    }

    /// Append an `OFS_DELTA` entry against an earlier item, resolving to
    /// `content`.
    ///
    /// The delta's kind is the base's kind: a delta entry carries no type of its
    /// own, which is exactly why `ObjType` distinguishes `OfsDelta` from the four
    /// real kinds.
    pub fn delta(&mut self, base: usize, content: impl Into<Vec<u8>>) -> usize {
        assert!(base < self.items.len(), "a delta's base must precede it");
        self.items.push(Item::Delta {
            base,
            content: content.into(),
        });
        self.items.len() - 1
    }

    /// Write the pack.
    pub fn build(self) -> Result<Fixture> {
        let mut bytes = Vec::new();
        bytes.extend_from_slice(b"PACK");
        bytes.extend_from_slice(&2u32.to_be_bytes());
        bytes.extend_from_slice(&(self.items.len() as u32).to_be_bytes());

        let mut entries: Vec<Entry> = Vec::with_capacity(self.items.len());
        for item in &self.items {
            let start = bytes.len() as u64;
            let (kind, content, obj_type, payload) = match item {
                Item::Base { kind, content } => {
                    (*kind, content.clone(), obj_type_of(*kind), content.clone())
                }
                Item::Delta { base, content } => {
                    let base_entry = &entries[*base];
                    let payload = encode_delta(&base_entry.content, content);
                    (base_entry.kind, content.clone(), ObjType::OfsDelta, payload)
                }
            };

            // The size in an entry header is the length of the entry's own
            // uncompressed data — the delta stream for a delta, not the object
            // it resolves to. Getting this backwards produces a pack that
            // inflates correctly and indexes wrong.
            write_entry_header(&mut bytes, obj_type, payload.len() as u64);
            if let Item::Delta { base, .. } = item {
                let distance = start - entries[*base].extent.0;
                write_offset(&mut bytes, distance);
            }
            deflate_at(&mut bytes, &payload, self.level)?;

            let id = gix_object::compute_hash(self.hash_kind, kind, &content)?;
            entries.push(Entry {
                id,
                kind,
                obj_type,
                content,
                extent: (start, bytes.len() as u64 - start),
            });
        }

        let mut hasher = gix_hash::hasher(self.hash_kind);
        hasher.update(&bytes);
        let trailer = hasher.try_finalize()?;
        bytes.extend_from_slice(trailer.as_slice());

        Ok(Fixture { bytes, entries })
    }
}

/// The [`ObjType`] a resolved git kind is stored under. The inverse of
/// [`kind_of`] over the four non-delta codes.
pub fn obj_type_of(kind: Kind) -> ObjType {
    match kind {
        Kind::Commit => ObjType::Commit,
        Kind::Tree => ObjType::Tree,
        Kind::Blob => ObjType::Blob,
        Kind::Tag => ObjType::Tag,
    }
}

/// The git kind an [`ObjType`] names, or `None` for the two delta codes.
pub fn kind_of(obj_type: ObjType) -> Option<Kind> {
    Some(match obj_type {
        ObjType::Commit => Kind::Commit,
        ObjType::Tree => Kind::Tree,
        ObjType::Blob => Kind::Blob,
        ObjType::Tag => Kind::Tag,
        ObjType::OfsDelta | ObjType::RefDelta => return None,
    })
}

// ───────────────────────────── the format ────────────────────────────────────

/// git's entry header: three type bits and a base-128 size, low nibble first.
///
/// `pub(crate)` because [`crate::mem::MemGitServe`]'s `emit_pack` writes entries
/// too, and two spellings of git's entry header in one crate is exactly the
/// twinning one implementation forbids — the emitter and the fixture writer agree because
/// they are the same function.
pub(crate) fn write_entry_header(out: &mut Vec<u8>, obj_type: ObjType, mut size: u64) {
    let mut byte = (obj_type.code() << 4) | (size as u8 & 0x0f);
    size >>= 4;
    while size > 0 {
        out.push(byte | 0x80);
        byte = size as u8 & 0x7f;
        size >>= 7;
    }
    out.push(byte);
}

/// git's `OFS_DELTA` distance: big-endian base-128, biased so no encoding is
/// wasted on a repeated prefix.
///
/// `pub(crate)` for the same reason as [`write_entry_header`]: the emitter
/// rewrites this field when it moves an entry into a new pack, and it must
/// write the encoding [`read_offset`] reads.
pub(crate) fn write_offset(out: &mut Vec<u8>, mut value: u64) {
    let mut buf = vec![(value & 0x7f) as u8];
    value >>= 7;
    while value > 0 {
        value -= 1;
        buf.push(0x80 | (value & 0x7f) as u8);
        value >>= 7;
    }
    buf.reverse();
    out.extend_from_slice(&buf);
}

/// git's delta-stream size varint: little-endian base-128.
fn write_varint(out: &mut Vec<u8>, mut value: u64) {
    loop {
        let byte = (value & 0x7f) as u8;
        value >>= 7;
        if value == 0 {
            out.push(byte);
            return;
        }
        out.push(byte | 0x80);
    }
}

/// A delta that reproduces `result` with insert instructions only.
///
/// Deliberately the dumbest possible encoding. A real deltifier emits copy
/// instructions against the base and that is what makes packs small; here the
/// only thing that matters is that the *stored* length differs from the
/// *resolved* length, so that a backend reporting one where the contract asks
/// for the other is caught.
fn encode_delta(base: &[u8], result: &[u8]) -> Vec<u8> {
    let mut out = Vec::new();
    write_varint(&mut out, base.len() as u64);
    write_varint(&mut out, result.len() as u64);
    for chunk in result.chunks(0x7f) {
        out.push(chunk.len() as u8);
        out.extend_from_slice(chunk);
    }
    out
}

/// `pub(crate)` for the same reason as [`write_entry_header`]: the in-memory
/// emitter rebuilds an entry whose delta base the request does not carry, and a
/// rebuilt entry has to be deflated with the encoder the reader below expects.
pub(crate) fn deflate_into(out: &mut Vec<u8>, payload: &[u8]) -> Result<()> {
    deflate_at(out, payload, Compression::default())
}

fn deflate_at(out: &mut Vec<u8>, payload: &[u8], level: Compression) -> Result<()> {
    let mut encoder = ZlibEncoder::new(Vec::new(), level);
    encoder.write_all(payload)?;
    out.extend_from_slice(&encoder.finish()?);
    Ok(())
}

// ───────────────────────────── reading it back ───────────────────────────────

/// One entry as a reader sees it, before any delta is resolved.
#[derive(Debug, Clone)]
pub struct RawEntry {
    /// The entry's pack type.
    pub obj_type: ObjType,
    /// For an `OFS_DELTA`, the absolute offset of its base entry.
    pub base_offset: Option<u64>,
    /// The entry's inflated payload: the object's content, or the delta stream.
    pub payload: Vec<u8>,
    /// Where the whole entry lives in the pack, header included.
    pub extent: Extent,
    /// How many bytes of [`RawEntry::extent`] are header — the type/size varint
    /// plus, for an `OFS_DELTA`, its base distance. The deflated payload is the
    /// rest.
    ///
    /// Recorded because a **pack-copying** emitter needs exactly this split: an
    /// `OFS_DELTA`'s distance is relative to where its base sits in *this* pack,
    /// so re-emitting the entry means rewriting those leading bytes and copying
    /// the zlib stream after them byte for byte. Without the boundary the only
    /// way to re-emit is to inflate and deflate again, which is the 18.4x
    /// fallback [`git_storage_trait::PackStats::recompressed`] exists to count.
    pub header_len: u64,
}

/// Parse a pack written by [`PackBuilder`].
///
/// Used by [`crate::mem::MemGitOps`]. It handles exactly the subset this module
/// emits: version 2, base entries and `OFS_DELTA`, no `REF_DELTA`. A backend is
/// never asked to use this — it exists so the suite has something to be
/// self-tested against.
pub fn parse(pack: &[u8], hash_kind: gix_hash::Kind) -> Result<Vec<RawEntry>> {
    let trailer_len = hash_kind.len_in_bytes();
    if pack.len() < 12 + trailer_len || &pack[..4] != b"PACK" {
        return Err(Error::backend("not a packfile"));
    }
    let version = u32::from_be_bytes(pack[4..8].try_into().expect("four bytes"));
    if version != 2 {
        return Err(Error::backend(format!("pack version {version}, want 2")));
    }
    let count = u32::from_be_bytes(pack[8..12].try_into().expect("four bytes"));

    let body_end = pack.len() - trailer_len;
    let mut hasher = gix_hash::hasher(hash_kind);
    hasher.update(&pack[..body_end]);
    if hasher.try_finalize()?.as_slice() != &pack[body_end..] {
        return Err(Error::backend("the pack trailer does not match its bytes"));
    }

    let mut out = Vec::with_capacity(count as usize);
    let mut pos = 12usize;
    for _ in 0..count {
        let start = pos;
        let (obj_type, size) = read_entry_header(pack, &mut pos)?;
        let base_offset = if obj_type == ObjType::OfsDelta {
            let distance = read_offset(pack, &mut pos)?;
            Some(
                (start as u64)
                    .checked_sub(distance)
                    .ok_or_else(|| Error::backend("an OFS_DELTA points before the pack"))?,
            )
        } else if obj_type == ObjType::RefDelta {
            return Err(Error::backend(
                "REF_DELTA is outside this fixture reader's subset",
            ));
        } else {
            None
        };
        let header_len = (pos - start) as u64;
        let payload = inflate(&pack[pos..body_end], size as usize, &mut pos)?;
        out.push(RawEntry {
            obj_type,
            base_offset,
            payload,
            extent: (start as u64, (pos - start) as u64),
            header_len,
        });
    }
    Ok(out)
}

fn read_entry_header(pack: &[u8], pos: &mut usize) -> Result<(ObjType, u64)> {
    let mut byte = *pack
        .get(*pos)
        .ok_or_else(|| Error::backend("truncated entry header"))?;
    *pos += 1;
    let code = (byte >> 4) & 0x07;
    let obj_type =
        ObjType::from_code(code).ok_or_else(|| Error::backend(format!("object type {code}")))?;
    let mut size = u64::from(byte & 0x0f);
    let mut shift = 4;
    while byte & 0x80 != 0 {
        byte = *pack
            .get(*pos)
            .ok_or_else(|| Error::backend("truncated entry header"))?;
        *pos += 1;
        size |= u64::from(byte & 0x7f) << shift;
        shift += 7;
    }
    Ok((obj_type, size))
}

fn read_offset(pack: &[u8], pos: &mut usize) -> Result<u64> {
    let mut byte = *pack
        .get(*pos)
        .ok_or_else(|| Error::backend("truncated delta offset"))?;
    *pos += 1;
    let mut value = u64::from(byte & 0x7f);
    while byte & 0x80 != 0 {
        byte = *pack
            .get(*pos)
            .ok_or_else(|| Error::backend("truncated delta offset"))?;
        *pos += 1;
        value = ((value + 1) << 7) | u64::from(byte & 0x7f);
    }
    Ok(value)
}

fn inflate(rest: &[u8], expected: usize, pos: &mut usize) -> Result<Vec<u8>> {
    use std::io::Read;
    let mut decoder = flate2::read::ZlibDecoder::new(rest);
    let mut payload = Vec::with_capacity(expected);
    decoder.read_to_end(&mut payload)?;
    if payload.len() != expected {
        return Err(Error::backend(format!(
            "entry header claims {expected} bytes and {} inflated",
            payload.len()
        )));
    }
    *pos += decoder.total_in() as usize;
    Ok(payload)
}

/// Apply a git delta stream to `base`.
pub fn apply_delta(base: &[u8], delta: &[u8]) -> Result<Vec<u8>> {
    let mut pos = 0usize;
    let base_size = read_varint(delta, &mut pos)?;
    if base_size as usize != base.len() {
        return Err(Error::backend(format!(
            "the delta expects a {base_size}-byte base and the base is {}",
            base.len()
        )));
    }
    let result_size = read_varint(delta, &mut pos)?;
    let mut out = Vec::with_capacity(result_size as usize);
    while pos < delta.len() {
        let op = delta[pos];
        pos += 1;
        if op & 0x80 != 0 {
            // Copy from the base. Never emitted by `encode_delta`, but a reader
            // that silently ignored it would turn a wrong pack into a wrong
            // object rather than into an error.
            let mut offset = 0u64;
            let mut len = 0u64;
            for i in 0..4 {
                if op & (1 << i) != 0 {
                    offset |= u64::from(delta[pos]) << (8 * i);
                    pos += 1;
                }
            }
            for i in 0..3 {
                if op & (1 << (4 + i)) != 0 {
                    len |= u64::from(delta[pos]) << (8 * i);
                    pos += 1;
                }
            }
            if len == 0 {
                len = 0x10000;
            }
            let (from, to) = (offset as usize, (offset + len) as usize);
            out.extend_from_slice(
                base.get(from..to)
                    .ok_or_else(|| Error::backend("a delta copies past the end of its base"))?,
            );
        } else if op == 0 {
            return Err(Error::backend("delta opcode 0 is reserved"));
        } else {
            let (from, to) = (pos, pos + op as usize);
            out.extend_from_slice(
                delta
                    .get(from..to)
                    .ok_or_else(|| Error::backend("a delta insert runs past the stream"))?,
            );
            pos = to;
        }
    }
    if out.len() as u64 != result_size {
        return Err(Error::backend(format!(
            "the delta claims a {result_size}-byte result and produced {}",
            out.len()
        )));
    }
    Ok(out)
}

fn read_varint(bytes: &[u8], pos: &mut usize) -> Result<u64> {
    let mut value = 0u64;
    let mut shift = 0;
    loop {
        let byte = *bytes
            .get(*pos)
            .ok_or_else(|| Error::backend("truncated delta varint"))?;
        *pos += 1;
        value |= u64::from(byte & 0x7f) << shift;
        if byte & 0x80 == 0 {
            return Ok(value);
        }
        shift += 7;
    }
}

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

    /// The round trip, and the one property the delta is here for: the entry's
    /// stored length is not its resolved length.
    #[test]
    fn a_delta_entry_stores_something_other_than_what_it_resolves_to() {
        let mut builder = PackBuilder::new(gix_hash::Kind::Sha256);
        let base = builder.object(Kind::Blob, b"the base blob\n".to_vec());
        builder.delta(
            base,
            b"a longer resolved result, not the delta stream\n".to_vec(),
        );
        let fixture = builder.build().expect("build");

        let raw = parse(&fixture.bytes, gix_hash::Kind::Sha256).expect("parse");
        assert_eq!(raw.len(), 2);
        assert_eq!(raw[1].obj_type, ObjType::OfsDelta);
        let resolved = apply_delta(&raw[0].payload, &raw[1].payload).expect("apply");
        assert_eq!(resolved, fixture.entries[1].content);
        assert_ne!(
            raw[1].payload.len(),
            resolved.len(),
            "the fixture delta must store a different number of bytes than it resolves to, \
             or the post-resolution-size check below is measuring nothing"
        );
    }

    #[test]
    fn every_entry_reads_back_at_the_extent_the_builder_recorded() {
        let mut builder = PackBuilder::new(gix_hash::Kind::Sha1);
        builder.object(Kind::Blob, b"one".to_vec());
        builder.object(Kind::Blob, vec![7u8; 100_000]);
        builder.object(Kind::Tree, Vec::new());
        let fixture = builder.build().expect("build");
        let raw = parse(&fixture.bytes, gix_hash::Kind::Sha1).expect("parse");
        for (entry, raw) in fixture.entries.iter().zip(&raw) {
            assert_eq!(entry.extent, raw.extent);
            assert_eq!(entry.content, raw.payload);
        }
    }

    /// A wrong trailer is an error, not a shrug. Without this the reader would
    /// happily accept a corrupted pack and the suite would blame the backend.
    #[test]
    fn a_corrupted_pack_is_refused() {
        let mut builder = PackBuilder::new(gix_hash::Kind::Sha1);
        builder.object(Kind::Blob, b"intact".to_vec());
        let mut fixture = builder.build().expect("build");
        let last = fixture.bytes.len() - 1;
        fixture.bytes[last] ^= 0xff;
        assert!(parse(&fixture.bytes, gix_hash::Kind::Sha1).is_err());
    }
}