v1.16.0

🐛 Bug Fixes

Macros can now take part in a left-recursive cycle

A macro invoked from a left-recursive rule always worked, but a macro that was itself part of the cycle did not:

Sum(A) <- Sum(A) '+' A / A

compiled and then recursed until the stack ran out — Holder::parse_core returned early for every macro, skipping both the seed-growing path and the re-entry guard that left recursion depends on. Each macro instantiation now gets its own identity (keyed by what its resolved arguments denote, so M(N) written at two call sites is one instantiation) and grows its own seed, so e.g. Sum(Digit) and Sum(Letter) recurse independently. A left-recursive macro also now forms its own semantic-value scope, like the equivalent non-macro rule — actions fire and the node appears in the AST, where a plain macro stays transparent.

DetectLeftRecursion had a matching hole: its visited set was keyed by rule name, so a grammar like A <- W('z') / W(A) had its second instantiation pruned and the cycle went undetected — it then parsed as if it weren't left recursive at all. Detection is now keyed by instantiation too, with a depth cap (32 levels) for macros that instantiate themselves with a growing argument and so have no finite set of instantiations.

Crash loading grammars with no left recursion at all

W(X) <- Y(X / 'x') hands Y an argument whose own X refers to W's parameter. The left-recursion analyser resolved that bare parameter by walking the frame stack, then visited what it found with the stack unchanged — so the inner X resolved back to the very node it came from and bounced between the two forever. load_grammar() crashed on grammars like this with no left recursion anywhere in them. Resolution now visits a parameter against the frames below where it was found — the scope it was written in — so nesting strictly decreases and terminates.

Both fixes are cross-checked against rust-peglib, which picked up the same two bugs (plus a related fix so a plain rule called from inside a macro body partitions its own left-recursion memo the same way cpp does) and now agrees with cpp on all new cases.

⚡ Performance

Packrat memoization now catches prefix-shared re-parses

The packrat filter only marked a rule for caching when it was reachable from 2+ alternatives at their start position, so it caught S <- A B / A C but not:

S <- '(' A ',' A ')' / '(' A ',' ')'

Here both alternatives parse A at the same offset — just behind a prefix that consumes input first. A stayed guard-only, so every backtrack re-parsed it from scratch, which is exponential once A can nest. Alternatives are now walked element by element: those agreeing on their first k elements reach element k at the same input position, and a rule 2+ of them query there is memoized. k == 0 is the previous start-position case, so this only widens what gets cached — and only for rules the parser was actually re-parsing.

Measured on the SQL benchmark (median of 30): big.sql 37.7 → 36.3 ms, all TPC-H 0.518 → 0.495 ms, optimized big.sql 34.3 → 33.1 ms.

📚 Documentation

• README's left-recursion section gains the macro-in-a-cycle example above, the semantic-value-scope rule for left-recursive macros, the 32-level instantiation-depth cap (and what it bounds), and the one growing-argument shape that isn't fixed by this release: a left-recursive macro whose recursive call wraps its own parameter in a larger expression (Sum(A) <- Sum(A / 'x') '+' A / A) builds a fresh argument every level, so no two levels share an instantiation and the seed memo never catches the recursion. Passing the parameter through unchanged in the recursive call avoids it.

🧹 Internal / Cleanup

• Consolidated the "resolve a macro parameter, then visit it in the scope it was written in" pattern into a single operation, closing off the one call site that previously had to remember to pair the two steps by hand.
• Folded the macro instantiation id into the argument frame it belongs to, instead of tracking it on a parallel stack.
• Folded the packrat filter's prefix walk into the existing CollectLeftmostRules visitor rather than maintaining a near-duplicate.
• rust-peglib (unpublished, internal parity port): all of the above ported and cross-checked against cpp via the shared language-independent spec harness.

⚠️ Compatibility Notes

• As a header-only library, this only requires recompiling — but the internal parse Context gained new state (macro instantiation tracking) for the left-recursive-macro fix, so don't mix object files compiled against different peglib versions.

Full Changelog: v1.15.1...v1.16.0