//! Unit tests for the delta format (draft-fossil-delta-format-00).
//!
//! Separated from the implementation per the kind-separation convention
//! (mirrors the sibling `*_fuzz.zig` split). Every test here exercises only
//! `delta`'s public surface; tests reaching file-private decls stay inline in
//! `delta.zig`.
const std = @import("std");
const delta = @import("delta.zig");
test "delta §3.1: base-64 integer round-trips (MSB-first)" {
var buf: [6]u8 = undefined;
for ([_]u32{ 0, 1, 63, 64, 4095, 100000, 0xFFFF_FFFF }) |v| {
const enc = delta.encodeInt(v, &buf);
const dec = try delta.decodeInt(enc);
try std.testing.expectEqual(v, dec.value);
try std.testing.expectEqual(enc.len, dec.len);
}
}
test "delta §3.1: decodeInt rejects an integer that reaches 2^32" {
// "400000" = 4*64^5 = 2^32: §3.1 lets a decoder reject >= 2^32, and the
// strict posture avoids the silent u32 wrap the naive accumulator would do.
try std.testing.expectError(delta.Error.MalformedDelta, delta.decodeInt("400000"));
// 2^32 - 1 is the largest in-range value and must still decode.
const max = try delta.decodeInt("3~~~~~");
try std.testing.expectEqual(@as(u32, 0xFFFF_FFFF), max.value);
}
test "delta §3.1: encodeInt is most-significant-digit first" {
var buf: [6]u8 = undefined;
// 64 = 1*64 + 0 -> "10" (MSB first), not "01".
try std.testing.expectEqualStrings("10", delta.encodeInt(64, &buf));
try std.testing.expectEqualStrings("0", delta.encodeInt(0, &buf));
}
test "delta §6: high-bit byte terminates integer accumulation" {
// §6 lines 565-567: bytes 0x80-0xFF are outside the 64-character
// alphabet and MUST terminate, not extend, an integer in progress.
// Table over the full range so a future switch to a masked lookup
// (`b & 0x7f`) regresses loudly rather than passing on a spot check.
var b: u16 = 0x80;
while (b <= 0xFF) : (b += 1) {
const byte: u8 = @intCast(b);
const dec = try delta.decodeInt(&[_]u8{ '1', byte });
try std.testing.expectEqual(@as(u32, 1), dec.value);
try std.testing.expectEqual(@as(usize, 1), dec.len);
}
}
test "delta §6: masking the high bit would diverge on a crafted digit byte" {
// 0xB0 = 0x30 | 0x80 = '0' | 0x80. §6 lines 567-570: a decoder that
// masks the high bit before lookup would read this as digit '0' and
// keep accumulating: (1*64+0)*64+2 = 4098, len 3 - "a parse result
// that diverges from conformant implementations". Conformant: 0xB0
// terminates at index 1; the trailing '2' is never reached.
const dec = try delta.decodeInt(&[_]u8{ '1', 0xB0, '2' });
try std.testing.expectEqual(@as(u32, 1), dec.value);
try std.testing.expectEqual(@as(usize, 1), dec.len);
}
test "delta §6: a high-bit byte in count position is rejected by apply" {
// Header declares target_len 3; the segment's count integer starts
// with 0xB0, which terminates immediately (count = 0, consuming zero
// bytes), so the opcode byte examined is 0xB0 itself - not in
// {@, :, ;} - matrix #10 (unknown opcode). Confirms the §6 terminator
// behavior propagates through the real decode path, not just the
// isolated codec.
try expectMalformed("abc", "3\n" ++ &[_]u8{0xB0} ++ "@0,");
}
test "delta §6: conformant encoder never emits a byte >= 0x80" {
// §6 line 571: "Well-formed deltas are unaffected, as conformant
// encoders never emit such bytes." digit64 (§3.1) spans 0x30-0x7E.
var buf: [6]u8 = undefined;
for ([_]u32{ 0, 1, 63, 64, 0xFFFF_FFFF }) |v| {
const enc = delta.encodeInt(v, &buf);
for (enc) |byte| try std.testing.expect(byte < 0x80);
}
const target = "the quick brown fox jumps over the lazy dog";
const d = try delta.create(std.testing.allocator, "source text", target);
defer std.testing.allocator.free(d);
for (d) |byte| try std.testing.expect(byte < 0x80);
}
test "checksum: modulo 2^32, big-endian words + tail (Section 3.4)" {
try std.testing.expectEqual(@as(u32, 0), delta.checksum(""));
try std.testing.expectEqual(@as(u32, 42), delta.checksum(&[_]u8{ 0, 0, 0, 42 }));
try std.testing.expectEqual(@as(u32, 0x0100_0000), delta.checksum(&[_]u8{1})); // 1-byte tail
try std.testing.expectEqual(@as(u32, 0x0000_2A00), delta.checksum(&[_]u8{ 0, 0, 42 })); // 3-byte tail
}
test "checksum: sliced-word form agrees with the §3.4 formula at every length" {
// checksum() slices its whole words off up front so the walk is a bounded
// counter; §3.4 is stated as an indexed loop. This runs both over the same
// bytes at every length through 64 words, so each word count meets each of
// the four tail cases.
var buf: [259]u8 = undefined;
var r = VecRng.init(0xC4EC_5011);
r.fill(&buf);
for (0..buf.len + 1) |n| {
const data = buf[0..n];
var want: u32 = 0;
var i: usize = 0;
while (i + 4 <= data.len) : (i += 4) {
want +%= (@as(u32, data[i]) << 24) | (@as(u32, data[i + 1]) << 16) |
(@as(u32, data[i + 2]) << 8) | @as(u32, data[i + 3]);
}
const rem = data.len - i;
if (rem >= 1) want +%= @as(u32, data[i]) << 24;
if (rem >= 2) want +%= @as(u32, data[i + 1]) << 16;
if (rem >= 3) want +%= @as(u32, data[i + 2]) << 8;
try std.testing.expectEqual(want, delta.checksum(data));
}
}
// ---------------------------------------------------------------------------
// apply() — Section 4 procedure and rejection matrix.
// ---------------------------------------------------------------------------
fn expectMalformed(source: []const u8, delta_bytes: []const u8) !void {
try std.testing.expectError(delta.Error.MalformedDelta, delta.apply(std.testing.allocator, source, delta_bytes));
}
fn expectChecksumMismatch(source: []const u8, delta_bytes: []const u8) !void {
try std.testing.expectError(delta.Error.ChecksumMismatch, delta.apply(std.testing.allocator, source, delta_bytes));
}
test "delta §4: worked example reconstructs the 151-byte target" {
// Appendix B.1: 102-byte source, 151-byte target, 79-byte delta.
const source = "The quick brown fox jumps over the lazy dog. A Fossil delta encodes byte-level differences compactly.\n";
const target = "The quick brown fox jumps over the sleeping fox. A Fossil delta encodes byte-level differences compactly.\n An example delta target with appended tail.\n";
const delta_bytes = "2N\n" ++ "Z@0," ++ "C:" ++ "sleeping fox" ++ "w@g," ++ "i:" ++ " An example delta target with appended tail.\n" ++ "2P4rrX" ++ ";";
try std.testing.expectEqual(@as(usize, 102), source.len);
try std.testing.expectEqual(@as(usize, 151), target.len);
try std.testing.expectEqual(@as(usize, 79), delta_bytes.len);
const result = try delta.apply(std.testing.allocator, source, delta_bytes);
defer std.testing.allocator.free(result);
try std.testing.expectEqualStrings(target, result);
try std.testing.expectEqual(@as(usize, 151), result.len);
// B.1/B.3: trailer 2P4rrX decodes to 2568187297 (0x99136DA1), matching
// checksum() applied independently to the target.
try std.testing.expectEqual(@as(u32, 2568187297), delta.checksum(target));
}
test "delta §4: empty-target delta 0\\n0; is accepted" {
// Appendix B.4: header 0, no segments, trailer checksum 0 (of a 0-byte output).
const result = try delta.apply(std.testing.allocator, "", "0\n0;");
defer std.testing.allocator.free(result);
try std.testing.expectEqual(@as(usize, 0), result.len);
}
test "delta §4: zero-length delta is rejected" {
try expectMalformed("", "");
}
test "delta §4: header integer not followed by 0x0a is rejected" {
try expectMalformed("", "1:a;");
}
test "delta §4: integer accumulation exhausting the buffer is rejected" {
try expectMalformed("", "5\n9");
}
test "delta §4: copy segment without a comma is rejected" {
try expectMalformed("abcdef", "3\n3@0;");
}
test "delta §4: copy past the target length is rejected" {
try expectMalformed("abcdef", "2\n3@0,");
}
test "delta §4: copy past the source end is rejected" {
try expectMalformed("abc", "5\n5@0,");
}
test "delta §4: literal past the target length is rejected" {
try expectMalformed("", "2\n5:hello;");
}
test "delta §4: literal count exceeding remaining delta is rejected" {
try expectMalformed("", "9\n5:ab");
}
test "delta §4: checksum mismatch is rejected" {
// checksum("A") = 0x41000000 (1-byte tail, §3.4); trailer int here is 0.
try expectChecksumMismatch("", "1\n1:A0;");
}
test "delta §4: output shorter than target length is rejected" {
try expectMalformed("", "5\n1:A0;");
}
test "delta §4: unknown opcode byte is rejected" {
try expectMalformed("abc", "3\n3!");
}
test "delta §4: delta ending without ';' is rejected" {
try expectMalformed("abc", "3\n3@0,");
}
// ---------------------------------------------------------------------------
// §4 segmentation independence and §4.1 target-size query.
// ---------------------------------------------------------------------------
test "delta §4: differently-segmented deltas for one target are all accepted" {
// source = target = "AB" (2 bytes); trailer 11GW00 = base-64 MSB-first
// encoding of checksum("AB") = 0x41420000 (§3.4: one 2-byte tail word,
// 'A'<<24 | 'B'<<16). A decoder MUST NOT reject any of these on the
// grounds of segmentation, copy-vs-literal choice, or segment count.
const source = "AB";
const target = "AB";
const deltas = [_][]const u8{
"2\n2@0,11GW00;", // single copy
"2\n1:A1:B11GW00;", // two literals
"2\n2:AB11GW00;", // single literal
};
var i: usize = 0;
while (i < deltas.len) : (i += 1) {
const result = try delta.apply(std.testing.allocator, source, deltas[i]);
defer std.testing.allocator.free(result);
try std.testing.expectEqualStrings(target, result);
}
}
test "delta §4.1: target-size query reads only the header, not later bytes" {
// "2N" = 2*64 + 23 ('N' is digit64 value 23) = 151, the Appendix B.1
// target length. Each tail is malformed or unrelated; none is read.
const cases = [_][]const u8{
"2N\n",
"2N\nZ@0,<garbage>",
"2N\n!!!bad-opcode",
"2N\n" ++ "Z@0," ++ "C:" ++ "sleeping fox" ++ "w@g," ++ "i:" ++ " An example delta target with appended tail.\n" ++ "2P4rrX" ++ ";",
};
var i: usize = 0;
while (i < cases.len) : (i += 1) {
try std.testing.expectEqual(@as(usize, 151), try delta.targetSize(cases[i]));
}
}
test "delta §4.1: target-size query rejects an empty buffer" {
try std.testing.expectError(delta.Error.MalformedDelta, delta.targetSize(""));
}
test "delta §4.1: target-size query rejects a header not immediately followed by 0x0a" {
// "5": the integer runs to the buffer end, so nothing follows it at all.
// "5 \n": 0x20 is not a DIGIT64 char (§3.1), so decodeInt stops after '5'
// and the next byte is a space, not 0x0a.
const cases = [_][]const u8{ "5", "5 \n" };
var i: usize = 0;
while (i < cases.len) : (i += 1) {
try std.testing.expectError(delta.Error.MalformedDelta, delta.targetSize(cases[i]));
}
}
test "delta §4.1: no bytes required after the header LF" {
try std.testing.expectEqual(@as(usize, 0), try delta.targetSize("0\n"));
try std.testing.expectEqual(@as(usize, 151), try delta.targetSize("2N\n"));
}
// ---------------------------------------------------------------------------
// create() — Section 5 encoder notes.
// ---------------------------------------------------------------------------
test "delta §5: create() then apply() round-trips the target" {
const long_source = "The quick brown fox jumps over the lazy dog. A Fossil delta encodes byte-level differences compactly.\n";
const long_target = "The quick brown fox jumps over the sleeping fox. A Fossil delta encodes byte-level differences compactly.\n An example delta target with appended tail.\n";
const embedded = "line1\nline2:tag@marker;end\x00\xff";
const cases = [_]struct { source: []const u8, target: []const u8 }{
.{ .source = "", .target = "" }, // empty target, zero-length source
.{ .source = "x", .target = "" }, // empty target, nonzero source
.{ .source = "", .target = "A" }, // single byte, zero-length source
.{ .source = "abcdefghijklmnop", .target = "z" }, // source == 16 bytes (boundary)
.{ .source = "abcdefghijklmnopq", .target = "z" }, // source > 16 bytes
.{ .source = "abc", .target = embedded }, // embedded 0x0a, ':', '@', ';', 0x00, 0xff
.{ .source = long_source, .target = long_target }, // Appendix B.1 sizes (102/151 bytes)
};
var i: usize = 0;
while (i < cases.len) : (i += 1) {
const d = try delta.create(std.testing.allocator, cases[i].source, cases[i].target);
defer std.testing.allocator.free(d);
const out = try delta.apply(std.testing.allocator, cases[i].source, d);
defer std.testing.allocator.free(out);
try std.testing.expectEqualStrings(cases[i].target, out);
}
}
test "delta §5: create() compresses a target that overlaps the source" {
// The delta's purpose (§5): exploit shared runs. For a source > 16 bytes and
// a target that shares a long prefix/suffix, the encoder MUST emit at least
// one copy and the delta MUST be strictly smaller than the target — a
// literal-only producer would fail both.
const source = "The quick brown fox jumps over the lazy dog and keeps on running.\n";
const target = "The quick brown fox jumps over the lazy dog and then stops running.\n";
const d = try delta.create(std.testing.allocator, source, target);
defer std.testing.allocator.free(d);
try std.testing.expect(std.mem.indexOfScalar(u8, d, '@') != null); // used a copy
try std.testing.expect(d.len < target.len); // actually compressed
const out = try delta.apply(std.testing.allocator, source, d);
defer std.testing.allocator.free(out);
try std.testing.expectEqualStrings(target, out); // and still reconstructs exactly
}
test "delta §5: create() emits a §3.3 literal and §3.4 trailer" {
// checksum("A") = 0x41000000 (1-byte tail, §3.4); encodeInt(0x41000000)
// (§3.1, remainders LSB->MSB 0,0,0,0,1,1, MSB-first) = "110000".
const d = try delta.create(std.testing.allocator, "unused source", "A");
defer std.testing.allocator.free(d);
try std.testing.expectEqualStrings("1\n1:A110000;", d);
}
test "delta §B.4: create() of an empty target is 0\\n0;" {
const d = try delta.create(std.testing.allocator, "any source at all", "");
defer std.testing.allocator.free(d);
try std.testing.expectEqualStrings("0\n0;", d);
}
test "delta §5: source <= 16 bytes yields a single literal (no copy)" {
const source = "ABCDEFGHIJKLMNOP"; // 16 bytes, boundary
const target = "ABCDEFGHIJKLMNOP";
const d = try delta.create(std.testing.allocator, source, target);
defer std.testing.allocator.free(d);
try std.testing.expectEqual(@as(?usize, null), std.mem.indexOfScalar(u8, d, '@'));
try std.testing.expectEqualStrings("G\nG:", d[0..4]); // 16 = 'G' (§3.1: A=10..G=16)
try std.testing.expectEqualStrings(target, d[4..20]);
try std.testing.expectEqual(@as(u8, ';'), d[d.len - 1]);
const trailer = try delta.decodeInt(d[20 .. d.len - 1]);
try std.testing.expectEqual(delta.checksum(target), trailer.value);
}
test "delta §3.1: create() rejects a target of 2^32 bytes or more" {
if (@bitSizeOf(usize) < 33) return; // a length >= 2^32 is unrepresentable on 32-bit
var byte: u8 = 0;
const len: usize = @as(usize, 1) << 32;
const huge_target = @as([*]const u8, @ptrCast(&byte))[0..len]; // never dereferenced past index 0: the guard returns first
try std.testing.expectError(delta.CreateError.TargetTooLarge, delta.create(std.testing.allocator, "", huge_target));
}
fn createNoLeak(allocator: std.mem.Allocator, source: []const u8, target: []const u8) !void {
const out = try delta.create(allocator, source, target);
allocator.free(out);
}
test "delta §5: create() propagates allocation failure" {
try @import("no_grow_allocator.zig").checkAllAllocationFailures(std.testing.allocator, createNoLeak, .{ "src", "some target bytes" });
}
test "delta §5: create() propagates allocation failure while building the block index" {
// The case above uses a 3-byte source, which never builds an index at all.
// A source longer than encoder_block reaches the index's own allocations,
// including the partial failure where the slot array is already held and
// the key array is the one that fails.
try @import("no_grow_allocator.zig").checkAllAllocationFailures(std.testing.allocator, createNoLeak, .{
"a source comfortably longer than one encoder_block, with a repeated tail, tail, tail",
"a source comfortably longer than one encoder_block, and then some quite different bytes, tail",
});
}
fn applyNoLeak(allocator: std.mem.Allocator, source: []const u8, delta_bytes: []const u8) !void {
const out = try delta.apply(allocator, source, delta_bytes);
allocator.free(out);
}
test "delta §4: apply propagates allocation failure" {
// Reuses the Appendix B.1 worked example: a valid delta that exercises
// apply()'s one allocation site (the output buffer) under a failing
// allocator, confirming the errdefer frees it on every failure point.
const source = "The quick brown fox jumps over the lazy dog. A Fossil delta encodes byte-level differences compactly.\n";
const delta_bytes = "2N\n" ++ "Z@0," ++ "C:" ++ "sleeping fox" ++ "w@g," ++ "i:" ++ " An example delta target with appended tail.\n" ++ "2P4rrX" ++ ";";
try @import("no_grow_allocator.zig").checkAllAllocationFailures(std.testing.allocator, applyNoLeak, .{ source, delta_bytes });
}
// ---------------------------------------------------------------------------
// Seeded deterministic fuzz / property tests. A fixed seed drives every draw,
// so a failure reproduces exactly and each block runs under plain `zig build
// test`. The 0.16 coverage-guided std.testing.fuzz (Smith) harness is an
// optional add-on, not relied on here.
// ---------------------------------------------------------------------------
test "delta fuzz: apply on arbitrary source+delta never crashes (§4 robustness)" {
const a = std.testing.allocator;
var prng = std.Random.DefaultPrng.init(0xF0FA_0001);
const rand = prng.random();
var round: usize = 0;
while (round < 400) : (round += 1) {
var sbuf: [128]u8 = undefined;
var dbuf: [160]u8 = undefined;
const slen = rand.uintLessThan(usize, sbuf.len + 1);
const dlen = rand.uintLessThan(usize, dbuf.len + 1);
for (sbuf[0..slen]) |*b| b.* = rand.int(u8);
// Bias delta bytes toward DIGIT64/opcodes so inputs reach deep into the
// decoder rather than being rejected at byte 0.
for (dbuf[0..dlen]) |*b| b.* = if (rand.boolean())
rand.int(u8)
else
delta.digit64[rand.uintLessThan(usize, delta.digit64.len)];
// Contract: a value or a declared error — never a crash or UB.
if (delta.apply(a, sbuf[0..slen], dbuf[0..dlen])) |out| a.free(out) else |_| {}
}
}
test "delta fuzz: apply(source, create(source, target)) == target (§5 round-trip)" {
const a = std.testing.allocator;
var prng = std.Random.DefaultPrng.init(0xF0FA_0002);
const rand = prng.random();
var round: usize = 0;
while (round < 400) : (round += 1) {
var sbuf: [256]u8 = undefined;
const slen = rand.uintLessThan(usize, sbuf.len + 1);
for (sbuf[0..slen]) |*b| b.* = rand.int(u8);
const source = sbuf[0..slen];
// Build target from a mix of source runs (exercises copies) and fresh
// random bytes (exercises literals).
var tbuf: [384]u8 = undefined;
const tlen = rand.uintLessThan(usize, tbuf.len + 1);
var t: usize = 0;
while (t < tlen) {
if (slen >= 8 and rand.boolean()) {
const start = rand.uintLessThan(usize, slen);
const run = 1 + rand.uintLessThan(usize, @min(slen - start, tlen - t));
@memcpy(tbuf[t..][0..run], source[start..][0..run]);
t += run;
} else {
tbuf[t] = rand.int(u8);
t += 1;
}
}
const target = tbuf[0..tlen];
const d = try delta.create(a, source, target);
defer a.free(d);
const out = try delta.apply(a, source, d);
defer a.free(out);
try std.testing.expectEqualSlices(u8, target, out);
}
}
test "delta fuzz: decodeInt on arbitrary digit strings stays bounded (§3.1)" {
var prng = std.Random.DefaultPrng.init(0xF0FA_0003);
const rand = prng.random();
var round: usize = 0;
while (round < 400) : (round += 1) {
var buf: [40]u8 = undefined;
const len = rand.uintLessThan(usize, buf.len + 1);
// Bias toward DIGIT64 so long all-digit runs (overflow candidates) occur.
for (buf[0..len]) |*b| b.* = if (rand.uintLessThan(u8, 4) == 0)
rand.int(u8)
else
delta.digit64[rand.uintLessThan(usize, delta.digit64.len)];
if (delta.decodeInt(buf[0..len])) |dec| {
try std.testing.expect(dec.len <= len); // consumed no more than the input
} else |err| {
try std.testing.expect(err == error.MalformedDelta); // rejection is the only error
}
}
}
test "delta fuzz: targetSize on arbitrary bytes never crashes (§4.1 robustness)" {
var prng = std.Random.DefaultPrng.init(0xF0FA_0004);
const rand = prng.random();
var round: usize = 0;
while (round < 400) : (round += 1) {
var buf: [64]u8 = undefined;
const len = rand.uintLessThan(usize, buf.len + 1);
for (buf[0..len]) |*b| b.* = if (rand.boolean())
rand.int(u8)
else
delta.digit64[rand.uintLessThan(usize, delta.digit64.len)];
// Contract: a value bounded by decodeInt's u32 cap, or MalformedDelta
// — never a crash or UB.
if (delta.targetSize(buf[0..len])) |size| {
try std.testing.expect(size <= std.math.maxInt(u32));
} else |err| {
try std.testing.expect(err == error.MalformedDelta);
}
}
}
test "delta fuzz: create rejects synthetic sizes >= 2^32 without panicking (§3.1)" {
if (@bitSizeOf(usize) < 33) return; // a length >= 2^32 is unrepresentable on 32-bit
var prng = std.Random.DefaultPrng.init(0xF0FA_0005);
const rand = prng.random();
var byte: u8 = 0;
const min_len: usize = @as(usize, 1) << 32;
const max_span: usize = (@as(usize, 1) << 40) - min_len;
var round: usize = 0;
while (round < 200) : (round += 1) {
const len = min_len + rand.uintLessThan(usize, max_span + 1);
const huge = @as([*]const u8, @ptrCast(&byte))[0..len]; // never dereferenced: the guard returns first
const variant = rand.uintLessThan(u8, 3); // 0: source oversized, 1: target oversized, 2: both
const source: []const u8 = if (variant == 1) "" else huge;
const target: []const u8 = if (variant == 0) "" else huge;
try std.testing.expectError(delta.CreateError.TargetTooLarge, delta.create(std.testing.allocator, source, target));
}
}
test "create: match extension stops on each of its three causes (§5)" {
// The extension walk was reshaped from two running bounds into a counter
// over two equal-length slices. Its stop condition has exactly three causes;
// each case below puts it on one of them and pins the resulting delta byte
// for byte, so a copy that runs one byte short or one byte long is a failure
// rather than a merely different-but-valid encoding.
const Case = struct { name: []const u8, source: []const u8, target: []const u8, copy_len: u32, tail: []const u8 };
const cases = [_]Case{
// Source runs out first: the copy takes all 20 source bytes, the extra
// target byte falls out as the closing literal.
.{ .name = "source exhausted", .source = "0123456789abcdefWXYZ", .target = "0123456789abcdefWXYZ!", .copy_len = 20, .tail = "1:!" },
// Target runs out first: the copy stops at 20 even though the source has
// two more matching-length bytes to offer.
.{ .name = "target exhausted", .source = "0123456789abcdefWXYZ!!", .target = "0123456789abcdefWXYZ", .copy_len = 20, .tail = "" },
// A differing byte stops it two bytes into the extension.
.{ .name = "bytes differ", .source = "0123456789abcdefWXYZ", .target = "0123456789abcdefWXQQ", .copy_len = 18, .tail = "2:QQ" },
};
for (cases) |c| {
var ibuf: [6]u8 = undefined;
var want: std.ArrayList(u8) = .empty;
defer want.deinit(std.testing.allocator);
try want.appendSlice(std.testing.allocator, delta.encodeInt(@intCast(c.target.len), &ibuf));
try want.append(std.testing.allocator, '\n');
try want.appendSlice(std.testing.allocator, delta.encodeInt(c.copy_len, &ibuf));
try want.appendSlice(std.testing.allocator, "@0,"); // the only indexed block is at offset 0
try want.appendSlice(std.testing.allocator, c.tail);
try want.appendSlice(std.testing.allocator, delta.encodeInt(delta.checksum(c.target), &ibuf));
try want.append(std.testing.allocator, ';');
const d = try delta.create(std.testing.allocator, c.source, c.target);
defer std.testing.allocator.free(d);
std.testing.expectEqualSlices(u8, want.items, d) catch |err| {
std.debug.print("extension case '{s}' diverged\n", .{c.name});
return err;
};
const back = try delta.apply(std.testing.allocator, c.source, d);
defer std.testing.allocator.free(back);
try std.testing.expectEqualSlices(u8, c.target, back);
}
}
// ---------------------------------------------------------------------------
// Pinned encoder vectors (§5)
//
// §5 is informative: any copy/literal segmentation that reproduces the target
// is a valid delta, so nothing in the format forces THIS encoder's choices.
// These vectors pin them anyway. They were captured from the encoder as it
// stood at fossil check-in 4a7c197abd and exist so that a change made for
// speed has to prove it changed no bytes -- byte-identity is the contract the
// stores on disk are compared under, and a reshaped encoder that emits a
// different (even smaller) delta is a different encoder, not a faster one.
//
// Between them the cases pin: the no-index path for a source of encoder_block
// bytes or fewer; the first indexable source (17 bytes); a pure-literal
// encoding; a long match extension; the index's latest-offset-per-key rule
// (case 7 must copy from offset 32, not 0 or 16); the fact that a run shared
// at an unindexed source offset yields no copy (case 8); a match window ending
// exactly at target.len; wholly repetitive input; a target longer than its
// source; a multi-KB mixed edit; and 512 near-identical blocks whose keys
// stress an index's probe behaviour.
// ---------------------------------------------------------------------------
/// xorshift64* written out longhand: the vectors must not move if std's
/// Random implementation ever changes.
const VecRng = struct {
s: u64,
fn init(seed: u64) VecRng {
return .{ .s = seed | 1 };
}
fn next(self: *VecRng) u64 {
var x = self.s;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.s = x;
return x *% 0x2545F4914F6CDD1D;
}
fn byte(self: *VecRng) u8 {
return @truncate(self.next() >> 33);
}
fn below(self: *VecRng, n: usize) usize {
return @intCast(self.next() % n);
}
fn fill(self: *VecRng, buf: []u8) void {
for (buf) |*b| b.* = self.byte();
}
};
const VecCase = struct {
name: []const u8,
source: []const u8,
target: []const u8,
};
const vec_case_count = 14;
/// Build case `i`. Every returned slice is owned by `arena`.
fn buildCase(arena: std.mem.Allocator, i: usize) !VecCase {
switch (i) {
// --- degenerate ------------------------------------------------
0 => return .{ .name = "empty source, empty target", .source = "", .target = "" },
1 => return .{ .name = "empty source, short target", .source = "", .target = "hello, delta" },
2 => return .{ .name = "source shorter than encoder_block", .source = "0123456789abcde", .target = "0123456789abcde0123456789abcde" },
3 => return .{ .name = "source exactly encoder_block", .source = "0123456789abcdef", .target = "0123456789abcdef0123456789abcdef" },
// --- first indexed source (17 bytes) ---------------------------
4 => return .{ .name = "source one byte past encoder_block", .source = "0123456789abcdefg", .target = "0123456789abcdefg" },
// --- literal only ----------------------------------------------
5 => {
const src = try arena.alloc(u8, 4096);
const tgt = try arena.alloc(u8, 4096);
var r = VecRng.init(0x51ED);
r.fill(src);
var r2 = VecRng.init(0xC0FFEE);
r2.fill(tgt);
return .{ .name = "literal only (independent random source/target)", .source = src, .target = tgt };
},
// --- long match extension --------------------------------------
6 => {
const src = try arena.alloc(u8, 4096);
var r = VecRng.init(0xA11CE);
r.fill(src);
return .{ .name = "long extension: target is an interior run of source", .source = src, .target = src[100..3000] };
},
// --- last-wins index semantics ---------------------------------
7 => {
// Same 16-byte block at aligned offsets 0, 16 and 32. The index
// keeps the LAST offset per hash, so the copy must name 32.
const blk = "BLOCKblockBLOCKb";
var buf: std.ArrayList(u8) = .empty;
try buf.appendSlice(arena, blk);
try buf.appendSlice(arena, blk);
try buf.appendSlice(arena, blk);
try buf.appendSlice(arena, "tail-that-differs-entirely-here!");
return .{ .name = "repeated aligned block pins last-wins index", .source = try buf.toOwnedSlice(arena), .target = blk };
},
// --- unaligned-only match is NOT indexed -----------------------
8 => {
// The only 16-byte run shared with the target starts at source
// offset 7, which no non-overlapping block covers, so the encoder
// must emit a pure literal.
const src = "AAAAAAA" ++ "UNIQUE-RUN-HERE!" ++ "BBBBBBBBBBBBBBBBBBBBBBBBB";
return .{ .name = "shared run at an unindexed offset stays literal", .source = src, .target = "UNIQUE-RUN-HERE!" };
},
// --- boundary: match ends exactly at target end -----------------
9 => {
const src = try arena.alloc(u8, 1024);
var r = VecRng.init(0xBEEF);
r.fill(src);
// target = 32-byte prefix of an aligned source block; the last
// match window ends exactly at target.len.
return .{ .name = "match window ends exactly at target end", .source = src, .target = src[64..96] };
},
// --- highly repetitive -----------------------------------------
10 => {
const src = try arena.alloc(u8, 8192);
@memset(src, 0);
const tgt = try arena.alloc(u8, 8192);
@memset(tgt, 0);
return .{ .name = "all-zero source and target", .source = src, .target = tgt };
},
// --- target longer than source ---------------------------------
11 => {
const src = try arena.alloc(u8, 2048);
var r = VecRng.init(0xD00D);
r.fill(src);
var buf: std.ArrayList(u8) = .empty;
try buf.appendSlice(arena, "prefix that is not in the source at all, padded out a bit");
try buf.appendSlice(arena, src);
try buf.appendSlice(arena, "suffix that is likewise absent from the source entirely");
try buf.appendSlice(arena, src[512..1536]);
return .{ .name = "target longer than source, source embedded twice", .source = src, .target = try buf.toOwnedSlice(arena) };
},
// --- multi-KB mixed edit ---------------------------------------
12 => {
const src = try arena.alloc(u8, 64 * 1024);
var r = VecRng.init(0x5EED_1234);
r.fill(src);
var buf: std.ArrayList(u8) = .empty;
// Three deletions, three insertions, three replacements, applied
// left to right over the source.
var pos: usize = 0;
var e: usize = 0;
while (e < 9) : (e += 1) {
const run = 4096 + r.below(2048);
const end = @min(src.len, pos + run);
try buf.appendSlice(arena, src[pos..end]);
pos = end;
switch (e % 3) {
0 => pos = @min(src.len, pos + 700 + r.below(300)), // delete
1 => { // insert
var ins: [512]u8 = undefined;
r.fill(&ins);
try buf.appendSlice(arena, &ins);
},
else => { // replace
var rep: [333]u8 = undefined;
r.fill(&rep);
try buf.appendSlice(arena, &rep);
pos = @min(src.len, pos + 333);
},
}
}
if (pos < src.len) try buf.appendSlice(arena, src[pos..]);
return .{ .name = "multi-KB mixed insert/delete/replace", .source = src, .target = try buf.toOwnedSlice(arena) };
},
// --- many colliding-bucket blocks -------------------------------
13 => {
// 512 distinct aligned blocks that differ only in their last two
// bytes: dense, adversarial for any index that keys on a prefix.
var buf: std.ArrayList(u8) = .empty;
var k: usize = 0;
while (k < 512) : (k += 1) {
try buf.appendSlice(arena, "commonprefix--");
try buf.append(arena, @truncate(k));
try buf.append(arena, @truncate(k >> 8));
}
const src = try buf.toOwnedSlice(arena);
// target walks the blocks backwards so copies come from all over.
var tb: std.ArrayList(u8) = .empty;
var j: usize = 512;
while (j > 0) {
j -= 1;
try tb.appendSlice(arena, src[j * 16 ..][0..16]);
}
return .{ .name = "512 near-identical aligned blocks, reversed target", .source = src, .target = try tb.toOwnedSlice(arena) };
},
else => unreachable,
}
}
const PinnedVector = struct {
case: usize,
len: usize,
sha3: *const [64]u8,
/// Full delta bytes, for cases small enough to read at a glance.
bytes: ?[]const u8,
};
const pinned_vectors = [_]PinnedVector{
.{ .case = 0, .len = 4, .sha3 = "19ff9322c0314782ad7af024cb2b23ae9463902ba011b92650a03de3d7783c76", .bytes = "0\n0;" },
.{ .case = 1, .len = 22, .sha3 = "23494eb5f5f4cd81b94a861f8ef0ba512dff1b877380ad41c2e556be744b5826", .bytes = "C\nC:hello, deltax~W4m;" },
.{ .case = 2, .len = 40, .sha3 = "c36ea8bd2da5b67c74bc050c8ac71f0a1dde1978ba0cf7e5754ec665338e42c5", .bytes = "U\nU:0123456789abcde0123456789abcde4CkkB;" },
.{ .case = 3, .len = 41, .sha3 = "50eba5631120dc9e2d73623029aecad8e1e9779971bb0e3d342c05915c23d8cd", .bytes = "W\nW:0123456789abcdef0123456789abcdef25u_;" },
.{ .case = 4, .len = 13, .sha3 = "10716f5c2219881506876e88864401bed4bd9f43df80093ab36456b1536706d2", .bytes = "H\nH@0,1c12xn;" },
.{ .case = 5, .len = 4111, .sha3 = "c3c12a6d41cd165bef23ba74585c262196ed1881d87c39cd0db68d2a50d61465", .bytes = null },
.{ .case = 6, .len = 30, .sha3 = "67eaf302c92b6350e0ba3ad52adbe4174d982bfe2bfd561cb29bd4670dfe81e4", .bytes = null },
.{ .case = 7, .len = 13, .sha3 = "ed828127d0c2ecb4b35c19a5186845e84333127922214dae4a6afc9e73800374", .bytes = "G\nG@W,10NKaW;" },
.{ .case = 8, .len = 27, .sha3 = "ddef1240f21819e983ce7c70f907182704f08db9120b7cb46414891d60eb226a", .bytes = "G\nG:UNIQUE-RUN-HERE!15Cz_C;" },
.{ .case = 9, .len = 14, .sha3 = "48886d5d2a4bd41a51c6e5083e9d8a25d092a2fa9a883db421860dc4af6644ce", .bytes = "W\nW@10,1G_qEr;" },
.{ .case = 10, .len = 3078, .sha3 = "e8d02e056139eba9aa68a1551e0a4fa57960079fc6f54bc4c981ca2b6d87f572", .bytes = null },
.{ .case = 11, .len = 137, .sha3 = "be3a89302692b1bf71b76dfeb6a13590035ee30b8f0e6c787191a2c620b4b38c", .bytes = null },
.{ .case = 12, .len = 2696, .sha3 = "e3688ff3364bcb28c1fef15027e8c1e9f7fee9e20d9cef9a80a0be024e85f63f", .bytes = null },
.{ .case = 13, .len = 2443, .sha3 = "235001b67ed0eff6e984af68f7b4175b7a47681774b8f8d3bb69af3dde249e9f", .bytes = null },
};
test "delta §5: create() output is byte-identical to the pinned vectors" {
try std.testing.expectEqual(vec_case_count, pinned_vectors.len);
for (pinned_vectors) |v| {
var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena_state.deinit();
const arena = arena_state.allocator();
const c = try buildCase(arena, v.case);
const d = try delta.create(arena, c.source, c.target);
// The vector is only meaningful if the delta still reconstructs.
const back = try delta.apply(arena, c.source, d);
try std.testing.expectEqualSlices(u8, c.target, back);
if (v.bytes) |want| {
std.testing.expectEqualSlices(u8, want, d) catch |err| {
std.debug.print("pinned vector {d} ({s}) diverged\n", .{ v.case, c.name });
return err;
};
}
var digest: [32]u8 = undefined;
std.crypto.hash.sha3.Sha3_256.hash(d, &digest, .{});
const got = std.fmt.bytesToHex(digest, .lower);
std.testing.expectEqualStrings(v.sha3, &got) catch |err| {
std.debug.print("pinned vector {d} ({s}): {d} bytes, wanted {d}\n", .{ v.case, c.name, d.len, v.len });
return err;
};
try std.testing.expectEqual(v.len, d.len);
}
}