//! 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;
/// How a diff is rendered. `ignore_whitespace` is fossil's "Ignore
/// Whitespace": lines that differ only in whitespace compare EQUAL, so a
/// reindent or a line-ending normalization produces no hunks at all.
///
/// It changes comparison only, never emission — a line that does survive
/// into a hunk is emitted with its original bytes, whitespace intact,
/// because the reader is being shown the file, not the comparison key.
pub const Options = struct {
context: usize = default_context,
ignore_whitespace: bool = false,
};
/// `line` with every ASCII whitespace byte removed — the comparison key
/// under `Options.ignore_whitespace`. Squeezing rather than collapsing runs
/// is `diff -w`'s rule (and fossil's): "a b" and "ab" are the same line.
/// A line never contains LF (the splitter consumed it), so stripping CR
/// here is what makes a CRLF/LF difference invisible, which is the
/// line-ending case the flag exists for.
fn whitespaceKey(arena: std.mem.Allocator, line: []const u8) error{OutOfMemory}![]const u8 {
const dst = try arena.alloc(u8, line.len);
var n: usize = 0;
for (line) |c| {
if (std.ascii.isWhitespace(c)) continue;
dst[n] = c;
n += 1;
}
return dst[0..n];
}
/// 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,
opts: Options,
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);
var edits: std.ArrayList(Edit) = .empty;
defer edits.deinit(gpa);
try lineEdits(gpa, a_bytes, b_bytes, opts, &a_lines, &b_lines, &edits);
try renderHunks(gpa, a_lines.items, b_lines.items, edits.items, opts.context, out);
}
/// Lines added and removed going from `a_bytes` to `b_bytes`: the `+` and
/// `-` lines `unified` would render, counted off the same edit script without
/// rendering them. Binary detection stays the caller's (`isBinary`).
pub const LineCounts = struct { added: usize, removed: usize };
pub fn lineCounts(
gpa: std.mem.Allocator,
a_bytes: []const u8,
b_bytes: []const u8,
opts: Options,
) error{OutOfMemory}!LineCounts {
var a_lines: std.ArrayList(Line) = .empty;
defer a_lines.deinit(gpa);
var b_lines: std.ArrayList(Line) = .empty;
defer b_lines.deinit(gpa);
var edits: std.ArrayList(Edit) = .empty;
defer edits.deinit(gpa);
try lineEdits(gpa, a_bytes, b_bytes, opts, &a_lines, &b_lines, &edits);
var counts: LineCounts = .{ .added = 0, .removed = 0 };
for (edits.items) |e| {
counts.added += e.ins;
counts.removed += e.del;
}
return counts;
}
/// `diff --by`: the same edit script rendered as a side-by-side HTML
/// table — one row per line pair, `eq`/`del`/`ins`/`chg` classes, text
/// escaped. Every line is shown; the classes carry the diff.
pub fn sideBySideHtml(
gpa: std.mem.Allocator,
a_bytes: []const u8,
b_bytes: []const u8,
opts: Options,
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);
var edits: std.ArrayList(Edit) = .empty;
defer edits.deinit(gpa);
try lineEdits(gpa, a_bytes, b_bytes, opts, &a_lines, &b_lines, &edits);
try out.appendSlice(gpa, "<table class=\"sbs\">\n");
var ai: usize = 0;
var bi: usize = 0;
for (edits.items) |e| {
var k: usize = 0;
while (k < e.equal) : (k += 1) {
try sbsRow(gpa, out, "eq", ai + 1, a_lines.items[ai].bytes, bi + 1, b_lines.items[bi].bytes);
ai += 1;
bi += 1;
}
const paired = @min(e.del, e.ins);
k = 0;
while (k < paired) : (k += 1) {
try sbsRow(gpa, out, "chg", ai + 1, a_lines.items[ai].bytes, bi + 1, b_lines.items[bi].bytes);
ai += 1;
bi += 1;
}
k = paired;
while (k < e.del) : (k += 1) {
try sbsRow(gpa, out, "del", ai + 1, a_lines.items[ai].bytes, 0, "");
ai += 1;
}
k = paired;
while (k < e.ins) : (k += 1) {
try sbsRow(gpa, out, "ins", 0, "", bi + 1, b_lines.items[bi].bytes);
bi += 1;
}
}
try out.appendSlice(gpa, "</table>\n");
}
fn sbsRow(gpa: std.mem.Allocator, out: *std.ArrayList(u8), class: []const u8, an: usize, a: []const u8, bn: usize, b: []const u8) error{OutOfMemory}!void {
try out.appendSlice(gpa, "<tr class=\"");
try out.appendSlice(gpa, class);
try out.appendSlice(gpa, "\"><td class=\"n\">");
if (an != 0) try out.print(gpa, "{d}", .{an});
try out.appendSlice(gpa, "</td><td>");
try htmlEscape(gpa, out, a);
try out.appendSlice(gpa, "</td><td class=\"n\">");
if (bn != 0) try out.print(gpa, "{d}", .{bn});
try out.appendSlice(gpa, "</td><td>");
try htmlEscape(gpa, out, b);
try out.appendSlice(gpa, "</td></tr>\n");
}
pub fn htmlEscape(gpa: std.mem.Allocator, out: *std.ArrayList(u8), text: []const u8) error{OutOfMemory}!void {
for (text) |c| switch (c) {
'&' => try out.appendSlice(gpa, "&"),
'<' => try out.appendSlice(gpa, "<"),
'>' => try out.appendSlice(gpa, ">"),
'"' => try out.appendSlice(gpa, """),
else => try out.append(gpa, c),
};
}
/// Split both sides into lines and compute the edit script `unified` and
/// `sideBySideHtml` both render. The lists borrow the input bytes.
fn lineEdits(
gpa: std.mem.Allocator,
a_bytes: []const u8,
b_bytes: []const u8,
opts: Options,
a_lines: *std.ArrayList(Line),
b_lines: *std.ArrayList(Line),
edits: *std.ArrayList(Edit),
) error{OutOfMemory}!void {
try splitLines(gpa, a_bytes, a_lines);
try splitLines(gpa, b_bytes, b_lines);
var interner = Interner{ .gpa = gpa };
defer interner.deinit();
// Comparison keys under `ignore_whitespace` outlive each `idOf` call (the
// interner borrows them as map keys), so they live on an arena freed with
// the rest of this call's scratch.
var key_arena = std.heap.ArenaAllocator.init(gpa);
defer key_arena.deinit();
const keys = key_arena.allocator();
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.
if (opts.ignore_whitespace) {
for (a_lines.items, a_ids) |line, *id| id.* = try interner.idOf(try whitespaceKey(keys, line.bytes));
for (b_lines.items, b_ids) |line, *id| id.* = try interner.idOf(try whitespaceKey(keys, line.bytes));
} else {
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;
}
}
try diffRange(gpa, a_ids, b_ids, edits);
}
/// 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, .{}, &out);
try t.expectEqualStrings(want, out.items);
}
fn expectUnifiedW(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, .{ .ignore_whitespace = true }, &out);
try t.expectEqualStrings(want, out.items);
}
test "textdiff -w: whitespace-only differences produce no hunks" {
// Indentation, interior runs, trailing space, and CRLF-vs-LF are all
// whitespace, so each of these pairs is "unchanged" under -w and a full
// diff without it.
try expectUnifiedW("a\n b\nc\n", "a\nb\nc\n", "");
try expectUnifiedW("x = 1\n", "x=1\n", "");
try expectUnifiedW("a\t\nb\n", "a\nb\n", "");
try expectUnifiedW("a\r\nb\r\n", "a\nb\n", "");
// The same inputs without the flag are real differences — otherwise the
// test above would pass for the wrong reason.
var out: std.ArrayList(u8) = .empty;
defer out.deinit(t.allocator);
try unified(t.allocator, "a\n b\nc\n", "a\nb\nc\n", .{}, &out);
try t.expect(out.items.len != 0);
}
test "textdiff -w: a real change still diffs, and emits ORIGINAL bytes" {
// -w changes comparison, never emission: the surviving line keeps its own
// whitespace, so a reader sees the file rather than the comparison key.
var out: std.ArrayList(u8) = .empty;
defer out.deinit(t.allocator);
try unified(t.allocator, " keep\nold\n", " keep\n new\n", .{ .ignore_whitespace = true }, &out);
try t.expect(std.mem.indexOf(u8, out.items, "+ new") != null);
try t.expect(std.mem.indexOf(u8, out.items, "-old") != null);
}
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"));
}
/// The `+` and `-` lines of a rendered diff, the way `--numstat` used to
/// count them: hunk headers, context and the newline marker are neither.
fn countRendered(rendered: []const u8) LineCounts {
var counts: LineCounts = .{ .added = 0, .removed = 0 };
var lines = std.mem.splitScalar(u8, rendered, '\n');
while (lines.next()) |line| {
if (line.len == 0) continue;
switch (line[0]) {
'+' => counts.added += 1,
'-' => counts.removed += 1,
else => {},
}
}
return counts;
}
test "textdiff: lineCounts equals the + and - lines unified renders" {
const gpa = t.allocator;
const cases = [_][2][]const u8{
.{ "", "" },
.{ "", "a\nb\n" },
.{ "a\nb\n", "" },
.{ "a\nend", "a\nend\n" },
.{ "a\r\nb\r\n", "a\nb\n" },
.{ "1\n2\n3\n4\n5\n", "1\nX\n3\nY\n5\n" },
.{ "-x\n+y\n", "+x\n-y\n" },
};
for (cases) |c| {
for ([_]bool{ false, true }) |ws| {
const opts: Options = .{ .ignore_whitespace = ws };
var out: std.ArrayList(u8) = .empty;
defer out.deinit(gpa);
try unified(gpa, c[0], c[1], opts, &out);
try t.expectEqual(countRendered(out.items), try lineCounts(gpa, c[0], c[1], opts));
}
}
// Random small buffers over a tiny alphabet: repeated lines, missing
// final newlines and whitespace-only differences all come up often.
var prng = std.Random.DefaultPrng.init(0x7e57_11e5);
const r = prng.random();
const alphabet = "ab \n\r";
var round: usize = 0;
while (round < 2000) : (round += 1) {
var a: [24]u8 = undefined;
var b: [24]u8 = undefined;
const al = r.uintLessThan(usize, a.len + 1);
const bl = r.uintLessThan(usize, b.len + 1);
for (a[0..al]) |*x| x.* = alphabet[r.uintLessThan(usize, alphabet.len)];
for (b[0..bl]) |*x| x.* = alphabet[r.uintLessThan(usize, alphabet.len)];
const opts: Options = .{ .ignore_whitespace = r.boolean() };
var out: std.ArrayList(u8) = .empty;
defer out.deinit(gpa);
try unified(gpa, a[0..al], b[0..bl], opts, &out);
try t.expectEqual(countRendered(out.items), try lineCounts(gpa, a[0..al], b[0..bl], opts));
}
}