lib/chant/src/lexer/stream.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const chant = @import("../root.zig");
4 const capacity_mod = @import("capacity.zig");
5 const scan = @import("scan.zig");
6 const state = @import("state.zig");
7
8 const Token = chant.token.Token;
9 const StreamExhaustion = error{
10 TokenCapacityExceeded,
11 SurveySourceMismatch,
12 };
13
14 /// The result of a counting pass (survey) over one source: how many tokens the
15 /// source holds, counting the end-of-file token, and the address and length of
16 /// both the source text and the file name. A caller gets one from `survey` and
17 /// passes it to `Storage.fill`. `fill` compares those addresses and lengths
18 /// with the slices it is given and returns `error.SurveySourceMismatch` when
19 /// any of them differs. The caller owns the source and file-name bytes and
20 /// keeps them at the same address and unchanged from the survey through the
21 /// last use of the tokens, because the check reads addresses and lengths and no
22 /// bytes.
23 pub const Survey = struct {
24 source_ptr: [*]const u8,
25 source_len: usize,
26 file_ptr: [*]const u8,
27 file_len: usize,
28 limits: Limits,
29 };
30
31 pub const Exhaustion = StreamExhaustion;
32
33 pub const Storage = struct {
34 phase: alloc_phase.capacity.Phase,
35 capacity: capacity_mod.Capacity,
36 storage: @This().Storage,
37 tokens: []Token,
38
39 pub const storage_alignment: usize = capacity_mod.storage_alignment;
40 pub const Storage = []align(storage_alignment) u8;
41 pub const Limits: type = capacity_mod.Limits;
42 pub const Capacity: type = capacity_mod.Capacity;
43 pub const Exhaustion: type = StreamExhaustion;
44 pub const InitError = capacity_mod.DeriveError || error{StorageTooShort};
45 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
46 .transition_steps_max = std.math.maxInt(usize),
47 .cleanup_steps_per_call_max = 0,
48 .cleanup_calls_at_capacity_max = 0,
49 };
50 pub const claim: alloc_phase.capacity.Declaration = .{
51 .source = .{
52 .id = "chant.lexed_token_storage",
53 .kind = .phase_static,
54 .limit_source = .caller,
55 .storage = .{
56 .covered = &.{
57 .{
58 .id = "exact_surveyed_lexed_token_sequence_including_eof",
59 .lifetime = .steady,
60 .detail = "exact surveyed lexed token sequence including EOF",
61 },
62 },
63 .excluded = &.{
64 "caller-owned stable source and file-name bytes borrowed by the survey and tokens",
65 "consumer-owned AST and diagnostic retention",
66 },
67 },
68 .capacity = .{
69 .inputs = &.{
70 alloc_phase.capacity.bindInput(capacity_mod.Limits, "tokens", "tokens"),
71 },
72 .type_selectors = &.{
73 alloc_phase.capacity.bindType(Token, "token"),
74 },
75 .nodes = &.{
76 .{ .input = 0 },
77 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
78 },
79 .assertions = &.{.{
80 .scope = .closure_total,
81 .measure = .retained,
82 .relation = .exact,
83 .expression = 1,
84 }},
85 },
86 .overload = .{
87 .kind = .reject_before_mutation,
88 .detail = "short storage and mismatched surveys reject before token placement",
89 },
90 .risks = .{
91 .transitive = .{
92 .status = .witnessed,
93 .detail = "survey and fill call only the allocator-free lexer scanner",
94 },
95 .foreign = .{
96 .status = .excluded,
97 .detail = "lexing reads borrowed memory and crosses no foreign boundary",
98 },
99 },
100 .work = .{ .equation = "survey and fill each take at most source bytes plus one lexer transition" },
101 .obligations = &.{
102 .{ .key = "chant_lexed_tokens_capacity", .role = .capacity_model },
103 .{ .key = "chant_lexed_tokens_boundary", .role = .overload },
104 .{ .key = "chant_lexed_tokens_oom", .role = .custom },
105 .{ .key = "chant_lexed_tokens_identity", .role = .overload },
106 .{ .key = "chant_lexed_tokens_sealed_transitive_risk", .role = .transitive_risk },
107 .{ .key = "chant_lexed_tokens_sealed_foreign_risk", .role = .foreign_risk },
108 .{ .key = "chant_lexed_tokens_differential", .role = .work_bound },
109 },
110 },
111 .bindings = .{
112 .owner = @This(),
113 .seal = .{
114 .family = alloc_phase.capacity.selector(@This().activate),
115 .premise = .{
116 .class = .checked_semantic_fact,
117 .authority = .checker,
118 },
119 },
120 .teardown = .{
121 .family = alloc_phase.capacity.selector(@This().deinit),
122 .premise = .{
123 .class = .checked_semantic_fact,
124 .authority = .checker,
125 },
126 },
127 },
128 };
129
130 pub fn init(
131 storage: @This().Storage,
132 limits: capacity_mod.Limits,
133 ) InitError!@This() {
134 const capacity = try capacity_mod.Capacity.derive(limits);
135 if (storage.len < capacity.storage_bytes) return error.StorageTooShort;
136 const owned = storage[0..capacity.storage_bytes];
137 return .{
138 .phase = .initialization,
139 .capacity = capacity,
140 .storage = owned,
141 .tokens = typedTokens(owned, limits.tokens),
142 };
143 }
144
145 pub fn activate(self: *@This()) void {
146 std.debug.assert(self.phase == .initialization);
147 std.debug.assert(self.storage.len == self.capacity.storage_bytes);
148 std.debug.assert(self.tokens.len == self.capacity.limits.tokens);
149 self.phase = .steady;
150 }
151
152 pub fn fill(
153 self: *@This(),
154 token_survey: Survey,
155 source: []const u8,
156 file: []const u8,
157 ) (chant.lexer.Error || StreamExhaustion)![]const Token {
158 std.debug.assert(self.phase == .steady);
159 try requireIdentity(token_survey, source, file);
160 if (token_survey.limits.tokens > self.tokens.len) {
161 return error.TokenCapacityExceeded;
162 }
163
164 var lexer = state.Lexer.init(source, file);
165 var index: usize = 0;
166 while (index < token_survey.limits.tokens) : (index += 1) {
167 const tok = try scan.next(&lexer);
168 self.tokens[index] = tok;
169 if (tok.kind == .eof) {
170 const token_count = index + 1;
171 if (token_count != token_survey.limits.tokens) unreachable;
172 return self.tokens[0..token_count];
173 }
174 }
175 unreachable;
176 }
177
178 pub fn deinit(self: *@This()) @This().Storage {
179 std.debug.assert(self.phase == .steady);
180 self.phase = .teardown;
181 const storage = self.storage;
182 self.* = undefined;
183 return storage;
184 }
185 };
186
187 pub const Limits = capacity_mod.Limits;
188 pub const Capacity = capacity_mod.Capacity;
189 pub const CapacityError = capacity_mod.DeriveError;
190
191 pub fn survey(
192 source: []const u8,
193 file: []const u8,
194 ) (chant.lexer.Error || Exhaustion)!Survey {
195 var lexer = state.Lexer.init(source, file);
196 var token_count: usize = 0;
197 while (true) {
198 const tok = try scan.next(&lexer);
199 token_count = std.math.add(usize, token_count, 1) catch
200 return error.TokenCapacityExceeded;
201 if (tok.kind == .eof) break;
202 }
203 return .{
204 .source_ptr = source.ptr,
205 .source_len = source.len,
206 .file_ptr = file.ptr,
207 .file_len = file.len,
208 .limits = .{ .tokens = token_count },
209 };
210 }
211
212 fn typedTokens(bytes: Storage.Storage, count: usize) []Token {
213 const region: []align(@alignOf(Token)) u8 = @alignCast(bytes);
214 return std.mem.bytesAsSlice(Token, region)[0..count];
215 }
216
217 fn requireIdentity(surveyed: Survey, source: []const u8, file: []const u8) Exhaustion!void {
218 if (surveyed.source_ptr != source.ptr) return error.SurveySourceMismatch;
219 if (surveyed.source_len != source.len) return error.SurveySourceMismatch;
220 if (surveyed.file_ptr != file.ptr) return error.SurveySourceMismatch;
221 if (surveyed.file_len != file.len) return error.SurveySourceMismatch;
222 }
223
224 fn initFailures(allocator: std.mem.Allocator) !void {
225 const source = "int value = 42;";
226 const token_survey = try survey(source, "oom.c");
227 const capacity = try Capacity.derive(token_survey.limits);
228 const bytes = try allocator.alignedAlloc(
229 u8,
230 .fromByteUnits(Storage.storage_alignment),
231 capacity.storage_bytes,
232 );
233 defer allocator.free(bytes);
234 var storage = try Storage.init(bytes, token_survey.limits);
235 storage.activate();
236 _ = try storage.fill(token_survey, source, "oom.c");
237 _ = storage.deinit();
238 }
239
240 test "token storage acquisition retries after allocation failure" {
241 comptime {
242 @stardustClaim(
243 @import("alloc_phase").capacity.witness(Storage, "chant_lexed_tokens_oom"),
244 null,
245 null,
246 null,
247 null,
248 null,
249 null,
250 );
251 }
252
253 try std.testing.checkAllAllocationFailures(std.testing.allocator, initFailures, .{});
254 }
255
256 test "token storage accepts max and rejects max plus one before mutation" {
257 comptime {
258 @stardustClaim(
259 @import("alloc_phase").capacity.witness(Storage, "chant_lexed_tokens_boundary"),
260 null,
261 null,
262 null,
263 null,
264 null,
265 null,
266 );
267 }
268
269 const source = "int value;";
270 const token_survey = try survey(source, "boundary.c");
271 const capacity = try Capacity.derive(token_survey.limits);
272 var bytes: [8 * @sizeOf(Token)]u8 align(Storage.storage_alignment) = undefined;
273 try std.testing.expect(capacity.storage_bytes <= bytes.len);
274
275 var exact = try Storage.init(bytes[0..capacity.storage_bytes], token_survey.limits);
276 exact.activate();
277 const tokens = try exact.fill(token_survey, source, "boundary.c");
278 try std.testing.expectEqual(token_survey.limits.tokens, tokens.len);
279 try std.testing.expectEqual(chant.token.Kind.eof, tokens[tokens.len - 1].kind);
280 _ = exact.deinit();
281
282 if (capacity.storage_bytes > 0) {
283 try std.testing.expectError(
284 error.StorageTooShort,
285 Storage.init(bytes[0 .. capacity.storage_bytes - 1], token_survey.limits),
286 );
287 }
288 var smaller = try Storage.init(bytes[0 .. capacity.storage_bytes - @sizeOf(Token)], .{
289 .tokens = token_survey.limits.tokens - 1,
290 });
291 smaller.activate();
292 const sentinel: u8 = 0xa7;
293 @memset(smaller.storage, sentinel);
294 try std.testing.expectError(
295 error.TokenCapacityExceeded,
296 smaller.fill(token_survey, source, "boundary.c"),
297 );
298 for (smaller.storage) |byte| try std.testing.expectEqual(sentinel, byte);
299 _ = smaller.deinit();
300 }
301
302 test "zero token capacity owns no bytes and rejects the first token" {
303 const empty = try Capacity.derive(.{ .tokens = 0 });
304 try std.testing.expectEqual(@as(usize, 0), empty.storage_bytes);
305 var bytes: [0]u8 align(Storage.storage_alignment) = .{};
306 var storage = try Storage.init(&bytes, .{ .tokens = 0 });
307 storage.activate();
308 const token_survey = try survey("", "zero.c");
309 try std.testing.expectEqual(@as(usize, 1), token_survey.limits.tokens);
310 try std.testing.expectError(
311 error.TokenCapacityExceeded,
312 storage.fill(token_survey, "", "zero.c"),
313 );
314 const returned = storage.deinit();
315 try std.testing.expectEqual(@as(usize, 0), returned.len);
316 }
317
318 test "token fill requires the surveyed source identity" {
319 comptime {
320 @stardustClaim(
321 @import("alloc_phase").capacity.witness(Storage, "chant_lexed_tokens_identity"),
322 null,
323 null,
324 null,
325 null,
326 null,
327 null,
328 );
329 }
330
331 const source = [_]u8{ 'i', 'n', 't' };
332 const file = [_]u8{ 'i', 'd', 'e', 'n', 't', 'i', 't', 'y', '.', 'c' };
333 const token_survey = try survey(&source, &file);
334 const capacity = try Capacity.derive(token_survey.limits);
335 var bytes: [2 * @sizeOf(Token)]u8 align(Storage.storage_alignment) = undefined;
336 try std.testing.expectEqual(bytes.len, capacity.storage_bytes);
337 var storage = try Storage.init(&bytes, token_survey.limits);
338 storage.activate();
339 @memset(storage.storage, 0x5c);
340
341 var other_source = source;
342 std.mem.doNotOptimizeAway(&other_source);
343 try std.testing.expect(@intFromPtr(&source) != @intFromPtr(&other_source));
344 try std.testing.expectError(
345 error.SurveySourceMismatch,
346 storage.fill(token_survey, &other_source, &file),
347 );
348 for (storage.storage) |byte| try std.testing.expectEqual(@as(u8, 0x5c), byte);
349 var other_file = file;
350 std.mem.doNotOptimizeAway(&other_file);
351 try std.testing.expect(@intFromPtr(&file) != @intFromPtr(&other_file));
352 try std.testing.expectError(
353 error.SurveySourceMismatch,
354 storage.fill(token_survey, &source, &other_file),
355 );
356 _ = storage.deinit();
357 }
358
359 test "activated token storage fills cold without allocation" {
360 comptime {
361 @stardustClaim(
362 @import("alloc_phase").capacity.witness(Storage, "chant_lexed_tokens_sealed_transitive_risk"),
363 null,
364 null,
365 null,
366 null,
367 null,
368 null,
369 );
370 }
371 comptime {
372 @stardustClaim(
373 @import("alloc_phase").capacity.witness(Storage, "chant_lexed_tokens_sealed_foreign_risk"),
374 null,
375 null,
376 null,
377 null,
378 null,
379 null,
380 );
381 }
382
383 const source = "int value = 42;";
384 const token_survey = try survey(source, "sealed.c");
385 const capacity = try Capacity.derive(token_survey.limits);
386 var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{});
387 const bytes = try counting.allocator().alignedAlloc(
388 u8,
389 .fromByteUnits(Storage.storage_alignment),
390 capacity.storage_bytes,
391 );
392 defer counting.allocator().free(bytes);
393 var storage = try Storage.init(bytes, token_survey.limits);
394 storage.activate();
395 const pointer = @intFromPtr(storage.tokens.ptr);
396 const token_capacity = storage.tokens.len;
397 const allocations = counting.alloc_index;
398
399 const first = try storage.fill(token_survey, source, "sealed.c");
400 const second = try storage.fill(token_survey, source, "sealed.c");
401 try std.testing.expectEqual(allocations, counting.alloc_index);
402 try std.testing.expectEqual(pointer, @intFromPtr(first.ptr));
403 try std.testing.expectEqual(pointer, @intFromPtr(second.ptr));
404 try std.testing.expectEqual(token_capacity, storage.tokens.len);
405 const returned = storage.deinit();
406 try std.testing.expectEqual(@intFromPtr(bytes.ptr), @intFromPtr(returned.ptr));
407 try std.testing.expectEqual(bytes.len, returned.len);
408 }
409
410 test "token survey and fill match direct lexing" {
411 comptime {
412 @stardustClaim(
413 @import("alloc_phase").capacity.witness(Storage, "chant_lexed_tokens_differential"),
414 null,
415 null,
416 null,
417 null,
418 null,
419 null,
420 );
421 }
422
423 const sources = [_][]const u8{
424 "",
425 "int value;",
426 "\n/* lead */ static const char *name = \"chant\"; // tail\n",
427 "for (int i = 0; i < 8; i += 1) value[i] = .5f;",
428 "_BitInt(17) signed_value = 42UL;",
429 };
430 var bytes: [64 * @sizeOf(Token)]u8 align(Storage.storage_alignment) = undefined;
431
432 for (sources) |source| {
433 const token_survey = try survey(source, "differential.c");
434 try std.testing.expect(token_survey.limits.tokens <= source.len + 1);
435 const capacity = try Capacity.derive(token_survey.limits);
436 try std.testing.expect(capacity.storage_bytes <= bytes.len);
437 var storage = try Storage.init(bytes[0..capacity.storage_bytes], token_survey.limits);
438 storage.activate();
439 const materialized = try storage.fill(token_survey, source, "differential.c");
440
441 var lexer = state.Lexer.init(source, "differential.c");
442 for (materialized) |actual| {
443 const expected = try scan.next(&lexer);
444 try std.testing.expectEqual(expected.kind, actual.kind);
445 try std.testing.expectEqualStrings(expected.text, actual.text);
446 try std.testing.expectEqualStrings(expected.file, actual.file);
447 try std.testing.expectEqual(expected.line, actual.line);
448 try std.testing.expectEqual(expected.column, actual.column);
449 }
450 try std.testing.expectEqual(chant.token.Kind.eof, materialized[materialized.len - 1].kind);
451 _ = storage.deinit();
452 }
453 }
454
455 test "token survey preserves deterministic lexer errors" {
456 const cases = .{
457 .{ "$", error.UnexpectedCharacter },
458 .{ "\"", error.UnterminatedString },
459 .{ "'", error.UnterminatedCharacter },
460 .{ "/*", error.UnterminatedComment },
461 };
462 inline for (cases) |case| {
463 try std.testing.expectError(case[1], survey(case[0], "error.c"));
464 }
465 }
466
467 comptime {
468 alloc_phase.capacity.requireProvisionedRejectingOwnerShape(Storage);
469 }