//! 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, 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 lines: std.ArrayList(Line) = .empty;
errdefer lines.deinit(gpa);
var start: usize = 0;
while (std.mem.indexOfScalarPos(u8, bytes, start, '\n')) |nl| {
try lines.append(gpa, .{ .start = start, .end = nl + 1 });
start = nl + 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), and the match count is a TRUE longest common subsequence: the
/// same length the O(n*m) table gives (`lcsOracle`, kept for the tests).
///
/// The core is Myers' O(ND) algorithm in its linear-space form (Eugene W.
/// Myers, "An O(ND) Difference Algorithm and Its Variations", 1986, §4b),
/// in the shape libxdiff's `xdl_split`/`xdl_recs_cmp` gave it: forward and
/// backward furthest-reaching searches meet on a middle snake, the problem
/// splits there, and each half first strips its common prefix and suffix.
/// D is the edit distance, so two adjacent versions of a 15k-line file that
/// differ in a hundred lines cost 15k*100 steps, not 225 million cells
///. Lines are interned to integer ids first so every comparison
/// on the search frontier is one integer compare.
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);
for (x_match) |*slot| slot.* = null;
if (x.len == 0 or y.len == 0) return;
var ids: LineIds = .{};
defer ids.deinit(gpa);
const xa = try ids.intern(gpa, x_bytes, x);
defer gpa.free(xa);
const ya = try ids.intern(gpa, y_bytes, y);
defer gpa.free(ya);
// Diagonal k = xi - yi ranges over [-m, n]; both frontiers are indexed by
// k and read one past each end, hence m+1 of offset and n+m+3 of room.
const room = x.len + y.len + 3;
const kvd = try gpa.alloc(isize, 2 * room);
defer gpa.free(kvd);
var work: std.ArrayList(Range) = .empty;
defer work.deinit(gpa);
try work.append(gpa, .{ .x0 = 0, .x1 = x.len, .y0 = 0, .y1 = y.len });
var m: Myers = .{
.a = xa,
.b = ya,
.kvdf = kvd[0..room],
.kvdb = kvd[room..],
.offset = @intCast(y.len + 1),
.match = x_match,
};
while (work.pop()) |r| {
if (m.split(r)) |halves| {
try work.append(gpa, halves[0]);
try work.append(gpa, halves[1]);
}
}
}
/// A half-open rectangle `[x0,x1) x [y0,y1)` of the two line sequences.
const Range = struct { x0: usize, x1: usize, y0: usize, y1: usize };
/// Interns line contents to dense ids so the diff compares integers. The map
/// keys borrow the source buffers, which outlive the diff.
const LineIds = struct {
map: std.StringHashMapUnmanaged(u32) = .empty,
fn deinit(self: *LineIds, gpa: std.mem.Allocator) void {
self.map.deinit(gpa);
}
fn intern(self: *LineIds, gpa: std.mem.Allocator, bytes: []const u8, lines: []const Line) error{OutOfMemory}![]u32 {
const out = try gpa.alloc(u32, lines.len);
errdefer gpa.free(out);
for (lines, out) |line, *id| {
const gop = try self.map.getOrPut(gpa, lineBytes(bytes, line));
if (!gop.found_existing) gop.value_ptr.* = @intCast(self.map.count() - 1);
id.* = gop.value_ptr.*;
}
return out;
}
};
const Myers = struct {
a: []const u32,
b: []const u32,
/// Forward frontier: furthest x reached on diagonal k, indexed k+offset.
kvdf: []isize,
/// Backward frontier: nearest x reached on diagonal k, indexed k+offset.
kvdb: []isize,
offset: isize,
match: []?usize,
/// Strip the common prefix and suffix of `r` (recording those matches),
/// then find a point on a middle snake of what remains and return the
/// two strictly smaller sub-rectangles around it; null when nothing is
/// left to split.
fn split(m: *Myers, r0: Range) ?[2]Range {
var r = r0;
while (r.x0 < r.x1 and r.y0 < r.y1 and m.a[r.x0] == m.b[r.y0]) {
m.match[r.x0] = r.y0;
r.x0 += 1;
r.y0 += 1;
}
while (r.x1 > r.x0 and r.y1 > r.y0 and m.a[r.x1 - 1] == m.b[r.y1 - 1]) {
r.x1 -= 1;
r.y1 -= 1;
m.match[r.x1] = r.y1;
}
if (r.x0 == r.x1 or r.y0 == r.y1) return null;
const p = m.middle(r);
assert(p.x > r.x0 or p.y > r.y0);
assert(p.x < r.x1 or p.y < r.y1);
return .{
.{ .x0 = r.x0, .x1 = p.x, .y0 = r.y0, .y1 = p.y },
.{ .x0 = p.x, .x1 = r.x1, .y0 = p.y, .y1 = r.y1 },
};
}
const Point = struct { x: usize, y: usize };
fn f(m: *Myers, k: isize) *isize {
return &m.kvdf[@intCast(k + m.offset)];
}
fn bk(m: *Myers, k: isize) *isize {
return &m.kvdb[@intCast(k + m.offset)];
}
/// A point on a middle snake of `r`, whose sides share no first or last
/// line and are both non-empty. Forward and backward searches advance one
/// edit at a time; the first overlap on a diagonal is on a shortest edit
/// script, so splitting there keeps the total LCS maximal.
fn middle(m: *Myers, r: Range) Point {
const x0: isize = @intCast(r.x0);
const x1: isize = @intCast(r.x1);
const y0: isize = @intCast(r.y0);
const y1: isize = @intCast(r.y1);
const dmin = x0 - y1;
const dmax = x1 - y0;
const fmid = x0 - y0;
const bmid = x1 - y1;
const odd = @mod(fmid - bmid, 2) != 0;
var fmin = fmid;
var fmax = fmid;
var bmin = bmid;
var bmax = bmid;
m.f(fmid).* = x0;
m.bk(bmid).* = x1;
while (true) {
if (fmin > dmin) {
fmin -= 1;
m.f(fmin - 1).* = -1;
} else fmin += 1;
if (fmax < dmax) {
fmax += 1;
m.f(fmax + 1).* = -1;
} else fmax -= 1;
var k = fmax;
while (k >= fmin) : (k -= 2) {
var xi: isize = if (m.f(k - 1).* >= m.f(k + 1).*) m.f(k - 1).* + 1 else m.f(k + 1).*;
var yi = xi - k;
while (xi < x1 and yi < y1 and m.a[@intCast(xi)] == m.b[@intCast(yi)]) {
xi += 1;
yi += 1;
}
m.f(k).* = xi;
if (odd and bmin <= k and k <= bmax and m.bk(k).* <= xi) {
return .{ .x = @intCast(xi), .y = @intCast(yi) };
}
}
if (bmin > dmin) {
bmin -= 1;
m.bk(bmin - 1).* = std.math.maxInt(isize);
} else bmin += 1;
if (bmax < dmax) {
bmax += 1;
m.bk(bmax + 1).* = std.math.maxInt(isize);
} else bmax -= 1;
k = bmax;
while (k >= bmin) : (k -= 2) {
var xi: isize = if (m.bk(k - 1).* < m.bk(k + 1).*) m.bk(k - 1).* else m.bk(k + 1).* - 1;
var yi = xi - k;
while (xi > x0 and yi > y0 and m.a[@intCast(xi - 1)] == m.b[@intCast(yi - 1)]) {
xi -= 1;
yi -= 1;
}
m.bk(k).* = xi;
if (!odd and fmin <= k and k <= fmax and xi <= m.f(k).*) {
return .{ .x = @intCast(xi), .y = @intCast(yi) };
}
}
}
}
};
/// The O(n*m) LCS table `lcsMatch` replaced, kept as the oracle for
/// the equivalence tests: same contract, same prefix/suffix trim, exact
/// suffix-table traceback. Test-only; nothing in the binary references it.
fn lcsOracle(
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);
for (x_match) |*slot| slot.* = null;
if (x.len == 0 or y.len == 0) return;
var pre: usize = 0;
while (pre < x.len and pre < y.len and linesEql(x_bytes, x[pre], y_bytes, y[pre])) : (pre += 1) {
x_match[pre] = pre;
}
var suf: usize = 0;
while (pre + suf < x.len and pre + suf < y.len and
linesEql(x_bytes, x[x.len - 1 - suf], y_bytes, y[y.len - 1 - suf])) : (suf += 1)
{
x_match[x.len - 1 - suf] = y.len - 1 - suf;
}
const x_mid = x[pre .. x.len - suf];
const y_mid = y[pre .. y.len - suf];
const n = x_mid.len;
const m = y_mid.len;
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_mid[i], y_bytes, y_mid[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_mid[i], y_bytes, y_mid[j])) {
x_match[pre + i] = pre + 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,
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 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);
var regions: std.ArrayList(Region) = .empty;
errdefer 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;
try appendRegionRange(®ions, a, 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];
try appendRegionRange(®ions, a, .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) {
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 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 => try out.appendSlice(a, a_reg),
.theirs => try out.appendSlice(a, b_reg),
.conflict => {
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);
errdefer a.free(conflicts);
const walked = try regions.toOwnedSlice(a);
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),
a: std.mem.Allocator,
kind: RegionKind,
base: LineRange,
current: LineRange,
other: LineRange,
) error{OutOfMemory}!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;
}
};
try regions.append(a, .{ .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),
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, conflict_terminator);
}
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,
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));
}
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]);
}
/// Equivalence check for one pair: the Myers core must match exactly as many
/// lines as the O(n*m) oracle, every match must pair equal lines, and the
/// matched indices must strictly increase. WHICH equal-length alignment is
/// chosen may differ (the inherent tiebreak of any line diff).
fn expectLcsAgree(gpa: std.mem.Allocator, newer: []const u8, older: []const u8) !void {
const x = try splitLines(gpa, newer);
defer gpa.free(x);
const y = try splitLines(gpa, older);
defer gpa.free(y);
const got = try gpa.alloc(?usize, x.len);
defer gpa.free(got);
const want = try gpa.alloc(?usize, x.len);
defer gpa.free(want);
try lcsMatch(gpa, newer, x, older, y, got);
try lcsOracle(gpa, newer, x, older, y, want);
var got_n: usize = 0;
var want_n: usize = 0;
var last: ?usize = null;
for (got, want, 0..) |g, w, i| {
if (w != null) want_n += 1;
const j = g orelse continue;
got_n += 1;
try testing.expect(linesEql(newer, x[i], older, y[j]));
if (last) |l| try testing.expect(j > l);
last = j;
}
try testing.expectEqual(want_n, got_n);
}
/// 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 "lcsMatch equals the LCS oracle 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 newer = randomLines(rand, &xb, alphabet);
const older = randomLines(rand, &yb, alphabet);
try expectLcsAgree(a, newer, older);
}
}
test "lcsMatch equals the LCS oracle 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 prefix/suffix 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 expectLcsAgree(a, edited.items, base.items);
try expectLcsAgree(a, base.items, edited.items);
}
}
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{@intFromEnum(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, .{});
}