Stack Overflow in Debug Builds During Full Test Suite

Status

Accepted. The Decision was amended for issue #285: the single shared parse-depth limit became two budgets, and the nesting default changed from 4,096 to 256 units.

Context

When running the full test suite (cargo test --test compat_utf8 -- --test-threads=1), a SIGSEGV occurs around test 1029. The affected test (named_group_underscore_backref) passes fine in isolation.

The root cause is a stack overflow: The recursive tree traversal functions tune_tree(), compile_tree(), tune_call(), tune_call2(), tune_called_state(), and is_exclusive() have — like in the C original — no depth limit. In Rust debug builds (without optimization), stack frames are significantly larger than in the C equivalent (~1-2 KB per recursion level). The default thread stack of 2 MB is insufficient after ~1000 sequential compilations.

Investigation

• All unsafe blocks were audited: No use-after-free, no dangling pointers, no state leaks between tests.
• No global mutable state between tests (each test creates fresh RegexType instances).
• RUST_MIN_STACK=268435456 (256 MB) resolves the issue completely — all 1468 tests pass with single-threaded execution.
• Using --test-threads=2 or higher with 64 MB stack also works reliably.
• After adding further recursive passes (tune_call, tune_call2, tune_called_state, tune_next, is_exclusive etc.), 16 MB is no longer sufficient.
• Release builds with optimization and inlining are not affected.
• The C original also has no depth limit in tune_tree/compile_tree (only the parser has the parse-depth limit). The issue doesn't manifest in C because C stack frames are smaller.
• Issue #285: deep patterns aborted before the limit fired. With the shared limit at 4,096, a pattern nested 2,022 groups deep overflowed a 2 MiB release thread, and 299 groups overflowed a 2 MiB debug thread. Both happened before the limit reached 2,048 groups. Nested character classes reached the limit with 12 levels of margin on a 2 MiB release thread.

Decision

Ferroni bounds every pattern with two budgets. A pattern over either one fails with ParseDepthLimitOver (RegexError::ParseDepthLimitOver), and neither budget may be exceeded during parsing, so the stack never has to hold more than the budget allows.

1. Nesting, set by onig_set_parse_depth_limit. This keeps C's name and meaning. The default is 256 parser units. A capture or non-capturing group costs two units (its alternation and its branch), and a nested character class costs one, so the default admits about 128 nested groups. C Oniguruma defaults to 4,096.
2. AST budget, set by onig_set_ast_node_limit. This is Ferroni-only: C Oniguruma has no such budget. The default is 4,096 expression nodes per pattern. Flat List and Alt cells are nodes too.

Why the AST budget exists: C's onig_node_free() iterates the cdr links of a flat spine, while Rust's derived Box destruction recurses through them, one frame per cell. The tree passes recurse the same way. The budget bounds that recursion. Long literal strings are unaffected because they occupy one node.

Why the nesting default changed: at C's default of 4,096 units, the parser needs about 14 MiB of stack in debug builds before the limit fires, so a compile at the limit could not fit a 2 MiB thread. The old shared limit also let release builds abort first, at 2,022 groups on a 2 MiB thread.

Deviation from C, recorded per ADR-001: C's default of 4,096 is a safe default only on a stack that C's smaller frames fit. Keeping that default in Ferroni would make every caller that compiles untrusted patterns in debug builds size its threads for about 16 MiB. The default is therefore lower. The setter's name, its meaning and its parser units are unchanged; only the default differs.

The defaults are chosen so that a compile at either limit fits a 2 MiB thread in debug and in release builds. Raising either limit raises the stack a compile needs in proportion, and callers who raise a limit must size their threads for it.

We considered these alternatives:

• Lower the shared default to 1,024, which the issue proposed. Rejected: 11 patterns in the real-world corpus need more than 1,024 expression nodes (the largest needs 3,565), and a debug 2 MiB thread still aborts at about 300 groups.
• Keep one shared limit at 256. Rejected: 60 corpus patterns need more than 256 nodes.
• Weight nesting inside one shared budget. Rejected: it keeps one knob, but the setter then means different things for nesting and for nodes. Two explicit setters say what each one limits.
• Budget the stack by address, failing once the parser has used N bytes. Rejected: whether a pattern compiles would depend on the depth of the calling thread's stack.
• Grow the stack on demand (stacker). Rejected: a new runtime dependency (ADR-009), and a change inside ported functions.

Consequences

Behavior changes

• A pattern nested deeper than 128 groups (or 254 nested classes) now fails with ParseDepthLimitOver. It compiled before, up to 2,048 groups. No pattern in the real-world corpus nests deeper than 16 groups.
• onig_set_parse_depth_limit no longer raises the expression budget. A caller that raised it to compile a wide alternation must also call onig_set_ast_node_limit.

Stack cost per unit

A flat spine costs no stack in the parser or the compiler, only when it is destroyed.

At the defaults:

Verified boundaries

Each case below was compiled on 2 MiB and 8 MiB threads, in release and in debug. Every run ends in success or ParseDepthLimitOver, and none aborts.

The regression tests in tests/api_test.rs compile the groups, classes and alternation boundaries on a 2 MiB thread in debug. tests/parse_limits.rs checks the setters and restores the defaults.

Real-world corpus: all 1,231 unique patterns from the bench grammars (TypeScript, CSS, Rust) and the Shiki trace scanners compile at the defaults. The maxima are 33 nesting units, 3,565 nodes (one pattern; 11 patterns above 1,024), and a longest flat spine of 704 cells.

Required stack sizes

This table is the canonical reference for RUST_MIN_STACK in this repository. README, CONTRIBUTING, AGENTS, .cargo/config.toml, the CI workflow, and scripts/coverage.sh link to or reuse these values in their runnable guidance.

CI may run with more headroom than the minimum (the compat_utf8 lane uses 512 MiB) -- that is deliberate slack on the largest suite, not a second rule.

• Tests should be run with the increased stack size:

  RUST_MIN_STACK=268435456 cargo test --test compat_utf8 -- --test-threads=1
  

  Copy
• The nesting limit bounds the parser and compiler recursion. The AST budget bounds the recursive destruction of flat spines. Both are enforced while parsing.