//! Seeded fuzz target for `merge3.zig` — the algebraic laws of the three-way
//! (diff3) line merge.
//!
//! Silent merge corruption is the worst failure mode a version-control system
//! has: unlike a parse error or a checksum mismatch it produces no diagnostic,
//! survives review, and lands in a commit. `merge3` is also the one engine in
//! the tree with no adversarial input to fuzz — it never sees a byte a peer
//! chose, only content the repository already accepted — so garbage-in
//! targeting buys nothing here. What it *does* have is a set of laws that hold
//! for every input triple, and those laws are what this target checks.
//!
//! Five oracles (contracts/merge.md B-merge-1/7):
//!
//! 1. `merge(b, x, b) == x` — only `current` moved: take it verbatim.
//! 2. `merge(b, b, y) == y` — only `other` moved: take it verbatim.
//! 3. `merge(b, x, x) == x` — both sides made the identical change.
//! 4. No invented lines — every output line *outside* a recorded
//! conflict span is a line of `base`, `current`, or `other`.
//! 5. Regions replay — each side's region ranges, concatenated,
//! reproduce that side byte for byte; replaying the regions with the
//! current side for every conflict gives the `-X ours` merge, and with
//! the other side the `-X theirs` merge. This is what lets a caller show
//! a conflict from `Result.regions` without merging a second time.
//!
//! Oracle 4 carries that carve-out because the merger is *supposed* to fabricate
//! lines inside an envelope: `appendEnvelope` emits `<<<<<<< current`,
//! `||||||| base`, `=======`, and `>>>>>>> other`, and `appendRegion` normalizes
//! a region that does not end on a newline by adding one. `Result.conflicts`
//! names exactly those envelopes, and `expectNoInventedLines` validates that
//! claim itself before subtracting anything: every recorded span must be
//! in-bounds, start at or after the previous span's end, open at a line boundary
//! with `conflict_sentinel`, close with `conflict_terminator` — the two markers
//! `appendEnvelope` alone produces — and carry no second terminator inside it.
//! The end-pinning stops a span from being stretched past its own envelope; the
//! ordering and interior-terminator checks stop a span from being stretched
//! *across* two real envelopes to swallow the clean lines between them, which
//! end-pinning alone would admit. Together they mean a span cannot be widened to
//! launder a fabricated line past the carve-out. (The oracle does not lean on
//! `merge3`'s own ordered/disjoint assert for this: that assert lives under
//! `std.debug.runtime_safety` and is erased in the release builds a sweep runs
//! under.)
//! Subtracting the recorded spans therefore leaves precisely the bytes the
//! engine claims it copied,
//! and *those* must be verbatim input. Oracles 1-3 need no such carve-out: by
//! construction at most one side differs from base, so a conflict there cannot
//! be legitimate and the equality check is the right place for it to fail.
//!
//! Deliberately out of scope, and honest about it: `classifyFile`'s
//! presence×equality matrix and the `whole_file_conflict` binary short-circuit
//! (B-merge-21) are decided *above* the line engine and are covered by the
//! example-based tests; this target drives `merge3` only. Conflict *content*
//! (which side lands in which envelope arm) is likewise unchecked — the laws
//! above constrain clean output, not the shape of a conflict.
//!
//! Registered as `merge3_properties` in fuzz_tests.zig; fixed-seed smoke `test`s
//! at the foot delegate to the same pub fn so the laws also run under
//! `zig build test` (and therefore in CI).
const std = @import("std");
const merge3 = @import("merge3.zig");
/// Line counts stay small on purpose. The LCS matcher is O(n*m) per side, and
/// the interesting behavior — region boundaries, adjacent edits, insertions at
/// a sync point — is all reachable within a handful of lines. Small inputs buy
/// orders of magnitude more distinct triples per second than long ones.
const max_lines: usize = 12;
/// Distinct line bodies a generated buffer draws from. Deliberately tiny: a
/// large alphabet makes every line unique, which makes every LCS match trivial
/// and every region the whole file. Repetition is what produces interesting
/// sync points, ambiguous matches, and adjacent-region edges.
const alphabet = [_][]const u8{ "a", "b", "c", "d", "e" };
comptime {
// Tripwire for `expectNoInventedLines`: its span validator reads an interior
// `conflict_terminator` as proof a span was widened across two envelopes.
// That inference holds only because no generated line can itself be marker
// text — every body here is one letter. Growing the alphabet toward `<`/`>`
// would silently weaken the check rather than fail it, so pin the shape.
for (alphabet) |body| {
std.debug.assert(body.len == 1);
std.debug.assert(body[0] != '<' and body[0] != '>');
}
}
/// B-merge-1/7 — the three-way line merge obeys its algebraic laws on every
/// input triple: the three one-sided identities reproduce the moved side byte
/// for byte with no conflict, and outside a recorded conflict span the merger
/// only ever copies lines it was given.
pub fn properties(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
// A zero-round sweep exits 0 and reports a clean run that never happened.
if (rounds == 0) return error.NoRounds;
var prng = std.Random.DefaultPrng.init(seed);
const rand = prng.random();
// Negative space: the corpus has to be able to reach the shapes the oracles
// exist for. If `alphabet` or `max_lines` were later narrowed toward a
// degenerate value every round would merge trivially, all four oracles would
// pass vacuously, and the registration pin in fuzz_tests.zig would still
// report this target as covered. Track the two shapes that matter and fail
// the run if the generators stopped producing them.
//
// Only on a run long enough for absence to mean something: a short run can
// legitimately draw neither shape, and a fuzz target that fails on a valid
// invocation is worse than the rot it guards against. Measured over 200
// seeds per round count: 8 rounds spuriously reports vacuous for 17 seeds,
// 16 rounds for 1, and 32/64/128 rounds for none. `vacuity_floor` sits an
// order of magnitude above the last observed false positive.
const vacuity_floor: usize = 256;
var saw_conflict = false;
var saw_newline_less = false;
var round: usize = 0;
while (round < rounds) : (round += 1) {
const base = try generate(gpa, rand);
defer gpa.free(base);
const current = try mutate(gpa, rand, base);
defer gpa.free(current);
const other = try mutate(gpa, rand, base);
defer gpa.free(other);
for ([_][]const u8{ base, current, other }) |b| {
if (b.len != 0 and b[b.len - 1] != '\n') saw_newline_less = true;
}
// (1)(2)(3) the one-sided identities.
try expectIdentity(gpa, base, current, base, current);
try expectIdentity(gpa, base, base, other, other);
try expectIdentity(gpa, base, current, current, current);
// (4) the full three-way merge invents no lines outside its envelopes.
if (try expectNoInventedLines(gpa, base, current, other)) saw_conflict = true;
// (5) the regions are the merge, told region by region.
try expectRegionsReplay(gpa, base, current, other);
}
if (rounds < vacuity_floor) return;
if (!saw_conflict) {
std.debug.print(
"merge3 fuzz corpus went vacuous: {d} rounds produced no conflict\n",
.{rounds},
);
return error.VacuousCorpus;
}
if (!saw_newline_less) {
std.debug.print(
"merge3 fuzz corpus went vacuous: {d} rounds produced no newline-less buffer\n",
.{rounds},
);
return error.VacuousCorpus;
}
}
/// Oracle 5: the regions tile each input, and replaying them reproduces both
/// resolving strategies' bytes exactly.
fn expectRegionsReplay(gpa: std.mem.Allocator, base: []const u8, current: []const u8, other: []const u8) !void {
const r = try merge3.merge3(gpa, base, current, other, .conflict);
defer r.deinit(gpa);
const sides = [3][]const u8{ base, current, other };
var lines: [3][]merge3.Line = undefined;
for (sides, &lines) |side, *l| l.* = try merge3.splitLines(gpa, side);
defer for (lines) |l| gpa.free(l);
var copies: [3]std.ArrayList(u8) = .{ .empty, .empty, .empty };
defer for (&copies) |*c| c.deinit(gpa);
var ours: std.ArrayList(u8) = .empty;
defer ours.deinit(gpa);
var theirs: std.ArrayList(u8) = .empty;
defer theirs.deinit(gpa);
for (r.regions) |reg| {
const ranges = [3]merge3.LineRange{ reg.base, reg.current, reg.other };
var slices: [3][]const u8 = undefined;
for (ranges, sides, lines, &slices, &copies) |rg, side, l, *sl, *c| {
sl.* = if (rg.lo == rg.hi) "" else side[l[rg.lo].start..l[rg.hi - 1].end];
try c.appendSlice(gpa, sl.*);
}
const o, const a, const b = slices;
switch (reg.kind) {
.same => {
try std.testing.expectEqualStrings(o, a);
try std.testing.expectEqualStrings(o, b);
try ours.appendSlice(gpa, o);
try theirs.appendSlice(gpa, o);
},
.current => {
try std.testing.expectEqualStrings(o, b);
try ours.appendSlice(gpa, a);
try theirs.appendSlice(gpa, a);
},
.other => {
try std.testing.expectEqualStrings(o, a);
try ours.appendSlice(gpa, b);
try theirs.appendSlice(gpa, b);
},
.both => {
try std.testing.expectEqualStrings(a, b);
try ours.appendSlice(gpa, a);
try theirs.appendSlice(gpa, a);
},
.conflict => {
try ours.appendSlice(gpa, a);
try theirs.appendSlice(gpa, b);
},
}
}
for (sides, copies) |side, c| try std.testing.expectEqualStrings(side, c.items);
const ro = try merge3.merge3(gpa, base, current, other, .ours);
defer ro.deinit(gpa);
try std.testing.expectEqualStrings(ro.bytes, ours.items);
const rt = try merge3.merge3(gpa, base, current, other, .theirs);
defer rt.deinit(gpa);
try std.testing.expectEqualStrings(rt.bytes, theirs.items);
}
/// One law of the form `merge(base, current, other) == want`, clean. A conflict
/// here is itself the failure: each caller passes a triple where at most one
/// side differs from `base`, so no region can be both-changed-differently.
fn expectIdentity(
gpa: std.mem.Allocator,
base: []const u8,
current: []const u8,
other: []const u8,
want: []const u8,
) !void {
const r = try merge3.merge3(gpa, base, current, other, .conflict);
defer r.deinit(gpa);
if (merge3.hasConflict(r)) {
std.debug.print(
"merge3 identity: unexpected conflict\n base={f}\n current={f}\n other={f}\n",
.{ Escaped{ .b = base }, Escaped{ .b = current }, Escaped{ .b = other } },
);
return error.UnexpectedConflict;
}
if (!std.mem.eql(u8, want, r.bytes)) {
std.debug.print(
"merge3 identity: wrong bytes\n base={f}\n current={f}\n other={f}\n want={f}\n got={f}\n",
.{
Escaped{ .b = base }, Escaped{ .b = current }, Escaped{ .b = other },
Escaped{ .b = want }, Escaped{ .b = r.bytes },
},
);
return error.IdentityViolated;
}
}
/// Oracle 4. Every line of the merged buffer that lies outside a recorded
/// conflict span must appear verbatim as a line of one of the three inputs.
///
/// A trailing final line with no newline needs no special case: `splitLines`
/// keeps a line's trailing '\n' when it has one, and a newline-less line can
/// only be the final line of its buffer — which `merge3` can only ever emit at
/// the end of the output, where it stays newline-less and compares equal.
fn expectNoInventedLines(
gpa: std.mem.Allocator,
base: []const u8,
current: []const u8,
other: []const u8,
) !bool {
const r = try merge3.merge3(gpa, base, current, other, .conflict);
defer r.deinit(gpa);
// The carve-out below subtracts `r.conflicts` from the output, so a span
// that is not genuinely a conflict envelope would let a fabricated line
// through unnoticed — the oracle would certify whatever the engine chose to
// exempt. Everything the carve-out needs is established here, locally: the
// spans are in-bounds, strictly ordered and disjoint, and each one is an
// envelope. `merge3` asserts the first three itself, but only inside
// `if (std.debug.runtime_safety)`, so a `-Doptimize=ReleaseFast` sweep — the
// build a fuzz run actually uses — erases them; this loop is what the oracle
// relies on, and it holds in every optimize mode.
//
// Every property is load-bearing, because `inAnySpan` matches on overlap: an
// over-long `len` exempts every output line up to its end. Both envelope
// ends are pinned — the span must open at a line boundary with
// `merge3.conflict_sentinel` and close with `merge3.conflict_terminator`,
// and `appendEnvelope` (merge3.zig) is the sole producer of either — but
// end-pinning alone does not foreclose widening once a merge records two
// envelopes, which is the common case rather than an edge one (roughly one
// round in six of this target's own generators). Two widenings have to be
// ruled out separately:
//
// - A span stretched over its neighbor: caught by `ordered`, which
// rejects any span starting before the previous span's end.
// - A single span replacing two envelopes, from the first one's start to
// the last one's end: `ordered` cannot see it — nothing overlaps — and
// it opens and closes correctly. `closes_once` catches it on the first
// envelope's terminator, which such a span necessarily carries in its
// interior.
//
// These are `return error`, not `assert`, for the same erasure reason: an
// assert compiles to nothing under ReleaseFast and the oracle would certify
// unvalidated spans while the arithmetic and slicing below lost their bounds
// precondition.
var prev_end: usize = 0;
for (r.conflicts) |s| {
// Subtraction, not `s.start + s.len`: the add is the thing being
// validated, so it cannot be trusted to compute the comparison.
const in_bounds = s.start <= r.bytes.len and s.len <= r.bytes.len - s.start;
const ordered = s.start >= prev_end;
const opens_aligned = in_bounds and (s.start == 0 or r.bytes[s.start - 1] == '\n');
const span = if (in_bounds) r.bytes[s.start..][0..s.len] else "";
// `conflict_terminator` ends on '\n', so matching it also proves the
// span closes on a line boundary; no separate alignment check needed.
const closes = std.mem.endsWith(u8, span, merge3.conflict_terminator);
// A span stretched across two whole envelopes still opens with the
// sentinel and closes with the terminator, and `ordered` cannot see it
// because it replaced both spans rather than overlapping one. What gives
// it away is the *first* envelope's terminator sitting in its interior:
// a single envelope contains exactly one, at its end. Generated lines
// are single letters (see the tripwire by `alphabet`), so an interior
// match cannot be copied input.
const closes_once = closes and
std.mem.indexOf(u8, span, merge3.conflict_terminator).? ==
span.len - merge3.conflict_terminator.len;
const is_envelope = ordered and opens_aligned and closes_once and
std.mem.startsWith(u8, span, merge3.conflict_sentinel);
if (is_envelope) {
prev_end = s.start + s.len;
continue;
}
std.debug.print(
"merge3 recorded a conflict span that is not an envelope\n span=[{d},{d}) of {d}, prev_end={d}\n base={f}\n current={f}\n other={f}\n merged={f}\n",
.{
s.start,
s.len,
r.bytes.len,
prev_end,
Escaped{ .b = base },
Escaped{ .b = current },
Escaped{ .b = other },
Escaped{ .b = r.bytes },
},
);
return error.MalformedConflictSpan;
}
const out_lines = try merge3.splitLines(gpa, r.bytes);
defer gpa.free(out_lines);
// Split each input once for the whole output, not once per output line.
const base_lines = try merge3.splitLines(gpa, base);
defer gpa.free(base_lines);
const current_lines = try merge3.splitLines(gpa, current);
defer gpa.free(current_lines);
const other_lines = try merge3.splitLines(gpa, other);
defer gpa.free(other_lines);
const srcs = [_]Source{
.{ .bytes = base, .lines = base_lines },
.{ .bytes = current, .lines = current_lines },
.{ .bytes = other, .lines = other_lines },
};
for (out_lines) |line| {
if (inAnySpan(r.conflicts, line)) continue;
const bytes = merge3.lineBytes(r.bytes, line);
if (isInputLine(bytes, &srcs)) continue;
std.debug.print(
"merge3 invented a line outside every conflict span\n line={f}\n base={f}\n current={f}\n other={f}\n merged={f}\n",
.{
Escaped{ .b = bytes }, Escaped{ .b = base }, Escaped{ .b = current },
Escaped{ .b = other }, Escaped{ .b = r.bytes },
},
);
return error.InventedLine;
}
return r.conflicts.len != 0;
}
/// True when `line` overlaps any conflict envelope at all. Overlap rather than
/// containment on purpose: envelopes are line-aligned by construction, so an
/// only-partially-covered line would itself be a bug, and treating it as
/// "inside" would hide that — but a *missed* carve-out produces a confusing
/// false `InventedLine`. Overlap keeps the oracle honest about what it claims:
/// it certifies the bytes the engine says it copied, nothing else.
fn inAnySpan(spans: []const merge3.Span, line: merge3.Line) bool {
for (spans) |s| {
if (line.start < s.start + s.len and s.start < line.end) return true;
}
return false;
}
/// One input buffer with its line index, split once per merge rather than once
/// per output line.
const Source = struct { bytes: []const u8, lines: []const merge3.Line };
/// True when `needle` is byte-identical to some line of one of the inputs.
fn isInputLine(needle: []const u8, srcs: []const Source) bool {
for (srcs) |src| {
for (src.lines) |line| {
if (std.mem.eql(u8, needle, merge3.lineBytes(src.bytes, line))) return true;
}
}
return false;
}
// --- generators ------------------------------------------------------------
/// A buffer of 0..max_lines lines drawn from `alphabet`. One buffer in eight
/// ends without a trailing newline: that is the shape most likely to expose an
/// off-by-one in the line model, and a purely newline-terminated generator
/// would never produce it.
fn generate(gpa: std.mem.Allocator, rand: std.Random) ![]u8 {
var out: std.ArrayList(u8) = .empty;
errdefer out.deinit(gpa);
const n = rand.uintLessThan(usize, max_lines + 1);
var i: usize = 0;
while (i < n) : (i += 1) {
try out.appendSlice(gpa, alphabet[rand.uintLessThan(usize, alphabet.len)]);
try out.append(gpa, '\n');
}
if (n != 0 and rand.uintLessThan(u8, 8) == 0) _ = out.pop();
return out.toOwnedSlice(gpa);
}
/// A derivative of `src`: each line is independently kept, dropped, replaced,
/// or duplicated with a fresh line appended, and one derivative in eight is
/// returned unchanged so the "side did not move" case is sampled often rather
/// than by luck. Per-line edits (rather than one splice) are what produce the
/// adjacent-changed-region and interleaved-edit shapes that make three-way
/// merges hard.
fn mutate(gpa: std.mem.Allocator, rand: std.Random, src: []const u8) ![]u8 {
if (rand.uintLessThan(u8, 8) == 0) return gpa.dupe(u8, src);
const lines = try merge3.splitLines(gpa, src);
defer gpa.free(lines);
var out: std.ArrayList(u8) = .empty;
errdefer out.deinit(gpa);
for (lines) |line| {
const bytes = merge3.lineBytes(src, line);
switch (rand.uintLessThan(u8, 8)) {
0 => {}, // drop
1 => try appendLine(&out, gpa, alphabet[rand.uintLessThan(usize, alphabet.len)]), // replace
2 => { // duplicate, then insert a fresh line after it
try out.appendSlice(gpa, bytes);
if (bytes.len != 0 and bytes[bytes.len - 1] != '\n') try out.append(gpa, '\n');
try appendLine(&out, gpa, alphabet[rand.uintLessThan(usize, alphabet.len)]);
},
else => try out.appendSlice(gpa, bytes), // keep
}
}
if (out.items.len != 0 and rand.uintLessThan(u8, 8) == 0) {
if (out.items[out.items.len - 1] == '\n') _ = out.pop();
}
return out.toOwnedSlice(gpa);
}
fn appendLine(out: *std.ArrayList(u8), gpa: std.mem.Allocator, body: []const u8) !void {
try out.appendSlice(gpa, body);
try out.append(gpa, '\n');
}
/// Newline-visible rendering for failure output. A merge counterexample is a
/// handful of near-identical short buffers; printed raw they are unreadable and
/// the reproduction gets transcribed wrong.
const Escaped = struct {
b: []const u8,
pub fn format(self: Escaped, w: *std.Io.Writer) std.Io.Writer.Error!void {
try w.writeByte('"');
for (self.b) |c| switch (c) {
'\n' => try w.writeAll("\\n"),
'"' => try w.writeAll("\\\""),
'\\' => try w.writeAll("\\\\"),
else => try w.writeByte(c),
};
try w.writeByte('"');
}
};
// ---------------------------------------------------------------------------
// Fixed-seed smoke: the same laws under `zig build test` (and CI), at a round
// count sized for the inner loop rather than for a sweep.
// ---------------------------------------------------------------------------
test "merge3 B-merge-1/7 fuzz: algebraic laws hold on random triples (smoke)" {
try properties(std.testing.allocator, 0x3ed6e3, 512);
}
// The identities are laws, not a sampling: pin the degenerate ends (empty
// buffers, and a newline-less final line on each side) so a regression there
// fails deterministically instead of one seed in a thousand.
test "merge3 B-merge-7: one-sided identities hold at the degenerate ends" {
const gpa = std.testing.allocator;
const cases = [_]struct { base: []const u8, side: []const u8 }{
.{ .base = "", .side = "" },
.{ .base = "", .side = "a\n" },
.{ .base = "a\n", .side = "" },
.{ .base = "a\n", .side = "a" }, // gains/loses the final newline
.{ .base = "a", .side = "a\nb\n" },
.{ .base = "a\nb\nc\n", .side = "a\nc\n" },
.{ .base = "a\nb\nc\n", .side = "a\nb\nb\nc\n" },
};
for (cases) |c| {
try expectIdentity(gpa, c.base, c.side, c.base, c.side);
try expectIdentity(gpa, c.base, c.base, c.side, c.side);
try expectIdentity(gpa, c.base, c.side, c.side, c.side);
}
}
// A both-changed-differently triple is the one shape where the merger legitimately
// fabricates lines. Pin that the carve-out is real: the envelope IS recorded as a
// span, so the no-invented-lines oracle passes rather than being weakened.
test "merge3 B-merge-1: a real conflict is recorded as a span, and the rest is verbatim" {
const gpa = std.testing.allocator;
const r = try merge3.merge3(gpa, "a\nb\nc\n", "a\nX\nc\n", "a\nY\nc\n", .conflict);
defer r.deinit(gpa);
try std.testing.expect(merge3.hasConflict(r));
// Pin span-to-envelope correspondence, not merely "a sentinel exists
// somewhere": the recorded span must be the envelope it claims to be.
try std.testing.expect(r.conflicts.len == 1);
try std.testing.expect(std.mem.startsWith(
u8,
r.bytes[r.conflicts[0].start..],
merge3.conflict_sentinel,
));
try std.testing.expect(try expectNoInventedLines(gpa, "a\nb\nc\n", "a\nX\nc\n", "a\nY\nc\n"));
}
// Oracle 5 on the shapes a forge meets in real files: CRLF lines, a side with
// no final newline, an empty side, and content that looks like a marker.
test "merge3 regions replay: CRLF, a missing final newline, an empty side, and marker-like content" {
const gpa = std.testing.allocator;
const cases = [_][3][]const u8{
.{ "a\r\nb\r\nc\r\n", "a\r\nB\r\nc\r\n", "a\r\nb\r\nC\r\n" },
.{ "a\nb\nc", "a\nX\nc", "a\nb\nY" },
.{ "a\nb\n", "", "a\nb\nc\n" },
.{ "", "x\n", "y" },
.{ "a\n=======\nb\n", "<<<<<<< here\n=======\nb\n", "a\n=======\n>>>>>>> other\n" },
};
for (cases) |c| try expectRegionsReplay(gpa, c[0], c[1], c[2]);
}