Cpp-Peglib Files

This release builds ASTs faster and in less memory where packrat parsing or left recursion is used, and fixes packrat parsing that could take exponential time. The trees a parse returns and what callbacks see of AST nodes do not change, but for the cases listed below.

⚠️ Changes to be aware of

AST built from records of the matches

A parse that uses packrat parsing or left recursion now records the matches of AST rules, and builds their nodes only for the tree it returns and where a callback reads them. A predicate, a leave handler or an action of your own gets nodes as they would have been built as the rules matched. Any other parse builds the node of each match as its rule matches, as before. Two things can differ, as the README now says:

• A node that a callback got can be kept until the parse ends, even where the match it belongs to is abandoned.
• Where packrat parsing or left recursion reuses a node, changing its children (nodes) in a callback can make the returned tree differ from one built as the rules matched.

Input size

With enable_ast, a parse fails on an input of 4 GiB or more, with "input is too long to build an AST (4 GiB or more)" at its start.

Packrat parsing memoizes more rules

Every recursion cycle now gets a memoized rule (see Fixes), which takes more memory on some grammars (see Performance). With labels, results reused after a recovery that reports a custom message list fewer failures, as the README allows.

API and ABI

• Ope::is_choice_like is replaced by Ope::choice_count, the number of alternatives a choice chooses among (0 for any other operator). Definition::choice_count() is new.
• Action keeps what add_ast_action declares about an AST action (Action::ast_action()), which changes its layout. Action::ast_node_type() is unchanged.
• New: make_ast_token, make_ast_node and make_collapsed_ast_node, which the AST actions and the records both build nodes with, and ChunkedArray.

⚡ Performance

Time of one parse, including freeing the tree, against v1.24.0 (Release -O2, min of 3 interleaved runs), and peak memory of one parse in a fresh process. The DuckDB grammar is the grammar of DuckDB's PEG parser ported to cpp-peglib (about 1,100 rules).

• Without packrat parsing or left recursion (JSON, CSV, sql.peg without packrat), parses build nodes as before: time and memory are unchanged, within 1-2%.
• The memory that grows on the DuckDB grammar goes to the memos of the recursion cycles (see Fixes); the AST itself takes less.
• With the DuckDB grammar, SELECT followed by 20 ( took 34.7 s to fail and now takes 3.4 ms.

🐛 Fixes

• Packrat parsing could take exponential time (since v1.10.0). It memoized only the rules it guessed alternatives of one choice would try again at one position, and backtracking comes back to a rule in more ways than that guess sees: two rules around the same prefix (if and if-else as two rules), (e 'a')? e, &e e, a choice reached only through a macro argument, and more. Every recursion cycle now gets a memoized rule, which bounds how often a rule is parsed again at one position. What is still not memoized is listed in the README.
• An AST rule checks the values handed to it. Where a precedence rule with nothing to fold, or a leave handler, handed an AST rule a value that is no node of its type, the rule threw std::bad_any_cast only where a tracer was set, and not where its value was unread. It now throws as soon as it matches, whatever is set.
• An AST rule throws on nothing handed to it in a lookahead. A rule with its action disabled hands on its first value, or nothing where it has none. Where such a rule handed an AST rule nothing in a lookahead, the AST rule threw std::bad_any_cast only where a tracer was set. It now throws there too.

🔧 Internals

• The tests pin what callbacks see of AST nodes and every field, parent and node of the returned tree, over 222 configurations, against the version that built every node as its rule matched.
• The records of the matches are kept in chunks that growing never copies.