Skip to content
zit Artifact [22c24bbea4]
Login

Artifact [22c24bbea4]

Check-ins Using Download Hex

Artifact 22c24bbea4b5fa79879c984b8208e6b0b17b4837977ac36b79821648a4f900bd:

//! Pure three-way (diff3) line merge engine behind `zit merge`
//! (contracts/merge.md, B-merge-1..24). Deep module, no I/O: every entry point
//! takes an injected allocator and byte slices and yields a value — no ambient
//! time, randomness, filesystem, or network (B-merge-6). The closed error set is
//! `error{OutOfMemory}` ONLY: every base/current/other byte triple is a valid
//! input that yields a result, so `InvalidInput` is defined out of existence
//! (B-merge-6). The verb layer (main.zig) imports this module, computes the
//! outcome set purely, and hands it to `update.applyMerge`; `commit` scans the
//! materialized bytes for `conflict_sentinel`.
//!
//! Two surfaces: `merge3` is the line engine (clean where at most one side
//! changed a region, or both changed it identically; else a marker envelope +
//! recorded span). `classifyFile` is the per-path presence×equality classifier
//! that decides unchanged / take_other / delete / clean_merge / text_conflict /
//! whole_file_conflict WITHOUT the CLI re-deriving the matrix. The both-modified
//! binary case short-circuits to `whole_file_conflict` before `merge3` is ever
//! reached (B-merge-21), so the binary guarantee is not laundered through the
//! line merger.

const std = @import("std");
const assert = std.debug.assert;

/// A merged buffer plus the spans of `bytes` that hold conflict envelopes.
/// Both slices are owned by the allocator passed to the producer; the caller
/// frees them (an arena in the CLI). `conflicts` is empty for a clean merge.
pub const Result = struct { bytes: []u8, conflicts: []const Span };

/// A half-open byte range `[start, start+len)` into a `Result.bytes`.
pub const Span = struct { start: usize, len: usize };

/// True when the merge produced at least one conflict envelope.
pub fn hasConflict(r: Result) bool {
    return r.conflicts.len != 0;
}

/// The first line of every conflict envelope: seven `<` then a space, at a line
/// start. `writeEnvelope` is the SOLE producer of this sentinel, and `commit`
/// keys its refusal scan on it (B-merge-10). Keep the 7-`<`+SP shape stable.
pub const conflict_sentinel = "<<<<<<< ";

comptime {
    // Tripwire: the sentinel is exactly seven '<' followed by a single space.
    assert(conflict_sentinel.len == 8);
    for (conflict_sentinel[0..7]) |c| assert(c == '<');
    assert(conflict_sentinel[7] == ' ');
}

/// A path's content on one side of the merge, or `null` when the path is absent
/// there (added, deleted, or never present). `classifyFile` totals the
/// presence×equality matrix over three `Side`s.
pub const Side = ?[]const u8;

/// The pure per-path verdict. Exhaustive so the compiler forces the caller to
/// handle every arm; `whole_file_conflict` carries no bytes because the caller
/// (or `writeEnvelope`) writes the whole-file envelope.
pub const FileOutcome = union(enum) {
    unchanged, // working tree already correct — keep the current side
    take_other, // materialize other's bytes
    delete, // remove from the working tree
    clean_merge: Result, // merge3 bytes, no markers
    text_conflict: Result, // merge3 bytes WITH markers
    whole_file_conflict, // caller writes the whole-file envelope
};

// --- line model -----------------------------------------------------------

/// One line as a half-open byte range into its source buffer. A line includes
/// its trailing '\n' except a final line with no newline, so concatenating
/// every line's bytes reproduces the source buffer exactly. Public so `annotate`
/// splits a version's content on the exact boundaries this engine diffs on
/// (contracts/annotate.md B-annotate-6: one line model, never a second).
pub const Line = struct { start: usize, end: usize };

/// Split `bytes` into `Line` ranges. Empty input yields zero lines. Public: the
/// one line splitter shared by `merge3` and `annotate`.
pub fn splitLines(gpa: std.mem.Allocator, bytes: []const u8) error{OutOfMemory}![]Line {
    var lines: std.ArrayList(Line) = .empty;
    errdefer lines.deinit(gpa);
    var start: usize = 0;
    var i: usize = 0;
    while (i < bytes.len) : (i += 1) {
        if (bytes[i] == '\n') {
            try lines.append(gpa, .{ .start = start, .end = i + 1 });
            start = i + 1;
        }
    }
    if (start < bytes.len) try lines.append(gpa, .{ .start = start, .end = bytes.len });
    return lines.toOwnedSlice(gpa);
}

pub fn lineBytes(bytes: []const u8, line: Line) []const u8 {
    return bytes[line.start..line.end];
}

/// Contiguous bytes covering `lines[lo..hi)` in `bytes`; empty when `lo == hi`.
/// Lines partition the buffer contiguously, so a line range is a byte range.
fn regionBytes(bytes: []const u8, lines: []const Line, lo: usize, hi: usize) []const u8 {
    if (lo == hi) return bytes[0..0];
    return bytes[lines[lo].start..lines[hi - 1].end];
}

fn linesEql(a_bytes: []const u8, a_line: Line, b_bytes: []const u8, b_line: Line) bool {
    return std.mem.eql(u8, lineBytes(a_bytes, a_line), lineBytes(b_bytes, b_line));
}

/// LCS of line sequence `x` against `y`; fills `x_match[i]` with the matched
/// index into `y` (or `null`) so the diff3 walk can find sync points. Matched
/// indices are strictly increasing in `i` (a standard LCS property the walk
/// relies on). DP suffix table sized to `(n+1)*(m+1)`, allocated once, freed.
fn lcsMatch(
    gpa: std.mem.Allocator,
    x_bytes: []const u8,
    x: []const Line,
    y_bytes: []const u8,
    y: []const Line,
    x_match: []?usize,
) error{OutOfMemory}!void {
    assert(x_match.len == x.len);
    const n = x.len;
    const m = y.len;
    for (x_match) |*slot| slot.* = null;
    if (n == 0 or m == 0) return;

    const width = m + 1;
    const dp = try gpa.alloc(usize, (n + 1) * width);
    defer gpa.free(dp);
    for (dp[n * width ..]) |*cell| cell.* = 0; // last row is all zero
    {
        var i: usize = n;
        while (i > 0) {
            i -= 1;
            dp[i * width + m] = 0; // last column is zero
            var j: usize = m;
            while (j > 0) {
                j -= 1;
                if (linesEql(x_bytes, x[i], y_bytes, y[j])) {
                    dp[i * width + j] = dp[(i + 1) * width + (j + 1)] + 1;
                } else {
                    dp[i * width + j] = @max(dp[(i + 1) * width + j], dp[i * width + (j + 1)]);
                }
            }
        }
    }

    var i: usize = 0;
    var j: usize = 0;
    while (i < n and j < m) {
        if (linesEql(x_bytes, x[i], y_bytes, y[j])) {
            x_match[i] = j;
            i += 1;
            j += 1;
        } else if (dp[(i + 1) * width + j] >= dp[i * width + (j + 1)]) {
            i += 1;
        } else {
            j += 1;
        }
    }
}

/// For each line of `newer`, the index of the `older` line the house LCS line
/// diff (the exact correspondence `merge3` runs internally) matches it to, or
/// null when the line is new in `newer`. This is the adjacent-version line
/// correspondence `annotate` propagates provenance across — the ONE house
/// line-diff core, never a second diff (contracts/annotate.md B-annotate-6,
/// ambiguities.md annotate-attribution). Caller frees the returned slice; its
/// length is the line count of `newer`. Pure over the injected allocator.
pub fn matchLines(gpa: std.mem.Allocator, newer: []const u8, older: []const u8) error{OutOfMemory}![]?usize {
    const x = try splitLines(gpa, newer);
    defer gpa.free(x);
    const y = try splitLines(gpa, older);
    defer gpa.free(y);
    const match = try gpa.alloc(?usize, x.len);
    errdefer gpa.free(match);
    try lcsMatch(gpa, newer, x, older, y, match);
    return match;
}

/// An O-line matched in BOTH derivatives: the three files agree on this line, so
/// it is a safe boundary between unstable regions.
const Sync = struct { io: usize, ia: usize, ib: usize };

// --- engine ----------------------------------------------------------------

/// diff3 line merge of `base`/`current`/`other`. Regions between sync points
/// (O-lines matched in both derivatives) are resolved: neither changed ⇒ keep
/// base; exactly one changed ⇒ take that side; both changed identically ⇒ take
/// it; both changed differently ⇒ a conflict envelope whose byte span is
/// recorded (B-merge-1/7). Concatenating the emitted regions reproduces a valid
/// merged buffer; `conflicts` is empty iff the merge is clean.
pub fn merge3(
    a: std.mem.Allocator,
    base: []const u8,
    current: []const u8,
    other: []const u8,
) error{OutOfMemory}!Result {
    const o_lines = try splitLines(a, base);
    defer a.free(o_lines);
    const a_lines = try splitLines(a, current);
    defer a.free(a_lines);
    const b_lines = try splitLines(a, other);
    defer a.free(b_lines);

    const match_a = try a.alloc(?usize, o_lines.len);
    defer a.free(match_a);
    const match_b = try a.alloc(?usize, o_lines.len);
    defer a.free(match_b);
    try lcsMatch(a, base, o_lines, current, a_lines, match_a);
    try lcsMatch(a, base, o_lines, other, b_lines, match_b);

    var syncs: std.ArrayList(Sync) = .empty;
    defer syncs.deinit(a);
    for (o_lines, 0..) |_, io| {
        if (match_a[io]) |ia| {
            if (match_b[io]) |ib| try syncs.append(a, .{ .io = io, .ia = ia, .ib = ib });
        }
    }

    var out: std.ArrayList(u8) = .empty;
    errdefer out.deinit(a);
    var spans: std.ArrayList(Span) = .empty;
    errdefer spans.deinit(a);

    // Regions indexed 0..=k: region m spans (prev sync, next sync); for m<k the
    // matched line `syncs[m]` is emitted verbatim after its preceding region.
    const k = syncs.items.len;
    var m: usize = 0;
    while (m <= k) : (m += 1) {
        const o_lo = if (m == 0) 0 else syncs.items[m - 1].io + 1;
        const o_hi = if (m == k) o_lines.len else syncs.items[m].io;
        const a_lo = if (m == 0) 0 else syncs.items[m - 1].ia + 1;
        const a_hi = if (m == k) a_lines.len else syncs.items[m].ia;
        const b_lo = if (m == 0) 0 else syncs.items[m - 1].ib + 1;
        const b_hi = if (m == k) b_lines.len else syncs.items[m].ib;

        const o_reg = regionBytes(base, o_lines, o_lo, o_hi);
        const a_reg = regionBytes(current, a_lines, a_lo, a_hi);
        const b_reg = regionBytes(other, b_lines, b_lo, b_hi);
        const a_changed = !std.mem.eql(u8, a_reg, o_reg);
        const b_changed = !std.mem.eql(u8, b_reg, o_reg);

        if (!a_changed and !b_changed) {
            try out.appendSlice(a, o_reg);
        } else if (a_changed and !b_changed) {
            try out.appendSlice(a, a_reg);
        } else if (!a_changed and b_changed) {
            try out.appendSlice(a, b_reg);
        } else if (std.mem.eql(u8, a_reg, b_reg)) {
            // Both sides made the identical change — clean, take either.
            try out.appendSlice(a, a_reg);
        } else {
            const start = out.items.len;
            try appendEnvelope(&out, a, a_reg, o_reg, b_reg);
            try spans.append(a, .{ .start = start, .len = out.items.len - start });
        }

        if (m < k) try out.appendSlice(a, lineBytes(base, o_lines[syncs.items[m].io]));
    }

    const bytes = try out.toOwnedSlice(a);
    errdefer a.free(bytes);
    const conflicts = try spans.toOwnedSlice(a);

    if (std.debug.runtime_safety) {
        // Spans are ordered, disjoint, and inside the output.
        var idx: usize = 0;
        while (idx < conflicts.len) : (idx += 1) {
            assert(conflicts[idx].start + conflicts[idx].len <= bytes.len);
            if (idx > 0) assert(conflicts[idx - 1].start + conflicts[idx - 1].len <= conflicts[idx].start);
        }
    }

    return .{ .bytes = bytes, .conflicts = conflicts };
}

/// Append one diff3 envelope for a hunk (or, via `writeEnvelope`, a whole file).
/// The sole producer of `conflict_sentinel`. Each region is normalized to end on
/// a newline so every marker line — and the sentinel — starts at a line start.
fn appendEnvelope(
    buf: *std.ArrayList(u8),
    a: std.mem.Allocator,
    current: []const u8,
    base: []const u8,
    other: []const u8,
) error{OutOfMemory}!void {
    try buf.appendSlice(a, conflict_sentinel);
    try buf.appendSlice(a, "current\n");
    try appendRegion(buf, a, current);
    try buf.appendSlice(a, "||||||| base\n");
    try appendRegion(buf, a, base);
    try buf.appendSlice(a, "=======\n");
    try appendRegion(buf, a, other);
    try buf.appendSlice(a, ">>>>>>> other\n");
}

fn appendRegion(buf: *std.ArrayList(u8), a: std.mem.Allocator, region: []const u8) error{OutOfMemory}!void {
    if (region.len == 0) return;
    try buf.appendSlice(a, region);
    if (region[region.len - 1] != '\n') try buf.append(a, '\n');
}

/// The ONLY whole-file conflict-marker producer. A `null` side renders as an
/// empty region. Used by the CLI for `whole_file_conflict` outcomes; shares the
/// exact envelope shape (and sentinel) with `merge3`'s per-hunk envelopes.
pub fn writeEnvelope(
    a: std.mem.Allocator,
    current: Side,
    base: Side,
    other: Side,
) error{OutOfMemory}![]u8 {
    var buf: std.ArrayList(u8) = .empty;
    errdefer buf.deinit(a);
    try appendEnvelope(&buf, a, current orelse "", base orelse "", other orelse "");
    return buf.toOwnedSlice(a);
}

/// NUL scan: a file with any 0 byte is treated as binary. Cheap, matches the
/// heuristic `commit`/fossil use, and is the sole binary predicate feeding the
/// both-modified guard (B-merge-21).
pub fn isBinary(bytes: []const u8) bool {
    return std.mem.indexOfScalar(u8, bytes, 0) != null;
}

fn sideEql(x: Side, y: Side) bool {
    if (x == null and y == null) return true;
    if (x == null or y == null) return false;
    return std.mem.eql(u8, x.?, y.?);
}

/// Pure per-path three-way classifier over the presence×equality matrix
/// (plan §2). `current`/`other`/`base` are `null` when the path is absent on
/// that side. The both-modified BINARY arm returns `whole_file_conflict`
/// UNCONDITIONALLY, before `merge3` is reached (B-merge-21). `add-vs-add` with
/// differing content and `delete-vs-modify`/`modify-vs-delete` are likewise
/// unconditional `whole_file_conflict`. Only text/text/text both-modified
/// reaches the line engine.
pub fn classifyFile(
    a: std.mem.Allocator,
    base: Side,
    current: Side,
    other: Side,
) error{OutOfMemory}!FileOutcome {
    // Nothing to do when both sides already agree (includes both-absent).
    if (sideEql(current, other)) return .unchanged;

    if (base == null) {
        // add-side: base absent, current != other (equality handled above).
        if (current != null and other != null) return .whole_file_conflict; // add-vs-add differ (B-merge-20)
        if (current != null) return .unchanged; // added our side only
        return .take_other; // added their side only
    }

    const c_eq_b = sideEql(current, base);
    const o_eq_b = sideEql(other, base);

    if (c_eq_b) {
        // Current is unchanged from base; other differs (since current != other).
        if (other == null) return .delete; // other deleted it
        return .take_other; // other modified it
    }
    if (o_eq_b) {
        // Other is unchanged from base; take the current side (modify or delete).
        return .unchanged;
    }

    // Both sides changed the path.
    if (current == null) return .whole_file_conflict; // delete-vs-modify (B-merge-19)
    if (other == null) return .whole_file_conflict; // modify-vs-delete (B-merge-19)

    // Both present and both modified. Binary on ANY side is a whole-file
    // conflict BY CONSTRUCTION — the line engine is never reached (B-merge-21).
    if (isBinary(base.?) or isBinary(current.?) or isBinary(other.?)) {
        return .whole_file_conflict;
    }

    const r = try merge3(a, base.?, current.?, other.?);
    return if (hasConflict(r)) .{ .text_conflict = r } else .{ .clean_merge = r };
}

// --- tests -----------------------------------------------------------------

const testing = std.testing;

fn freeOutcome(a: std.mem.Allocator, o: FileOutcome) void {
    switch (o) {
        .clean_merge, .text_conflict => |r| {
            a.free(r.bytes);
            a.free(r.conflicts);
        },
        else => {},
    }
}

test "merge3 clean disjoint edits merge (B-merge-1)" {
    const a = testing.allocator;
    const r = try merge3(a, "A\nB\nC\n", "A1\nB\nC\n", "A\nB\nC1\n");
    defer a.free(r.bytes);
    defer a.free(r.conflicts);
    try testing.expectEqualStrings("A1\nB\nC1\n", r.bytes);
    try testing.expect(!hasConflict(r));
}

test "merge3 identical edits both sides merge to that content" {
    const a = testing.allocator;
    const r = try merge3(a, "A\nB\nC\n", "A\nX\nC\n", "A\nX\nC\n");
    defer a.free(r.bytes);
    defer a.free(r.conflicts);
    try testing.expectEqualStrings("A\nX\nC\n", r.bytes);
    try testing.expect(!hasConflict(r));
}

test "merge3 only one side changed is clean" {
    const a = testing.allocator;
    const r = try merge3(a, "A\nB\nC\n", "A\nB\nC\n", "A\nZ\nC\n");
    defer a.free(r.bytes);
    defer a.free(r.conflicts);
    try testing.expectEqualStrings("A\nZ\nC\n", r.bytes);
    try testing.expect(!hasConflict(r));
}

test "merge3 overlapping edits emit diff3 envelope (B-merge-7)" {
    const a = testing.allocator;
    const r = try merge3(a, "A\nB\nC\n", "A\nX\nC\n", "A\nY\nC\n");
    defer a.free(r.bytes);
    defer a.free(r.conflicts);
    try testing.expect(hasConflict(r));
    try testing.expectEqual(@as(usize, 1), r.conflicts.len);

    // The sentinel is present and starts a line (index 0 or after a '\n').
    const idx = std.mem.indexOf(u8, r.bytes, conflict_sentinel).?;
    try testing.expect(idx == 0 or r.bytes[idx - 1] == '\n');

    // Full diff3 envelope, in order, with every region byte.
    const expected =
        "A\n" ++
        "<<<<<<< current\nX\n||||||| base\nB\n=======\nY\n>>>>>>> other\n" ++
        "C\n";
    try testing.expectEqualStrings(expected, r.bytes);

    // The recorded span points exactly at the envelope.
    const span = r.conflicts[0];
    try testing.expectEqualStrings(
        "<<<<<<< current\nX\n||||||| base\nB\n=======\nY\n>>>>>>> other\n",
        r.bytes[span.start .. span.start + span.len],
    );
}

test "merge3 empty base merges added content" {
    const a = testing.allocator;
    // Both add distinct content over an empty base at the same position → conflict.
    const r = try merge3(a, "", "X\n", "Y\n");
    defer a.free(r.bytes);
    defer a.free(r.conflicts);
    try testing.expect(hasConflict(r));
}

test "classifyFile equal sides and both-absent are unchanged (B-merge-1)" {
    const a = testing.allocator;
    try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, "b", "same", "same"));
    try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, "b", null, null));
}

test "classifyFile only-other-changed is take_other" {
    const a = testing.allocator;
    try testing.expectEqual(FileOutcome.take_other, try classifyFile(a, "b\n", "b\n", "o\n"));
}

test "classifyFile only-current-changed is unchanged (CARRY)" {
    const a = testing.allocator;
    try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, "b\n", "c\n", "b\n"));
}

test "classifyFile current-equals-base other-deleted is delete" {
    const a = testing.allocator;
    try testing.expectEqual(FileOutcome.delete, try classifyFile(a, "b\n", "b\n", null));
}

test "classifyFile current-deleted other-unchanged stays deleted" {
    const a = testing.allocator;
    // base present, current absent (deleted), other == base → keep our delete.
    try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, "b\n", null, "b\n"));
}

test "classifyFile add our side / their side" {
    const a = testing.allocator;
    // base absent, only current present → we added it → keep (unchanged).
    try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, null, "x\n", null));
    // base absent, only other present → take their add.
    try testing.expectEqual(FileOutcome.take_other, try classifyFile(a, null, null, "y\n"));
}

test "classifyFile delete-vs-modify is whole_file_conflict (B-merge-19)" {
    const a = testing.allocator;
    // current deleted, other modified.
    try testing.expectEqual(FileOutcome.whole_file_conflict, try classifyFile(a, "b\n", null, "o\n"));
    // current modified, other deleted (symmetric).
    try testing.expectEqual(FileOutcome.whole_file_conflict, try classifyFile(a, "b\n", "c\n", null));
}

test "classifyFile add-vs-add differing is whole_file_conflict, identical is unchanged (B-merge-20)" {
    const a = testing.allocator;
    try testing.expectEqual(FileOutcome.whole_file_conflict, try classifyFile(a, null, "x\n", "y\n"));
    try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, null, "same\n", "same\n"));
}

test "classifyFile both-modified text clean_merge" {
    const a = testing.allocator;
    const outcome = try classifyFile(a, "A\nB\nC\n", "A1\nB\nC\n", "A\nB\nC1\n");
    defer freeOutcome(a, outcome);
    try testing.expect(outcome == .clean_merge);
    try testing.expectEqualStrings("A1\nB\nC1\n", outcome.clean_merge.bytes);
}

test "classifyFile both-modified text_conflict carries markers" {
    const a = testing.allocator;
    const outcome = try classifyFile(a, "A\nB\nC\n", "A\nX\nC\n", "A\nY\nC\n");
    defer freeOutcome(a, outcome);
    try testing.expect(outcome == .text_conflict);
    try testing.expect(std.mem.indexOf(u8, outcome.text_conflict.bytes, conflict_sentinel) != null);
}

test "classifyFile both-modified binary is whole_file_conflict bypassing merge3 (B-merge-21)" {
    const a = testing.allocator;
    // Each side carries a NUL; current and other differ in DISJOINT byte-line
    // regions, so the line engine would clean-merge them. The binary guard must
    // return whole_file_conflict without ever calling merge3.
    const base = "H\x00\nM\nT\n";
    const current = "H1\x00\nM\nT\n"; // changed first region
    const other = "H\x00\nM\nT1\n"; // changed last region
    try testing.expectEqual(
        FileOutcome.whole_file_conflict,
        try classifyFile(a, base, current, other),
    );
}

test "classifyFile rename is delete+add, no tracking (B-merge-22)" {
    const a = testing.allocator;
    // A rename on the other side appears as two independent paths:
    //   old path: base present, current == base, other absent → delete
    try testing.expectEqual(FileOutcome.delete, try classifyFile(a, "data\n", "data\n", null));
    //   new path: base absent, current absent, other present → take_other (add)
    try testing.expectEqual(FileOutcome.take_other, try classifyFile(a, null, null, "data\n"));
}

test "matchLines maps carried lines and nulls new ones (annotate line-diff reuse)" {
    const a = testing.allocator;
    // older: A B C ; newer inserts X after A and drops C → A X B.
    const match = try matchLines(a, "A\nX\nB\n", "A\nB\nC\n");
    defer a.free(match);
    try testing.expectEqual(@as(usize, 3), match.len);
    try testing.expectEqual(@as(?usize, 0), match[0]); // A ↔ older A (line 0)
    try testing.expectEqual(@as(?usize, null), match[1]); // X is new
    try testing.expectEqual(@as(?usize, 1), match[2]); // B ↔ older B (line 1)
}

test "matchLines against an empty older marks every newer line new" {
    const a = testing.allocator;
    const match = try matchLines(a, "A\nB\n", "");
    defer a.free(match);
    try testing.expectEqual(@as(usize, 2), match.len);
    try testing.expectEqual(@as(?usize, null), match[0]);
    try testing.expectEqual(@as(?usize, null), match[1]);
}

test "isBinary NUL scan" {
    try testing.expect(!isBinary("plain text\n"));
    try testing.expect(isBinary("has\x00nul"));
    try testing.expect(!isBinary(""));
}

test "hasConflict reflects the span set" {
    try testing.expect(!hasConflict(.{ .bytes = "", .conflicts = &.{} }));
    try testing.expect(hasConflict(.{ .bytes = "", .conflicts = &.{.{ .start = 0, .len = 1 }} }));
}

test "writeEnvelope produces the sentinel at a line start" {
    const a = testing.allocator;
    const env = try writeEnvelope(a, "cur\n", "base\n", "oth\n");
    defer a.free(env);
    try testing.expectEqualStrings(
        "<<<<<<< current\ncur\n||||||| base\nbase\n=======\noth\n>>>>>>> other\n",
        env,
    );
    try testing.expect(std.mem.startsWith(u8, env, conflict_sentinel));

    // A null side renders as an empty region; markers still line-aligned.
    const env2 = try writeEnvelope(a, "cur\n", null, null);
    defer a.free(env2);
    try testing.expectEqualStrings(
        "<<<<<<< current\ncur\n||||||| base\n=======\n>>>>>>> other\n",
        env2,
    );
}

/// Fill `buf` with a byte triple's worth of adversarial content: mostly ASCII
/// letters and newlines (to exercise the line splitter) with occasional NUL and
/// high bytes. Pure over the injected `rand`.
fn fuzzFill(rand: std.Random, buf: []u8) usize {
    const len = rand.uintLessThan(usize, buf.len + 1);
    for (buf[0..len]) |*b| {
        b.* = switch (rand.uintLessThan(u8, 10)) {
            0, 1, 2 => '\n',
            3 => 0, // NUL — makes the side binary
            4 => rand.int(u8), // full range
            else => 'A' + rand.uintLessThan(u8, 6), // A..F, small alphabet → line reuse
        };
    }
    return len;
}

/// One deterministic fuzz pass: fold every merge3/classifyFile output for a
/// fixed seed into a running hash. Same seed ⇒ same returned hash.
fn fuzzPass(seed: u64) u64 {
    const a = testing.allocator;
    var prng = std.Random.DefaultPrng.init(seed);
    const rand = prng.random();
    var h = std.hash.Wyhash.init(0);

    var round: usize = 0;
    while (round < 400) : (round += 1) {
        var bb: [64]u8 = undefined;
        var cb: [64]u8 = undefined;
        var ob: [64]u8 = undefined;
        const base = bb[0..fuzzFill(rand, &bb)];
        const current = cb[0..fuzzFill(rand, &cb)];
        const other = ob[0..fuzzFill(rand, &ob)];

        if (merge3(a, base, current, other)) |r| {
            h.update(r.bytes);
            for (r.conflicts) |s| {
                h.update(std.mem.asBytes(&s.start));
                h.update(std.mem.asBytes(&s.len));
            }
            a.free(r.bytes);
            a.free(r.conflicts);
        } else |_| {
            h.update("E"); // OOM (or any declared error) folds in deterministically
        }

        // classifyFile over presence-varied Sides on the same bytes.
        const bs: Side = if (round & 1 == 0) base else null;
        const cs: Side = if (round & 2 == 0) current else null;
        const os: Side = if (round & 4 == 0) other else null;
        if (classifyFile(a, bs, cs, os)) |outcome| {
            h.update(&[_]u8{@intFromEnum(outcome)});
            switch (outcome) {
                .clean_merge, .text_conflict => |r| {
                    h.update(r.bytes);
                    a.free(r.bytes);
                    a.free(r.conflicts);
                },
                else => {},
            }
        } else |_| {
            h.update("F");
        }
    }
    return h.final();
}

test "merge3 seeded deterministic fuzz never crashes (B-merge-24)" {
    // Fixed seed (no ambient rng). Two passes at the same seed must be
    // byte-identical; the engine returns a value or a declared error, never a
    // crash, for every adversarial triple.
    const first = fuzzPass(0x5EED_1234_ABCD_0001);
    const second = fuzzPass(0x5EED_1234_ABCD_0001);
    try testing.expectEqual(first, second);
    // A different seed should (overwhelmingly) diverge — sanity that the hash
    // actually depends on inputs.
    const other = fuzzPass(0x0BAD_C0DE_0000_0002);
    try testing.expect(first != other);
}

fn merge3NoLeak(a: std.mem.Allocator) error{OutOfMemory}!void {
    // A conflict input exercises the envelope + span allocations.
    const r = try merge3(a, "A\nB\nC\n", "A\nX\nC\n", "A\nY\nC\n");
    a.free(r.bytes);
    a.free(r.conflicts);
}

test "merge3 leak-free under checkAllAllocationFailures" {
    try testing.checkAllAllocationFailures(testing.allocator, merge3NoLeak, .{});
}

fn classifyNoLeak(a: std.mem.Allocator) error{OutOfMemory}!void {
    // Both-modified text drives an internal merge3 allocation.
    const outcome = try classifyFile(a, "A\nB\nC\n", "A1\nB\nC\n", "A\nB\nC1\n");
    freeOutcome(a, outcome);
}

test "classifyFile leak-free under checkAllAllocationFailures" {
    try testing.checkAllAllocationFailures(testing.allocator, classifyNoLeak, .{});
}