//! 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, a port of Fossil's merge3.c
//! walk (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; adjacent `same` regions are folded into one, 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));
}
/// The copy/delete/insert triples turning `base` into `side`, as a mutable
/// copy ending in Fossil's zero triple: the walk below consumes copies in
/// place, and `endsWithCopy` reads up to that terminator. The diff is
/// Fossil's line diff with Fossil's merge settings (`linediff`, optimized, no
/// whitespace flags), so the merge pairs the same copies of repeated lines
/// that `fossil merge` does. A final line gaining or losing its newline is a
/// change, never a copy; Fossil's diff compares lines without their newlines,
/// so its merge copies such a line and loses the newline change.
fn editScript(gpa: std.mem.Allocator, base: []const u8, side: []const u8) error{OutOfMemory}![]linediff.Triple {
const triples = try linediff.diff(gpa, base, side, .{});
defer gpa.free(triples);
var n: usize = 0;
while (n < triples.len and !isEnd(triples[n])) n += 1;
const script = try gpa.alloc(linediff.Triple, n + 1);
@memcpy(script[0..n], triples[0..n]);
script[n] = .{ .copy = 0, .delete = 0, .insert = 0 };
return script;
}
fn isEnd(t: linediff.Triple) bool {
return t.copy == 0 and t.delete == 0 and t.insert == 0;
}
/// Fossil's `ends_with_copy`: whether advancing `sz` base lines from the
/// start of `script` lands inside a copy rather than inside a delete.
fn endsWithCopy(script: []const linediff.Triple, sz_in: usize) bool {
var sz = sz_in;
var i: usize = 0;
while (sz > 0 and !isEnd(script[i])) : (i += 1) {
if (script[i].copy >= sz) return true;
sz -= script[i].copy;
if (script[i].delete > sz) return false;
sz -= script[i].delete;
}
return true;
}
/// Fossil's `skip_conflict`: consume `sz` base lines of `script` from index
/// `i`, setting `side_lines` to the lines of the side that keeps the two in
/// step, and return the index of the triple the walk resumes at. A copy the
/// advance ends inside is shortened in place.
fn skipConflict(script: []linediff.Triple, i_in: usize, sz_in: usize, side_lines: *usize) usize {
var i = i_in;
var sz = sz_in;
side_lines.* = 0;
while (sz > 0) {
if (isEnd(script[i])) break;
if (script[i].copy >= sz) {
script[i].copy -= @intCast(sz);
side_lines.* += sz;
break;
}
side_lines.* += script[i].copy + script[i].insert;
sz -= script[i].copy + script[i].delete;
i += 1;
}
return i;
}
/// The walk's regions, each given as line counts in base, current and other
/// and turned into ranges by a running position on each side.
const Walk = struct {
regions: *std.ArrayList(Region),
at: [3]usize = .{ 0, 0, 0 },
n_base: usize,
fn push(w: *Walk, kind: RegionKind, n_base: usize, n_current: usize, n_other: usize) void {
// A conflict is at least one base line long, as in Fossil, even where
// it sits after the last one; there it takes none.
const base_hi = @min(w.at[0] + n_base, w.n_base);
const current_hi = w.at[1] + n_current;
const other_hi = w.at[2] + n_other;
appendRegionRange(
w.regions,
kind,
.{ .lo = w.at[0], .hi = base_hi },
.{ .lo = w.at[1], .hi = current_hi },
.{ .lo = w.at[2], .hi = other_hi },
);
w.at = .{ base_hi, current_hi, other_hi };
}
fn rivalRange(r: Region, kind: RegionKind) LineRange {
return if (kind == .current) r.current else r.other;
}
/// The insert one side makes after the other side's script has ended.
/// When the region before it is the other side's change and leaves a final
/// line without its newline, Fossil writes the insert straight after that
/// line, joining the two into a line neither side has. Here the change and
/// the insert become one conflict instead.
fn pushTail(w: *Walk, kind: RegionKind, n: usize, rival: []const u8) void {
assert(kind == .current or kind == .other);
const rival_kind: RegionKind = if (kind == .current) .other else .current;
const items = w.regions.items;
const joins = rival.len != 0 and rival[rival.len - 1] != '\n' and items.len != 0 and
items[items.len - 1].kind == rival_kind and
rivalRange(items[items.len - 1], rival_kind).hi != rivalRange(items[items.len - 1], rival_kind).lo;
if (!joins) {
if (kind == .current) w.push(.current, 0, n, 0) else w.push(.other, 0, 0, n);
return;
}
const last = &items[items.len - 1];
last.kind = .conflict;
if (kind == .current) {
last.current.hi += n;
w.at[1] += n;
} else {
last.other.hi += n;
w.at[2] += n;
}
}
};
/// Fossil's `merge_three_blobs` walk (merge3.c, D. Richard Hipp), kept
/// branch for branch so a merge here is clean or conflicting exactly where
/// `fossil merge` is. The two edit scripts are walked together against base:
/// lines both copy are kept; an edit on one side that falls inside lines the
/// other side copies is taken, whatever sits next to it; an edit both sides
/// made identically is taken once; anything else is a conflict, grown one
/// base line at a time until both scripts are back inside a copy.
fn walkRegions(
regions: *std.ArrayList(Region),
s1: []linediff.Triple,
s2: []linediff.Triple,
current: []const u8,
c_lines: []const Line,
other: []const u8,
t_lines: []const Line,
n_base: usize,
) void {
var w: Walk = .{ .regions = regions, .n_base = n_base };
const limit1 = s1.len - 1;
const limit2 = s2.len - 1;
var x1: usize = 0;
var x2: usize = 0;
while (x1 < limit1 and x2 < limit2) {
const e1 = &s1[x1];
const e2 = &s2[x2];
if (e1.copy > 0 and e2.copy > 0) {
const n = @min(e1.copy, e2.copy);
w.push(.same, n, n, n);
e1.copy -= n;
e2.copy -= n;
} else if (e1.copy >= e2.delete and e1.copy > 0 and e2.delete + e2.insert > 0) {
w.push(.other, e2.delete, e2.delete, e2.insert);
e1.copy -= e2.delete;
x2 += 1;
} else if (e2.copy >= e1.delete and e2.copy > 0 and e1.delete + e1.insert > 0) {
w.push(.current, e1.delete, e1.insert, e1.delete);
e2.copy -= e1.delete;
x1 += 1;
} else if (sameEdit(e1.*, e2.*, current, c_lines, w.at[1], other, t_lines, w.at[2])) {
assert(e1.copy == 0);
w.push(.both, e1.delete, e1.insert, e1.insert);
x1 += 1;
x2 += 1;
} else {
var sz: usize = 1;
while (!endsWithCopy(s1[x1..], sz) or !endsWithCopy(s2[x2..], sz)) sz += 1;
var n1: usize = undefined;
var n2: usize = undefined;
x1 = skipConflict(s1, x1, sz, &n1);
x2 = skipConflict(s2, x2, sz, &n2);
w.push(.conflict, sz, n1, n2);
}
if (x1 < limit1 and isEnd(s1[x1])) x1 += 1;
if (x2 < limit2 and isEnd(s2[x2])) x2 += 1;
}
// One script can end with an insert after the other has run out.
if (x1 < limit1 and s1[x1].insert > 0) {
w.pushTail(.current, s1[x1].insert, other);
} else if (x2 < limit2 and s2[x2].insert > 0) {
w.pushTail(.other, s2[x2].insert, current);
}
assert(w.at[0] == n_base and w.at[1] == c_lines.len and w.at[2] == t_lines.len);
}
/// Fossil's `sameEdit`: the two next edits delete the same base lines and
/// insert the same text. Inserted lines compare as bytes, newline included.
fn sameEdit(
e1: linediff.Triple,
e2: linediff.Triple,
current: []const u8,
c_lines: []const Line,
c_at: usize,
other: []const u8,
t_lines: []const Line,
t_at: usize,
) bool {
if (e1.copy != e2.copy or e1.delete != e2.delete or e1.insert != e2.insert) return false;
return std.mem.eql(
u8,
regionBytes(current, c_lines, c_at, c_at + e1.insert),
regionBytes(other, t_lines, t_at, t_at + e2.insert),
);
}
// --- engine ----------------------------------------------------------------
/// diff3 line merge of `base`/`current`/`other`, deciding regions as Fossil's
/// merge3 does (`walkRegions`): 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 s1 = try editScript(a, base, current);
defer a.free(s1);
const s2 = try editScript(a, base, other);
defer a.free(s2);
// 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. Each pass of the walk
// yields one region and either finishes a triple or empties a copy that
// the next pass on that side finishes, so two regions per triple bound it.
const max_regions = 2 * (s1.len + s2.len);
var regions = try std.ArrayList(Region).initCapacity(a, max_regions);
defer regions.deinit(a);
walkRegions(®ions, s1, s2, current, a_lines, other, b_lines, o_lines.len);
// Each region emits its bytes from at most the three inputs, which the
// regions partition, plus at most one envelope's markers.
const n_regions = regions.items.len;
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);
for (regions.items) |reg| {
const o_reg = regionBytes(base, o_lines, reg.base.lo, reg.base.hi);
const a_reg = regionBytes(current, a_lines, reg.current.lo, reg.current.hi);
const b_reg = regionBytes(other, b_lines, reg.other.lo, reg.other.hi);
switch (reg.kind) {
.same => out.appendSliceAssumeCapacity(o_reg),
.current => out.appendSliceAssumeCapacity(a_reg),
.other, .both => out.appendSliceAssumeCapacity(b_reg),
.conflict => switch (strategy) {
// The whole of `-X ours` / `-X theirs`: the clean regions 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 });
},
},
}
}
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.
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`.
/// The sections are Fossil's, in Fossil's order -- current, base, other -- but
/// the marker lines are git's diff3 ones, which editors and merge tools read,
/// rather than Fossil's `<<<<<<< BEGIN MERGE CONFLICT: local copy shown first`
/// set; and there is no counterpart of the token-level suggested resolution
/// Fossil writes after the current side.
/// 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));
}
/// Triples whose merged bytes are `fossil 3-way-merge`'s output, with
/// Fossil's marker lines rewritten to zit's and its suggested-resolution
/// section dropped. They pin the cases the walk decides differently from a
/// merge that synchronises only on lines both sides keep: an edit next to an
/// edit, delete or insert on the other side merges cleanly, and a conflict
/// takes in the base line after an insert, as Fossil's does.
const FossilCase = struct {
name: []const u8,
base: []const u8,
current: []const u8,
other: []const u8,
want: []const u8,
conflicts: usize,
};
const fossil_cases = [_]FossilCase{
.{ .name = "issue: edit next to edit", .base = "a\nb\nc\n", .current = "a\nB\nc\n", .other = "a\nb\nC\n", .want = "a\nB\nC\n", .conflicts = 0 },
.{ .name = "edit next to edit, reversed", .base = "a\nb\nc\n", .current = "a\nb\nC\n", .other = "a\nB\nc\n", .want = "a\nB\nC\n", .conflicts = 0 },
.{ .name = "delete next to edit", .base = "a\nb\nc\nd\n", .current = "a\nc\nd\n", .other = "a\nb\nC\nd\n", .want = "a\nC\nd\n", .conflicts = 0 },
.{ .name = "edit next to delete", .base = "a\nb\nc\nd\n", .current = "a\nB\nc\nd\n", .other = "a\nb\nd\n", .want = "a\nB\nd\n", .conflicts = 0 },
.{ .name = "insert after edit", .base = "a\nb\nc\n", .current = "a\nB\nc\n", .other = "a\nb\nX\nc\n", .want = "a\nB\nX\nc\n", .conflicts = 0 },
.{ .name = "edit after insert", .base = "a\nb\nc\n", .current = "a\nX\nb\nc\n", .other = "a\nb\nC\n", .want = "a\nX\nb\nC\n", .conflicts = 0 },
.{ .name = "insert before edit", .base = "a\nb\nc\n", .current = "a\nX\nb\nc\n", .other = "a\nB\nc\n", .want = "a\n<<<<<<< current\nX\nb\n||||||| base\nb\n=======\nB\n>>>>>>> other\nc\n", .conflicts = 1 },
.{ .name = "both insert same spot differently", .base = "a\nb\nc\n", .current = "a\nX\nb\nc\n", .other = "a\nY\nb\nc\n", .want = "a\n<<<<<<< current\nX\nb\n||||||| base\nb\n=======\nY\nb\n>>>>>>> other\nc\n", .conflicts = 1 },
.{ .name = "both insert same spot identically", .base = "a\nb\nc\n", .current = "a\nX\nb\nc\n", .other = "a\nX\nb\nc\n", .want = "a\nX\nb\nc\n", .conflicts = 0 },
.{ .name = "identical edits", .base = "a\nb\nc\n", .current = "a\nB\nc\n", .other = "a\nB\nc\n", .want = "a\nB\nc\n", .conflicts = 0 },
.{ .name = "overlapping edits", .base = "a\nb\nc\n", .current = "a\nX\nc\n", .other = "a\nY\nc\n", .want = "a\n<<<<<<< current\nX\n||||||| base\nb\n=======\nY\n>>>>>>> other\nc\n", .conflicts = 1 },
.{ .name = "edit vs delete same line", .base = "a\nb\nc\n", .current = "a\nX\nc\n", .other = "a\nc\n", .want = "a\n<<<<<<< current\nX\n||||||| base\nb\n=======\n>>>>>>> other\nc\n", .conflicts = 1 },
.{ .name = "both delete same line", .base = "a\nb\nc\n", .current = "a\nc\n", .other = "a\nc\n", .want = "a\nc\n", .conflicts = 0 },
.{ .name = "repeated blocks, edit second", .base = "x\ny\nx\ny\nx\ny\n", .current = "x\ny\nx\nY\nx\ny\n", .other = "x\ny\nx\ny\nx\nY\n", .want = "x\ny\nx\nY\nx\nY\n", .conflicts = 0 },
.{ .name = "repeated blocks, adjacent", .base = "a\na\na\na\n", .current = "a\nA\na\na\n", .other = "a\na\nA\na\n", .want = "a\nA\nA\na\n", .conflicts = 0 },
.{ .name = "start of file edits", .base = "a\nb\nc\n", .current = "A\nb\nc\n", .other = "a\nB\nc\n", .want = "A\nB\nc\n", .conflicts = 0 },
.{ .name = "start of file inserts", .base = "a\nb\n", .current = "X\na\nb\n", .other = "Y\na\nb\n", .want = "<<<<<<< current\nX\na\n||||||| base\na\n=======\nY\na\n>>>>>>> other\nb\n", .conflicts = 1 },
.{ .name = "end of file appends differ", .base = "a\nb\n", .current = "a\nb\nX\n", .other = "a\nb\nY\n", .want = "a\nb\n<<<<<<< current\nX\n||||||| base\n=======\nY\n>>>>>>> other\n", .conflicts = 1 },
.{ .name = "end of file append vs edit last", .base = "a\nb\n", .current = "a\nb\nX\n", .other = "a\nB\n", .want = "a\nB\nX\n", .conflicts = 0 },
.{ .name = "end of file edits adjacent", .base = "a\nb\nc\n", .current = "a\nB\nc\n", .other = "a\nb\nC\n", .want = "a\nB\nC\n", .conflicts = 0 },
.{ .name = "empty base, both add", .base = "", .current = "X\n", .other = "Y\n", .want = "<<<<<<< current\nX\n||||||| base\n=======\nY\n>>>>>>> other\n", .conflicts = 1 },
.{ .name = "empty base, same add", .base = "", .current = "X\n", .other = "X\n", .want = "X\n", .conflicts = 0 },
.{ .name = "empty current", .base = "a\nb\n", .current = "", .other = "a\nB\n", .want = "<<<<<<< current\n||||||| base\na\nb\n=======\na\nB\n>>>>>>> other\n", .conflicts = 1 },
.{ .name = "all empty", .base = "", .current = "", .other = "", .want = "", .conflicts = 0 },
.{ .name = "empty base one side adds", .base = "", .current = "X\nY\n", .other = "", .want = "X\nY\n", .conflicts = 0 },
.{ .name = "crlf adjacent edits", .base = "a\r\nb\r\nc\r\n", .current = "a\r\nB\r\nc\r\n", .other = "a\r\nb\r\nC\r\n", .want = "a\r\nB\r\nC\r\n", .conflicts = 0 },
.{ .name = "crlf conflict", .base = "a\r\nb\r\nc\r\n", .current = "a\r\nX\r\nc\r\n", .other = "a\r\nY\r\nc\r\n", .want = "a\r\n<<<<<<< current\nX\r\n||||||| base\nb\r\n=======\nY\r\n>>>>>>> other\nc\r\n", .conflicts = 1 },
.{ .name = "crlf vs lf line", .base = "a\nb\nc\n", .current = "a\nb\r\nc\n", .other = "a\nb\nC\n", .want = "a\nb\r\nC\n", .conflicts = 0 },
.{ .name = "two conflicts", .base = "a\nb\nc\nd\ne\n", .current = "a\nX\nc\nZ\ne\n", .other = "a\nY\nc\nW\ne\n", .want = "a\n<<<<<<< current\nX\n||||||| base\nb\n=======\nY\n>>>>>>> other\nc\n<<<<<<< current\nZ\n||||||| base\nd\n=======\nW\n>>>>>>> other\ne\n", .conflicts = 2 },
.{ .name = "conflict then clean", .base = "a\nb\nc\nd\ne\nf\n", .current = "a\nX\nc\nd\nE\nf\n", .other = "a\nY\nc\nd\ne\nF\n", .want = "a\n<<<<<<< current\nX\n||||||| base\nb\n=======\nY\n>>>>>>> other\nc\nd\nE\nF\n", .conflicts = 1 },
.{ .name = "delete run vs inner edit", .base = "a\nb\nc\nd\ne\n", .current = "a\ne\n", .other = "a\nb\nC\nd\ne\n", .want = "a\n<<<<<<< current\n||||||| base\nb\nc\nd\n=======\nb\nC\nd\n>>>>>>> other\ne\n", .conflicts = 1 },
.{ .name = "replace many vs edit inside", .base = "a\nb\nc\nd\ne\n", .current = "a\nP\nQ\ne\n", .other = "a\nb\nc\nD\ne\n", .want = "a\n<<<<<<< current\nP\nQ\n||||||| base\nb\nc\nd\n=======\nb\nc\nD\n>>>>>>> other\ne\n", .conflicts = 1 },
.{ .name = "large delete vs adjacent insert", .base = "a\nb\nc\nd\ne\n", .current = "a\ne\n", .other = "a\nb\nc\nd\nX\ne\n", .want = "a\nX\ne\n", .conflicts = 0 },
.{ .name = "both delete overlapping ranges", .base = "a\nb\nc\nd\ne\n", .current = "a\nd\ne\n", .other = "a\nb\ne\n", .want = "a\n<<<<<<< current\nd\n||||||| base\nb\nc\nd\n=======\nb\n>>>>>>> other\ne\n", .conflicts = 1 },
.{ .name = "insert at start vs edit first", .base = "a\nb\n", .current = "X\na\nb\n", .other = "A\nb\n", .want = "<<<<<<< current\nX\na\n||||||| base\na\n=======\nA\n>>>>>>> other\nb\n", .conflicts = 1 },
.{ .name = "edit first vs delete first", .base = "a\nb\n", .current = "A\nb\n", .other = "b\n", .want = "<<<<<<< current\nA\n||||||| base\na\n=======\n>>>>>>> other\nb\n", .conflicts = 1 },
};
test "merge3 agrees with fossil 3-way-merge on crafted triples" {
const a = testing.allocator;
for (fossil_cases) |c| {
const r = try merge3(a, c.base, c.current, c.other, .conflict);
defer r.deinit(a);
testing.expectEqualStrings(c.want, r.bytes) catch |err| {
std.debug.print("case: {s}\n", .{c.name});
return err;
};
try testing.expectEqual(c.conflicts, r.conflicts.len);
}
}
test "merge3 keeps a final newline change that Fossil drops" {
const a = testing.allocator;
// Fossil's diff compares lines without their newlines, so current adding
// the final newline is no change to it and it writes "A\nb". Here that
// addition is an edit next to other's, and both are kept.
const r = try merge3(a, "a\nb", "a\nb\n", "A\nb", .conflict);
defer r.deinit(a);
try testing.expectEqualStrings("A\nb\n", r.bytes);
try testing.expect(!hasConflict(r));
}
test "merge3 never joins a final line without a newline to the other side's append" {
const a = testing.allocator;
// Current drops the final newline; other appends a line after it. Fossil
// writes "Xb\n", a line neither side has. Here the two edits conflict.
for ([_][3][]const u8{
.{ "a\n", "X", "a\nb\n" },
.{ "a\n", "a\nb\n", "X" },
.{ "e\nc\nc\nd\nc\nc\n", "e\nc\nd\nc", "e\ne\nc\nc\nd\nc\nc\nb\n" },
}) |t| {
const r = try merge3(a, t[0], t[1], t[2], .conflict);
defer r.deinit(a);
try testing.expectEqual(@as(usize, 1), r.conflicts.len);
}
const r = try merge3(a, "a\n", "X", "a\nb\n", .conflict);
defer r.deinit(a);
try testing.expectEqualStrings(
"<<<<<<< current\nX\n||||||| base\na\n=======\na\nb\n>>>>>>> other\n",
r.bytes,
);
}
test "merge3 keeps a byte-order mark that Fossil drops" {
const a = testing.allocator;
// Fossil strips the mark from all three inputs before it diffs them and
// then, since the copies no longer start with one, does not write it
// back. Here the mark is part of the first line on every side.
const r = try merge3(a, "\xef\xbb\xbfa\nb\nc\n", "\xef\xbb\xbfa\nB\nc\n", "\xef\xbb\xbfa\nb\nC\n", .conflict);
defer r.deinit(a);
try testing.expectEqualStrings("\xef\xbb\xbfa\nB\nC\n", r.bytes);
}
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 line diff's invariants for one pair, the ones the merge 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);
const triples = try linediff.diff(gpa, base, side, .{});
defer gpa.free(triples);
linediff.matchFrom(triples, 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 "merge line diff 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 "merge line diff 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 "merge line diff never matches a final line across a newline change" {
const a = testing.allocator;
var m: [2]?usize = undefined;
const triples = try linediff.diff(a, "a\nb", "a\nb\n", .{});
defer a.free(triples);
linediff.matchFrom(triples, &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, .{});
}