crates/gunnar-delta/tests/roundtrip_gix.rs
//! Every delta reconstructs, byte-exact, through gix's own decoder.
//!
//! LAW 2 applies harder here than anywhere else in the crate. A delta that is
//! *almost* right produces a pack that is structurally valid, passes a size
//! check, and fails months later as a corrupt repository at somebody's clone. So
//! nothing here asserts on a size, a ratio or a boolean; every test compares the
//! **applied output**, the bytes gix reconstructs, against the bytes that went
//! in.
//!
//! And the decoder is gix's, reached through a real packfile
//! (`gix_pack::data::File::decode_entry`), because a delta encoder verified with
//! its own author's applier is verified against nothing.
mod support;
use std::sync::atomic::AtomicBool;
use gix_object::Kind;
use support::{decode_all_with_gix, delta_header, write_pack, PackEntry};
use gunnar_delta::{delta, deltify, Object, Options};
/// Deterministic pseudo-random bytes, so a failure is reproducible.
fn noise(seed: u64, len: usize) -> Vec<u8> {
let mut s = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1;
(0..len)
.map(|_| {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
(s >> 24) as u8
})
.collect()
}
/// Encode `target` against `base`, put both in a pack, and demand that gix
/// hands back exactly `target`.
#[track_caller]
fn assert_roundtrip(base: &[u8], target: &[u8]) -> usize {
let d = delta(base, target).expect("encode");
let pack = write_pack(&[
PackEntry::Base {
kind: Kind::Blob,
data: base.to_vec(),
},
PackEntry::OfsDelta {
kind: Kind::Blob,
base: 0,
delta: d.clone(),
},
]);
let dir = tempfile::tempdir().expect("tempdir");
let decoded = decode_all_with_gix(&pack, dir.path());
assert_eq!(decoded[0], base, "the base object itself did not survive");
assert_eq!(
decoded[1],
target,
"gix reconstructed {} bytes, expected {}",
decoded[1].len(),
target.len()
);
d.len()
}
#[test]
fn an_identical_target_reconstructs_and_costs_almost_nothing() {
let base = noise(1, 100_000);
let size = assert_roundtrip(&base, &base);
// One copy instruction per 0xffffff bytes plus the two header varints. If
// this ever grows, the match loop stopped finding the trivial match.
assert!(size < 32, "an identical copy took {size} bytes");
}
#[test]
fn an_appended_tail_reconstructs() {
let base = noise(2, 60_000);
let mut target = base.clone();
target.extend_from_slice(&noise(3, 5_000));
assert_roundtrip(&base, &target);
}
#[test]
fn a_truncated_target_reconstructs() {
let base = noise(4, 60_000);
assert_roundtrip(&base, &base[..17_291]);
}
#[test]
fn an_insertion_in_the_middle_reconstructs() {
let base = noise(5, 80_000);
let mut target = base[..40_000].to_vec();
target.extend_from_slice(b"a line nobody wrote before, inserted right here\n");
target.extend_from_slice(&base[40_000..]);
assert_roundtrip(&base, &target);
}
#[test]
fn a_transposition_reconstructs() {
// Copy offsets must be free to go backwards. An encoder that assumed
// monotonically increasing base offsets passes every other test in this file
// and fails this one.
let base = noise(6, 90_000);
let mut target = base[45_000..].to_vec();
target.extend_from_slice(&base[..45_000]);
assert_roundtrip(&base, &target);
}
#[test]
fn an_empty_target_reconstructs() {
assert_roundtrip(&noise(7, 4_096), &[]);
}
#[test]
fn an_empty_base_reconstructs() {
assert_roundtrip(&[], &noise(8, 4_096));
}
#[test]
fn every_length_from_zero_to_past_one_anchor_reconstructs() {
// The anchor is 16 bytes and the match loop's bounds are written around it.
// An off-by-one at the boundary lives exactly here.
let base = noise(9, 200);
for len in 0..=64 {
let target = &base[..len];
assert_roundtrip(&base, target);
assert_roundtrip(target, &base);
}
}
#[test]
fn a_copy_longer_than_one_instruction_can_carry_is_split_and_reconstructs() {
// A single copy instruction tops out at 0xffffff bytes. This target is
// larger than that and identical to its base, so the encoder is forced to
// split, and the split is where the running offset arithmetic can go wrong.
let unit = noise(10, 1 << 16);
let base: Vec<u8> = unit.iter().cycle().take(0x0100_0100).copied().collect();
assert_roundtrip(&base, &base);
}
/// The fourth offset byte — bits 24..31, flag `0x08` — is only written when the
/// copy starts at or past 16 MiB, and nothing else in the suite reaches there.
///
/// Found red-first: shifting that byte's extraction from `>> 24` to `>> 25` left
/// the entire suite green, so the widest copy the format can express was
/// unencoded territory. This is the test that turns that mutation red.
#[test]
fn a_copy_offset_above_sixteen_mebibytes_uses_the_fourth_offset_byte_and_reconstructs() {
const HIGH: usize = 1 << 24;
// Just over the boundary, so the interesting copy starts above 2^24 while
// the buffers stay small enough to be a unit test.
let base = noise(21, HIGH + 300_000);
// A target that can only be built by copying from the far end of the base.
let target = base[HIGH + 40_000..].to_vec();
let d = delta(&base, &target).expect("encode");
// Prove the fourth offset byte is genuinely exercised rather than hoping.
let (_, _, mut i) = delta_header(&d);
let mut saw_four_byte_offset = false;
while i < d.len() {
let cmd = d[i];
i += 1;
if cmd & 0x80 != 0 {
if cmd & 0x08 != 0 {
saw_four_byte_offset = true;
}
i += (cmd & 0x0f).count_ones() as usize + (cmd & 0x70).count_ones() as usize;
} else {
i += cmd as usize;
}
}
assert_eq!(i, d.len(), "the instruction stream did not parse cleanly");
assert!(
saw_four_byte_offset,
"no copy in this delta set flag 0x08, so the fourth offset byte is still untested"
);
assert_roundtrip(&base, &target);
}
/// The two header varints must state the base's real length and the target's
/// real length.
///
/// This assertion is here because gix's decoder does **not** check the first
/// one: mutating `base.len()` to `base.len() + 1` in the emitter leaves every
/// gix round trip in this file green and is caught only by stock `git`. A crate
/// whose format-level guarantee depends on one heavyweight subprocess test is a
/// crate one `#[ignore]` away from unverified.
#[test]
fn the_header_states_the_exact_base_and_result_sizes() {
for (b, t) in [
(0usize, 0usize),
(1, 1),
(16, 16),
(127, 300),
(70_000, 40_000),
] {
let base = noise(22, b);
let target = noise(23, t);
let d = delta(&base, &target).expect("encode");
let (stated_base, stated_result, at) = delta_header(&d);
assert_eq!(
stated_base, b as u64,
"delta claims a {stated_base} byte base, base is {b}"
);
assert_eq!(
stated_result, t as u64,
"delta claims a {stated_result} byte result, target is {t}"
);
assert!(at <= d.len(), "the header ran past the delta");
}
}
#[test]
fn a_target_of_pure_repetition_reconstructs() {
// The degenerate case for a hash-bucketed index: every anchor collides.
// `Encode::max_chain` bounds the scan; correctness must survive it.
let base = vec![0x5au8; 300_000];
let mut target = vec![0x5au8; 250_000];
target.extend_from_slice(b"tail");
assert_roundtrip(&base, &target);
}
/// The chain test. Depth 1 proves nothing about depth 50: a decoder walks a
/// chain by repeatedly applying, and an encoder that mis-sizes the base at depth
/// 1 is invisible until the reconstruction it feeds is itself a reconstruction.
#[test]
fn a_delta_chain_at_depth_fifty_reconstructs_every_link() {
const DEPTH: usize = 50;
let mut contents: Vec<Vec<u8>> = Vec::with_capacity(DEPTH + 1);
contents.push(noise(11, 120_000));
for i in 1..=DEPTH {
// Each revision edits its predecessor in three places and shrinks a
// little, which is what a real file's history looks like.
let mut next = contents[i - 1].clone();
let stamp = format!("revision {i} of this file\n").into_bytes();
for (k, at) in [7_000usize, 51_000, 96_000].into_iter().enumerate() {
let at = at + k * i;
next.splice(at..at + stamp.len(), stamp.iter().copied());
}
next.truncate(next.len() - 37);
contents.push(next);
}
let mut entries = vec![PackEntry::Base {
kind: Kind::Blob,
data: contents[0].clone(),
}];
for i in 1..=DEPTH {
entries.push(PackEntry::OfsDelta {
kind: Kind::Blob,
base: i - 1,
delta: delta(&contents[i - 1], &contents[i]).expect("encode"),
});
}
let pack = write_pack(&entries);
let dir = tempfile::tempdir().expect("tempdir");
let decoded = decode_all_with_gix(&pack, dir.path());
assert_eq!(decoded.len(), DEPTH + 1);
for (i, (got, want)) in decoded.iter().zip(&contents).enumerate() {
assert_eq!(got, want, "link {i} of the chain did not reconstruct");
}
// And prove the chain is real rather than 51 base objects: the last entry
// must be far smaller than the object it reconstructs.
let last = match &entries[DEPTH] {
PackEntry::OfsDelta { delta, .. } => delta.len(),
PackEntry::Base { .. } => unreachable!(),
};
assert!(
last < contents[DEPTH].len() / 10,
"the depth-{DEPTH} delta is {last} bytes against a {} byte object, which is no delta",
contents[DEPTH].len()
);
}
/// A corpus of near-duplicate revisions plus some objects that delta to nothing,
/// so no test built on it is a monoculture.
fn revisions() -> Vec<Vec<u8>> {
let mut contents: Vec<Vec<u8>> = Vec::new();
let seed = noise(12, 40_000);
for rev in 0..40 {
let mut c = seed.clone();
let stamp = format!("=== revision {rev:03} ===\n").into_bytes();
for at in (0..c.len() - 64).step_by(3_000) {
c.splice(at..at + stamp.len(), stamp.iter().copied());
}
c.truncate(c.len() - rev * 11);
contents.push(c);
}
for k in 0..10 {
contents.push(noise(100 + k, 3_000 + k as usize * 700));
}
contents
}
/// Run the window driver over `contents`, pack whatever it produced, and demand
/// that gix reconstructs every entry byte-for-byte. Returns the driver's output
/// so a caller can assert on the shape it got.
#[track_caller]
fn deltify_and_reconstruct(contents: &[Vec<u8>], opts: &Options) -> Vec<gunnar_delta::Deltified> {
let objects: Vec<Object<'_>> = contents
.iter()
.map(|c| Object {
id: support::object_id(Kind::Blob, c),
kind: Kind::Blob,
name_hash: 0,
epoch: 0,
data: c.as_slice(),
})
.collect();
let out = deltify(
&objects,
opts,
&mut gix_utils::progress::Discard,
&AtomicBool::default(),
)
.expect("deltify");
assert_eq!(out.len(), objects.len());
let entries: Vec<PackEntry> = out
.iter()
.map(|d| match (&d.data, d.base) {
(Some(delta), Some(base)) => PackEntry::OfsDelta {
kind: Kind::Blob,
base,
delta: delta.clone(),
},
(None, None) => PackEntry::Base {
kind: Kind::Blob,
data: contents[d.source].clone(),
},
_ => panic!("a Deltified must carry a base and bytes together, or neither"),
})
.collect();
let pack = write_pack(&entries);
let dir = tempfile::tempdir().expect("tempdir");
let decoded = decode_all_with_gix(&pack, dir.path());
for (i, d) in out.iter().enumerate() {
assert_eq!(
decoded[i], contents[d.source],
"entry {i} (source object {}) did not reconstruct",
d.source
);
}
out
}
/// The window driver's output, put in a pack and reconstructed. This is the test
/// that would catch a base index pointing at the wrong object, which no
/// single-pair test can see.
#[test]
fn a_whole_deltified_object_set_reconstructs() {
let contents = revisions();
let out = deltify_and_reconstruct(&contents, &Options::default());
assert!(
out.iter().filter(|d| d.is_delta()).count() >= 35,
"only {} of {} objects deltified. The window found nothing, which for 40 near-duplicate \
revisions means the search is broken, not that the data is incompressible",
out.iter().filter(|d| d.is_delta()).count(),
out.len()
);
}
/// **The fallback re-encode reconstructs too.**
///
/// When an object's best base is already at the depth limit, `resolve_chains`
/// drops to the next-best candidate and encodes that pair *again*: a second,
/// serial call to the encoder with a base the parallel phase did not choose. It
/// is the only place in the crate where the delta that ships is not the delta
/// the window search produced, and at the default depth of 50 over a corpus like
/// this it essentially never runs. `determinism.rs` reaches it, but only asserts
/// depths and back-pointers; nothing has ever decoded its bytes.
///
/// A tight depth limit forces it on nearly every object, and then the assertion
/// is the usual one: gix reconstructs every entry exactly.
#[test]
fn a_tight_depth_limit_forces_the_fallback_re_encode_and_it_still_reconstructs() {
let contents = revisions();
for depth in [1usize, 2, 3] {
let out = deltify_and_reconstruct(
&contents,
&Options {
depth,
..Options::default()
},
);
let deepest = out.iter().map(|d| d.depth).max().unwrap_or(0) as usize;
assert_eq!(
deepest, depth,
"the depth limit of {depth} was never reached, so nothing fell back and this \
iteration proved nothing"
);
// A base at the limit with a delta hanging off something else is the
// shape that only exists because a fallback happened.
let at_limit = out.iter().filter(|d| d.depth as usize == depth).count();
assert!(
at_limit > 0 && out.iter().any(|d| d.is_delta()),
"depth {depth}: {at_limit} entries at the limit, so the fallback path was not taken"
);
}
}