lib/chant/src/parse/state/capacity.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ast = @import("../../ast/root.zig");
3 const origin = @import("origin.zig");
4
5 pub const storage_alignment: usize = @max(
6 @alignOf(ast.Expr),
7 @alignOf(ast.Stmt),
8 @alignOf(ast.Type),
9 @alignOf(origin.TypeOrigin),
10 @alignOf(usize),
11 @alignOf(?*const ast.Type),
12 );
13
14 pub const Limits = struct {
15 tokens: usize,
16 };
17
18 pub const DeriveError = error{
19 CapacityOverflow,
20 };
21
22 pub const Capacity = struct {
23 limits: Limits,
24 expressions: usize,
25 statements: usize,
26 types: usize,
27 expressions_offset: usize,
28 statements_offset: usize,
29 types_offset: usize,
30 type_origins_offset: usize,
31 expression_origins_offset: usize,
32 expression_types_offset: usize,
33 type_charges_offset: usize,
34 storage_bytes: usize,
35
36 pub fn derive(limits: Limits) DeriveError!Capacity {
37 const expressions = try twiceTokens(limits.tokens);
38 const types = try twiceTokens(limits.tokens);
39 const expression_region = try placed(ast.Expr, 0, expressions);
40 const statement_region = try placed(
41 ast.Stmt,
42 expression_region.end,
43 limits.tokens,
44 );
45 const type_region = try placed(
46 ast.Type,
47 statement_region.end,
48 types,
49 );
50 const type_origin_region = try placed(
51 origin.TypeOrigin,
52 type_region.end,
53 types,
54 );
55 const expression_origin_region = try placed(
56 usize,
57 type_origin_region.end,
58 expressions,
59 );
60 const expression_type_region = try placed(
61 ?*const ast.Type,
62 expression_origin_region.end,
63 expressions,
64 );
65 const type_charge_region = try placed(
66 u8,
67 expression_type_region.end,
68 limits.tokens,
69 );
70 return .{
71 .limits = limits,
72 .expressions = expressions,
73 .statements = limits.tokens,
74 .types = types,
75 .expressions_offset = expression_region.start,
76 .statements_offset = statement_region.start,
77 .types_offset = type_region.start,
78 .type_origins_offset = type_origin_region.start,
79 .expression_origins_offset = expression_origin_region.start,
80 .expression_types_offset = expression_type_region.start,
81 .type_charges_offset = type_charge_region.start,
82 .storage_bytes = type_charge_region.end,
83 };
84 }
85 };
86
87 fn twiceTokens(tokens: usize) DeriveError!usize {
88 return std.math.mul(usize, tokens, 2) catch
89 return error.CapacityOverflow;
90 }
91
92 const Region = struct {
93 start: usize,
94 end: usize,
95 };
96
97 fn placed(comptime T: type, offset: usize, count: usize) DeriveError!Region {
98 const alignment = std.mem.Alignment.of(T);
99 const start = alignment.forward(offset);
100 const bytes = std.math.mul(
101 usize,
102 count,
103 @sizeOf(T),
104 ) catch return error.CapacityOverflow;
105 return .{
106 .start = start,
107 .end = std.math.add(usize, start, bytes) catch
108 return error.CapacityOverflow,
109 };
110 }
111
112 fn modelCapacity(limits: Limits) DeriveError!Capacity {
113 const expressions_u128 = @as(u128, limits.tokens) * 2;
114 if (expressions_u128 > std.math.maxInt(usize)) {
115 return error.CapacityOverflow;
116 }
117 const expressions: usize = @intCast(expressions_u128);
118 const types_u128 = @as(u128, limits.tokens) * 2;
119 if (types_u128 > std.math.maxInt(usize)) {
120 return error.CapacityOverflow;
121 }
122 const types: usize = @intCast(types_u128);
123 const expression_region = try modelPlaced(ast.Expr, 0, expressions);
124 const statement_region = try modelPlaced(
125 ast.Stmt,
126 expression_region.end,
127 limits.tokens,
128 );
129 const type_region = try modelPlaced(
130 ast.Type,
131 statement_region.end,
132 types,
133 );
134 const type_origin_region = try modelPlaced(
135 origin.TypeOrigin,
136 type_region.end,
137 types,
138 );
139 const expression_origin_region = try modelPlaced(
140 usize,
141 type_origin_region.end,
142 expressions,
143 );
144 const expression_type_region = try modelPlaced(
145 ?*const ast.Type,
146 expression_origin_region.end,
147 expressions,
148 );
149 const type_charge_region = try modelPlaced(
150 u8,
151 expression_type_region.end,
152 limits.tokens,
153 );
154 return .{
155 .limits = limits,
156 .expressions = expressions,
157 .statements = limits.tokens,
158 .types = types,
159 .expressions_offset = expression_region.start,
160 .statements_offset = statement_region.start,
161 .types_offset = type_region.start,
162 .type_origins_offset = type_origin_region.start,
163 .expression_origins_offset = expression_origin_region.start,
164 .expression_types_offset = expression_type_region.start,
165 .type_charges_offset = type_charge_region.start,
166 .storage_bytes = type_charge_region.end,
167 };
168 }
169
170 fn modelPlaced(comptime T: type, offset: usize, count: usize) DeriveError!Region {
171 const alignment = @as(u128, @alignOf(T));
172 const start_u128 = (@as(u128, offset) + alignment - 1) & ~(alignment - 1);
173 const end_u128 = start_u128 + @as(u128, count) * @sizeOf(T);
174 if (end_u128 > std.math.maxInt(usize)) return error.CapacityOverflow;
175 return .{ .start = @intCast(start_u128), .end = @intCast(end_u128) };
176 }
177
178 test "parser node capacity matches an independent aligned byte model" {
179 comptime {
180 @stardustClaim(
181 @import("alloc_phase").capacity.witness(@import("./root.zig").Storage, "chant_parser_nodes_capacity"),
182 null,
183 null,
184 null,
185 null,
186 null,
187 null,
188 );
189 }
190
191 for ([_]usize{ 0, 1, 45, 193, std.math.maxInt(u16) }) |tokens| {
192 const limits = Limits{ .tokens = tokens };
193 try std.testing.expectEqual(
194 try modelCapacity(limits),
195 try Capacity.derive(limits),
196 );
197 }
198 }
199
200 test "parser node capacity rejects overflowing token limits" {
201 try std.testing.expectError(
202 error.CapacityOverflow,
203 Capacity.derive(.{ .tokens = std.math.maxInt(usize) }),
204 );
205 }
206
207 test "parser node count multiplier accepts max and rejects max plus one" {
208 const tokens_max = std.math.maxInt(usize) / 2;
209 try std.testing.expectEqual(tokens_max * 2, try twiceTokens(tokens_max));
210 try std.testing.expectError(
211 error.CapacityOverflow,
212 twiceTokens(tokens_max + 1),
213 );
214 }