{"record":{"id":"8f14871de5950181","repo":"oracle/graal","slug":"too-many-branches-in-capture-group-tracking-dfa","errorCode":null,"errorMessage":"too many branches in capture group tracking DFA","messagePattern":"too many branches in capture group tracking DFA","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":2007,"sourceCode":"\n    private DFACaptureGroupLazyTransition createWithLookup(DFAStateNodeBuilder s,\n                    EconomicMap<DFACaptureGroupPartialTransition, ArrayList<Integer>>[] maps, int i) {\n        if (i < 0) {\n            return null;\n        }\n        EconomicMap<DFACaptureGroupPartialTransition, ArrayList<Integer>> map = maps[i];\n        if (map.size() == 1) {\n            return createSingleLazyTransition(maps, i);\n        }\n        DFACaptureGroupPartialTransition[] transitions = new DFACaptureGroupPartialTransition[map.size()];\n        if (lookupTableRequired(map)) {\n            /*\n             * Generate a lookup table to map lastTransitionIndex to the current successor's\n             * grouping, followed by a regular if-else cascade.\n             */\n            if (map.size() > 0xff) {\n                // bail out if we can't use byte[] as the lookup table\n                throw new UnsupportedRegexException(\"too many branches in capture group tracking DFA\", getNfa().getAst().getSource());\n            }\n            byte[] lookupTable = new byte[s.getPredecessors().length];\n            MapCursor<DFACaptureGroupPartialTransition, ArrayList<Integer>> cursor = map.getEntries();\n            int iCursor = 0;\n            while (cursor.advance()) {\n                transitions[iCursor] = cursor.getKey();\n                for (int t : cursor.getValue()) {\n                    lookupTable[t] = (byte) iCursor;\n                }\n                iCursor++;\n            }\n            return DFACaptureGroupLazyTransition.BranchesWithLookupTable.create(transitions, lookupTable);\n        } else {\n            /*\n             * There is only one group with more than one element, so we can avoid the lookup table\n             * by generating an if-else cascade where the last else-branch is the group with more\n             * than one element.\n             */","sourceCodeStart":1989,"sourceCodeEnd":2025,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java#L1989-L2025","documentation":"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.","triggerScenarios":"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).","commonSituations":"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.","solutions":["Convert capturing branches to non-capturing '(?:...)' wherever the group positions are not consumed","Reduce alternation width: use character classes [abc] instead of (a|b|c) when branches are single characters","Split the pattern into multiple simpler regexes run in sequence","Do not force linear execution for such patterns; rely on the automatic backtracking fallback"],"exampleFix":"// before\nString p = \"(a|b|c|d)(e|f|g|h)(i|j|k|l)...\"; // capturing wide alternations\n\n// after\nString p = \"[abcd][efgh][ijkl]...\"; // classes, capture only what you read","handlingStrategy":"try-catch","validationCode":null,"typeGuard":null,"tryCatchPattern":"try {\n    return compileDfaExecutor(pattern);\n} catch (UnsupportedRegexException e) {\n    if (e.getReason().contains(\"too many branches\")) {\n        return compileDfaExecutor(replaceCapturingBranchesWithClasses(pattern));\n    }\n    throw e;\n}","preventionTips":["Use character classes instead of capturing single-char alternations","Keep capture groups minimal in CG-tracking DFA patterns; rely on the automatic backtracking fallback for the rest"],"tags":["regex","tregex","dfa","capture-groups","limits"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}