{"record":{"id":"75bfee723fefdb12","repo":"oracle/graal","slug":"s-dfa-explosion","errorCode":null,"errorMessage":"%s DFA explosion","messagePattern":"(.+?) DFA 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":1264,"sourceCode":"        finalStateSuccessor.setFinalStateSuccessor();\n        finalStateSuccessor.setOverrideFinalState(false);\n        finalStateSuccessor.clearPreCalculatedResults();\n        finalStateSuccessor.updateFinalStateData(this);\n        expansionQueue.push(finalStateSuccessor);\n    }\n\n    private DFAStateNodeBuilder lookupState(TransitionSet<NFA, NFAState, NFAStateTransition> transitionSet, boolean isBackWardPrefixState) {\n        lookupDummyState.setNfaTransitionSet(transitionSet);\n        lookupDummyState.setIsBackwardPrefixState(isBackWardPrefixState);\n        return stateMap.get(lookupDummyState);\n    }\n\n    private DFAStateNodeBuilder createState(TransitionSet<NFA, NFAState, NFAStateTransition> transitionSet, boolean isBackwardPrefixState, boolean isInitialState) {\n        assert stateIndexMap == null : \"state index map created before dfa generation!\";\n        DFAStateNodeBuilder dfaState = new DFAStateNodeBuilder(nextID++, transitionSet, isBackwardPrefixState, isInitialState, isForward(), isForward() && !isBooleanMatch());\n        stateMap.put(dfaState, dfaState);\n        if (stateMap.size() + (isForward() ? expansionQueue.size() : 0) > TRegexOptions.TRegexMaxDFASize) {\n            throw new UnsupportedRegexException((isForward() ? (isGenericCG() ? \"CG\" : \"Forward\") : \"Backward\") + \" DFA explosion\");\n        }\n        if (!hasAmbiguousStates && (transitionSet.size() > 2 || (transitionSet.size() == 2 && transitionSet.getTransition(1) != nfa.getInitialLoopBackTransition()))) {\n            hasAmbiguousStates = true;\n        }\n        if (!(isBooleanMatch() && dfaState.updateFinalStateData(this).isUnAnchoredFinalState())) {\n            expansionQueue.push(dfaState);\n        }\n        return dfaState;\n    }\n\n    private void optimizeDFA() {\n        RegexProperties props = nfa.getAst().getProperties();\n        Group root = nfa.getAst().getRoot();\n\n        boolean doSimpleCGBackward = !props.hasQuantifiers() && !props.hasEmptyCaptureGroups() &&\n                        (!root.hasCaret() || root.startsWithCaret()) &&\n                        (!root.hasDollar() || root.endsWithDollar());\n","sourceCodeStart":1246,"sourceCodeEnd":1282,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java#L1246-L1282","documentation":"Thrown by DFAGenerator.createState when the DFA being built would exceed TRegexMaxDFASize (default 1300 states, counted as existing states plus queued expansions). Patterns whose NFA has many character-disjoint combinations make the DFA grow multiplicatively; to bound compile time and code size, generation aborts with a Forward/Backward/CG-flavored 'DFA explosion' message.","triggerScenarios":"Compiling a pattern whose determinization explodes: large alternations of overlapping classes ((a|ab|abc|abcd|...)+), nested quantifiers over distinct character sets ((a+b+)+ style shapes), or many interleaved optional groups. The check fires per created state once stateMap.size() + expansionQueue.size() > 1300.","commonSituations":"Fuzzing or untrusted-pattern services compiling arbitrary user regexes; generated keyword-matchers with hundreds of alternation branches. Under default options the exception triggers the backtracking fallback; with forceLinearExecution it propagates to the caller.","solutions":["Simplify the pattern: factor common prefixes in alternations (a|ab|abc -> a(?:b(?:c)?)?), reduce nested quantifier nesting","Split one large alternation into several compilations (e.g. match keywords with a trie or a sequence of simple regexes)","If the pattern is trusted, let the engine fall back to the backtracking NFA matcher (do not force linear execution)","Raise TRegexOptions.TRegexMaxDFASize if you accept larger compiled matchers and longer compile times"],"exampleFix":"// before\nString p = \"(a|ab|abc|abcd|abcde)+\"; // explodes under determinization\n\n// after\nString p = \"a(?:b(?:c(?:d(?:e)?)?)?)+\"; // factored prefixes","handlingStrategy":"fallback","validationCode":"// cheap heuristic: very wide alternations and nested quantified groups risk DFA explosion\nint alternationBranches(String pattern) {\n    int n = 1;\n    for (int i = 0; i < pattern.length(); i++) {\n        char c = pattern.charAt(i);\n        if (c == '\\\\') { i++; continue; }\n        if (c == '|' ) n++;\n    }\n    return n; // > ~100 branches on distinct prefixes: expect explosion risk\n}","typeGuard":null,"tryCatchPattern":"try {\n    RegexObject re = compile(pattern, forceLinearOptions);\n} catch (UnsupportedRegexException e) {\n    if (e.getReason().contains(\"DFA explosion\")) {\n        re = compile(pattern, defaultOptions); // backtracking fallback for trusted patterns\n    } else { throw e; }\n}","preventionTips":["Factor shared prefixes in large alternations or replace them with trie-based matching","For untrusted pattern services, cap alternation width and quantifier nesting before compiling","Know that TRegexMaxDFASize (1300) is the knob if larger DFAs are acceptable"],"tags":["regex","tregex","dfa","state-explosion","performance"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}