oracle/graal · error · UnsupportedRegexException

too many transitions

Error message

too many transitions

What it means

Thrown by TRegexDFAExecutorNode.calcNumberOfTransitions when the sum of successor edges over all DFA states (plus no-match successors of sequential matchers) exceeds source.getOptions().getMaxDFASize(). This caps the size of the compiled DFA so code generation stays bounded.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nodes/dfa/TRegexDFAExecutorNode.java:240

    }

    @Override
    public int getNumberOfStates() {
        return states.length;
    }

    private static int calcNumberOfTransitions(RegexSource source, DFAAbstractNode[] states) {
        int sum = 0;
        for (DFAAbstractNode state : states) {
            if (state instanceof DFAAbstractStateNode s) {
                sum += s.getSuccessors().length;
            }
            if (state instanceof DFAStateNode dfaState && !dfaState.treeTransitionMatching() && dfaState.getSequentialMatchers().getNoMatchSuccessor() >= 0) {
                sum++;
            }
        }
        if (sum > source.getOptions().getMaxDFASize()) {
            throw new UnsupportedRegexException("too many transitions");
        }
        return sum;
    }

    public CounterTracker[] getCounterTrackers() {
        return counterTrackers;
    }

    public boolean recordExecution() {
        return debugRecorder != null;
    }

    public TRegexDFAExecutorDebugRecorder getDebugRecorder() {
        return debugRecorder;
    }

    TruffleString.ByteIndexOfCodePointSetNode getIndexOfNode(int index) {
        if (indexOfNodes == null) {

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Simplify the pattern: replace long literal alternations with a common-prefix factoring or a trie-like structure, or use a character class where possible.
2. Split the regex into several smaller ones and merge results in code.
3. Rely on automatic fallback to the backtracking NFA engine (UnsupportedRegexException is caught in TRegexCompiler.java:79) instead of forcing DFA compilation.
4. If you control RegexOptions, review getMaxDFASize() before raising it — the cost is compiled-code size.

Example fix

// before
String pattern = "cat|car|can|cap|cad|..."; // hundreds of literal alternatives

// after
String pattern = "ca[t rnpd]"; // or split into groups sharing prefixes: "ca(?:t|r|n|p|d)|..."

int branches = pattern.split("\\|", -1).length - 1; if (branches > 500) throw new IllegalArgumentException("alternation too wide; DFA transition limit risk");

null

try { compileDfa(pattern); } catch (UnsupportedRegexException e) { compileBacktracking(pattern); } // mirrors TRegexCompiler.java:79

When it happens

Trigger: Compiling a regex to a DFA whose total transition count grows beyond the configured MaxDFASize — typically patterns with many distinct character classes or long alternations of literals, where the deterministic automaton blows up.

Common situations: Large generated alternations (dictionaries, token lists); wide Unicode case-insensitive classes; the guest language raising or lowering the DFA size option; a regex that is fine on one GraalVM version but exceeds a changed default on another.

Related errors

• DFA transition size explosion
• 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/bac0bcfc435d376d. Report an issue: GitHub.