Skip to content
zit Artifact [d44a9d7e4d]
Login

Artifact [d44a9d7e4d]

Check-ins Using Download Hex

Artifact d44a9d7e4d3c4710bd226fedc3593903438008692d3e3b52d76e8e78db98fd67:

//! 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.
    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 — 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, .{});
}