//! 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 Fossil's line diff (`linediff`, ported from Fossil's
//! diff.c), with Fossil's `diff_optimize` sliding each block to the edge
//! Fossil would show, so `zit diff` and `fossil diff` draw the same changes.
const std = @import("std");
const linediff = @import("linediff.zig");
/// 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,
};
/// One aligned step of the edit script: lines the two sides share, then
/// lines only in a, then lines only in b.
const Edit = linediff.Triple;
/// 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;
}
}
}
/// One file's hunks as `diff -F json` reports them: null when either side
/// is binary (`binary: true`, `diff: null`), else the unified hunks without
/// a banner, owned by `gpa`. An absent side is passed as empty.
pub fn fileHunks(gpa: std.mem.Allocator, old: []const u8, new: []const u8, opts: Options) error{OutOfMemory}!?[]u8 {
if (isBinary(old) or isBinary(new)) return null;
var hunks: std.ArrayList(u8) = .empty;
errdefer hunks.deinit(gpa);
try unified(gpa, old, new, opts, &hunks);
return try hunks.toOwnedSlice(gpa);
}
/// 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);
const edits = try lineEdits(gpa, a_bytes, b_bytes, opts, &a_lines, &b_lines);
defer gpa.free(edits);
try renderHunks(gpa, a_lines.items, b_lines.items, edits, 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);
const edits = try lineEdits(gpa, a_bytes, b_bytes, opts, &a_lines, &b_lines);
defer gpa.free(edits);
var counts: LineCounts = .{ .added = 0, .removed = 0 };
for (edits) |e| {
counts.added += e.insert;
counts.removed += e.delete;
}
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);
const edits = try lineEdits(gpa, a_bytes, b_bytes, opts, &a_lines, &b_lines);
defer gpa.free(edits);
try out.appendSlice(gpa, "<table class=\"sbs\">\n");
var ai: usize = 0;
var bi: usize = 0;
for (edits) |e| {
var k: usize = 0;
while (k < e.copy) : (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.delete, e.insert);
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.delete) : (k += 1) {
try sbsRow(gpa, out, "del", ai + 1, a_lines.items[ai].bytes, 0, "");
ai += 1;
}
k = paired;
while (k < e.insert) : (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),
};
}
/// `bytes` without a leading UTF-8 byte-order mark. Fossil's `text_diff`
/// drops it first (`blob_to_utf8_no_bom`), so adding or removing one is no
/// change in `fossil diff`, and the first line is shown without it.
fn withoutBom(bytes: []const u8) []const u8 {
const bom = "\xEF\xBB\xBF";
return if (std.mem.startsWith(u8, bytes, bom)) bytes[bom.len..] else bytes;
}
/// Split both sides into lines and compute the edit script `unified` and
/// `sideBySideHtml` both render, as Fossil's `diff` computes it: the
/// whitespace flag is Fossil's `-w`, and the blocks are optimized. A final
/// line without its newline differs from the same text with one, so the
/// marker renders. The lists borrow the input bytes; the caller frees the
/// script.
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),
) error{OutOfMemory}![]Edit {
const a_text = withoutBom(a_bytes);
const b_text = withoutBom(b_bytes);
try splitLines(gpa, a_text, a_lines);
try splitLines(gpa, b_text, b_lines);
return linediff.diff(gpa, a_text, b_text, .{
.flags = .{ .ignore_all_ws = opts.ignore_whitespace },
});
}
/// 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.copy);
try ops.appendNTimes(gpa, .del, e.delete);
try ops.appendNTimes(gpa, .ins, e.insert);
}
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: a line inserted before a repeated brace stays inside its function" {
// The repeated `}` lines must not glue 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: a leading UTF-8 byte-order mark is no change, as in fossil diff" {
// `fossil xdiff` prints no hunk for the first pair, and shows the first
// line without the mark in the second.
try expectUnified("\xEF\xBB\xBFa\nb\n", "a\nb\n", "");
try expectUnified("\xEF\xBB\xBFa\nb\n", "a\nc\n", "@@ -1,2 +1,2 @@\n a\n-b\n+c\n");
try t.expectEqual(LineCounts{ .added = 0, .removed = 0 }, try lineCounts(t.allocator, "a\n", "\xEF\xBB\xBFa\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));
}
}