oracle/graal · error · UnsupportedRegexException

%s DFA explosion

Error message

%s DFA explosion

What it means

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.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java:1264

        finalStateSuccessor.setFinalStateSuccessor();
        finalStateSuccessor.setOverrideFinalState(false);
        finalStateSuccessor.clearPreCalculatedResults();
        finalStateSuccessor.updateFinalStateData(this);
        expansionQueue.push(finalStateSuccessor);
    }

    private DFAStateNodeBuilder lookupState(TransitionSet<NFA, NFAState, NFAStateTransition> transitionSet, boolean isBackWardPrefixState) {
        lookupDummyState.setNfaTransitionSet(transitionSet);
        lookupDummyState.setIsBackwardPrefixState(isBackWardPrefixState);
        return stateMap.get(lookupDummyState);
    }

    private DFAStateNodeBuilder createState(TransitionSet<NFA, NFAState, NFAStateTransition> transitionSet, boolean isBackwardPrefixState, boolean isInitialState) {
        assert stateIndexMap == null : "state index map created before dfa generation!";
        DFAStateNodeBuilder dfaState = new DFAStateNodeBuilder(nextID++, transitionSet, isBackwardPrefixState, isInitialState, isForward(), isForward() && !isBooleanMatch());
        stateMap.put(dfaState, dfaState);
        if (stateMap.size() + (isForward() ? expansionQueue.size() : 0) > TRegexOptions.TRegexMaxDFASize) {
            throw new UnsupportedRegexException((isForward() ? (isGenericCG() ? "CG" : "Forward") : "Backward") + " DFA explosion");
        }
        if (!hasAmbiguousStates && (transitionSet.size() > 2 || (transitionSet.size() == 2 && transitionSet.getTransition(1) != nfa.getInitialLoopBackTransition()))) {
            hasAmbiguousStates = true;
        }
        if (!(isBooleanMatch() && dfaState.updateFinalStateData(this).isUnAnchoredFinalState())) {
            expansionQueue.push(dfaState);
        }
        return dfaState;
    }

    private void optimizeDFA() {
        RegexProperties props = nfa.getAst().getProperties();
        Group root = nfa.getAst().getRoot();

        boolean doSimpleCGBackward = !props.hasQuantifiers() && !props.hasEmptyCaptureGroups() &&
                        (!root.hasCaret() || root.startsWithCaret()) &&
                        (!root.hasDollar() || root.endsWithDollar());

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Simplify the pattern: factor common prefixes in alternations (a|ab|abc -> a(?:b(?:c)?)?), reduce nested quantifier nesting
2. Split one large alternation into several compilations (e.g. match keywords with a trie or a sequence of simple regexes)
3. If the pattern is trusted, let the engine fall back to the backtracking NFA matcher (do not force linear execution)
4. Raise TRegexOptions.TRegexMaxDFASize if you accept larger compiled matchers and longer compile times

Example fix

// before
String p = "(a|ab|abc|abcd|abcde)+"; // explodes under determinization

// after
String p = "a(?:b(?:c(?:d(?:e)?)?)?)+"; // factored prefixes

// cheap heuristic: very wide alternations and nested quantified groups risk DFA explosion
int alternationBranches(String pattern) {
    int n = 1;
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        if (c == '\\') { i++; continue; }
        if (c == '|' ) n++;
    }
    return n; // > ~100 branches on distinct prefixes: expect explosion risk
}

try {
    RegexObject re = compile(pattern, forceLinearOptions);
} catch (UnsupportedRegexException e) {
    if (e.getReason().contains("DFA explosion")) {
        re = compile(pattern, defaultOptions); // backtracking fallback for trusted patterns
    } else { throw e; }
}

When it happens

Trigger: 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.

Common situations: 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.

Related errors

• Too much additional capture group tracking overhead
• too many capture group transitions
• too many parallel NFA states in one DFA state for bounded qu
• dependency cycle
• Regex has unsupported bounded quantifier

AI-assisted analysis of oracle/graal@a66e9ccd1d (2026-08-14). Data as JSON: /api/errors/75bfee723fefdb12. Report an issue: GitHub.