crates/gunnar-store/src/conformance/pack.rs
//! **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());
}
}