{"record":{"id":"30a411542c0f84f0","repo":"oracle/graal","slug":"dfa-transition-size-explosion","errorCode":null,"errorMessage":"DFA transition size explosion","messagePattern":"DFA transition size explosion","errorType":"exception","errorClass":"UnsupportedRegexException","httpStatus":null,"severity":"error","filePath":"regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java","lineNumber":2312,"sourceCode":"                        DFACaptureGroupPartialTransition.EMPTY,\n                        DFACaptureGroupPartialTransition.EMPTY,\n                        indexUpdates,\n                        indexClears,\n                        lastGroupUpdates,\n                        (byte) DFACaptureGroupPartialTransition.FINAL_STATE_RESULT_INDEX);\n        if (debugMode()) {\n            DFACaptureGroupTransitionBuilder.PartialTransitionDebugInfo debugInfo = new DFACaptureGroupTransitionBuilder.PartialTransitionDebugInfo(partialTransitionNode, 1);\n            debugInfo.mapResultToNFATransition(0, transition);\n            registerCGPartialTransitionDebugInfo(debugInfo);\n        }\n        return partialTransitionNode;\n    }\n\n    void updateMaxNumberOfNFAStatesInOneTransition(int value) {\n        if (value > maxNumberOfNfaStates) {\n            maxNumberOfNfaStates = value;\n            if (maxNumberOfNfaStates > TRegexOptions.TRegexMaxNumberOfNFAStatesInOneDFATransition) {\n                throw new UnsupportedRegexException(\"DFA transition size explosion\");\n            }\n        }\n    }\n\n    private boolean debugMode() {\n        return getOptions().isDumpAutomata() || getOptions().isStepExecution();\n    }\n\n    public String getDebugDumpName(String name) {\n        return name == null ? getDebugDumpName() : name;\n    }\n\n    public String getDebugDumpName() {\n        if (isForward()) {\n            if (isGenericCG()) {\n                if (isSearching()) {\n                    return \"eagerCG\";\n                } else {","sourceCodeStart":2294,"sourceCodeEnd":2330,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java#L2294-L2330","documentation":"Thrown by DFAGenerator.updateMaxNumberOfNFAStatesInOneTransition when a single DFA transition would have to remember more than TRegexMaxNumberOfNFAStatesInOneDFATransition (255) distinct NFA states. The DFA engine tracks which NFA states a compressed transition came from (needed for capture-group updates), and that bookkeeping is capped so the generated node stays compact. A regex that fans many NFA paths onto one character transition (many capture groups or merged look-aheads on the same input) trips this cap.","triggerScenarios":"Compiling a regex in DFA mode where the number of capture groups exceeds TRegexMaxNumberOfCaptureGroupsForDFA (127) combined with alternation/look-aheads that collapse onto one transition; updateMaxNumberOfNFAStatesInOneTransition is called with a value > 255 during DFA construction in DFAGenerator.","commonSituations":"Machine-generated or user-supplied regexes with hundreds of capture groups; regexes with many look-aheads merged onto a shared transition; enabling U+180E-style forced DFA options that disable automatic fallback to the backtracking engine.","solutions":["Reduce the number of capture groups in the pattern (use non-capturing (?:...) groups) so the per-transition NFA-state set stays under 255.","Split the regex into several smaller patterns and combine results in application code.","Remove or simplify look-ahead assertions that merge onto the same character transition.","Allow the engine to fall back: TRegexCompiler (TRegexCompiler.java:79) catches UnsupportedRegexException and retries with the backtracking NFA executor, so do not force DFA-only compilation options."],"exampleFix":"// before\nString pattern = \"(a)(b)(c)...(z)(a|b|c)?(?=x)(?=y)\"; // 100+ capture groups on one transition\n\n// after\nString pattern = \"(?:a)(?:b)(?:c)...(?:z)(?:a|b|c)?(?:x)\"; // non-capturing groups keep NFA state set small","handlingStrategy":"fallback","validationCode":"int groups = 0; for (int i = 0; i + 1 < pattern.length(); i++) { if (pattern.charAt(i) == '(' && pattern.charAt(i + 1) != '?') groups++; } if (groups > 100) throw new IllegalArgumentException(\"pattern has too many capture groups for the linear engine\");","typeGuard":"null","tryCatchPattern":"try { compileLinear(pattern); } catch (UnsupportedRegexException e) { compileBacktracking(pattern); } // TRegexCompiler does this internally at TRegexCompiler.java:79 — do not disable the fallback","preventionTips":["Prefer non-capturing (?:...) groups unless you need the captured value.","Keep capture groups per pattern under ~100 for DFA-friendly compilation.","Never force DFA-only options on user-supplied patterns."],"tags":["regex","tregex","dfa","compilation","limit-exceeded"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}