tiny.smg.SuffixIndex

1pub const SuffixIndex = struct {2    pub const Limits = struct {3        entries: usize,4        nodes: usize,5        max_name_bytes: usize,6    };78    pub const Capacity = struct {9        entries: usize,10        nodes: usize,11        max_name_bytes: usize,12        bytes: usize,1314        pub fn derive(limits: Limits) error{CapacityOverflow}!Capacity {15            if (limits.nodes > std.math.maxInt(u32)) return error.CapacityOverflow;16            if (limits.max_name_bytes > std.math.maxInt(u32)) return error.CapacityOverflow;17            return .{18                .entries = limits.entries,19                .nodes = limits.nodes,20                .max_name_bytes = limits.max_name_bytes,21                .bytes = std.math.mul(usize, limits.entries, @sizeOf(SuffixEntry)) catch return error.CapacityOverflow,22            };23        }24    };2526    pub const InitError = std.mem.Allocator.Error || error{CapacityOverflow};2728    pub const claim: alloc_phase.capacity.Declaration = .{29        .source = .{30            .id = "smg.suffix_index",31            .kind = .phase_static,32            .limit_source = .caller,33            .storage = .{34                .covered = &.{35                    .{36                        .id = "one_compact_hash_node_and_suffix_start_record_per_d_8a2d437489ef",37                        .lifetime = .steady,38                        .detail = "one compact hash, node, and suffix-start record per dotted-name suffix",39                    },40                },41                .excluded = &.{42                    "graph nodes and decoded name storage referenced by index records",43                    "caller-owned resolution result arrays",44                    "linear fallback after graph mutation invalidates the snapshot",45                },46            },47            .capacity = .{48                .inputs = &.{49                    alloc_phase.capacity.bindInput(Limits, "entries", "entries"),50                    alloc_phase.capacity.bindInput(Limits, "max_name_bytes", "max_name_bytes"),51                    alloc_phase.capacity.bindInput(Limits, "nodes", "nodes"),52                },53                .type_selectors = &.{},54                .nodes = &.{55                    .{ .input = 0 },56                    .{ .input = 1 },57                    .{ .input = 2 },58                    .{ .add = .{ .left = 0, .right = 1 } },59                    .{ .add = .{ .left = 3, .right = 2 } },60                },61                .assertions = &.{.{62                    .scope = .closure_total,63                    .measure = .retained,64                    .relation = .upper_bound,65                    .expression = 4,66                }},67            },68            .overload = .{69                .kind = .reject_before_seal,70                .detail = "checked entry and byte counts plus u32 node and name bounds reject overflow or OOM before activation",71            },72            .risks = .{73                .transitive = .{74                    .status = .open,75                    .detail = "standard hash and sort helpers are allocation-free in the witness but lack a transitive allocation-closure certificate",76                },77                .foreign = .{78                    .status = .excluded,79                    .detail = "the index is process-local caller-owned memory with no operating-system or callback edge",80                },81            },82            .obligations = &.{83                .{ .key = "smg_suffix_index_capacity_capacity_model", .role = .capacity_model },84                .{ .key = "smg_suffix_index_capacity_overload", .role = .overload },85                .{ .key = "smg_suffix_index_oom", .role = .overload },86                .{ .key = "smg_suffix_index_sealed_transitive_risk", .role = .transitive_risk },87                .{ .key = "smg_suffix_index_sealed_foreign_risk", .role = .foreign_risk },88                .{ .key = "smg_suffix_index_invalidation", .role = .custom },89            },90        },91        .bindings = .{92            .owner = @This(),93            .seal = .{94                .family = alloc_phase.capacity.selector(@This().activate),95                .premise = .{96                    .class = .checked_semantic_fact,97                    .authority = .checker,98                },99            },100            .teardown = .{101                .family = alloc_phase.capacity.selector(@This().deinit),102                .premise = .{103                    .class = .checked_semantic_fact,104                    .authority = .checker,105                },106            },107        },108    };109110    phase: alloc_phase.capacity.Phase,111    capacity: Capacity,112    entries: []SuffixEntry,113114    pub fn init(allocator: std.mem.Allocator, limits: Limits) InitError!SuffixIndex {115        const capacity = try Capacity.derive(limits);116        const entries = if (capacity.entries == 0)117            @constCast((&[_]SuffixEntry{})[0..])118        else119            try allocator.alloc(SuffixEntry, capacity.entries);120        return .{121            .phase = .initialization,122            .capacity = capacity,123            .entries = entries,124        };125    }126127    pub fn fill(self: *SuffixIndex, nodes: []const model.Node) void {128        std.debug.assert(self.phase == .initialization);129        std.debug.assert(nodes.len == self.capacity.nodes);130        var filled: usize = 0;131        for (nodes, 0..) |node, node_index| {132            std.debug.assert(node.name.len <= self.capacity.max_name_bytes);133            var start: usize = 0;134            while (start < node.name.len) {135                std.debug.assert(filled < self.entries.len);136                self.entries[filled] = .{137                    .hash = std.hash_map.hashString(node.name[start..]),138                    .node = @intCast(node_index),139                    .start = @intCast(start),140                };141                filled += 1;142                const dot = std.mem.indexOfScalar(u8, node.name[start..], '.') orelse break;143                start += dot + 1;144            }145        }146        std.debug.assert(filled == self.entries.len);147        std.mem.sort(SuffixEntry, self.entries, {}, suffixEntryLess);148    }149150    pub fn activate(self: *SuffixIndex) void {151        std.debug.assert(self.phase == .initialization);152        self.phase = .steady;153    }154155    pub fn deinit(self: *SuffixIndex, allocator: std.mem.Allocator) void {156        std.debug.assert(self.phase != .teardown);157        self.phase = .teardown;158        if (self.entries.len != 0) allocator.free(self.entries);159        self.* = undefined;160    }161162    pub fn hashMatches(self: *const SuffixIndex, hash: u64) []const SuffixEntry {163        std.debug.assert(self.phase == .steady);164        const start = suffixHashLowerBound(self.entries, hash);165        const end = suffixHashUpperBound(self.entries[start..], hash) + start;166        return self.entries[start..end];167    }168};

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