Issue #587: The parser takes exponential time on nested parentheses, ifs and blocks, and overflows the stack at about 900 nested calls

Open and answer this issue on GitHub.

compiler, ready · opened 2026-10-12 · updated 2026-10-29 · 1 comment

Found

By the self-hosting sessions of 2026-10-11 (emit U1a, and the check-core planning). Not measured with callgrind yet (counts, never time, per CLAUDE.md); the figures below are observations.

Today

• Nested parentheses, ifs and blocks are exponential: 16 levels took 0.6-1.7 s, 60 nested parentheses did not finish in 60 s, and 16 blocks with a missing } ran past 20 s.
• Deep nesting of calls overflows the stack in the parser at about 900 levels; a .abs() chain overflows after parsing between 1,600 and 1,800 (default 8 MB stack).
• The tests emit_deep_nesting.rs and check_deep_nesting.rs therefore chain (calls 500, lists 500, ?? 500, a chain of 1,000) and never nest parentheses, ifs or blocks.

To build

1. A test that parses nested parentheses, if expressions and blocks 64 deep and finishes (today it does not); a missing-} case that reports the error without backtracking blow-up. Measure with callgrind (instructions) at 8, 12 and 16 levels to show the growth.
2. Find the cause (a backtracking alternative that re-parses a sub-expression: callgrind_annotate) and remove the re-parse (parse once and decide, or memoise by position).
3. A stack guard in the parser (a depth limit with a Nikaia message, Part III C.2) so nested calls fail with a diagnostic instead of a stack overflow, at a depth above the deep-nesting tests.
4. Extend the deep-nesting tests to parentheses, ifs and blocks. Fixes #<this issue> on the last commit.

Related: #125, the checker core plan (docs/selfhosting-plan.md, “C-6 in units”: a 2,953-line match is one large frame).

Comments

keywan-ghadami, 2026-10-29

Triage (#982), class B: waits for the parser R rows (after #903 and #557). The fix lands in parser/mod.rs’s grammar!.

---

Generated by Claude Code

Back to Open Issues