//! Pure per-line provenance engine behind `zit annotate` (contracts/annotate.md
//! B-annotate-1..8, ambiguities.md `annotate-attribution`). Deep module, no I/O:
//! the sole entry point takes the file's version chain — one `Node` per check-in
//! in the annotated file's full ancestry, reduced to PATH's content there plus
//! its §3.2 primary/merge parent indices — plus an injected allocator, and yields
//! each target line's origin check-in. It reads no repository state: the CLI
//! (main.zig) materializes the `Node`s from `Repository.fileAt` (the §8 effective
//! set) + `blob` and the repostate §3.3 parent query, orders them oldest-first via
//! the repostate topological linearization (`ancestryLinearized` — a parent always
//! precedes its child), and hands them here, so the engine is unit-testable on plain strings
//! (B-annotate-7). The adjacent-version line diff is `linediff`, zit's one
//! line-diff core (B-annotate-6), run as Fossil's annotate runs it: the
//! parent diffed into the child, CR before a newline ignored, a final
//! newline not a change, and no `diff_optimize`. Fossil diffs each ancestor
//! against the annotated version where this engine diffs adjacent versions,
//! so a block that moves can still be credited differently.
//!
//! Attribution rule, implemented VERBATIM from `annotate-attribution`: a line is
//! attributed to the OLDEST version in the chain that carries it, propagated
//! backward through adjacent-version line diffs. Across a merge check-in a line
//! present in ANY parent side's version is NOT charged to the merge — attribution
//! passes through the parent that carries it, preferring the PRIMARY parent when
//! both sides carry it; the merge check-in is charged only for lines in its
//! version and in NO parent version (true conflict-resolution edits).
const std = @import("std");
const linediff = @import("linediff.zig");
/// Fossil annotate's diff: DIFF_STRIP_EOLCR, and `diff_all` without
/// `diff_optimize`. A cache of this diff's output keys on it.
pub const annotate_diff: linediff.Options = .{
.flags = .{ .strip_eol_cr = true },
.optimize = false,
.newline_significant = false,
};
/// One check-in in the annotated file's ancestry, reduced to what the engine
/// needs. `content` is PATH's effective content there, or null when PATH is
/// absent (never added yet, or a delta delete). `primary` is the index of the
/// §3.2 primary parent within the `nodes` slice, or null for a root / a parent
/// this view never interned. `merges` are the merge-parent indices in P-card
/// order (the primary excluded). All indices reference the same `nodes` slice.
pub const Node = struct {
content: ?[]const u8,
primary: ?u32 = null,
merges: []const u32 = &.{},
};
/// Per-line provenance of `nodes[target]`: `result[i]` is the index into `nodes`
/// of the check-in that INTRODUCED line i of the target's content — the oldest
/// version in the chain that carries it. `nodes` MUST be in processing order — a
/// topological linearization of the ancestry DAG (repostate `ancestryLinearized`)
/// so every parent index is strictly less than its child's and is resolved first,
/// with topologically-incomparable versions in a deterministic tiebreak; the CLI
/// owns that ordering. Pure: allocation
/// via `gpa` only, no I/O; every loop is bounded by node count × line count
/// (B-annotate-7). Caller frees the returned slice.
pub fn attribute(
gpa: std.mem.Allocator,
nodes: []const Node,
target: u32,
) error{OutOfMemory}![]u32 {
std.debug.assert(target < nodes.len);
var walk = try Walk.init(gpa, nodes.len, false);
defer walk.deinit();
for (nodes, 0..) |node, ni| walk.add(@intCast(ni), node) catch |e| switch (e) {
error.OutOfMemory => return error.OutOfMemory,
error.Corrupt => unreachable, // only a kept edge is refused, and there are none
};
return gpa.dupe(u32, walk.origins(target) orelse &.{});
}
/// What a walk to `target` does with each node once some nodes' origins are
/// already known (`cached`): `seed` a cached node the walk reaches, `walk`
/// an uncached one it reaches, and `skip` the rest. A reached cached node
/// stands in for its ancestry, so the walk stops there; an uncached node
/// reaches all of its parents. Merges need nothing special: an uncached
/// side walks back to its own cached node or root.
pub const Role = enum(u8) { skip, walk, seed };
/// The `Role` of every node, by the rule above. Only the parent links of
/// `nodes` are read. Bounded by the node count: each node is decided once.
/// Caller frees the returned slice.
pub fn planCut(
gpa: std.mem.Allocator,
nodes: []const Node,
target: u32,
cached: []const bool,
) error{OutOfMemory}![]Role {
const roles = try gpa.alloc(Role, nodes.len);
errdefer gpa.free(roles);
@memset(roles, .skip);
var stack: std.ArrayList(u32) = .empty;
defer stack.deinit(gpa);
try stack.append(gpa, target);
while (stack.pop()) |ni| {
if (roles[ni] != .skip) continue;
if (cached[ni]) {
roles[ni] = .seed;
continue;
}
roles[ni] = .walk;
const node = nodes[ni];
if (node.primary) |p| try stack.append(gpa, p);
try stack.appendSlice(gpa, node.merges);
}
return roles;
}
/// `attribute` one node at a time, so a caller can drop each version once
/// no later node names it as a parent. Holding every version until the end
/// made memory the file's size times its history: a 33k-line file over a few
/// thousand check-ins went past 4 GB.
///
/// Nodes are added in processing order (as `attribute`'s `nodes`), each
/// parent added and not yet released. A node's content is either new bytes,
/// which the walk takes and, when `owns_content`, frees on release, or the
/// very slice `content(primary)` returned: the check-in did not change the
/// file, and the node shares its parent's version instead of diffing it.
pub const Walk = struct {
gpa: std.mem.Allocator,
owns_content: bool,
/// One per node: null when the node has no content or was released.
slots: []?*Version,
/// Where an edge's diff may already be kept, and where one diffed here
/// is handed. Null diffs every edge.
edges: ?Edges = null,
/// Edges diffed by this walk, rather than answered from `edges`.
diffed: usize = 0,
pub const Error = error{
OutOfMemory,
/// A kept edge disagrees with the line counts of the versions it
/// joins, or a node added unread has an edge that is not kept.
Corrupt,
};
/// One version of the file and the origin of each of its lines, shared
/// by a run of nodes that did not change it.
const Version = struct {
/// Null for a version added unread: every edge it is on is kept.
content: ?[]const u8,
/// `content` split for the line diff, made the first time an edge
/// diffs it and kept for its other edges, so a version is split once
/// though it is the newer side of one diff and the older of the
/// next. Fossil's annotate (`annotation_start` and
/// `annotation_step` in diff.c, D. Richard Hipp) keeps the annotated
/// version's lines across its steps in the same way.
lines: ?[]linediff.DLine = null,
origins: []u32,
refs: u32,
};
pub fn init(gpa: std.mem.Allocator, node_count: usize, owns_content: bool) error{OutOfMemory}!Walk {
const slots = try gpa.alloc(?*Version, node_count);
@memset(slots, null);
return .{ .gpa = gpa, .owns_content = owns_content, .slots = slots };
}
pub fn deinit(self: *Walk) void {
for (0..self.slots.len) |ni| self.release(@intCast(ni));
self.gpa.free(self.slots);
self.* = undefined;
}
/// Node `ni`'s content, or null when it has none, was released, or was
/// added unread.
pub fn content(self: *const Walk, ni: u32) ?[]const u8 {
return if (self.slots[ni]) |v| v.content else null;
}
/// The origin of each line of node `ni`'s content (indices of nodes), or
/// null when it has none or was released.
pub fn origins(self: *const Walk, ni: u32) ?[]const u32 {
return if (self.slots[ni]) |v| v.origins else null;
}
/// Attribute node `ni`'s lines against its parents. The content is the
/// walk's from here on, even when this fails.
pub fn add(self: *Walk, ni: u32, node: Node) Error!void {
std.debug.assert(self.slots[ni] == null);
const bytes = node.content orelse return;
// The CLI shares the pointer when the check-in did not change the
// file, and identical content resolves to exactly the parent's
// origins: the line diff matches every line, the primary pass adopts
// them wholesale and the merge passes find nothing left to claim.
// Skipping the diff is the difference between attributing ~200 real
// versions and 36,000 ancestors.
if (node.primary) |pi| if (self.slots[pi]) |pv| if (pv.content) |pc| {
if (pc.ptr == bytes.ptr and pc.len == bytes.len) {
pv.refs += 1;
self.slots[ni] = pv;
return;
}
};
errdefer if (self.owns_content) self.gpa.free(bytes);
try self.attributeNew(ni, bytes, linediff.lineCount(bytes), node.primary, node.merges);
}
/// `add` without node `ni`'s content: every edge into it from a parent
/// with a version is answered by `edges`, so the diffs need neither
/// side's bytes and the line count is the edges'. The caller reads the
/// content of every node an unkept edge joins, and of the target.
pub fn addUnread(self: *Walk, ni: u32, primary: ?u32, merges: []const u32) Error!void {
std.debug.assert(self.slots[ni] == null);
const kept = self.edges orelse return error.Corrupt;
var it: ParentIter = .{ .primary = primary, .merges = merges };
const line_count = while (it.next()) |p| {
if (self.slots[p] == null) continue;
const triples = kept.get(kept.ctx, p, ni) orelse return error.Corrupt;
break sideLines(triples).to;
} else return error.Corrupt;
try self.attributeNew(ni, null, line_count, primary, merges);
}
/// A new version for node `ni`, its lines attributed against its
/// parents. The walk takes neither `bytes` nor anything else on failure.
fn attributeNew(self: *Walk, ni: u32, bytes: ?[]const u8, line_count: usize, primary: ?u32, merges: []const u32) Error!void {
const v = try self.gpa.create(Version);
errdefer self.gpa.destroy(v);
const line_origins = try self.gpa.alloc(u32, line_count);
errdefer self.gpa.free(line_origins);
// Every line is provisionally introduced here; a parent that carries it
// overrides below. `origins[i] == ni` is the "still unclaimed" sentinel:
// a parent origin is always a strict ancestor index, never `ni` itself.
@memset(line_origins, ni);
v.* = .{ .content = bytes, .origins = line_origins, .refs = 1 };
errdefer if (v.lines) |l| self.gpa.free(l);
// Primary parent first (§3.2 preference), then each merge parent in
// P-card order. `inheritCarried` only overrides lines still charged to
// `ni`, so the primary wins whenever both sides carry a line and a merge
// is charged only for lines no parent carries (annotate-attribution).
try self.inheritCarried(v, primary, ni);
for (merges) |mp| try self.inheritCarried(v, mp, ni);
self.slots[ni] = v;
}
/// Stand node `ni` in for its whole ancestry: `line_origins` is the
/// origin of each line of `bytes`, as an earlier walk attributed them,
/// so no parent is read. Attribution is a pure function of a node's
/// parents' origins, which is what makes the answer `add` would give.
/// The caller guarantees one origin per line, each an index below `ni`
/// (a later node reading an origin equal to its own index would take
/// the line as unclaimed). The walk takes both slices, even when this
/// fails: the origins always, the content when it `owns_content`.
pub fn seed(self: *Walk, ni: u32, bytes: []const u8, line_origins: []u32) error{OutOfMemory}!void {
std.debug.assert(self.slots[ni] == null);
errdefer {
if (self.owns_content) self.gpa.free(bytes);
self.gpa.free(line_origins);
}
const v = try self.gpa.create(Version);
v.* = .{ .content = bytes, .origins = line_origins, .refs = 1 };
self.slots[ni] = v;
}
/// Drop node `ni`'s hold on its version; the last holder frees it. A
/// node with no content, or released already, is a no-op.
pub fn release(self: *Walk, ni: u32) void {
const v = self.slots[ni] orelse return;
self.slots[ni] = null;
v.refs -= 1;
if (v.refs > 0) return;
if (self.owns_content) if (v.content) |c| self.gpa.free(c);
if (v.lines) |l| self.gpa.free(l);
self.gpa.free(v.origins);
self.gpa.destroy(v);
}
/// `v`'s lines for the diff, split on first use.
fn linesOf(self: *Walk, v: *Version) Error![]linediff.DLine {
if (v.lines) |l| return l;
const bytes = v.content orelse return error.Corrupt;
const l = try linediff.breakLines(self.gpa, bytes, annotate_diff.flags);
v.lines = l;
return l;
}
/// Push origins backward across one adjacent-version edge: for each line of
/// `child` still charged to `self_idx` that the parent CARRIES (matched by
/// the house line diff), adopt the parent's already-resolved origin for the
/// matched line. A null parent index, or a parent with no PATH content,
/// carries nothing (the child keeps the line). The diff is the kept one
/// when `edges` has it; a diff made here is handed to `edges`. Bounded by
/// the two versions' line counts.
fn inheritCarried(
self: *Walk,
child: *Version,
parent_idx: ?u32,
self_idx: u32,
) Error!void {
const pidx = parent_idx orelse return;
std.debug.assert(pidx < self_idx); // parents are added first
const parent = self.slots[pidx] orelse return;
const line_origins = child.origins;
var made: ?[]linediff.Triple = null;
defer if (made) |t| self.gpa.free(t);
const kept: ?[]const linediff.Triple = if (self.edges) |e| e.get(e.ctx, pidx, self_idx) else null;
const triples = kept orelse blk: {
const t = try linediff.diffLines(self.gpa, try self.linesOf(parent), try self.linesOf(child), annotate_diff);
made = t;
self.diffed += 1;
if (self.edges) |e| try e.put(e.ctx, pidx, self_idx, t);
break :blk t;
};
// A diff made here sums to both counts; a kept one must, or it is
// not this edge's.
const sides = sideLines(triples);
if (sides.from != parent.origins.len or sides.to != line_origins.len) return error.Corrupt;
const match = try self.gpa.alloc(?usize, line_origins.len);
defer self.gpa.free(match);
linediff.matchTo(triples, match);
for (match, 0..) |m, i| {
if (line_origins[i] != self_idx) continue; // already claimed by a higher-priority parent
if (m) |older_line| {
std.debug.assert(older_line < parent.origins.len);
line_origins[i] = parent.origins[older_line];
}
}
}
};
/// Where a walk finds the diff of an edge an earlier walk made, by node
/// index, and hands the ones it makes. `get`'s triples are borrowed for the
/// walk's life.
pub const Edges = struct {
ctx: *anyopaque,
get: *const fn (ctx: *anyopaque, parent: u32, child: u32) ?[]const linediff.Triple,
put: *const fn (ctx: *anyopaque, parent: u32, child: u32, triples: []const linediff.Triple) error{OutOfMemory}!void,
};
/// A node's parents in the order the walk attributes against them: the
/// primary, then the merges in P-card order.
pub const ParentIter = struct {
primary: ?u32,
merges: []const u32,
at: usize = 0,
pub fn next(self: *ParentIter) ?u32 {
if (self.primary) |p| {
self.primary = null;
return p;
}
if (self.at == self.merges.len) return null;
self.at += 1;
return self.merges[self.at - 1];
}
};
/// The line counts of the two sides a list of triples joins.
pub fn sideLines(triples: []const linediff.Triple) struct { from: usize, to: usize } {
var from: usize = 0;
var to: usize = 0;
for (triples) |t| {
from += @as(usize, t.copy) + t.delete;
to += @as(usize, t.copy) + t.insert;
}
return .{ .from = from, .to = to };
}
// --- tests -----------------------------------------------------------------
const testing = std.testing;
/// Attribution over a slice of nodes, returning the origin index per target line.
fn attrib(nodes: []const Node, target: u32) ![]u32 {
return attribute(testing.allocator, nodes, target);
}
test "attribute linear add/modify chain: oldest-origin per line (B-annotate-1/-2)" {
// v0 adds A,B,C ; v1 edits B→B1 ; v2 appends D.
// A unchanged since v0 → origin v0
// B1 introduced at v1 → origin v1
// C unchanged since v0 → origin v0
// D introduced at v2 → origin v2
const nodes = [_]Node{
.{ .content = "A\nB\nC\n", .primary = null },
.{ .content = "A\nB1\nC\n", .primary = 0 },
.{ .content = "A\nB1\nC\nD\n", .primary = 1 },
};
const origins = try attrib(&nodes, 2);
defer testing.allocator.free(origins);
try testing.expectEqualSlices(u32, &.{ 0, 1, 0, 2 }, origins);
}
test "attribute merge pass-through: each side's lines keep their branch origin (B-annotate-3)" {
// v0 base A,B,C. Fork:
// v1 (other branch) edits A→A1 → A1 origin v1
// v2 (current branch) edits C→C1 → C1 origin v2
// v3 merge: A1,B,C1 — primary=v2, merge=v1.
// A1 carried by v1 (not v2), B carried by both (oldest v0), C1 carried by v2.
// Nothing is charged to the merge (no resolution line).
const nodes = [_]Node{
.{ .content = "A\nB\nC\n", .primary = null }, // 0 base
.{ .content = "A1\nB\nC\n", .primary = 0 }, // 1 other
.{ .content = "A\nB\nC1\n", .primary = 0 }, // 2 current
.{ .content = "A1\nB\nC1\n", .primary = 2, .merges = &.{1} }, // 3 merge
};
const origins = try attrib(&nodes, 3);
defer testing.allocator.free(origins);
// A1 → v1 (other), B → v0 (base), C1 → v2 (current)
try testing.expectEqualSlices(u32, &.{ 1, 0, 2 }, origins);
}
test "attribute merge primary-parent preference when both sides carry a line (B-annotate-3)" {
// Both parents independently introduce the identical line X (not in base).
// The merge keeps X; primary parent must win.
const nodes = [_]Node{
.{ .content = "A\n", .primary = null }, // 0 base
.{ .content = "A\nX\n", .primary = 0 }, // 1 merge parent adds X
.{ .content = "A\nX\n", .primary = 0 }, // 2 primary parent adds X
.{ .content = "A\nX\n", .primary = 2, .merges = &.{1} }, // 3 merge
};
const origins = try attrib(&nodes, 3);
defer testing.allocator.free(origins);
// A → base v0 ; X → primary parent v2 (preferred over v1)
try testing.expectEqualSlices(u32, &.{ 0, 2 }, origins);
}
test "attribute merge charged only for a true resolution edit (B-annotate-4)" {
// v3 merge introduces R, present in NEITHER parent → charged to the merge.
const nodes = [_]Node{
.{ .content = "A\nB\n", .primary = null }, // 0 base
.{ .content = "A1\nB\n", .primary = 0 }, // 1 other (A→A1)
.{ .content = "A\nB1\n", .primary = 0 }, // 2 current (B→B1)
.{ .content = "A1\nR\nB1\n", .primary = 2, .merges = &.{1} }, // 3 merge adds R
};
const origins = try attrib(&nodes, 3);
defer testing.allocator.free(origins);
// A1 → v1 (other), R → v3 (merge resolution), B1 → v2 (current)
try testing.expectEqualSlices(u32, &.{ 1, 3, 2 }, origins);
}
test "attribute is deterministic across repeated runs (B-annotate-5)" {
const nodes = [_]Node{
.{ .content = "A\nB\nC\n", .primary = null },
.{ .content = "A1\nB\nC\n", .primary = 0 },
.{ .content = "A\nB\nC1\n", .primary = 0 },
.{ .content = "A1\nB\nC1\n", .primary = 2, .merges = &.{1} },
};
const a = try attrib(&nodes, 3);
defer testing.allocator.free(a);
const b = try attrib(&nodes, 3);
defer testing.allocator.free(b);
try testing.expectEqualSlices(u32, a, b);
}
test "attribute over an add whose primary parent lacks the file: origin is the adder" {
// v0 has no PATH (null content); v1 adds A,B. Both attributed to v1.
const nodes = [_]Node{
.{ .content = null, .primary = null }, // 0 PATH absent
.{ .content = "A\nB\n", .primary = 0 }, // 1 add
};
const origins = try attrib(&nodes, 1);
defer testing.allocator.free(origins);
try testing.expectEqualSlices(u32, &.{ 1, 1 }, origins);
}
test "attribute over a single-line file with no trailing newline" {
const nodes = [_]Node{
.{ .content = "only", .primary = null },
};
const origins = try attrib(&nodes, 0);
defer testing.allocator.free(origins);
try testing.expectEqualSlices(u32, &.{0}, origins);
}
test "attribute empty target content yields no origins" {
const nodes = [_]Node{
.{ .content = "", .primary = null },
};
const origins = try attrib(&nodes, 0);
defer testing.allocator.free(origins);
try testing.expectEqual(@as(usize, 0), origins.len);
}
/// One deterministic fuzz pass: build a random linear-plus-merge chain of string
/// versions and fold the attribution output into a running hash. Same seed ⇒ same
/// hash, and every chain yields a valid attribution (never a crash) — the
/// B-annotate-8 obligation over the engine.
fn fuzzPass(seed: u64) u64 {
const a = testing.allocator;
var prng = std.Random.DefaultPrng.init(seed);
const rand = prng.random();
var h = std.hash.Wyhash.init(0);
var round: usize = 0;
while (round < 200) : (round += 1) {
const n = 1 + rand.uintLessThan(usize, 6);
const nodes = a.alloc(Node, n) catch return h.final();
defer {
for (nodes) |node| {
if (node.content) |c| a.free(c);
if (node.merges.len != 0) a.free(node.merges);
}
a.free(nodes);
}
for (nodes, 0..) |*node, i| {
// Adversarial content: empty versions, no trailing LF, repeats, long.
var buf: [48]u8 = undefined;
const len = rand.uintLessThan(usize, buf.len + 1);
for (buf[0..len]) |*b| {
b.* = switch (rand.uintLessThan(u8, 8)) {
0, 1 => '\n',
else => 'A' + rand.uintLessThan(u8, 4), // small alphabet → line reuse
};
}
const content: ?[]const u8 = if (rand.boolean() and i == 0)
null
else
(a.dupe(u8, buf[0..len]) catch return h.final());
var merges: []const u32 = &.{};
var primary: ?u32 = null;
if (i > 0) {
primary = rand.uintLessThan(u32, @intCast(i));
// Occasionally a merge parent (a different earlier node).
if (i > 1 and rand.boolean()) {
const m = a.alloc(u32, 1) catch return h.final();
m[0] = rand.uintLessThan(u32, @intCast(i));
merges = m;
}
}
node.* = .{ .content = content, .primary = primary, .merges = merges };
}
const target: u32 = @intCast(n - 1);
if (attribute(a, nodes, target)) |origins| {
for (origins) |o| h.update(std.mem.asBytes(&o));
h.update("|");
a.free(origins);
} else |_| h.update("E");
}
return h.final();
}
test "attribute seeded deterministic fuzz never crashes (B-annotate-8)" {
const first = fuzzPass(0xA55E_7710_0001_0001);
const second = fuzzPass(0xA55E_7710_0001_0001);
try testing.expectEqual(first, second);
const other = fuzzPass(0x0BAD_0DE0_0002_0002);
try testing.expect(first != other);
}
fn attribNoLeak(a: std.mem.Allocator) error{OutOfMemory}!void {
const nodes = [_]Node{
.{ .content = "A\nB\nC\n", .primary = null },
.{ .content = "A1\nB\nC\n", .primary = 0 },
.{ .content = "A1\nB\nC1\n", .primary = 1, .merges = &.{0} },
};
const origins = try attribute(a, &nodes, 2);
a.free(origins);
}
test "attribute leak-free under checkAllAllocationFailures" {
try testing.checkAllAllocationFailures(testing.allocator, attribNoLeak, .{});
}
test "walk: a released version stays readable while a node sharing it holds it" {
var walk = try Walk.init(testing.allocator, 3, false);
defer walk.deinit();
try walk.add(0, .{ .content = "A\nB\n" });
// Unchanged: the same slice as the primary's, so the version is shared.
try walk.add(1, .{ .content = walk.content(0).?, .primary = 0 });
walk.release(0);
try testing.expect(walk.content(0) == null);
try testing.expectEqualSlices(u32, &.{ 0, 0 }, walk.origins(1).?);
try walk.add(2, .{ .content = "A\nC\nB\n", .primary = 1 });
walk.release(1);
try testing.expectEqualSlices(u32, &.{ 0, 2, 0 }, walk.origins(2).?);
}
fn walkOwnedNoLeak(a: std.mem.Allocator) Walk.Error!void {
var walk = try Walk.init(a, 3, true);
defer walk.deinit();
try walk.add(0, .{ .content = try a.dupe(u8, "A\nB\nC\n") });
try walk.add(1, .{ .content = walk.content(0).?, .primary = 0 });
try walk.add(2, .{ .content = try a.dupe(u8, "A1\nB\nC1\n"), .primary = 1, .merges = &.{0} });
walk.release(0);
walk.release(1);
}
test "walk owning its content is leak-free under checkAllAllocationFailures" {
try testing.checkAllAllocationFailures(testing.allocator, walkOwnedNoLeak, .{});
}
/// The cut's differential: over random DAGs (merges, identical content,
/// empty versions, no trailing newline), seeding any subset of nodes with
/// the full walk's own origins and walking only what `planCut` reaches
/// gives the full walk's answer for the target, exactly.
fn cutPass(a: std.mem.Allocator, seed_value: u64) !void {
var prng = std.Random.DefaultPrng.init(seed_value);
const rand = prng.random();
// Vacuity: the rounds must seed nodes and skip the ancestry behind them.
var seeded: usize = 0;
var skipped: usize = 0;
var round: usize = 0;
while (round < 300) : (round += 1) {
const n = 1 + rand.uintLessThan(usize, 14);
const nodes = try a.alloc(Node, n);
defer a.free(nodes);
var contents: std.ArrayList([]u8) = .empty;
defer {
for (contents.items) |c| a.free(c);
contents.deinit(a);
}
var merge_lists: std.ArrayList([]u32) = .empty;
defer {
for (merge_lists.items) |m| a.free(m);
merge_lists.deinit(a);
}
for (nodes, 0..) |*node, i| {
var primary: ?u32 = null;
var merges: []const u32 = &.{};
if (i > 0 and rand.uintLessThan(u8, 8) != 0) {
primary = rand.uintLessThan(u32, @intCast(i));
if (i > 1 and rand.uintLessThan(u8, 3) == 0) {
const m = try a.alloc(u32, 1 + rand.uintLessThan(usize, 2));
try merge_lists.append(a, m);
for (m) |*x| x.* = rand.uintLessThan(u32, @intCast(i));
merges = m;
}
}
const content: ?[]const u8 = switch (rand.uintLessThan(u8, 10)) {
0 => null,
// Identical content to the primary, as an unchanged check-in.
1, 2 => if (primary) |p| nodes[p].content else null,
else => blk: {
var buf: [40]u8 = undefined;
const len = rand.uintLessThan(usize, buf.len + 1);
for (buf[0..len]) |*b| b.* = switch (rand.uintLessThan(u8, 6)) {
0, 1 => '\n',
else => 'A' + rand.uintLessThan(u8, 3),
};
const c = try a.dupe(u8, buf[0..len]);
try contents.append(a, c);
break :blk c;
},
};
node.* = .{ .content = content, .primary = primary, .merges = merges };
}
const target: u32 = @intCast(n - 1);
// The full walk, every node's origins kept.
var full = try Walk.init(a, n, false);
defer full.deinit();
for (nodes, 0..) |node, ni| try full.add(@intCast(ni), node);
const cached = try a.alloc(bool, n);
defer a.free(cached);
for (0..4) |_| {
for (cached, 0..) |*c, i| c.* = full.origins(@intCast(i)) != null and rand.uintLessThan(u8, 3) == 0;
const roles = try planCut(a, nodes, target, cached);
defer a.free(roles);
var cut = try Walk.init(a, n, false);
defer cut.deinit();
for (nodes, roles, 0..) |node, role, i| {
const ni: u32 = @intCast(i);
switch (role) {
.skip => skipped += 1,
.walk => try cut.add(ni, node),
.seed => {
seeded += 1;
try cut.seed(ni, node.content.?, try a.dupe(u32, full.origins(ni).?));
},
}
}
if (full.origins(target)) |want| {
try testing.expectEqualSlices(u32, want, cut.origins(target).?);
} else try testing.expect(cut.origins(target) == null);
}
}
try testing.expect(seeded > 100 and skipped > 100);
}
test "cut: seeding any subset with its own origins gives the full walk's attribution" {
try cutPass(testing.allocator, 0xC0_7C07_0001);
try cutPass(testing.allocator, 0xC0_7C07_0002);
try cutPass(testing.allocator, 0xC0_7C07_0003);
}
test "cut: a seeded node stops the walk, and an uncached merge side walks to its own root" {
// 0 base; 1 and 2 fork from it; 3 merges 2 (primary) and 1.
const nodes = [_]Node{
.{ .content = "A\n" },
.{ .content = "A\nB\n", .primary = 0 },
.{ .content = "A\nC\n", .primary = 0 },
.{ .content = "A\nC\nB\n", .primary = 2, .merges = &.{1} },
};
const roles = try planCut(testing.allocator, &nodes, 3, &.{ false, false, true, false });
defer testing.allocator.free(roles);
try testing.expectEqualSlices(Role, &.{ .walk, .walk, .seed, .walk }, roles);
const none = try planCut(testing.allocator, &nodes, 3, &.{ false, false, false, true });
defer testing.allocator.free(none);
try testing.expectEqualSlices(Role, &.{ .skip, .skip, .skip, .seed }, none);
}
fn seededWalkNoLeak(a: std.mem.Allocator) Walk.Error!void {
var walk = try Walk.init(a, 3, true);
defer walk.deinit();
const bytes = try a.dupe(u8, "A\nB\n");
const origins = a.alloc(u32, 2) catch |e| {
a.free(bytes);
return e;
};
origins[0] = 0;
origins[1] = 1;
try walk.seed(1, bytes, origins);
try walk.add(2, .{ .content = walk.content(1).?, .primary = 1 });
try walk.add(0, .{ .content = try a.dupe(u8, "A\nC\nB\n"), .merges = &.{} });
walk.release(1);
}
test "walk seeded from a cache is leak-free under checkAllAllocationFailures" {
try testing.checkAllAllocationFailures(testing.allocator, seededWalkNoLeak, .{});
}
/// Edges kept by node pair, as a caller's diff cache keeps them by blob pair.
const TestEdges = struct {
gpa: std.mem.Allocator,
map: std.AutoHashMapUnmanaged(u64, []linediff.Triple) = .empty,
fn deinit(self: *TestEdges) void {
var it = self.map.valueIterator();
while (it.next()) |t| self.gpa.free(t.*);
self.map.deinit(self.gpa);
}
fn key(parent: u32, child: u32) u64 {
return @as(u64, parent) << 32 | child;
}
fn get(ctx: *anyopaque, parent: u32, child: u32) ?[]const linediff.Triple {
const self: *TestEdges = @ptrCast(@alignCast(ctx));
return self.map.get(key(parent, child));
}
fn put(ctx: *anyopaque, parent: u32, child: u32, triples: []const linediff.Triple) error{OutOfMemory}!void {
const self: *TestEdges = @ptrCast(@alignCast(ctx));
const owned = try self.gpa.dupe(linediff.Triple, triples);
errdefer self.gpa.free(owned);
const gop = try self.map.getOrPut(self.gpa, key(parent, child));
if (gop.found_existing) self.gpa.free(gop.value_ptr.*);
gop.value_ptr.* = owned;
}
fn edges(self: *TestEdges) Edges {
return .{ .ctx = self, .get = get, .put = put };
}
};
/// The diff cache's differential: over random DAGs, a walk that replays the
/// edges an earlier walk diffed, reading content only where `need` says,
/// gives every node the origins of the walk that diffed them all, and diffs
/// nothing.
fn edgePass(a: std.mem.Allocator, seed_value: u64) !void {
var prng = std.Random.DefaultPrng.init(seed_value);
const rand = prng.random();
var unread: usize = 0;
var round: usize = 0;
while (round < 300) : (round += 1) {
const n = 1 + rand.uintLessThan(usize, 12);
const nodes = try a.alloc(Node, n);
defer a.free(nodes);
var contents: std.ArrayList([]u8) = .empty;
defer {
for (contents.items) |c| a.free(c);
contents.deinit(a);
}
var merge_lists: std.ArrayList([]u32) = .empty;
defer {
for (merge_lists.items) |m| a.free(m);
merge_lists.deinit(a);
}
for (nodes, 0..) |*node, i| {
var primary: ?u32 = null;
var merges: []const u32 = &.{};
if (i > 0 and rand.uintLessThan(u8, 8) != 0) {
primary = rand.uintLessThan(u32, @intCast(i));
if (i > 1 and rand.uintLessThan(u8, 3) == 0) {
const m = try a.alloc(u32, 1 + rand.uintLessThan(usize, 2));
try merge_lists.append(a, m);
for (m) |*x| x.* = rand.uintLessThan(u32, @intCast(i));
merges = m;
}
}
const content: ?[]const u8 = if (rand.uintLessThan(u8, 10) == 0) null else blk: {
var buf: [40]u8 = undefined;
const len = rand.uintLessThan(usize, buf.len + 1);
for (buf[0..len]) |*b| b.* = switch (rand.uintLessThan(u8, 6)) {
0, 1 => '\n',
else => 'A' + rand.uintLessThan(u8, 3),
};
const c = try a.dupe(u8, buf[0..len]);
try contents.append(a, c);
break :blk c;
};
node.* = .{ .content = content, .primary = primary, .merges = merges };
}
var kept: TestEdges = .{ .gpa = a };
defer kept.deinit();
var full = try Walk.init(a, n, false);
defer full.deinit();
full.edges = kept.edges();
for (nodes, 0..) |node, ni| try full.add(@intCast(ni), node);
// A node needs its content when it has no edge to stand on: no
// parent with content. Otherwise every edge into it is kept.
var replay = try Walk.init(a, n, false);
defer replay.deinit();
replay.edges = kept.edges();
for (nodes, 0..) |node, i| {
const ni: u32 = @intCast(i);
var has_edge = false;
if (node.primary) |p| has_edge = has_edge or nodes[p].content != null;
for (node.merges) |p| has_edge = has_edge or nodes[p].content != null;
if (node.content != null and has_edge and rand.boolean()) {
unread += 1;
try replay.addUnread(ni, node.primary, node.merges);
try testing.expect(replay.content(ni) == null);
} else try replay.add(ni, node);
}
try testing.expectEqual(@as(usize, 0), replay.diffed);
for (0..n) |i| {
const ni: u32 = @intCast(i);
if (full.origins(ni)) |want| {
try testing.expectEqualSlices(u32, want, replay.origins(ni).?);
} else try testing.expect(replay.origins(ni) == null);
}
}
try testing.expect(unread > 300);
}
test "walk: replaying kept edges gives every node the diffing walk's origins, and diffs nothing" {
try edgePass(testing.allocator, 0xED6E_0001);
try edgePass(testing.allocator, 0xED6E_0002);
}
test "walk: a kept edge whose line counts disagree with the versions is refused" {
var kept: TestEdges = .{ .gpa = testing.allocator };
defer kept.deinit();
try TestEdges.put(&kept, 0, 1, &.{.{ .copy = 1, .delete = 0, .insert = 0 }});
var walk = try Walk.init(testing.allocator, 2, false);
defer walk.deinit();
walk.edges = kept.edges();
try walk.add(0, .{ .content = "A\nB\n" });
try testing.expectError(error.Corrupt, walk.add(1, .{ .content = "A\nB\nC\n", .primary = 0 }));
}
fn edgeWalkNoLeak(a: std.mem.Allocator) !void {
var kept: TestEdges = .{ .gpa = a };
defer kept.deinit();
{
var walk = try Walk.init(a, 3, true);
defer walk.deinit();
walk.edges = kept.edges();
try walk.add(0, .{ .content = try a.dupe(u8, "A\nB\nC\n") });
try walk.add(1, .{ .content = try a.dupe(u8, "A\nX\nC\n"), .primary = 0 });
try walk.add(2, .{ .content = try a.dupe(u8, "A\nX\nC\nD\n"), .primary = 1, .merges = &.{0} });
}
var walk = try Walk.init(a, 3, true);
defer walk.deinit();
walk.edges = kept.edges();
try walk.add(0, .{ .content = try a.dupe(u8, "A\nB\nC\n") });
try walk.addUnread(1, 0, &.{});
try walk.add(2, .{ .content = try a.dupe(u8, "A\nX\nC\nD\n"), .primary = 1, .merges = &.{0} });
try testing.expectEqualSlices(u32, &.{ 0, 1, 0, 2 }, walk.origins(2).?);
}
test "walk with kept edges is leak-free under checkAllAllocationFailures" {
try testing.checkAllAllocationFailures(testing.allocator, edgeWalkNoLeak, .{});
}