v1.18.0

⚡ Performance

Most of this release comes from issue #343, a C11 grammar parsing a 3.1MB preprocessed sqlite3.c. All numbers below are from the commit messages, measured in Release builds with alternating A/B runs against the previous commit.

Selective packrat memoizes less and lays its table out better

• The packrat length table is laid out rule-major, so pages that belong to a rule that rarely succeeds are never touched. C11 with packrat: peak RSS 809MB -> 442MB.
• A rule is no longer memoized when every alternative reaches it only through one and the same shared rule, since that rule already answers from its own cache entry. C11 cached rules 65 -> 28, peak RSS 442MB -> 247MB; culebra 80 -> 19 cached rules and 4-11% faster.

Parsing without packrat

• A rule re-entering the position it is already being parsed at is now guarded with a per-rule array instead of a std::map insert and erase on every call. C11 recognition 2.59s -> 1.61s, culebra's test corpus 16.1s -> 9.3s.
• Plain rules no longer push an empty argument frame.

Left recursion is linear in the input length

Every growth step used to walk all of lr_memo to clear stale entries, which made left-recursive parses quadratic. pl0_left_recursive on 390KB: about 20s -> 76ms.

AST construction

• enable_ast(true) builds the optimized tree directly, collapsing single-child nodes as they are built instead of copying the whole tree in optimize_ast(). C11: 4.41s -> 2.87s, peak RSS 1.41GB -> 265MB.
• A collapsed node takes its child's place when nothing else shares the child, and a rule's values are released right after its action runs, so fewer nodes are copied.
• With enable_ast(true), AST nodes are built only for the rule matches that end up in the tree. The actions are recorded and run later, when user code could first see the node. C11 AST parse 1.85s -> 1.50s, culebra corpus -21%. Grammars where nearly every node is kept, or where every rule has a predicate or a leave handler, can get up to about 25% slower. Packrat, left recursion and tracers keep building nodes right away.

Values that nothing reads are not built

A rule match whose value is never read (inside ~, & and !, below a token rule, or below a rule without an action whose own value is unread) or is always empty now runs on the recognizer path, even in AST parses and with a logger set. This replaces the old recognizer mode, which applied only when no rule had any callback. C11 with a logger: recognition 1.10s -> 0.78s, enable_ast(true) parse 1.43s -> 1.32s. Grammars without callbacks stay within about 2%.

Smaller cuts

• Expected tokens for error messages are recorded lazily when a logger is set.
• A rule's name is hashed into its AST tag once.
• The trace path moved out of Ope::parse, so the hot path is small enough to inline everywhere.

✨ New

parser::set_max_depth(n)

Deeply nested input, such as a few thousand (s, makes the parser recurse until the stack overflows and the process crashes. With set_max_depth(n), a parse that has more than n rule matches in progress at once fails instead, reporting "exceeded the maximum nesting depth of n" with the rule entered there as its label. Reaching the limit abandons the whole parse; no more actions, predicates or leave handlers run. There is no limit by default, and a parse without one pays only for a branch.

enable_ast(collapse_mode, opt_mode)

enable_ast takes the options of optimize_ast and builds the optimized tree directly (see Performance). The defaults keep the previous behavior.

🐛 Fixes

• Packrat ids across start rules: parsing from a second start rule that shares rules with the first one renumbered them, so a later packrat parse from the first start rule read other rules' cache entries or past the end of its tables.
• Precedence operators after the grammar text is freed: PrecedenceClimbing kept views into the grammar text, so a parser built from a temporary string (parser p(read_file(path))) read freed memory and failed to parse 1+2.
• Back reference in an error message: the expected text of a failed back reference pointed at captured text that was already freed, and printed as expecting ''.
• enable_packrat_parsing() after load_blob(): a blob made without packrat could never have it turned on; the call silently did nothing.

⚠️ Changes to be aware of

• PrecedenceClimbing::BinOpeInfo is now std::map<std::string, std::pair<size_t, char>, std::less<>> instead of a map keyed by std::string_view. Code that fills one with operator[] and a string_view key needs an explicit std::string.
• AstBase::original_name, original_choice_count, original_choice and original_tag are no longer const.
• With enable_ast(true), a node's parent is set only once its parent node is built, so a predicate or leave handler may see it unset during the parse. It is set on every node of the finished tree.

🧹 Repository

• rust-peglib, the unpublished Rust port, has been removed together with the language-independent spec and its harness. The spec cases that the test suite did not already cover were moved into it.
• The test suite now also runs with every grammar round-tripped through serialize_grammar() / load_blob(), which is how the load_blob() packrat bug was found.