Recursive AST Drop stack-overflows on very deep inputs; revisit MAX_EXPR_DEPTH value #37

Carved out of #14 (subtleties 1 & 3) so #14 can close on its answered question (root cause is not checker allocation complexity — confirmed Linux + Windows CI).

The subtlety

The #14 investigation proved check_expr/is_assignable_from are linear, so MAX_EXPR_DEPTH = 256 is not a memory safeguard — it bounds stack recursion. Two real, still-open consequences:

1. Recursive Drop of a deep AST overflows the stack. The auto-derived Drop for the Box chain recurses once per nesting level. This is independent of the checker (it happens even if checking is skipped) and is currently only worked around by a shape-specific test helper (drop_program_iteratively in crates/my-lang/src/checker.rs, which only handles 2-arg Call chains). A real input shaped differently would still overflow on drop.
2. MAX_EXPR_DEPTH = 256 is now unjustified at that specific value. It was chosen as an OOM defence that doesn't exist. It rejects deep-but-legal programs; the value should be re-derived from the actual stack budget of the deepest recursive walk (checker recursion and Drop), not from the disproven memory argument.

Why this is not a quick PR

Per #14's own "no speculative fix without measurement" principle: a general iterative Drop for the whole AST is a non-trivial, risky core change. It should be measured first (actual stack frame size per check_expr / per Drop level on the target platforms) and then either: a generalized iterative drop, a Box-arena / flattened AST, or an explicit recursion limit tied to a measured budget.

Definition of done

• Measure stack-frame cost per recursion level for check_expr and AST Drop (Linux + the Windows CI toolchain).
• Replace the test-only shape-specific drop helper with a general, non-overflowing AST teardown (or justify an alternative AST representation).
• Re-derive MAX_EXPR_DEPTH from the measured budget (or remove it if the structural fix makes it unnecessary), updating the doc-comment reframed in docs(checker): reframe MAX_EXPR_DEPTH as a stack-recursion bound (closes #14) #36.
• Regression test with a deep, non-Call-shaped AST.

Resolution

All DoD items complete across two PRs:

• fix(checker): general non-overflowing AST teardown + measured MAX_EXPR_DEPTH (#37) #43 (merged) — subtleties 1 & 3: general shape-independent ast::drop_program_iteratively (explicit heap worklist, O(1) stack; impl Drop for Expr rejected with justification — the "or justify an alternative" clause); MAX_EXPR_DEPTH re-derived 256 → 128 from a measured ≈4.4 KiB/level; non-Call (Unary) deep regression test. Left open only for the Windows/msvc CI leg of the measurement.

• fix(checker): self-driving stack-depth measurement + CI guard (#37) #80 (merged) — closes that last item. examples/measure_depth.rs was rewritten from a manual single-shot probe into a self-driving measurement (re-execs itself as worker subprocesses, binary-searches each overflow cliff, prints per-platform bytes/level, and exits non-zero if MAX_EXPR_DEPTH no longer fits the 1 MiB Windows floor with headroom). The new .github/workflows/stack-depth.yml runs it plus tests/stack_depth_37.rs on ubuntu-latest and windows-latest, so the msvc datapoint is now produced and locked in on every change. CI confirmed MAX_EXPR_DEPTH = 128 safe on the 1 MiB msvc main-thread stack (measure (windows-latest) ✅, scaling (windows-latest) ✅).

An independent review of the measurement logic (exhaustive verification of both binary searches, the 819 KiB budget arithmetic, and the overflow→abort mechanism) found it correct; one hardening fix — survives() now distinguishes survived / overflowed / infra-failure with positive OK-line confirmation rather than collapsing all non-success to "cliffed" — was applied in #80.

Closing as completed.