Skip to content
zit Artifact [53ac948c41]
Login

Artifact [53ac948c41]

Check-ins Using Download Hex

Artifact 53ac948c41530846e89015895a92c9f48ea9d4c630ff05b412077c03abf8ad36:

//! 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.
//!
//! Four 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`.
//!
//! 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;
    }

    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;
    }
}

/// 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 gpa.free(r.bytes);
    defer gpa.free(r.conflicts);

    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 gpa.free(r.bytes);
    defer gpa.free(r.conflicts);

    // 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 gpa.free(r.bytes);
    defer gpa.free(r.conflicts);

    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"));
}