Crash: long patterns overflow the native stack in compile and backtracking

Reported from zig-js, where regular expression literals reach this library directly from JavaScript source: zig-utils/zig-js#934.

Valid patterns that segfault

Each row was executed through zig-js's current test262 --eval binary, with the recursion taken from an lldb backtrace at the crash. node compiles and runs each pattern.

The first two are flat, not nested, so they are ordinary large patterns rather than adversarial ones.

Other recursive walkers found

A mapping pass over the library found these recursing over pattern structure with no guard. Only the three rows above are confirmed crashes; the rest are listed so they are not lost:

Parser.parseSetExpr (parser.zig:2130), Parser.validateDuplicateGroupNames (parser.zig:636), PatternAnalyzer.analyzeNode (pattern_analyzer.zig:10), optimizer.scanFeatures (optimizer.zig:335), requiresBacktracking (regex.zig:2611), onepass Builder.flatten (onepass.zig:176), ClassSet.matchesMode (ast.zig:164).

Two different fixes

1. Flat concatenation and alternation are sequences. Compiling them iteratively, instead of recursing once per element, lets these patterns work — node accepts them, so failing with an error would still be incompatible.
2. Genuine nesting (deep groups, nested classes) and backtracking depth need a bounded depth or an explicit backtrack stack, and a clean error return the host engine can map to a JavaScript SyntaxError or RangeError, rather than a process crash.

Fixed in zig-utils/zig-regex@3e8654e.

Reproduced first, through zig-js test262 --eval (ReleaseFast, built at zig-js 2dce0416) with node v24.4.1 as the oracle — all three rows in the table above still crashed, and the two controls still passed.

Fix. Every site is the same idea: a pattern's AST spine is as long as the pattern, so a walker over it cannot recurse. What differs is how much of the tree shape is observable.

• Concatenation contributes no states of its own — only an epsilon from one element's accept to the next element's start — so compileConcat chains a whole sequence in one frame and builds exactly the automaton the pairwise recursion built, for either associativity.
• Alternation does have observable shape: each | owns a start/accept pair and clears the captures of the branch it skips. compileAlternation therefore evaluates the same tree bottom-up with an explicit stack — identical states, transitions and branch order — rather than being flattened.
• collectCaptureIndices runs over the skipped branch, which for these patterns is the rest of the pattern, so it crashed on the same inputs and is now iterative.
• Backtracking: the six structural checks share one iterative walker, and clearCapturesIn, isEndAnchorOnly and matchConcat's no-choices path walk their spines. That path touches the heap only for a left-leaning spine, since a sequence without choices has nothing to backtrack into.
• Optimizer analysis: ten walkers converted (calculateMinLength, calculateMaxLength, scanFeatures, isExactLiteral, collectLiteralPrefix, collectMandatory, detectFirstUnboundedClass, collectFirstBytes, flattenAlternation, collectLiteralAlternatives).
• Node.destroy is iterative and allocation-free — a teardown runs on the rollback path of a failed allocation, where memory is exactly what is unavailable.

Before → after:

The working ceiling for a flat pattern moves from about 26,000 elements to at least 1,000,000.

Method worth recording: each successive crash was located by running the pattern and reading the repeated frames in the process's own crash report (~/Library/Logs/DiagnosticReports/), which named Compiler.compileNode, then optimizer.calculateMaxLength, then optimizer.collectLiteralPrefix, then ast.Node.destroy — one build cycle each. lldb was unusably slow against this binary.

Two constraints the library's own tests enforced, worth knowing before touching these paths again:

1. Allocation failures must propagate — answering conservatively on OOM fails optimizer/parser/regex "exhaustive-allocation-failure safe" with SwallowedOutOfMemoryError. The length walkers return !usize / !?usize accordingly.
2. For the same reason Node.destroy must not allocate at all, hence its fixed stack plus freeing childless nodes in place.

Gates. zig build test-core passes, including the four allocation-failure suites. Downstream zig-js conformance is unchanged: all 11 test/built-ins/RegExp child directories plus its 500 top-level tests, test/language/literals/regexp 238 and test/built-ins/String 1,223 — 3,352 tests, 0 fail before and after, every per-directory failure list identical.

Two items from this issue are not covered by this commit and are filed separately: deep nesting (which already declines cleanly with a SyntaxError rather than crashing, though the accepted depth is well below node's), and the walkers that remain recursive but are unreachable by the shapes tested here.

Crashes fixed in 3e8654e with the evidence above. The two parts this issue raised that are not crashes are split out: nesting depth as #25, and the walkers that remain recursive as #26.