tiny.smg.storage.graph

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const sql = @import("sql");4const sys = @import("sys");5const smg = @import("../root.zig");6const storage = smg.storage;7const database = storage.database;8const database_read = database.read;9const search = smg.search;10const store = storage.store;11const sync = storage.sync;12const rows = storage.rows;1314const graph_mod = smg.graph;15const model = smg.model;1617pub const Snapshot = struct {18    graph: graph_mod.Graph,19    head: sql.Hash,20};2122pub const PublishTiming = struct {23    head: sql.Hash,24    begin_ns: u64,25    graph_ns: u64,26    summary_ns: u64,27    index_ns: u64,28    index_kind: search.SyncKind,29    node_puts: usize,30    node_deletes: usize,31    edge_puts: usize,32    edge_deletes: usize,33    finish_ns: u64,3435    pub fn atomicNanoseconds(self: PublishTiming) u64 {36        return self.begin_ns +| self.finish_ns;37    }38};3940pub const Replacement = struct {41    head: sql.Hash,42    changes: sync.ChangeSet,4344    pub fn deinit(self: *Replacement, allocator: std.mem.Allocator) void {45        self.changes.deinit(allocator);46        self.* = undefined;47    }48};4950const PublishedChanges = struct {51    node_puts: []const rows.NodePut = &.{},52    node_deletes: []const i64 = &.{},53    edge_puts: usize = 0,54    edge_deletes: usize = 0,55};5657const PublishState = struct {58    previous_head: sql.Hash,59    head: sql.Hash,60    changes: PublishedChanges = .{},61    begin_ns: u64,62    graph_ns: u64,63};6465pub const LoadPlan = struct {66    pub const Limits = struct {67        nodes: usize,68        edges: usize,69    };7071    pub const Capacity = struct {72        node_rows: usize,73        edge_rows: usize,74        incoming: usize,75        outgoing: usize,76        bytes: usize,7778        pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {79            return .{80                .node_rows = limits.nodes,81                .edge_rows = limits.edges,82                .incoming = limits.nodes,83                .outgoing = limits.nodes,84                .bytes = try loadPlanBytes(limits),85            };86        }87    };8889    pub const InitError = std.mem.Allocator.Error || error{CapacityOverflow};9091    pub const claim: alloc_phase.capacity.Declaration = .{92        .source = .{93            .id = "smg.graph_load_plan",94            .kind = .phase_static,95            .limit_source = .caller,96            .storage = .{97                .covered = &.{98                    .{99                        .id = "decoded_node_and_edge_row_records_admitted_from_catalog_counts",100                        .lifetime = .initialization,101                        .detail = "decoded node and edge row records admitted from catalog counts",102                    },103                    .{104                        .id = "incoming_and_outgoing_degree_counters_admitted_from_node_count",105                        .lifetime = .initialization,106                        .detail = "incoming and outgoing degree counters admitted from node count",107                    },108                },109                .excluded = &.{110                    "decoded model strings and metadata transferred into the retained graph",111                    "graph arrays, hash indexes, adjacency entries, edge keys, and suffix index",112                    "SQL catalog, relation scan, pager, and operating-system read storage",113                },114            },115            .capacity = .{116                .inputs = &.{117                    alloc_phase.capacity.bindInput(Limits, "nodes", "nodes"),118                    alloc_phase.capacity.bindInput(Limits, "edges", "edges"),119                },120                .type_selectors = &.{121                    alloc_phase.capacity.bindType(rows.NodeRow, "node_row"),122                    alloc_phase.capacity.bindType(usize, "usize"),123                    alloc_phase.capacity.bindType(rows.EdgeRow, "edge_row"),124                },125                .nodes = &.{126                    .{ .input = 0 },127                    .{ .constant = 1 },128                    .{ .scale = .{ .node = 1, .coefficient = .{ .size_of_concrete_type = 0 } } },129                    .{ .scale = .{ .node = 1, .coefficient = .{ .size_of_concrete_type = 1 } } },130                    .{ .scale = .{ .node = 3, .coefficient = .{ .literal = 2 } } },131                    .{ .add = .{ .left = 2, .right = 4 } },132                    .{ .product = .{ .left = 0, .right = 5 } },133                    .{ .input = 1 },134                    .{ .scale = .{ .node = 7, .coefficient = .{ .size_of_concrete_type = 2 } } },135                    .{ .add = .{ .left = 6, .right = 8 } },136                },137                .assertions = &.{.{138                    .scope = .closure_total,139                    .measure = .retained,140                    .relation = .exact,141                    .expression = 9,142                }},143            },144            .overload = .{145                .kind = .reject_before_seal,146                .detail = "checked byte arithmetic and exact acquisitions reject overflow or OOM before row decoding begins",147            },148            .risks = .{149                .transitive = .{150                    .status = .open,151                    .detail = "SQL scans and model decoding use excluded allocators and lack a transitive allocation-closure certificate",152                },153                .foreign = .{154                    .status = .excluded,155                    .detail = "database and filesystem reads are outside the caller-owned load-plan slices",156                },157            },158            .obligations = &.{159                .{ .key = "smg_graph_load_plan_capacity_capacity_model", .role = .capacity_model },160                .{ .key = "smg_graph_load_plan_capacity_overload", .role = .overload },161                .{ .key = "smg_graph_load_plan_oom", .role = .overload },162                .{ .key = "smg_graph_load_plan_sealed", .role = .custom },163                .{ .key = "smg_graph_load_plan_integration_transitive_risk", .role = .transitive_risk },164                .{ .key = "smg_graph_load_plan_integration_foreign_risk", .role = .foreign_risk },165            },166        },167        .bindings = .{168            .owner = @This(),169            .seal = .{170                .family = alloc_phase.capacity.selector(@This().activate),171                .premise = .{172                    .class = .checked_semantic_fact,173                    .authority = .checker,174                },175            },176            .teardown = .{177                .family = alloc_phase.capacity.selector(@This().deinit),178                .premise = .{179                    .class = .checked_semantic_fact,180                    .authority = .checker,181                },182            },183        },184    };185186    phase: alloc_phase.capacity.Phase,187    capacity: Capacity,188    node_rows: []rows.NodeRow,189    edge_rows: []rows.EdgeRow,190    incoming: []usize,191    outgoing: []usize,192193    pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!LoadPlan {194        const capacity = try Capacity.derive(limits);195        const node_rows = try allocSlice(rows.NodeRow, allocator, capacity.node_rows);196        errdefer freeSlice(rows.NodeRow, allocator, node_rows);197        const edge_rows = try allocSlice(rows.EdgeRow, allocator, capacity.edge_rows);198        errdefer freeSlice(rows.EdgeRow, allocator, edge_rows);199        const incoming = try allocSlice(usize, allocator, capacity.incoming);200        errdefer freeSlice(usize, allocator, incoming);201        const outgoing = try allocSlice(usize, allocator, capacity.outgoing);202        return .{203            .phase = .initialization,204            .capacity = capacity,205            .node_rows = node_rows,206            .edge_rows = edge_rows,207            .incoming = incoming,208            .outgoing = outgoing,209        };210    }211212    pub fn activate(self: *LoadPlan) void {213        std.debug.assert(self.phase == .initialization);214        @memset(self.incoming, 0);215        @memset(self.outgoing, 0);216        self.phase = .steady;217    }218219    pub fn deinit(self: *LoadPlan, allocator: std.mem.Allocator) void {220        std.debug.assert(self.phase != .teardown);221        self.phase = .teardown;222        freeSlice(rows.NodeRow, allocator, self.node_rows);223        freeSlice(rows.EdgeRow, allocator, self.edge_rows);224        freeSlice(usize, allocator, self.incoming);225        freeSlice(usize, allocator, self.outgoing);226        self.* = undefined;227    }228};229230comptime {231    alloc_phase.capacity.requireAllocatorExactOwnerShape(LoadPlan);232}233234pub fn load(235    allocator: std.mem.Allocator,236    scratch: std.mem.Allocator,237    root: []const u8,238    limits: smg.StorageLimits,239) !graph_mod.Graph {240    return (try loadSnapshot(allocator, scratch, root, limits)).graph;241}242243pub fn loadSnapshot(244    allocator: std.mem.Allocator,245    scratch: std.mem.Allocator,246    root: []const u8,247    limits: smg.StorageLimits,248) !Snapshot {249    var opened = try store.openRead(scratch, root, limits);250    defer opened.close();251    return .{252        .graph = try loadRecordsFromReader(allocator, scratch, &opened.reader, true),253        .head = opened.reader.head,254    };255}256257pub fn loadFromReader(allocator: std.mem.Allocator, scratch: std.mem.Allocator, reader: *database.Reader) !graph_mod.Graph {258    return try loadRecordsFromReader(allocator, scratch, reader, true);259}260261pub fn loadNodes(262    allocator: std.mem.Allocator,263    scratch: std.mem.Allocator,264    root: []const u8,265    limits: smg.StorageLimits,266) !graph_mod.Graph {267    return try loadRecords(allocator, scratch, root, limits, false);268}269270pub fn replace(allocator: std.mem.Allocator, opened: *database.Database, graph: graph_mod.Graph) !sql.Hash {271    var replaced = try replaceObserved(allocator, opened, graph);272    defer replaced.deinit(allocator);273    return replaced.head;274}275276pub fn replaceObserved(277    allocator: std.mem.Allocator,278    opened: *database.Database,279    graph: graph_mod.Graph,280) !Replacement {281    var changes = try sync.replaceGraphObserved(allocator, opened, graph);282    errdefer changes.deinit(allocator);283    return .{284        .head = (try opened.connection.checkout()).head,285        .changes = changes,286    };287}288289pub fn publish(290    allocator: std.mem.Allocator,291    root: []const u8,292    graph: graph_mod.Graph,293    expected_head: sql.Hash,294    limits: smg.Limits,295) !void {296    _ = try publishTimed(allocator, root, graph, expected_head, limits);297}298299pub fn publishTimed(300    allocator: std.mem.Allocator,301    root: []const u8,302    graph: graph_mod.Graph,303    expected_head: sql.Hash,304    limits: smg.Limits,305) !PublishTiming {306    var started = sys.time.nanoTimestamp();307    var publisher = try store.beginPublish(allocator, root, expected_head, limits.storage);308    defer publisher.close();309    const begin_ns = elapsedNanoseconds(&started);310    var replaced = try replaceObserved(allocator, &publisher.store.database, graph);311    defer replaced.deinit(allocator);312    const graph_ns = elapsedNanoseconds(&started);313    return try finishPublishTimed(314        allocator,315        root,316        graph,317        &publisher,318        .{319            .previous_head = expected_head,320            .head = replaced.head,321            .changes = .{322                .node_puts = replaced.changes.node_puts,323                .node_deletes = replaced.changes.node_deletes,324                .edge_puts = replaced.changes.edge_puts,325                .edge_deletes = replaced.changes.edge_deletes,326            },327            .begin_ns = begin_ns,328            .graph_ns = graph_ns,329        },330        limits,331        &started,332    );333}334335pub fn publishMatchedTimed(336    allocator: std.mem.Allocator,337    root: []const u8,338    graph: graph_mod.Graph,339    expected_head: sql.Hash,340    limits: smg.Limits,341) !PublishTiming {342    var started = sys.time.nanoTimestamp();343    var publisher = try store.beginPublish(allocator, root, expected_head, limits.storage);344    defer publisher.close();345    const begin_ns = elapsedNanoseconds(&started);346    return try finishPublishTimed(347        allocator,348        root,349        graph,350        &publisher,351        .{352            .previous_head = expected_head,353            .head = expected_head,354            .begin_ns = begin_ns,355            .graph_ns = 0,356        },357        limits,358        &started,359    );360}361362fn finishPublishTimed(363    allocator: std.mem.Allocator,364    root: []const u8,365    graph: graph_mod.Graph,366    publisher: *store.Publisher,367    state: PublishState,368    limits: smg.Limits,369    started: *i128,370) !PublishTiming {371    try storage.summary.writeGraphForHead(372        allocator,373        root,374        graph,375        state.head,376    );377    const summary_ns = elapsedNanoseconds(started);378    const index_kind = try search.syncStoredFromDatabase(379        allocator,380        root,381        &publisher.store.database,382        state.previous_head,383        state.head,384        state.changes.node_puts,385        state.changes.node_deletes,386        limits.search,387    );388    const index_ns = elapsedNanoseconds(started);389    try publisher.finish();390    return .{391        .head = state.head,392        .begin_ns = state.begin_ns,393        .graph_ns = state.graph_ns,394        .summary_ns = summary_ns,395        .index_ns = index_ns,396        .index_kind = index_kind,397        .node_puts = state.changes.node_puts.len,398        .node_deletes = state.changes.node_deletes.len,399        .edge_puts = state.changes.edge_puts,400        .edge_deletes = state.changes.edge_deletes,401        .finish_ns = elapsedNanoseconds(started),402    };403}404405fn elapsedNanoseconds(started: *i128) u64 {406    const finished = sys.time.nanoTimestamp();407    std.debug.assert(finished >= started.*);408    const elapsed: u64 = @intCast(finished - started.*);409    started.* = finished;410    return elapsed;411}412413fn loadRecords(414    allocator: std.mem.Allocator,415    scratch: std.mem.Allocator,416    root: []const u8,417    limits: smg.StorageLimits,418    include_edges: bool,419) !graph_mod.Graph {420    var opened = try store.openRead(scratch, root, limits);421    defer opened.close();422    return try loadRecordsFromReader(allocator, scratch, &opened.reader, include_edges);423}424425fn loadRecordsFromReader(allocator: std.mem.Allocator, scratch: std.mem.Allocator, reader: *database.Reader, include_edges: bool) !graph_mod.Graph {426    const counts = try database_read.readerGraphCounts(reader);427    var plan = try LoadPlan.init(scratch, .{428        .nodes = counts.nodes,429        .edges = if (include_edges) counts.edges else 0,430    });431    defer plan.deinit(scratch);432    plan.activate();433    var graph = graph_mod.init(allocator);434    errdefer graph_mod.deinit(&graph);435    try graph_mod.reserveNodes(&graph, counts.nodes);436437    try database_read.readerNodesInto(reader, allocator, plan.node_rows);438    std.mem.sort(rows.NodeRow, plan.node_rows, {}, nodeRowLess);439    for (plan.node_rows) |loaded| try graph_mod.addNode(&graph, loaded.node);440    if (!include_edges) return graph;441442    try graph_mod.reserveEdges(&graph, counts.edges);443    try database_read.readerEdgesInto(reader, allocator, plan.edge_rows);444    sortEdgeRows(plan.edge_rows);445    for (plan.edge_rows) |loaded| {446        const source = graph.node_index.get(loaded.edge.source) orelse continue;447        const target = graph.node_index.get(loaded.edge.target) orelse continue;448        plan.outgoing[source] = std.math.add(usize, plan.outgoing[source], 1) catch return graph_mod.Error.CapacityOverflow;449        plan.incoming[target] = std.math.add(usize, plan.incoming[target], 1) catch return graph_mod.Error.CapacityOverflow;450    }451    try graph_mod.reserveAdjacency(&graph, plan.incoming, plan.outgoing);452    for (plan.edge_rows) |loaded| {453        var edge = loaded.edge;454        graph_mod.addEdge(&graph, edge) catch |err| {455            model.deinitEdge(&edge, allocator);456            if (err != graph_mod.Error.NodeNotFound) return err;457        };458    }459    return graph;460}461462fn loadPlanBytes(limits: LoadPlan.Limits) error{CapacityOverflow}!usize {463    var total: usize = 0;464    total = try addLoadBytes(total, limits.nodes, @sizeOf(rows.NodeRow));465    total = try addLoadBytes(total, limits.edges, @sizeOf(rows.EdgeRow));466    total = try addLoadBytes(total, limits.nodes, @sizeOf(usize));467    return try addLoadBytes(total, limits.nodes, @sizeOf(usize));468}469470fn addLoadBytes(total: usize, count: usize, size: usize) error{CapacityOverflow}!usize {471    const bytes = std.math.mul(usize, count, size) catch return error.CapacityOverflow;472    return std.math.add(usize, total, bytes) catch error.CapacityOverflow;473}474475fn allocSlice(comptime T: type, allocator: std.mem.Allocator, count: usize) std.mem.Allocator.Error![]T {476    if (count == 0) return @constCast((&[_]T{})[0..]);477    return try allocator.alloc(T, count);478}479480fn freeSlice(comptime T: type, allocator: std.mem.Allocator, values: []T) void {481    if (values.len != 0) allocator.free(values);482}483484fn sortEdgeRows(edge_rows: []rows.EdgeRow) void {485    std.mem.sort(rows.EdgeRow, edge_rows, {}, edgeRowLess);486}487488fn nodeRowLess(_: void, left: rows.NodeRow, right: rows.NodeRow) bool {489    return std.mem.lessThan(u8, left.node.name, right.node.name);490}491492fn edgeRowLess(_: void, left: rows.EdgeRow, right: rows.EdgeRow) bool {493    const source = std.mem.order(u8, left.edge.source, right.edge.source);494    if (source != .eq) return source == .lt;495    const rel = std.mem.order(u8, left.edge.rel, right.edge.rel);496    if (rel != .eq) return rel == .lt;497    return std.mem.lessThan(u8, left.edge.target, right.edge.target);498}499500test "graph save load and node-only load" {501    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);502    defer arena.deinit();503    const allocator = arena.allocator();504    const root = try testRoot(allocator, 0);505    defer sys.fs.deleteTree(root) catch {};506    try initStore(allocator, root);507    var stored = graph_mod.init(allocator);508    const meta = try model.sourcePair(allocator, "manual");509    try graph_mod.addNode(&stored, .{ .name = "a", .type = model.NodeType.module, .metadata = meta });510    try graph_mod.addNode(&stored, .{ .name = "a.f", .type = model.NodeType.function });511    try graph_mod.addEdge(&stored, .{ .source = "a", .target = "a.f", .rel = model.RelType.contains });512    _ = try replaceForTest(allocator, stored, root);513    const loaded = try load(allocator, allocator, root, smg.default_limits.storage);514    try std.testing.expect(graph_mod.getNode(&loaded, "a") != null);515    try std.testing.expectEqual(@as(usize, 1), loaded.edges.items.len);516517    const loaded_nodes = try loadNodes(allocator, allocator, root, smg.default_limits.storage);518    try std.testing.expectEqual(@as(usize, 2), loaded_nodes.nodes.items.len);519    try std.testing.expectEqual(@as(usize, 0), loaded_nodes.edges.items.len);520    try std.testing.expect(graph_mod.getNode(&loaded_nodes, "a.f") != null);521}522523test "save graph orders nodes and preserves json metadata" {524    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);525    defer arena.deinit();526    const allocator = arena.allocator();527    const root = try testRoot(allocator, 1);528    defer sys.fs.deleteTree(root) catch {};529    try initStore(allocator, root);530    var stored = graph_mod.init(allocator);531    const async_meta = try allocator.alloc(model.Pair, 1);532    async_meta[0] = .{ .key = "async", .value = "true", .json = true };533    try graph_mod.addNode(&stored, .{ .name = "z", .type = model.NodeType.module });534    try graph_mod.addNode(&stored, .{ .name = "a", .type = model.NodeType.function, .metadata = async_meta });535    try graph_mod.addEdge(&stored, .{ .source = "z", .target = "a", .rel = model.RelType.imports });536    _ = try replaceForTest(allocator, stored, root);537    const loaded = try load(allocator, allocator, root, smg.default_limits.storage);538    try std.testing.expectEqual(@as(usize, 2), loaded.nodes.items.len);539    try std.testing.expectEqualStrings("a", loaded.nodes.items[0].name);540    try std.testing.expectEqualStrings("z", loaded.nodes.items[1].name);541    try std.testing.expectEqual(@as(usize, 1), loaded.edges.items.len);542    const node = graph_mod.getNode(&loaded, "a").?;543    try std.testing.expectEqualStrings("true", model.pairValue(node.metadata, "async").?);544    try std.testing.expect(node.metadata[0].json);545}546547test "unchanged save adds no commit and changed save advances head" {548    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);549    defer arena.deinit();550    const allocator = arena.allocator();551    const root = try testRoot(allocator, 2);552    defer sys.fs.deleteTree(root) catch {};553    try initStore(allocator, root);554    var stored = graph_mod.init(allocator);555    try graph_mod.addNode(&stored, .{ .name = "a", .type = model.NodeType.module });556    try graph_mod.addNode(&stored, .{ .name = "a.f", .type = model.NodeType.function, .line = 3 });557    try graph_mod.addEdge(&stored, .{ .source = "a", .target = "a.f", .rel = model.RelType.contains });558    _ = try replaceForTest(allocator, stored, root);559    const first = try testHeadHash(allocator, root);560561    var rescanned = graph_mod.init(allocator);562    try graph_mod.addNode(&rescanned, .{ .name = "a", .type = model.NodeType.module });563    try graph_mod.addNode(&rescanned, .{ .name = "a.f", .type = model.NodeType.function, .line = 3 });564    try graph_mod.addEdge(&rescanned, .{ .source = "a", .target = "a.f", .rel = model.RelType.contains });565    _ = try replaceForTest(allocator, rescanned, root);566    const second = try testHeadHash(allocator, root);567    try std.testing.expect(std.mem.eql(u8, first[0..], second[0..]));568569    var changed = graph_mod.init(allocator);570    try graph_mod.addNode(&changed, .{ .name = "a", .type = model.NodeType.module });571    try graph_mod.addNode(&changed, .{ .name = "a.f", .type = model.NodeType.function, .line = 9 });572    try graph_mod.addEdge(&changed, .{ .source = "a", .target = "a.f", .rel = model.RelType.contains });573    _ = try replaceForTest(allocator, changed, root);574    const third = try testHeadHash(allocator, root);575    try std.testing.expect(!std.mem.eql(u8, first[0..], third[0..]));576577    const loaded = try load(allocator, allocator, root, smg.default_limits.storage);578    const node = graph_mod.getNode(&loaded, "a.f").?;579    try std.testing.expectEqual(@as(?i64, 9), node.line);580}581582test "matched publication preserves the graph and repairs summary and names" {583    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);584    defer arena.deinit();585    const allocator = arena.allocator();586    const root = try testRoot(allocator, 5);587    defer sys.fs.deleteTree(root) catch {};588    try initStore(allocator, root);589    const source = try loadSnapshot(allocator, allocator, root, smg.default_limits.storage);590    var graph = graph_mod.init(allocator);591    try graph_mod.addNode(&graph, .{ .name = "matched", .type = model.NodeType.module });592    const published = try publishTimed(allocator, root, graph, source.head, smg.default_limits);593594    const empty = graph_mod.init(allocator);595    try storage.summary.writeGraphForHead(allocator, root, empty, published.head);596    try std.testing.expectEqual(597        @as(usize, 0),598        (try storage.summary.load(allocator, root, smg.default_limits.storage)).nodes,599    );600    const summary_repair = try publishMatchedTimed(601        allocator,602        root,603        graph,604        published.head,605        smg.default_limits,606    );607    try expectMatchedPublish(published.head, summary_repair, .matched);608    try std.testing.expectEqual(609        @as(usize, 1),610        (try storage.summary.load(allocator, root, smg.default_limits.storage)).nodes,611    );612613    const wrong_head: sql.Hash = @splat(0x7f);614    {615        var opened = try store.open(allocator, root, smg.default_limits.storage);616        defer opened.close();617        try storage.names.writeForHead(allocator, root, &opened.database, wrong_head);618    }619    try std.testing.expect(!try storage.names.matchesHead(allocator, root, published.head));620    const names_repair = try publishMatchedTimed(621        allocator,622        root,623        graph,624        published.head,625        smg.default_limits,626    );627    try expectMatchedPublish(published.head, names_repair, .matched);628    try std.testing.expect(try storage.names.matchesHead(allocator, root, published.head));629    try std.testing.expectEqual(@as(usize, 1), (try load(630        allocator,631        allocator,632        root,633        smg.default_limits.storage,634    )).nodes.items.len);635}636637test "stale graph publication preserves the winning generation" {638    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);639    defer arena.deinit();640    const allocator = arena.allocator();641    const root = try testRoot(allocator, 4);642    defer sys.fs.deleteTree(root) catch {};643    try initStore(allocator, root);644645    const source = try loadSnapshot(allocator, allocator, root, smg.default_limits.storage);646    var winner = try graph_mod.clone(allocator, allocator, source.graph);647    try graph_mod.addNode(&winner, .{ .name = "winner", .type = model.NodeType.module });648    var loser = try graph_mod.clone(allocator, allocator, source.graph);649    try graph_mod.addNode(&loser, .{ .name = "loser", .type = model.NodeType.module });650651    try publish(allocator, root, winner, source.head, smg.default_limits);652    const winner_head = try testHeadHash(allocator, root);653    try std.testing.expectError(654        error.StaleSourceHead,655        publish(allocator, root, loser, source.head, smg.default_limits),656    );657    try std.testing.expectError(658        error.StaleSourceHead,659        publishMatchedTimed(allocator, root, winner, source.head, smg.default_limits),660    );661    try std.testing.expect(!try sync.refreshIncomplete(allocator, root));662    try std.testing.expect(sql.version.same(winner_head, try testHeadHash(allocator, root)));663664    const reloaded = try load(allocator, allocator, root, smg.default_limits.storage);665    try std.testing.expect(graph_mod.getNode(&reloaded, "winner") != null);666    try std.testing.expect(graph_mod.getNode(&reloaded, "loser") == null);667    try std.testing.expectEqual(668        @as(usize, 1),669        (try storage.summary.load(allocator, root, smg.default_limits.storage)).nodes,670    );671    try std.testing.expectEqual(672        @as(i64, 1),673        (try search.searchStored(674            allocator,675            root,676            "winner",677            null,678            10,679            smg.default_limits.storage,680        )).total,681    );682    try std.testing.expectEqual(683        @as(i64, 0),684        (try search.searchStored(685            allocator,686            root,687            "loser",688            null,689            10,690            smg.default_limits.storage,691        )).total,692    );693}694695fn expectMatchedPublish(696    expected_head: sql.Hash,697    timing: PublishTiming,698    index_kind: search.SyncKind,699) !void {700    try std.testing.expect(sql.version.same(expected_head, timing.head));701    try std.testing.expectEqual(@as(u64, 0), timing.graph_ns);702    try std.testing.expectEqual(index_kind, timing.index_kind);703    try std.testing.expectEqual(@as(usize, 0), timing.node_puts);704    try std.testing.expectEqual(@as(usize, 0), timing.node_deletes);705    try std.testing.expectEqual(@as(usize, 0), timing.edge_puts);706    try std.testing.expectEqual(@as(usize, 0), timing.edge_deletes);707}708709fn modelLoadPlanBytes(limits: LoadPlan.Limits) ?usize {710    const counts = [_]usize{ limits.nodes, limits.edges, limits.nodes, limits.nodes };711    const sizes = [_]usize{ @sizeOf(rows.NodeRow), @sizeOf(rows.EdgeRow), @sizeOf(usize), @sizeOf(usize) };712    var total: usize = 0;713    for (counts, sizes) |count, size| {714        if (count > std.math.maxInt(usize) / size) return null;715        const bytes = count * size;716        if (total > std.math.maxInt(usize) - bytes) return null;717        total += bytes;718    }719    return total;720}721722test "graph load plan capacity matches an independent typed storage model" {723    comptime {724        @stardustClaim(725            @import("alloc_phase").capacity.witness(LoadPlan, "smg_graph_load_plan_capacity_capacity_model"),726            null,727            null,728            null,729            null,730            null,731            null,732        );733    }734    comptime {735        @stardustClaim(736            @import("alloc_phase").capacity.witness(LoadPlan, "smg_graph_load_plan_capacity_overload"),737            null,738            null,739            null,740            null,741            null,742            null,743        );744    }745746    for (0..64) |count| {747        const limits = LoadPlan.Limits{ .nodes = count, .edges = count * 3 };748        const capacity = try LoadPlan.Capacity.derive(limits);749        try std.testing.expectEqual(modelLoadPlanBytes(limits).?, capacity.bytes);750    }751    const overflow = LoadPlan.Limits{ .nodes = std.math.maxInt(usize), .edges = 0 };752    try std.testing.expect(modelLoadPlanBytes(overflow) == null);753    try std.testing.expectError(error.CapacityOverflow, LoadPlan.Capacity.derive(overflow));754}755756fn checkLoadPlanInitAllocationFailures(allocator: std.mem.Allocator) !void {757    var plan = try LoadPlan.init(allocator, .{ .nodes = 3, .edges = 5 });758    plan.deinit(allocator);759}760761test "graph load plan initialization cleans allocation failure and retries" {762    comptime {763        @stardustClaim(764            @import("alloc_phase").capacity.witness(LoadPlan, "smg_graph_load_plan_oom"),765            null,766            null,767            null,768            null,769            null,770            null,771        );772    }773774    try std.testing.checkAllAllocationFailures(775        std.testing.allocator,776        checkLoadPlanInitAllocationFailures,777        .{},778    );779    var plan = try LoadPlan.init(std.testing.allocator, .{ .nodes = 1, .edges = 1 });780    defer plan.deinit(std.testing.allocator);781    plan.activate();782    try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, plan.phase);783}784785test "graph load plan fills admitted records and degrees while sealed" {786    comptime {787        @stardustClaim(788            @import("alloc_phase").capacity.witness(LoadPlan, "smg_graph_load_plan_sealed"),789            null,790            null,791            null,792            null,793            null,794            null,795        );796    }797798    var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(std.testing.allocator);799    var plan = try LoadPlan.init(800        phase_allocator.initializationAllocator(),801        .{ .nodes = 2, .edges = 1 },802    );803    defer {804        if (phase_allocator.phase() == .initialization) phase_allocator.abortInitialization();805        if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();806        plan.deinit(phase_allocator.teardownAllocator());807        phase_allocator.deinit();808    }809    const node_rows_pointer = plan.node_rows.ptr;810    const edge_rows_pointer = plan.edge_rows.ptr;811    phase_allocator.seal();812    plan.activate();813    plan.node_rows[0] = .{ .rowid = 1, .node = .{ .name = "a", .type = model.NodeType.module } };814    plan.edge_rows[0] = .{ .rowid = 2, .edge = .{ .source = "a", .target = "b", .rel = model.RelType.contains } };815    plan.outgoing[0] = 1;816    plan.incoming[1] = 1;817    try std.testing.expectEqual(node_rows_pointer, plan.node_rows.ptr);818    try std.testing.expectEqual(edge_rows_pointer, plan.edge_rows.ptr);819    try std.testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());820}821822test "graph load reserves stable retained containers from persisted counts and degrees" {823    comptime {824        @stardustClaim(825            @import("alloc_phase").capacity.witness(LoadPlan, "smg_graph_load_plan_integration_transitive_risk"),826            null,827            null,828            null,829            null,830            null,831            null,832        );833    }834    comptime {835        @stardustClaim(836            @import("alloc_phase").capacity.witness(LoadPlan, "smg_graph_load_plan_integration_foreign_risk"),837            null,838            null,839            null,840            null,841            null,842            null,843        );844    }845846    var arena = std.heap.ArenaAllocator.init(std.testing.allocator);847    defer arena.deinit();848    const allocator = arena.allocator();849    const root = try testRoot(allocator, 3);850    defer sys.fs.deleteTree(root) catch {};851    try initStore(allocator, root);852    var stored = graph_mod.init(allocator);853    try graph_mod.addNode(&stored, .{ .name = "a", .type = model.NodeType.module });854    try graph_mod.addNode(&stored, .{ .name = "a.f", .type = model.NodeType.function });855    try graph_mod.addEdge(&stored, .{ .source = "a", .target = "a.f", .rel = model.RelType.contains });856    _ = try replaceForTest(allocator, stored, root);857858    var scratch: std.heap.DebugAllocator(.{}) = .init;859    defer std.debug.assert(scratch.deinit() == .ok);860    const loaded = try load(861        allocator,862        scratch.allocator(),863        root,864        smg.default_limits.storage,865    );866867    try std.testing.expectEqual(@as(usize, 2), loaded.nodes.capacity);868    try std.testing.expectEqual(@as(usize, 1), loaded.edges.capacity);869    try std.testing.expectEqual(@as(usize, 2), loaded.incoming_index.capacity);870    try std.testing.expectEqual(@as(usize, 2), loaded.outgoing_index.capacity);871    try std.testing.expectEqual(@as(usize, 0), loaded.incoming_index.items[0].capacity);872    try std.testing.expectEqual(@as(usize, 1), loaded.outgoing_index.items[0].capacity);873    try std.testing.expectEqual(@as(usize, 1), loaded.incoming_index.items[1].capacity);874    try std.testing.expectEqual(@as(usize, 0), loaded.outgoing_index.items[1].capacity);875}876877fn initStore(allocator: std.mem.Allocator, root: []const u8) !void {878    try sys.fs.createDirPath(root);879    var opened = try store.open(allocator, root, smg.default_limits.storage);880    opened.close();881}882883fn replaceForTest(allocator: std.mem.Allocator, graph: graph_mod.Graph, root: []const u8) !sql.Hash {884    var opened = try store.open(allocator, root, smg.default_limits.storage);885    defer opened.close();886    return try replace(allocator, &opened.database, graph);887}888889fn testHeadHash(allocator: std.mem.Allocator, root: []const u8) !sql.Hash {890    var opened = try store.open(allocator, root, smg.default_limits.storage);891    defer opened.close();892    return (try opened.database.connection.checkout()).head;893}894895fn testRoot(allocator: std.mem.Allocator, offset: i64) ![]const u8 {896    return try std.fmt.allocPrint(allocator, "/tmp/smg-storage-graph-test-{x}", .{@as(u64, @intCast(@max(0, sys.time.realMilliTimestamp() + offset)))});897}

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