crates/gunnar-pack/src/delta.rs
//! Writing a pack whose deltas have to be **computed**, not copied.
//!
//! # The defect this exists to fix
//!
//! [`crate::write_pack`] emits every object whole. Its own doc says so, and for
//! the path it was written for — a store with no packs to copy from — that is
//! the honest shape. But `gunnar-client`'s `send-pack` called it, and a pushing
//! client is precisely the case where whole objects are wrong: the objects it is
//! sending are usually loose, so there is nothing for `P-001`'s pack-copy to
//! reuse, and nobody upstream of it will ever compute a delta for them either.
//!
//! MEASURED, oden 2026-08-03, `gunnar.real_repo_clone` over 19 real nordisk
//! repositories, same server, same history, same wire, only the client
//! differing:
//!
//! | client | the server ended up storing | deltified, per `git verify-pack -v` |
//! |---|---|---|
//! | gunnar's own | 407.08 MiB | **0.0%** |
//! | stock git | 88.14 MiB | 74.0% |
//!
//! **And `P-001` makes it permanent.** The server's pack-copy is working
//! perfectly, which is exactly why it matters: it faithfully copies those
//! undeltified entries out to every later clone, so one push from our client
//! inflates that repository for the rest of its life. This could not have shown
//! up on `P-001`'s own fixtures, whose packs `git repack` had just built.
//!
//! # The two halves, composed
//!
//! gitoxide owns the **reuse** half (`PackCopyAndBaseObjects`, which is a delta
//! *copier*) and has no encoder at all. `gunnar-delta` is the **encode** half,
//! built donation-shaped under D21. This module is the seam between them and
//! deliberately nothing else: it reads objects, hands them to
//! [`gunnar_delta::deltify`], and turns the result into pack entries through
//! [`crate::PackWriter`], which is the same writer, the same deflate scratch and
//! the same trailer hasher every other path uses (LAW 5).
//!
//! Which half a caller wants is decided by what it holds, not by preference:
//!
//! * objects sitting in a pack already → [`crate::write_pack_copy`], reuse;
//! * loose objects, which is a push → this, compute.
//!
//! `gunnar-delta`'s own honest caveat applies and points the same way: against
//! git *reusing* packed deltas it measures 1.06–1.44×, against git *computing*
//! them 0.92–0.97×. Reuse is the half we do not own; computing is.
//!
//! # Memory, and the pre-pass that bounds it
//!
//! [`gunnar_delta::deltify`] takes `&[Object<'_>]` — every object borrowed at
//! once — because a sliding window is not expressible over a stream. A whole
//! repository's inflated bytes is not a peak this can take: `nornir` alone is
//! 417 MiB raw.
//!
//! So the objects are written in **batches** under
//! [`DeltaOptions::memory_budget`], and the batches are chosen by a size
//! pre-pass rather than by arrival order. `gix_object::FindHeader` gives every
//! object's kind and size without inflating its content, the ids are sorted into
//! `(kind, name hash descending, size descending, id)` — `gunnar-delta`'s own
//! order — and each batch is a contiguous run of that order. A batch boundary
//! therefore costs the same
//! thing a chunk boundary already costs *inside* `deltify`: the window cannot
//! see across it, so up to `window` objects near the seam lose their best base.
//! Batching by arrival order instead would scatter similar objects across every
//! batch and cost far more, for the same peak.
//!
//! The pre-pass is why this function needs `FindHeader` on top of
//! [`crate::ObjectSource`]. `gix::Repository` has it; a store that does not can
//! still use [`crate::write_pack`].
use std::io::Write;
use std::sync::atomic::AtomicBool;
use gix_hash::ObjectId;
use crate::write::prepare_ids;
use crate::{Error, ObjectSource, PackWriter, Result, WriteOptions, WriteOutcome};
/// How hard to look for deltas, and how much memory that may cost.
///
/// The defaults are git's own search parameters (`--window=10 --depth=50`) plus
/// a byte budget that is this crate's, not git's, because git streams its object
/// set and this cannot.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DeltaOptions {
/// How many earlier objects, in size order, each object is compared
/// against. git's default is 10.
pub window: usize,
/// Longest delta chain permitted. git's default is 50. A reader pays one
/// object reconstruction per link.
pub depth: usize,
/// Cap on worker threads. `None` is the machine's core count.
///
/// Correct for a client, which is a batch tier: a push happens once, on a
/// developer's machine, and the whole box is available. A *serving* path
/// must not be here at all — the server reuses deltas (`P-001`) rather than
/// computing them, and per-request fan-out at forge concurrency is a
/// measured regression (`P-004`).
pub thread_limit: Option<usize>,
/// Bytes of inflated object content held in memory at one time.
///
/// Not a tuning knob — a ceiling. See the module docs. The peak is roughly
/// this plus the deltas produced for one batch, and one object may exceed it
/// on its own, because a batch is never empty.
pub memory_budget: usize,
}
impl Default for DeltaOptions {
fn default() -> Self {
DeltaOptions {
window: 10,
depth: 50,
thread_limit: None,
memory_budget: 512 * 1024 * 1024,
}
}
}
impl DeltaOptions {
/// The `gunnar-delta` options this maps onto, leaving that crate's own
/// [`Limits`](gunnar_delta::Limits) at their defaults: they are caps against
/// an OOM, not settings, and nothing here has any business raising them.
fn to_delta(&self) -> gunnar_delta::Options {
gunnar_delta::Options {
window: self.window,
depth: self.depth,
thread_limit: self.thread_limit,
..Default::default()
}
}
}
/// One object of a batch, owned for as long as the batch is being deltified.
struct Loaded {
id: ObjectId,
kind: gix_object::Kind,
order: OrderKey,
data: Vec<u8>,
}
/// Everything the window is told about one object that is not in its bytes.
///
/// Two numbers rather than two closures: they come from the same walk, they are
/// asked for together once per object, and splitting them would let a caller
/// supply one and forget the other — which reads as "this repository has no
/// history", not as an error.
///
/// `Default` is both fields at `0`, which is each field's documented "no
/// information" value, so a caller that has neither is exactly the caller that
/// existed before this struct did.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct OrderKey {
/// What the object's path is worth to the search. See
/// [`gunnar_delta::Object::name_hash`].
pub name_hash: u32,
/// How new the object is, larger being newer. See
/// [`gunnar_delta::Object::epoch`].
pub epoch: u32,
}
/// What an object's path and age are worth to the search, per object.
///
/// A `&dyn Fn` rather than a map, because the two callers hold the answer in
/// completely different shapes — a repack has a walked path table, a pushing
/// client has nothing — and a trait object costs one indirect call per object
/// against a window search that is thousands of times that.
pub type NameHashFn<'a> = &'a dyn Fn(&ObjectId) -> OrderKey;
/// Write a packfile containing exactly `ids`, **computing a delta** for every
/// object that has a worthwhile base among the others.
///
/// The drop-in for [`crate::write_pack`] on any path whose objects are loose.
/// Same inputs, same guarantees, same errors, plus
/// [`WriteOutcome::objects_deltified`] — which is the applied output, and the
/// only field that can tell this apart from the whole-object writer.
///
/// Duplicate ids are written once. An empty `ids` produces a valid, empty pack.
/// When `options.ofs_delta` is false the deltas are named by their base's object
/// id (`OBJ_REF_DELTA`) instead of by distance, exactly as
/// [`crate::write_pack_copy`] does, so a conservative reader still gets the
/// compression.
///
/// # Errors
///
/// * [`Error::ObjectMissing`] if an id is not in `source`, from either pass.
/// * [`Error::HashKindMismatch`] if an id's hash kind is not `options.hash_kind`.
/// * [`Error::Delta`] if the encoder refused the request; see [`DeltaOptions`].
pub fn write_pack_deltified<S, W>(
ids: &[ObjectId],
source: &S,
out: W,
options: &WriteOptions,
delta: &DeltaOptions,
) -> Result<WriteOutcome>
where
S: ObjectSource + gix_object::FindHeader + ?Sized,
W: Write,
{
// A fresh flag: this entry point has never been cancellable and the
// signature is `gunnar-client`'s, which has no interrupt to give.
write_pack_deltified_ordered(
ids,
&|_| OrderKey::default(),
&AtomicBool::default(),
source,
out,
options,
delta,
)
}
/// [`write_pack_deltified`], plus the one thing that decides how good the
/// deltas are: **what the window considers alike**.
///
/// `name_hash` is asked once per object and its answer becomes
/// [`gunnar_delta::Object::name_hash`] and [`gunnar_delta::Object::epoch`] —
/// the primary sort key after the object kind, and the term inside it that
/// decides which way a delta chain points. Returning [`OrderKey::default`] for
/// everything is exactly [`write_pack_deltified`], and that is not a formality
/// — it is why this pair is one implementation and not two (LAW 5).
///
/// # What to put in it
///
/// A hash of the object's path, from [`gunnar_delta::name_hash`]. The published
/// numbers for the key alone, `git repack -adf` with nothing else changed:
/// fluentui 439 MiB → 160 MiB and 96 s → 34 s for `--name-hash-version=2`
/// (Blau), 438 MB → 148 MB for `--path-walk` (Stolee). A caller with real paths
/// and no hash — a repack that has walked the trees — is better off numbering
/// the distinct paths and passing the number, which is `--path-walk`'s grouping
/// with none of its machinery.
///
/// A caller with no paths, which is every pushing client, passes
/// [`write_pack_deltified`] and gets the size-ordered search it had before.
pub fn write_pack_deltified_ordered<S, W>(
ids: &[ObjectId],
name_hash: NameHashFn<'_>,
should_interrupt: &AtomicBool,
source: &S,
out: W,
options: &WriteOptions,
delta: &DeltaOptions,
) -> Result<WriteOutcome>
where
S: ObjectSource + gix_object::FindHeader + ?Sized,
W: Write,
{
let (ids, count) = prepare_ids(ids, options)?;
// ── pass 1: kinds, sizes and name hashes, no content ────────────────────
let mut sized: Vec<(ObjectId, gix_object::Kind, u64, OrderKey)> = Vec::with_capacity(ids.len());
for id in &ids {
let header = source
.try_header(id)
.map_err(|source| Error::Find { id: *id, source: source.into() })?
.ok_or(Error::ObjectMissing { id: *id })?;
sized.push((*id, header.kind, header.size, name_hash(id)));
}
// `gunnar_delta`'s own order, restated here so a batch is a contiguous run
// of it and the window loses nothing except at the seams. It has to include
// the name hash for the same reason it has to include the size: a batch cut
// across a group of like-named objects would separate exactly the pairs the
// key was added to bring together, which is the failure that would show up
// as "the ordering bought nothing on large repositories only".
sized.sort_unstable_by(|a, b| {
(a.1 as u8)
.cmp(&(b.1 as u8))
.then(b.3.name_hash.cmp(&a.3.name_hash))
.then(a.3.epoch.cmp(&b.3.epoch))
.then(b.2.cmp(&a.2))
.then(a.0.cmp(&b.0))
});
// ── pass 2: load a batch, deltify it, write it, drop it ─────────────────
let mut writer = PackWriter::new(out, count, options)?;
let mut batch: Vec<Loaded> = Vec::new();
let mut batch_bytes: usize = 0;
let mut buf = Vec::with_capacity(8 * 1024);
let mut deltified = 0usize;
for (id, _, size, order) in sized {
if !batch.is_empty() && batch_bytes.saturating_add(size as usize) > delta.memory_budget {
deltified += flush(&mut writer, &batch, options, delta, should_interrupt)?;
batch.clear();
batch_bytes = 0;
}
let object = source
.try_find(&id, &mut buf)
.map_err(|source| Error::Find { id, source: source.into() })?
.ok_or(Error::ObjectMissing { id })?;
batch_bytes += object.data.len();
batch.push(Loaded {
id,
kind: object.kind,
order,
data: object.data.to_vec(),
});
}
if !batch.is_empty() {
deltified += flush(&mut writer, &batch, options, delta, should_interrupt)?;
}
let mut outcome = writer.finish()?;
outcome.objects_deltified = deltified;
debug_assert_eq!(
outcome.objects_recompressed + outcome.objects_deltified,
outcome.num_objects as usize,
"on this path every entry is either a whole object or a computed delta"
);
tracing::debug!(
target: crate::GIT_TARGET,
objects = outcome.num_objects,
deltified = outcome.objects_deltified,
whole = outcome.objects_recompressed,
bytes = outcome.bytes_written,
"wrote a packfile with computed deltas"
);
Ok(outcome)
}
/// Deltify one batch and write its entries. Returns how many came out as deltas.
fn flush<W: Write>(
writer: &mut PackWriter<W>,
batch: &[Loaded],
options: &WriteOptions,
delta: &DeltaOptions,
should_interrupt: &AtomicBool,
) -> Result<usize> {
let objects: Vec<gunnar_delta::Object<'_>> = batch
.iter()
.map(|o| gunnar_delta::Object {
id: o.id,
kind: o.kind,
name_hash: o.order.name_hash,
epoch: o.order.epoch,
data: &o.data,
})
.collect();
let entries = gunnar_delta::deltify(
&objects,
&delta.to_delta(),
&mut gix_utils::progress::Discard,
should_interrupt,
)?;
// Where each entry of THIS batch landed in the pack. `Deltified::base`
// indexes into `entries`, and every base precedes the deltas that name it,
// so this is always already filled in by the time it is read.
let mut offsets: Vec<u64> = Vec::with_capacity(entries.len());
let mut deltified = 0usize;
for entry in &entries {
let at = writer.offset();
match (&entry.data, entry.base) {
(Some(payload), Some(base)) => {
let header = if options.ofs_delta {
gix_pack::data::entry::Header::OfsDelta {
base_distance: at - offsets[base],
}
} else {
gix_pack::data::entry::Header::RefDelta {
base_id: batch[entries[base].source].id,
}
};
writer.add_delta(&header, payload)?;
deltified += 1;
}
(None, None) => {
let object = &batch[entry.source];
writer.add_object(object.kind, &object.data)?;
}
// `Deltified` carries a base and its bytes together or neither; the
// encoder's own type makes the other two combinations unreachable.
_ => return Err(Error::ObjectVanished),
}
offsets.push(at);
}
Ok(deltified)
}