oracle/graal · error · UnsupportedRegexException

too many branches in capture group tracking DFA

Error message

too many branches in capture group tracking DFA

What it means

Thrown by DFAGenerator when building the capture-group lazy transition for a DFA state that needs a byte-indexed lookup table mapping predecessor-transition indices to successor groupings, but the number of distinct groupings (branches) exceeds 255 (0xff). The table must be a byte[], so more than 256 branches cannot be encoded and compilation aborts with UnsupportedRegexException.

Source

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

    private DFACaptureGroupLazyTransition createWithLookup(DFAStateNodeBuilder s,
                    EconomicMap<DFACaptureGroupPartialTransition, ArrayList<Integer>>[] maps, int i) {
        if (i < 0) {
            return null;
        }
        EconomicMap<DFACaptureGroupPartialTransition, ArrayList<Integer>> map = maps[i];
        if (map.size() == 1) {
            return createSingleLazyTransition(maps, i);
        }
        DFACaptureGroupPartialTransition[] transitions = new DFACaptureGroupPartialTransition[map.size()];
        if (lookupTableRequired(map)) {
            /*
             * Generate a lookup table to map lastTransitionIndex to the current successor's
             * grouping, followed by a regular if-else cascade.
             */
            if (map.size() > 0xff) {
                // bail out if we can't use byte[] as the lookup table
                throw new UnsupportedRegexException("too many branches in capture group tracking DFA", getNfa().getAst().getSource());
            }
            byte[] lookupTable = new byte[s.getPredecessors().length];
            MapCursor<DFACaptureGroupPartialTransition, ArrayList<Integer>> cursor = map.getEntries();
            int iCursor = 0;
            while (cursor.advance()) {
                transitions[iCursor] = cursor.getKey();
                for (int t : cursor.getValue()) {
                    lookupTable[t] = (byte) iCursor;
                }
                iCursor++;
            }
            return DFACaptureGroupLazyTransition.BranchesWithLookupTable.create(transitions, lookupTable);
        } else {
            /*
             * There is only one group with more than one element, so we can avoid the lookup table
             * by generating an if-else cascade where the last else-branch is the group with more
             * than one element.
             */

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Convert capturing branches to non-capturing '(?:...)' wherever the group positions are not consumed
2. Reduce alternation width: use character classes [abc] instead of (a|b|c) when branches are single characters
3. Split the pattern into multiple simpler regexes run in sequence
4. Do not force linear execution for such patterns; rely on the automatic backtracking fallback

Example fix

// before
String p = "(a|b|c|d)(e|f|g|h)(i|j|k|l)..."; // capturing wide alternations

// after
String p = "[abcd][efgh][ijkl]..."; // classes, capture only what you read

try {
    return compileDfaExecutor(pattern);
} catch (UnsupportedRegexException e) {
    if (e.getReason().contains("too many branches")) {
        return compileDfaExecutor(replaceCapturingBranchesWithClasses(pattern));
    }
    throw e;
}

When it happens

Trigger: Compiling in CG-tracking DFA mode a state with a very large predecessor set whose capture-group updates fall into more than 255 distinct equivalence classes — typically patterns with many capture groups combined with wide alternations ((a|b|...|z)(x|y|...)... with each branch capturing).

Common situations: Generated lexers/grammars with per-branch capture groups; like the other DFA-generation bailouts, it is normally swallowed into the backtracking fallback and only surfaces under forceLinearExecution/eager DFA or as a log line.

Related errors

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

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