//! Line-oriented unified diff — the textual-hunk half of `zit diff`.
//!
//! NOT AN RFC SURFACE. No draft specifies a diff rendering; this module is
//! zit's own design, shaped by the smol contract: one well-defined problem
//! (two byte buffers in, unified hunks out), behavior most users expect
//! (`@@ -l,n +l,n @@` hunks, three context lines, the standard
//! no-trailing-newline marker), and no ambient anything — pure functions of
//! their inputs.
//!
//! The alignment is PATIENCE DIFF over interned line identities: lines
//! unique to both sides anchor the alignment (longest increasing subsequence
//! over their pairing), and the gaps between anchors recurse. A gap with no
//! unique anchors falls back to a bounded LCS table when it is small and to
//! an honest whole-gap replacement when it is not — bounded memory on
//! pathological inputs, never a quadratic surprise. Patience favors the
//! hunks a human would draw (moved-past braces do not glue unrelated
//! functions together), which is why it is git's `--patience` and the shape
//! most modern tools converged on.
const std = @import("std");
/// The classic three lines of leading/trailing context per hunk.
pub const default_context: usize = 3;
/// The LCS-fallback ceiling: a gap with no unique-line anchors runs the
/// exact dynamic program only when `a_len * b_len` stays under this bound
/// (a 256 x 256 gap = 64 KiB of u16 cells); a larger anchorless gap becomes
/// one replacement run. Exactness where it is cheap, a stated bound where
/// it is not.
const lcs_cell_cap: usize = 256 * 256;
/// One aligned edit: how many lines the two sides advance together (equal
/// run) and then apart (deleted from a, inserted into b). The whole diff is
/// a sequence of these; rendering walks it once.
const Edit = struct {
equal: usize,
del: usize,
ins: usize,
};
/// A borrowed line: the byte slice EXCLUDING its newline, plus whether the
/// newline was present (the last line of an unterminated buffer lacks it,
/// and unified output must say so).
const Line = struct {
bytes: []const u8,
terminated: bool,
};
/// True when `bytes` should be treated as binary: a NUL anywhere in the
/// buffer. The caller renders "binary files differ" instead of hunks.
pub fn isBinary(bytes: []const u8) bool {
return std.mem.indexOfScalar(u8, bytes, 0) != null;
}
/// Split `bytes` into lines, newline excluded, final-line termination
/// recorded. An empty buffer is zero lines.
fn splitLines(gpa: std.mem.Allocator, bytes: []const u8, out: *std.ArrayList(Line)) error{OutOfMemory}!void {
var start: usize = 0;
while (start < bytes.len) {
if (std.mem.indexOfScalarPos(u8, bytes, start, '\n')) |nl| {
try out.append(gpa, .{ .bytes = bytes[start..nl], .terminated = true });
start = nl + 1;
} else {
try out.append(gpa, .{ .bytes = bytes[start..], .terminated = false });
return;
}
}
}
/// Intern each line to a dense id so every later comparison is an integer
/// compare. Ids are shared across both sides — equality of ids IS equality
/// of line bytes.
const Interner = struct {
gpa: std.mem.Allocator,
ids: std.StringHashMapUnmanaged(u32) = .empty,
next: u32 = 0,
fn idOf(self: *Interner, line: []const u8) error{OutOfMemory}!u32 {
const gop = try self.ids.getOrPut(self.gpa, line);
if (!gop.found_existing) {
gop.value_ptr.* = self.next;
self.next += 1;
}
return gop.value_ptr.*;
}
fn deinit(self: *Interner) void {
self.ids.deinit(self.gpa);
}
};
/// Emit edits aligning `a[a0..a1]` with `b[b0..b1]` (id slices) into `out`
/// as (del, ins) runs; equal runs are appended by the caller around the
/// recursion. Patience: anchor on lines unique within BOTH ranges, LIS the
/// anchors, recurse between them.
fn diffRange(
gpa: std.mem.Allocator,
a: []const u32,
b: []const u32,
out: *std.ArrayList(Edit),
) error{OutOfMemory}!void {
// Common prefix / suffix first: cheap, and it feeds the anchor pass
// smaller ranges.
var lo: usize = 0;
while (lo < a.len and lo < b.len and a[lo] == b[lo]) lo += 1;
var a_hi = a.len;
var b_hi = b.len;
while (a_hi > lo and b_hi > lo and a[a_hi - 1] == b[b_hi - 1]) {
a_hi -= 1;
b_hi -= 1;
}
if (lo > 0) try pushEqual(gpa, out, lo);
const am = a[lo..a_hi];
const bm = b[lo..b_hi];
if (am.len == 0 or bm.len == 0) {
if (am.len != 0 or bm.len != 0) try pushEdit(gpa, out, am.len, bm.len);
} else if (try patienceAnchors(gpa, am, bm, out)) {
// recursed inside
} else if (am.len * bm.len <= lcs_cell_cap) {
try lcsFallback(gpa, am, bm, out);
} else {
// Anchorless and large: one honest replacement run.
try pushEdit(gpa, out, am.len, bm.len);
}
if (a.len - a_hi > 0) try pushEqual(gpa, out, a.len - a_hi);
}
/// The patience core: pair lines unique in both ranges, take the longest
/// increasing subsequence of the pairing, and recurse between consecutive
/// anchors. Returns false when no anchor exists (the caller falls back).
fn patienceAnchors(
gpa: std.mem.Allocator,
a: []const u32,
b: []const u32,
out: *std.ArrayList(Edit),
) error{OutOfMemory}!bool {
// Occurrence counts and last positions per id, both sides.
const Occ = struct { count: u32 = 0, pos: usize = 0 };
var in_a: std.AutoHashMapUnmanaged(u32, Occ) = .empty;
defer in_a.deinit(gpa);
var in_b: std.AutoHashMapUnmanaged(u32, Occ) = .empty;
defer in_b.deinit(gpa);
for (a, 0..) |id, i| {
const gop = try in_a.getOrPut(gpa, id);
if (!gop.found_existing) gop.value_ptr.* = .{};
gop.value_ptr.count += 1;
gop.value_ptr.pos = i;
}
for (b, 0..) |id, i| {
const gop = try in_b.getOrPut(gpa, id);
if (!gop.found_existing) gop.value_ptr.* = .{};
gop.value_ptr.count += 1;
gop.value_ptr.pos = i;
}
// Candidate anchors in a-order: unique on both sides.
const Pair = struct { a: usize, b: usize };
var pairs: std.ArrayList(Pair) = .empty;
defer pairs.deinit(gpa);
for (a, 0..) |id, i| {
const oa = in_a.get(id).?;
if (oa.count != 1) continue;
const ob = in_b.get(id) orelse continue;
if (ob.count != 1) continue;
try pairs.append(gpa, .{ .a = i, .b = ob.pos });
}
if (pairs.items.len == 0) return false;
// Longest increasing subsequence over b-positions (a-positions are
// already ascending): patience sorting with binary search, O(n log n).
const tails = try gpa.alloc(usize, pairs.items.len); // index into pairs
defer gpa.free(tails);
const back = try gpa.alloc(?usize, pairs.items.len);
defer gpa.free(back);
var piles: usize = 0;
for (pairs.items, 0..) |p, i| {
var lo: usize = 0;
var hi: usize = piles;
while (lo < hi) {
const mid = (lo + hi) / 2;
if (pairs.items[tails[mid]].b < p.b) lo = mid + 1 else hi = mid;
}
back[i] = if (lo > 0) tails[lo - 1] else null;
tails[lo] = i;
if (lo == piles) piles += 1;
}
var chain: std.ArrayList(Pair) = .empty;
defer chain.deinit(gpa);
var at: ?usize = tails[piles - 1];
while (at) |i| {
try chain.append(gpa, pairs.items[i]);
at = back[i];
}
std.mem.reverse(Pair, chain.items);
// Recurse between anchors; each anchor itself is one equal line.
var a0: usize = 0;
var b0: usize = 0;
for (chain.items) |anchor| {
try diffRange(gpa, a[a0..anchor.a], b[b0..anchor.b], out);
try pushEqual(gpa, out, 1);
a0 = anchor.a + 1;
b0 = anchor.b + 1;
}
try diffRange(gpa, a[a0..], b[b0..], out);
return true;
}
/// Exact LCS dynamic program for small anchorless gaps. Table bound is the
/// caller's `lcs_cell_cap` check; cells are u16 (a gap side never exceeds
/// 256 under the cap... unless the other side is 1 — lengths still fit).
fn lcsFallback(
gpa: std.mem.Allocator,
a: []const u32,
b: []const u32,
out: *std.ArrayList(Edit),
) error{OutOfMemory}!void {
const w = b.len + 1;
const cells = try gpa.alloc(u16, (a.len + 1) * w);
defer gpa.free(cells);
@memset(cells, 0);
var i: usize = a.len;
while (i > 0) {
i -= 1;
var j: usize = b.len;
while (j > 0) {
j -= 1;
cells[i * w + j] = if (a[i] == b[j])
cells[(i + 1) * w + j + 1] + 1
else
@max(cells[(i + 1) * w + j], cells[i * w + j + 1]);
}
}
var x: usize = 0;
var y: usize = 0;
while (x < a.len and y < b.len) {
if (a[x] == b[y]) {
try pushEqual(gpa, out, 1);
x += 1;
y += 1;
} else if (cells[(x + 1) * w + y] >= cells[x * w + y + 1]) {
try pushEdit(gpa, out, 1, 0);
x += 1;
} else {
try pushEdit(gpa, out, 0, 1);
y += 1;
}
}
if (a.len - x > 0 or b.len - y > 0) try pushEdit(gpa, out, a.len - x, b.len - y);
}
/// Append an equal run, folding into a trailing equal edit when possible.
fn pushEqual(gpa: std.mem.Allocator, out: *std.ArrayList(Edit), n: usize) error{OutOfMemory}!void {
std.debug.assert(n > 0);
if (out.items.len > 0) {
const last = &out.items[out.items.len - 1];
if (last.del == 0 and last.ins == 0) {
last.equal += n;
return;
}
}
try out.append(gpa, .{ .equal = n, .del = 0, .ins = 0 });
}
/// Append a delete/insert run, folding into a trailing edit that has no
/// intervening equal lines.
fn pushEdit(gpa: std.mem.Allocator, out: *std.ArrayList(Edit), del: usize, ins: usize) error{OutOfMemory}!void {
std.debug.assert(del > 0 or ins > 0);
if (out.items.len > 0) {
const last = &out.items[out.items.len - 1];
if (last.equal == 0 or (last.del == 0 and last.ins == 0 and last.equal == 0)) {
// never merges across an equal run
}
if (last.equal > 0 and last.del == 0 and last.ins == 0) {
// the previous entry is a pure equal run: start a fresh edit
} else if (out.items.len > 0 and out.items[out.items.len - 1].equal == 0) {
out.items[out.items.len - 1].del += del;
out.items[out.items.len - 1].ins += ins;
return;
}
}
try out.append(gpa, .{ .equal = 0, .del = del, .ins = ins });
}
/// Render the unified diff of `a_bytes` vs `b_bytes` into `out`: zero or
/// more `@@` hunks with `context` lines of surrounding context and the
/// standard `\ No newline at end of file` marker. Emits NOTHING when the
/// buffers are line-identical. The caller owns file headers (`---`/`+++`)
/// and binary detection (`isBinary`).
pub fn unified(
gpa: std.mem.Allocator,
a_bytes: []const u8,
b_bytes: []const u8,
context: usize,
out: *std.ArrayList(u8),
) error{OutOfMemory}!void {
var a_lines: std.ArrayList(Line) = .empty;
defer a_lines.deinit(gpa);
var b_lines: std.ArrayList(Line) = .empty;
defer b_lines.deinit(gpa);
try splitLines(gpa, a_bytes, &a_lines);
try splitLines(gpa, b_bytes, &b_lines);
var interner = Interner{ .gpa = gpa };
defer interner.deinit();
const a_ids = try gpa.alloc(u32, a_lines.items.len);
defer gpa.free(a_ids);
const b_ids = try gpa.alloc(u32, b_lines.items.len);
defer gpa.free(b_ids);
// Termination participates in identity: a final line without its newline
// is not equal to the same bytes with one, and the marker must say so.
for (a_lines.items, a_ids) |line, *id| id.* = try interner.idOf(line.bytes);
for (b_lines.items, b_ids) |line, *id| id.* = try interner.idOf(line.bytes);
if (a_lines.items.len > 0 and b_lines.items.len > 0) {
const la = a_lines.items[a_lines.items.len - 1];
const lb = b_lines.items[b_lines.items.len - 1];
if (a_ids[a_ids.len - 1] == b_ids[b_ids.len - 1] and la.terminated != lb.terminated) {
// Same bytes, different termination: force them unequal so the
// edit script rewrites the final line and the marker renders.
b_ids[b_ids.len - 1] = interner.next;
}
}
var edits: std.ArrayList(Edit) = .empty;
defer edits.deinit(gpa);
try diffRange(gpa, a_ids, b_ids, &edits);
try renderHunks(gpa, a_lines.items, b_lines.items, edits.items, context, out);
}
/// Walk the edit script and emit `@@` hunks: changed runs plus `context`
/// equal lines on both flanks, adjacent changes folded into one hunk when
/// their contexts touch.
fn renderHunks(
gpa: std.mem.Allocator,
a_lines: []const Line,
b_lines: []const Line,
edits: []const Edit,
context: usize,
out: *std.ArrayList(u8),
) error{OutOfMemory}!void {
// Flatten the script into per-line ops so hunk grouping is one pass.
const Op = enum { equal, del, ins };
var ops: std.ArrayList(Op) = .empty;
defer ops.deinit(gpa);
for (edits) |e| {
try ops.appendNTimes(gpa, .equal, e.equal);
try ops.appendNTimes(gpa, .del, e.del);
try ops.appendNTimes(gpa, .ins, e.ins);
}
var i: usize = 0;
var a_at: usize = 0; // a-line index at ops[i]
var b_at: usize = 0;
while (i < ops.items.len) {
if (ops.items[i] == .equal) {
i += 1;
a_at += 1;
b_at += 1;
continue;
}
// A change starts here. The hunk opens `context` equal lines back and
// extends until a gap of more than 2*context equal lines (or the end).
const lead = @min(context, a_at); // equal lines are equal on both sides
var a_end = a_at;
var b_end = b_at;
var trail: usize = 0;
var j = i;
while (j < ops.items.len) : (j += 1) {
switch (ops.items[j]) {
.equal => {
trail += 1;
a_end += 1;
b_end += 1;
if (trail > 2 * context) break;
},
.del => {
trail = 0;
a_end += 1;
},
.ins => {
trail = 0;
b_end += 1;
},
}
}
const keep_trail = @min(trail, context);
const drop_trail = trail - keep_trail;
// On the break path `j` still points AT the equal op that overflowed
// the gap — it is counted in `trail`, so count it as consumed too.
const consumed = @min(j + 1, ops.items.len);
const hunk_end = consumed - drop_trail;
const a_start = a_at - lead;
const b_start = b_at - lead;
// Count the hunk's a/b line spans by replay (clearer than closed-form
// arithmetic over four cursors, and this pass is bounded by the hunk).
var a_n: usize = 0;
var b_n: usize = 0;
var k = i - lead;
while (k < hunk_end) : (k += 1) {
switch (ops.items[k]) {
.equal => {
a_n += 1;
b_n += 1;
},
.del => a_n += 1,
.ins => b_n += 1,
}
}
try appendHunkHeader(gpa, out, a_start, a_n, b_start, b_n);
var a_cur = a_start;
var b_cur = b_start;
k = i - lead;
while (k < hunk_end) : (k += 1) {
switch (ops.items[k]) {
.equal => {
try appendDiffLine(gpa, out, ' ', a_lines[a_cur]);
a_cur += 1;
b_cur += 1;
},
.del => {
try appendDiffLine(gpa, out, '-', a_lines[a_cur]);
a_cur += 1;
},
.ins => {
try appendDiffLine(gpa, out, '+', b_lines[b_cur]);
b_cur += 1;
},
}
}
i = hunk_end;
a_at = a_cur;
b_at = b_cur;
}
}
/// `@@ -start,count +start,count @@` with unified's 1-based starts, the
/// `start`-0-when-empty convention, and git/GNU's `,count` OMITTED when the
/// count is exactly 1 — byte-compatible with `git diff` hunk headers, which
/// is what downstream diff consumers are tuned against.
fn appendHunkHeader(
gpa: std.mem.Allocator,
out: *std.ArrayList(u8),
a_start: usize,
a_n: usize,
b_start: usize,
b_n: usize,
) error{OutOfMemory}!void {
var buf: [80]u8 = undefined;
var w = std.Io.Writer.fixed(&buf);
const a_disp: usize = if (a_n == 0) a_start else a_start + 1;
const b_disp: usize = if (b_n == 0) b_start else b_start + 1;
w.print("@@ -{d}", .{a_disp}) catch unreachable;
if (a_n != 1) w.print(",{d}", .{a_n}) catch unreachable;
w.print(" +{d}", .{b_disp}) catch unreachable;
if (b_n != 1) w.print(",{d}", .{b_n}) catch unreachable;
w.print(" @@\n", .{}) catch unreachable;
try out.appendSlice(gpa, w.buffered());
}
/// One rendered diff line: marker, bytes, newline — and the standard
/// no-newline marker when the source line was unterminated.
fn appendDiffLine(gpa: std.mem.Allocator, out: *std.ArrayList(u8), marker: u8, line: Line) error{OutOfMemory}!void {
try out.append(gpa, marker);
try out.appendSlice(gpa, line.bytes);
try out.append(gpa, '\n');
if (!line.terminated) try out.appendSlice(gpa, "\\ No newline at end of file\n");
}
const t = std.testing;
fn expectUnified(a: []const u8, b: []const u8, want: []const u8) !void {
var out: std.ArrayList(u8) = .empty;
defer out.deinit(t.allocator);
try unified(t.allocator, a, b, default_context, &out);
try t.expectEqualStrings(want, out.items);
}
test "textdiff: identical buffers emit nothing" {
try expectUnified("a\nb\nc\n", "a\nb\nc\n", "");
try expectUnified("", "", "");
}
test "textdiff: one changed line carries three context lines each side" {
try expectUnified(
"1\n2\n3\n4\n5\n6\n7\n8\n9\n",
"1\n2\n3\n4\nX\n6\n7\n8\n9\n",
"@@ -2,7 +2,7 @@\n 2\n 3\n 4\n-5\n+X\n 6\n 7\n 8\n",
);
}
test "textdiff: pure addition and pure deletion" {
try expectUnified("a\n", "a\nb\n", "@@ -1 +1,2 @@\n a\n+b\n");
try expectUnified("a\nb\n", "a\n", "@@ -1,2 +1 @@\n a\n-b\n");
try expectUnified("", "n\n", "@@ -0,0 +1 @@\n+n\n");
try expectUnified("g\n", "", "@@ -1 +0,0 @@\n-g\n");
}
test "textdiff: nearby changes fold into one hunk, distant ones split" {
// Changes 2 apart (< 2*context): one hunk.
try expectUnified(
"1\n2\n3\n4\n5\n",
"1\nX\n3\nY\n5\n",
"@@ -1,5 +1,5 @@\n 1\n-2\n+X\n 3\n-4\n+Y\n 5\n",
);
// Changes far apart: two hunks.
try expectUnified(
"1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\n",
"X\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\nY\n",
"@@ -1,4 +1,4 @@\n-1\n+X\n 2\n 3\n 4\n@@ -10,4 +10,4 @@\n 10\n 11\n 12\n-13\n+Y\n",
);
}
test "textdiff: the no-trailing-newline marker renders on both sides" {
try expectUnified(
"a\nend",
"a\nend\n",
"@@ -1,2 +1,2 @@\n a\n-end\n\\ No newline at end of file\n+end\n",
);
try expectUnified(
"a\nold\n",
"a\nnew",
"@@ -1,2 +1,2 @@\n a\n-old\n+new\n\\ No newline at end of file\n",
);
}
test "textdiff: patience anchors keep unique lines aligned" {
// The unique `fn middle` line anchors; the repeated `}` lines cannot
// confuse the alignment into gluing the two functions together.
try expectUnified(
"fn a() {\n}\nfn middle() {\n}\n",
"fn a() {\nnew\n}\nfn middle() {\n}\n",
"@@ -1,4 +1,5 @@\n fn a() {\n+new\n }\n fn middle() {\n }\n",
);
}
test "textdiff: isBinary triggers on NUL only" {
try t.expect(isBinary("a\x00b"));
try t.expect(!isBinary("plain text\nwith lines\n"));
}