1//! Example usage:
2//! zig build gen-parser-oracle
3//! zig build check-parser-oracle
4
5// This program implements a subset of the PEG grammar definition
6// in the peg(1) man page.
7//
8// It generates a recursive descent parser that returns true if a given input is
9// matched by the grammar. This generated parser is used as an oracle for fuzz testing.
10
11const std = @import("std");
12const assert = std.debug.assert;
13const Io = std.Io;
14const mem = std.mem;
15const Allocator = mem.Allocator;
16const log = std.log;
17
18pub fn main(init: std.process.Init) !void {
19 const gpa = init.gpa;
20 const arena = init.arena.allocator();
21 const io = init.io;
22 const args = try init.minimal.args.toSlice(arena);
23
24 const grammar_path = args[1];
25 const out_path = args[2];
26 const check = args.len > 3 and mem.eql(u8, args[3], "--check");
27
28 const grammar = try Io.Dir.cwd().readFileAlloc(io, grammar_path, gpa, .unlimited);
29 defer gpa.free(grammar);
30
31 var parser: Parser = .init(gpa, grammar);
32 defer parser.deinit();
33
34 const root = try parser.parseGrammar() orelse {
35 log.err("Invalid grammar", .{});
36 std.process.exit(1);
37 };
38
39 var buffer: Io.Writer.Allocating = .init(gpa);
40 defer buffer.deinit();
41
42 var g: Generator = .init(&buffer.writer, &parser);
43 try g.genRoot(root);
44
45 const generated = try buffer.toOwnedSliceSentinel(0);
46 defer gpa.free(generated);
47
48 // Parse the generated Zig code and render it in the canonical format
49 var tree = try std.zig.Ast.parse(gpa, generated, .{});
50 defer tree.deinit(gpa);
51
52 if (tree.errors.len != 0) {
53 // This should never be reached, but helps a lot when debugging this script.
54 try std.zig.printAstErrorsToStderr(gpa, io, tree, "generated", .auto);
55 return error.ParseError;
56 }
57
58 if (check) {
59 const current = try Io.Dir.cwd().readFileAlloc(io, out_path, gpa, .unlimited);
60 defer gpa.free(current);
61 var aw: Io.Writer.Allocating = .init(gpa);
62 defer aw.deinit();
63 try tree.render(gpa, &aw.writer, .{});
64 if (!mem.eql(u8, current, aw.written())) {
65 std.log.err("grammar.peg modified without regenerating oracle", .{});
66 std.log.info("Run zig build gen-parser-oracle to regenerate", .{});
67 std.process.exit(1);
68 }
69 } else {
70 var out_file = try Io.Dir.cwd().createFile(io, out_path, .{});
71 defer out_file.close(io);
72 var out_buffer: [4096]u8 = undefined;
73 var out_writer = out_file.writer(io, &out_buffer);
74 const out = &out_writer.interface;
75
76 try tree.render(gpa, out, .{});
77 try out.flush();
78 }
79}
80
81const Generator = struct {
82 w: *Io.Writer,
83 p: *const Parser,
84 /// Suffix for generated identifiers, incremented for each nested scope to avoid shadowing,
85 /// Decremented at end of each generated scope to give smaller git diffs when regenerating
86 /// lib/std/zig/parser_generated_oracle.zig.
87 suffix: usize,
88
89 fn init(w: *Io.Writer, p: *const Parser) Generator {
90 return .{ .w = w, .p = p, .suffix = 0 };
91 }
92
93 const Error = Io.Writer.Error;
94 const Node = Parser.Node;
95
96 fn genRoot(g: *Generator, node: Node.Index) Error!void {
97 try g.w.writeAll(
98 \\//! This file is generated, do not edit manually! To generate, run:
99 \\//! zig build gen-parser-oracle
100 \\
101 \\const std = @import("std");
102 \\
103 \\const Error = error{MaxDepth};
104 \\const max_depth = 5;
105 \\
106 \\/// Returns true if the input source is in the language defined by
107 \\/// the grammar.
108 \\/// Returns error.MaxDepth if more than `max_depth` levels of recursion/iteration are reached.
109 \\pub fn parse(source: []const u8) Error!bool {
110 \\ var p: Parser = .{ .source = source, .i = 0, .depths = @splat(1) };
111 \\ return p.parseRoot();
112 \\}
113 );
114
115 const defs = g.p.getExtra(node.get(g.p).root);
116
117 // This enum exists to minimize git diffs in the generated oracle when
118 // the grammar is modified. It allows mapping from def name (stable) to
119 // def index (unstable).
120 try g.w.writeAll("const Def = enum {");
121 for (defs) |n| {
122 const def = n.get(g.p).def;
123 const id = def.id.get(g.p).id;
124 try g.w.print("def{s},", .{id});
125 }
126 try g.w.writeAll("};");
127
128 try g.w.print(
129 \\const Parser = struct {{
130 \\ source: []const u8,
131 \\ i: usize,
132 \\ depths: [{d}]u8,
133 , .{defs.len});
134 for (defs) |def| {
135 try g.genDef(def);
136 }
137 try g.w.writeAll("};");
138 }
139
140 fn genDef(g: *Generator, node: Node.Index) Error!void {
141 const def = node.get(g.p).def;
142 const id = def.id.get(g.p).id;
143 assert(g.suffix == 0);
144 try g.w.print("pub fn parse{s}(p: *Parser) Error!bool {{", .{id});
145 try g.w.print(
146 \\const def_index = @intFromEnum(Def.def{s});
147 \\if (p.depths[def_index] > max_depth) return error.MaxDepth;
148 \\p.depths[def_index] += 1;
149 \\defer p.depths[def_index] -= 1;
150 , .{id});
151 try g.w.writeAll("return ");
152 try g.genExpr(def.expr);
153 try g.w.writeAll(";}");
154 }
155
156 fn genExpr(g: *Generator, node: Node.Index) Error!void {
157 const suffix = g.suffix;
158 g.suffix += 1;
159 defer g.suffix -= 1;
160 try g.w.print(
161 \\blk_{d}: {{
162 \\const pos_{d} = p.i;
163 , .{ suffix, suffix });
164 for (g.p.getExtra(node.get(g.p).expr)) |seq| {
165 try g.w.writeAll("if (");
166 try g.genSeq(seq);
167 try g.w.print(") break :blk_{d} true;", .{suffix});
168 try g.w.print("p.i = pos_{d};", .{suffix});
169 }
170 try g.w.print("break :blk_{d} false; }}", .{suffix});
171 }
172
173 fn genSeq(g: *Generator, node: Node.Index) Error!void {
174 const items = g.p.getExtra(node.get(g.p).seq);
175 for (items, 0..) |item, i| {
176 if (i > 0) try g.w.writeAll(" and ");
177 try g.genNode(item);
178 }
179 }
180
181 fn genNode(g: *Generator, node: Node.Index) Error!void {
182 const suffix = g.suffix;
183 g.suffix += 1;
184 defer g.suffix -= 1;
185 switch (node.get(g.p)) {
186 .id => |id| try g.w.print("try p.parse{s}()", .{id}),
187 .expr => try g.genExpr(node),
188 .@"&" => |child| {
189 // XXX forbid unbounded lookahead
190 try g.w.print(
191 \\blk_{d}: {{
192 \\const pos_{d} = p.i;
193 \\const match_{d} =
194 , .{ suffix, suffix, suffix });
195 try g.genNode(child);
196 try g.w.print(
197 \\;
198 \\p.i = pos_{d};
199 \\ break :blk_{d} match_{d};
200 \\}}
201 , .{ suffix, suffix, suffix });
202 },
203 .@"!" => |child| {
204 // XXX forbid unbounded lookahead
205 try g.w.print(
206 \\blk_{d}: {{
207 \\const pos_{d} = p.i;
208 \\const match_{d} =
209 , .{ suffix, suffix, suffix });
210 try g.genNode(child);
211 try g.w.print(
212 \\;
213 \\p.i = pos_{d};
214 \\ break :blk_{d} !match_{d};
215 \\}}
216 , .{ suffix, suffix, suffix });
217 },
218 .@"?" => |child| {
219 try g.w.writeAll("(");
220 try g.genNode(child);
221 try g.w.writeAll(" or true )");
222 },
223 .@"*" => |child| {
224 try g.w.print(
225 \\blk_{d}: {{
226 \\var i_{d}: usize = 0;
227 \\while (
228 , .{ suffix, suffix });
229 try g.genNode(child);
230 try g.w.print(
231 \\) {{
232 \\ if (i_{d} > max_depth) return error.MaxDepth;
233 \\ i_{d} += 1;
234 \\}}
235 \\break :blk_{d} true; }}
236 , .{ suffix, suffix, suffix });
237 },
238 .@"+" => |child| {
239 try g.w.print(
240 \\blk_{d}: {{
241 \\var match_{d} = false;
242 \\var i_{d}: usize = 0;
243 \\while (
244 , .{ suffix, suffix, suffix });
245 try g.genNode(child);
246 try g.w.print(
247 \\) {{
248 \\ match_{d} = true;
249 \\ if (i_{d} > max_depth) return error.MaxDepth;
250 \\ i_{d} += 1;
251 \\}}
252 \\break :blk_{d} match_{d}; }}
253 , .{ suffix, suffix, suffix, suffix, suffix });
254 },
255 .@"." => {
256 try g.w.print(
257 \\blk_{d}: {{
258 \\ if (p.i < p.source.len) {{
259 \\ p.i += 1;
260 \\ break :blk_{d} true;
261 \\ }}
262 \\ break :blk_{d} false;
263 \\}}
264 , .{ suffix, suffix, suffix });
265 },
266 .literal => |literal| {
267 const bytes = g.p.strings.items[literal.off..][0..literal.len];
268 try g.w.print(
269 \\blk_{d}: {{
270 \\if (std.mem.startsWith(u8, p.source[p.i..], {q})) {{
271 \\
272 \\p.i += {d};
273 \\ break :blk_{d} true;
274 \\}}
275 \\break :blk_{d} false;
276 \\}}
277 , .{ suffix, bytes, bytes.len, suffix, suffix });
278 },
279 .class => |ranges| {
280 try g.w.writeAll("(p.i < p.source.len and switch (p.source[p.i]) {");
281 for (g.p.getExtra(ranges)) |n| {
282 const range = n.get(g.p).range;
283 try g.w.writeAll("'");
284 try std.zig.charEscape(range.start, g.w);
285 try g.w.writeAll("'...'");
286 try std.zig.charEscape(range.end, g.w);
287 try g.w.writeAll("',");
288 }
289 try g.w.print(
290 \\=> blk_{d}: {{ p.i += 1; break :blk_{d} true; }},
291 \\else => false,
292 \\}})
293 , .{ suffix, suffix });
294 },
295 .sof => try g.w.writeAll("(p.i == 0)"),
296 else => unreachable,
297 }
298 }
299};
300
301/// Parser implements a subset of the PEG grammar definition.
302/// We don't bother implementing the Action, BEGIN, and END rules
303/// and also omit unneeded character escape sequences.
304///
305/// The full PEG grammar found in the peg(1) man page:
306///
307/// Grammar <- Spacing Definition+ EndOfFile
308///
309/// Definition <- Identifier LEFTARROW Expression
310/// Expression <- Sequence ( SLASH Sequence )*
311/// Sequence <- Prefix*
312/// Prefix <- AND Action
313/// / ( AND / NOT )? Suffix
314/// Suffix <- Primary ( QUERY / STAR / PLUS )?
315/// Primary <- Identifier !LEFTARROW
316/// / OPEN Expression CLOSE
317/// / Literal
318/// / Class
319/// / DOT
320/// / Action
321/// / BEGIN
322/// / END
323///
324/// Identifier <- < IdentStart IdentCont* > Spacing
325/// IdentStart <- [a-zA-Z_]
326/// IdentCont <- IdentStart / [0-9]
327/// Literal <- ['] < ( !['] Char )* > ['] Spacing
328/// / ["] < ( !["] Char )* > ["] Spacing
329/// Class <- '[' < ( !']' Range )* > ']' Spacing
330/// Range <- Char '-' Char / Char
331/// Char <- '\\' [abefnrtv'"\[\]\\]
332/// / '\\' [0-3][0-7][0-7]
333/// / '\\' [0-7][0-7]?
334/// / '\\' '-'
335/// / !'\\' .
336/// LEFTARROW <- '<-' Spacing
337/// SLASH <- '/' Spacing
338/// AND <- '&' Spacing
339/// NOT <- '!' Spacing
340/// QUERY <- '?' Spacing
341/// STAR <- '*' Spacing
342/// PLUS <- '+' Spacing
343/// OPEN <- '(' Spacing
344/// CLOSE <- ')' Spacing
345/// DOT <- '.' Spacing
346/// Spacing <- ( Space / Comment )*
347/// Comment <- '#' ( !EndOfLine . )* EndOfLine
348/// Space <- ' ' / '\t' / EndOfLine
349/// EndOfLine <- '\r\n' / '\n' / '\r'
350/// EndOfFile <- !.
351/// Action <- '{' < [^}]* > '}' Spacing
352/// BEGIN <- '<' Spacing
353/// END <- '>' Spacing
354const Parser = struct {
355 gpa: Allocator,
356 /// PEG grammar source
357 source: []const u8,
358 /// Current index into source
359 i: u32,
360 nodes: std.ArrayList(Node),
361 extra: std.ArrayList(Node.Index),
362 strings: std.ArrayList(u8),
363
364 const Node = union(enum) {
365 /// Slice into extra
366 root: Slice,
367 def: struct {
368 id: Index,
369 expr: Index,
370 },
371 /// Slice into Parser.source
372 id: []const u8,
373 /// Slice into extra
374 expr: Slice,
375 /// Slice into extra
376 seq: Slice,
377 @"&": Index,
378 @"!": Index,
379 @"?": Index,
380 @"*": Index,
381 @"+": Index,
382 @".",
383 /// Slice into strings
384 literal: Slice,
385 /// Slice into extra
386 class: Slice,
387 range: struct {
388 start: u8,
389 end: u8,
390 },
391 /// Start of file
392 sof,
393
394 const Index = enum(u32) {
395 _,
396
397 fn get(index: Index, p: *const Parser) Node {
398 return p.nodes.items[@backingInt(index)];
399 }
400 };
401
402 const Slice = struct {
403 off: u32,
404 len: u32,
405 };
406 };
407
408 fn init(gpa: Allocator, source: []const u8) Parser {
409 return .{
410 .gpa = gpa,
411 .source = source,
412 .i = 0,
413 .nodes = .empty,
414 .extra = .empty,
415 .strings = .empty,
416 };
417 }
418
419 fn deinit(p: *Parser) void {
420 p.nodes.deinit(p.gpa);
421 p.extra.deinit(p.gpa);
422 p.strings.deinit(p.gpa);
423 }
424
425 // Grammar <- Spacing Definition+ EndOfFile
426 // EndOfFile <- !.
427 fn parseGrammar(p: *Parser) !?Node.Index {
428 var scratch: std.ArrayList(Node.Index) = .empty;
429 defer scratch.deinit(p.gpa);
430 _ = p.eatSpacing();
431 while (try p.parseDefinition()) |def| {
432 try scratch.append(p.gpa, def);
433 }
434 if (scratch.items.len == 0) return null;
435 if (p.peek() != null) return null;
436 const defs = try p.addExtra(scratch.items);
437 return try p.addNode(.{ .root = defs });
438 }
439
440 // Definition <- Identifier LEFTARROW Expression
441 fn parseDefinition(p: *Parser) !?Node.Index {
442 const id = try p.parseIdentifier() orelse return null;
443 if (!p.eatLeftArrow()) return null;
444 const expr = try p.parseExpression() orelse return null;
445 return try p.addNode(.{ .def = .{
446 .id = id,
447 .expr = expr,
448 } });
449 }
450
451 // Expression <- Sequence ( SLASH Sequence )*
452 fn parseExpression(p: *Parser) error{OutOfMemory}!?Node.Index {
453 var scratch: std.ArrayList(Node.Index) = .empty;
454 defer scratch.deinit(p.gpa);
455 while (try p.parseSequence()) |seq| {
456 try scratch.append(p.gpa, seq);
457 if (!p.eatSlash()) break;
458 }
459 if (scratch.items.len == 0) return null;
460 const seqs = try p.addExtra(scratch.items);
461 return try p.addNode(.{ .expr = seqs });
462 }
463
464 // Sequence <- Prefix*
465 fn parseSequence(p: *Parser) !?Node.Index {
466 var scratch: std.ArrayList(Node.Index) = .empty;
467 defer scratch.deinit(p.gpa);
468 while (try p.parsePrefix()) |primary| {
469 try scratch.append(p.gpa, primary);
470 }
471 const primaries = try p.addExtra(scratch.items);
472 return try p.addNode(.{ .seq = primaries });
473 }
474
475 // Prefix <- AND Action
476 // / ( AND / NOT )? Suffix
477 fn parsePrefix(p: *Parser) !?Node.Index {
478 if (p.eatAnd()) {
479 // We only support a single hardcoded "start of file" Action
480 if (p.eat('{')) {
481 // Action <- '{' < [^}]* > '}' Spacing
482 if (std.mem.startsWith(u8, p.source[p.i..], " (yy->__pos == 0) }")) {
483 while (!p.eat('}')) p.i += 1;
484 _ = p.eatSpacing();
485 return try p.addNode(.sof);
486 }
487 return null;
488 }
489 const suffix = try p.parseSuffix() orelse return null;
490 return try p.addNode(.{ .@"&" = suffix });
491 }
492 if (p.eatNot()) {
493 const suffix = try p.parseSuffix() orelse return null;
494 return try p.addNode(.{ .@"!" = suffix });
495 }
496 return try p.parseSuffix();
497 }
498
499 // Suffix <- Primary ( QUERY / STAR / PLUS )?
500 fn parseSuffix(p: *Parser) !?Node.Index {
501 const primary = try p.parsePrimary() orelse return null;
502 if (p.eatQuery()) {
503 return try p.addNode(.{ .@"?" = primary });
504 }
505 if (p.eatStar()) {
506 return try p.addNode(.{ .@"*" = primary });
507 }
508 if (p.eatPlus()) {
509 return try p.addNode(.{ .@"+" = primary });
510 }
511 return primary;
512 }
513
514 // Primary <- Identifier !LEFTARROW
515 // / OPEN Expression CLOSE
516 // / Literal
517 // / Class
518 // / DOT
519 // / Action
520 // / BEGIN
521 // / END
522 fn parsePrimary(p: *Parser) !?Node.Index {
523 const init_pos = p.savePos();
524 if (try p.parseIdentifier()) |id| {
525 const pos = p.savePos();
526 if (!p.eatLeftArrow()) {
527 p.restorePos(pos);
528 return id;
529 }
530 }
531 p.restorePos(init_pos);
532 if (p.eatOpen()) if (try p.parseExpression()) |expr| if (p.eatClose()) return expr;
533 p.restorePos(init_pos);
534 if (try p.parseLiteral()) |literal| return literal;
535 p.restorePos(init_pos);
536 if (try p.parseClass()) |class| return class;
537 p.restorePos(init_pos);
538 if (p.eatDot()) return try p.addNode(.@".");
539 // We don't implement Action, BEGIN, and END.
540 return null;
541 }
542
543 // Identifier <- < IdentStart IdentCont* > Spacing
544 // IdentStart <- [a-zA-Z_]
545 // IdentCont <- IdentStart / [0-9]
546 fn parseIdentifier(p: *Parser) !?Node.Index {
547 const start = p.i;
548 switch (p.next() orelse return null) {
549 'a'...'z', 'A'...'Z', '_' => {},
550 else => return null,
551 }
552 while (p.peek()) |cont| {
553 switch (cont) {
554 'a'...'z', 'A'...'Z', '_', '0'...'9' => p.i += 1,
555 else => break,
556 }
557 }
558 const id = p.source[start..p.i];
559 _ = p.eatSpacing();
560 return try p.addNode(.{ .id = id });
561 }
562
563 // Literal <- ['] < ( !['] Char )* > ['] Spacing
564 // / ["] < ( !["] Char )* > ["] Spacing
565 fn parseLiteral(p: *Parser) !?Node.Index {
566 const quote: u8 = if (p.eat('\'')) '\'' else if (p.eat('"')) '"' else return null;
567 const off = p.strings.items.len;
568 while (!p.eat(quote)) {
569 const byte = p.parseChar() orelse return null;
570 try p.strings.append(p.gpa, byte);
571 }
572 _ = p.eatSpacing();
573 return try p.addNode(.{ .literal = .{
574 .off = @intCast(off),
575 .len = @intCast(p.strings.items.len - off),
576 } });
577 }
578
579 // Class <- '[' < ( !']' Range )* > ']' Spacing
580 fn parseClass(p: *Parser) !?Node.Index {
581 var scratch: std.ArrayList(Node.Index) = .empty;
582 defer scratch.deinit(p.gpa);
583 if (!p.eat('[')) return null;
584 while (!p.eat(']')) {
585 const range = try p.parseRange() orelse return null;
586 try scratch.append(p.gpa, range);
587 }
588 _ = p.eatSpacing();
589 const ranges = try p.addExtra(scratch.items);
590 return try p.addNode(.{ .class = ranges });
591 }
592
593 // Range <- Char '-' Char / Char
594 fn parseRange(p: *Parser) !?Node.Index {
595 const start = p.parseChar() orelse return null;
596 const end = blk: {
597 if (p.eat('-')) {
598 break :blk p.parseChar() orelse return null;
599 }
600 break :blk start;
601 };
602 return try p.addNode(.{ .range = .{
603 .start = start,
604 .end = end,
605 } });
606 }
607
608 // Char <- '\\' [abefnrtv'"\[\]\\]
609 // / '\\' [0-3][0-7][0-7]
610 // / '\\' [0-7][0-7]?
611 // / '\\' '-'
612 // / !'\\' .
613 fn parseChar(p: *Parser) ?u8 {
614 if (p.eat('\\')) {
615 const c = p.next() orelse return null;
616 return switch (c) {
617 // Only the escape sequences actually used in the Zig grammar are implemented
618 'n' => '\n',
619 'r' => '\r',
620 't' => '\t',
621 '\'' => '\'',
622 '"' => '"',
623 '[' => '[',
624 ']' => ']',
625 '\\' => '\\',
626 '-' => '-',
627 '0'...'7' => {
628 // octal
629 if (c <= '3') {
630 const c2 = p.next() orelse return null;
631 if (c2 < '0' or c2 > '7') return null;
632 const c3 = p.next() orelse return null;
633 if (c3 < '0' or c3 > '7') return null;
634 return (c - '0') * 8 * 8 + (c2 - '0') * 8 + (c3 - '0');
635 } else {
636 if (p.peek()) |c2| {
637 if (c2 >= '0' and c2 <= '7') {
638 p.i += 1;
639 return (c - '0') * 8 + (c2 - '0');
640 }
641 }
642 return (c - '0');
643 }
644 },
645 else => null,
646 };
647 } else {
648 return p.next();
649 }
650 }
651
652 // LEFTARROW <- '<-' Spacing
653 fn eatLeftArrow(p: *Parser) bool {
654 return p.eat('<') and p.eat('-') and p.eatSpacing();
655 }
656
657 // SLASH <- '/' Spacing
658 fn eatSlash(p: *Parser) bool {
659 return p.eat('/') and p.eatSpacing();
660 }
661
662 // AND <- '&' Spacing
663 fn eatAnd(p: *Parser) bool {
664 return p.eat('&') and p.eatSpacing();
665 }
666
667 // NOT <- '!' Spacing
668 fn eatNot(p: *Parser) bool {
669 return p.eat('!') and p.eatSpacing();
670 }
671
672 // QUERY <- '?' Spacing
673 fn eatQuery(p: *Parser) bool {
674 return p.eat('?') and p.eatSpacing();
675 }
676
677 // STAR <- '*' Spacing
678 fn eatStar(p: *Parser) bool {
679 return p.eat('*') and p.eatSpacing();
680 }
681
682 // PLUS <- '+' Spacing
683 fn eatPlus(p: *Parser) bool {
684 return p.eat('+') and p.eatSpacing();
685 }
686
687 // OPEN <- '(' Spacing
688 fn eatOpen(p: *Parser) bool {
689 return p.eat('(') and p.eatSpacing();
690 }
691
692 // CLOSE <- ')' Spacing
693 fn eatClose(p: *Parser) bool {
694 return p.eat(')') and p.eatSpacing();
695 }
696
697 // DOT <- '.' Spacing
698 fn eatDot(p: *Parser) bool {
699 return p.eat('.') and p.eatSpacing();
700 }
701
702 // Spacing <- ( Space / Comment )*
703 fn eatSpacing(p: *Parser) bool {
704 while (p.eatSpace() or p.eatComment()) {}
705 return true;
706 }
707
708 // Comment <- '#' ( !EndOfLine . )* EndOfLine
709 fn eatComment(p: *Parser) bool {
710 if (!p.eat('#')) return false;
711 while (!p.eatEndOfLine()) p.i += 1;
712 return true;
713 }
714
715 // Space <- ' ' / '\t' / EndOfLine
716 fn eatSpace(p: *Parser) bool {
717 return p.eat(' ') or p.eat('\t') or p.eatEndOfLine();
718 }
719
720 // EndOfLine <- '\r\n' / '\n' / '\r'
721 fn eatEndOfLine(p: *Parser) bool {
722 return p.eat('\r') | p.eat('\n');
723 }
724
725 fn peek(p: *Parser) ?u8 {
726 if (p.i < p.source.len) {
727 return p.source[p.i];
728 }
729 return null;
730 }
731
732 fn next(p: *Parser) ?u8 {
733 if (p.i < p.source.len) {
734 defer p.i += 1;
735 return p.source[p.i];
736 }
737 return null;
738 }
739
740 fn eat(p: *Parser, byte: u8) bool {
741 if (p.i < p.source.len and p.source[p.i] == byte) {
742 p.i += 1;
743 return true;
744 }
745 return false;
746 }
747
748 fn addNode(p: *Parser, node: Node) !Node.Index {
749 try p.nodes.append(p.gpa, node);
750 return @fromBackingInt(@intCast(p.nodes.items.len - 1));
751 }
752
753 fn addExtra(p: *Parser, nodes: []const Node.Index) !Node.Slice {
754 const off = p.extra.items.len;
755 try p.extra.appendSlice(p.gpa, nodes);
756 return .{ .off = @intCast(off), .len = @intCast(p.extra.items.len - off) };
757 }
758
759 const Pos = struct {
760 i: u32,
761 nodes_len: u32,
762 extra_len: u32,
763 strings_len: u32,
764 };
765
766 fn savePos(p: *const Parser) Pos {
767 return .{
768 .i = p.i,
769 .nodes_len = @intCast(p.nodes.items.len),
770 .extra_len = @intCast(p.extra.items.len),
771 .strings_len = @intCast(p.strings.items.len),
772 };
773 }
774
775 fn restorePos(p: *Parser, pos: Pos) void {
776 assert(p.i >= pos.i);
777 p.i = pos.i;
778 p.nodes.shrinkRetainingCapacity(pos.nodes_len);
779 p.extra.shrinkRetainingCapacity(pos.extra_len);
780 p.strings.shrinkRetainingCapacity(pos.strings_len);
781 }
782
783 fn getExtra(p: *const Parser, s: Node.Slice) []const Node.Index {
784 return p.extra.items[s.off..][0..s.len];
785 }
786};