//! 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;
const linediff = @import("linediff.zig");
/// A merged buffer, the spans of `bytes` that hold conflict envelopes, and the
/// regions the merge walked. All three slices are owned by the allocator passed
/// to the producer; the caller frees them with `deinit` (or an arena).
/// `conflicts` is empty for a clean merge.
pub const Result = struct {
bytes: []u8,
conflicts: []const Span,
regions: []const Region,
pub fn deinit(r: Result, a: std.mem.Allocator) void {
a.free(r.bytes);
a.free(r.conflicts);
a.free(r.regions);
}
};
/// Who changed a region, decided before any strategy answers it: a region
/// both sides changed differently is `conflict` under `-X ours` too.
pub const RegionKind = enum { same, current, other, both, conflict };
/// A half-open range of line indexes in `splitLines`'s model.
pub const LineRange = struct { lo: usize, hi: usize };
/// One region of a three-way merge, as line ranges in each of the three
/// inputs. A merge's regions are ordered, cover each input completely, and
/// do not overlap; sync lines are folded into `same` regions, so two `same`
/// regions are never adjacent. Concatenating one side's ranges reproduces
/// that side; replaying them -- base for `same`, the changed side for
/// `current`/`other`/`both`, an answer for `conflict` -- reproduces the merge.
/// This is how a caller shows a conflict without merging a second time.
pub const Region = struct {
kind: RegionKind,
base: LineRange,
current: LineRange,
other: LineRange,
};
/// 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.
/// How a region both sides changed DIFFERENTLY is resolved.
///
/// `.conflict` is the default and the only one that can produce markers: the
/// region becomes a diff3 envelope for a human to settle. The other two answer
/// it wholesale, which is what `git merge -X ours` / `-X theirs` do, and they
/// exist for the mechanical cases -- a regenerated lockfile, a vendored tree
/// taken from upstream -- where resolving by hand is where mistakes enter.
///
/// NOT `--backout`, and the distinction is worth stating because the two read
/// alike and are not: `--backout` REVERSES a change; `.ours` keeps the current
/// side wherever the two disagree and reverses nothing.
pub const Strategy = enum {
/// Emit an envelope and record the span. The historical behaviour.
conflict,
/// Take the current side's region.
ours,
/// Take the other side's region.
theirs,
};
pub const conflict_sentinel = "<<<<<<< ";
/// The last line of every conflict envelope, and the closing counterpart of
/// `conflict_sentinel`: seven `>` then ` other` then the newline that puts the
/// next byte at a line start. `appendEnvelope` is the SOLE producer of it.
/// Exported so consumers that reason about envelope extents — the merge3 fuzz
/// target's oracle-4 carve-out — pin both ends against this module rather than
/// re-typing the literal.
pub const conflict_terminator = ">>>>>>> other\n";
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] == ' ');
// Tripwire: the terminator is seven '>' followed by " other\n".
assert(conflict_terminator.len == 14);
for (conflict_terminator[0..7]) |c| assert(c == '>');
assert(std.mem.eql(u8, conflict_terminator[7..], " other\n"));
}
/// 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: WholeFile, // caller writes the whole-file envelope
};
/// Why a path conflicts as a whole file rather than region by region.
pub const WholeFile = enum {
/// Both changed it and a side is binary: the line engine never runs.
binary,
/// Both added it, with different content.
add_add,
/// Current deleted it; other changed it.
delete_modify,
/// Current changed it; other deleted it.
modify_delete,
};
// --- 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 n = std.mem.count(u8, bytes, "\n");
if (bytes.len > 0 and bytes[bytes.len - 1] != '\n') n += 1;
const lines = try gpa.alloc(Line, n);
var start: usize = 0;
var i: usize = 0;
while (std.mem.indexOfScalarPos(u8, bytes, start, '\n')) |nl| : (i += 1) {
lines[i] = .{ .start = start, .end = nl + 1 };
start = nl + 1;
}
if (start < bytes.len) {
lines[i] = .{ .start = start, .end = bytes.len };
i += 1;
}
assert(i == n);
return lines;
}
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));
}
/// For each line of `base`, the line of `side` it is matched to, or null,
/// so the diff3 walk can find sync points. The matching is Fossil's line
/// diff with Fossil's merge settings (`linediff`, optimized, no whitespace
/// flags), so a merge here pairs the same copies of repeated lines that
/// `fossil merge` does. Matched indices strictly increase and pair
/// byte-identical lines, newline included: a final line gaining or losing
/// its newline is a change, never a match.
fn matchSide(
gpa: std.mem.Allocator,
base: []const u8,
side: []const u8,
base_match: []?usize,
) error{OutOfMemory}!void {
const triples = try linediff.diff(gpa, base, side, .{});
defer gpa.free(triples);
linediff.matchFrom(triples, base_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,
strategy: Strategy,
) 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 matchSide(a, base, current, match_a);
try matchSide(a, base, other, match_b);
// Every buffer is sized from the inputs up front and never grows, and
// the results are copied out at their exact length rather than shrunk
// in place: whether an in-place resize succeeds depends on the heap, and
// the allocations must depend on the input alone.
var syncs = try std.ArrayList(Sync).initCapacity(a, o_lines.len);
defer syncs.deinit(a);
for (o_lines, 0..) |_, io| {
if (match_a[io]) |ia| {
if (match_b[io]) |ib| syncs.appendAssumeCapacity(.{ .io = io, .ia = ia, .ib = ib });
}
}
// Each region emits its bytes from at most the three inputs, which the
// regions and sync lines partition, plus at most one envelope's markers.
const n_regions = syncs.items.len + 1;
var out = try std.ArrayList(u8).initCapacity(a, base.len + current.len + other.len + n_regions * envelope_overhead);
defer out.deinit(a);
var spans = try std.ArrayList(Span).initCapacity(a, n_regions);
defer spans.deinit(a);
var regions = try std.ArrayList(Region).initCapacity(a, 2 * n_regions);
defer regions.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);
const kind: RegionKind = if (!a_changed and !b_changed)
.same
else if (!b_changed)
.current
else if (!a_changed)
.other
else if (std.mem.eql(u8, a_reg, b_reg))
.both
else
.conflict;
appendRegionRange(®ions, kind, .{ .lo = o_lo, .hi = o_hi }, .{ .lo = a_lo, .hi = a_hi }, .{ .lo = b_lo, .hi = b_hi });
if (m < k) {
const s = syncs.items[m];
appendRegionRange(®ions, .same, .{ .lo = s.io, .hi = s.io + 1 }, .{ .lo = s.ia, .hi = s.ia + 1 }, .{ .lo = s.ib, .hi = s.ib + 1 });
}
if (!a_changed and !b_changed) {
out.appendSliceAssumeCapacity(o_reg);
} else if (a_changed and !b_changed) {
out.appendSliceAssumeCapacity(a_reg);
} else if (!a_changed and b_changed) {
out.appendSliceAssumeCapacity(b_reg);
} else if (std.mem.eql(u8, a_reg, b_reg)) {
// Both sides made the identical change — clean, take either.
out.appendSliceAssumeCapacity(a_reg);
} else switch (strategy) {
// The whole of `-X ours` / `-X theirs`: the clean cases above are
// untouched, because a strategy only answers a question the merge
// could not. A region exactly one side changed is still that
// side's, whichever strategy is in force.
.ours => out.appendSliceAssumeCapacity(a_reg),
.theirs => out.appendSliceAssumeCapacity(b_reg),
.conflict => {
const start = out.items.len;
appendEnvelope(&out, a_reg, o_reg, b_reg);
spans.appendAssumeCapacity(.{ .start = start, .len = out.items.len - start });
},
}
if (m < k) out.appendSliceAssumeCapacity(lineBytes(base, o_lines[syncs.items[m].io]));
}
const bytes = try a.dupe(u8, out.items);
errdefer a.free(bytes);
const conflicts = try a.dupe(Span, spans.items);
errdefer a.free(conflicts);
const walked = try a.dupe(Region, regions.items);
if (std.debug.runtime_safety) {
// A resolving strategy answers every region, so it can never leave a
// span behind -- and a marker in the output would then be content the
// sides actually contained, not one this function wrote.
if (strategy != .conflict) assert(conflicts.len == 0);
// 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);
}
// Regions tile all three inputs, and one envelope per conflict region.
var ends = [3]usize{ 0, 0, 0 };
var n_conflict: usize = 0;
for (walked) |r| {
assert(r.base.lo == ends[0] and r.current.lo == ends[1] and r.other.lo == ends[2]);
ends = .{ r.base.hi, r.current.hi, r.other.hi };
if (r.kind == .conflict) n_conflict += 1;
}
assert(ends[0] == o_lines.len and ends[1] == a_lines.len and ends[2] == b_lines.len);
if (strategy == .conflict) assert(n_conflict == conflicts.len);
}
return .{ .bytes = bytes, .conflicts = conflicts, .regions = walked };
}
/// Append one region, folding it into the last when both are `same` and
/// dropping it when it is empty on all three sides (an edge between two
/// adjacent sync lines).
fn appendRegionRange(
regions: *std.ArrayList(Region),
kind: RegionKind,
base: LineRange,
current: LineRange,
other: LineRange,
) void {
if (base.lo == base.hi and current.lo == current.hi and other.lo == other.hi) return;
if (kind == .same) if (regions.items.len != 0) {
const last = ®ions.items[regions.items.len - 1];
if (last.kind == .same) {
last.base.hi = base.hi;
last.current.hi = current.hi;
last.other.hi = other.hi;
return;
}
};
regions.appendAssumeCapacity(.{ .kind = kind, .base = base, .current = current, .other = other });
}
/// Append one diff3 envelope for a hunk (or, via `writeEnvelope`, a whole file).
/// The sole producer of both `conflict_sentinel` and `conflict_terminator`.
/// 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),
current: []const u8,
base: []const u8,
other: []const u8,
) void {
buf.appendSliceAssumeCapacity(conflict_sentinel);
buf.appendSliceAssumeCapacity("current\n");
appendRegion(buf, current);
buf.appendSliceAssumeCapacity("||||||| base\n");
appendRegion(buf, base);
buf.appendSliceAssumeCapacity("=======\n");
appendRegion(buf, other);
buf.appendSliceAssumeCapacity(conflict_terminator);
}
/// The most bytes `appendEnvelope` adds beyond its three regions: the four
/// marker lines and a newline closing each region.
const envelope_overhead = conflict_sentinel.len + "current\n".len + "||||||| base\n".len +
"=======\n".len + conflict_terminator.len + 3;
fn appendRegion(buf: *std.ArrayList(u8), region: []const u8) void {
if (region.len == 0) return;
buf.appendSliceAssumeCapacity(region);
if (region[region.len - 1] != '\n') buf.appendAssumeCapacity('\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 {
const c = current orelse "";
const b = base orelse "";
const o = other orelse "";
var buf = try std.ArrayList(u8).initCapacity(a, c.len + b.len + o.len + envelope_overhead);
defer buf.deinit(a);
appendEnvelope(&buf, c, b, o);
return a.dupe(u8, buf.items);
}
/// 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,
strategy: Strategy,
) 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 switch (strategy) {
// add-vs-add differ (B-merge-20) is a CONTENT disagreement: both
// sides produced a file where there was none, and a strategy is
// exactly an instruction for whose content wins.
.ours => .unchanged,
.theirs => .take_other,
.conflict => .{ .whole_file_conflict = .add_add },
};
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.
//
// MODIFY-VS-DELETE IS NOT RESOLVED BY A STRATEGY, deliberately, and this is
// the one place `-X` declines to answer. "Prefer my side where we disagree"
// is an instruction about CONTENT; it does not say whether the file should
// exist. Reading it as "keep my deletion" would silently discard the other
// side's edits, and reading it as "keep my file" would silently resurrect a
// path someone deleted on purpose -- opposite outcomes, both defensible
// from the same flag, which is the definition of a switch that should not
// guess. git leaves this conflicting under `-X` too.
if (current == null) return .{ .whole_file_conflict = .delete_modify }; // B-merge-19
if (other == null) return .{ .whole_file_conflict = .modify_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.?)) {
// Both present, both modified, and the line engine is unreachable --
// still a content disagreement, so a strategy answers it whole-file.
return switch (strategy) {
.ours => .unchanged,
.theirs => .take_other,
.conflict => .{ .whole_file_conflict = .binary },
};
}
const r = try merge3(a, base.?, current.?, other.?, strategy);
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| r.deinit(a),
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", .conflict);
defer r.deinit(a);
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", .conflict);
defer r.deinit(a);
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", .conflict);
defer r.deinit(a);
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", .conflict);
defer r.deinit(a);
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", .conflict);
defer r.deinit(a);
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", .conflict));
try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, "b", null, null, .conflict));
}
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", .conflict));
}
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", .conflict));
}
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, .conflict));
}
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", .conflict));
}
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, .conflict));
// base absent, only other present → take their add.
try testing.expectEqual(FileOutcome.take_other, try classifyFile(a, null, null, "y\n", .conflict));
}
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 = .delete_modify }, try classifyFile(a, "b\n", null, "o\n", .conflict));
// current modified, other deleted (symmetric).
try testing.expectEqual(FileOutcome{ .whole_file_conflict = .modify_delete }, try classifyFile(a, "b\n", "c\n", null, .conflict));
}
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 = .add_add }, try classifyFile(a, null, "x\n", "y\n", .conflict));
try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, null, "same\n", "same\n", .conflict));
}
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", .conflict);
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", .conflict);
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 "merge3 regions: who changed each region, as line ranges that tile all three sides" {
const a = testing.allocator;
// base: a b c d e
// current: a B c d e f (changed b, appended f)
// other: a b c D e (changed d)
const r = try merge3(a, "a\nb\nc\nd\ne\n", "a\nB\nc\nd\ne\nf\n", "a\nb\nc\nD\ne\n", .conflict);
defer r.deinit(a);
const want = [_]Region{
.{ .kind = .same, .base = .{ .lo = 0, .hi = 1 }, .current = .{ .lo = 0, .hi = 1 }, .other = .{ .lo = 0, .hi = 1 } },
.{ .kind = .current, .base = .{ .lo = 1, .hi = 2 }, .current = .{ .lo = 1, .hi = 2 }, .other = .{ .lo = 1, .hi = 2 } },
.{ .kind = .same, .base = .{ .lo = 2, .hi = 3 }, .current = .{ .lo = 2, .hi = 3 }, .other = .{ .lo = 2, .hi = 3 } },
.{ .kind = .other, .base = .{ .lo = 3, .hi = 4 }, .current = .{ .lo = 3, .hi = 4 }, .other = .{ .lo = 3, .hi = 4 } },
.{ .kind = .same, .base = .{ .lo = 4, .hi = 5 }, .current = .{ .lo = 4, .hi = 5 }, .other = .{ .lo = 4, .hi = 5 } },
.{ .kind = .current, .base = .{ .lo = 5, .hi = 5 }, .current = .{ .lo = 5, .hi = 6 }, .other = .{ .lo = 5, .hi = 5 } },
};
try testing.expectEqualSlices(Region, &want, r.regions);
}
test "merge3 regions: a conflict stays a conflict under a resolving strategy" {
const a = testing.allocator;
for ([_]Strategy{ .conflict, .ours, .theirs }) |st| {
const r = try merge3(a, "a\nb\nc\n", "a\nX\nc\n", "a\nY\nY\nc\n", st);
defer r.deinit(a);
try testing.expectEqual(@as(usize, 3), r.regions.len);
try testing.expectEqual(RegionKind.conflict, r.regions[1].kind);
try testing.expectEqual(LineRange{ .lo = 1, .hi = 2 }, r.regions[1].base);
try testing.expectEqual(LineRange{ .lo = 1, .hi = 2 }, r.regions[1].current);
try testing.expectEqual(LineRange{ .lo = 1, .hi = 3 }, r.regions[1].other);
}
}
test "merge3 regions: identical changes are both, and empty inputs have none" {
const a = testing.allocator;
const r = try merge3(a, "a\nb\n", "a\nZ\n", "a\nZ\n", .conflict);
defer r.deinit(a);
try testing.expectEqual(@as(usize, 2), r.regions.len);
try testing.expectEqual(RegionKind.both, r.regions[1].kind);
const e = try merge3(a, "", "", "", .conflict);
defer e.deinit(a);
try testing.expectEqual(@as(usize, 0), e.regions.len);
}
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 = .binary },
try classifyFile(a, base, current, other, .conflict),
);
}
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, .conflict));
// new path: base absent, current absent, other present → take_other (add)
try testing.expectEqual(FileOutcome.take_other, try classifyFile(a, null, null, "data\n", .conflict));
}
/// The matcher's invariants for one pair, the ones the diff3 walk relies on:
/// every match pairs byte-identical lines and the matched indices strictly
/// increase.
fn expectMatchSound(gpa: std.mem.Allocator, base: []const u8, side: []const u8) !void {
const x = try splitLines(gpa, base);
defer gpa.free(x);
const y = try splitLines(gpa, side);
defer gpa.free(y);
const got = try gpa.alloc(?usize, x.len);
defer gpa.free(got);
try matchSide(gpa, base, side, got);
var last: ?usize = null;
for (got, 0..) |g, i| {
const j = g orelse continue;
try testing.expect(j < y.len);
try testing.expect(linesEql(base, x[i], side, y[j]));
if (last) |l| try testing.expect(j > l);
last = j;
}
}
/// A random line buffer over a small alphabet: one letter per line, so
/// repeated lines (the tiebreak-heavy case) are common.
fn randomLines(rand: std.Random, buf: []u8, alphabet: u8) []const u8 {
const n = rand.uintLessThan(usize, buf.len / 2 + 1);
for (0..n) |i| {
buf[2 * i] = 'a' + rand.uintLessThan(u8, alphabet);
buf[2 * i + 1] = '\n';
}
return buf[0 .. 2 * n];
}
test "matchSide pairs equal lines in increasing order on random sequences" {
const a = testing.allocator;
var prng = std.Random.DefaultPrng.init(0x176_0001);
const rand = prng.random();
var xb: [120]u8 = undefined;
var yb: [120]u8 = undefined;
for (0..3000) |round| {
const alphabet: u8 = switch (round % 3) {
0 => 2,
1 => 4,
else => 12,
};
const base = randomLines(rand, &xb, alphabet);
const side = randomLines(rand, &yb, alphabet);
try expectMatchSound(a, base, side);
}
}
test "matchSide pairs equal lines in increasing order under random edits of one file" {
const a = testing.allocator;
var prng = std.Random.DefaultPrng.init(0x176_0002);
const rand = prng.random();
for (0..400) |_| {
var base: std.ArrayList(u8) = .empty;
defer base.deinit(a);
const n = rand.uintLessThan(usize, 300);
for (0..n) |_| {
try base.append(a, 'a' + rand.uintLessThan(u8, 26));
try base.append(a, '\n');
}
// Edits at both ends and in the middle, so the head and tail trim
// leaves real work for the search.
var edited: std.ArrayList(u8) = .empty;
defer edited.deinit(a);
try edited.appendSlice(a, base.items);
const edits = rand.uintLessThan(usize, 40);
for (0..edits) |_| {
const lines = edited.items.len / 2;
const at = 2 * rand.uintLessThan(usize, lines + 1);
if (rand.boolean() and at < edited.items.len) {
edited.replaceRangeAssumeCapacity(at, 2, &.{});
} else {
try edited.insertSlice(a, at, &.{ 'a' + rand.uintLessThan(u8, 26), '\n' });
}
}
try expectMatchSound(a, edited.items, base.items);
try expectMatchSound(a, base.items, edited.items);
}
}
test "matchSide never matches a final line across a newline change" {
const a = testing.allocator;
var m: [2]?usize = undefined;
try matchSide(a, "a\nb", "a\nb\n", &m);
try testing.expectEqualSlices(?usize, &.{ 0, null }, &m);
}
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 = &.{}, .regions = &.{} }));
try testing.expect(hasConflict(.{ .bytes = "", .conflicts = &.{.{ .start = 0, .len = 1 }}, .regions = &.{} }));
}
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, .conflict)) |r| {
h.update(r.bytes);
for (r.conflicts) |s| {
h.update(std.mem.asBytes(&s.start));
h.update(std.mem.asBytes(&s.len));
}
r.deinit(a);
} 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, .conflict)) |outcome| {
h.update(&[_]u8{@backingInt(outcome)});
switch (outcome) {
.clean_merge, .text_conflict => |r| {
h.update(r.bytes);
r.deinit(a);
},
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", .conflict);
r.deinit(a);
}
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", .conflict);
freeOutcome(a, outcome);
}
test "classifyFile leak-free under checkAllAllocationFailures" {
try testing.checkAllAllocationFailures(testing.allocator, classifyNoLeak, .{});
}