Skip to content

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

@hyperpolymath

Description

@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<Expr> 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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions