//! Seeded fuzz target for `linediff.zig` — the properties every line diff
//! must have, whatever alignment it chooses among equal lines:
//!
//! 1. The triples tile both inputs: copies and deletes sum to the first
//! input's line count, copies and inserts to the second's.
//! 2. Replaying the triples reproduces the second input byte for byte.
//! Under exact comparison (no flag, newline significant) a copied line
//! is taken from the FIRST input, so a copy that pairs unequal lines
//! fails here; under the flags copies are taken from the second input
//! and the replay checks only that the triples walk it in order.
//! 3. A file diffed against itself is one copy of every line.
//!
//! Which copy of a repeated line the diff keeps is Fossil's choice and is
//! checked against Fossil itself by the crafted fixtures in linediff.zig and
//! the smoke lane, not here. Registered as `linediff_properties` in
//! fuzz_tests.zig; the fixed-seed `test` at the foot runs it under
//! `zig build test`.
const std = @import("std");
const linediff = @import("zit").linediff;
const max_lines: usize = 40;
/// Few distinct bodies, so lines repeat, plus the bytes the flags treat
/// specially: a CR, trailing spaces, a tab, an empty line.
const alphabet = [_][]const u8{ "}", "", "{", "x();", "x(); ", "\tx();", "y\r", "y" };
fn generate(rand: std.Random, out: *std.ArrayList(u8), gpa: std.mem.Allocator) !void {
out.clearRetainingCapacity();
const n = rand.uintLessThan(usize, max_lines + 1);
for (0..n) |_| {
try out.appendSlice(gpa, alphabet[rand.uintLessThan(usize, alphabet.len)]);
try out.append(gpa, '\n');
}
// A final line without its newline, sometimes.
if (out.items.len > 0 and rand.uintLessThan(u8, 4) == 0) _ = out.pop();
}
/// The second input derived from the first by a few line edits, so most of
/// it is shared and the alignment has real choices to make.
fn mutate(rand: std.Random, from: []const u8, out: *std.ArrayList(u8), gpa: std.mem.Allocator) !void {
out.clearRetainingCapacity();
var it = std.mem.splitScalar(u8, from, '\n');
while (it.next()) |line| {
switch (rand.uintLessThan(u8, 8)) {
0 => continue,
1 => {
try out.appendSlice(gpa, alphabet[rand.uintLessThan(usize, alphabet.len)]);
try out.append(gpa, '\n');
},
else => {},
}
try out.appendSlice(gpa, line);
try out.append(gpa, '\n');
}
if (rand.boolean() and out.items.len > 0) _ = out.pop();
}
fn splitLines(gpa: std.mem.Allocator, bytes: []const u8) ![][]const u8 {
var lines: std.ArrayList([]const u8) = .empty;
var start: usize = 0;
while (std.mem.indexOfScalarPos(u8, bytes, start, '\n')) |nl| {
try lines.append(gpa, bytes[start .. nl + 1]);
start = nl + 1;
}
if (start < bytes.len) try lines.append(gpa, bytes[start..]);
return lines.toOwnedSlice(gpa);
}
fn check(gpa: std.mem.Allocator, from: []const u8, to: []const u8, opts: linediff.Options) !void {
const triples = try linediff.diff(gpa, from, to, opts);
defer gpa.free(triples);
const a = try splitLines(gpa, from);
defer gpa.free(a);
const b = try splitLines(gpa, to);
defer gpa.free(b);
const exact = opts.newline_significant and !opts.flags.strip_eol_cr and
!opts.flags.ignore_eol_ws and !opts.flags.ignore_all_ws;
var rebuilt: std.ArrayList(u8) = .empty;
defer rebuilt.deinit(gpa);
var i: usize = 0;
var j: usize = 0;
for (triples) |t| {
for (0..t.copy) |_| {
if (i >= a.len or j >= b.len) return error.TriplesOverrun;
// Exact comparison: a copy takes the first input's line, so a
// copy pairing unequal lines makes the replay differ.
try rebuilt.appendSlice(gpa, if (exact) a[i] else b[j]);
i += 1;
j += 1;
}
i += t.delete;
for (0..t.insert) |_| {
if (j >= b.len) return error.TriplesOverrun;
try rebuilt.appendSlice(gpa, b[j]);
j += 1;
}
}
if (i != a.len or j != b.len) return error.TriplesDoNotTile;
if (!std.mem.eql(u8, rebuilt.items, to)) return error.ReplayDiffers;
}
pub fn properties(gpa: std.mem.Allocator, seed: u64, rounds: usize) !void {
if (rounds == 0) return error.NoRounds;
var prng = std.Random.DefaultPrng.init(seed);
const rand = prng.random();
var from: std.ArrayList(u8) = .empty;
defer from.deinit(gpa);
var to: std.ArrayList(u8) = .empty;
defer to.deinit(gpa);
for (0..rounds) |_| {
try generate(rand, &from, gpa);
if (rand.boolean()) try mutate(rand, from.items, &to, gpa) else try generate(rand, &to, gpa);
const opts: linediff.Options = .{
.flags = .{
.strip_eol_cr = rand.boolean(),
.ignore_eol_ws = rand.boolean(),
.ignore_all_ws = rand.uintLessThan(u8, 4) == 0,
},
.optimize = rand.boolean(),
.newline_significant = rand.boolean(),
};
try check(gpa, from.items, to.items, opts);
try check(gpa, from.items, to.items, .{});
const same = try linediff.diff(gpa, from.items, from.items, .{});
defer gpa.free(same);
if (from.items.len == 0) {
if (same.len != 0) return error.SelfDiffNotCopy;
} else if (same.len != 1 or same[0].delete != 0 or same[0].insert != 0) {
return error.SelfDiffNotCopy;
}
}
}
test "linediff_properties: fixed seeds" {
for ([_]u64{ 1, 2, 3, 0xd1ff }) |seed| try properties(std.testing.allocator, seed, 400);
}