╭─────────────╮ │scroll to top│ ╰─────────────╯ ╭ gen_parser_oracle.zig ────────────────────────────────────────╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───────────────────────────────────────────────────────────────╯
🬂🬂🬒 🬂🬰🬂 🬑🬂🬀 ╭master╮ master xeubie: 🬋 🬋 🬃🬇🬋 │files │ commits refs discuss issues patches new login 🬯🬭🬭 🬭🬰🬭 🬟🬭🬑 ╰──────╯ (15882) user
╭ find file ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╮ ╭────╮ ╭ clone ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╮ │ │ │http│ ssh │ │ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─╯ ╰────╯ ╰ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ╯
.. crc/ loongarch/ spirv/ bsp.zig check_mingw.zig compiler_gdb_pretty_printers.py docgen.zig doctest.zig dump-cov.zig fetch_them_macos_headers.zig gen_loongarch_encoding.zig gen_macos_headers_c.zig gen_outline_atomics.zig ╭─────────────────────────────────╮ │gen_parser_oracle.zig │ ╰─────────────────────────────────╯ gen_spirv_spec.zig gen_stubs.zig generate_JSONTestSuite.zig generate_linux_syscalls.zig incr-check.zig macos-headers.c migrate_langref.zig process_headers.zig unskip_spirv_tests.zig update-linux-headers.zig update_clang_options.zig update_cpu_features.zig update_crc_catalog.zig update_freebsd_libc.zig update_glibc.zig update_mingw.zig update_netbsd_libc.zig update_openbsd_libc.zig
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 354 const 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 }; 787