v1.19.0

🐛 Fixes

Deep ASTs no longer crash

A long chain of left-associative operators, such as 1+1+...+1 with a precedence rule, gives a tree as deep as the chain, and several places walked it recursively until the stack overflowed.

• Releasing an AST recursed through each node's destructor and overflowed from about 130k levels in a Release build. It now releases the nodes in a loop.
• enable_ast(true) with a precedence rule recorded each fold to be built later, and building the records of a long chain recursed as deep as the chain (overflow from about 60k operators). A fold now builds its node right away.
• set_max_depth(n) and precedence rules: the right operand of an operator was parsed by a nested call that was not counted, so a long chain of right-associative operators overflowed the stack even with a limit set. Each right operand in progress now counts as one level.
• set_max_depth(n) and the returned AST: a tree can be deeper than the parse ever nested (left-associative folds, left recursion, packrat reusing a subtree). When a parse returns an AST under a limit, the tree is now checked once, in a loop, and one deeper than the limit fails the parse with the same "exceeded the maximum nesting depth" error, labeled with the first node past the limit.

optimize_ast(), ast_to_s() and user code still walk a tree recursively. The README now recommends enable_ast(true) over optimize_ast() together with set_max_depth(n) for such input.

Repetitions that can match empty no longer loop forever

A repetition whose element matched without consuming input repeated it forever, adding values until memory ran out.

• At run time, an unbounded repetition now ends at a match that consumes nothing, and so does a precedence rule's loop over operators and operands. This also covers grammars built with combinators, which are never checked.
• At load time, the check for such repetitions assumed that a rule reached again while checking could not match empty, so R <- R*, A <- ('x' / A)* and A <- 'a'* A* loaded and then looped on every input. They are now rejected, as in other PEG tools, and the error names the rule and its position instead of in ''.

Precedence rules

• An action received only the first value of each operand, with no tag: an operand without a value (an operator rule defined with ~) was read out of range, and further values were dropped. Every operand value now reaches the action with its tag.
• A precedence instruction in a macro folded in the caller's values before the macro.
• The captures made while trying an operator that the rule did not use were kept, so a later back reference could match against them.
• When the atom can match empty, the rule can start with an operator, but its first set left the operator out, so a choice could skip it.

Captures and back references

• A capture viewed its name in the grammar text, so a grammar loaded from a string that was then freed compared back references against freed memory.
• With packrat parsing, a rule whose match records or reads captures (directly, through the rules below it, or through a %whitespace that captures) was memoized, and a cache hit left its captures out. Such rules are no longer memoized.

First sets

A choice skips an alternative whose first set excludes the next byte, so a first set that misses a byte drops a valid parse. These cases were missed:

• A left-recursive rule that can match empty (A <- A 'x' / '').
• A cut before the first byte, which must stop the enclosing choice even when the expression then fails.
• %whitespace skipped after an empty match of a literal, a token boundary or a no_whitespace rule (T <- 'y' / '' 'x' failed on " x").

Parser without a grammar

enable_ast(), optimize_ast() and serialize_grammar() crashed on a parser whose grammar failed to load. They now do nothing, like the other methods.

⚡ Performance

Rules that cannot start with the next byte are not entered

A choice already skipped an alternative that cannot start with the next byte. A rule reference now does the same, saving the whole cost of a rule call, wherever entering the rule would run no callback, so the result of a parse does not change. A parse with a logger, a tracer or a nesting limit still enters it. C11 grammar on a 3.1MB sqlite3.c without a logger: recognition -15.7% instructions, enable_ast(true) -11.6%. SQL big.sql -2.2%.

Precedence rules

Operands are parsed into the expression's values instead of a fresh copy of the scope, and an unused operator is rolled back like an unused alternative. A 1MB expression with a calculator grammar: -28% instructions with value actions, -14% with enable_ast(true).

Smaller cuts

• A failed match rolls back only what it added. C11 recognition -5.8% instructions, enable_ast(true) -3.3%.
• A macro argument's operands are moved instead of copied. A grammar that passes sequences to macros: -8% instructions.

⚠️ Changes to be aware of

• Grammars such as R <- R* and A <- 'a'* A* are now rejected when loaded (see Fixes). They never parsed without looping.
• An unbounded repetition stops at a match that consumes nothing. A parse that terminated before is unaffected, unless such a match changes a capture so that the next round would consume.
• With enable_ast(true), the nodes of a precedence expression are built even in an alternative that is abandoned later. An input parsed whole by a first alternative that then fails: +24% instructions.
• With set_max_depth(n), right operands of precedence rules count against the limit, and a returned AST is checked against it. With enable_ast() on a large input, the check adds about 0.4% instructions and 15% cycles; with enable_ast(true) it costs nothing measurable.
• AstBase now declares its destructor and defaults its copy and move constructors, which changes the ABI.
• The README now says that the callbacks of an attempt that is later abandoned may run any number of times, including zero (packrat, left recursion, skipped alternatives). Pair state changes in enter and leave, or build the state from what the parse returns.

🧹 Repository

• CI compiles with four parallel jobs; the slowest job went from about 21 to 12 minutes.