A long elif chain exhausts the C stack in the parser before the compiler's depth limit can reject it

[Nitjsefnie]

Describe the bug

parse_statement recurses once per elif arm, so C-stack usage grows linearly with the length of an if/elif chain. Past roughly 12,800 arms the process segfaults while parsing.

I want to be straightforward about the severity, because the interesting part isn't the crash: below that threshold the behaviour is already correct. COMPILE_MAX_DEPTH (src/compiler.c:237, 128) rejects a long chain cleanly with expression nesting too deep to compile (limit 128). So no valid program is affected, and a chain long enough to crash is one the compiler would have refused anyway — it just never gets the chance, because the parser exhausts the stack first. What seems worth reporting is the two invariants underneath:

• PARSE_MAX_DEPTH does not cover this path. Its comment at src/parser.c:636-640 scopes it to nested expressions and nested blocks, and an elif chain is syntactically flat, so nothing on this path ever charges g_parse_depth. The guard isn't defeated — it has nothing to compare.
• The comment at src/parser.c:1390-1391 doesn't hold here. It reads Nesting depth is preserved by parse_block's own guard, but the elif desugaring manufactures nesting by recursing at src/parser.c:1616 (else_body[0] = parse_statement(p);) after that guard has already unwound. The recursion is non-tail — the result is stored and more work follows — so it cannot be flattened away.

Measured cost is ~656 bytes of C stack per arm at -O2. The exact threshold is therefore ulimit -s-dependent: ulimit -s 65536 turns every crash below back into normal behaviour.

Surfaced while working on #870.

To reproduce

The chain has to be generated. The shape is an ordinary top-level chain, one statement per arm:

x is 0
if x == 0:
    print of 0
elif x == 1:
    print of 1
else:
    print of -1

Generate a long one and run it:

python3 -c '
n = 14000
print("x is 0")
print("if x == 0:")
print("    print of 0")
for i in range(1, n):
    print(f"elif x == {i}:")
    print(f"    print of {i}")
print("else:")
print("    print of -1")
' > deep_elif.eigs

./src/eigenscript deep_elif.eigs ; echo "rc=$?"
./src/eigenscript --lint deep_elif.eigs ; echo "rc=$?"

Expected behavior

A chain this long is refused, not fatal. Either the existing compile-depth error, or a parse-time depth error in the same style as the other bounds in the tree — the point is a diagnostic and a non-zero exit rather than a signal.

Actual behavior

At n = 14000, both invocations die with rc=139 (128 + 11, SIGSEGV) during parsing, with no diagnostic.

The two modes differ below the crash threshold, which is worth knowing when reproducing:

• ./src/eigenscript deep_elif.eigs at n = 200 and at n = 12000 → rc=1, expression nesting too deep to compile (limit 128). Correct behaviour.
• ./src/eigenscript --lint deep_elif.eigs at n = 12000 → rc=0. Linting doesn't run the compiler, so the depth limit that saves the plain path isn't in play at all.

So if you reproduce with a few hundred arms you'll get the clean error and see nothing wrong — the crash needs roughly 12,800+ at the default stack size.

Environment

• OS: Debian GNU/Linux 13 (trixie)
• GCC version: 14.2.0 (Debian 14.2.0-19)
• EigenScript version: 0.39.0 (built from main at 4e398aa1e47eeb0dc7182478ab4bf3240a7f8476)

[Nitjsefnie]

Thanks — taking this. Plan is a depth bound on the elif desugaring path itself rather than reaching for PARSE_MAX_DEPTH, since that counter is scoped to nested expressions and blocks and an elif chain is flat, so nothing charges it. That also lets the stale claim at parser.c:1390-1391 go with it.

One thing to flag before I build it: the crash needs ~12,800+ arms, and COMPILE_MAX_DEPTH already rejects anything past 128 cleanly, so this is only reachable via --lint (which never runs the compiler) or as a parse-time crash that pre-empts a diagnostic you already emit. If you would rather the parse-time bound simply match the compiler's 128 instead of being its own limit, say so and I will build that shape.

[InauguralPhysicist]

Neither shape — and the reason is that the premise both options rest on is off by
one layer: the parser and the compiler already share the counter.

compile_node (src/compiler.c:1893) guards on g_parse_depth, the same
variable parse_block and parse_expression charge. COMPILE_MAX_DEPTH (128)
and PARSE_MAX_DEPTH (256) are two limits on one counter, not two counters. So
"match the compiler's 128" would not be aligning two independent bounds — it
would be adding a third constant against a counter that already has both.

What to build

Charge the existing shared g_parse_depth at the elif recursion site, using
the mechanism the tree already has for exactly this shape: chain_too_deep
(src/parser.c:1127). That function exists because a syntactically flat
construct that recurses in C has to charge the depth counter itself — it is
what a long a + b + c + ... chain does at six call sites. An elif chain is
the same shape with a different token, and it is the one such construct that
never got wired up. Your diagnosis of why it is uncharged is right; the
conclusion is that it should reuse this, not get its own bound.

That gives you, with no new constant:

• No new number to drift out of step with the other two. This is live in the
  repo right now — werror gate: pin the expected compile-invocation count so batching cannot silently shrink coverage #921 and werror gate: the compile-invocation RECOGNIZER is two hand-written lists, and both have already drifted (${CC:-gcc}, $SRCS) #925 are both open on hand-maintained lists that
  drifted from the tree, and werror gate: the compile-invocation RECOGNIZER is two hand-written lists, and both have already drifted (${CC:-gcc}, $SRCS) #925 is specifically about a second copy of a
  pattern silently going stale. I do not want a PARSE_ELIF_MAX_DEPTH joining
  that set.
• Behaviour below 256 arms byte-identical to today: 200 arms still parses
  clean and still gets expression nesting too deep to compile (limit 128) from
  the compiler, because 200 < 256. I verified this at HEAD.
• 257+ arms gets a clean parse diagnostic and non-zero exit instead of, today,
  either the compile error (257–12,800) or SIGSEGV (12,800+). Strictly better in
  both bands.
• --lint fixed by construction, since the bound is now in the stage lint
  actually runs.

One implementation note: the if (chain_too_deep(p)) break; idiom at the
existing sites is loop-shaped and the elif site is not, so the too-deep path
there means "record the error and stop recursing" — leave else_body NULL and
let the chain terminate rather than descending. And parse_statement's
g_parse_depth = saved_depth restore is what makes the charge per-statement, so
you should not need a matching decrement at the recursion site; worth asserting
in the test that a long chain does not leak depth into the statement that
follows it.

At 656 bytes/arm, 256 arms is ~168 KB of C stack, comfortably inside any
ulimit -s worth supporting — so the existing constant is already the right
order of magnitude for this path, which is a decent sign it is the right counter.

Yes to retiring the parser.c:1390-1391 claim along with it — it is false for
this path exactly as you describe.

Confirmed at HEAD

Reproduced on main @ 8b7501a, your generator verbatim:

n	eigenscript	--lint
200	rc=1, compile-depth error	rc=0
12,000	rc=1, compile-depth error	rc=0
14,000	rc=139	rc=139

A separate gap this turned up — not yours to fix here

--lint returns 0 with no issues found on the 200-arm chain, a program the
compiler refuses outright. Meanwhile it returns 1 for an unused parameter.
So lint's exit code today reports style but not compilability, and a program that
cannot run passes it clean. That is the reason the crash was reachable through
lint at all, and it is worth its own issue rather than being folded in here —
I will file it. Please keep #926 scoped to the depth charge.

[Nitjsefnie]

Understood, and thanks for the correction — I had PARSE_MAX_DEPTH and COMPILE_MAX_DEPTH as two counters rather than two limits on g_parse_depth, which is what made "align them" look like a sensible option at all. compile_node guarding the same variable settles it.

Building the chain_too_deep charge at the recursion site, no new constant, non-descending on the too-deep path, and retiring the parser.c:1390-1391 claim with it. Tests will pin the 200-arm behaviour as unchanged in both modes and assert a long chain leaks no depth into the following statement. Keeping it off #927.

[Nitjsefnie]

Built it, and the SIGSEGV is gone — but verification says one clause of the design never actually runs, and I would rather hand that back than paper over it.

What holds: 14,000 arms goes from rc=139 in both modes to a non-zero exit with a diagnostic, and the 200-arm band is byte-identical to base — I diffed the actual output strings against a build of the base commit rather than comparing exit codes. No new constant, no decrement needed, no depth leaking into the following statement, and lint.c and compiler.c are untouched, so #927 stays yours.

What does not hold: the too-deep branch at the elif site never executes. An instrumented build with a counter in that branch fires zero times at 253, 256, 258, 300 and 14,000 arms. Deleting the branch entirely while keeping the depth charge produces byte-identical stdout, stderr and exit code on every fixture, with the committed tests still green — by the mutation standard, the line is inert. The cause is that the expression-level guard on the same counter trips one level earlier: any elif <expr>: descends into expression parsing before the statement-level check can fire.

So what actually terminates the chain is error-recovery desync rather than the designed bound, and the result is not the clean diagnostic the design intends. At 14,000 arms it emits on the order of 41,000 parse errors across ~27,500 lines of stderr. For contrast, the +-chain idiom you pointed me at yields a single error for a 100,000-term chain. It also makes the 253–~12,800 band noisier than base, which handled that range with one clean compile error — so in that band this is currently a regression, not an improvement.

The tension I do not want to resolve on your behalf: the only way I found to make that branch reachable is reserving headroom at the elif site so it trips before the expression guard — which means a number, and that pulls directly against "no new constant" for the reason you gave about #921 and #925.

Two shapes I can see, and I am equally happy to build a third you prefer:

1. Reserve headroom at the site, accepting one constant, and get the single clean diagnostic.
2. Charge at the elif site before descending into the arm's expression, so the statement-level check is the first to trip — if that ordering is sound, it needs no new number.

Option 2 looks to me like it fits your original intent best, but I have not built it, and whether that ordering is safe is a call about your parser rather than mine.

Branch is held on my fork with no PR open. Say which shape you want and I will send it.

[Nitjsefnie]

Built the reordering. The bound is now genuinely live — instrumented, it fires exactly once, at depth 256, for 257, 300 and 14,000 arms, and deleting it changes behaviour, so it is load-bearing rather than the dead clause from last time. The 14,000-arm cascade is gone.

But the measurement turned the headroom question from a hypothetical into a concrete one, and I would rather show you the numbers than pick.

Charging one level per arm on the shared counter means arm N sits at depth N, so the arm's own condition and body parsing pushes past PARSE_MAX_DEPTH before arm 257 is reached. Behaviour therefore changes below the boundary you specified. Base against this branch, same fixtures, freshly rebuilt binaries:

arms	base, plain	this branch, plain
253	rc=1, 2 lines, compile diagnostic	rc=1, 2 lines, 1 parse error
254	rc=1, 2 lines, compile diagnostic	rc=1, 4 lines, 3 parse errors
256	rc=1, 2 lines, compile diagnostic	rc=1, 13 lines, 8 parse errors
300	rc=1, 2 lines, compile diagnostic	rc=1, 12 lines, 8 parse errors
12,000	rc=1, 2 lines, compile diagnostic	rc=1, 12 lines, 8 parse errors

Base emitted its single clean expression nesting too deep to compile (limit 128) at every one of those points. Under --lint the gap is starker: base returned rc=0 with no issues found through 12,000; this branch returns rc=1 with parse errors from 253 up. Your "200 arms unchanged" check still holds exactly — 200 is far enough below that the arm charge does not matter — which is why it did not surface earlier.

So the two constraints cannot both hold as stated: an arm bound that is live at 257 and a 253–256 band identical to base cannot coexist while arm depth and expression depth draw on one budget. Something has to give, and which one is yours:

1. Reserve headroom at the site so the arm bound trips before expressions exhaust the budget — this is the constant you did not want, and I understand why.
2. Accept that the sub-boundary band now reports a parse error instead of a compile error, and document it as the cost of the bound. It is arguably the better diagnostic anyway, since the program is unparseable rather than merely uncompilable — but it is a visible behaviour change and not mine to wave through.
3. Measure chain depth separately from expression depth at the elif site — save and restore around the condition parse so the arm count accumulates without stacking on expression nesting. That would keep both properties with no new constant, but whether that ordering is sound is a question about your parser, not mine.

Option 3 looks right to me if it is safe; option 2 is the smallest diff.

Separately, and regardless of which you pick: our own regression test was too weak. It asserted only a non-zero exit and the presence of a parse error, so it stayed green when the guard was deleted and the full error cascade came back. Caught by deleting the branch and re-running. I am tightening it to assert an exact error count and a stderr-line ceiling, and to fail against that mutant — that part needs no decision from you.

Branch is on my fork, no PR open.

[InauguralPhysicist]

Ruling: option 2. Take the diagnostic change from 253 up, document it at the guard site, and I'm explicitly releasing you from the 253–256-band constraint I set — your measurement shows it can't coexist with a live arm bound on a shared budget, and I've now convinced myself option 3 can't rescue it either.

Why option 3 is out, since it was the attractive one: the save/restore around an arm's parse is unsound against nesting. If each arm's body parse restores the counter to the chain-entry baseline, then a chain nested inside that body starts its own arm budget from the block baseline — parse_block's charge is only the block-nesting level, so the schemes multiply. Worst case is roughly Σ over nesting levels k of (256−k) arms ≈ 32k parser C-frames, and your own measurement puts the base parser's segfault threshold near 12.8k frames. So "closes the class by construction" inverts: option 3 reopens the crash class through chain-in-body nesting. The variant that restores around only the condition stays bounded (arm charges persist through body parses, total ≤ 256), but it doesn't restore the band either — a trivial body still charges parse_block + expression levels from the depleted budget, so arms 254–255 fail parse anyway. Once the band is unrecoverable without a reserved-headroom constant, option 2 is both the smallest diff and, as you said, arguably the better diagnostic: the program is unparseable under the bound, and saying so is honest.

Two requirements on the PR:

1. The tightened regression test you described — exact error count, stderr-line ceiling, and failing against the guard-deleted mutant. Your observation that the old test stayed green under mutation is exactly the failure mode we gate against; that part of your comment needs no ruling and full agreement.
2. A comment at the guard site recording (a) that arm depth deliberately draws on the shared budget, and (b) why the per-arm save/restore alternative is rejected — the nesting multiplication above — so the next person doesn't rebuild option 3 in good faith.

The bounded error cascade (~8 errors / 12–13 lines flat regardless of arm count) is acceptable as measured; don't spend more on it.

Open the PR when ready — the instrumented fires-exactly-once-at-256 evidence and the mutation-caught test are the acceptance bar, and you've already met both.