Skip to content

v1.23.0

Choose a tag to compare

View all tags
@yhirose yhirose released this 20 Oct 21:29
· 5 commits to master since this release
v1.23.0
6a6d425

This release fixes bugs found while auditing the documents and the structure of the parser: error reports, packrat parsing, left recursion, macros, and the checks made when a grammar is loaded. Many of the fixes change what a grammar loads, matches or reports, and blobs must be written again, so please read the first section before upgrading.

⚠️ Changes to be aware of

Grammar blobs

Blobs are now PEG4: load_blob() returns false for a blob written by v1.21.0 or v1.22.0. Write them again with serialize_grammar(). A recovery (^label, %recover(e)) is now held as itself instead of as a call of a built-in %recover macro, and %recover is no longer one of the grammar's rules.

A blob is also checked for what only the text loader made sure of. A rule without a body, which parser["Typo"] = ... makes for a name the grammar does not define, is left out of a blob; such a blob used to crash load_blob(). A blob that holds a missing operator, a class without a range, or parameters on a rule that is not a macro is rejected.

Grammars that no longer load

  • A repetition of something that can match empty is found wherever it is reached. It used to be missed in an element after one that consumes, at the start of a sequence under a repetition, in an argument of a recursive macro call, and in a rule made with the combinators that repeats itself. Such a repetition stops at its first empty match, so these grammars ran, but not as written: 
    S <- (A ';')*        # 2:10 infinite loop is detected in 'B'.
A <- 'a' B*
B <- 'b'?
    Line <- (Sp* Word)* with Sp <- ' '? and S <- (('a'?)* 'b')* are rejected too. Where loops are several or rules form a cycle, the rule reported can differ: for S <- A and A <- S*, it is now 2:6 infinite loop is detected in 'S'. instead of 1:6 ... 'A'.
  • A cut matches empty in these checks, so S <- (↑ / 'a')* is rejected as ('' / 'a')* is.
  • A %word that can match the empty string is rejected: '%word' can match the empty string. With %word <- [a-z]*, every word-like literal used to fail. A lookahead counts as possibly empty, so %word <- &[a-z] [a-z]*, which worked, is rejected too. Write [a-z]+.
  • A macro parameter called with arguments, as x('b') in M(x) <- x('b') 'c', is reported as 'x' is not macro. The arguments used to be dropped.
  • %whitespace or %word defined as a macro, as %whitespace(x) <- [ ]*, is reported as '%whitespace' cannot be a macro.
  • A rule made with the combinators and given in Rules is now known to match empty when it can, so a grammar that reaches one can report an infinite loop or a %word that can match empty, as the same grammar written out does.

Error reports

Error reports no longer depend on shortcuts or on packrat parsing: they list what a parse that tries everything would list.

  • Packrat parsing: a reused result lists what parsing the rule again would. With S <- R 'x' / T, T <- < R 'y' > and R <- 'a' [b], ac reported expecting <R>. with packrat parsing and expecting <R>, <T>. without. It is now expecting <R>, <T>. with both. After a recovery that reported a custom message, a reused result still lists none of its failures from before the report (see the README).
  • Skipped alternatives: an alternative skipped because it cannot start with the next byte lists what trying it would. With S <- A / B, A <- ('x' / 'y') 'z' and B <- [0-9] 'w', q now reports expecting 'x', 'y', <B>. instead of expecting <A>, <B>. Some reports list more, and some grammar load errors are reported further on: S <- 'a' { error_message } is a syntax error at 1:26 instead of 1:12.
  • The operand of ! reports nothing: its failures are not listed and its messages are not given, as in Peggy, Ohm and pest. With Ident <- !Keyword < [a-z]+ > and Keyword <- 'let' / 'if' / 'else', let 1 = 2 reports expecting <Ident>. instead of expecting 'let', 'if', 'else', <Ident>.
  • A custom message stands only where its failure is the error, as Peggy counts a named rule's failure:
    • With E <- N (Op N)* and Op <- [+-] { error_message "expected an operator" }, Op fails at the end of every expression, so 1+2;3+; reported 1:4 expected an operator. It now reports 1:7 syntax error, unexpected ';', expecting <N>.
    • A message given by an alternative tried later no longer hides an error that an earlier alternative went further to. With S <- Let / Expr and a message on Expr, let x = ; reported 1:1 bad expression and now reports 1:9 syntax error, unexpected ';', expecting <Num>.
    • No rule in %whitespace gives a message. A comment rule with error_message "unterminated comment" in %whitespace took over errors where the whitespace stops, such as at the end of the input. To report an unterminated comment, give it a recovery label: 
      Comment      <- '/*' (!'*/' .)* '*/'^unterminated
unterminated <- '' { error_message "unterminated comment" }
  • Labels (ErrorReport::label and the rule passed to a logger):
    • An error that a recovery reports is labeled with its recovery label, whether or not the label has an error_message. Without one, the label used to be the first rule expected, or empty.
    • Other errors no longer keep the label of an earlier message. With S <- A? 'x' and A <- 'a' { error_message "bad a" }, expected end of input on xy was labeled A, and now has no label.
  • A recovery reports once where it runs. Where backtracking parsed a rule again at the same position, its recovery reported again whatever was pending, such as what an abandoned alternative expected. With Item <- Labeled / Stmt and Labeled <- Stmt ':' Stmt, a statement missing its ; also reported expecting ':'. without packrat parsing. It now reports the missing ; only, with or without packrat parsing.
  • An undefined back reference sets its message as other messages do: only where errors are reported, and not over a message at or after its position.

Parse results

  • A cut or a recovery in a lookahead (& or !) no longer commits the choice around the lookahead. With Item <- !Decl Expr ';' / 'let' Name ';' / Decl and Decl <- 'let' ↑ Name '=' Expr ';', let x; and let x = 1; failed and now match.
  • A recovery in the operand of ! recovers without reporting an error or failing the parse: S <- !('x' ';'^semi) . / 'x' 'y' failed on xy and now matches.
  • Packrat parsing and cuts: a rule with a cut or a recovery that commits the choice around it is not memoized, as a rule with captures is not. With Func <- Sig Block / Sig ';' and Sig <- 'fn' ↑ Name '(' ')', fn matched with packrat parsing only. It now fails with both.
  • %whitespace and token boundaries: a rule used where no whitespace is skipped (in a token boundary, a { no_whitespace } rule or the whitespace) is parsed there apart from its uses elsewhere, as if it had a copy there that skips no whitespace. A rule that calls itself in its own token boundary therefore grows only inside it: Q <- < Q '.' I / I > matches a single I. It used to accept a.b.c, but also a .b, carrying whitespace into the token. Put the recursion in a rule of its own: Q <- < QBody > with QBody <- QBody '.' I / I. Without %whitespace, nothing changes.
  • Left recursion: a match built from an earlier seed was reused after the seed changed, so S <- &S G / 'a' with G <- S 'z' / 'q' rejected azz. It now matches. In left-recursive grammars, rules are entered and actions run far fewer times.
  • Macros:
    • A macro instance that is not left-recursive fails where it is entered again at the position where it is being parsed, as a rule does. With S <- Pair(E, T), E <- Pair(E, T) / T and Pair(A, B) <- A '+' B, S now matches 1+2 but not 1+2+3; it matched neither. M(x) <- x M('b'*) / 'c' used to overflow the stack.
    • ~ on a macro's definition throws its values away: with ~M(x) <- x, S <- A M(B) received the value of B and now does not.
    • A macro parameter named like a rule is no longer taken for that rule: with S <- x, x <- M('a') and M(x) <- x 'b', the rule x was taken to be left recursive, and with left recursion disabled the grammar did not load.
  • Dictionaries: a word gets the choice index it is first listed at. With 'January' | 'Jan', vs.choice() for Jan was 0 and is now 1.
  • {n,m} with m below n acts as {n} everywhere: [0-9]{2,1} rejected 12.

Callbacks, tracing and nesting limits

  • With a logger or an error reporter, a rule that cannot start with the next byte is skipped as it is without them, so its enter and leave handlers do not run. A rule that gives a message or is left-recursive is tried instead of skipped where errors are reported or nesting is limited. The same rules are entered with or without a logger.
  • Under set_max_depth, a skipped rule counts no level. With a tracer, which enable_tracing and enable_profiling set, such a rule is still entered, so the limit can be reached a few levels sooner.
  • A trace no longer shows what a recovery skips unless it is verbose, and no longer shows a %recover rule.

API and ABI

  • ErrorInfo::add takes different arguments, and FirstSet::failures replaces first_literal and first_rule.
  • New: Context::reports_errors.
  • Removed: Context::in_token_boundary_count (Context::skips_no_whitespace is now a member), Reference::get_core_operator, and the enable_shared_from_this base of seven operator types.
  • The layouts of Context, ErrorInfo, Recovery and other types changed, which changes the ABI.

🐛 Fixes

  • Crashes:
    • Loading a grammar given a combinator rule that refers to itself, as NUM <= seq(cls("0-9"), opt(NUM)) in Rules, overflowed the stack.
    • Left recursion through a cut went unseen: S <- M('x') with M(x) <- 'a' / ↑ !M('b') overflowed the stack.
    • Arithmetic on a null pointer, undefined behavior, where a parse stops before the end of its input.
  • Exponential time (process times on the shapes below, v1.22.0 -> v1.23.0):
    • Parsing a ladder of left-recursive rules, E1 <- E1 'a' E2 / E2, E2 <- E2 'b' E3 / E3, ...: 24 levels, 7.5 s -> 43 ms.
    • Loading levels that each start with the next in two alternatives, ending in a left-recursive rule: 22 levels, 1.6 s -> 33 ms. Such levels under a repetition: 23 levels, 0.8 s -> 47 ms.
    • Loading a chain of macros that each pass their parameter twice, A1(x) <- A2(x x), ...: 24 levels, 1.6 s -> 26 ms.
    • Error reporting dropped repeated expected items in quadratic time, which a grammar listing hundreds of keywords at one position pays at the end of every input.
  • Packrat parsing:
    • A rule used in %whitespace and in tokens could make the whole error vanish (since v1.20.0): with %whitespace <- (R / ' ')* and T <- < R 'y' >, the parse reported nothing.
    • Where left recursion detection misses a cycle that a macro argument brings, packrat parsing could change the result. Packrat parsing now stops for the rest of the parse where that shows.
  • Rules made with the combinators that can match empty were taken not to: with X <= opt(chr('x')) in Rules and B <- A 'b' / X, br did not parse. A combinator start rule whose whitespace differs from the grammar's %whitespace could fail where it should match.

🛠 Tools

  • peglint gives its hints about speed, such as alternatives that start with the same rule, only with --hints. The README's calculator used to print two such warnings. The warning about a literal before a predicate (#319), which is about correctness, still prints by default.
  • cd lint; cmake .. builds peglint with a compiler that defaults to C++14, and pl0's Makefile builds with Homebrew LLVM.

📝 Documentation

  • The README matches the code: $( ... ) and %recover( ... ) in the syntax list, the repetition forms and ←; a precedence instruction's first entry binds the loosest (the README said the opposite); the forms of a semantic action; where whitespace is skipped; the fields of an AST node; tracing, profiling and set_max_depth.
  • New limitations in the README: a left-recursive macro whose recursive call wraps its parameter, as Sum(A) <- Sum(A / 'x') '+' A / A, overflows the stack (set_max_depth makes it fail with an error instead); packrat parsing inside !; and what a reused result misses across a recovery.
  • The Java example of error recovery recovers by tokens instead of statements.
  • CI compiles every C++ example in the READMEs and checks every peglint example against what peglint prints.

⚡ Performance

Instructions of one parse against v1.22.0. The large grammar is the grammar of DuckDB's PEG parser ported to cpp-peglib (about 1,100 rules), on a 1.2MB SQL file with packrat parsing.

  • Left-recursive grammars: grammar/monkey_left_recursive.peg on 100KB of Monkey programs, 5.48G -> 0.26G instructions (-95%), 546ms -> 24ms; with packrat parsing, -87%. grammar/pl0_left_recursive.peg on 200KB of PL/0, -50%; with packrat parsing, -44%.
  • With a logger: the large grammar, 4.84G -> 3.74G (-23%), whether the input is valid or fails near its end. benchmark/data/sql.peg without packrat parsing, -8.6%.
  • With set_max_depth: the large grammar, -15%.
  • Slower: without a logger, the large grammar takes 3.0% more for recognition, 3.5% more with enable_ast(true) and 2.3% more with enable_ast(). benchmark/data/sql.peg takes up to 1.0% more, and the calculator of the README's macro example 1.1% more, or 9.3% more with a logger.
  • Loading a grammar: the same or a little less (-0.2% to -2.4%).
Assets 2
Loading