tiny.smg.storage.sync

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

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 edits = database.edits;9const read = database.read;10const rows = storage.rows;1112const graph_mod = smg.graph;13const model = smg.model;14const text = smg.text;1516const PlannedPut = struct {17    rowid: i64,18    index: u32,19};2021const GraphIndex = u32;2223const PlannedEdits = struct {24    node_puts: []const PlannedPut,25    node_deletes: []const i64,26    edge_puts: []const PlannedPut,27    edge_deletes: []const i64,28};2930pub const ChangeSet = struct {31    node_puts: []rows.NodePut,32    node_deletes: []i64,33    edge_puts: usize,34    edge_deletes: usize,3536    pub fn deinit(self: *ChangeSet, allocator: std.mem.Allocator) void {37        freeSlice(rows.NodePut, allocator, self.node_puts);38        freeSlice(i64, allocator, self.node_deletes);39        self.* = undefined;40    }41};4243pub const GraphPlan = struct {44    pub const Limits = struct {45        desired_nodes: usize,46        stored_nodes: usize,47        desired_edges: usize,48        stored_edges: usize,49        batch_size: usize,50    };5152    pub const Capacity = struct {53        node_order: usize,54        node_puts: usize,55        node_deletes: usize,56        edge_order: usize,57        edge_key_ptrs: usize,58        edge_puts: usize,59        edge_deletes: usize,60        seen_node_bytes: usize,61        seen_edge_bytes: usize,62        batch_node_puts: usize,63        batch_edge_puts: usize,64        batch_size: usize,65        bytes: usize,6667        pub fn derive(limits: Limits) error{ CapacityOverflow, InvalidEditBatchSize }!Capacity {68            if (limits.batch_size == 0) return error.InvalidEditBatchSize;69            if (limits.desired_nodes > std.math.maxInt(u32)) return error.CapacityOverflow;70            if (limits.desired_edges > std.math.maxInt(u32)) return error.CapacityOverflow;71            return .{72                .node_order = limits.desired_nodes,73                .node_puts = limits.desired_nodes,74                .node_deletes = limits.stored_nodes,75                .edge_order = limits.desired_edges,76                .edge_key_ptrs = limits.desired_edges,77                .edge_puts = limits.desired_edges,78                .edge_deletes = limits.stored_edges,79                .seen_node_bytes = bitmapBytes(limits.desired_nodes),80                .seen_edge_bytes = bitmapBytes(limits.desired_edges),81                .batch_node_puts = @min(limits.desired_nodes, limits.batch_size),82                .batch_edge_puts = @min(limits.desired_edges, limits.batch_size),83                .batch_size = limits.batch_size,84                .bytes = try graphPlanBytes(limits),85            };86        }87    };8889    pub const InitError = std.mem.Allocator.Error || error{ CapacityOverflow, InvalidEditBatchSize };9091    pub const claim: alloc_phase.capacity.Declaration = .{92        .source = .{93            .id = "smg.graph_diff_plan",94            .kind = .phase_static,95            .limit_source = .caller,96            .storage = .{97                .covered = &.{98                    .{99                        .id = "compact_graph_relative_node_and_edge_order_indexes_29865def4529",100                        .lifetime = .steady,101                        .detail = "compact graph-relative node and edge order indexes bounded by desired row counts",102                    },103                    .{104                        .id = "borrowed_combined_edge_key_pointers_indexed_by_the_34559d226c70",105                        .lifetime = .steady,106                        .detail = "borrowed combined-edge-key pointers indexed by the retained graph",107                    },108                    .{109                        .id = "compact_node_and_edge_put_descriptors_bounded_by_de_139e5f58f713",110                        .lifetime = .steady,111                        .detail = "compact node and edge put descriptors bounded by desired row counts",112                    },113                    .{114                        .id = "node_and_edge_delete_plans_bounded_by_stored_row_counts",115                        .lifetime = .steady,116                        .detail = "node and edge delete plans bounded by stored row counts",117                    },118                    .{119                        .id = "packed_desired_row_seen_bitmaps",120                        .lifetime = .steady,121                        .detail = "packed desired-row seen bitmaps",122                    },123                    .{124                        .id = "full_width_database_edits_bounded_by_one_commit_batch",125                        .lifetime = .steady,126                        .detail = "full-width database edits bounded by one commit batch",127                    },128                },129                .excluded = &.{130                    "retained graph models, indexes, edge keys, suffixes, and adjacency lists",131                    "SQL catalog, relation scans, database pages, and bounded row decode scratch",132                    "database write staging, pager, WAL, history, and search-index storage",133                },134            },135            .capacity = .{136                .inputs = &.{137                    alloc_phase.capacity.bindInput(Limits, "desired_nodes", "desired_nodes"),138                    alloc_phase.capacity.bindInput(Limits, "desired_edges", "desired_edges"),139                    alloc_phase.capacity.bindInput(Limits, "stored_nodes", "stored_nodes"),140                    alloc_phase.capacity.bindInput(Limits, "stored_edges", "stored_edges"),141                    alloc_phase.capacity.bindInput(Limits, "batch_size", "batch_size"),142                },143                .type_selectors = &.{144                    alloc_phase.capacity.bindType(GraphIndex, "graphindex"),145                    alloc_phase.capacity.bindType(PlannedPut, "plannedput"),146                    alloc_phase.capacity.bindType(i64, "i64"),147                    alloc_phase.capacity.bindType([*]const u8, "edge_key_pointer"),148                    alloc_phase.capacity.bindType(rows.NodePut, "node_put"),149                    alloc_phase.capacity.bindType(rows.EdgePut, "edge_put"),150                },151                .nodes = &.{152                    .{ .input = 0 },153                    .{ .input = 1 },154                    .{ .input = 2 },155                    .{ .input = 3 },156                    .{ .constant = 1 },157                    .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 0 } } },158                    .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 1 } } },159                    .{ .add = .{ .left = 5, .right = 6 } },160                    .{ .product = .{ .left = 0, .right = 7 } },161                    .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 2 } } },162                    .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 0 } } },163                    .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 3 } } },164                    .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 1 } } },165                    .{ .add = .{ .left = 10, .right = 11 } },166                    .{ .add = .{ .left = 13, .right = 12 } },167                    .{ .product = .{ .left = 1, .right = 14 } },168                    .{ .scale = .{ .node = 3, .coefficient = .{ .size_of_concrete_type = 2 } } },169                    .{ .constant = 8 },170                    .{ .ceiling_division = .{ .left = 0, .right = 17 } },171                    .{ .ceiling_division = .{ .left = 1, .right = 17 } },172                    .{ .input = 4 },173                    .{ .conditional = .{ .predicate = .{ .comparison = .less_than, .left = 0, .right = 20 }, .when_true = 0, .when_false = 20 } },174                    .{ .scale = .{ .node = 21, .coefficient = .{ .size_of_concrete_type = 4 } } },175                    .{ .conditional = .{ .predicate = .{ .comparison = .less_than, .left = 1, .right = 20 }, .when_true = 1, .when_false = 20 } },176                    .{ .scale = .{ .node = 23, .coefficient = .{ .size_of_concrete_type = 5 } } },177                    .{ .add = .{ .left = 8, .right = 9 } },178                    .{ .add = .{ .left = 25, .right = 15 } },179                    .{ .add = .{ .left = 26, .right = 16 } },180                    .{ .add = .{ .left = 27, .right = 18 } },181                    .{ .add = .{ .left = 28, .right = 19 } },182                    .{ .add = .{ .left = 29, .right = 22 } },183                    .{ .add = .{ .left = 30, .right = 24 } },184                },185                .assertions = &.{.{186                    .scope = .closure_total,187                    .measure = .retained,188                    .relation = .exact,189                    .expression = 31,190                }},191            },192            .overload = .{193                .kind = .reject_before_seal,194                .detail = "checked byte arithmetic and exact acquisitions reject overflow or OOM before the plan activates",195            },196            .risks = .{197                .transitive = .{198                    .status = .open,199                    .detail = "streaming row decode and SQL scans remain outside the fixed plan and lack a transitive allocation-closure certificate",200                },201                .foreign = .{202                    .status = .excluded,203                    .detail = "filesystem and durable database effects occur only after plan construction and are outside plan-owned storage",204                },205            },206            .obligations = &.{207                .{ .key = "smg_graph_diff_plan_capacity_capacity_model", .role = .capacity_model },208                .{ .key = "smg_graph_diff_plan_capacity_overload", .role = .overload },209                .{ .key = "smg_graph_diff_plan_oom", .role = .overload },210                .{ .key = "smg_graph_diff_plan_sealed", .role = .custom },211                .{ .key = "smg_graph_diff_plan_streaming_transitive_risk", .role = .transitive_risk },212                .{ .key = "smg_graph_diff_plan_streaming_foreign_risk", .role = .foreign_risk },213            },214        },215        .bindings = .{216            .owner = @This(),217            .seal = .{218                .family = alloc_phase.capacity.selector(@This().activate),219                .premise = .{220                    .class = .checked_semantic_fact,221                    .authority = .checker,222                },223            },224            .teardown = .{225                .family = alloc_phase.capacity.selector(@This().deinit),226                .premise = .{227                    .class = .checked_semantic_fact,228                    .authority = .checker,229                },230            },231        },232    };233234    phase: alloc_phase.capacity.Phase,235    capacity: Capacity,236    node_order: []GraphIndex,237    node_puts: []PlannedPut,238    node_deletes: []i64,239    edge_order: []GraphIndex,240    edge_key_ptrs: [][*]const u8,241    edge_puts: []PlannedPut,242    edge_deletes: []i64,243    seen_nodes: []u8,244    seen_edges: []u8,245    batch_node_puts: []rows.NodePut,246    batch_edge_puts: []rows.EdgePut,247    node_put_count: usize = 0,248    node_delete_count: usize = 0,249    edge_put_count: usize = 0,250    edge_delete_count: usize = 0,251252    pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!GraphPlan {253        const capacity = try Capacity.derive(limits);254        const node_order = try allocSlice(GraphIndex, allocator, capacity.node_order);255        errdefer freeSlice(GraphIndex, allocator, node_order);256        const node_puts = try allocSlice(PlannedPut, allocator, capacity.node_puts);257        errdefer freeSlice(PlannedPut, allocator, node_puts);258        const node_deletes = try allocSlice(i64, allocator, capacity.node_deletes);259        errdefer freeSlice(i64, allocator, node_deletes);260        const edge_order = try allocSlice(GraphIndex, allocator, capacity.edge_order);261        errdefer freeSlice(GraphIndex, allocator, edge_order);262        const edge_key_ptrs = try allocSlice([*]const u8, allocator, capacity.edge_key_ptrs);263        errdefer freeSlice([*]const u8, allocator, edge_key_ptrs);264        const edge_puts = try allocSlice(PlannedPut, allocator, capacity.edge_puts);265        errdefer freeSlice(PlannedPut, allocator, edge_puts);266        const edge_deletes = try allocSlice(i64, allocator, capacity.edge_deletes);267        errdefer freeSlice(i64, allocator, edge_deletes);268        const seen_nodes = try allocSlice(u8, allocator, capacity.seen_node_bytes);269        errdefer freeSlice(u8, allocator, seen_nodes);270        const seen_edges = try allocSlice(u8, allocator, capacity.seen_edge_bytes);271        errdefer freeSlice(u8, allocator, seen_edges);272        const batch_node_puts = try allocSlice(rows.NodePut, allocator, capacity.batch_node_puts);273        errdefer freeSlice(rows.NodePut, allocator, batch_node_puts);274        const batch_edge_puts = try allocSlice(rows.EdgePut, allocator, capacity.batch_edge_puts);275        return .{276            .phase = .initialization,277            .capacity = capacity,278            .node_order = node_order,279            .node_puts = node_puts,280            .node_deletes = node_deletes,281            .edge_order = edge_order,282            .edge_key_ptrs = edge_key_ptrs,283            .edge_puts = edge_puts,284            .edge_deletes = edge_deletes,285            .seen_nodes = seen_nodes,286            .seen_edges = seen_edges,287            .batch_node_puts = batch_node_puts,288            .batch_edge_puts = batch_edge_puts,289        };290    }291292    fn order(self: *GraphPlan, graph: graph_mod.Graph) void {293        std.debug.assert(self.phase == .initialization);294        std.debug.assert(self.node_order.len == graph.nodes.items.len);295        std.debug.assert(self.edge_order.len == graph.edges.items.len);296        std.debug.assert(self.edge_key_ptrs.len == graph.edges.items.len);297        for (self.node_order, 0..) |*entry, index| entry.* = @intCast(index);298        for (self.edge_order, 0..) |*entry, index| entry.* = @intCast(index);299        var edge_iterator = graph.edge_index.iterator();300        var edge_key_count: usize = 0;301        while (edge_iterator.next()) |entry| : (edge_key_count += 1) {302            self.edge_key_ptrs[entry.value_ptr.*] = entry.key_ptr.*.ptr;303        }304        std.debug.assert(edge_key_count == self.edge_key_ptrs.len);305        std.mem.sort(GraphIndex, self.node_order, graph.nodes.items, nodeIndexLess);306        std.mem.sort(GraphIndex, self.edge_order, EdgeSort{307            .edges = graph.edges.items,308            .key_ptrs = self.edge_key_ptrs,309            .encoded_order = encodedEdgeOrderMatchesFields(graph.edges.items),310        }, edgeIndexLess);311    }312313    pub fn activate(self: *GraphPlan) void {314        std.debug.assert(self.phase == .initialization);315        @memset(self.seen_nodes, 0);316        @memset(self.seen_edges, 0);317        self.phase = .steady;318    }319320    pub fn deinit(self: *GraphPlan, allocator: std.mem.Allocator) void {321        std.debug.assert(self.phase != .teardown);322        self.phase = .teardown;323        freeSlice(GraphIndex, allocator, self.node_order);324        freeSlice(PlannedPut, allocator, self.node_puts);325        freeSlice(i64, allocator, self.node_deletes);326        freeSlice(GraphIndex, allocator, self.edge_order);327        freeSlice([*]const u8, allocator, self.edge_key_ptrs);328        freeSlice(PlannedPut, allocator, self.edge_puts);329        freeSlice(i64, allocator, self.edge_deletes);330        freeSlice(u8, allocator, self.seen_nodes);331        freeSlice(u8, allocator, self.seen_edges);332        freeSlice(rows.NodePut, allocator, self.batch_node_puts);333        freeSlice(rows.EdgePut, allocator, self.batch_edge_puts);334        self.* = undefined;335    }336337    fn markNode(self: *GraphPlan, index: usize) bool {338        std.debug.assert(self.phase == .steady);339        std.debug.assert(index < self.node_order.len);340        return markBit(self.seen_nodes, index);341    }342343    fn markEdge(self: *GraphPlan, index: usize) bool {344        std.debug.assert(self.phase == .steady);345        std.debug.assert(index < self.edge_order.len);346        return markBit(self.seen_edges, index);347    }348349    fn nodeSeen(self: *const GraphPlan, index: usize) bool {350        std.debug.assert(self.phase == .steady);351        std.debug.assert(index < self.node_order.len);352        return bitSet(self.seen_nodes, index);353    }354355    fn edgeSeen(self: *const GraphPlan, index: usize) bool {356        std.debug.assert(self.phase == .steady);357        std.debug.assert(index < self.edge_order.len);358        return bitSet(self.seen_edges, index);359    }360361    fn putNode(self: *GraphPlan, rowid: i64, index: usize) void {362        std.debug.assert(self.phase == .steady);363        std.debug.assert(self.node_put_count < self.node_puts.len);364        std.debug.assert(index < self.node_order.len);365        self.node_puts[self.node_put_count] = .{ .rowid = rowid, .index = @intCast(index) };366        self.node_put_count += 1;367    }368369    fn deleteNode(self: *GraphPlan, rowid: i64) void {370        std.debug.assert(self.phase == .steady);371        std.debug.assert(self.node_delete_count < self.node_deletes.len);372        self.node_deletes[self.node_delete_count] = rowid;373        self.node_delete_count += 1;374    }375376    fn putEdge(self: *GraphPlan, rowid: i64, index: usize) void {377        std.debug.assert(self.phase == .steady);378        std.debug.assert(self.edge_put_count < self.edge_puts.len);379        std.debug.assert(index < self.edge_order.len);380        self.edge_puts[self.edge_put_count] = .{ .rowid = rowid, .index = @intCast(index) };381        self.edge_put_count += 1;382    }383384    fn deleteEdge(self: *GraphPlan, rowid: i64) void {385        std.debug.assert(self.phase == .steady);386        std.debug.assert(self.edge_delete_count < self.edge_deletes.len);387        self.edge_deletes[self.edge_delete_count] = rowid;388        self.edge_delete_count += 1;389    }390391    fn edits(self: *const GraphPlan) PlannedEdits {392        std.debug.assert(self.phase == .steady);393        return .{394            .node_puts = self.node_puts[0..self.node_put_count],395            .node_deletes = self.node_deletes[0..self.node_delete_count],396            .edge_puts = self.edge_puts[0..self.edge_put_count],397            .edge_deletes = self.edge_deletes[0..self.edge_delete_count],398        };399    }400401    fn materializeNodePuts(self: *GraphPlan, graph: graph_mod.Graph, planned: []const PlannedPut) []const rows.NodePut {402        std.debug.assert(self.phase == .steady);403        std.debug.assert(planned.len <= self.batch_node_puts.len);404        for (planned, 0..) |put, index| {405            self.batch_node_puts[index] = .{406                .rowid = put.rowid,407                .node = graph.nodes.items[put.index],408            };409        }410        return self.batch_node_puts[0..planned.len];411    }412413    fn materializeEdgePuts(self: *GraphPlan, graph: graph_mod.Graph, planned: []const PlannedPut) []const rows.EdgePut {414        std.debug.assert(self.phase == .steady);415        std.debug.assert(planned.len <= self.batch_edge_puts.len);416        for (planned, 0..) |put, index| {417            self.batch_edge_puts[index] = .{418                .rowid = put.rowid,419                .edge = graph.edges.items[put.index],420            };421        }422        return self.batch_edge_puts[0..planned.len];423    }424};425426comptime {427    alloc_phase.capacity.requireAllocatorExactOwnerShape(GraphPlan);428}429430pub fn beginRefresh(allocator: std.mem.Allocator, root: []const u8) !void {431    const path = try refreshPath(allocator, root);432    defer allocator.free(path);433    try text.writeFile(path, "graph refresh in progress\n");434}435436pub fn finishRefresh(allocator: std.mem.Allocator, root: []const u8) !void {437    const path = try refreshPath(allocator, root);438    defer allocator.free(path);439    sys.fs.deleteFile(path) catch |err| switch (err) {440        error.FileNotFound => {},441        else => return err,442    };443}444445pub fn refreshIncomplete(allocator: std.mem.Allocator, root: []const u8) !bool {446    const path = try refreshPath(allocator, root);447    defer allocator.free(path);448    return sys.fs.exists(path);449}450451fn refreshPath(allocator: std.mem.Allocator, root: []const u8) ![]const u8 {452    return try std.fs.path.join(allocator, &.{ root, storage.paths.smg_dir_name, storage.paths.refresh_file_name });453}454455pub fn replaceGraph(456    allocator: std.mem.Allocator,457    store_database: *database.Database,458    graph: graph_mod.Graph,459) !void {460    var changes = try replaceGraphObserved(allocator, store_database, graph);461    changes.deinit(allocator);462}463464pub fn replaceGraphObserved(465    allocator: std.mem.Allocator,466    store_database: *database.Database,467    graph: graph_mod.Graph,468) !ChangeSet {469    const stored = try read.graphCounts(store_database);470    var plan = try GraphPlan.init(allocator, .{471        .desired_nodes = graph.nodes.items.len,472        .stored_nodes = stored.nodes,473        .desired_edges = graph.edges.items.len,474        .stored_edges = stored.edges,475        .batch_size = store_database.limits.edit_batch_size,476    });477    defer plan.deinit(allocator);478    plan.order(graph);479    plan.activate();480    try fillNodeDiff(allocator, store_database, graph, &plan);481    try fillEdgeDiff(allocator, store_database, graph, &plan);482    var changes = try changeSet(allocator, graph, plan.edits());483    errdefer changes.deinit(allocator);484    _ = try applyBatches(store_database, graph, &plan);485    return changes;486}487488fn changeSet(489    allocator: std.mem.Allocator,490    graph: graph_mod.Graph,491    planned: PlannedEdits,492) !ChangeSet {493    const node_puts = try allocSlice(rows.NodePut, allocator, planned.node_puts.len);494    errdefer freeSlice(rows.NodePut, allocator, node_puts);495    for (planned.node_puts, 0..) |put, index| {496        node_puts[index] = .{497            .rowid = put.rowid,498            .node = graph.nodes.items[put.index],499        };500    }501    const node_deletes = try allocSlice(i64, allocator, planned.node_deletes.len);502    @memcpy(node_deletes, planned.node_deletes);503    return .{504        .node_puts = node_puts,505        .node_deletes = node_deletes,506        .edge_puts = planned.edge_puts.len,507        .edge_deletes = planned.edge_deletes.len,508    };509}510511fn applyBatches(512    store_database: *database.Database,513    graph: graph_mod.Graph,514    plan: *GraphPlan,515) !usize {516    const planned = plan.edits();517    var node_put_offset: usize = 0;518    var node_delete_offset: usize = 0;519    var edge_put_offset: usize = 0;520    var edge_delete_offset: usize = 0;521    var batches: usize = 0;522    while (node_put_offset < planned.node_puts.len or node_delete_offset < planned.node_deletes.len or edge_put_offset < planned.edge_puts.len or edge_delete_offset < planned.edge_deletes.len) {523        var remaining = plan.capacity.batch_size;524        const node_put_end = @min(node_put_offset + remaining, planned.node_puts.len);525        remaining -= node_put_end - node_put_offset;526        const edge_put_end = @min(edge_put_offset + remaining, planned.edge_puts.len);527        remaining -= edge_put_end - edge_put_offset;528        const edge_delete_end = @min(edge_delete_offset + remaining, planned.edge_deletes.len);529        remaining -= edge_delete_end - edge_delete_offset;530        const node_delete_end = @min(node_delete_offset + remaining, planned.node_deletes.len);531        const node_puts = plan.materializeNodePuts(graph, planned.node_puts[node_put_offset..node_put_end]);532        const edge_puts = plan.materializeEdgePuts(graph, planned.edge_puts[edge_put_offset..edge_put_end]);533        try edits.apply(store_database, .{534            .node_puts = node_puts,535            .node_deletes = planned.node_deletes[node_delete_offset..node_delete_end],536            .edge_puts = edge_puts,537            .edge_deletes = planned.edge_deletes[edge_delete_offset..edge_delete_end],538        });539        try database.commitIfDirty(store_database);540        node_put_offset = node_put_end;541        node_delete_offset = node_delete_end;542        edge_put_offset = edge_put_end;543        edge_delete_offset = edge_delete_end;544        batches += 1;545    }546    return batches;547}548549fn fillNodeDiff(550    allocator: std.mem.Allocator,551    store_database: *database.Database,552    graph: graph_mod.Graph,553    plan: *GraphPlan,554) !void {555    var handle = store_database.connection.catalog.openRelation(556        store_database.allocator,557        rows.nodes_relation,558    ) catch |err| switch (err) {559        error.RelationNotFound => return fillNewNodes(0, plan),560        else => return err,561    };562    defer handle.deinit();563    var scan: sql.TableScan = undefined;564    try handle.relation.scan(&scan, store_database.allocator, null, null);565    defer scan.deinit();566    var row_arena = std.heap.ArenaAllocator.init(allocator);567    defer row_arena.deinit();568    var max_rowid: i64 = 0;569    while (try scan.next()) |entry| {570        max_rowid = @max(max_rowid, entry.rowid);571        const name = try rows.nodeNameView(entry.bytes);572        const desired_index = graph.node_index.get(name) orelse {573            plan.deleteNode(entry.rowid);574            continue;575        };576        if (!plan.markNode(desired_index)) {577            plan.deleteNode(entry.rowid);578            continue;579        }580        _ = row_arena.reset(.retain_capacity);581        const loaded = try rows.decodeNodeRow(582            row_arena.allocator(),583            entry.rowid,584            entry.bytes,585        );586        if (!model.nodeEquals(loaded.node, graph.nodes.items[desired_index])) {587            plan.putNode(entry.rowid, desired_index);588        }589    }590    try fillNewNodes(max_rowid, plan);591}592593fn fillEdgeDiff(594    allocator: std.mem.Allocator,595    store_database: *database.Database,596    graph: graph_mod.Graph,597    plan: *GraphPlan,598) !void {599    const key_buffer = try allocSlice(u8, allocator, maxEdgeKeyLen(graph.edges.items));600    defer freeSlice(u8, allocator, key_buffer);601    var handle = store_database.connection.catalog.openRelation(602        store_database.allocator,603        rows.edges_relation,604    ) catch |err| switch (err) {605        error.RelationNotFound => return fillNewEdges(0, plan),606        else => return err,607    };608    defer handle.deinit();609    var scan: sql.TableScan = undefined;610    try handle.relation.scan(&scan, store_database.allocator, null, null);611    defer scan.deinit();612    var row_arena = std.heap.ArenaAllocator.init(allocator);613    defer row_arena.deinit();614    var max_rowid: i64 = 0;615    while (try scan.next()) |entry| {616        max_rowid = @max(max_rowid, entry.rowid);617        const desired_index = try desiredEdgeIndex(graph, entry.bytes, key_buffer);618        if (desired_index == null or !plan.markEdge(desired_index.?)) {619            plan.deleteEdge(entry.rowid);620            continue;621        }622        _ = row_arena.reset(.retain_capacity);623        const loaded = try rows.decodeEdgeRow(624            row_arena.allocator(),625            entry.rowid,626            entry.bytes,627        );628        if (!model.edgeEquals(loaded.edge, graph.edges.items[desired_index.?])) {629            plan.putEdge(entry.rowid, desired_index.?);630        }631    }632    try fillNewEdges(max_rowid, plan);633}634635fn fillNewNodes(636    max_rowid: i64,637    plan: *GraphPlan,638) !void {639    var next_rowid: ?i64 = std.math.add(i64, max_rowid, 1) catch null;640    for (plan.node_order) |order| {641        const index: usize = order;642        if (plan.nodeSeen(index)) continue;643        plan.putNode(next_rowid orelse return error.RowIdOverflow, index);644        next_rowid = std.math.add(i64, next_rowid.?, 1) catch null;645    }646}647648fn fillNewEdges(649    max_rowid: i64,650    plan: *GraphPlan,651) !void {652    var next_rowid: ?i64 = std.math.add(i64, max_rowid, 1) catch null;653    for (plan.edge_order) |order| {654        const index: usize = order;655        if (plan.edgeSeen(index)) continue;656        plan.putEdge(next_rowid orelse return error.RowIdOverflow, index);657        next_rowid = std.math.add(i64, next_rowid.?, 1) catch null;658    }659}660661fn desiredEdgeIndex(662    graph: graph_mod.Graph,663    bytes: []const u8,664    key_buffer: []u8,665) rows.Error!?usize {666    const source = try rows.edgeSourceView(bytes);667    const rel = try rows.edgeRelView(bytes);668    const target = try rows.edgeTargetView(bytes);669    const key_len = graph_mod.edgeKeyLen(source, rel, target);670    if (key_len > key_buffer.len) return null;671    const key = graph_mod.edgeKeyInto(key_buffer[0..key_len], source, rel, target);672    return graph.edge_index.get(key);673}674675fn maxEdgeKeyLen(edges: []const model.Edge) usize {676    var maximum: usize = 0;677    for (edges) |edge| {678        maximum = @max(679            maximum,680            graph_mod.edgeKeyLen(edge.source, edge.rel, edge.target),681        );682    }683    return maximum;684}685686fn nodeIndexLess(nodes: []const model.Node, left: GraphIndex, right: GraphIndex) bool {687    const order = std.mem.order(u8, nodes[left].name, nodes[right].name);688    if (order != .eq) return order == .lt;689    return left < right;690}691692const EdgeSort = struct {693    edges: []const model.Edge,694    key_ptrs: []const [*]const u8,695    encoded_order: bool,696};697698fn edgeIndexLess(context: EdgeSort, left: GraphIndex, right: GraphIndex) bool {699    const left_edge = context.edges[left];700    const right_edge = context.edges[right];701    if (!context.encoded_order) return edgeFieldIndexLess(left_edge, right_edge, left, right);702    const left_key = context.key_ptrs[left][0..graph_mod.edgeKeyLen(left_edge.source, left_edge.rel, left_edge.target)];703    const right_key = context.key_ptrs[right][0..graph_mod.edgeKeyLen(right_edge.source, right_edge.rel, right_edge.target)];704    const order = std.mem.order(u8, left_key, right_key);705    if (order != .eq) return order == .lt;706    return left < right;707}708709fn edgeFieldIndexLess(left_edge: model.Edge, right_edge: model.Edge, left: GraphIndex, right: GraphIndex) bool {710    const source = std.mem.order(u8, left_edge.source, right_edge.source);711    if (source != .eq) return source == .lt;712    const rel = std.mem.order(u8, left_edge.rel, right_edge.rel);713    if (rel != .eq) return rel == .lt;714    const target = std.mem.order(u8, left_edge.target, right_edge.target);715    if (target != .eq) return target == .lt;716    return left < right;717}718719fn encodedEdgeOrderMatchesFields(edges: []const model.Edge) bool {720    for (edges) |edge| {721        for (edge.source) |byte| if (byte <= graph_mod.edge_key_separator) return false;722        for (edge.rel) |byte| if (byte <= graph_mod.edge_key_separator) return false;723    }724    return true;725}726727fn bitmapBytes(count: usize) usize {728    return count / 8 + @intFromBool(count % 8 != 0);729}730731fn markBit(bitmap: []u8, index: usize) bool {732    const byte_index = index / 8;733    const mask = bitMask(index);734    if (bitmap[byte_index] & mask != 0) return false;735    bitmap[byte_index] |= mask;736    return true;737}738739fn bitSet(bitmap: []const u8, index: usize) bool {740    return bitmap[index / 8] & bitMask(index) != 0;741}742743fn bitMask(index: usize) u8 {744    return @as(u8, 1) << @intCast(index % 8);745}746747fn graphPlanBytes(limits: GraphPlan.Limits) error{CapacityOverflow}!usize {748    if (limits.desired_nodes > std.math.maxInt(u32)) return error.CapacityOverflow;749    if (limits.desired_edges > std.math.maxInt(u32)) return error.CapacityOverflow;750    var total: usize = 0;751    total = try addPlanBytes(total, limits.desired_nodes, @sizeOf(GraphIndex));752    total = try addPlanBytes(total, limits.desired_nodes, @sizeOf(PlannedPut));753    total = try addPlanBytes(total, limits.stored_nodes, @sizeOf(i64));754    total = try addPlanBytes(total, limits.desired_edges, @sizeOf(GraphIndex));755    total = try addPlanBytes(total, limits.desired_edges, @sizeOf([*]const u8));756    total = try addPlanBytes(total, limits.desired_edges, @sizeOf(PlannedPut));757    total = try addPlanBytes(total, limits.stored_edges, @sizeOf(i64));758    total = try addPlanBytes(total, bitmapBytes(limits.desired_nodes), @sizeOf(u8));759    total = try addPlanBytes(total, bitmapBytes(limits.desired_edges), @sizeOf(u8));760    total = try addPlanBytes(total, @min(limits.desired_nodes, limits.batch_size), @sizeOf(rows.NodePut));761    return try addPlanBytes(total, @min(limits.desired_edges, limits.batch_size), @sizeOf(rows.EdgePut));762}763764fn addPlanBytes(total: usize, count: usize, size: usize) error{CapacityOverflow}!usize {765    const bytes = std.math.mul(usize, count, size) catch return error.CapacityOverflow;766    return std.math.add(usize, total, bytes) catch error.CapacityOverflow;767}768769fn allocSlice(770    comptime T: type,771    allocator: std.mem.Allocator,772    count: usize,773) std.mem.Allocator.Error![]T {774    if (count == 0) return @constCast((&[_]T{})[0..]);775    return try allocator.alloc(T, count);776}777778fn freeSlice(comptime T: type, allocator: std.mem.Allocator, values: []T) void {779    if (values.len != 0) allocator.free(values);780}781782test "graph edits commit in bounded batches" {783    var tmp = std.testing.tmpDir(.{});784    defer tmp.cleanup();785    var opened = try database.open(std.testing.allocator, tmp.dir, smg.default_limits.storage);786    defer opened.deinit();787    var graph = graph_mod.init(std.testing.allocator);788    defer graph_mod.deinit(&graph);789    try graph_mod.addNode(&graph, .{ .name = "a", .type = model.NodeType.module });790    try graph_mod.addNode(&graph, .{ .name = "b", .type = model.NodeType.module });791    try graph_mod.addNode(&graph, .{ .name = "c", .type = model.NodeType.module });792    var plan = try GraphPlan.init(std.testing.allocator, .{793        .desired_nodes = 3,794        .stored_nodes = 0,795        .desired_edges = 0,796        .stored_edges = 0,797        .batch_size = 2,798    });799    defer plan.deinit(std.testing.allocator);800    plan.order(graph);801    plan.activate();802    plan.putNode(1, 0);803    plan.putNode(2, 1);804    plan.putNode(3, 2);805    try std.testing.expectEqual(@as(usize, 2), try applyBatches(&opened, graph, &plan));806    const loaded = try read.databaseNodes(&opened, std.testing.allocator, std.testing.allocator);807    defer rows.freeNodeRowSlice(std.testing.allocator, std.testing.allocator, loaded);808    try std.testing.expectEqual(@as(usize, 3), loaded.len);809    try std.testing.expectError(error.InvalidEditBatchSize, GraphPlan.Capacity.derive(.{810        .desired_nodes = 0,811        .stored_nodes = 0,812        .desired_edges = 0,813        .stored_edges = 0,814        .batch_size = 0,815    }));816}817818fn modelGraphPlanBytes(limits: GraphPlan.Limits) ?usize {819    if (limits.batch_size == 0) return null;820    if (limits.desired_nodes > std.math.maxInt(u32)) return null;821    if (limits.desired_edges > std.math.maxInt(u32)) return null;822    const counts = [_]usize{823        limits.desired_nodes,824        limits.desired_nodes,825        limits.stored_nodes,826        limits.desired_edges,827        limits.desired_edges,828        limits.desired_edges,829        limits.stored_edges,830        limits.desired_nodes / 8 + @intFromBool(limits.desired_nodes % 8 != 0),831        limits.desired_edges / 8 + @intFromBool(limits.desired_edges % 8 != 0),832        @min(limits.desired_nodes, limits.batch_size),833        @min(limits.desired_edges, limits.batch_size),834    };835    const sizes = [_]usize{836        @sizeOf(GraphIndex),837        @sizeOf(PlannedPut),838        @sizeOf(i64),839        @sizeOf(GraphIndex),840        @sizeOf([*]const u8),841        @sizeOf(PlannedPut),842        @sizeOf(i64),843        @sizeOf(u8),844        @sizeOf(u8),845        @sizeOf(rows.NodePut),846        @sizeOf(rows.EdgePut),847    };848    var total: usize = 0;849    for (counts, sizes) |count, size| {850        if (count > std.math.maxInt(usize) / size) return null;851        const bytes = count * size;852        if (total > std.math.maxInt(usize) - bytes) return null;853        total += bytes;854    }855    return total;856}857858test "graph diff plan capacity matches an independent typed storage model" {859    comptime {860        @stardustClaim(861            @import("alloc_phase").capacity.witness(GraphPlan, "smg_graph_diff_plan_capacity_capacity_model"),862            null,863            null,864            null,865            null,866            null,867            null,868        );869    }870    comptime {871        @stardustClaim(872            @import("alloc_phase").capacity.witness(GraphPlan, "smg_graph_diff_plan_capacity_overload"),873            null,874            null,875            null,876            null,877            null,878            null,879        );880    }881882    for (0..64) |count| {883        const limits = GraphPlan.Limits{884            .desired_nodes = count,885            .stored_nodes = count + 1,886            .desired_edges = count * 2,887            .stored_edges = count * 3,888            .batch_size = 7,889        };890        const capacity = try GraphPlan.Capacity.derive(limits);891        try std.testing.expectEqual(modelGraphPlanBytes(limits).?, capacity.bytes);892    }893    try std.testing.expect(@sizeOf(PlannedPut) < @sizeOf(rows.NodePut));894    try std.testing.expect(@sizeOf(PlannedPut) < @sizeOf(rows.EdgePut));895    try std.testing.expect(@sizeOf(GraphIndex) < @sizeOf(model.Node));896    try std.testing.expect(@sizeOf(GraphIndex) < @sizeOf(model.Edge));897    const overflow = GraphPlan.Limits{898        .desired_nodes = std.math.maxInt(usize),899        .stored_nodes = 0,900        .desired_edges = 0,901        .stored_edges = 0,902        .batch_size = 1,903    };904    try std.testing.expect(modelGraphPlanBytes(overflow) == null);905    try std.testing.expectError(906        error.CapacityOverflow,907        GraphPlan.Capacity.derive(overflow),908    );909}910911test "graph diff plan packs seen bits across byte boundaries" {912    var bitmap = [_]u8{ 0, 0 };913    try std.testing.expect(markBit(&bitmap, 0));914    try std.testing.expect(markBit(&bitmap, 8));915    try std.testing.expect(!markBit(&bitmap, 0));916    try std.testing.expect(bitSet(&bitmap, 0));917    try std.testing.expect(!bitSet(&bitmap, 7));918    try std.testing.expect(bitSet(&bitmap, 8));919}920921test "graph edge index ordering preserves field tuple semantics" {922    const edges = [_]model.Edge{923        .{ .source = "a", .rel = model.RelType.calls, .target = "z" },924        .{ .source = "a\n", .rel = model.RelType.calls, .target = "z" },925    };926    var first_key: [graph_mod.edgeKeyLen("a", model.RelType.calls, "z")]u8 = undefined;927    var second_key: [graph_mod.edgeKeyLen("a\n", model.RelType.calls, "z")]u8 = undefined;928    const first = graph_mod.edgeKeyInto(&first_key, edges[0].source, edges[0].rel, edges[0].target);929    const second = graph_mod.edgeKeyInto(&second_key, edges[1].source, edges[1].rel, edges[1].target);930    const key_ptrs = [_][*]const u8{ first.ptr, second.ptr };931    const context = EdgeSort{932        .edges = &edges,933        .key_ptrs = &key_ptrs,934        .encoded_order = encodedEdgeOrderMatchesFields(&edges),935    };936    try std.testing.expect(!context.encoded_order);937    try std.testing.expect(edgeIndexLess(context, 0, 1));938}939940fn checkGraphPlanInitAllocationFailures(allocator: std.mem.Allocator) !void {941    var plan = try GraphPlan.init(allocator, .{942        .desired_nodes = 3,943        .stored_nodes = 4,944        .desired_edges = 5,945        .stored_edges = 6,946        .batch_size = 2,947    });948    plan.deinit(allocator);949}950951test "graph diff plan initialization cleans allocation failure and retries" {952    comptime {953        @stardustClaim(954            @import("alloc_phase").capacity.witness(GraphPlan, "smg_graph_diff_plan_oom"),955            null,956            null,957            null,958            null,959            null,960            null,961        );962    }963964    try std.testing.checkAllAllocationFailures(965        std.testing.allocator,966        checkGraphPlanInitAllocationFailures,967        .{},968    );969    var graph = graph_mod.init(std.testing.allocator);970    defer graph_mod.deinit(&graph);971    try graph_mod.addNode(&graph, .{ .name = "a", .type = model.NodeType.module });972    try graph_mod.addEdge(&graph, .{ .source = "a", .target = "a", .rel = model.RelType.calls });973    var plan = try GraphPlan.init(std.testing.allocator, .{974        .desired_nodes = 1,975        .stored_nodes = 1,976        .desired_edges = 1,977        .stored_edges = 1,978        .batch_size = 1,979    });980    defer plan.deinit(std.testing.allocator);981    plan.order(graph);982    plan.activate();983    try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, plan.phase);984}985986test "graph diff plan stays sealed while filling bounded storage" {987    comptime {988        @stardustClaim(989            @import("alloc_phase").capacity.witness(GraphPlan, "smg_graph_diff_plan_sealed"),990            null,991            null,992            null,993            null,994            null,995            null,996        );997    }998999    var graph = graph_mod.init(std.testing.allocator);1000    defer graph_mod.deinit(&graph);1001    try graph_mod.addNode(&graph, .{ .name = "b", .type = model.NodeType.module });1002    try graph_mod.addNode(&graph, .{ .name = "a", .type = model.NodeType.module });1003    try graph_mod.addEdge(&graph, .{ .source = "b", .target = "a", .rel = model.RelType.calls });1004    try graph_mod.addEdge(&graph, .{ .source = "a", .target = "b", .rel = model.RelType.contains });1005    var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(1006        std.testing.allocator,1007    );1008    var plan = try GraphPlan.init(phase_allocator.initializationAllocator(), .{1009        .desired_nodes = 2,1010        .stored_nodes = 2,1011        .desired_edges = 2,1012        .stored_edges = 2,1013        .batch_size = 1,1014    });1015    defer {1016        if (phase_allocator.phase() == .initialization) {1017            phase_allocator.abortInitialization();1018        }1019        if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();1020        plan.deinit(phase_allocator.teardownAllocator());1021        phase_allocator.deinit();1022    }1023    const node_puts_pointer = plan.node_puts.ptr;1024    const edge_puts_pointer = plan.edge_puts.ptr;1025    const batch_node_puts_pointer = plan.batch_node_puts.ptr;1026    const batch_edge_puts_pointer = plan.batch_edge_puts.ptr;1027    phase_allocator.seal();1028    plan.order(graph);1029    plan.activate();1030    try std.testing.expectEqual(@as(u32, 1), plan.node_order[0]);1031    try std.testing.expectEqual(@as(u32, 0), plan.node_order[1]);1032    try std.testing.expectEqual(@as(u32, 1), plan.edge_order[0]);1033    try std.testing.expectEqual(@as(u32, 0), plan.edge_order[1]);1034    _ = plan.markNode(0);1035    _ = plan.markEdge(1);1036    plan.putNode(1, 0);1037    plan.deleteNode(2);1038    plan.putEdge(3, 1);1039    plan.deleteEdge(4);1040    const graph_edits = plan.edits();1041    try std.testing.expectEqual(@as(usize, 1), graph_edits.node_puts.len);1042    try std.testing.expectEqual(@as(usize, 1), graph_edits.edge_puts.len);1043    try std.testing.expectEqualStrings("b", plan.materializeNodePuts(graph, graph_edits.node_puts)[0].node.name);1044    try std.testing.expectEqualStrings(model.RelType.contains, plan.materializeEdgePuts(graph, graph_edits.edge_puts)[0].edge.rel);1045    try std.testing.expectEqual(node_puts_pointer, plan.node_puts.ptr);1046    try std.testing.expectEqual(edge_puts_pointer, plan.edge_puts.ptr);1047    try std.testing.expectEqual(batch_node_puts_pointer, plan.batch_node_puts.ptr);1048    try std.testing.expectEqual(batch_edge_puts_pointer, plan.batch_edge_puts.ptr);1049    try std.testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());1050}10511052test "graph replacement streams stored rows and preserves stable rowids" {1053    comptime {1054        @stardustClaim(1055            @import("alloc_phase").capacity.witness(GraphPlan, "smg_graph_diff_plan_streaming_transitive_risk"),1056            null,1057            null,1058            null,1059            null,1060            null,1061            null,1062        );1063    }1064    comptime {1065        @stardustClaim(1066            @import("alloc_phase").capacity.witness(GraphPlan, "smg_graph_diff_plan_streaming_foreign_risk"),1067            null,1068            null,1069            null,1070            null,1071            null,1072            null,1073        );1074    }10751076    var tmp = std.testing.tmpDir(.{});1077    defer tmp.cleanup();1078    var opened = try database.open(std.testing.allocator, tmp.dir, smg.default_limits.storage);1079    defer opened.deinit();1080    try edits.apply(&opened, .{1081        .node_puts = &.{1082            .{ .rowid = 5, .node = .{ .name = "a", .type = "module", .line = 1 } },1083            .{ .rowid = 8, .node = .{ .name = "a", .type = "module", .line = 2 } },1084            .{ .rowid = 9, .node = .{ .name = "orphan", .type = "module" } },1085        },1086        .edge_puts = &.{1087            .{ .rowid = 3, .edge = .{ .source = "a", .target = "b", .rel = "contains" } },1088            .{ .rowid = 4, .edge = .{ .source = "a", .target = "b", .rel = "contains" } },1089            .{ .rowid = 7, .edge = .{ .source = "orphan", .target = "a", .rel = "calls" } },1090        },1091    });1092    _ = try database.commit(&opened);10931094    var graph = graph_mod.init(std.testing.allocator);1095    defer graph_mod.deinit(&graph);1096    try graph_mod.addNode(&graph, .{ .name = "b", .type = "module" });1097    try graph_mod.addNode(&graph, .{ .name = "a", .type = "module", .line = 42 });1098    try graph_mod.addEdge(&graph, .{ .source = "b", .target = "a", .rel = "calls" });1099    try graph_mod.addEdge(&graph, .{ .source = "a", .target = "b", .rel = "contains" });1100    try replaceGraph(std.testing.allocator, &opened, graph);11011102    const loaded_nodes = try read.databaseNodes(&opened, std.testing.allocator, std.testing.allocator);1103    defer rows.freeNodeRowSlice(std.testing.allocator, std.testing.allocator, loaded_nodes);1104    const loaded_edges = try read.databaseEdges(&opened, std.testing.allocator, std.testing.allocator);1105    defer rows.freeEdgeRowSlice(std.testing.allocator, std.testing.allocator, loaded_edges);1106    try std.testing.expectEqual(@as(usize, 2), loaded_nodes.len);1107    try std.testing.expectEqual(@as(i64, 5), loaded_nodes[0].rowid);1108    try std.testing.expectEqual(@as(?i64, 42), loaded_nodes[0].node.line);1109    try std.testing.expectEqual(@as(i64, 10), loaded_nodes[1].rowid);1110    try std.testing.expectEqual(@as(usize, 2), loaded_edges.len);1111    try std.testing.expectEqual(@as(i64, 3), loaded_edges[0].rowid);1112    try std.testing.expectEqual(@as(i64, 8), loaded_edges[1].rowid);1113}