Split out of #23. That commit (3e8654e) converted the walkers a flat pattern actually reaches — compilation, the backtracking engine's structural checks and no-choices sequence match, the optimizer's analysis, and the AST teardown. The list below is what still recurses over pattern structure.
None of them is a known crash. Every shape exercised in #23 (flat concatenation to 1,000,000 elements, flat alternation to 60,000 branches, backtracking over 31,000 elements, nested classes 5,000 deep) now runs, and deep nesting is refused before these are reached (#25). They are recorded so the work is not lost, and so the next crash report has a short list to check against.
| file | functions |
|---|---|
src/pattern_analyzer.zig | analyzeNode, leadingLiteral, containsUnboundedQuantifier, containsQuantifier, isSafeToQuantify, hasFixedStart, hasFixedEnd, startsDisjointFromAtom, canStartWith, nodesAreIdentical |
src/regex.zig | requiresBacktracking, containsAlternation, canMatchEmpty, firstByteSet, variableQuantifierTailBytes, containsCapture, capturedVariableTailBytes, hasAmbiguousCaptureBoundary |
src/ast_optimizer.zig | constantFold, removeRedundant, flattenConcat, mergeLiterals, simplifyQuantifiers, eliminateDeadCode |
src/backtrack.zig | matchNodeConstrained, collectAllMatches, matchReverseNodeConstrained, collectAllReverseMatches, canMatchEmpty, containsCodepointAtom, matchNamedBackreferenceParticipating{,Reverse} |
src/onepass.zig | Builder.flatten |
src/parser.zig | parseSetExpr, validateDuplicateGroupNames |
src/optimizer.zig | collectFirstBytes (its alternation arm; the sequence arm is iterative) |
src/debug.zig, src/pretty_print.zig | printNode, calculateComplexity, canMatchEmpty, detectIssues, printTree, printSExpr, printDotNode, printCompact, computeRecursive — tooling only, not on the compile or match path |
Notes for whoever takes this
- The backtracking group is the one that can still be reached by a valid pattern: a long sequence that also contains a quantifier or alternation takes
matchConcat's choices path, which callscollectAllMatchesandmatchNodeConstrained. I did not find a crashing case, but I also did not search hard — that is the first place to probe. - Two constraints the library's own tests enforce: allocation failures must propagate (answering conservatively fails the "exhaustive-allocation-failure safe" suites with
SwallowedOutOfMemoryError), and anything on a teardown path must not allocate at all. src/backtrack.zigalready hasanyNodeMatches+pushNodeChildrenas a reusable iterative walker for predicate-shaped checks.
Done
Either converted, or shown by execution to be unreachable at a depth that matters, with the evidence recorded here.