{"record":{"id":"30dcd8a9f4f3e007","repo":"oracle/graal","slug":"astsuccessor-explosion-30dcd8","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/ASTSuccessor.java","lineNumber":182,"sourceCode":"\n                    for (int i = 0; i < lookAroundState.getTransitionSet().size(); i++) {\n                        ASTTransition t = lookAroundState.getTransitionSet().getTransition(i);\n                        if (mergedStateSet.add(t.getTarget())) {\n                            mergedTransitions.add(t);\n                            mergedConstraints.addAll(t.getConstraints());\n                            mergedOperations.addAll(t.getOperations());\n                        }\n                    }\n                    if (!mergedConstraints.isEmpty()) {\n                        int firstQid = TransitionConstraint.getQuantifierID(mergedConstraints.get(0));\n                        for (long constraint : mergedConstraints) {\n                            if (TransitionConstraint.getQuantifierID(constraint) != firstQid) {\n                                throw new UnsupportedRegexException(\"Regex with overlapping bounded quantifier (after look-ahead merging)\");\n                            }\n                        }\n                    }\n                    if (result.size() >= TRegexOptions.TRegexMaxNumberOfASTSuccessorsInOneASTStep) {\n                        throw new UnsupportedRegexException(\"ASTSuccessor explosion\");\n                    }\n                    result.add(new TransitionBuilder<>(mergedTransitions.toArray(new ASTTransition[mergedTransitions.length()]), mergedStateSet, intersection, mergedConstraints.toArray(),\n                                    mergedOperations.toArray()));\n                }\n            }\n        }\n    }\n\n    @TruffleBoundary\n    @Override\n    public JsonValue toJson() {\n        return Json.obj(Json.prop(\"lookAheads\", lookAheads.stream().map(x -> Json.val(x.getRoot().getId())).collect(Collectors.toList())),\n                        Json.prop(\"lookBehinds\", lookBehinds.stream().map(x -> Json.val(x.getRoot().getId())).collect(Collectors.toList())),\n                        Json.prop(\"mergedStates\", mergedStates));\n    }\n}\n","sourceCodeStart":164,"sourceCodeEnd":199,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/ASTSuccessor.java#L164-L199","documentation":"Thrown by ASTSuccessor.addAllIntersecting when the result list of merging look-aheads with the current transition reaches TRegexMaxNumberOfASTSuccessorsInOneASTStep (Short.MAX_VALUE = 32767) before the next element is added. It is the same exponential-successor guard as in ASTStep.addSuccessor, but applied during look-around merging, where each look-ahead multiplies the number of merged transitions.","triggerScenarios":"Compiling a regex that combines multiple look-aheads with branching transitions so that the cartesian product of merged states exceeds 32767, e.g. several (?=...)(?=...) assertions stacked over a wide alternation.","commonSituations":"Password-strength / format-validation patterns stacking many look-aheads; generated patterns that prepend dozens of independent look-ahead checks; look-aheads over character-class alternations with many branches.","solutions":["Reduce the number of stacked look-aheads; combine their conditions into fewer assertions or plain alternatives.","Narrow the alternatives inside the look-aheads (character classes instead of long alternations).","Replace look-ahead stacks with separate sequential matches validated in code.","Allow fallback to the backtracking engine rather than forcing the linear engine."],"exampleFix":"// before\nString pattern = \"(?=.*a)(?=.*b)(?=.*c)(?=.*d)...(?=.*z)^.*$\"; // many look-aheads merged\n\n// after\nboolean ok = input.chars().anyMatch(...); // simple contains() checks per letter in code\nPattern p = Pattern.compile(\"^.*$\");","handlingStrategy":"validation","validationCode":"int lookAheads = pattern.split(\"\\\\(\\\\?=\", -1).length - 1; if (lookAheads > 10) throw new IllegalArgumentException(\"too many stacked look-aheads; risk of successor explosion\");","typeGuard":"null","tryCatchPattern":"try { compile(pattern); } catch (UnsupportedRegexException e) { /* reduce look-ahead count or fall back to backtracking engine */ }","preventionTips":["Limit the number of stacked look-aheads in generated validation patterns.","Replace look-ahead stacks with plain code checks after a simple match.","Simplify alternations inside look-aheads."],"tags":["regex","tregex","look-ahead","complexity-explosion","limit-exceeded"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}