tiny.chant.ParserNodeStorage

1/// The storage divides one buffer the caller supplies into slots for up to two2/// expression nodes, one statement node and two type nodes per admitted token,3/// along with the source token and cached inferred type of each node. A caller4/// allocates one aligned buffer of `Capacity.storage_bytes`, hands it to5/// `init`, activates it, and passes it to `parse`, and every node of the6/// resulting syntax tree (the parsed translation unit) lives here. The buffer7/// belongs to the caller, and `deinit` hands it back. Each parse starts by8/// clearing the node counts, so a second parse into the same storage9/// invalidates every node pointer from the first, and `deinit` invalidates them10/// as well. A request for a node when its slots are full returns11/// `error.NodeCapacityExceeded` before anything is written. The order of use is12/// `init`, `activate`, any number of parses, then `deinit`.13pub const Storage = struct {14    phase: alloc_phase.capacity.Phase,15    capacity: capacity_mod.Capacity,16    storage: @This().Storage,17    expressions: []ast.Expr,18    statements: []ast.Stmt,19    types: []ast.Type,20    type_origins: []origin.TypeOrigin,21    expression_origins: []usize,22    expression_types: []?*const ast.Type,23    type_charges: []u8,24    admitted_tokens_len: usize,25    expression_count: usize,26    statement_count: usize,27    type_count: usize,2829    pub const storage_alignment: usize = capacity_mod.storage_alignment;30    pub const Storage = []align(storage_alignment) u8;31    pub const Limits: type = capacity_mod.Limits;32    pub const Capacity: type = capacity_mod.Capacity;33    pub const Exhaustion: type = NodeExhaustion;34    pub const InitError = capacity_mod.DeriveError || error{StorageTooShort};35    pub const work_limits: alloc_phase.capacity.WorkLimits = .{36        .transition_steps_max = std.math.maxInt(usize),37        .cleanup_steps_per_call_max = 0,38        .cleanup_calls_at_capacity_max = 0,39    };40    pub const claim: alloc_phase.capacity.Declaration = .{41        .source = .{42            .id = "chant.parser_node_storage",43            .kind = .phase_static,44            .limit_source = .caller,45            .storage = .{46                .covered = &.{47                    .{48                        .id = "at_most_two_expression_nodes_per_lexed_token",49                        .lifetime = .steady,50                        .detail = "at most two expression nodes per lexed token",51                    },52                    .{53                        .id = "at_most_one_statement_node_per_lexed_token",54                        .lifetime = .steady,55                        .detail = "at most one statement node per lexed token",56                    },57                    .{58                        .id = "at_most_two_dynamic_type_nodes_per_lexed_token",59                        .lifetime = .steady,60                        .detail = "at most two dynamic type nodes per lexed token",61                    },62                    .{63                        .id = "node_origin_inferred_type_cache_and_two_charge_toke_1bf7f8a5a1ad",64                        .lifetime = .steady,65                        .detail = "node origin, inferred-type cache, and two-charge token ledger metadata",66                    },67                },68                .excluded = &.{69                    "list and map backing bytes plus their container metadata",70                    "object bindings, scopes, and decoded token-text bytes",71                    "caller-owned lexed tokens and their borrowed source and file bytes",72                    "allocator metadata for caller acquisition and excluded parser allocations",73                    "Choir context and lowered IR storage",74                },75            },76            .capacity = .{77                .inputs = &.{78                    alloc_phase.capacity.bindInput(capacity_mod.Limits, "tokens", "tokens"),79                },80                .type_selectors = &.{81                    alloc_phase.capacity.bindType(ast.Expr, "expr"),82                    alloc_phase.capacity.bindType(ast.Stmt, "stmt"),83                    alloc_phase.capacity.bindType(ast.Type, "type"),84                    alloc_phase.capacity.bindType(origin.TypeOrigin, "typeorigin"),85                    alloc_phase.capacity.bindType(usize, "usize"),86                    alloc_phase.capacity.bindType(?*const ast.Type, "type_type"),87                    alloc_phase.capacity.bindType(u8, "u8"),88                },89                .nodes = &.{90                    .{ .input = 0 },91                    .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 2 } } },92                    .{ .scale = .{ .node = 1, .coefficient = .{ .size_of_concrete_type = 0 } } },93                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 1 } } },94                    .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 2 } } },95                    .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 2 } } },96                    .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 2 } } },97                    .{ .scale = .{ .node = 6, .coefficient = .{ .size_of_concrete_type = 3 } } },98                    .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 2 } } },99                    .{ .scale = .{ .node = 8, .coefficient = .{ .size_of_concrete_type = 4 } } },100                    .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 2 } } },101                    .{ .scale = .{ .node = 10, .coefficient = .{ .size_of_concrete_type = 5 } } },102                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 6 } } },103                    .{ .constant = 0 },104                    .{ .alignment = .{ .node = 13, .alignment = .{ .concrete_type = 0 } } },105                    .{ .add = .{ .left = 14, .right = 2 } },106                    .{ .alignment = .{ .node = 15, .alignment = .{ .concrete_type = 1 } } },107                    .{ .add = .{ .left = 16, .right = 3 } },108                    .{ .alignment = .{ .node = 17, .alignment = .{ .concrete_type = 2 } } },109                    .{ .add = .{ .left = 18, .right = 5 } },110                    .{ .alignment = .{ .node = 19, .alignment = .{ .concrete_type = 3 } } },111                    .{ .add = .{ .left = 20, .right = 7 } },112                    .{ .alignment = .{ .node = 21, .alignment = .{ .concrete_type = 4 } } },113                    .{ .add = .{ .left = 22, .right = 9 } },114                    .{ .alignment = .{ .node = 23, .alignment = .{ .concrete_type = 5 } } },115                    .{ .add = .{ .left = 24, .right = 11 } },116                    .{ .alignment = .{ .node = 25, .alignment = .{ .concrete_type = 6 } } },117                    .{ .add = .{ .left = 26, .right = 12 } },118                    .{ .alignment = .{ .node = 27, .alignment = .{ .literal = 1 } } },119                },120                .assertions = &.{.{121                    .scope = .closure_total,122                    .measure = .retained,123                    .relation = .exact,124                    .expression = 28,125                }},126            },127            .overload = .{128                .kind = .reject_before_mutation,129                .detail = "short regions and mismatched or over-limit token surveys reject before node placement",130            },131            .risks = .{132                .transitive = .{133                    .status = .witnessed,134                    .detail = "all parser node creation dispatches exhaustively into the three typed slices",135                },136                .foreign = .{137                    .status = .excluded,138                    .detail = "node placement reads borrowed memory and crosses no foreign boundary",139                },140            },141            .work = .{ .equation = "each node placement is one checked slice write bounded by lexed tokens" },142            .dependencies = &.{"chant.lexed_token_storage"},143            .obligations = &.{144                .{ .key = "chant_parser_nodes_capacity", .role = .capacity_model },145                .{ .key = "chant_parser_nodes_boundary", .role = .overload },146                .{ .key = "chant_parser_nodes_oom", .role = .custom },147                .{ .key = "chant_parser_nodes_identity", .role = .overload },148                .{ .key = "chant_parser_nodes_prepublication", .role = .overload },149                .{ .key = "chant_parser_nodes_sealed_transitive_risk", .role = .transitive_risk },150                .{ .key = "chant_parser_nodes_sealed_foreign_risk", .role = .foreign_risk },151                .{ .key = "chant_parser_nodes_sealed_work_bound", .role = .work_bound },152                .{ .key = "chant_parser_nodes_differential", .role = .transitive_risk },153                .{ .key = "chant_parser_nodes_adversarial", .role = .transitive_risk },154                .{ .key = "chant_parser_type_charge", .role = .transitive_risk },155                .{ .key = "chant_parser_type_cache", .role = .transitive_risk },156            },157        },158        .bindings = .{159            .owner = @This(),160            .seal = .{161                .family = alloc_phase.capacity.selector(@This().activate),162                .premise = .{163                    .class = .checked_semantic_fact,164                    .authority = .checker,165                },166            },167            .teardown = .{168                .family = alloc_phase.capacity.selector(@This().deinit),169                .premise = .{170                    .class = .checked_semantic_fact,171                    .authority = .checker,172                },173            },174        },175    };176177    pub const Status = struct {178        expressions: usize,179        statements: usize,180        types: usize,181    };182183    pub fn init(184        storage: @This().Storage,185        limits: capacity_mod.Limits,186    ) InitError!@This() {187        const capacity = try capacity_mod.Capacity.derive(limits);188        if (storage.len < capacity.storage_bytes) return error.StorageTooShort;189        const owned = storage[0..capacity.storage_bytes];190        return .{191            .phase = .initialization,192            .capacity = capacity,193            .storage = owned,194            .expressions = typedSlice(195                ast.Expr,196                owned,197                capacity.expressions_offset,198                capacity.expressions,199            ),200            .statements = typedSlice(201                ast.Stmt,202                owned,203                capacity.statements_offset,204                capacity.statements,205            ),206            .types = typedSlice(207                ast.Type,208                owned,209                capacity.types_offset,210                capacity.types,211            ),212            .type_origins = typedSlice(213                origin.TypeOrigin,214                owned,215                capacity.type_origins_offset,216                capacity.types,217            ),218            .expression_origins = typedSlice(219                usize,220                owned,221                capacity.expression_origins_offset,222                capacity.expressions,223            ),224            .expression_types = typedSlice(225                ?*const ast.Type,226                owned,227                capacity.expression_types_offset,228                capacity.expressions,229            ),230            .type_charges = typedSlice(231                u8,232                owned,233                capacity.type_charges_offset,234                capacity.limits.tokens,235            ),236            .admitted_tokens_len = 0,237            .expression_count = 0,238            .statement_count = 0,239            .type_count = 0,240        };241    }242243    pub fn activate(self: *@This()) void {244        std.debug.assert(self.phase == .initialization);245        self.assertStorage();246        self.phase = .steady;247    }248249    pub fn admit(250        self: *@This(),251        token_survey: Survey,252        tokens: []const Token,253    ) NodeExhaustion!void {254        std.debug.assert(self.phase == .steady);255        try requireIdentity(token_survey, tokens);256        if (token_survey.limits.tokens > self.capacity.limits.tokens) {257            return error.NodeCapacityExceeded;258        }259        @memset(self.type_charges, 0);260        self.admitted_tokens_len = tokens.len;261        self.expression_count = 0;262        self.statement_count = 0;263        self.type_count = 0;264    }265266    pub fn createExpr(self: *@This(), value: ast.Expr) PlacementExhaustion!*ast.Expr {267        return self.createExprAt(value, null);268    }269270    pub fn createExprAt(271        self: *@This(),272        value: ast.Expr,273        token_index: ?usize,274    ) PlacementExhaustion!*ast.Expr {275        std.debug.assert(self.phase == .steady);276        if (self.expression_count >= self.expressions.len) {277            return error.NodeCapacityExceeded;278        }279        if (token_index) |index| {280            if (index >= self.admitted_tokens_len) {281                return error.NodeCapacityExceeded;282            }283        }284        const result = &self.expressions[self.expression_count];285        self.expression_origins[self.expression_count] = token_index orelse286            origin.no_token;287        self.expression_types[self.expression_count] = null;288        self.expression_count += 1;289        result.* = value;290        return result;291    }292293    pub fn createStmt(self: *@This(), value: ast.Stmt) PlacementExhaustion!*ast.Stmt {294        std.debug.assert(self.phase == .steady);295        if (self.statement_count >= self.statements.len) {296            return error.NodeCapacityExceeded;297        }298        const result = &self.statements[self.statement_count];299        self.statement_count += 1;300        result.* = value;301        return result;302    }303304    pub fn createType(305        self: *@This(),306        value: ast.Type,307        placement: origin.TypePlacement,308    ) PlacementExhaustion!*ast.Type {309        std.debug.assert(self.phase == .steady);310        if (self.type_count >= self.types.len) return error.NodeCapacityExceeded;311        if (!self.validTypePlacement(placement)) {312            return error.NodeCapacityExceeded;313        }314        if (self.type_charges[placement.charged] >= 2) {315            return error.NodeCapacityExceeded;316        }317        const result = &self.types[self.type_count];318        self.type_charges[placement.charged] += 1;319        self.type_origins[self.type_count] = placement.origin;320        self.type_count += 1;321        result.* = value;322        return result;323    }324325    pub fn typeOrigin(326        self: *const @This(),327        value: *const ast.Type,328    ) ?origin.TypeOrigin {329        const index = pointerIndex(ast.Type, self.types, value) orelse return null;330        std.debug.assert(index < self.type_count);331        return self.type_origins[index];332    }333334    pub fn expressionOrigin(335        self: *const @This(),336        value: *const ast.Expr,337    ) usize {338        const index = pointerIndex(ast.Expr, self.expressions, value) orelse339            unreachable;340        std.debug.assert(index < self.expression_count);341        const token_index = self.expression_origins[index];342        std.debug.assert(token_index != origin.no_token);343        return token_index;344    }345346    pub fn inferredType(347        self: *const @This(),348        value: *const ast.Expr,349    ) ?*const ast.Type {350        const index = pointerIndex(ast.Expr, self.expressions, value) orelse351            unreachable;352        std.debug.assert(index < self.expression_count);353        return self.expression_types[index];354    }355356    pub fn setInferredType(357        self: *@This(),358        value: *const ast.Expr,359        inferred: *const ast.Type,360    ) void {361        const index = pointerIndex(ast.Expr, self.expressions, value) orelse362            unreachable;363        std.debug.assert(index < self.expression_count);364        std.debug.assert(self.expression_types[index] == null);365        self.expression_types[index] = inferred;366    }367368    pub fn status(self: *const @This()) Status {369        std.debug.assert(self.phase == .steady);370        return .{371            .expressions = self.expression_count,372            .statements = self.statement_count,373            .types = self.type_count,374        };375    }376377    pub fn deinit(self: *@This()) @This().Storage {378        std.debug.assert(self.phase == .steady);379        self.phase = .teardown;380        const storage = self.storage;381        self.* = undefined;382        return storage;383    }384385    fn assertStorage(self: *const @This()) void {386        const expected = capacity_mod.Capacity.derive(387            self.capacity.limits,388        ) catch unreachable;389        std.debug.assert(std.meta.eql(expected, self.capacity));390        std.debug.assert(self.storage.len == self.capacity.storage_bytes);391        std.debug.assert(self.expressions.len == self.capacity.expressions);392        std.debug.assert(self.statements.len == self.capacity.statements);393        std.debug.assert(self.types.len == self.capacity.types);394        std.debug.assert(self.type_origins.len == self.capacity.types);395        std.debug.assert(self.expression_origins.len == self.capacity.expressions);396        std.debug.assert(self.expression_types.len == self.capacity.expressions);397        std.debug.assert(self.type_charges.len == self.capacity.limits.tokens);398    }399400    fn validTypePlacement(401        self: *const @This(),402        placement: origin.TypePlacement,403    ) bool {404        if (placement.charged >= self.admitted_tokens_len) return false;405        if (placement.origin.primary >= self.admitted_tokens_len) return false;406        if (placement.origin.secondary != origin.no_token and407            placement.origin.secondary >= self.admitted_tokens_len)408        {409            return false;410        }411        return placement.charged == placement.origin.primary or412            placement.charged == placement.origin.secondary;413    }414};

1pub const ParserNodeStorage = parse.Storage;