{"record":{"id":"4ac06c950edd286b","repo":"oracle/graal","slug":"astsuccessor-explosion","errorCode":null,"errorMessage":"ASTSuccessor explosion","messagePattern":"ASTSuccessor explosion","errorType":"exception","errorClass":"UnsupportedRegexException","httpStatus":null,"severity":"error","filePath":"regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/ASTStep.java","lineNumber":89,"sourceCode":"    }\n\n    public TBitSet getMatchedConditionGroups() {\n        return matchedConditionGroups;\n    }\n\n    public void addSuccessor(ASTSuccessor successor) {\n        successors.add(successor);\n        // When compiling a regular expression, almost all ASTSuccessors will yield at least 1 NFA\n        // transition (the only case when an ASTSuccessor yields no NFA transitions is when the NFA\n        // transition would collide with a position assertion such as $ or ^, as in /(?=a$)ab/, see\n        // NFAGenerator#createNFATransitions). Furthermore, there exist regular expressions such as\n        // (a?|b?|c?|d?|e?|f?|g?)(a?|b?|c?|d?|e?|f?|g?)... The number of ASTSuccessors in a single\n        // ASTStep rises exponentially with the number of repetitions of this pattern (there is a\n        // different ASTSuccessor for every possible path to a next matching character). If we want\n        // to avoid running out of memory in such situations, we have to bailout during the\n        // collection of ASTSuccessors in ASTStep, before they are transformed into NFA transitions.\n        if (successors.size() > TRegexOptions.TRegexMaxNumberOfASTSuccessorsInOneASTStep) {\n            throw new UnsupportedRegexException(\"ASTSuccessor explosion\");\n        }\n    }\n\n    @TruffleBoundary\n    @Override\n    public JsonValue toJson() {\n        return Json.obj(Json.prop(\"root\", root.getId()),\n                        Json.prop(\"successors\", successors),\n                        Json.prop(\"matchedConditionGroups\", Json.array(matchedConditionGroups.stream().toArray())));\n    }\n}\n","sourceCodeStart":71,"sourceCodeEnd":101,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/ASTStep.java#L71-L101","documentation":"Thrown by ASTStep.addSuccessor when the number of ASTSuccessors in a single ASTStep exceeds TRegexMaxNumberOfASTSuccessorsInOneASTStep (Short.MAX_VALUE = 32767). Each ASTSuccessor represents one possible path to the next matching character; patterns like (a?|b?|c?|...)+ make this count grow exponentially with the number of repetitions. The bail-out happens during successor collection, before NFA transitions are built, to avoid running out of memory.","triggerScenarios":"Compiling a regex whose single AST step (one input position) can be reached via exponentially many paths, e.g. (a?|b?|c?|d?|e?|f?|g?){n} repeated enough times, or deeply nested optional alternations that all converge on the same next term.","commonSituations":"Dynamically constructed regexes that concatenate many optional-alternation blocks; data-driven pattern generation that unrolls quantifiers into long optional chains; denial-of-service-like patterns accidentally fed to the compiler.","solutions":["Rewrite the pattern to avoid optional-alternation blocks that all continue into the same successor term; e.g. replace (a?|b?|c?){8} style constructs with character classes or a bounded loop over a class.","Use a single character class [abc]? instead of alternations of single optional characters.","Split the expression into multiple regexes matched separately and combined in application code.","Accept the backtracking-engine fallback (the exception is caught in TRegexCompiler/TRegexCompilationRequest and retried as NFA) instead of forcing the linear-time engine."],"exampleFix":"// before\nString pattern = \"(a?|b?|c?|d?|e?|f?|g?)(a?|b?|c?|d?|e?|f?|g?)(a?|b?|c?|d?|e?|f?|g?)...\"; // repeated many times\n\n// after\nString pattern = \"[a-g]?[a-g]?[a-g]?...\"; // or \"[a-g]{0,n}\" — one successor per step","handlingStrategy":"validation","validationCode":"// reject patterns concatenating many optional-alternation blocks before compiling\nint optionalAltBlocks = pattern.split(\"\\\\?\\\\|\", -1).length - 1; // heuristic\nif (optionalAltBlocks > 20) throw new IllegalArgumentException(\"pattern risks ASTSuccessor explosion\");","typeGuard":"null","tryCatchPattern":"try { compile(pattern); } catch (UnsupportedRegexException e) { /* log and fall back to backtracking engine or reject input pattern */ }","preventionTips":["Replace optional single-character alternations with character classes.","Cap the number of concatenated optional blocks in generated patterns.","Treat UnsupportedRegexException as a signal about pattern shape, not an environment fault."],"tags":["regex","tregex","nfa","complexity-explosion","limit-exceeded"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}