Artifact 1483a7a5a14a2a532cb0f211c58e2ac072f2e6825398a701bf37fd7fa2d868c0:
- File
src/merge3.zig
— part of check-in
[a6c2215859]
at
2026-09-07 01:09:01
on branch trunk
— annotate: per-file hashes in the crosslink record, Myers diff
The crosslink record now carries each changed file's artifact hash (fossil's mlink shape), so annotate reads blobs by hash instead of re-deriving every manifest on the walk. merge3 moves to a linear-space Myers LCS and annotate caches plaintext and baselines across versions. Repocache format 5, checkpoint format 5: the first open after upgrading re-derives. Help states the 12-character prefix annotate actually prints. (user: dmestas, size: 43707) [annotate] [blame] [check-ins using]
//! Pure three-way (diff3) line merge engine behind `zit merge` //! (contracts/merge.md, B-merge-1..24). Deep module, no I/O: every entry point //! takes an injected allocator and byte slices and yields a value — no ambient //! time, randomness, filesystem, or network (B-merge-6). The closed error set is //! `error{OutOfMemory}` ONLY: every base/current/other byte triple is a valid //! input that yields a result, so `InvalidInput` is defined out of existence //! (B-merge-6). The verb layer (main.zig) imports this module, computes the //! outcome set purely, and hands it to `update.applyMerge`; `commit` scans the //! materialized bytes for `conflict_sentinel`. //! //! Two surfaces: `merge3` is the line engine (clean where at most one side //! changed a region, or both changed it identically; else a marker envelope + //! recorded span). `classifyFile` is the per-path presence×equality classifier //! that decides unchanged / take_other / delete / clean_merge / text_conflict / //! whole_file_conflict WITHOUT the CLI re-deriving the matrix. The both-modified //! binary case short-circuits to `whole_file_conflict` before `merge3` is ever //! reached (B-merge-21), so the binary guarantee is not laundered through the //! line merger. const std = @import("std"); const assert = std.debug.assert; /// A merged buffer plus the spans of `bytes` that hold conflict envelopes. /// Both slices are owned by the allocator passed to the producer; the caller /// frees them (an arena in the CLI). `conflicts` is empty for a clean merge. pub const Result = struct { bytes: []u8, conflicts: []const Span }; /// A half-open byte range `[start, start+len)` into a `Result.bytes`. pub const Span = struct { start: usize, len: usize }; /// True when the merge produced at least one conflict envelope. pub fn hasConflict(r: Result) bool { return r.conflicts.len != 0; } /// The first line of every conflict envelope: seven `<` then a space, at a line /// start. `writeEnvelope` is the SOLE producer of this sentinel, and `commit` /// keys its refusal scan on it (B-merge-10). Keep the 7-`<`+SP shape stable. /// How a region both sides changed DIFFERENTLY is resolved (#91 item 1). /// /// `.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, // caller writes the whole-file envelope }; // --- line model ----------------------------------------------------------- /// One line as a half-open byte range into its source buffer. A line includes /// its trailing '\n' except a final line with no newline, so concatenating /// every line's bytes reproduces the source buffer exactly. Public so `annotate` /// splits a version's content on the exact boundaries this engine diffs on /// (contracts/annotate.md B-annotate-6: one line model, never a second). pub const Line = struct { start: usize, end: usize }; /// Split `bytes` into `Line` ranges. Empty input yields zero lines. Public: the /// one line splitter shared by `merge3` and `annotate`. pub fn splitLines(gpa: std.mem.Allocator, bytes: []const u8) error{OutOfMemory}![]Line { var lines: std.ArrayList(Line) = .empty; errdefer lines.deinit(gpa); var start: usize = 0; 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 /// (zit#176). 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 (zit#176), 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); // Regions indexed 0..=k: region m spans (prev sync, next sync); for m<k the // matched line `syncs[m]` is emitted verbatim after its preceding region. const k = syncs.items.len; var m: usize = 0; while (m <= k) : (m += 1) { const o_lo = if (m == 0) 0 else syncs.items[m - 1].io + 1; const o_hi = if (m == k) o_lines.len else syncs.items[m].io; const a_lo = if (m == 0) 0 else syncs.items[m - 1].ia + 1; const a_hi = if (m == k) a_lines.len else syncs.items[m].ia; const b_lo = if (m == 0) 0 else syncs.items[m - 1].ib + 1; const b_hi = if (m == k) b_lines.len else syncs.items[m].ib; const o_reg = regionBytes(base, o_lines, o_lo, o_hi); const a_reg = regionBytes(current, a_lines, a_lo, a_hi); const b_reg = regionBytes(other, b_lines, b_lo, b_hi); const a_changed = !std.mem.eql(u8, a_reg, o_reg); const b_changed = !std.mem.eql(u8, b_reg, o_reg); if (!a_changed and !b_changed) { try out.appendSlice(a, o_reg); } else if (a_changed and !b_changed) { try out.appendSlice(a, a_reg); } else if (!a_changed and b_changed) { try out.appendSlice(a, b_reg); } else if (std.mem.eql(u8, a_reg, b_reg)) { // Both sides made the identical change — clean, take either. try out.appendSlice(a, a_reg); } else 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); 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); } } return .{ .bytes = bytes, .conflicts = conflicts }; } /// 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, }; 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-vs-modify (B-merge-19) if (other == null) return .whole_file_conflict; // modify-vs-delete (B-merge-19) // Both present and both modified. Binary on ANY side is a whole-file // conflict BY CONSTRUCTION — the line engine is never reached (B-merge-21). if (isBinary(base.?) or isBinary(current.?) or isBinary(other.?)) { // 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, }; } 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| { a.free(r.bytes); a.free(r.conflicts); }, else => {}, } } test "merge3 clean disjoint edits merge (B-merge-1)" { const a = testing.allocator; const r = try merge3(a, "A\nB\nC\n", "A1\nB\nC\n", "A\nB\nC1\n", .conflict); defer a.free(r.bytes); defer a.free(r.conflicts); try testing.expectEqualStrings("A1\nB\nC1\n", r.bytes); try testing.expect(!hasConflict(r)); } test "merge3 identical edits both sides merge to that content" { const a = testing.allocator; const r = try merge3(a, "A\nB\nC\n", "A\nX\nC\n", "A\nX\nC\n", .conflict); defer a.free(r.bytes); defer a.free(r.conflicts); try testing.expectEqualStrings("A\nX\nC\n", r.bytes); try testing.expect(!hasConflict(r)); } test "merge3 only one side changed is clean" { const a = testing.allocator; const r = try merge3(a, "A\nB\nC\n", "A\nB\nC\n", "A\nZ\nC\n", .conflict); defer a.free(r.bytes); defer a.free(r.conflicts); try testing.expectEqualStrings("A\nZ\nC\n", r.bytes); try testing.expect(!hasConflict(r)); } test "merge3 overlapping edits emit diff3 envelope (B-merge-7)" { const a = testing.allocator; const r = try merge3(a, "A\nB\nC\n", "A\nX\nC\n", "A\nY\nC\n", .conflict); defer a.free(r.bytes); defer a.free(r.conflicts); try testing.expect(hasConflict(r)); try testing.expectEqual(@as(usize, 1), r.conflicts.len); // The sentinel is present and starts a line (index 0 or after a '\n'). const idx = std.mem.indexOf(u8, r.bytes, conflict_sentinel).?; try testing.expect(idx == 0 or r.bytes[idx - 1] == '\n'); // Full diff3 envelope, in order, with every region byte. const expected = "A\n" ++ "<<<<<<< current\nX\n||||||| base\nB\n=======\nY\n>>>>>>> other\n" ++ "C\n"; try testing.expectEqualStrings(expected, r.bytes); // The recorded span points exactly at the envelope. const span = r.conflicts[0]; try testing.expectEqualStrings( "<<<<<<< current\nX\n||||||| base\nB\n=======\nY\n>>>>>>> other\n", r.bytes[span.start .. span.start + span.len], ); } test "merge3 empty base merges added content" { const a = testing.allocator; // Both add distinct content over an empty base at the same position → conflict. const r = try merge3(a, "", "X\n", "Y\n", .conflict); defer a.free(r.bytes); defer a.free(r.conflicts); try testing.expect(hasConflict(r)); } test "classifyFile equal sides and both-absent are unchanged (B-merge-1)" { const a = testing.allocator; try testing.expectEqual(FileOutcome.unchanged, try classifyFile(a, "b", "same", "same", .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, try classifyFile(a, "b\n", null, "o\n", .conflict)); // current modified, other deleted (symmetric). try testing.expectEqual(FileOutcome.whole_file_conflict, 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, 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 "classifyFile both-modified binary is whole_file_conflict bypassing merge3 (B-merge-21)" { const a = testing.allocator; // Each side carries a NUL; current and other differ in DISJOINT byte-line // regions, so the line engine would clean-merge them. The binary guard must // return whole_file_conflict without ever calling merge3. const base = "H\x00\nM\nT\n"; const current = "H1\x00\nM\nT\n"; // changed first region const other = "H\x00\nM\nT1\n"; // changed last region try testing.expectEqual( FileOutcome.whole_file_conflict, try classifyFile(a, base, current, other, .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 (zit#176)" { 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 (zit#176)" { 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 = &.{} })); try testing.expect(hasConflict(.{ .bytes = "", .conflicts = &.{.{ .start = 0, .len = 1 }} })); } test "writeEnvelope produces the sentinel at a line start" { const a = testing.allocator; const env = try writeEnvelope(a, "cur\n", "base\n", "oth\n"); defer a.free(env); try testing.expectEqualStrings( "<<<<<<< current\ncur\n||||||| base\nbase\n=======\noth\n>>>>>>> other\n", env, ); try testing.expect(std.mem.startsWith(u8, env, conflict_sentinel)); // A null side renders as an empty region; markers still line-aligned. const env2 = try writeEnvelope(a, "cur\n", null, null); defer a.free(env2); try testing.expectEqualStrings( "<<<<<<< current\ncur\n||||||| base\n=======\n>>>>>>> other\n", env2, ); } /// Fill `buf` with a byte triple's worth of adversarial content: mostly ASCII /// letters and newlines (to exercise the line splitter) with occasional NUL and /// high bytes. Pure over the injected `rand`. fn fuzzFill(rand: std.Random, buf: []u8) usize { const len = rand.uintLessThan(usize, buf.len + 1); for (buf[0..len]) |*b| { b.* = switch (rand.uintLessThan(u8, 10)) { 0, 1, 2 => '\n', 3 => 0, // NUL — makes the side binary 4 => rand.int(u8), // full range else => 'A' + rand.uintLessThan(u8, 6), // A..F, small alphabet → line reuse }; } return len; } /// One deterministic fuzz pass: fold every merge3/classifyFile output for a /// fixed seed into a running hash. Same seed ⇒ same returned hash. fn fuzzPass(seed: u64) u64 { const a = testing.allocator; var prng = std.Random.DefaultPrng.init(seed); const rand = prng.random(); var h = std.hash.Wyhash.init(0); var round: usize = 0; while (round < 400) : (round += 1) { var bb: [64]u8 = undefined; var cb: [64]u8 = undefined; var ob: [64]u8 = undefined; const base = bb[0..fuzzFill(rand, &bb)]; const current = cb[0..fuzzFill(rand, &cb)]; const other = ob[0..fuzzFill(rand, &ob)]; if (merge3(a, base, current, other, .conflict)) |r| { h.update(r.bytes); for (r.conflicts) |s| { h.update(std.mem.asBytes(&s.start)); h.update(std.mem.asBytes(&s.len)); } a.free(r.bytes); a.free(r.conflicts); } else |_| { h.update("E"); // OOM (or any declared error) folds in deterministically } // classifyFile over presence-varied Sides on the same bytes. const bs: Side = if (round & 1 == 0) base else null; const cs: Side = if (round & 2 == 0) current else null; const os: Side = if (round & 4 == 0) other else null; if (classifyFile(a, bs, cs, os, .conflict)) |outcome| { h.update(&[_]u8{@intFromEnum(outcome)}); switch (outcome) { .clean_merge, .text_conflict => |r| { h.update(r.bytes); a.free(r.bytes); a.free(r.conflicts); }, else => {}, } } else |_| { h.update("F"); } } return h.final(); } test "merge3 seeded deterministic fuzz never crashes (B-merge-24)" { // Fixed seed (no ambient rng). Two passes at the same seed must be // byte-identical; the engine returns a value or a declared error, never a // crash, for every adversarial triple. const first = fuzzPass(0x5EED_1234_ABCD_0001); const second = fuzzPass(0x5EED_1234_ABCD_0001); try testing.expectEqual(first, second); // A different seed should (overwhelmingly) diverge — sanity that the hash // actually depends on inputs. const other = fuzzPass(0x0BAD_C0DE_0000_0002); try testing.expect(first != other); } fn merge3NoLeak(a: std.mem.Allocator) error{OutOfMemory}!void { // A conflict input exercises the envelope + span allocations. const r = try merge3(a, "A\nB\nC\n", "A\nX\nC\n", "A\nY\nC\n", .conflict); a.free(r.bytes); a.free(r.conflicts); } test "merge3 leak-free under checkAllAllocationFailures" { try testing.checkAllAllocationFailures(testing.allocator, merge3NoLeak, .{}); } fn classifyNoLeak(a: std.mem.Allocator) error{OutOfMemory}!void { // Both-modified text drives an internal merge3 allocation. const outcome = try classifyFile(a, "A\nB\nC\n", "A1\nB\nC\n", "A\nB\nC1\n", .conflict); freeOutcome(a, outcome); } test "classifyFile leak-free under checkAllAllocationFailures" { try testing.checkAllAllocationFailures(testing.allocator, classifyNoLeak, .{}); }