tiny.smg.graph

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const model = @import("model.zig");45pub const edge_key_separator: u8 = 0x1f;67pub const Error = error{8    NodeNotFound,9    EdgeNotFound,10    AmbiguousName,11    CapacityOverflow,12};1314const SuffixEntry = struct {15    hash: u64,16    node: u32,17    start: u32,18};1920pub const SuffixIndex = struct {21    pub const Limits = struct {22        entries: usize,23        nodes: usize,24        max_name_bytes: usize,25    };2627    pub const Capacity = struct {28        entries: usize,29        nodes: usize,30        max_name_bytes: usize,31        bytes: usize,3233        pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {34            if (limits.nodes > std.math.maxInt(u32)) return error.CapacityOverflow;35            if (limits.max_name_bytes > std.math.maxInt(u32)) return error.CapacityOverflow;36            return .{37                .entries = limits.entries,38                .nodes = limits.nodes,39                .max_name_bytes = limits.max_name_bytes,40                .bytes = std.math.mul(usize, limits.entries, @sizeOf(SuffixEntry)) catch return error.CapacityOverflow,41            };42        }43    };4445    pub const InitError = std.mem.Allocator.Error || error{CapacityOverflow};4647    pub const claim: alloc_phase.capacity.Declaration = .{48        .source = .{49            .id = "smg.suffix_index",50            .kind = .phase_static,51            .limit_source = .caller,52            .storage = .{53                .covered = &.{54                    .{55                        .id = "one_compact_hash_node_and_suffix_start_record_per_d_8a2d437489ef",56                        .lifetime = .steady,57                        .detail = "one compact hash, node, and suffix-start record per dotted-name suffix",58                    },59                },60                .excluded = &.{61                    "graph nodes and decoded name storage referenced by index records",62                    "caller-owned resolution result arrays",63                    "linear fallback after graph mutation invalidates the snapshot",64                },65            },66            .capacity = .{67                .inputs = &.{68                    alloc_phase.capacity.bindInput(Limits, "entries", "entries"),69                    alloc_phase.capacity.bindInput(Limits, "max_name_bytes", "max_name_bytes"),70                    alloc_phase.capacity.bindInput(Limits, "nodes", "nodes"),71                },72                .type_selectors = &.{},73                .nodes = &.{74                    .{ .input = 0 },75                    .{ .input = 1 },76                    .{ .input = 2 },77                    .{ .add = .{ .left = 0, .right = 1 } },78                    .{ .add = .{ .left = 3, .right = 2 } },79                },80                .assertions = &.{.{81                    .scope = .closure_total,82                    .measure = .retained,83                    .relation = .upper_bound,84                    .expression = 4,85                }},86            },87            .overload = .{88                .kind = .reject_before_seal,89                .detail = "checked entry and byte counts plus u32 node and name bounds reject overflow or OOM before activation",90            },91            .risks = .{92                .transitive = .{93                    .status = .open,94                    .detail = "standard hash and sort helpers are allocation-free in the witness but lack a transitive allocation-closure certificate",95                },96                .foreign = .{97                    .status = .excluded,98                    .detail = "the index is process-local caller-owned memory with no operating-system or callback edge",99                },100            },101            .obligations = &.{102                .{ .key = "smg_suffix_index_capacity_capacity_model", .role = .capacity_model },103                .{ .key = "smg_suffix_index_capacity_overload", .role = .overload },104                .{ .key = "smg_suffix_index_oom", .role = .overload },105                .{ .key = "smg_suffix_index_sealed_transitive_risk", .role = .transitive_risk },106                .{ .key = "smg_suffix_index_sealed_foreign_risk", .role = .foreign_risk },107                .{ .key = "smg_suffix_index_invalidation", .role = .custom },108            },109        },110        .bindings = .{111            .owner = @This(),112            .seal = .{113                .family = alloc_phase.capacity.selector(@This().activate),114                .premise = .{115                    .class = .checked_semantic_fact,116                    .authority = .checker,117                },118            },119            .teardown = .{120                .family = alloc_phase.capacity.selector(@This().deinit),121                .premise = .{122                    .class = .checked_semantic_fact,123                    .authority = .checker,124                },125            },126        },127    };128129    phase: alloc_phase.capacity.Phase,130    capacity: Capacity,131    entries: []SuffixEntry,132133    pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!SuffixIndex {134        const capacity = try Capacity.derive(limits);135        const entries = if (capacity.entries == 0)136            @constCast((&[_]SuffixEntry{})[0..])137        else138            try allocator.alloc(SuffixEntry, capacity.entries);139        return .{140            .phase = .initialization,141            .capacity = capacity,142            .entries = entries,143        };144    }145146    pub fn fill(self: *SuffixIndex, nodes: []const model.Node) void {147        std.debug.assert(self.phase == .initialization);148        std.debug.assert(nodes.len == self.capacity.nodes);149        var filled: usize = 0;150        for (nodes, 0..) |node, node_index| {151            std.debug.assert(node.name.len <= self.capacity.max_name_bytes);152            var start: usize = 0;153            while (start < node.name.len) {154                std.debug.assert(filled < self.entries.len);155                self.entries[filled] = .{156                    .hash = std.hash_map.hashString(node.name[start..]),157                    .node = @intCast(node_index),158                    .start = @intCast(start),159                };160                filled += 1;161                const dot = std.mem.indexOfScalar(u8, node.name[start..], '.') orelse break;162                start += dot + 1;163            }164        }165        std.debug.assert(filled == self.entries.len);166        std.mem.sort(SuffixEntry, self.entries, {}, suffixEntryLess);167    }168169    pub fn activate(self: *SuffixIndex) void {170        std.debug.assert(self.phase == .initialization);171        self.phase = .steady;172    }173174    pub fn deinit(self: *SuffixIndex, allocator: std.mem.Allocator) void {175        std.debug.assert(self.phase != .teardown);176        self.phase = .teardown;177        if (self.entries.len != 0) allocator.free(self.entries);178        self.* = undefined;179    }180181    pub fn hashMatches(self: *const SuffixIndex, hash: u64) []const SuffixEntry {182        std.debug.assert(self.phase == .steady);183        const start = suffixHashLowerBound(self.entries, hash);184        const end = suffixHashUpperBound(self.entries[start..], hash) + start;185        return self.entries[start..end];186    }187};188189comptime {190    alloc_phase.capacity.requireAllocatorExactOwnerShape(SuffixIndex);191}192193pub const Graph = struct {194    allocator: std.mem.Allocator,195    nodes: std.ArrayList(model.Node) = .empty,196    edges: std.ArrayList(model.Edge) = .empty,197    node_index: std.StringHashMap(usize),198    suffix_index: ?SuffixIndex = null,199    edge_index: std.StringHashMap(usize),200    incoming_index: std.ArrayList(std.ArrayList(usize)) = .empty,201    outgoing_index: std.ArrayList(std.ArrayList(usize)) = .empty,202};203204pub fn init(allocator: std.mem.Allocator) Graph {205    return .{206        .allocator = allocator,207        .node_index = std.StringHashMap(usize).init(allocator),208        .edge_index = std.StringHashMap(usize).init(allocator),209    };210}211212pub fn clone(allocator: std.mem.Allocator, scratch: std.mem.Allocator, source: Graph) !Graph {213    var graph = init(allocator);214    errdefer {215        for (graph.nodes.items) |*node| model.deinitNode(node, allocator);216        for (graph.edges.items) |*edge| model.deinitEdge(edge, allocator);217        deinit(&graph);218    }219    try reserveNodes(&graph, source.nodes.items.len);220    for (source.nodes.items) |node| {221        var cloned = try model.cloneNode(allocator, node);222        errdefer model.deinitNode(&cloned, allocator);223        try addNode(&graph, cloned);224    }225    try reserveEdges(&graph, source.edges.items.len);226    const incoming = try scratch.alloc(usize, source.nodes.items.len);227    defer scratch.free(incoming);228    const outgoing = try scratch.alloc(usize, source.nodes.items.len);229    defer scratch.free(outgoing);230    for (source.nodes.items, 0..) |_, index| {231        incoming[index] = source.incoming_index.items[index].items.len;232        outgoing[index] = source.outgoing_index.items[index].items.len;233    }234    try reserveAdjacency(&graph, incoming, outgoing);235    for (source.edges.items) |edge| {236        var cloned = try model.cloneEdge(allocator, edge);237        errdefer model.deinitEdge(&cloned, allocator);238        try addEdge(&graph, cloned);239    }240    return graph;241}242243pub fn deinit(graph: *Graph) void {244    graph.nodes.deinit(graph.allocator);245    graph.edges.deinit(graph.allocator);246    graph.node_index.deinit();247    if (graph.suffix_index) |*index| index.deinit(graph.allocator);248    var edge_it = graph.edge_index.iterator();249    while (edge_it.next()) |entry| graph.allocator.free(entry.key_ptr.*);250    graph.edge_index.deinit();251    for (graph.incoming_index.items) |*list| list.deinit(graph.allocator);252    graph.incoming_index.deinit(graph.allocator);253    for (graph.outgoing_index.items) |*list| list.deinit(graph.allocator);254    graph.outgoing_index.deinit(graph.allocator);255    graph.* = undefined;256}257258pub fn incomingEdges(graph: *const Graph, name: []const u8) []const usize {259    const index = graph.node_index.get(name) orelse return &.{};260    return graph.incoming_index.items[index].items;261}262263pub fn outgoingEdges(graph: *const Graph, name: []const u8) []const usize {264    const index = graph.node_index.get(name) orelse return &.{};265    return graph.outgoing_index.items[index].items;266}267268pub fn reserveNodes(graph: *Graph, count: usize) !void {269    const map_count = std.math.cast(u32, count) orelse return Error.CapacityOverflow;270    try graph.nodes.ensureTotalCapacityPrecise(graph.allocator, count);271    try graph.node_index.ensureTotalCapacity(map_count);272    try graph.incoming_index.ensureTotalCapacityPrecise(graph.allocator, count);273    try graph.outgoing_index.ensureTotalCapacityPrecise(graph.allocator, count);274}275276pub fn reserveEdges(graph: *Graph, count: usize) !void {277    const map_count = std.math.cast(u32, count) orelse return Error.CapacityOverflow;278    try graph.edges.ensureTotalCapacityPrecise(graph.allocator, count);279    try graph.edge_index.ensureTotalCapacity(map_count);280}281282pub fn reserveAdjacency(graph: *Graph, incoming: []const usize, outgoing: []const usize) !void {283    std.debug.assert(incoming.len == graph.incoming_index.items.len);284    std.debug.assert(outgoing.len == graph.outgoing_index.items.len);285    for (graph.incoming_index.items, incoming) |*list, count| {286        try list.ensureTotalCapacityPrecise(graph.allocator, count);287    }288    for (graph.outgoing_index.items, outgoing) |*list, count| {289        try list.ensureTotalCapacityPrecise(graph.allocator, count);290    }291}292293pub fn addNode(graph: *Graph, node: model.Node) !void {294    if (graph.node_index.get(node.name)) |index| {295        var existing = &graph.nodes.items[index];296        existing.type = node.type;297        if (node.file != null) existing.file = node.file;298        if (node.line != null) existing.line = node.line;299        if (node.end_line != null) existing.end_line = node.end_line;300        if (node.docstring != null) existing.docstring = node.docstring;301        if (node.metadata.len != 0) existing.metadata = try model.mergePairs(graph.allocator, existing.metadata, node.metadata);302        return;303    }304    try graph.nodes.append(graph.allocator, node);305    errdefer _ = graph.nodes.pop();306    try graph.node_index.put(node.name, graph.nodes.items.len - 1);307    errdefer _ = graph.node_index.remove(node.name);308    try graph.incoming_index.append(graph.allocator, .empty);309    errdefer _ = graph.incoming_index.pop();310    try graph.outgoing_index.append(graph.allocator, .empty);311    errdefer _ = graph.outgoing_index.pop();312    invalidateSuffixIndex(graph);313}314315pub fn buildSuffixIndex(graph: *Graph) !void {316    if (graph.suffix_index != null) return;317    const limits = try suffixIndexLimits(graph.nodes.items);318    var index = try SuffixIndex.init(graph.allocator, limits);319    errdefer index.deinit(graph.allocator);320    index.fill(graph.nodes.items);321    index.activate();322    graph.suffix_index = index;323}324325pub fn suffixIndexReady(graph: Graph) bool {326    return graph.suffix_index != null;327}328329pub const SuffixIterator = struct {330    graph: *const Graph,331    raw: []const u8,332    entries: ?[]const SuffixEntry,333    position: usize = 0,334335    pub fn nextNode(self: *SuffixIterator) ?*const model.Node {336        if (self.entries) |entries| {337            while (self.position < entries.len) {338                const entry = entries[self.position];339                self.position += 1;340                if (!suffixEntryMatches(self.graph.nodes.items, entry, self.raw)) continue;341                return &self.graph.nodes.items[entry.node];342            }343            return null;344        }345        while (self.position < self.graph.nodes.items.len) {346            const node = &self.graph.nodes.items[self.position];347            self.position += 1;348            if (matchesDottedSuffix(node.name, self.raw)) return node;349        }350        return null;351    }352353    pub fn next(self: *SuffixIterator) ?[]const u8 {354        const node = self.nextNode() orelse return null;355        return node.name;356    }357};358359pub fn suffixIterator(graph: *const Graph, raw: []const u8) SuffixIterator {360    return .{361        .graph = graph,362        .raw = raw,363        .entries = if (graph.suffix_index) |*index|364            index.hashMatches(std.hash_map.hashString(raw))365        else366            null,367    };368}369370pub fn appendSuffixMatches(graph: Graph, allocator: std.mem.Allocator, raw: []const u8, out: *std.ArrayList([]const u8)) !void {371    var iterator = suffixIterator(&graph, raw);372    while (iterator.next()) |name| try out.append(allocator, name);373}374375fn suffixEntryMatches(nodes: []const model.Node, entry: SuffixEntry, raw: []const u8) bool {376    const node = nodes[entry.node];377    return std.mem.eql(u8, node.name[entry.start..], raw);378}379380fn matchesDottedSuffix(name: []const u8, suffix: []const u8) bool {381    if (!std.mem.endsWith(u8, name, suffix)) return false;382    if (name.len == suffix.len) return true;383    return name[name.len - suffix.len - 1] == '.';384}385386fn suffixMatchCount(graph: Graph, raw: []const u8) usize {387    var count: usize = 0;388    var iterator = suffixIterator(&graph, raw);389    while (iterator.next() != null) count += 1;390    return count;391}392393pub fn addEdge(graph: *Graph, edge: model.Edge) !void {394    _ = try addEdgeTracked(graph, edge);395}396397pub fn addEdgeTracked(graph: *Graph, edge: model.Edge) !bool {398    if (!graph.node_index.contains(edge.source) or !graph.node_index.contains(edge.target)) return Error.NodeNotFound;399    var stack: [4096]u8 = undefined;400    const key_len = edgeKeyLen(edge.source, edge.rel, edge.target);401    const lookup_key = if (key_len <= stack.len)402        edgeKeyInto(stack[0..key_len], edge.source, edge.rel, edge.target)403    else404        try edgeKey(graph.allocator, edge.source, edge.rel, edge.target);405    var lookup_key_owned = key_len > stack.len;406    errdefer if (lookup_key_owned) graph.allocator.free(lookup_key);407    if (graph.edge_index.get(lookup_key)) |index| {408        defer if (lookup_key_owned) graph.allocator.free(lookup_key);409        if (edge.metadata.len != 0) graph.edges.items[index].metadata = try model.mergePairs(graph.allocator, graph.edges.items[index].metadata, edge.metadata);410        return false;411    }412    const key = if (lookup_key_owned) key: {413        lookup_key_owned = false;414        break :key lookup_key;415    } else try graph.allocator.dupe(u8, lookup_key);416    var key_owned = true;417    errdefer if (key_owned) graph.allocator.free(key);418    try graph.edges.append(graph.allocator, edge);419    errdefer _ = graph.edges.pop();420    const edge_position = graph.edges.items.len - 1;421    const source_index = graph.node_index.get(edge.source).?;422    const target_index = graph.node_index.get(edge.target).?;423    try graph.outgoing_index.items[source_index].append(graph.allocator, edge_position);424    errdefer _ = graph.outgoing_index.items[source_index].pop();425    try graph.incoming_index.items[target_index].append(graph.allocator, edge_position);426    errdefer _ = graph.incoming_index.items[target_index].pop();427    try graph.edge_index.put(key, edge_position);428    key_owned = false;429    return true;430}431432pub fn getNode(graph: *const Graph, name: []const u8) ?model.Node {433    const index = graph.node_index.get(name) orelse return null;434    return graph.nodes.items[index];435}436437const dead_position = std.math.maxInt(usize);438439pub fn removeNodes(graph: *Graph, names: []const []const u8) !void {440    if (names.len == 0) return;441    var removed = std.StringHashMap(void).init(graph.allocator);442    defer removed.deinit();443    try removed.ensureTotalCapacity(@intCast(names.len));444    for (names) |name| {445        if (!graph.node_index.contains(name)) return Error.NodeNotFound;446        removed.putAssumeCapacity(name, {});447    }448    const node_map = try graph.allocator.alloc(usize, graph.nodes.items.len);449    defer graph.allocator.free(node_map);450    const edge_map = try graph.allocator.alloc(usize, graph.edges.items.len);451    defer graph.allocator.free(edge_map);452    const key_buffer = try graph.allocator.alloc(u8, maxRetiredEdgeKeyLen(graph.*, removed));453    defer graph.allocator.free(key_buffer);454455    const kept_nodes = planNodeRemoval(graph.*, removed, node_map);456    const kept_edges = planEdgeRemoval(graph.*, removed, edge_map);457    std.debug.assert(kept_nodes < graph.nodes.items.len);458    invalidateSuffixIndex(graph);459    pruneEdgeIndex(graph, edge_map, key_buffer);460    pruneNodeIndex(graph, names, node_map);461    compactAdjacency(graph, node_map, edge_map, kept_nodes);462    compactEdges(graph, edge_map, kept_edges);463    compactNodes(graph, node_map, kept_nodes);464    std.debug.assert(graph.nodes.items.len == kept_nodes);465    std.debug.assert(graph.edges.items.len == kept_edges);466    std.debug.assert(graph.node_index.count() == kept_nodes);467    std.debug.assert(graph.edge_index.count() == kept_edges);468}469470pub fn removeEdge(graph: *Graph, source: []const u8, rel: []const u8, target: []const u8) !void {471    var stack: [4096]u8 = undefined;472    const key_len = edgeKeyLen(source, rel, target);473    const lookup_key = if (key_len <= stack.len)474        edgeKeyInto(stack[0..key_len], source, rel, target)475    else476        try edgeKey(graph.allocator, source, rel, target);477    defer if (key_len > stack.len) graph.allocator.free(lookup_key);478    const entry = graph.edge_index.fetchRemove(lookup_key) orelse return Error.EdgeNotFound;479    graph.allocator.free(entry.key);480    const position = entry.value;481    std.debug.assert(position < graph.edges.items.len);482    _ = graph.edges.orderedRemove(position);483    var index_it = graph.edge_index.valueIterator();484    while (index_it.next()) |value| {485        std.debug.assert(value.* != position);486        if (value.* > position) value.* -= 1;487    }488    for (graph.incoming_index.items) |*list| dropEdgeReference(list, position);489    for (graph.outgoing_index.items) |*list| dropEdgeReference(list, position);490}491492fn dropEdgeReference(list: *std.ArrayList(usize), position: usize) void {493    var write: usize = 0;494    for (list.items) |reference| {495        if (reference == position) continue;496        list.items[write] = if (reference > position) reference - 1 else reference;497        write += 1;498    }499    list.shrinkRetainingCapacity(write);500}501502fn maxRetiredEdgeKeyLen(graph: Graph, removed: std.StringHashMap(void)) usize {503    var max_len: usize = 0;504    for (graph.edges.items) |edge| {505        if (!removed.contains(edge.source) and !removed.contains(edge.target)) continue;506        max_len = @max(max_len, edgeKeyLen(edge.source, edge.rel, edge.target));507    }508    return max_len;509}510511fn planNodeRemoval(graph: Graph, removed: std.StringHashMap(void), node_map: []usize) usize {512    var kept: usize = 0;513    for (graph.nodes.items, 0..) |node, index| {514        if (removed.contains(node.name)) {515            node_map[index] = dead_position;516        } else {517            node_map[index] = kept;518            kept += 1;519        }520    }521    return kept;522}523524fn planEdgeRemoval(graph: Graph, removed: std.StringHashMap(void), edge_map: []usize) usize {525    var kept: usize = 0;526    for (graph.edges.items, 0..) |edge, index| {527        if (removed.contains(edge.source) or removed.contains(edge.target)) {528            edge_map[index] = dead_position;529        } else {530            edge_map[index] = kept;531            kept += 1;532        }533    }534    return kept;535}536537fn pruneEdgeIndex(graph: *Graph, edge_map: []const usize, key_buffer: []u8) void {538    for (graph.edges.items, 0..) |edge, index| {539        if (edge_map[index] != dead_position) continue;540        const key_len = edgeKeyLen(edge.source, edge.rel, edge.target);541        std.debug.assert(key_len <= key_buffer.len);542        const key = edgeKeyInto(key_buffer[0..key_len], edge.source, edge.rel, edge.target);543        const entry = graph.edge_index.fetchRemove(key) orelse unreachable;544        graph.allocator.free(entry.key);545    }546    var values = graph.edge_index.valueIterator();547    while (values.next()) |value| {548        std.debug.assert(edge_map[value.*] != dead_position);549        value.* = edge_map[value.*];550    }551}552553fn pruneNodeIndex(graph: *Graph, names: []const []const u8, node_map: []const usize) void {554    for (names) |name| _ = graph.node_index.remove(name);555    var values = graph.node_index.valueIterator();556    while (values.next()) |value| {557        std.debug.assert(node_map[value.*] != dead_position);558        value.* = node_map[value.*];559    }560}561562fn compactAdjacency(graph: *Graph, node_map: []const usize, edge_map: []const usize, kept_nodes: usize) void {563    remapAdjacencyLists(graph, graph.incoming_index.items, node_map, edge_map);564    remapAdjacencyLists(graph, graph.outgoing_index.items, node_map, edge_map);565    graph.incoming_index.shrinkRetainingCapacity(kept_nodes);566    graph.outgoing_index.shrinkRetainingCapacity(kept_nodes);567}568569fn remapAdjacencyLists(graph: *Graph, lists: []std.ArrayList(usize), node_map: []const usize, edge_map: []const usize) void {570    for (lists, 0..) |*list, index| {571        if (node_map[index] == dead_position) {572            list.deinit(graph.allocator);573            continue;574        }575        var write: usize = 0;576        for (list.items) |reference| {577            if (edge_map[reference] == dead_position) continue;578            list.items[write] = edge_map[reference];579            write += 1;580        }581        list.shrinkRetainingCapacity(write);582        std.debug.assert(node_map[index] <= index);583        lists[node_map[index]] = list.*;584    }585}586587fn compactEdges(graph: *Graph, edge_map: []const usize, kept_edges: usize) void {588    for (graph.edges.items, 0..) |edge, index| {589        if (edge_map[index] == dead_position) continue;590        std.debug.assert(edge_map[index] <= index);591        graph.edges.items[edge_map[index]] = edge;592    }593    graph.edges.shrinkRetainingCapacity(kept_edges);594}595596fn compactNodes(graph: *Graph, node_map: []const usize, kept_nodes: usize) void {597    for (graph.nodes.items, 0..) |node, index| {598        if (node_map[index] == dead_position) continue;599        graph.nodes.items[node_map[index]] = node;600    }601    graph.nodes.shrinkRetainingCapacity(kept_nodes);602}603604fn suffixIndexLimits(nodes: []const model.Node) error{CapacityOverflow}!SuffixIndex.Limits {605    if (nodes.len > std.math.maxInt(u32)) return error.CapacityOverflow;606    var entries: usize = 0;607    var max_name_bytes: usize = 0;608    for (nodes) |node| {609        if (node.name.len > std.math.maxInt(u32)) return error.CapacityOverflow;610        max_name_bytes = @max(max_name_bytes, node.name.len);611        var suffixes = if (node.name.len == 0)612            0613        else614            std.math.add(usize, std.mem.countScalar(u8, node.name, '.'), 1) catch return error.CapacityOverflow;615        if (node.name.len != 0 and node.name[node.name.len - 1] == '.') suffixes -= 1;616        entries = std.math.add(usize, entries, suffixes) catch return error.CapacityOverflow;617    }618    const limits = SuffixIndex.Limits{619        .entries = entries,620        .nodes = nodes.len,621        .max_name_bytes = max_name_bytes,622    };623    _ = try SuffixIndex.Capacity.derive(limits);624    return limits;625}626627fn invalidateSuffixIndex(graph: *Graph) void {628    if (graph.suffix_index) |*index| index.deinit(graph.allocator);629    graph.suffix_index = null;630}631632fn suffixEntryLess(_: void, left: SuffixEntry, right: SuffixEntry) bool {633    return left.hash < right.hash;634}635636fn suffixHashLowerBound(entries: []const SuffixEntry, hash: u64) usize {637    var lower: usize = 0;638    var upper = entries.len;639    while (lower < upper) {640        const middle = lower + (upper - lower) / 2;641        if (entries[middle].hash < hash) {642            lower = middle + 1;643        } else {644            upper = middle;645        }646    }647    return lower;648}649650fn suffixHashUpperBound(entries: []const SuffixEntry, hash: u64) usize {651    var lower: usize = 0;652    var upper = entries.len;653    while (lower < upper) {654        const middle = lower + (upper - lower) / 2;655        if (entries[middle].hash <= hash) {656            lower = middle + 1;657        } else {658            upper = middle;659        }660    }661    return lower;662}663664pub fn edgeKey(allocator: std.mem.Allocator, source: []const u8, rel: []const u8, target: []const u8) ![]const u8 {665    const out = try allocator.alloc(u8, edgeKeyLen(source, rel, target));666    return edgeKeyInto(out, source, rel, target);667}668669pub fn edgeKeyLen(source: []const u8, rel: []const u8, target: []const u8) usize {670    return source.len + 1 + rel.len + 1 + target.len;671}672673pub fn edgeKeyInto(out: []u8, source: []const u8, rel: []const u8, target: []const u8) []const u8 {674    var index: usize = 0;675    @memcpy(out[index..][0..source.len], source);676    index += source.len;677    out[index] = edge_key_separator;678    index += 1;679    @memcpy(out[index..][0..rel.len], rel);680    index += rel.len;681    out[index] = edge_key_separator;682    index += 1;683    @memcpy(out[index..][0..target.len], target);684    return out;685}686687pub fn isScan(pairs: []const model.Pair) bool {688    const source = model.pairValue(pairs, "source") orelse return false;689    return std.mem.eql(u8, source, "scan");690}691692test "graph clone owns payload independently" {693    var source_arena = std.heap.ArenaAllocator.init(std.testing.allocator);694    var source_live = true;695    defer if (source_live) source_arena.deinit();696    const source_allocator = source_arena.allocator();697    var source = init(source_allocator);698    const metadata = try model.sourcePair(source_allocator, "scan");699    const parent = try source_allocator.dupe(u8, "app");700    const child = try source_allocator.dupe(u8, "app.main");701    try addNode(&source, .{702        .name = parent,703        .type = try source_allocator.dupe(u8, model.NodeType.module),704        .file = try source_allocator.dupe(u8, "app.zig"),705        .metadata = metadata,706    });707    try addNode(&source, .{708        .name = child,709        .type = try source_allocator.dupe(u8, model.NodeType.function),710        .docstring = try source_allocator.dupe(u8, "entrypoint"),711        .metadata = metadata,712    });713    try addEdge(&source, .{714        .source = try source_allocator.dupe(u8, parent),715        .rel = try source_allocator.dupe(u8, model.RelType.contains),716        .target = try source_allocator.dupe(u8, child),717        .metadata = metadata,718    });719720    var cloned_arena = std.heap.ArenaAllocator.init(std.testing.allocator);721    defer cloned_arena.deinit();722    const cloned = try clone(cloned_arena.allocator(), std.testing.allocator, source);723    try std.testing.expect(source.nodes.items[0].name.ptr != cloned.nodes.items[0].name.ptr);724    try std.testing.expect(source.edges.items[0].source.ptr != cloned.edges.items[0].source.ptr);725    source_arena.deinit();726    source_live = false;727728    try std.testing.expectEqualStrings("app.zig", getNode(&cloned, "app").?.file.?);729    try std.testing.expectEqualStrings("entrypoint", getNode(&cloned, "app.main").?.docstring.?);730    try std.testing.expectEqualStrings("scan", model.pairValue(cloned.edges.items[0].metadata, "source").?);731    try std.testing.expectEqual(@as(usize, 1), outgoingEdges(&cloned, "app").len);732    try std.testing.expectEqual(@as(usize, 1), incomingEdges(&cloned, "app.main").len);733}734735fn checkGraphCloneAllocationFailures(allocator: std.mem.Allocator) !void {736    var source = init(std.testing.allocator);737    defer deinit(&source);738    try addNode(&source, .{ .name = "app", .type = model.NodeType.module, .file = "app.zig" });739    try addNode(&source, .{ .name = "app.main", .type = model.NodeType.function, .docstring = "entrypoint" });740    try addEdge(&source, .{ .source = "app", .rel = model.RelType.contains, .target = "app.main" });741    var cloned = try clone(allocator, allocator, source);742    defer {743        for (cloned.nodes.items) |*node| model.deinitNode(node, allocator);744        for (cloned.edges.items) |*edge| model.deinitEdge(edge, allocator);745        deinit(&cloned);746    }747    try std.testing.expectEqual(@as(usize, 2), cloned.nodes.items.len);748    try std.testing.expectEqual(@as(usize, 1), cloned.edges.items.len);749}750751test "graph clone cleans every allocation failure" {752    try std.testing.checkAllAllocationFailures(753        std.testing.allocator,754        checkGraphCloneAllocationFailures,755        .{},756    );757}758759test "graph operations clean up allocation failures" {760    try std.testing.checkAllAllocationFailures(761        std.testing.allocator,762        checkGraphAllocationFailures,763        .{},764    );765}766767fn checkGraphAllocationFailures(allocator: std.mem.Allocator) !void {768    const source = &(@as([4100]u8, @splat('s')));769    const target = &(@as([4100]u8, @splat('t')));770    var graph = init(allocator);771    defer deinit(&graph);772    try buildSuffixIndex(&graph);773    try addNode(&graph, .{ .name = source, .type = model.NodeType.module });774    try addNode(&graph, .{ .name = target, .type = model.NodeType.function });775    removeEdge(&graph, source, model.RelType.calls, target) catch |err| switch (err) {776        error.OutOfMemory => return err,777        Error.EdgeNotFound => {},778        else => return err,779    };780    try std.testing.expect(try addEdgeTracked(&graph, .{ .source = source, .rel = model.RelType.calls, .target = target }));781    try std.testing.expect(!try addEdgeTracked(&graph, .{ .source = source, .rel = model.RelType.calls, .target = target }));782    try removeEdge(&graph, source, model.RelType.calls, target);783    try removeNodes(&graph, &.{target});784}785786fn modelSuffixIndexBytes(nodes: []const model.Node) ?usize {787    if (nodes.len > std.math.maxInt(u32)) return null;788    var entries: usize = 0;789    for (nodes) |node| {790        if (node.name.len > std.math.maxInt(u32)) return null;791        var suffixes: usize = 0;792        for (node.name) |byte| {793            if (byte != '.') continue;794            if (suffixes == std.math.maxInt(usize)) return null;795            suffixes += 1;796        }797        if (node.name.len != 0) {798            if (suffixes == std.math.maxInt(usize)) return null;799            suffixes += 1;800        }801        if (node.name.len != 0 and node.name[node.name.len - 1] == '.') suffixes -= 1;802        if (entries > std.math.maxInt(usize) - suffixes) return null;803        entries += suffixes;804    }805    if (entries > std.math.maxInt(usize) / @sizeOf(SuffixEntry)) return null;806    return entries * @sizeOf(SuffixEntry);807}808809test "suffix index capacity matches an independent dotted-name model" {810    comptime {811        @stardustClaim(812            @import("alloc_phase").capacity.witness(SuffixIndex, "smg_suffix_index_capacity_capacity_model"),813            null,814            null,815            null,816            null,817            null,818            null,819        );820    }821    comptime {822        @stardustClaim(823            @import("alloc_phase").capacity.witness(SuffixIndex, "smg_suffix_index_capacity_overload"),824            null,825            null,826            null,827            null,828            null,829            null,830        );831    }832833    const nodes = [_]model.Node{834        .{ .name = "", .type = model.NodeType.module },835        .{ .name = "app", .type = model.NodeType.module },836        .{ .name = "app.main", .type = model.NodeType.function },837        .{ .name = "lib.util.main", .type = model.NodeType.function },838        .{ .name = "trailing.", .type = model.NodeType.module },839    };840    const limits = try suffixIndexLimits(&nodes);841    const capacity = try SuffixIndex.Capacity.derive(limits);842    try std.testing.expectEqual(modelSuffixIndexBytes(&nodes).?, capacity.bytes);843    try std.testing.expectEqual(@as(usize, 7), capacity.entries);844845    const overflow = SuffixIndex.Limits{846        .entries = std.math.maxInt(usize),847        .nodes = 0,848        .max_name_bytes = 0,849    };850    try std.testing.expectError(error.CapacityOverflow, SuffixIndex.Capacity.derive(overflow));851}852853fn checkSuffixIndexInitAllocationFailures(allocator: std.mem.Allocator) !void {854    var index = try SuffixIndex.init(allocator, .{ .entries = 8, .nodes = 3, .max_name_bytes = 32 });855    index.deinit(allocator);856}857858test "suffix index initialization cleans allocation failure and retries" {859    comptime {860        @stardustClaim(861            @import("alloc_phase").capacity.witness(SuffixIndex, "smg_suffix_index_oom"),862            null,863            null,864            null,865            null,866            null,867            null,868        );869    }870871    try std.testing.checkAllAllocationFailures(872        std.testing.allocator,873        checkSuffixIndexInitAllocationFailures,874        .{},875    );876    const nodes = [_]model.Node{.{ .name = "node", .type = model.NodeType.module }};877    var index = try SuffixIndex.init(std.testing.allocator, try suffixIndexLimits(&nodes));878    defer index.deinit(std.testing.allocator);879    index.fill(&nodes);880    index.activate();881    try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, index.phase);882}883884test "suffix index fills sorts and resolves while sealed" {885    comptime {886        @stardustClaim(887            @import("alloc_phase").capacity.witness(SuffixIndex, "smg_suffix_index_sealed_transitive_risk"),888            null,889            null,890            null,891            null,892            null,893            null,894        );895    }896    comptime {897        @stardustClaim(898            @import("alloc_phase").capacity.witness(SuffixIndex, "smg_suffix_index_sealed_foreign_risk"),899            null,900            null,901            null,902            null,903            null,904            null,905        );906    }907908    const nodes = [_]model.Node{909        .{ .name = "app.main", .type = model.NodeType.function },910        .{ .name = "lib.main", .type = model.NodeType.function },911        .{ .name = "lib.other", .type = model.NodeType.function },912    };913    var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(std.testing.allocator);914    var index = try SuffixIndex.init(915        phase_allocator.initializationAllocator(),916        try suffixIndexLimits(&nodes),917    );918    defer {919        if (phase_allocator.phase() == .initialization) phase_allocator.abortInitialization();920        if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();921        index.deinit(phase_allocator.teardownAllocator());922        phase_allocator.deinit();923    }924    const entries_pointer = index.entries.ptr;925    phase_allocator.seal();926    index.fill(&nodes);927    const main_hash = std.hash_map.hashString("main");928    for (index.entries) |*entry| {929        if (suffixEntryMatches(&nodes, entry.*, "other")) entry.hash = main_hash;930    }931    std.mem.sort(SuffixEntry, index.entries, {}, suffixEntryLess);932    index.activate();933934    var main_count: usize = 0;935    const candidates = index.hashMatches(main_hash);936    for (candidates) |entry| {937        if (suffixEntryMatches(&nodes, entry, "main")) main_count += 1;938    }939    try std.testing.expectEqual(@as(usize, 3), candidates.len);940    try std.testing.expectEqual(@as(usize, 2), main_count);941    try std.testing.expectEqual(entries_pointer, index.entries.ptr);942    try std.testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());943}944945test "suffix lookup preserves linear semantics across snapshot invalidation" {946    comptime {947        @stardustClaim(948            @import("alloc_phase").capacity.witness(SuffixIndex, "smg_suffix_index_invalidation"),949            null,950            null,951            null,952            null,953            null,954            null,955        );956    }957958    var graph = init(std.testing.allocator);959    defer deinit(&graph);960    try addNode(&graph, .{ .name = "app.main", .type = model.NodeType.function });961    try addNode(&graph, .{ .name = "lib.util.main", .type = model.NodeType.function });962    try std.testing.expect(!suffixIndexReady(graph));963    try std.testing.expectEqual(@as(usize, 2), suffixMatchCount(graph, "main"));964965    try buildSuffixIndex(&graph);966    try std.testing.expect(suffixIndexReady(graph));967    try std.testing.expectEqual(@as(usize, 2), suffixMatchCount(graph, "main"));968    try std.testing.expectEqual(@as(usize, 1), suffixMatchCount(graph, "util.main"));969    var indexed = suffixIterator(&graph, "util.main");970    const indexed_node = indexed.nextNode().?;971    try std.testing.expect(indexed_node == &graph.nodes.items[graph.node_index.get("lib.util.main").?]);972    try std.testing.expect(indexed.nextNode() == null);973974    try addNode(&graph, .{ .name = "pkg.helper", .type = model.NodeType.function });975    try std.testing.expect(!suffixIndexReady(graph));976    try std.testing.expectEqual(@as(usize, 1), suffixMatchCount(graph, "helper"));977    try buildSuffixIndex(&graph);978    try std.testing.expectEqual(@as(usize, 1), suffixMatchCount(graph, "helper"));979980    try removeNodes(&graph, &.{"app.main"});981    try std.testing.expect(!suffixIndexReady(graph));982    try std.testing.expectEqual(@as(usize, 1), suffixMatchCount(graph, "main"));983    try buildSuffixIndex(&graph);984    try std.testing.expectEqual(@as(usize, 1), suffixMatchCount(graph, "main"));985986    var deferred = init(std.testing.allocator);987    defer deinit(&deferred);988    try addNode(&deferred, .{ .name = "app.main", .type = model.NodeType.function });989    try addNode(&deferred, .{ .name = "app", .type = model.NodeType.module });990    try addEdge(&deferred, .{ .source = "app", .rel = model.RelType.contains, .target = "app.main" });991    try removeNodes(&deferred, &.{"app.main"});992    try std.testing.expect(!suffixIndexReady(deferred));993}994995test "node removal compacts storage in place" {996    var graph = init(std.testing.allocator);997    defer deinit(&graph);998    for ([_][]const u8{ "app", "app.first", "app.second", "keep" }) |name| {999        try addNode(&graph, .{ .name = name, .type = model.NodeType.function });1000    }1001    try addEdge(&graph, .{ .source = "app", .rel = model.RelType.contains, .target = "app.first" });1002    try addEdge(&graph, .{ .source = "keep", .rel = model.RelType.calls, .target = "app.second" });1003    try addEdge(&graph, .{ .source = "app", .rel = model.RelType.calls, .target = "keep" });1004    try buildSuffixIndex(&graph);10051006    const nodes_ptr = graph.nodes.items.ptr;1007    const edges_ptr = graph.edges.items.ptr;1008    const nodes_capacity = graph.nodes.capacity;1009    const edges_capacity = graph.edges.capacity;10101011    try removeNodes(&graph, &.{ "app.first", "app.second" });10121013    try std.testing.expectEqual(nodes_ptr, graph.nodes.items.ptr);1014    try std.testing.expectEqual(edges_ptr, graph.edges.items.ptr);1015    try std.testing.expectEqual(nodes_capacity, graph.nodes.capacity);1016    try std.testing.expectEqual(edges_capacity, graph.edges.capacity);1017    try std.testing.expectEqual(@as(usize, 2), graph.nodes.items.len);1018    try std.testing.expectEqual(@as(usize, 1), graph.edges.items.len);1019    try std.testing.expectEqual(@as(usize, 1), outgoingEdges(&graph, "app").len);1020    try std.testing.expectEqual(@as(usize, 1), incomingEdges(&graph, "keep").len);1021    try std.testing.expectEqualStrings("keep", graph.edges.items[graph.edge_index.get("app\x1fcalls\x1fkeep").?].target);10221023    try removeEdge(&graph, "app", model.RelType.calls, "keep");1024    try std.testing.expectEqual(@as(usize, 0), graph.edges.items.len);1025    try std.testing.expectEqual(@as(usize, 0), outgoingEdges(&graph, "app").len);1026    try std.testing.expectEqual(@as(usize, 0), incomingEdges(&graph, "keep").len);1027    try std.testing.expectEqual(edges_ptr, graph.edges.items.ptr);1028}10291030test "batch node removal rebuilds graph indexes once" {1031    var graph = init(std.testing.allocator);1032    defer deinit(&graph);1033    for ([_][]const u8{ "app", "app.first", "app.second", "keep" }) |name| {1034        try addNode(&graph, .{ .name = name, .type = model.NodeType.function });1035    }1036    try addEdge(&graph, .{ .source = "app", .rel = model.RelType.contains, .target = "app.first" });1037    try addEdge(&graph, .{ .source = "app", .rel = model.RelType.contains, .target = "app.second" });1038    try addEdge(&graph, .{ .source = "keep", .rel = model.RelType.calls, .target = "app.first" });1039    try addEdge(&graph, .{ .source = "app", .rel = model.RelType.calls, .target = "keep" });1040    try buildSuffixIndex(&graph);10411042    try removeNodes(&graph, &.{ "app.first", "app.second" });10431044    try std.testing.expectEqual(@as(usize, 2), graph.nodes.items.len);1045    try std.testing.expectEqual(@as(usize, 1), graph.edges.items.len);1046    try std.testing.expect(graph.node_index.contains("app"));1047    try std.testing.expect(graph.node_index.contains("keep"));1048    try std.testing.expect(!graph.node_index.contains("app.first"));1049    try std.testing.expect(!suffixIndexReady(graph));1050    try buildSuffixIndex(&graph);1051    try std.testing.expectEqual(@as(usize, 0), suffixMatchCount(graph, "first"));1052    try std.testing.expectEqual(@as(usize, 0), incomingEdges(&graph, "app").len);1053    try std.testing.expectEqual(@as(usize, 1), incomingEdges(&graph, "keep").len);1054    try std.testing.expectEqual(@as(usize, 1), outgoingEdges(&graph, "app").len);1055    try std.testing.expectEqual(@as(usize, 0), outgoingEdges(&graph, "keep").len);1056}

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