tiny.smg.diff

1const std = @import("std");2const pretty = @import("pretty");3const sys = @import("sys");4const smg = @import("root.zig");5const git = @import("git.zig");6const graph_mod = @import("graph.zig");7const scan = @import("scan/root.zig");8const view = @import("view.zig");9const model = @import("model.zig");10const text = @import("text/root.zig");11const pretty_json = pretty.json;1213pub const NodeChange = struct {14    name: []const u8,15    field: []const u8,16    old: ?[]const u8,17    new: ?[]const u8,18};1920pub const ChangedNode = struct {21    node: model.Node,22    changes: []const NodeChange,23};2425pub const RenamedNode = struct {26    old_name: []const u8,27    new_name: []const u8,28    old_node: model.Node,29    new_node: model.Node,30    match_type: []const u8,31};3233pub const Result = struct {34    added_nodes: []const model.Node = &.{},35    removed_nodes: []const model.Node = &.{},36    changed_nodes: []const ChangedNode = &.{},37    renamed_nodes: []const RenamedNode = &.{},38    added_edges: []const model.Edge = &.{},39    removed_edges: []const model.Edge = &.{},4041    pub fn empty(self: Result) bool {42        return self.added_nodes.len == 0 and self.removed_nodes.len == 0 and self.changed_nodes.len == 0 and self.renamed_nodes.len == 0 and self.added_edges.len == 0 and self.removed_edges.len == 0;43    }44};4546pub fn graphs(allocator: std.mem.Allocator, old: graph_mod.Graph, new: graph_mod.Graph, detect_renames: bool) !Result {47    var result = Result{};48    var added_nodes: std.ArrayList(model.Node) = .empty;49    var removed_nodes: std.ArrayList(model.Node) = .empty;50    var changed_nodes: std.ArrayList(ChangedNode) = .empty;51    var added_edges: std.ArrayList(model.Edge) = .empty;52    var removed_edges: std.ArrayList(model.Edge) = .empty;53    for (new.nodes.items) |node| {54        if (graph_mod.getNode(&old, node.name) == null) try added_nodes.append(allocator, node);55    }56    for (old.nodes.items) |node| {57        if (graph_mod.getNode(&new, node.name) == null) try removed_nodes.append(allocator, node);58    }59    for (new.nodes.items) |node| {60        const old_node = graph_mod.getNode(&old, node.name) orelse continue;61        const changes = try nodeChanges(allocator, old_node, node);62        if (changes.len != 0) try changed_nodes.append(allocator, .{ .node = node, .changes = changes });63    }64    var new_edge_iterator = new.edge_index.iterator();65    while (new_edge_iterator.next()) |entry| {66        const edge = new.edges.items[entry.value_ptr.*];67        if (!hasIndexedEdge(old, entry.key_ptr.*, edge)) try added_edges.append(allocator, edge);68    }69    var old_edge_iterator = old.edge_index.iterator();70    while (old_edge_iterator.next()) |entry| {71        const edge = old.edges.items[entry.value_ptr.*];72        if (!hasIndexedEdge(new, entry.key_ptr.*, edge)) try removed_edges.append(allocator, edge);73    }74    view.sortNodes(added_nodes.items);75    view.sortNodes(removed_nodes.items);76    sortChangedNodes(changed_nodes.items);77    view.sortEdges(added_edges.items);78    view.sortEdges(removed_edges.items);79    result.added_nodes = try added_nodes.toOwnedSlice(allocator);80    result.removed_nodes = try removed_nodes.toOwnedSlice(allocator);81    result.changed_nodes = try changed_nodes.toOwnedSlice(allocator);82    result.added_edges = try added_edges.toOwnedSlice(allocator);83    result.removed_edges = try removed_edges.toOwnedSlice(allocator);84    result.renamed_nodes = &.{};85    if (detect_renames and result.added_nodes.len != 0 and result.removed_nodes.len != 0) result = try detectRenames(allocator, result);86    return result;87}8889fn sortChangedNodes(nodes: []ChangedNode) void {90    std.mem.sort(ChangedNode, nodes, {}, changedNodeLessThan);91}9293fn changedNodeLessThan(_: void, left: ChangedNode, right: ChangedNode) bool {94    return std.mem.lessThan(u8, left.node.name, right.node.name);95}9697fn hasIndexedEdge(graph: graph_mod.Graph, key: []const u8, edge: model.Edge) bool {98    const index = graph.edge_index.get(key) orelse return false;99    const candidate = graph.edges.items[index];100    return std.mem.eql(u8, candidate.source, edge.source) and101        std.mem.eql(u8, candidate.rel, edge.rel) and102        std.mem.eql(u8, candidate.target, edge.target);103}104105fn nodeChanges(allocator: std.mem.Allocator, old: model.Node, new: model.Node) ![]const NodeChange {106    var changes: std.ArrayList(NodeChange) = .empty;107    if (!std.mem.eql(u8, old.type, new.type)) try changes.append(allocator, .{ .name = new.name, .field = "type", .old = old.type, .new = new.type });108    if (!optionalEqual(old.file, new.file)) try changes.append(allocator, .{ .name = new.name, .field = "file", .old = old.file, .new = new.file });109    if (old.line != new.line) try changes.append(allocator, .{ .name = new.name, .field = "line", .old = try lineText(allocator, old.line), .new = try lineText(allocator, new.line) });110    if (!optionalEqual(old.docstring, new.docstring)) try changes.append(allocator, .{ .name = new.name, .field = "docstring", .old = old.docstring, .new = new.docstring });111    const old_content = model.pairValue(old.metadata, "content_hash");112    const new_content = model.pairValue(new.metadata, "content_hash");113    if (!optionalEqual(old_content, new_content)) try changes.append(allocator, .{ .name = new.name, .field = "content_hash", .old = old_content, .new = new_content });114    const old_structure = model.pairValue(old.metadata, "structure_hash");115    const new_structure = model.pairValue(new.metadata, "structure_hash");116    if (!optionalEqual(old_structure, new_structure)) try changes.append(allocator, .{ .name = new.name, .field = "structure_hash", .old = old_structure, .new = new_structure });117    return try changes.toOwnedSlice(allocator);118}119120fn optionalEqual(a: ?[]const u8, b: ?[]const u8) bool {121    if (a == null and b == null) return true;122    if (a == null or b == null) return false;123    return std.mem.eql(u8, a.?, b.?);124}125126fn lineText(allocator: std.mem.Allocator, value: ?i64) ![]const u8 {127    if (value) |line| return try std.fmt.allocPrint(allocator, "{d}", .{line});128    return "None";129}130131fn detectRenames(allocator: std.mem.Allocator, result: Result) !Result {132    var matched_added: std.ArrayList([]const u8) = .empty;133    var matched_removed: std.ArrayList([]const u8) = .empty;134    var renamed: std.ArrayList(RenamedNode) = .empty;135    for (result.added_nodes) |added| {136        const structure_hash = model.pairValue(added.metadata, "structure_hash") orelse continue;137        var candidates: std.ArrayList(model.Node) = .empty;138        for (result.removed_nodes) |removed| {139            if (containsString(matched_removed.items, removed.name)) continue;140            const removed_structure = model.pairValue(removed.metadata, "structure_hash") orelse continue;141            if (std.mem.eql(u8, removed_structure, structure_hash)) try candidates.append(allocator, removed);142        }143        if (candidates.items.len == 0) continue;144        const content_hash = model.pairValue(added.metadata, "content_hash");145        var exact: std.ArrayList(model.Node) = .empty;146        if (content_hash) |hash| {147            for (candidates.items) |candidate| {148                const candidate_hash = model.pairValue(candidate.metadata, "content_hash") orelse continue;149                if (std.mem.eql(u8, candidate_hash, hash)) try exact.append(allocator, candidate);150            }151        }152        var match: ?model.Node = null;153        var match_type: []const u8 = "structure";154        if (exact.items.len == 1) {155            match = exact.items[0];156            match_type = "content";157        } else if (candidates.items.len == 1) {158            match = candidates.items[0];159        }160        if (match) |node| {161            try renamed.append(allocator, .{ .old_name = node.name, .new_name = added.name, .old_node = node, .new_node = added, .match_type = match_type });162            try matched_added.append(allocator, added.name);163            try matched_removed.append(allocator, node.name);164        }165    }166    try fuzzyMatch(allocator, result.added_nodes, result.removed_nodes, &renamed, &matched_added, &matched_removed);167    var added_nodes: std.ArrayList(model.Node) = .empty;168    var removed_nodes: std.ArrayList(model.Node) = .empty;169    for (result.added_nodes) |node| {170        if (!containsString(matched_added.items, node.name)) try added_nodes.append(allocator, node);171    }172    for (result.removed_nodes) |node| {173        if (!containsString(matched_removed.items, node.name)) try removed_nodes.append(allocator, node);174    }175    return .{176        .added_nodes = try added_nodes.toOwnedSlice(allocator),177        .removed_nodes = try removed_nodes.toOwnedSlice(allocator),178        .changed_nodes = result.changed_nodes,179        .renamed_nodes = try renamed.toOwnedSlice(allocator),180        .added_edges = result.added_edges,181        .removed_edges = result.removed_edges,182    };183}184185fn fuzzyMatch(allocator: std.mem.Allocator, added_nodes: []const model.Node, removed_nodes: []const model.Node, renamed: *std.ArrayList(RenamedNode), matched_added: *std.ArrayList([]const u8), matched_removed: *std.ArrayList([]const u8)) !void {186    for (added_nodes) |added| {187        if (containsString(matched_added.items, added.name)) continue;188        const added_tokens = try tokenize(allocator, added.name);189        if (added_tokens.len == 0) continue;190        var best_score: f64 = 0.0;191        var best_match: ?model.Node = null;192        for (removed_nodes) |removed| {193            if (containsString(matched_removed.items, removed.name)) continue;194            if (!std.mem.eql(u8, removed.type, added.type)) continue;195            const removed_tokens = try tokenize(allocator, removed.name);196            if (removed_tokens.len == 0) continue;197            const smaller = @min(added_tokens.len, removed_tokens.len);198            const larger = @max(added_tokens.len, removed_tokens.len);199            if (@as(f64, @floatFromInt(smaller)) / @as(f64, @floatFromInt(larger)) < 0.5) continue;200            const score = jaccard(added_tokens, removed_tokens);201            if (score > best_score) {202                best_score = score;203                best_match = removed;204            }205        }206        if (best_match) |node| {207            if (best_score >= 0.8) {208                try renamed.append(allocator, .{ .old_name = node.name, .new_name = added.name, .old_node = node, .new_node = added, .match_type = "fuzzy" });209                try matched_added.append(allocator, added.name);210                try matched_removed.append(allocator, node.name);211            }212        }213    }214}215216fn tokenize(allocator: std.mem.Allocator, name: []const u8) ![]const []const u8 {217    var out: std.ArrayList([]const u8) = .empty;218    var start: usize = 0;219    var index: usize = 0;220    while (index <= name.len) : (index += 1) {221        if (index == name.len or name[index] == '.' or name[index] == '_') {222            if (index > start) try appendUniqueString(allocator, &out, name[start..index]);223            start = index + 1;224        }225    }226    return try out.toOwnedSlice(allocator);227}228229fn jaccard(a: []const []const u8, b: []const []const u8) f64 {230    var intersection: usize = 0;231    for (a) |item| {232        if (containsString(b, item)) intersection += 1;233    }234    var union_count: usize = a.len;235    for (b) |item| {236        if (!containsString(a, item)) union_count += 1;237    }238    if (union_count == 0) return 0.0;239    return @as(f64, @floatFromInt(intersection)) / @as(f64, @floatFromInt(union_count));240}241242pub fn loadGraphFromGit(allocator: std.mem.Allocator, root: []const u8, ref: []const u8, invalid: *bool, limits: smg.Limits) !?graph_mod.Graph {243    invalid.* = false;244    if (!std.mem.eql(u8, ref, "HEAD")) {245        if (!try git.refExists(allocator, root, ref)) {246            invalid.* = true;247            return null;248        }249    }250    const temp_root = try std.fmt.allocPrint(allocator, "/tmp/smg-diff-ref-{x}-{x}", .{ @as(u64, @intCast(@max(0, sys.time.realMilliTimestamp()))), @intFromPtr(&allocator) });251    defer allocator.free(temp_root);252    defer sys.fs.deleteTree(temp_root) catch {};253    const add = try git.run(allocator, root, &.{ "git", "worktree", "add", "--detach", "--quiet", temp_root, ref }, 1024 * 1024);254    if (!add.ok) return null;255    defer {256        _ = git.run(allocator, root, &.{ "git", "worktree", "remove", "--force", temp_root }, 1024 * 1024) catch {};257    }258    var graph = graph_mod.init(allocator);259    _ = try scan.scanPathsWithOptions(allocator, &graph, temp_root, &.{temp_root}, false, .{ .limits = limits });260    return graph;261}262263test "loadGraphFromGit scans committed source ref" {264    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);265    defer arena.deinit();266    const allocator = arena.allocator();267    const root = try std.fmt.allocPrint(allocator, "/tmp/smg-diff-git-test-{x}-{x}", .{ @as(u64, @intCast(@max(0, sys.time.realMilliTimestamp()))), @intFromPtr(&arena) });268    defer sys.fs.deleteTree(root) catch {};269    try sys.fs.createDirPath(root);270    try std.testing.expect((try git.run(allocator, root, &.{ "git", "init" }, 1024 * 1024)).ok);271    const source_path = try std.fs.path.join(allocator, &.{ root, "app.py" });272    try text.writeFile(source_path, "def alpha():\n    return 1\n");273    try std.testing.expect((try git.run(allocator, root, &.{ "git", "add", "app.py" }, 1024 * 1024)).ok);274    try std.testing.expect((try git.run(allocator, root, &.{ "git", "-c", "user.name=smg", "-c", "user.email=smg@example.invalid", "commit", "-m", "base" }, 1024 * 1024)).ok);275    try text.writeFile(source_path, "def alpha():\n    return 1\n\ndef beta():\n    return 2\n");276    var invalid = false;277    const loaded = (try loadGraphFromGit(allocator, root, "HEAD", &invalid, smg.default_limits)).?;278    try std.testing.expect(!invalid);279    try std.testing.expect(graph_mod.getNode(&loaded, "app.alpha") != null);280    try std.testing.expect(graph_mod.getNode(&loaded, "app.beta") == null);281}282283pub fn toJson(allocator: std.mem.Allocator, result: Result, ref: []const u8) ![]const u8 {284    var out: std.Io.Writer.Allocating = .init(allocator);285    errdefer out.deinit();286    var writer = pretty_json.Writer.init(&out.writer, .minified);287    try writer.beginObject();288    try writer.objectField("ref");289    try writer.write(ref);290    try writer.objectField("added_nodes");291    try writeNodeNames(&writer, result.added_nodes);292    try writer.objectField("removed_nodes");293    try writeNodeNames(&writer, result.removed_nodes);294    try writer.objectField("changed_nodes");295    try writer.beginArray();296    for (result.changed_nodes) |changed| {297        try writer.beginObject();298        try writer.objectField("name");299        try writer.write(changed.node.name);300        try writer.objectField("changes");301        try writer.beginArray();302        for (changed.changes) |change| {303            try writer.beginObject();304            try writer.objectField("field");305            try writer.write(change.field);306            try writer.objectField("old");307            try writer.write(change.old);308            try writer.objectField("new");309            try writer.write(change.new);310            try writer.endObject();311        }312        try writer.endArray();313        try writer.endObject();314    }315    try writer.endArray();316    try writer.objectField("renamed_nodes");317    try writer.beginArray();318    for (result.renamed_nodes) |renamed| {319        try writer.beginObject();320        try writer.objectField("old_name");321        try writer.write(renamed.old_name);322        try writer.objectField("new_name");323        try writer.write(renamed.new_name);324        try writer.objectField("match_type");325        try writer.write(renamed.match_type);326        try writer.endObject();327    }328    try writer.endArray();329    try writer.objectField("added_edges");330    try writeEdges(&writer, result.added_edges);331    try writer.objectField("removed_edges");332    try writeEdges(&writer, result.removed_edges);333    try writer.objectField("summary");334    try writer.beginObject();335    try writer.objectField("nodes_added");336    try writer.write(result.added_nodes.len);337    try writer.objectField("nodes_removed");338    try writer.write(result.removed_nodes.len);339    try writer.objectField("nodes_changed");340    try writer.write(result.changed_nodes.len);341    try writer.objectField("nodes_renamed");342    try writer.write(result.renamed_nodes.len);343    try writer.objectField("edges_added");344    try writer.write(result.added_edges.len);345    try writer.objectField("edges_removed");346    try writer.write(result.removed_edges.len);347    try writer.endObject();348    try writer.endObject();349    try out.writer.writeByte('\n');350    return try out.toOwnedSlice();351}352353pub fn toText(allocator: std.mem.Allocator, result: Result, ref: []const u8, old_missing: bool) ![]const u8 {354    var out: std.Io.Writer.Allocating = .init(allocator);355    errdefer out.deinit();356    if (old_missing) try out.writer.print("No graph found at ref {s}. Showing full graph as new.\n", .{ref});357    if (result.empty()) {358        try out.writer.print("No structural changes vs {s}.\n", .{ref});359        return try out.toOwnedSlice();360    }361    try out.writer.print("Diff vs {s}\n\n", .{ref});362    if (result.added_nodes.len != 0) {363        try out.writer.print("+ {d} node(s) added\n", .{result.added_nodes.len});364        for (result.added_nodes) |node| try out.writer.print("  + [{s}] {s}\n", .{ node.type, node.name });365    }366    if (result.removed_nodes.len != 0) {367        try out.writer.print("- {d} node(s) removed\n", .{result.removed_nodes.len});368        for (result.removed_nodes) |node| try out.writer.print("  - [{s}] {s}\n", .{ node.type, node.name });369    }370    if (result.changed_nodes.len != 0) {371        try out.writer.print("~ {d} node(s) changed\n", .{result.changed_nodes.len});372        for (result.changed_nodes) |changed| {373            try out.writer.print("  ~ {s}\n", .{changed.node.name});374            for (changed.changes) |change| try out.writer.print("      {s}: {s} → {s}\n", .{ change.field, change.old orelse "None", change.new orelse "None" });375        }376    }377    if (result.renamed_nodes.len != 0) {378        try out.writer.print("~ {d} node(s) renamed/moved\n", .{result.renamed_nodes.len});379        for (result.renamed_nodes) |renamed| {380            const tag: []const u8 = if (std.mem.eql(u8, renamed.match_type, "content")) "exact" else "structural";381            try out.writer.print("  ~ {s} → {s} ({s} match)\n", .{ renamed.old_name, renamed.new_name, tag });382        }383    }384    if (result.added_edges.len != 0) {385        try out.writer.print("+ {d} edge(s) added\n", .{result.added_edges.len});386        for (result.added_edges[0..@min(result.added_edges.len, 20)]) |edge| try out.writer.print("  + {s} --{s}--> {s}\n", .{ edge.source, edge.rel, edge.target });387        if (result.added_edges.len > 20) try out.writer.print("  ... and {d} more\n", .{result.added_edges.len - 20});388    }389    if (result.removed_edges.len != 0) {390        try out.writer.print("- {d} edge(s) removed\n", .{result.removed_edges.len});391        for (result.removed_edges[0..@min(result.removed_edges.len, 20)]) |edge| try out.writer.print("  - {s} --{s}--> {s}\n", .{ edge.source, edge.rel, edge.target });392        if (result.removed_edges.len > 20) try out.writer.print("  ... and {d} more\n", .{result.removed_edges.len - 20});393    }394    try out.writer.writeAll("\nNodes: ");395    var wrote = false;396    if (result.added_nodes.len != 0) {397        try out.writer.print("+{d}", .{result.added_nodes.len});398        wrote = true;399    }400    if (result.removed_nodes.len != 0) {401        if (wrote) try out.writer.writeAll(", ");402        try out.writer.print("-{d}", .{result.removed_nodes.len});403        wrote = true;404    }405    if (result.changed_nodes.len != 0) {406        if (wrote) try out.writer.writeAll(", ");407        try out.writer.print("~{d}", .{result.changed_nodes.len});408        wrote = true;409    }410    if (result.renamed_nodes.len != 0) {411        if (wrote) try out.writer.writeAll(", ");412        try out.writer.print("↷{d}", .{result.renamed_nodes.len});413    }414    try out.writer.print(" | Edges: +{d} -{d}\n", .{ result.added_edges.len, result.removed_edges.len });415    return try out.toOwnedSlice();416}417418fn writeNodeNames(writer: *pretty_json.Writer, nodes: []const model.Node) !void {419    try writer.beginArray();420    for (nodes) |node| try writer.write(node.name);421    try writer.endArray();422}423424fn writeEdges(writer: *pretty_json.Writer, edges: []const model.Edge) !void {425    try writer.beginArray();426    for (edges) |edge| {427        try writer.beginObject();428        try writer.objectField("source");429        try writer.write(edge.source);430        try writer.objectField("rel");431        try writer.write(edge.rel);432        try writer.objectField("target");433        try writer.write(edge.target);434        try writer.endObject();435    }436    try writer.endArray();437}438439fn containsString(values: []const []const u8, value: []const u8) bool {440    for (values) |item| {441        if (std.mem.eql(u8, item, value)) return true;442    }443    return false;444}445446fn appendUniqueString(allocator: std.mem.Allocator, list: *std.ArrayList([]const u8), value: []const u8) !void {447    if (!containsString(list.items, value)) try list.append(allocator, value);448}449450fn linearHasEdge(graph: graph_mod.Graph, edge: model.Edge) bool {451    for (graph.edges.items) |candidate| {452        if (std.mem.eql(u8, candidate.source, edge.source) and453            std.mem.eql(u8, candidate.rel, edge.rel) and454            std.mem.eql(u8, candidate.target, edge.target)) return true;455    }456    return false;457}458459fn linearEdgeDiff(460    allocator: std.mem.Allocator,461    subject: graph_mod.Graph,462    other: graph_mod.Graph,463) ![]const model.Edge {464    var edges: std.ArrayList(model.Edge) = .empty;465    for (subject.edges.items) |edge| {466        if (!linearHasEdge(other, edge)) try edges.append(allocator, edge);467    }468    view.sortEdges(edges.items);469    return try edges.toOwnedSlice(allocator);470}471472fn expectEdgeIdentityEqual(expected: []const model.Edge, actual: []const model.Edge) !void {473    try std.testing.expectEqual(expected.len, actual.len);474    for (expected, actual) |left, right| {475        try std.testing.expectEqualStrings(left.source, right.source);476        try std.testing.expectEqualStrings(left.rel, right.rel);477        try std.testing.expectEqualStrings(left.target, right.target);478    }479}480481const DifferentialFixture = struct {482    old: graph_mod.Graph,483    new: graph_mod.Graph,484};485486fn differentialFixture(allocator: std.mem.Allocator, seed: usize) !DifferentialFixture {487    const node_count = 32;488    var names: [node_count][]const u8 = undefined;489    for (&names, 0..) |*name, index| {490        name.* = try std.fmt.allocPrint(allocator, "node_{d:0>2}", .{index});491    }492    var old = graph_mod.init(allocator);493    var new = graph_mod.init(allocator);494    for (0..node_count) |step| {495        const old_index = (step * 5 + seed) % node_count;496        const new_index = (step * 7 + seed) % node_count;497        try graph_mod.addNode(&old, .{ .name = names[old_index], .type = model.NodeType.function });498        try graph_mod.addNode(&new, .{ .name = names[new_index], .type = model.NodeType.function });499    }500    for (0..node_count) |step| {501        const old_index = (step * 5 + seed) % node_count;502        const new_index = (step * 7 + seed) % node_count;503        try graph_mod.addEdge(&old, .{504            .source = names[old_index],505            .rel = "common",506            .target = names[(old_index + 1) % node_count],507        });508        try graph_mod.addEdge(&new, .{509            .source = names[new_index],510            .rel = "common",511            .target = names[(new_index + 1) % node_count],512        });513    }514    for (0..8) |index| {515        const target = names[(index + 9) % node_count];516        try graph_mod.addEdge(&old, .{ .source = names[index], .rel = "old", .target = target });517        try graph_mod.addEdge(&new, .{518            .source = names[7 - index],519            .rel = "new",520            .target = names[(7 - index + 9) % node_count],521        });522    }523    return .{ .old = old, .new = new };524}525526test "diff detects added removed changed and edges" {527    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);528    defer arena.deinit();529    const allocator = arena.allocator();530    var old = graph_mod.init(allocator);531    try graph_mod.addNode(&old, .{ .name = "app", .type = model.NodeType.module });532    try graph_mod.addNode(&old, .{ .name = "app.main", .type = model.NodeType.function, .file = "app.py", .line = 1, .docstring = "Entry" });533    try graph_mod.addNode(&old, .{ .name = "app.Server", .type = model.NodeType.class, .file = "app.py", .line = 10 });534    try graph_mod.addEdge(&old, .{ .source = "app", .rel = model.RelType.contains, .target = "app.main" });535    try graph_mod.addEdge(&old, .{ .source = "app", .rel = model.RelType.contains, .target = "app.Server" });536    var new = graph_mod.init(allocator);537    try graph_mod.addNode(&new, .{ .name = "app", .type = model.NodeType.module });538    try graph_mod.addNode(&new, .{ .name = "app.main", .type = model.NodeType.function, .file = "app.py", .line = 5, .docstring = "Updated" });539    try graph_mod.addNode(&new, .{ .name = "app.helper", .type = model.NodeType.function });540    try graph_mod.addEdge(&new, .{ .source = "app", .rel = model.RelType.contains, .target = "app.main" });541    try graph_mod.addEdge(&new, .{ .source = "app", .rel = model.RelType.contains, .target = "app.helper" });542    try graph_mod.addEdge(&new, .{ .source = "app.main", .rel = model.RelType.calls, .target = "app.helper" });543    const result = try graphs(allocator, old, new, true);544    try std.testing.expectEqual(@as(usize, 1), result.added_nodes.len);545    try std.testing.expectEqual(@as(usize, 1), result.removed_nodes.len);546    try std.testing.expectEqual(@as(usize, 1), result.changed_nodes.len);547    try std.testing.expectEqual(@as(usize, 2), result.added_edges.len);548    try std.testing.expectEqual(@as(usize, 1), result.removed_edges.len);549    try std.testing.expectEqualStrings("app.helper", result.added_nodes[0].name);550}551552test "diff preserves edge identity and text output" {553    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);554    defer arena.deinit();555    const allocator = arena.allocator();556    var old = graph_mod.init(allocator);557    var new = graph_mod.init(allocator);558    const names = [_][]const u8{ "root", "shared", "old_only", "new_only" };559    for (names) |name| {560        const node: model.Node = .{ .name = name, .type = model.NodeType.function };561        try graph_mod.addNode(&old, node);562        try graph_mod.addNode(&new, node);563    }564    const old_metadata = [_]model.Pair{.{ .key = "weight", .value = "1" }};565    const new_metadata = [_]model.Pair{.{ .key = "weight", .value = "2" }};566    try graph_mod.addEdge(&old, .{567        .source = "root",568        .rel = model.RelType.contains,569        .target = "shared",570        .metadata = &old_metadata,571    });572    try graph_mod.addEdge(&new, .{573        .source = "root",574        .rel = model.RelType.contains,575        .target = "shared",576        .metadata = &new_metadata,577    });578    try graph_mod.addEdge(&old, .{579        .source = "root",580        .rel = model.RelType.calls,581        .target = "old_only",582    });583    try graph_mod.addEdge(&new, .{584        .source = "root",585        .rel = model.RelType.calls,586        .target = "new_only",587    });588    const result = try graphs(allocator, old, new, false);589    try std.testing.expectEqual(@as(usize, 1), result.added_edges.len);590    try std.testing.expectEqual(@as(usize, 1), result.removed_edges.len);591    try std.testing.expectEqualStrings("new_only", result.added_edges[0].target);592    try std.testing.expectEqualStrings("old_only", result.removed_edges[0].target);593    try std.testing.expectEqualStrings(594        "Diff vs base\n\n" ++595            "+ 1 edge(s) added\n" ++596            "  + root --calls--> new_only\n" ++597            "- 1 edge(s) removed\n" ++598            "  - root --calls--> old_only\n" ++599            "\nNodes:  | Edges: +1 -1\n",600        try toText(allocator, result, "base", false),601    );602}603604test "diff verifies indexed edge identity without graph allocation" {605    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);606    defer arena.deinit();607    const allocator = arena.allocator();608    var old = graph_mod.init(allocator);609    var new = graph_mod.init(allocator);610    const long_source = try allocator.alloc(u8, 4096);611    @memset(long_source, 'x');612    const names = [_][]const u8{613        "a\x1fb",614        "d",615        "a",616        "c\x1fd",617        long_source,618        "long-target",619    };620    for (names) |name| {621        const node: model.Node = .{ .name = name, .type = model.NodeType.function };622        try graph_mod.addNode(&old, node);623        try graph_mod.addNode(&new, node);624    }625    try graph_mod.addEdge(&old, .{ .source = "a\x1fb", .rel = "c", .target = "d" });626    try graph_mod.addEdge(&new, .{ .source = "a", .rel = "b", .target = "c\x1fd" });627    const long_edge: model.Edge = .{628        .source = long_source,629        .rel = model.RelType.calls,630        .target = "long-target",631    };632    try graph_mod.addEdge(&old, long_edge);633    try graph_mod.addEdge(&new, long_edge);634    var failing = std.testing.FailingAllocator.init(allocator, .{ .fail_index = 0 });635    old.allocator = failing.allocator();636    new.allocator = failing.allocator();637    const result = try graphs(allocator, old, new, false);638    try std.testing.expectEqual(@as(usize, 1), result.added_edges.len);639    try std.testing.expectEqual(@as(usize, 1), result.removed_edges.len);640    try std.testing.expectEqualStrings("c\x1fd", result.added_edges[0].target);641    try std.testing.expectEqualStrings("a\x1fb", result.removed_edges[0].source);642}643644test "diff index matches linear edge oracle across insertion orders" {645    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);646    defer arena.deinit();647    const allocator = arena.allocator();648    for (0..16) |seed| {649        const fixture = try differentialFixture(allocator, seed);650        const result = try graphs(allocator, fixture.old, fixture.new, false);651        const expected_added = try linearEdgeDiff(allocator, fixture.new, fixture.old);652        const expected_removed = try linearEdgeDiff(allocator, fixture.old, fixture.new);653        try expectEdgeIdentityEqual(expected_added, result.added_edges);654        try expectEdgeIdentityEqual(expected_removed, result.removed_edges);655    }656}657658test "diff detects hash and fuzzy renames" {659    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);660    defer arena.deinit();661    const allocator = arena.allocator();662    var old = graph_mod.init(allocator);663    var new = graph_mod.init(allocator);664    const old_meta = [_]model.Pair{665        .{ .key = "content_hash", .value = "same" },666        .{ .key = "structure_hash", .value = "shape" },667    };668    const new_meta = [_]model.Pair{669        .{ .key = "content_hash", .value = "same" },670        .{ .key = "structure_hash", .value = "shape" },671    };672    try graph_mod.addNode(&old, .{ .name = "app.foo", .type = model.NodeType.function, .metadata = &old_meta });673    try graph_mod.addNode(&new, .{ .name = "app.bar", .type = model.NodeType.function, .metadata = &new_meta });674    const result = try graphs(allocator, old, new, true);675    try std.testing.expectEqual(@as(usize, 1), result.renamed_nodes.len);676    try std.testing.expectEqualStrings("content", result.renamed_nodes[0].match_type);677}

1pub const diff = @import("diff.zig");