oracle/graal · error · UnsupportedRegexException

DFA transition size explosion

Error message

DFA transition size explosion

What it means

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.

Source

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

                        DFACaptureGroupPartialTransition.EMPTY,
                        DFACaptureGroupPartialTransition.EMPTY,
                        indexUpdates,
                        indexClears,
                        lastGroupUpdates,
                        (byte) DFACaptureGroupPartialTransition.FINAL_STATE_RESULT_INDEX);
        if (debugMode()) {
            DFACaptureGroupTransitionBuilder.PartialTransitionDebugInfo debugInfo = new DFACaptureGroupTransitionBuilder.PartialTransitionDebugInfo(partialTransitionNode, 1);
            debugInfo.mapResultToNFATransition(0, transition);
            registerCGPartialTransitionDebugInfo(debugInfo);
        }
        return partialTransitionNode;
    }

    void updateMaxNumberOfNFAStatesInOneTransition(int value) {
        if (value > maxNumberOfNfaStates) {
            maxNumberOfNfaStates = value;
            if (maxNumberOfNfaStates > TRegexOptions.TRegexMaxNumberOfNFAStatesInOneDFATransition) {
                throw new UnsupportedRegexException("DFA transition size explosion");
            }
        }
    }

    private boolean debugMode() {
        return getOptions().isDumpAutomata() || getOptions().isStepExecution();
    }

    public String getDebugDumpName(String name) {
        return name == null ? getDebugDumpName() : name;
    }

    public String getDebugDumpName() {
        if (isForward()) {
            if (isGenericCG()) {
                if (isSearching()) {
                    return "eagerCG";
                } else {

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Reduce the number of capture groups in the pattern (use non-capturing (?:...) groups) so the per-transition NFA-state set stays under 255.
2. Split the regex into several smaller patterns and combine results in application code.
3. Remove or simplify look-ahead assertions that merge onto the same character transition.
4. 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.

Example fix

// before
String pattern = "(a)(b)(c)...(z)(a|b|c)?(?=x)(?=y)"; // 100+ capture groups on one transition

// after
String pattern = "(?:a)(?:b)(?:c)...(?:z)(?:a|b|c)?(?:x)"; // non-capturing groups keep NFA state set small

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");

null

try { compileLinear(pattern); } catch (UnsupportedRegexException e) { compileBacktracking(pattern); } // TRegexCompiler does this internally at TRegexCompiler.java:79 — do not disable the fallback

When it happens

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

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

Related errors

• too many transitions
• too many quantifiers
• too many partial transitions
• Too much additional capture group tracking overhead
• too many capture group transitions

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