gh-158847: Avoid enumerating cycles when choosing pegen recursion leaders - #158848

Summary

To pick a leader for a left-recursive SCC, pegen walked every path from every node in the SCC. The number of paths grows factorially with the SCC size. A leader is a rule that sits on every cycle, so we can test each candidate directly: remove it and check whether what's left is acyclic.

 compute_left_recursives
   for each SCC with >1 rule
-    for start in scc
-      for cycle in find_cycles_in_scc(start)   # every path, O(n!)
-        leaders -= scc - set(cycle)
-    leader = min(leaders)
+    for leader in sorted(scc)
+      if is_acyclic(scc - {leader})          # Kahn's toposort, O(V+E)
+        mark leader; break
+    else
+      raise ValueError("no leadership candidate ...")

Overall that's O(V·(V+E)) per SCC. It picks the same leader as before (smallest name that lies on every cycle) and raises the same error. find_cycles_in_scc had no other callers, so I removed it.

CPython's own grammar barely notices this, because its biggest SCC has two rules. Generated Parser/parser.c is byte-identical before and after. Grammars with wider mutual left recursion hit a wall, though.

Evidence

Parser generation, median of 7, release build, macOS arm64. n is the number of mutually left-recursive rules:

New test test_left_recursion_analysis_work counts name comparisons on a fully connected 8-rule grammar that has no leader:

• Before: AssertionError: 1067658 not less than 2000
• After: 1,272 comparisons, passes

Also added test_left_recursion_leader_order (leader choice stays the same) and test_large_left_recursive_grammar (12-rule SCC still generates a working parser).

I checked the old and new compute_left_recursives against each other on all 512 three-rule graphs and 256 random four-rule graphs. Flags, SCCs and errors matched every time. test_peg_generator -u cpu: 125 run, all pass.

Merge Danger

Door: two-way

Build-time tooling only. Generated parser output is unchanged.

Blast Radius: tooling

This only matters to people running pegen on their own grammars. For them, leader choice and error messages stay the same.

AI disclosure: the profiling, the patch and the equivalence check were done with AI tools (Codex, Claude).

🤖 Generated with Claude Code