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

[hyperpolymath]

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.

[hyperpolymath]

PR #43 addresses subtleties 1 & 3 (the Linux-doable scope), with the toolchain now set up locally:

• Subtlety 1 (Drop overflow): general shape-independent ast::drop_program_iteratively (explicit heap worklist, by-value destructure, O(1) stack) replaces the Call-only test helper. impl Drop for Expr rejected with justification (breaks by-value destructure across parser/HIR/MIR — the "or justify an alternative" clause). Verified tearing down a 1,000,000-deep non-Call chain at 512 KiB stack.
• Subtlety 3 (MAX_EXPR_DEPTH): measured ≈4.4 KiB/level (examples/measure_depth.rs). Finding: the old 256 needs ~1.14 MiB and is unsafe on the Windows 1 MiB main-thread stack (can overflow before the guard trips), not merely unjustified. Re-derived → 128; parser's independent MAX_PARSE_EXPR_DEPTH=64 is the real ceiling so zero real programs are rejected.
• DoD item 4: non-Call (Unary) deep regression test added; alloc-scaling ladder made constant-relative.

Remaining (kept open): the Windows-CI leg of the stack measurement — needs CI access, but examples/measure_depth.rs ships so it's now a single command there. Leave #37 open until that datapoint confirms the 128 budget on the msvc toolchain.