//! The line diff: zit's one engine for aligning two versions of a text, used
//! by `diff`, `annotate`, the three-way merge and every line count derived
//! from them.
//!
//! The algorithm is Fossil's, ported from src/diff.c (D. Richard Hipp):
//! `break_into_lines`, `compare_dline`, `longestCommonSequence`,
//! `optimalLCS`, `likelyNotIndentChngArtifact`, `diff_step`,
//! `appendTriple`, `diff_all` and `diff_optimize`. It is a port rather than
//! a reimplementation because the point is to agree with Fossil on which
//! copy of a repeated line two versions share. Any longest common
//! subsequence is a correct diff, but files are full of equal lines
//! (braces, blanks, a repeated statement), and a different choice among
//! equally long alignments shows a different diff and credits a different
//! check-in in annotate. So the details that look arbitrary are kept as
//! Fossil has them: the hash, the order of the hash chains, the chain
//! cutoffs, the scoring that prefers a match near the centre, the
//! whitespace table, and two comparisons in `diff_optimize` that read
//! oddly but decide which way a hunk slides.
//!
//! The result is a list of copy/delete/insert triples in Fossil's shape.
//! `optimize` is Fossil's `diff_optimize`, which slides inserted and deleted
//! blocks to read better. Fossil applies it to `diff` and to merge, and not
//! to annotate.
//!
//! Fossil's `text_diff` also drops a leading UTF-8 byte-order mark before
//! diffing; that belongs to the display diff and is done in `textdiff`, not
//! here, because merge and annotate compare the bytes as stored.
//!
//! Two departures. Lines longer than 32767 bytes, which Fossil refuses as
//! binary, are diffed here with the same hash and an exact comparison, so
//! every input has an answer. And under `newline_significant` a final line
//! without its newline is unequal to the same text with one. Fossil treats
//! the two as equal, which silently drops a newline change from a merge and
//! cannot show the `\ No newline` marker in a diff.
const std = @import("std");
const assert = std.debug.assert;
/// The engine's output version. Anything kept from its output, as the diff
/// cache keeps annotate's triples, is keyed on it: bump it whenever a change
/// here alters the triples any input gives, or a kept diff would be replayed
/// where this engine now answers differently.
pub const engine_version: u16 = 1;
/// Fossil's line-comparison flags: DIFF_STRIP_EOLCR, DIFF_IGNORE_EOLWS and
/// DIFF_IGNORE_ALLWS. `ignore_all_ws` implies `ignore_eol_ws`, as Fossil's
/// bit values make it.
pub const Flags = struct {
strip_eol_cr: bool = false,
ignore_eol_ws: bool = false,
ignore_all_ws: bool = false,
};
pub const Options = struct {
flags: Flags = .{},
/// Fossil's `diff_optimize`: on unless DIFF_NOOPT.
optimize: bool = true,
/// A final line lacking its newline differs from the same text with one.
newline_significant: bool = true,
};
/// `copy` lines common to both sides, then `delete` lines only in the
/// first, then `insert` lines only in the second. Fossil's aEdit[] triple.
pub const Triple = struct { copy: u32, delete: u32, insert: u32 };
/// Fossil's LENGTH_MASK_SZ: the low bits of a line hash hold its length.
const length_bits = 15;
const length_mask: u64 = (1 << length_bits) - 1;
const hash_multiplier: u64 = 9000000000000000041;
const hash_modulus: u64 = 281474976710597;
/// Fossil's `diffIsSpace` table. It marks backspace and not vertical tab,
/// which is not the C library's set, and is kept as it is because it decides
/// which lines compare equal under the whitespace flags.
fn isSpace(c: u8) bool {
return switch (c) {
8, 9, 10, 12, 13, ' ' => true,
else => false,
};
}
/// Fossil's DLine. `n` is the line's length after a stripped CR, the
/// length `diff_optimize` weighs. `klen` is the comparison length that
/// Fossil keeps in the hash's low bits, kept separately so a line too long
/// for those bits still compares exactly.
pub const DLine = struct {
z: []const u8,
h: u64,
klen: u32,
indent: u32,
nw: u32,
/// 1 + index of the next line in this line's hash bucket; 0 ends it.
next: u32,
/// 1 + index of the first line in the bucket this slot heads.
head: u32,
terminated: bool,
};
/// How many lines `diff` sees in `bytes`: a final line without its newline
/// counts.
pub fn lineCount(bytes: []const u8) usize {
var n = std.mem.count(u8, bytes, "\n");
if (bytes.len > 0 and bytes[bytes.len - 1] != '\n') n += 1;
return n;
}
/// Fossil's `break_into_lines`, with the hash table built only for the
/// side `longestCommonSequence` looks lines up in.
fn breakIntoLines(gpa: std.mem.Allocator, bytes: []const u8, flags: Flags, with_buckets: bool) error{OutOfMemory}![]DLine {
const n_lines = lineCount(bytes);
assert(n_lines <= std.math.maxInt(u32));
const lines = try gpa.alloc(DLine, n_lines);
errdefer gpa.free(lines);
var start: usize = 0;
for (lines) |*line| {
const nl = std.mem.indexOfScalarPos(u8, bytes, start, '\n');
const end = nl orelse bytes.len;
line.* = hashLine(bytes[start..end], flags);
line.terminated = nl != null;
start = end + 1;
}
if (with_buckets) {
for (lines, 0..) |*line, i| {
const bucket = line.h % n_lines;
line.next = lines[bucket].head;
lines[bucket].head = @intCast(i + 1);
}
}
return lines;
}
fn hashLine(raw: []const u8, flags: Flags) DLine {
var k = raw.len;
if (flags.strip_eol_cr and k > 0 and raw[k - 1] == '\r') k -= 1;
const z = raw[0..k];
if (flags.ignore_eol_ws or flags.ignore_all_ws) {
while (k > 0 and isSpace(z[k - 1])) k -= 1;
}
var h: u64 = 0;
var s: usize = 0;
var indent: usize = 0;
var nw: usize = 0;
if (flags.ignore_all_ws) {
// Fossil compares `z[s] <= ' '` on a plain `char`, so bytes 0x80 and
// up count as leading space, and the hash sign-extends each byte,
// where `char` is signed. This matches Fossil built where it is:
// x86-64 on every OS and arm64 macOS. A Fossil built where `char` is
// unsigned (arm64 Linux) hashes and indents such lines differently
// under -w.
while (s < k and @as(i8, @bitCast(z[s])) <= ' ') s += 1;
indent = s;
nw = k - s;
var numws: usize = 0;
for (z[s..k]) |c| {
if (isSpace(c)) {
numws += 1;
} else {
const ext: u64 = @bitCast(@as(i64, @as(i8, @bitCast(c))));
h = (h ^ ext) *% hash_multiplier;
}
}
k -= numws;
} else {
const k2 = k & ~@as(usize, 7);
var x: usize = 0;
while (x < k2) : (x += 8) {
h = (h ^ std.mem.readInt(u64, z[x..][0..8], .little)) *% hash_multiplier;
}
var m: u64 = 0;
for (z[k2..k], 0..) |c, i| m |= @as(u64, c) << @intCast(8 * i);
h ^= m;
}
const klen = k - s;
return .{
.z = z,
.h = ((h % hash_modulus) << length_bits) | (@as(u64, klen) & length_mask),
.klen = @intCast(klen),
.indent = @intCast(indent),
.nw = @intCast(nw),
.next = 0,
.head = 0,
.terminated = true,
};
}
/// The indent and non-space width `likelyNotIndentChngArtifact` reads, which
/// Fossil fills in lazily on a line whose `nw` is still 0. Filling them in
/// up front gives the same values: the fill depends only on the line, and
/// under ignore-all-space the lines it changes have no non-space bytes, so
/// every comparison of them is settled before `indent` is read.
fn fillWidths(lines: []DLine) void {
for (lines) |*line| {
if (line.nw != 0 or line.z.len == 0) continue;
const z = line.z;
var ii: usize = 0;
while (ii < z.len and isSpace(z[ii])) ii += 1;
var jj: usize = z.len - 1;
while (jj > ii and isSpace(z[jj])) jj -= 1;
line.indent = @intCast(ii);
line.nw = @intCast(@as(usize, jj + 1) -| ii);
}
}
const Context = struct {
gpa: std.mem.Allocator,
from: []DLine,
to: []DLine,
all_ws: bool,
newline_significant: bool,
edits: std.ArrayList(Triple) = .empty,
/// Fossil's `xDiffer`: true when the two lines differ.
fn differ(c: *const Context, a: *const DLine, b: *const DLine) bool {
if (c.newline_significant and a.terminated != b.terminated) return true;
if (a.h != b.h or a.klen != b.klen) return true;
if (std.mem.eql(u8, a.z[0..a.klen], b.z[0..a.klen])) return false;
if (!c.all_ws) return true;
// compare_dline_ignore_allws
var ai: usize = a.indent;
var bi: usize = b.indent;
while (ai < a.z.len or bi < b.z.len) {
if (ai < a.z.len and bi < b.z.len) {
const ca = a.z[ai];
const cb = b.z[bi];
ai += 1;
bi += 1;
if (ca != cb) return true;
} else if ((ai < a.z.len and !isSpace(a.z[ai])) or (bi < b.z.len and !isSpace(b.z[bi]))) {
// One side is spent and the other has text left. Fossil
// loops here forever; only a hash collision gets here.
return true;
}
while (ai < a.z.len and isSpace(a.z[ai])) ai += 1;
while (bi < b.z.len and isSpace(b.z[bi])) bi += 1;
}
return a.z.len - ai != b.z.len - bi;
}
fn differAt(c: *const Context, i: usize, j: usize) bool {
return c.differ(&c.from[i], &c.to[j]);
}
/// Fossil's `appendTriple`: fold into the previous triple where the
/// script reads the same either way.
fn appendTriple(c: *Context, n_copy: usize, n_del: usize, n_ins: usize) error{OutOfMemory}!void {
const copy: u32 = @intCast(n_copy);
const del: u32 = @intCast(n_del);
const ins: u32 = @intCast(n_ins);
if (c.edits.items.len >= 1) {
const last = &c.edits.items[c.edits.items.len - 1];
if (last.insert == 0) {
if (last.delete == 0) {
last.copy += copy;
last.delete += del;
last.insert += ins;
return;
}
if (copy == 0) {
last.delete += del;
last.insert += ins;
return;
}
}
if (copy == 0 and del == 0) {
last.insert += ins;
return;
}
}
c.edits.appendAssumeCapacity(.{ .copy = copy, .delete = del, .insert = ins });
}
const Span = struct { sx: usize, ex: usize, sy: usize, ey: usize };
/// Fossil's `optimalLCS`: the exhaustive search, for small ranges where
/// the hashed search found nothing.
fn optimalLcs(c: *const Context, s1: usize, e1: usize, s2: usize, e2: usize) Span {
var mx: usize = 0;
var sxb = s1;
var syb = s2;
var i = s1;
while (i + mx < e1) : (i += 1) {
var j = s2;
while (j + mx < e2) : (j += 1) {
if (c.differAt(i, j)) continue;
if (mx != 0 and c.differAt(i + mx, j + mx)) continue;
var k: usize = 1;
while (i + k < e1 and j + k < e2 and !c.differAt(i + k, j + k)) k += 1;
if (k > mx) {
sxb = i;
syb = j;
mx = k;
}
}
}
return .{ .sx = sxb, .ex = sxb + mx, .sy = syb, .ey = syb + mx };
}
/// Fossil's `longestCommonSequence`: a long run of equal lines near the
/// centre of the ranges, found through the hash chains. The bounds
/// checks against `j` mix one-based and zero-based indexes exactly as
/// Fossil's do, since they decide which candidate wins.
fn longestCommonSequence(c: *const Context, s1: usize, e1: usize, s2: usize, e2: usize) Span {
const is1: i64 = @intCast(s1);
const ie1: i64 = @intCast(e1);
const is2: i64 = @intCast(s2);
const ie2: i64 = @intCast(e2);
const span: i64 = (ie1 - is1) + (ie2 - is2);
var best_score: i64 = -9223300000 * @as(i64, 1000000000);
var sxb = is1;
var exb = is1;
var syb = is2;
var eyb = is2;
var sxp = is1;
var exp = is1;
var syp = is2;
var eyp = is2;
const mid = @divTrunc(ie1 + is1, 2);
var cutoff: usize = 4;
const n_to: u64 = c.to.len;
while (true) {
var next_cutoff: usize = 0;
var i = is1;
while (i < ie1) : (i += 1) {
const from_line = &c.from[@intCast(i)];
var limit: usize = 0;
var j: i64 = c.to[@intCast(from_line.h % n_to)].head;
while (j > 0 and (j - 1 < is2 or j >= ie2 or c.differ(from_line, &c.to[@intCast(j - 1)]))) {
if (limit > cutoff) {
j = 0;
next_cutoff = cutoff * 4;
break;
}
limit += 1;
j = c.to[@intCast(j - 1)].next;
}
if (j == 0) continue;
if (i < exb and j >= syb and j < eyb) continue;
if (i < exp and j >= syp and j < eyp) continue;
var sx = i;
var sy = j - 1;
var n = @min(sx - is1, sy - is2);
var k: i64 = 0;
while (k < n and !c.differAt(@intCast(sx - 1 - k), @intCast(sy - 1 - k))) k += 1;
sx -= k;
sy -= k;
var ex = i + 1;
var ey = j;
n = @min(ie1 - ex, ie2 - ey);
k = 0;
while (k < n and !c.differAt(@intCast(ex + k), @intCast(ey + k))) k += 1;
ex += k;
ey += k;
const skew: i64 = @intCast(@abs((sx - is1) - (sy - is2)));
const dist: i64 = @intCast(@abs(@divTrunc(sx + ex, 2) - mid));
const score = (ex - sx) * span - (skew + dist);
if (score > best_score) {
best_score = score;
sxb = sx;
syb = sy;
exb = ex;
eyb = ey;
} else if (ex > exp) {
sxp = sx;
syp = sy;
exp = ex;
eyp = ey;
}
}
if (sxb != exb or next_cutoff == 0) break;
cutoff = next_cutoff;
if (cutoff > 64) break;
}
if (sxb == exb and (ie1 - is1) * (ie2 - is2) < 2500) return c.optimalLcs(s1, e1, s2, e2);
return .{ .sx = @intCast(sxb), .ex = @intCast(exb), .sy = @intCast(syb), .ey = @intCast(eyb) };
}
/// Fossil's `likelyNotIndentChngArtifact`: whether a short common run is
/// a real match rather than braces and blanks an indentation change
/// happens to leave equal.
fn likelyNotIndentArtifact(c: *const Context, s1: usize, sx: usize, ex: usize, e1: usize) bool {
if ((ex - sx) * 7 >= e1 - s1) return true;
var n: usize = 0;
for (c.from[sx..ex]) |line| {
if (line.nw > 1) n += 1;
}
if (n == 0) return false;
for (c.from[sx..ex]) |line| {
if (line.nw <= 1) continue;
const text = line.z[line.indent..][0..line.nw];
if (c.occursIn(text, s1, sx)) continue;
if (!c.occursIn(text, ex, e1)) return true;
}
return false;
}
fn occursIn(c: *const Context, text: []const u8, lo: usize, hi: usize) bool {
for (c.from[lo..hi]) |other| {
if (other.nw != text.len) continue;
if (std.mem.eql(u8, other.z[other.indent..][0..other.nw], text)) return true;
}
return false;
}
/// Fossil's `diff_step`, with its recursion turned into an explicit
/// stack that visits the ranges in the same order, so the triples come
/// out in the same order.
fn diffStep(c: *Context, s1: usize, e1: usize, s2: usize, e2: usize) error{OutOfMemory}!void {
const Work = union(enum) {
range: [4]usize,
copy: usize,
};
// Each split leaves its right range and its copy waiting while its
// left range is worked, and the waiting copies are disjoint runs of
// both files, so at most 2*min(lines)+1 items wait, plus the three a
// split pushes. Sized up front, the stack never grows.
var stack = try std.ArrayList(Work).initCapacity(c.gpa, 2 * @min(c.from.len, c.to.len) + 4);
defer stack.deinit(c.gpa);
stack.appendAssumeCapacity(.{ .range = .{ s1, e1, s2, e2 } });
while (stack.pop()) |work| {
switch (work) {
.copy => |n| try c.appendTriple(n, 0, 0),
.range => |r| {
const is1, const ie1, const is2, const ie2 = r;
if (ie1 <= is1) {
if (ie2 > is2) try c.appendTriple(0, 0, ie2 - is2);
continue;
}
if (ie2 <= is2) {
try c.appendTriple(0, ie1 - is1, 0);
continue;
}
const m = c.longestCommonSequence(is1, ie1, is2, ie2);
if (m.ex > m.sx + 5 or (m.ex > m.sx and c.likelyNotIndentArtifact(is1, m.sx, m.ex, ie1))) {
stack.appendAssumeCapacity(.{ .range = .{ m.ex, ie1, m.ey, ie2 } });
if (m.ex > m.sx) stack.appendAssumeCapacity(.{ .copy = m.ex - m.sx });
stack.appendAssumeCapacity(.{ .range = .{ is1, m.sx, is2, m.sy } });
} else {
try c.appendTriple(0, ie1 - is1, ie2 - is2);
}
},
}
}
}
/// Fossil's `diff_all`: trim the common head and tail, diff the middle.
fn diffAll(c: *Context) error{OutOfMemory}!void {
var e1 = c.from.len;
var e2 = c.to.len;
while (e1 > 0 and e2 > 0 and !c.differAt(e1 - 1, e2 - 1)) {
e1 -= 1;
e2 -= 1;
}
const mn = @min(e1, e2);
var s: usize = 0;
while (s < mn and !c.differAt(s, s)) s += 1;
if (s > 0) try c.appendTriple(s, 0, 0);
try c.diffStep(s, e1, s, e2);
if (e1 < c.from.len) try c.appendTriple(c.from.len - e1, 0, 0);
}
/// A line's LENGTH(). Fossil can read one past the end of the first file
/// here, which is heap garbage. In this port that read is unreachable:
/// it needs an insertion at the very end whose last line equals the
/// first file's last line, and the tail trim in `diffAll` has already
/// copied such a line. The bound returns 0 for safety only.
fn lenOf(lines: []const DLine, i: usize) usize {
return if (i < lines.len) lines[i].z.len else 0;
}
/// Fossil's `diff_optimize`, over the triples plus their terminating
/// zero triple, which a shift at the end of the file can turn into a
/// copy. The shift of deletions toward the end weighs LENGTH(pTop) on
/// both sides, as Fossil's does.
fn optimize(c: *Context) error{OutOfMemory}!void {
c.edits.appendAssumeCapacity(.{ .copy = 0, .delete = 0, .insert = 0 });
const e = c.edits.items;
const from = c.from;
const to = c.to;
var ln_from: usize = 0;
var ln_to: usize = 0;
for (0..e.len) |r| {
var cpy: usize = e[r].copy;
const del: usize = e[r].delete;
const ins: usize = e[r].insert;
ln_from += cpy;
ln_to += cpy;
while (cpy > 0 and del == 0 and ins > 0) {
if (c.differ(&from[ln_from - 1], &to[ln_to + ins - 1])) break;
if (lenOf(from, ln_from) + to[ln_to + ins - 1].z.len <= from[ln_from - 1].z.len + to[ln_to + ins - 2].z.len) break;
ln_from -= 1;
ln_to -= 1;
e[r].copy -= 1;
e[r + 1].copy += 1;
cpy -= 1;
}
while (r + 1 < e.len and e[r + 1].copy > 0 and del == 0 and ins > 0) {
if (c.differ(&to[ln_to], &to[ln_to + ins])) break;
if (to[ln_to].z.len + to[ln_to + ins - 1].z.len <= to[ln_to + 1].z.len + to[ln_to + ins].z.len) break;
ln_from += 1;
ln_to += 1;
e[r].copy += 1;
e[r + 1].copy -= 1;
cpy += 1;
}
while (cpy > 0 and del > 0 and ins == 0) {
if (c.differ(&from[ln_from - 1], &from[ln_from + del - 1])) break;
if (from[ln_from].z.len + from[ln_from + del - 1].z.len <= from[ln_from - 1].z.len + from[ln_from + del - 2].z.len) break;
ln_from -= 1;
ln_to -= 1;
e[r].copy -= 1;
e[r + 1].copy += 1;
cpy -= 1;
}
while (r + 1 < e.len and e[r + 1].copy > 0 and del > 0 and ins == 0) {
if (c.differ(&from[ln_from], &from[ln_from + del])) break;
if (from[ln_from].z.len + from[ln_from + del - 1].z.len <= from[ln_from].z.len + from[ln_from + del].z.len) break;
ln_from += 1;
ln_to += 1;
e[r].copy += 1;
e[r + 1].copy -= 1;
cpy += 1;
}
ln_from += del;
ln_to += ins;
}
// Readers of Fossil's triples stop at the first all-zero one.
var end: usize = 0;
while (end < e.len and (e[end].copy | e[end].delete | e[end].insert) != 0) end += 1;
c.edits.shrinkRetainingCapacity(end);
}
};
/// The copy/delete/insert triples turning `from` into `to`, owned by `gpa`.
/// Two empty inputs give no triples; otherwise the copies and deletes sum to
/// `from`'s line count and the copies and inserts to `to`'s.
pub fn diff(gpa: std.mem.Allocator, from: []const u8, to: []const u8, opts: Options) error{OutOfMemory}![]Triple {
const from_lines = try breakIntoLines(gpa, from, opts.flags, false);
defer gpa.free(from_lines);
const to_lines = try breakIntoLines(gpa, to, opts.flags, true);
defer gpa.free(to_lines);
return diffLines(gpa, from_lines, to_lines, opts);
}
/// `bytes` split and hashed once, as `diffLines` takes either side: with
/// the hash buckets, which only the `to` side reads. A caller diffing a
/// chain of versions splits each one once rather than twice, as the newer
/// side of one diff and the older side of the next. The lines slice
/// `bytes`, which must outlive them.
pub fn breakLines(gpa: std.mem.Allocator, bytes: []const u8, flags: Flags) error{OutOfMemory}![]DLine {
return breakIntoLines(gpa, bytes, flags, true);
}
/// `diff` over lines `breakLines` made under `opts.flags`. Either array may
/// have served on either side of an earlier call: the buckets are a
/// function of the array alone, and the widths this fills in on `from` are
/// the ones `fillWidths` would fill in again.
pub fn diffLines(gpa: std.mem.Allocator, from_lines: []DLine, to_lines: []DLine, opts: Options) error{OutOfMemory}![]Triple {
fillWidths(from_lines);
var c: Context = .{
.gpa = gpa,
.from = from_lines,
.to = to_lines,
.all_ws = opts.flags.ignore_all_ws,
.newline_significant = opts.newline_significant,
};
// Every triple but the last consumes a line, so this holds them all and
// the terminating zero triple. Sizing every buffer from the line counts
// up front, and copying the result out rather than shrinking in place,
// makes the allocations a function of the input alone: growing or
// shrinking in place succeeds or not depending on the heap.
c.edits = try std.ArrayList(Triple).initCapacity(gpa, from_lines.len + to_lines.len + 2);
defer c.edits.deinit(gpa);
try c.diffAll();
if (opts.optimize) try c.optimize();
const triples = try gpa.dupe(Triple, c.edits.items);
if (std.debug.runtime_safety) {
var nf: usize = 0;
var nt: usize = 0;
for (triples) |tr| {
nf += tr.copy + tr.delete;
nt += tr.copy + tr.insert;
}
assert(nf == from_lines.len and nt == to_lines.len);
}
return triples;
}
/// For each `from` line, the `to` line the triples copy it to, or null when
/// it is deleted. `from_match.len` is `from`'s line count.
pub fn matchFrom(triples: []const Triple, from_match: []?usize) void {
var i: usize = 0;
var j: usize = 0;
for (triples) |tr| {
for (0..tr.copy) |_| {
from_match[i] = j;
i += 1;
j += 1;
}
for (0..tr.delete) |_| {
from_match[i] = null;
i += 1;
}
j += tr.insert;
}
assert(i == from_match.len);
}
/// For each `to` line, the `from` line the triples copy it from, or null
/// when it is inserted. `to_match.len` is `to`'s line count.
pub fn matchTo(triples: []const Triple, to_match: []?usize) void {
var i: usize = 0;
var j: usize = 0;
for (triples) |tr| {
for (0..tr.copy) |_| {
to_match[j] = i;
i += 1;
j += 1;
}
i += tr.delete;
for (0..tr.insert) |_| {
to_match[j] = null;
j += 1;
}
}
assert(j == to_match.len);
}
// --- tests -----------------------------------------------------------------
const testing = std.testing;
fn expectTriples(from: []const u8, to: []const u8, opts: Options, want: []const [3]u32) !void {
const got = try diff(testing.allocator, from, to, opts);
defer testing.allocator.free(got);
const as_arrays = try testing.allocator.alloc([3]u32, got.len);
defer testing.allocator.free(as_arrays);
for (got, as_arrays) |tr, *a| a.* = .{ tr.copy, tr.delete, tr.insert };
try testing.expectEqualSlices([3]u32, want, as_arrays);
}
test "linediff: empty and identical inputs" {
try expectTriples("", "", .{}, &.{});
try expectTriples("a\nb\n", "a\nb\n", .{}, &.{.{ 2, 0, 0 }});
try expectTriples("", "a\n", .{}, &.{.{ 0, 0, 1 }});
try expectTriples("a\n", "", .{}, &.{.{ 0, 1, 0 }});
}
test "linediff: a final newline matters only under newline_significant" {
try expectTriples("a\nb", "a\nb\n", .{}, &.{.{ 1, 1, 1 }});
try expectTriples("a\nb", "a\nb\n", .{ .newline_significant = false }, &.{.{ 2, 0, 0 }});
}
test "linediff: CR and whitespace flags decide equality as Fossil's do" {
try expectTriples("a\r\n", "a\n", .{}, &.{.{ 0, 1, 1 }});
try expectTriples("a\r\n", "a\n", .{ .flags = .{ .strip_eol_cr = true } }, &.{.{ 1, 0, 0 }});
try expectTriples("a \n", "a\n", .{ .flags = .{ .ignore_eol_ws = true } }, &.{.{ 1, 0, 0 }});
try expectTriples(" a b\n", "ab\n", .{ .flags = .{ .ignore_all_ws = true } }, &.{.{ 1, 0, 0 }});
// Fossil's space table has backspace and lacks vertical tab.
try expectTriples("a\x08\n", "a\n", .{ .flags = .{ .ignore_eol_ws = true } }, &.{.{ 1, 0, 0 }});
try expectTriples("a\x0b\n", "a\n", .{ .flags = .{ .ignore_eol_ws = true } }, &.{.{ 0, 1, 1 }});
}
test "linediff: the hash is Fossil's" {
// Values from Fossil's break_into_lines for these lines.
const empty = hashLine("", .{});
try testing.expectEqual(@as(u64, 0), empty.h);
const short = hashLine("abc", .{});
try testing.expectEqual(((@as(u64, 0x636261) % hash_modulus) << 15) | 3, short.h);
const eight = hashLine("abcdefgh", .{});
const word = std.mem.readInt(u64, "abcdefgh", .little);
try testing.expectEqual((((word *% hash_multiplier) % hash_modulus) << 15) | 8, eight.h);
}
test "linediff: matchFrom and matchTo invert each other" {
const triples = try diff(testing.allocator, "a\nb\nc\nd\n", "a\nx\nc\nd\ny\n", .{});
defer testing.allocator.free(triples);
var from_match: [4]?usize = undefined;
var to_match: [5]?usize = undefined;
matchFrom(triples, &from_match);
matchTo(triples, &to_match);
try testing.expectEqualSlices(?usize, &.{ 0, null, 2, 3 }, &from_match);
try testing.expectEqualSlices(?usize, &.{ 0, null, 2, 3, null }, &to_match);
}
/// Pairs whose alignment depends on Fossil's choices among equal lines, with
/// the triples `fossil xdiff --raw` (2.28) prints for them, `--noopt` first.
const fossil_fixtures = [_]struct {
name: []const u8,
from: []const u8,
to: []const u8,
noopt: []const [3]u32,
opt: []const [3]u32,
}{
.{
.name = "a function inserted between two functions slides past the shared brace",
.from = "int f(void){\n return 1;\n}\n\nint h(void){\n return 3;\n}\n",
.to = "int f(void){\n return 1;\n}\n\nint g(void){\n return 2;\n}\n\nint h(void){\n return 3;\n}\n",
.noopt = &.{ .{ 2, 0, 4 }, .{ 5, 0, 0 } },
.opt = &.{ .{ 3, 0, 4 }, .{ 4, 0, 0 } },
},
.{
.name = "a moved block is a delete and an insert",
.from = "alpha\nbeta\ngamma\ndelta one\ndelta two\ndelta three\nepsilon\nzeta\n",
.to = "alpha\ndelta one\ndelta two\ndelta three\nbeta\ngamma\nepsilon\nzeta\n",
.noopt = &.{ .{ 1, 2, 0 }, .{ 3, 0, 2 }, .{ 2, 0, 0 } },
.opt = &.{ .{ 1, 2, 0 }, .{ 3, 0, 2 }, .{ 2, 0, 0 } },
},
.{
.name = "runs of blank lines",
.from = "a\n\n\nb\n\nc\n\n\n\nd\n",
.to = "a\n\nb\n\n\n\nc\n\nd\n\n",
.noopt = &.{ .{ 2, 1, 0 }, .{ 1, 0, 2 }, .{ 3, 2, 0 }, .{ 1, 0, 1 } },
.opt = &.{ .{ 2, 1, 0 }, .{ 1, 0, 2 }, .{ 3, 2, 0 }, .{ 1, 0, 1 } },
},
.{
.name = "a reindent keeps no brace-only match",
.from = "if (x) {\n foo();\n bar();\n}\nbaz();\n",
.to = "if (y) {\n if (x) {\n foo();\n bar();\n }\n}\nbaz();\n",
.noopt = &.{ .{ 0, 3, 5 }, .{ 2, 0, 0 } },
.opt = &.{ .{ 0, 3, 5 }, .{ 2, 0, 0 } },
},
.{
.name = "repeated statements keep the copies Fossil keeps",
.from = "x();\ny();\nx();\nz();\nx();\nw();\nx();\n",
.to = "x();\nz();\nx();\nx();\n",
.noopt = &.{ .{ 1, 2, 0 }, .{ 2, 1, 0 }, .{ 1, 0, 0 } },
.opt = &.{ .{ 1, 2, 0 }, .{ 2, 1, 0 }, .{ 1, 0, 0 } },
},
.{
.name = "a deleted block at the end keeps the trailing brace and blank",
.from = "a\n}\n\nb\n}\n\n",
.to = "a\n}\n\n",
.noopt = &.{ .{ 1, 3, 0 }, .{ 2, 0, 0 } },
.opt = &.{ .{ 1, 3, 0 }, .{ 2, 0, 0 } },
},
.{
.name = "repeated braces and blanks across many hash-chain entries",
.from = "}\n\nl2\n}\n\nl5\n}\n\nl1\n}\n\nl4\n}\n\nl0\n}\n\nl3\n}\n\nl6\n}\n\nl2\n}\n\nl5\n}\n\nl1\n}\n\nl4\n}\n\nl0\n}\n\nl3\n}\n\nl6\n}\n\nl2\n}\n\nl5\n}\n\nl1\n}\n\nl4\n}\n\nl0\n}\n\nl3\n",
.to = "}\n\n\nl2\n}\n\n\nl5\n}\n\n\nl1\n}\n\nl4\n}\n\nl0\n}\n\nm3\n}\n\nl6\n}\n\nl2\n}\n\nl5\n}\n\nl1\n}\n\nl4\n}\n\nl0\n}\n\nm3\n}\n\nl6\n}\n\nl2\n}\n\nl5\n}\n\nl1\n}\n\nl4\n}\n\nl0\n}\n\nl3\n",
.noopt = &.{ .{ 2, 0, 1 }, .{ 3, 0, 1 }, .{ 2, 0, 1 }, .{ 10, 1, 1 }, .{ 20, 1, 1 }, .{ 21, 0, 0 } },
.opt = &.{ .{ 1, 0, 1 }, .{ 3, 0, 1 }, .{ 3, 0, 1 }, .{ 10, 1, 1 }, .{ 20, 1, 1 }, .{ 21, 0, 0 } },
},
.{
.name = "a run of equal lines splits where the head and tail trims meet",
.from = "x\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\n",
.to = "x\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\ny\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\nx\n",
.noopt = &.{ .{ 15, 0, 6 }, .{ 25, 0, 0 } },
.opt = &.{ .{ 15, 0, 6 }, .{ 25, 0, 0 } },
},
.{
.name = "a reversed file",
.from = "p\nq\nr\ns\n",
.to = "s\nr\nq\np\n",
.noopt = &.{ .{ 0, 2, 1 }, .{ 1, 1, 2 } },
.opt = &.{ .{ 0, 2, 1 }, .{ 1, 1, 2 } },
},
};
fn expectSameAsDiff(gpa: std.mem.Allocator, from: []DLine, to: []DLine, from_bytes: []const u8, to_bytes: []const u8, opts: Options) !void {
const want = try diff(gpa, from_bytes, to_bytes, opts);
defer gpa.free(want);
const got = try diffLines(gpa, from, to, opts);
defer gpa.free(got);
try testing.expectEqualSlices(Triple, want, got);
}
test "linediff: one line array per version serves as either side, as diff's own do" {
const gpa = testing.allocator;
for (fossil_fixtures) |f| {
errdefer std.debug.print("fixture: {s}\n", .{f.name});
for ([_]Options{ .{ .optimize = false }, .{}, .{ .flags = .{ .ignore_all_ws = true } }, .{ .flags = .{ .strip_eol_cr = true }, .optimize = false, .newline_significant = false } }) |opts| {
const from = try breakLines(gpa, f.from, opts.flags);
defer gpa.free(from);
const to = try breakLines(gpa, f.to, opts.flags);
defer gpa.free(to);
try testing.expectEqual(lineCount(f.to), to.len);
// `to` first as the newer side, then as the older one, as a
// version is diffed against its parent and then its child.
try expectSameAsDiff(gpa, from, to, f.from, f.to, opts);
try expectSameAsDiff(gpa, to, from, f.to, f.from, opts);
try expectSameAsDiff(gpa, from, to, f.from, f.to, opts);
try expectSameAsDiff(gpa, to, to, f.to, f.to, opts);
}
}
}
test "linediff: Fossil's own triples on crafted pairs" {
for (fossil_fixtures) |f| {
errdefer std.debug.print("fixture: {s}\n", .{f.name});
try expectTriples(f.from, f.to, .{ .optimize = false }, f.noopt);
try expectTriples(f.from, f.to, .{}, f.opt);
}
}