ADR-0020: Bound nesting as CPython does and compile on a large stack¶
Status¶
Accepted
Date¶
2026-11-13
Context¶
The parser and every pass of the compiler recurse over the syntax tree:
converting it, checking, lowering and generating code. Deep nesting
therefore uses deep stack. A fuzzed input with about 45 nested braces
overflowed the parser's stack under AddressSanitizer, and the typy
command itself aborted on 1000 nested brackets, a 2 KB program, against
NFR-09.
CPython bounds nesting itself. Its tokenizer refuses brackets nested more
than 200 deep, "too many nested parentheses", and blocks more than 99
deep, "too many levels of indentation". Its parser and compiler refuse
deeper expressions with MemoryError or RecursionError. Measured with
compile():
| Shape | CPython 3.12 | CPython 3.15 |
|---|---|---|
| Brackets, calls | 200 | 200 |
| Blocks | 99 | 99 |
Unary operators, not |
5966 | 5965 |
a if c else b chains |
5966 | 2982 |
+ chains, attribute chains |
9995 | 22685 |
Comparison and and chains |
over 30000, flat | over 30000, flat |
The TyIR verifier also computed, for every block, the set of blocks that
dominate it, which costs memory in the square of the number of blocks: a
chain of 20000 elif clauses ran out of 6 GB, and 5966 nested if
expressions took 87 seconds.
Options considered¶
- Refuse brackets past 200 only. Matches CPython for brackets, but
unary operators,
ifexpressions andelifchains nest without brackets and still overflow. - Rewrite every pass without recursion. Removes the limit on the stack, at the cost of rewriting the converter, the checker, lowering and code generation.
- Bound nesting and size the stack for the bound. Refuse what
CPython's tokenizer refuses, with its messages; let the parser grow its
stack on the heap (the
stackerfeature ofruff_python_parser); cut off expressions and statements nested past a depth deeper than any program CPython compiles; and run the compiler on a thread whose stack holds that depth.
Decision¶
TyPy uses option 3 (LEX-11).
- Before parsing, a pass over the tokens refuses the 201st nested bracket with "too many nested parentheses" and the 100th nested block with "too many levels of indentation", as E0103.
- The parser grows its stack on the heap, so no input overflows it.
- Converting the parser's tree counts the nesting of expressions and
statements, an
elifcounting as theifit becomes, and stops pastMAX_DEPTH, 25000, with "the program nests more than 25000 levels deep, past what CPython compiles". 25000 is past the deepest program any oracle version compiles. typyruns the compiler on a thread with a 512 MiB stack. The memory is reserved, and only what a program's nesting uses is taken.- The verifier finds immediate dominators with Cooper, Harvey and Kennedy's iteration, and answers whether a block dominates another from a numbering of the dominator tree, in constant time.
Consequences¶
- Every program CPython compiles, compiles; a deeper one is refused with E0103, never a crash. A program 22685 levels deep builds in about 2 seconds.
- Code that calls the stages in its own thread, such as a test or the
fuzz harness, gives that thread the same large stack to convert a tree
nested
MAX_DEPTHlevels. stackerandpsmjoin the compiler's dependencies; the runtime is unchanged.- A function of many blocks verifies in time and memory in proportion to them.
Related requirements¶
LEX-11, NFR-09, STD-01, OI-03, ADR-0005.