Artifact c125f32fa24794a47c85c7aa8077e7977a38d9d5dc747ef19354d26425d2436c:
- File
src/annotate.zig
— part of check-in
[22bdf84fd3]
at
2026-09-02 01:32:46
on branch trunk
— annotate walks the file's versions, not the whole ancestry
Every ancestor cost a manifest read and a full-file line diff — ~36k of each on SQLite where ~400 touched the file. The cache records already say who changed PATH (their diff is against the primary parent, so unlisted means byte-equal there): untouched ancestors inherit the parent's content pointer, the engine copies the parent's origins on pointer-identity, and the LCS trims the common prefix/suffix before its O(n*m) table.
Unfinishable on SQLite before; 0.5-1.2s typical, 57s for a 15k-line heavily-edited file (the multi-hunk quadratic middle remains — a real diff core is the named follow-up). Attribution of a repeated line between equally-valid origins can shift, as any LCS tiebreak may.
zit#172 (user: dmestas, size: 15907) [annotate] [blame] [check-ins using]
//! 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); // `per_node[n]`: for node n (when it carries content), the resolved origin of // each of its lines. Built oldest-first so a child inherits its parent's // already-computed origins. A node with no content stays null. // `per_node` BORROWS its arrays; `owned` frees them. Separated so a node // whose origins are exactly its primary parent's — identical content — // can SHARE the parent's array instead of duplicating it: for a 15k-line // file over 36k mostly-untouched ancestors the dupes alone were two // gigabytes of memcpy (zit#172). var owned: std.ArrayList([]u32) = .empty; defer { for (owned.items) |a| gpa.free(a); owned.deinit(gpa); } const per_node = try gpa.alloc(?[]const u32, nodes.len); defer gpa.free(per_node); for (per_node) |*p| p.* = null; for (nodes, 0..) |node, ni_usize| { const ni: u32 = @intCast(ni_usize); const content = node.content orelse continue; // A node whose content is the SAME SLICE as its primary parent's — // the CLI shares the pointer when the check-in did not change the // file (zit#172) — resolves to exactly the parent's origins: the // line diff of identical content matches every line, so the primary // pass adopts the parent's origins 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 (nodes[pi].content) |pc| { if (pc.ptr == content.ptr and pc.len == content.len) { if (per_node[pi]) |po| { per_node[ni] = po; // shared: read-only from here on continue; } } } } const lines = try merge3.splitLines(gpa, content); defer gpa.free(lines); const origins = try gpa.alloc(u32, lines.len); { errdefer gpa.free(origins); try owned.append(gpa, 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. for (origins) |*o| o.* = 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 inheritCarried(gpa, nodes, per_node, content, node.primary, ni, origins); for (node.merges) |mp| { try inheritCarried(gpa, nodes, per_node, content, mp, ni, origins); } per_node[ni] = origins; } const t = per_node[target] orelse return gpa.alloc(u32, 0); return gpa.dupe(u32, t); } /// 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, a parent that never interned, or a parent /// with no PATH content carries nothing (the child keeps the line). Bounded by /// the child's line count. fn inheritCarried( gpa: std.mem.Allocator, nodes: []const Node, per_node: []const ?[]const u32, child_content: []const u8, parent_idx: ?u32, self_idx: u32, origins: []u32, ) error{OutOfMemory}!void { const pidx = parent_idx orelse return; const parent = nodes[pidx]; const parent_content = parent.content orelse return; // Topological processing order guarantees the parent (a strict ancestor) was // resolved first, so a resolved parent always has origins; a null here means // the parent interned none (no PATH content) — treat as no-carry so the engine // degrades deterministically instead of crashing. const parent_origins = per_node[pidx] orelse return; const match = try merge3.matchLines(gpa, child_content, parent_content); defer gpa.free(match); std.debug.assert(match.len == origins.len); for (match, 0..) |m, i| { if (origins[i] != self_idx) continue; // already claimed by a higher-priority parent if (m) |older_line| { std.debug.assert(older_line < parent_origins.len); 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, .{}); }