//! 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 `merge3.matchLines` — the
//! one house line-diff core, never a second diff (B-annotate-6).
//!
//! 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 merge3 = @import("merge3.zig");
/// 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| try walk.add(@intCast(ni), node);
return gpa.dupe(u32, walk.origins(target) orelse &.{});
}
/// `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,
/// 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 {
content: []const u8,
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 or was released.
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{OutOfMemory}!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.ptr == bytes.ptr and pv.content.len == bytes.len) {
pv.refs += 1;
self.slots[ni] = pv;
return;
}
};
errdefer if (self.owns_content) self.gpa.free(bytes);
const line_count = blk: {
const lines = try merge3.splitLines(self.gpa, bytes);
defer self.gpa.free(lines);
break :blk lines.len;
};
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);
// 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(bytes, node.primary, ni, line_origins);
for (node.merges) |mp| try self.inheritCarried(bytes, mp, ni, 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) self.gpa.free(v.content);
self.gpa.free(v.origins);
self.gpa.destroy(v);
}
/// Push origins backward across one adjacent-version edge: for each line of
/// `child_content` 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). Bounded by the child's line
/// count.
fn inheritCarried(
self: *const Walk,
child_content: []const u8,
parent_idx: ?u32,
self_idx: u32,
line_origins: []u32,
) error{OutOfMemory}!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 match = try merge3.matchLines(self.gpa, child_content, parent.content);
defer self.gpa.free(match);
std.debug.assert(match.len == line_origins.len);
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];
}
}
}
};
// --- 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) error{OutOfMemory}!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, .{});
}