v1.20.0

The parser core was rebuilt on the structure of v1.17.0. Every change made since then was redone one at a time, each checked against the previous implementation: its tests, and the full ASTs, error messages and callbacks on C11, SQL, culebra and 200 random grammars. The public API is the same as in v1.19.1, and peglib.h is about 250 lines shorter.

⚠️ Changes to be aware of

Expected tokens in syntax errors

A failure at the position of the error used to replace the list of expected tokens, unless it came from a later alternative of the choice being parsed. So the list depended on which failure came last, and packrat parsing could change it.

• The list is now what every failure at the furthest position expected, as in PEG parsers for other languages (Peggy, pest, Ohm): expecting ']' can become expecting ',', ']'.
• A literal that the grammar has in more than one place is listed once: expecting '+', '+' becomes expecting '+'.
• The tokens are listed in the order the parser first tried them.
• What %whitespace fails to match while it is skipped is never listed and does not move the position of the error. A comment that is never closed is reported where it starts: with S <- 'a' 'b' and /* */ comments in %whitespace, the input a /* x gave 1:7 syntax error, expecting '*/', <S>, '*/' and now gives 1:3 syntax error, unexpected '/', expecting 'b'.
• With packrat parsing, a failure that is reused instead of tried again lists nothing more, so the name of a token rule can be missing when a rule it uses has already failed at that position outside it. The README describes this.

If your tests compare error messages, expect some of them to change. This change alone does not change whether a parse succeeds.

leave handlers and exceptions

When an exception thrown by an action, a predicate or a handler leaves the parser, the leave handlers of the rules it passes through no longer run. They used to run with a failure they had nothing to do with, and a leave handler that threw terminated the program.

ASTs

• enable_ast(true) builds each node as soon as its rule matches. The deferred building of v1.18.0 is gone, with the same trees (see Performance for the speed). During the parse, a node that packrat parsing or left recursion reuses can point to a parent built for an alternative that was abandoned, instead of having none. As before, parent is guaranteed once parse has returned.
• enable_ast() links the parents of the tree again before it is returned (see Fixes). A zero-length node that packrat parsing put under two parents is copied for the second, so such a node in the returned tree can be another object than the one an action or a leave handler saw.

enable_profiling()

The report is written once, when the parse ends. A start rule that matches inside itself used to report once for each of its matches.

ABI

The layouts of Definition, Context, SemanticValues, ErrorInfo and Ope changed, which changes the ABI.

🐛 Fixes

Precedence rules

• Operator given through a macro: with OPM(X) <- PLUS / X as the operator, the rule kept the token of an alternative that had failed and folded 1 + 2 * 3 as (1 + 2) * 3. With OPM(X) <- PLUS '!' / X, the right-associative 1 += 2 += 3 was folded from the left. An operator behind a lookahead in a macro (OPM(X) <- &PEEK X) did not parse at all. The operator is now the first match that remains in the rule's own values.
• After a recovered error: once %recover had recovered from an error, operator rules no longer handed over their tokens, so every later expression stopped at its first operand and its first operator was reported as one more error.
• Operator rule defined with ~: without packrat, an expression could stop at its first operand.
• Operator rule memoized by packrat: an expression stopped at an operator whose match came from the cache.
• Left-recursive operator rule: O <- O '*' / [-+*] folded 1**2+3 as 1 ** (2+3), and O <- O '!' / < [-+*] > failed after a lookahead had parsed O at the operator.

Packrat and left recursion

• Matches inside and outside a token: inside a token, a no_whitespace rule or the whitespace itself, no whitespace is skipped, so a rule can match differently there than at the same position elsewhere. The packrat cache and the left-recursion memo handed a match from one place to the other: with %whitespace, TYPE <- < NAME > followed by NAME '/' NAME at the same position failed on x / y with packrat, and a left-recursive rule used the same way failed with or without it. The two are now kept apart.
• Left recursion across a token boundary: matches made inside a token while a left-recursive rule grew outside it were kept, so a later parse inside the token depended on whether the rule had been parsed outside first.
• Combinators: a rule that reaches itself at its own start, such as A <= cho(seq(A, chr('b')), chr('a')), overflowed the stack while the parser worked out which rules can match empty.

Values

• A value that a leave handler put in place of its rule's did not reach an action above it when the rules in between had no action.
• With a whitespace operator set on a Definition without wsp(), the values of the rules it matched did not reach the action of the rule being parsed.

Cut in a lookahead

A rule that cannot start with the next byte is not entered (v1.19.0). That also skipped a cut inside a lookahead in it: with S <- 'x' R / 'x' 'c', R <- !E 'b', E <- ↑ 'a', the input xc parsed. Such a rule is entered again.

Exceptions with GCC 12 to 14 and assertions enabled

In a build with assertions enabled, a parse that an exception left (the nesting limit of set_max_depth, or an exception thrown by an action) aborted on an assertion in ~Context when the grammar had a cut or a recovery (↑, ^label, %recover). GCC 12 to 14 drop a std::vector<bool>::pop_back() from the cleanup that runs while an exception propagates, which left the parser's stack of cuts unbalanced. That stack is no longer a std::vector<bool>. Builds without assertions were not affected.

Building with GCC 11

peglib.h did not compile with GCC 11 since v1.18.0: enable_ast called a member template through a variable that GCC 11 treats as dependent, without the template keyword (expected primary-expression before '>' token). (#344)

AST parents with enable_ast()

A node reused from the packrat cache or a left-recursive rule's memo could end up in the tree with a parent that had been discarded. enable_ast(true) already linked the finished tree again; enable_ast() does the same now.

leave handlers

A leave handler that threw terminated the program. The exception now reaches the caller of parse.

enable_profiling()

A parse cut short by an exception or by set_max_depth reported nothing.

⚡ Performance

Instructions of one parse against v1.19.1, with identical output in every mode. C11 is the grammar of #343 on a 3.1MB preprocessed sqlite3.c; culebra is its corpus of 295 source files, parsed with a logger set.

ASTs with packrat parsing

With packrat parsing, a rule match whose value no parse from the start rule ever reads, such as one below a ~ rule, in a token or in a lookahead, is now neither built nor cached.

• enable_ast(true): C11 16.6G -> 11.3G instructions (-32%), peak RSS 1151MB -> 794MB. culebra 14.3G -> 10.4G (-27%), 55MB -> 35MB.
• enable_ast(): C11 24.8G -> 17.4G (-30%), 1904MB -> 1564MB. culebra 16.2G -> 12.4G (-24%).

ASTs without packrat parsing

• enable_ast(): C11 29.8G -> 22.3G instructions (-25%).
• enable_ast(true): C11 14.2G -> 14.1G, and peak RSS 308MB -> 199MB, now that nodes are built right away (see Changes).

Recognition

Without a tree, C11 takes between 4.5% fewer and 2.9% more instructions depending on the mode, and culebra with packrat 4.4% more.

An SQL grammar on a 1.2MB script is within 3% in every mode.

🧹 Repository

• The test suite is built once and runs a second time with every grammar reloaded from its blob, chosen by an environment variable. The test build takes half as long.
• CI also runs the tests with assertions enabled.
• The README says in which positions columns count bytes and in which codepoints, and when packrat parsing pays: it trades memory, which grows with the input and with the values or AST nodes it keeps, for the rules it need not try again, so a grammar that seldom tries a rule again at one position can be faster without it.