1//! Parser takes a Token list and creates a Node list. It does not own the source code or
2//! token data, but transferring into an `Ast` does move token list ownership.
3gpa: Allocator,
4source: [:0]const u8,
5token_tags: []const Token.Tag,
6token_starts: []const ByteOffset,
7
8pos: TokenIndex = 0,
9nodes: Node.List = .{},
10extra: ArrayListUnmanaged(u32) = .{},
11scratch: ArrayListUnmanaged(NodeIndex) = .{},
12
13ast_error: ?AstError.WithTrace = null,
14
15depth: u32 = 0,
16
17/// Instead of implementing a non-recursive parser, the stack size is limited by this constant.
18const depth_limit = 4096;
19
20pub fn parse(gpa: std.mem.Allocator, source: [:0]const u8, ast_error: *AstError.WithTrace) Parse.Error!Ast {
21 var tokens = try Tokenizer.tokenize(source, gpa);
22 errdefer tokens.deinit(gpa);
23
24 var parser = Parse.init(gpa, source, tokens);
25 errdefer parser.deinit();
26
27 try parser.nodes.ensureUnusedCapacity(
28 gpa,
29 @max(1, @divFloor(tokens.len, 4)),
30 );
31
32 parser.parseRoot() catch |err| switch (err) {
33 error.OutOfMemory => return error.OutOfMemory,
34 error.ParseFail => {
35 ast_error.* = parser.ast_error.?;
36 return error.ParseFail;
37 },
38 };
39
40 return try parser.finalize(tokens);
41}
42
43fn init(gpa: Allocator, source: [:0]const u8, tokens: Token.List.Slice) Parse {
44 return Parse{
45 .gpa = gpa,
46 .source = source,
47 .token_tags = tokens.items(.tag),
48 .token_starts = tokens.items(.offset),
49 };
50}
51
52/// This transfers the parse result into an Ast
53fn finalize(p: *Parse, token_slice: Token.List.Slice) !Ast {
54 const extra = try p.extra.toOwnedSlice(p.gpa);
55 defer p.* = undefined;
56 assert(token_slice.items(.tag).ptr == p.token_tags.ptr);
57 assert(token_slice.items(.offset).ptr == p.token_starts.ptr);
58 p.scratch.deinit(p.gpa);
59
60 const ast: Ast = .{
61 .utf8_source = p.source,
62 .tokens = token_slice,
63 .nodes = p.nodes.toOwnedSlice(),
64 .extra = extra,
65 };
66
67 return ast;
68}
69
70/// This discards all parser work
71fn deinit(p: *Parse) void {
72 defer p.* = undefined;
73 p.nodes.deinit(p.gpa);
74 p.extra.deinit(p.gpa);
75 p.scratch.deinit(p.gpa);
76}
77
78pub const Error = error{
79 OutOfMemory,
80 ParseFail,
81};
82
83pub const ExpectedContext = enum {
84 param,
85 argument,
86 statement,
87 expression,
88 else_clause,
89 struct_field,
90 param_list,
91 static_field,
92
93 pub fn description(tag: ExpectedContext) []const u8 {
94 return switch (tag) {
95 .param => "a parameter",
96 .param_list => "function parameters",
97 .argument => "an argument",
98 .statement => "a statement",
99 .expression => "an expression",
100 .else_clause => "an else clause",
101 .struct_field => "a field definition",
102 .static_field => "a field name or number",
103 };
104 }
105};
106
107const Operator = enum(u8) {
108 add = @intFromEnum(Token.Tag.plus),
109 sub = @intFromEnum(Token.Tag.minus),
110 mul = @intFromEnum(Token.Tag.star),
111 div = @intFromEnum(Token.Tag.slash),
112 rem = @intFromEnum(Token.Tag.percent),
113 pow = @intFromEnum(Token.Tag.star_star),
114 bool_and = @intFromEnum(Token.Tag.kw_and),
115 bool_or = @intFromEnum(Token.Tag.kw_or),
116 bit_and = @intFromEnum(Token.Tag.@"and"),
117 bit_or = @intFromEnum(Token.Tag.pipe),
118 bit_xor = @intFromEnum(Token.Tag.caret),
119 shl = @intFromEnum(Token.Tag.lt_lt),
120 shr = @intFromEnum(Token.Tag.gt_gt),
121 eq = @intFromEnum(Token.Tag.equal_equal),
122 ne = @intFromEnum(Token.Tag.bang_equal),
123 lt = @intFromEnum(Token.Tag.lt),
124 le = @intFromEnum(Token.Tag.lt_equal),
125 gt = @intFromEnum(Token.Tag.gt),
126 ge = @intFromEnum(Token.Tag.gt_equal),
127 // Following operators are assignment operators
128 assign = @intFromEnum(Token.Tag.equal),
129 add_assign = @intFromEnum(Token.Tag.plus_equal),
130 sub_assign = @intFromEnum(Token.Tag.minus_equal),
131 mul_assign = @intFromEnum(Token.Tag.star_equal),
132 div_assign = @intFromEnum(Token.Tag.slash_equal),
133 rem_assign = @intFromEnum(Token.Tag.percent_equal),
134 pow_assign = @intFromEnum(Token.Tag.star_star_equal),
135 and_assign = @intFromEnum(Token.Tag.and_and_equal),
136 or_assign = @intFromEnum(Token.Tag.pipe_pipe_equal),
137 bit_and_assign = @intFromEnum(Token.Tag.and_equal),
138 bit_or_assign = @intFromEnum(Token.Tag.pipe_equal),
139 bit_xor_assign = @intFromEnum(Token.Tag.caret_equal),
140 shl_assign = @intFromEnum(Token.Tag.lt_lt_equal),
141 shr_assign = @intFromEnum(Token.Tag.gt_gt_equal),
142
143 const Direction = enum { ltr, rtl };
144
145 /// Only the binary operator levels are actually used,
146 /// but all are listed for reference.
147 const Level = enum {
148 /// e. e[] e()
149 accessor,
150 /// new
151 new,
152 /// ++e, --e, !e, ~e, +e, -e, typeof, void, delete
153 prefix,
154 /// **
155 exponentiation,
156 /// *, /, %
157 multiplicative,
158 /// +, -
159 additive,
160 /// <<, >>, >>>
161 bitwise_shift,
162 /// <, <=, >, >=
163 relational,
164 /// ==, !=
165 equality,
166 /// &
167 bit_and,
168 /// ^
169 bit_xor,
170 /// |
171 bit_or,
172 /// &&
173 logical_and,
174 /// ||, ??
175 logical_or,
176 /// =, +=, -=, *=, /=, %=, / <<=, >>=, >>>=, &=, ^=, |=
177 assign,
178 };
179
180 pub fn direction(op: Operator) Direction {
181 return switch (op) {
182 .pow => .rtl,
183
184 .assign,
185 .add_assign,
186 .sub_assign,
187 .mul_assign,
188 .div_assign,
189 .rem_assign,
190 .pow_assign,
191 .and_assign,
192 .or_assign,
193 .bit_and_assign,
194 .bit_or_assign,
195 .bit_xor_assign,
196 .shl_assign,
197 .shr_assign,
198 => .rtl,
199
200 else => .ltr,
201 };
202 }
203
204 pub fn level(op: Operator) Level {
205 return switch (op) {
206 .pow => .exponentiation,
207 .mul, .div, .rem => .multiplicative,
208 .add, .sub => .additive,
209 .shl, .shr => .bitwise_shift,
210 .lt, .le, .gt, .ge => .relational,
211 .eq, .ne => .equality,
212 .bool_and => .logical_and,
213 .bool_or => .logical_or,
214 .bit_and => .bit_and,
215 .bit_xor => .bit_xor,
216 .bit_or => .bit_or,
217 .assign,
218 .add_assign,
219 .sub_assign,
220 .mul_assign,
221 .div_assign,
222 .rem_assign,
223 .pow_assign,
224 .and_assign,
225 .or_assign,
226 .bit_and_assign,
227 .bit_or_assign,
228 .bit_xor_assign,
229 .shl_assign,
230 .shr_assign,
231 => .assign,
232 };
233 }
234
235 const lut = brk: {
236 const token_tags = std.enums.values(Token.Tag);
237 const op_tags = std.enums.values(Operator);
238
239 var is_operator_lut: [token_tags.len]bool = .{false} ** token_tags.len;
240 for (op_tags) |op| {
241 is_operator_lut[@intFromEnum(op)] = true;
242 }
243
244 var ast_tag_lut: [token_tags.len]Node.Tag = .{.root} ** token_tags.len;
245 for (op_tags) |op| {
246 ast_tag_lut[@intFromEnum(op)] = @field(Node.Tag, @tagName(op));
247 }
248
249 break :brk struct {
250 const is_operator = is_operator_lut;
251 const ast_tag = ast_tag_lut;
252 };
253 };
254
255 pub fn fromToken(tag: Token.Tag) ?Operator {
256 return if (lut.is_operator[@intFromEnum(tag)])
257 @enumFromInt(@intFromEnum(tag))
258 else
259 null;
260 }
261
262 pub fn astTag(op: Operator) Node.Tag {
263 const tag = lut.ast_tag[@intFromEnum(op)];
264 assert(tag != .root); // invalid operator or lut construction
265 return tag;
266 }
267
268 pub fn isAssign(op: Operator) bool {
269 return switch (op) {
270 .assign,
271 .add_assign,
272 .sub_assign,
273 .mul_assign,
274 .div_assign,
275 .rem_assign,
276 .pow_assign,
277 .and_assign,
278 .or_assign,
279 .bit_and_assign,
280 .bit_or_assign,
281 .bit_xor_assign,
282 .shl_assign,
283 .shr_assign,
284 => true,
285 else => false,
286 };
287 }
288};
289
290const ParseExprMode = enum {
291 /// Standard parsing
292 expression,
293 /// Statements allow assignment binary operators in addition to other expressions.
294 statement,
295 /// This bans struct initializations so that parsing stops at a '{'
296 /// Example: "if hello {" must not be parsed as a struct initialization.
297 preceding_block,
298};
299
300/// Some constructs are valid expressions as well as valid top-level
301/// declarations. Top level declarations must have associated names, but the
302/// anonymous versions of these must not have names.
303const ExprParseContext = enum {
304 declaration,
305 expression,
306};
307
308const TypePresence = enum {
309 types_optional,
310 types_required,
311};
312
313/// When error.SyntaxError is returned, `p.err` is set to this as well as `p.pos`
314/// When printing these, token list and Ast is not actually available, so full tokens
315/// are stored in the errors.
316pub const AstError = union(enum) {
317 /// Unexpected data, expected a token.
318 unexpected_token: struct {
319 expected: Token.Tag,
320 got: Token,
321 },
322 /// Unexpected data, expected <ExpectedContext>
323 unexpected_context: struct {
324 expected: ExpectedContext,
325 got: Token,
326 },
327 /// Went past depth maximum
328 depth_limit: Token,
329
330 array_type_flipped_hint: Token,
331
332 pub fn toReport(err: AstError, allocator: Allocator, trace: DebugStoredTrace) !Report {
333 return (Report.Err{ .ast = err }).toReport(allocator, trace);
334 }
335
336 pub fn build(err: AstError, ctx: *Report.MsgContext) !void {
337 switch (err) {
338 .unexpected_token => |data| {
339 try ctx.msg(.{ .token_stored = data.got }, "expected {s}, but found {s}", .{
340 data.expected.description(),
341 data.got.tag.description(),
342 });
343 },
344 .unexpected_context => |data| {
345 try ctx.msg(.{ .token_stored = data.got }, "expected {s}, but found {s}", .{
346 data.expected.description(),
347 data.got.tag.description(),
348 });
349 },
350 .array_type_flipped_hint => |token| {
351 try ctx.msg(.{ .token_stored = token }, "expected {s}, but found {s}", .{
352 ExpectedContext.expression.description(),
353 token.tag.description(),
354 });
355 try ctx.msgAlone("the syntax for array types is \"[]T\", not \"T[]\"", .{});
356 },
357 .depth_limit => |data| {
358 try ctx.msg(.{ .token_stored = data }, "syntax tree is nested too deeply (limit: {d})", .{depth_limit});
359 },
360 }
361 }
362
363 pub const WithTrace = struct {
364 err: AstError,
365 trace: DebugStoredTrace,
366
367 pub fn toReport(wt: WithTrace, allocator: Allocator) !Report {
368 return wt.err.toReport(allocator, wt.trace);
369 }
370 };
371};
372
373pub fn parseRoot(p: *Parse) Error!void {
374 const trace = t.trace(@src());
375 defer trace.end();
376
377 assert(p.nodes.len == 0);
378 assert(p.extra.items.len == 0);
379 assert(p.pos == 0);
380 assert(p.nodes.capacity > 0);
381
382 p.nodes.appendAssumeCapacity(.{
383 .tag = .root,
384 .main_token = 0,
385 .data = undefined,
386 });
387
388 const list = try p.parseModuleMembers();
389 p.nodes.items(.data)[0] = .{
390 .list = list,
391 };
392}
393
394fn parseModuleMembers(p: *Parse) Error!SubList {
395 p.depth += 1;
396 defer p.depth -= 1;
397 if (p.depth > depth_limit) {
398 return p.fail(.{ .depth_limit = p.fullToken(p.pos) });
399 }
400
401 const trace = t.trace(@src());
402 defer trace.end();
403
404 const scratch_top = p.scratch.items.len;
405 defer p.scratch.shrinkRetainingCapacity(scratch_top);
406
407 // skip module doc comment
408 while (p.eatToken(.module_doc_comment)) |_| {}
409
410 while (true) switch (p.currentTag()) {
411 .kw_let,
412 .kw_var,
413 .kw_fn,
414 .kw_pub,
415 => try p.scratch.append(p.gpa, try p.parseModuleDecl()),
416
417 .kw_struct => try p.scratch.append(p.gpa, try p.parseStructDecl(.declaration)),
418 .kw_tuple => try p.scratch.append(p.gpa, try p.parseStructDecl(.declaration)),
419
420 .id => if (p.isContextualKeyword("test")) {
421 try p.scratch.append(p.gpa, try p.parseTestDecl());
422 } else {
423 try p.parseExpressionStatement();
424 },
425
426 .kw_enum,
427 .kw_trait,
428 .kw_impl,
429 => |tag| std.debug.panic("TODO: parse {s}", .{@tagName(tag)}),
430
431 .eof => break,
432
433 else => {
434 if (!p.isExpressionStart()) {
435 return p.failUnexpectedToken(.statement);
436 }
437 try p.parseExpressionStatement();
438 },
439 };
440
441 return p.scratchToSubList(scratch_top);
442}
443
444fn parseExpressionStatement(p: *Parse) !void {
445 if (!p.isExpressionStart()) {
446 return p.failUnexpectedToken(.statement);
447 }
448
449 const first_tag = p.currentTag();
450
451 try p.scratch.append(p.gpa, try p.parseExpression(.statement));
452
453 switch (first_tag) {
454 // some control flow and blocks are allowed to not have
455 // trailing semicolons. this is a stylistic choice.
456 .kw_if,
457 .start_brace,
458 => {},
459
460 // TODO: make semicolons optional, but emit a warning
461 else => _ = try p.expect(.semi),
462 }
463}
464
465fn parseModuleDecl(p: *Parse) Error!NodeIndex {
466 const trace = t.trace(@src());
467 defer trace.end();
468
469 _ = p.eatToken(.kw_pub);
470
471 return switch (p.currentTag()) {
472 .kw_var, .kw_let => try p.parseVarDecl(),
473
474 .kw_fn => try p.parseFnDecl(),
475
476 else => unreachable,
477 };
478}
479
480fn parseFnDecl(p: *Parse) Error!NodeIndex {
481 const trace = t.trace(@src());
482 defer trace.end();
483
484 const main_token = p.assertToken(.kw_fn);
485
486 _ = try p.expect(.id);
487
488 const params = if (p.eatToken(.start_paren) != null)
489 try p.parseParamList(.types_required)
490 else
491 null;
492
493 const return_type = if (p.eatToken(.minus_lt)) |_|
494 if (!p.isExpressionStart())
495 return p.failUnexpectedToken(.expression)
496 else
497 try p.parseExpression(.preceding_block)
498 else
499 null;
500
501 const body = try p.parseExpression(.expression);
502
503 const extra = try p.addExtra(Ast.Fn, .{
504 .params = params orelse .empty,
505 .return_type = optionalNodeIndex(return_type),
506 });
507
508 return try p.addNode(.{
509 .tag = .fn_decl,
510 .main_token = main_token,
511 .data = .{ .function = .{
512 .body = body,
513 .extra = extra,
514 } },
515 });
516}
517
518fn parseParamList(p: *Parse, types: TypePresence) Error!SubList {
519 const trace = t.trace(@src());
520 defer trace.end();
521
522 const scratch_top = p.scratch.items.len;
523 defer p.scratch.shrinkRetainingCapacity(scratch_top);
524
525 while (true) {
526 const trace_param = t.traceFmt(@src(), "Param {d}", .{p.scratch.items.len - scratch_top});
527 defer trace_param.end();
528
529 if (p.currentTag() == .end_paren) break;
530
531 try p.scratch.append(p.gpa, try p.parseParamDecl(types));
532
533 switch (p.currentTag()) {
534 .comma => {
535 _ = p.nextToken();
536 },
537 .end_paren => break,
538 else => return p.failUnexpectedToken(.param),
539 }
540 }
541
542 _ = p.assertToken(.end_paren);
543
544 return p.scratchToSubList(scratch_top);
545}
546
547fn parseParamDecl(p: *Parse, types: TypePresence) Error!NodeIndex {
548 const trace = t.trace(@src());
549 defer trace.end();
550
551 const main_token = p.assertToken(.id);
552
553 const ty = if (types == .types_required or p.currentTag() == .colon) brk: {
554 _ = try p.expect(.colon);
555 break :brk try p.parseExpression(.expression);
556 } else null;
557
558 return try p.addNode(.{
559 .tag = .param_decl,
560 .main_token = main_token,
561 .data = .{ .param_decl = .{
562 .type = optionalNodeIndex(ty),
563 } },
564 });
565}
566
567fn parseStructDecl(p: *Parse, ctx: ExprParseContext) Error!NodeIndex {
568 const trace = t.trace(@src());
569 defer trace.end();
570
571 const main_token = p.assertToken(.kw_struct);
572
573 switch (ctx) {
574 .declaration => _ = try p.expect(.id),
575 else => {},
576 }
577
578 _ = try p.expect(.start_brace);
579
580 const fields = try p.parseStructFieldList();
581
582 return try p.addNode(.{
583 .tag = .struct_decl,
584 .main_token = main_token,
585 .data = .{ .list = fields },
586 });
587}
588
589fn parseTupleDecl(p: *Parse, ctx: ExprParseContext) Error!NodeIndex {
590 const trace = t.trace(@src());
591 defer trace.end();
592
593 const main_token = p.assertToken(.kw_tuple);
594
595 switch (ctx) {
596 .declaration => _ = try p.expect(.id),
597 else => {},
598 }
599
600 _ = try p.expect(.start_paren);
601
602 const fields = try p.parseExpressionList(.end_paren, .expression);
603
604 return try p.addNode(.{
605 .tag = .tuple_type,
606 .main_token = main_token,
607 .data = .{ .list = fields },
608 });
609}
610
611fn parseTestDecl(p: *Parse) Error!NodeIndex {
612 const trace = t.trace(@src());
613 defer trace.end();
614
615 const main_token = p.assertToken(.id);
616
617 _ = p.eatToken(.string);
618
619 try p.expectWithoutAdvance(.start_brace);
620
621 const block = try p.parseBlock();
622
623 return try p.addNode(.{
624 .tag = .test_decl,
625 .main_token = main_token,
626 .data = .{ .test_decl = .{
627 .doc_test_name = .none,
628 .block = block,
629 } },
630 });
631}
632
633fn parseStructFieldList(p: *Parse) Error!SubList {
634 const trace = t.trace(@src());
635 defer trace.end();
636
637 const scratch_top = p.scratch.items.len;
638 defer p.scratch.shrinkRetainingCapacity(scratch_top);
639
640 while (true) {
641 const trace_param = t.traceFmt(@src(), "Param {d}", .{p.scratch.items.len - scratch_top});
642 defer trace_param.end();
643
644 if (p.currentTag() == .end_brace) break;
645
646 try p.scratch.append(p.gpa, try p.parseStructField());
647
648 switch (p.currentTag()) {
649 .comma => _ = p.nextToken(),
650 .end_brace => break,
651 else => return p.failUnexpectedToken(.struct_field),
652 }
653 }
654
655 _ = p.assertToken(.end_brace);
656
657 return p.scratchToSubList(scratch_top);
658}
659
660fn parseStructField(p: *Parse) Error!NodeIndex {
661 const trace = t.trace(@src());
662 defer trace.end();
663
664 const main_token = try p.expect(.id);
665
666 _ = try p.expect(.colon);
667
668 const expr = try p.parseExpression(.expression);
669
670 return try p.addNode(.{
671 .tag = .struct_field,
672 .main_token = main_token,
673 .data = .{ .un = .{ .expr = expr } },
674 });
675}
676
677fn parseBlock(p: *Parse) Error!NodeIndex {
678 const trace = t.trace(@src());
679 defer trace.end();
680
681 const main_token = p.assertToken(.start_brace);
682
683 const tag, const list = try p.parseBlockContents();
684 assert(p.lastTag() == .end_brace);
685
686 return try p.addNode(.{
687 .tag = tag,
688 .main_token = main_token,
689 .data = .{
690 .list = list,
691 },
692 });
693}
694
695fn parseLabelExpression(p: *Parse) Error!NodeIndex {
696 const trace = t.trace(@src());
697 defer trace.end();
698
699 const main_token = p.assertToken(.id);
700 _ = try p.expect(.colon);
701 const expr = try p.parseExpression(.expression);
702
703 return try p.addNode(.{
704 .tag = .label,
705 .main_token = main_token,
706 .data = .{ .label = .{
707 .expr = expr,
708 } },
709 });
710}
711
712fn parseBlockContents(p: *Parse) Error!struct { Node.Tag, SubList } {
713 const trace = t.trace(@src());
714 defer trace.end();
715
716 assert(p.lastTag() == .start_brace);
717 const scratch_top = p.scratch.items.len;
718 defer p.scratch.shrinkRetainingCapacity(scratch_top);
719
720 const tag: Node.Tag = while (true) switch (p.currentTag()) {
721 .kw_let,
722 .kw_var,
723 => try p.scratch.append(p.gpa, try p.parseVarDecl()),
724
725 .end_brace => break .block_void,
726
727 else => {
728 if (!p.isExpressionStart()) {
729 return p.failUnexpectedToken(.statement);
730 }
731
732 const first_tag = p.currentTag();
733
734 try p.scratch.append(p.gpa, try p.parseExpression(.statement));
735
736 switch (first_tag) {
737 // some control flow and blocks are allowed to not have
738 // trailing semicolons. this is a stylistic choice.
739 .kw_if,
740 .start_brace,
741 => {
742 // ending a block here should also count as an implicit return,
743 // even though voiding it with a semicolon is not allowed.
744 if (p.currentTag() == .end_brace) break .block_implicit_return;
745 },
746
747 // TODO: make semicolons optional, but emit a warning
748
749 else => {
750 if (p.eatToken(.semi) == null) {
751 // this must be last statement in block if it isnt,
752 // the p.expect(.end_brace) later will fail.
753 break .block_implicit_return;
754 }
755 },
756 }
757 },
758 };
759
760 _ = try p.expect(.end_brace);
761
762 return .{ tag, try p.scratchToSubList(scratch_top) };
763}
764
765/// VarDecl <- (kw_pub)? (kw_var | kw_let) id (colon expr)? equal expr semi
766fn parseVarDecl(p: *Parse) Error!NodeIndex {
767 const trace = t.trace(@src());
768 defer trace.end();
769
770 const kind = p.currentTag();
771 assert(kind == .kw_var or kind == .kw_let);
772
773 const main_token = p.nextToken();
774
775 _ = try p.expect(.id);
776
777 const data_type: OptionalNodeIndex = if (p.eatToken(.colon)) |_|
778 optionalNodeIndex(try p.parseExpressionOrFail(.expression))
779 else
780 .none;
781
782 _ = try p.expect(.equal);
783
784 const data_init = try p.parseExpressionOrFail(.expression);
785
786 _ = try p.expect(.semi);
787
788 return try p.addNode(.{
789 .tag = .var_decl,
790 .main_token = main_token,
791 .data = .{ .var_decl = .{
792 .type = data_type,
793 .init = data_init,
794 } },
795 });
796}
797
798fn isExpressionStart(p: *Parse) bool {
799 return switch (p.currentTag()) {
800 .bang,
801 .builtin_id,
802 .dot,
803 .id,
804 .kw_assert,
805 .kw_break,
806 .kw_comptime,
807 .kw_if,
808 .kw_pure,
809 .kw_return,
810 .minus,
811 .number_float,
812 .number_int,
813 .start_brace,
814 .start_bracket,
815 .start_paren,
816 .string,
817 .tilde,
818 .kw_fn,
819 .kw_struct,
820 .kw_tuple,
821 .multiline_string,
822 => true,
823 else => false,
824 };
825}
826
827fn parseExpression(p: *Parse, mode: ParseExprMode) Error!NodeIndex {
828 const trace = t.trace(@src());
829 defer trace.end();
830
831 p.depth += 1;
832 defer p.depth -= 1;
833 if (p.depth > depth_limit) {
834 return p.fail(.{ .depth_limit = p.fullToken(p.pos) });
835 }
836
837 assert(p.isExpressionStart());
838
839 // These unary operators are greedy, so handle them first.
840 switch (p.currentTag()) {
841 .kw_return => return p.parseReturn(mode),
842 .kw_break => return p.parseBreak(mode),
843
844 .kw_assert => return p.parseGreedyUnary(.assert, mode),
845 .kw_comptime => return p.parseGreedyUnary(.@"comptime", mode),
846 .kw_pure => return p.parseGreedyUnary(.pure, mode),
847
848 else => {},
849 }
850
851 var expr = try p.parseExpressionPart(mode);
852
853 while (Operator.fromToken(p.currentTag())) |op| {
854 if (mode != .statement and op.isAssign()) break;
855 expr = try p.parseBinarySuffix(expr, op, mode);
856 }
857
858 return expr;
859}
860
861fn parseExpressionOrFail(p: *Parse, mode: ParseExprMode) Error!NodeIndex {
862 return if (p.isExpressionStart())
863 p.parseExpression(mode)
864 else
865 p.failUnexpectedToken(.expression);
866}
867
868fn parseExpressionPart(p: *Parse, mode: ParseExprMode) Error!NodeIndex {
869 const trace = t.trace(@src());
870 defer trace.end();
871
872 var expr = switch (p.currentTag()) {
873 .id => if (p.nextTag() == .colon)
874 try p.parseLabelExpression()
875 else
876 try p.blankNode(.id),
877 .number_int => try p.blankNode(.number_int),
878 .number_float => try p.blankNode(.number_float),
879 .string => try p.blankNode(.string),
880 .multiline_string => try p.parseMultilineString(),
881
882 .builtin_id => try p.parseBuiltinCall(),
883 .dot => try p.parseAnonStructInit(),
884 .kw_fn => try p.parseAnonFunction(),
885 .kw_if => try p.parseIf(),
886 .kw_tuple => try p.parseTupleType(),
887
888 .start_brace => try p.parseBlock(),
889 .start_bracket => try p.parseArrayValueOrType(mode),
890 .start_paren => try p.parseTupleInit(),
891
892 .kw_struct => try p.parseStructDecl(.expression),
893
894 .kw_return => return p.parseReturn(mode),
895 .kw_break => return p.parseBreak(mode),
896 .kw_assert => return p.parseGreedyUnary(.assert, mode),
897 .kw_comptime => return p.parseGreedyUnary(.@"comptime", mode),
898 .kw_pure => return p.parseGreedyUnary(.pure, mode),
899
900 inline .bang,
901 .tilde,
902 .minus,
903 => |tag| unary: {
904 const main_token = p.nextToken();
905 const expr = try p.parseExpressionPart(mode);
906
907 break :unary try p.addNode(.{
908 .tag = switch (tag) {
909 .bang => .bool_not,
910 .tilde => .bit_not,
911 .minus => .negate,
912 .kw_comptime => .@"comptime",
913 .kw_pure => .pure,
914 .kw_assert => .assert,
915 else => @compileError(unreachable),
916 },
917 .main_token = main_token,
918 .data = .{ .un = .{
919 .expr = expr,
920 } },
921 });
922 },
923
924 else => return p.failUnexpectedToken(.expression),
925 };
926
927 // parse field, calls, and index expressions
928 while (true) {
929 const trace2 = t.traceFmt(@src(), "(field/call)", .{});
930 defer trace2.end();
931
932 switch (p.currentTag()) {
933 .dot => {
934 const main_token = p.nextToken();
935 const field = switch (p.currentTag()) {
936 .id, .number_int => p.nextToken(),
937 else => return p.failUnexpectedToken(.static_field),
938 };
939
940 expr = try p.addNode(.{
941 .tag = .field,
942 .main_token = main_token,
943 .data = .{ .field = .{
944 .base = expr,
945 .field_token = field,
946 } },
947 });
948 },
949 .start_paren => {
950 const main_token = p.nextToken();
951 const args = try p.parseExpressionList(.end_paren, .argument);
952
953 const extra = try p.addExtra(Ast.Call, .{
954 .args = args,
955 });
956
957 expr = try p.addNode(.{
958 .tag = .call,
959 .main_token = main_token,
960 .data = .{ .call = .{
961 .base = expr,
962 .extra = extra,
963 } },
964 });
965 },
966 .start_bracket => {
967 const main_token = p.nextToken();
968
969 if (p.currentTag() == .end_bracket) {
970 return p.fail(.{ .array_type_flipped_hint = p.fullToken(p.pos) });
971 }
972
973 const index = try p.parseExpressionOrFail(.expression);
974
975 _ = try p.expect(.end_bracket);
976
977 expr = try p.addNode(.{
978 .tag = .index,
979 .main_token = main_token,
980 .data = .{ .bin = .{
981 .lhs = expr,
982 .rhs = index,
983 } },
984 });
985 },
986 .start_brace => {
987 if (mode == .preceding_block) break;
988
989 const main_token = p.nextToken();
990 const initializers = try p.parseStructFieldList();
991 expr = try p.addNode(.{
992 .tag = .struct_init,
993 .main_token = main_token,
994 .data = .{ .struct_init = .{
995 .base = optionalNodeIndex(expr),
996 .extra = try p.addExtra(Ast.SubList, initializers),
997 } },
998 });
999 },
1000 else => break,
1001 }
1002 }
1003
1004 return expr;
1005}
1006
1007fn parseBinarySuffix(p: *Parse, lhs: NodeIndex, op: Operator, mode: ParseExprMode) Error!NodeIndex {
1008 const trace = t.trace(@src());
1009 defer trace.end();
1010
1011 const main_token = p.nextToken();
1012 const level = op.level();
1013 var rhs = try p.parseExpressionPart(mode);
1014
1015 while (Operator.fromToken(p.currentTag())) |next_op| {
1016 if (mode != .statement and next_op.isAssign()) break;
1017
1018 const new_level = next_op.level();
1019 const use = switch (op.direction()) {
1020 .ltr => @intFromEnum(new_level) < @intFromEnum(level),
1021 .rtl => @intFromEnum(new_level) <= @intFromEnum(level),
1022 };
1023 if (!use) break;
1024
1025 rhs = try p.parseBinarySuffix(rhs, next_op, mode);
1026 }
1027
1028 return try p.addNode(.{
1029 .tag = op.astTag(),
1030 .main_token = main_token,
1031 .data = .{ .bin = .{
1032 .lhs = lhs,
1033 .rhs = rhs,
1034 } },
1035 });
1036}
1037
1038fn parseReturn(p: *Parse, mode: ParseExprMode) Error!NodeIndex {
1039 const trace = t.trace(@src());
1040 defer trace.end();
1041
1042 const main_token = p.assertToken(.kw_return);
1043
1044 const expr = if (p.isExpressionStart())
1045 try p.parseExpression(mode)
1046 else
1047 null;
1048
1049 return try p.addNode(.{
1050 .tag = .@"return",
1051 .main_token = main_token,
1052 .data = .{ .@"return" = .{
1053 .expr = optionalNodeIndex(expr),
1054 } },
1055 });
1056}
1057
1058fn parseBreak(p: *Parse, mode: ParseExprMode) Error!NodeIndex {
1059 const trace = t.trace(@src());
1060 defer trace.end();
1061
1062 const main_token = p.assertToken(.kw_break);
1063
1064 const label = if (p.eatToken(.colon)) |_|
1065 try p.expect(.id)
1066 else
1067 null;
1068
1069 const expr = if (p.isExpressionStart())
1070 try p.parseExpression(mode)
1071 else
1072 null;
1073
1074 return try p.addNode(.{
1075 .tag = .@"break",
1076 .main_token = main_token,
1077 .data = .{ .@"break" = .{
1078 .label = optionalTokenIndex(label),
1079 .value = optionalNodeIndex(expr),
1080 } },
1081 });
1082}
1083
1084fn parseGreedyUnary(p: *Parse, tag: Node.Tag, mode: ParseExprMode) Error!NodeIndex {
1085 const trace = t.trace(@src());
1086 defer trace.end();
1087
1088 const main_token = p.nextToken();
1089
1090 const expr = try p.parseExpressionOrFail(mode);
1091
1092 return try p.addNode(.{
1093 .tag = tag,
1094 .main_token = main_token,
1095 .data = .{ .un = .{
1096 .expr = expr,
1097 } },
1098 });
1099}
1100
1101fn parseBuiltinCall(p: *Parse) Error!NodeIndex {
1102 const trace = t.trace(@src());
1103 defer trace.end();
1104
1105 const main_token = p.assertToken(.builtin_id);
1106
1107 _ = try p.expect(.start_paren);
1108
1109 const args = try p.parseExpressionList(.end_paren, .argument);
1110
1111 return try p.addNode(.{
1112 .tag = .builtin_call,
1113 .main_token = main_token,
1114 .data = .{ .list = args },
1115 });
1116}
1117
1118fn parseExpressionList(p: *Parse, comptime end_token: Token.Tag, fail_context: ExpectedContext) Error!SubList {
1119 const trace = t.trace(@src());
1120 defer trace.end();
1121
1122 const scratch_top = p.scratch.items.len;
1123 defer p.scratch.shrinkRetainingCapacity(scratch_top);
1124
1125 while (p.isExpressionStart()) {
1126 try p.scratch.append(p.gpa, try p.parseExpression(.expression));
1127
1128 switch (p.currentTag()) {
1129 end_token => {
1130 break;
1131 },
1132 .comma => {
1133 _ = p.nextToken();
1134 if (p.currentTag() == end_token)
1135 break;
1136 },
1137 else => return p.failUnexpectedToken(fail_context),
1138 }
1139 }
1140
1141 _ = try p.expect(end_token);
1142
1143 return p.scratchToSubList(scratch_top);
1144}
1145
1146fn parseIf(p: *Parse) Error!NodeIndex {
1147 const trace = t.trace(@src());
1148 defer trace.end();
1149
1150 const main_token = p.assertToken(.kw_if);
1151
1152 const cond = try p.parseExpression(.preceding_block);
1153
1154 _ = try p.expectWithoutAdvance(.start_brace);
1155 const yes = try p.parseBlock();
1156
1157 const no = if (p.eatToken(.kw_else)) |_|
1158 try p.parseElseValue()
1159 else
1160 null;
1161
1162 const extra = try p.addExtra(Ast.If, .{
1163 .yes = yes,
1164 .no = optionalNodeIndex(no),
1165 });
1166
1167 return try p.addNode(.{
1168 .tag = .@"if",
1169 .main_token = main_token,
1170 .data = .{ .@"if" = .{
1171 .cond = cond,
1172 .extra = extra,
1173 } },
1174 });
1175}
1176
1177fn parseElseValue(p: *Parse) Error!NodeIndex {
1178 const trace = t.trace(@src());
1179 defer trace.end();
1180
1181 assert(p.lastTag() == .kw_else);
1182
1183 return switch (p.currentTag()) {
1184 .start_brace => p.parseBlock(),
1185 .kw_if => p.parseIf(),
1186 .id => p.parseLabelExpression(),
1187
1188 else => return p.failUnexpectedToken(.else_clause),
1189 };
1190}
1191
1192fn parseAnonStructInit(p: *Parse) Error!NodeIndex {
1193 const trace = t.trace(@src());
1194 defer trace.end();
1195
1196 _ = p.assertToken(.dot);
1197
1198 const main_token = try p.expect(.start_brace);
1199 const initializers = try p.parseStructFieldList();
1200 return try p.addNode(.{
1201 .tag = .struct_init,
1202 .main_token = main_token,
1203 .data = .{ .struct_init = .{
1204 .base = .none,
1205 .extra = try p.addExtra(Ast.SubList, initializers),
1206 } },
1207 });
1208}
1209
1210fn parseAnonFunction(p: *Parse) Error!NodeIndex {
1211 const trace = t.trace(@src());
1212 defer trace.end();
1213
1214 const main_token = p.assertToken(.kw_fn);
1215
1216 const params = switch (p.currentTag()) {
1217 // fn { 1 }
1218 .start_brace => SubList.empty,
1219 // fn (args, here) { 2 }
1220 .start_paren => param_list: {
1221 _ = p.assertToken(.start_paren);
1222 break :param_list try p.parseParamList(.types_optional);
1223 },
1224 // fn arg { 3 }
1225 .id => single_param: {
1226 const scratch_top = p.scratch.items.len;
1227 defer p.scratch.shrinkRetainingCapacity(scratch_top);
1228 try p.scratch.append(p.gpa, try p.blankNode(.id));
1229 break :single_param try p.scratchToSubList(scratch_top);
1230 },
1231 else => return p.failUnexpectedToken(.param_list),
1232 };
1233
1234 const return_type = if (p.eatToken(.minus_lt)) |_|
1235 if (!p.isExpressionStart())
1236 return p.failUnexpectedToken(.expression)
1237 else
1238 try p.parseExpression(.preceding_block)
1239 else
1240 null;
1241
1242 try p.expectWithoutAdvance(.start_brace);
1243 const body = try p.parseBlock();
1244
1245 const extra = try p.addExtra(Ast.Fn, .{
1246 .params = params,
1247 .return_type = optionalNodeIndex(return_type),
1248 });
1249
1250 return try p.addNode(.{
1251 .tag = .fn_expr,
1252 .main_token = main_token,
1253 .data = .{ .function = .{
1254 .extra = extra,
1255 .body = body,
1256 } },
1257 });
1258}
1259
1260fn parseArrayValueOrType(p: *Parse, mode: ParseExprMode) Error!NodeIndex {
1261 const main_token = p.assertToken(.start_bracket);
1262
1263 if (p.eatToken(.end_bracket) != null) {
1264 // Either array type or an empty array. These are technically ambiguous forms:
1265 //
1266 // [] & x;
1267 //
1268 // This is either a binary expression with an empty array, or an array
1269 // of references. Since the latter makes more sense, we will defer to
1270 // that. The same applies to the other operators that are both prefix
1271 // and infix, however those will all lead to semantic analysis errors.
1272 if (!p.isExpressionStart() or
1273 (mode == .preceding_block and p.currentTag() == .start_brace))
1274 {
1275 // []
1276 return p.addNode(.{
1277 .tag = .array_init,
1278 .main_token = main_token,
1279 .data = .{ .list = SubList.empty },
1280 });
1281 } else {
1282 // []T
1283 const operand = try p.parseExpressionPart(mode);
1284 return p.addNode(.{
1285 .tag = .array_type,
1286 .main_token = main_token,
1287 .data = .{ .un = .{
1288 .expr = operand,
1289 } },
1290 });
1291 }
1292 }
1293
1294 // [x, y, z]
1295 const list = try p.parseExpressionList(.end_bracket, .expression);
1296 return p.addNode(.{
1297 .tag = .array_init,
1298 .main_token = main_token,
1299 .data = .{ .list = list },
1300 });
1301}
1302
1303fn parseTupleInit(p: *Parse) Error!NodeIndex {
1304 const main_token = p.assertToken(.start_paren);
1305 const list = try p.parseExpressionList(.end_paren, .expression);
1306 return p.addNode(.{
1307 .tag = .tuple_init,
1308 .main_token = main_token,
1309 .data = .{ .list = list },
1310 });
1311}
1312
1313fn parseTupleType(p: *Parse) Error!NodeIndex {
1314 const main_token = p.assertToken(.kw_tuple);
1315 _ = try p.expect(.start_paren);
1316 const list = try p.parseExpressionList(.end_paren, .expression);
1317 return p.addNode(.{
1318 .tag = .tuple_type,
1319 .main_token = main_token,
1320 .data = .{ .list = list },
1321 });
1322}
1323
1324fn parseMultilineString(p: *Parse) !NodeIndex {
1325 const start = p.assertToken(.multiline_string);
1326
1327 while (p.eatToken(.multiline_string) != null) {}
1328
1329 const len = p.pos - start;
1330 return p.addNode(.{
1331 .tag = .multiline_string,
1332 .main_token = start,
1333 .data = .{ .list = .{
1334 .start = start,
1335 .len = len,
1336 } },
1337 });
1338}
1339
1340// helpers
1341
1342/// Append a node and return its index.
1343fn addNode(p: *Parse, node: Node) !NodeIndex {
1344 const trace = t.trace(@src());
1345 defer trace.end();
1346
1347 try p.nodes.append(p.gpa, node);
1348 // @intCast is always safe because 2^32 tokens always produce less than
1349 // 2^32 nodes, and there is a 2^32 limit on source file bytes.
1350 return @intCast(p.nodes.len - 1);
1351}
1352
1353fn addExtra(p: *Parse, comptime T: type, extra: T) !ExtraIndex {
1354 const trace = t.trace(@src());
1355 defer trace.end();
1356
1357 const extra_top = p.extra.items.len;
1358 const bytes = std.mem.asBytes(&extra);
1359 try p.extra.appendSlice(p.gpa, std.mem.bytesAsSlice(u32, bytes));
1360 return @intCast(extra_top);
1361}
1362
1363fn fail(p: *Parse, ast_error: AstError) Error {
1364 p.ast_error = .{
1365 .err = ast_error,
1366 .trace = DebugStoredTrace.capture(@returnAddress()),
1367 };
1368 return Error.ParseFail;
1369}
1370
1371fn failUnexpectedToken(p: *Parse, kind: ExpectedContext) Error {
1372 var got = p.fullToken(p.pos);
1373 if (got.tag == .eof) {
1374 // note: it is impossible to get a failure at an empty file, so subtraction is fine
1375 const prev = p.fullToken(p.pos - 1);
1376 got.offset = prev.offset + prev.len(p.source);
1377 }
1378 return p.fail(.{ .unexpected_context = .{
1379 .got = got,
1380 .expected = kind,
1381 } });
1382}
1383
1384fn blankNode(p: *Parse, comptime tag: Token.Tag) !NodeIndex {
1385 const main_token = p.assertToken(tag);
1386 return try p.addNode(.{
1387 .tag = @field(Node.Tag, @tagName(tag)),
1388 .main_token = main_token,
1389 .data = .{ .none = .{} },
1390 });
1391}
1392
1393fn currentTag(p: *Parse) Token.Tag {
1394 return p.token_tags[p.pos];
1395}
1396
1397fn lastTag(p: *Parse) Token.Tag {
1398 return p.token_tags[p.pos - 1];
1399}
1400
1401fn nextTag(p: *Parse) Token.Tag {
1402 return p.token_tags[p.pos + 1];
1403}
1404
1405fn eatToken(p: *Parse, tag: Token.Tag) ?TokenIndex {
1406 return if (p.token_tags[p.pos] == tag) p.nextToken() else null;
1407}
1408
1409fn expect(p: *Parse, tag: Token.Tag) !TokenIndex {
1410 try p.expectWithoutAdvance(tag);
1411 return p.nextToken();
1412}
1413
1414fn expectWithoutAdvance(p: *Parse, tag: Token.Tag) !void {
1415 if (p.currentTag() != tag) {
1416 return p.fail(.{ .unexpected_token = .{
1417 .got = p.fullToken(p.pos),
1418 .expected = tag,
1419 } });
1420 }
1421}
1422
1423fn assertToken(p: *Parse, tag: Token.Tag) TokenIndex {
1424 const token = p.nextToken();
1425 assert(p.token_tags[token] == tag);
1426 return token;
1427}
1428
1429fn nextToken(p: *Parse) TokenIndex {
1430 const result = p.pos;
1431 p.pos += 1;
1432 return result;
1433}
1434
1435fn isContextualKeyword(p: *Parse, kw: []const u8) bool {
1436 assert(p.currentTag() == .id);
1437 return mem.startsWith(u8, p.source[p.token_starts[p.pos]..], kw);
1438}
1439
1440fn fullToken(p: *Parse, token: TokenIndex) Token {
1441 return Token{
1442 .tag = p.token_tags[token],
1443 .offset = p.token_starts[token],
1444 };
1445}
1446
1447fn scratchToSubList(p: *Parse, scratch_top: usize) !SubList {
1448 const trace = t.trace(@src());
1449 defer trace.end();
1450
1451 const items = p.scratch.items[scratch_top..];
1452 const extra_top = p.extra.items.len;
1453 try p.extra.appendSlice(p.gpa, p.scratch.items[scratch_top..]);
1454 return .{
1455 .start = @intCast(extra_top),
1456 .len = @intCast(items.len),
1457 };
1458}
1459
1460const Parse = @This();
1461
1462const std = @import("std");
1463const assert = std.debug.assert;
1464const mem = std.mem;
1465const Allocator = mem.Allocator;
1466const ArrayListUnmanaged = std.ArrayListUnmanaged;
1467
1468const core = @import("mod.zig");
1469const DebugStoredTrace = core.DebugStoredTrace;
1470
1471const Tokenizer = core.Tokenizer;
1472const Token = Tokenizer.Token;
1473const ByteOffset = Tokenizer.ByteOffset;
1474
1475const Ast = core.Ast;
1476const Node = Ast.Node;
1477const Data = Node.Data;
1478const SubList = Ast.SubList;
1479const NodeIndex = Ast.NodeIndex;
1480const TokenIndex = Ast.TokenIndex;
1481const ExtraIndex = Ast.ExtraIndex;
1482const OptionalNodeIndex = Ast.OptionalNodeIndex;
1483const OptionalTokenIndex = Ast.OptionalTokenIndex;
1484const OptionalExtraIndex = Ast.OptionalExtraIndex;
1485const optionalTokenIndex = OptionalTokenIndex.init;
1486const optionalNodeIndex = OptionalNodeIndex.init;
1487const optionalExtraIndex = OptionalExtraIndex.init;
1488
1489const t = @import("tracer");
1490
1491const Report = core.Report;
1492const Comp = core.Comp;
1493
1494test "fuzz test parser for crashes" {
1495 try core.unicode_props.init();
1496 try std.testing.fuzz(struct {
1497 fn run(input_bytes: []const u8) !void {
1498 const sentinel = try std.testing.allocator.dupeZ(u8, input_bytes);
1499 defer std.testing.allocator.free(sentinel);
1500
1501 var err: AstError.WithTrace = undefined;
1502 var ast = parse(std.testing.allocator, sentinel, &err) catch
1503 return; // ignore parser errors, only fail on crashes
1504 ast.deinit(std.testing.allocator);
1505 }
1506 }.run, .{});
1507}