//! 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
}
// ---------------------------------------------------------------------------
// 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 std.testing.checkAllAllocationFailures(std.testing.allocator, createNoLeak, .{ "src", "some target bytes" });
}
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 std.testing.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));
}
}