{"record":{"id":"8cc43c2dcd80545f","repo":"oracle/graal","slug":"too-many-parallel-nfa-states-in-one-dfa-state-for","errorCode":null,"errorMessage":"too many parallel NFA states in one DFA state for bounded quantifier tracking","messagePattern":"too many parallel NFA states in one DFA state for bounded quantifier tracking","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":425,"sourceCode":"         * every DFA state.\n         */\n        private int[] newOrder;\n        private int[] copySource;\n        private TBitSet targetsUsed;\n        private TBitSet copyTargets;\n        private final LongArrayBuffer ops = new LongArrayBuffer();\n        private final LongArrayBuffer opsSet1 = new LongArrayBuffer();\n\n        private QuantifierMappingBuilder(StateMapping[] stateMappings) {\n            this.stateMappings = stateMappings;\n        }\n\n        private void addState(DFAStateNodeBuilder state, NFAState mapState) {\n            StateSet<NFA, NFAState> states = stateMappings[state.getId()].states;\n            if (states.add(mapState)) {\n                maxMapSize = Math.max(maxMapSize, states.size());\n                if (maxMapSize > 0xff) {\n                    throw new UnsupportedRegexException(\"too many parallel NFA states in one DFA state for bounded quantifier tracking\");\n                }\n            }\n        }\n\n        private void initBuffers() {\n            newOrder = new int[maxMapSize];\n            copySource = new int[maxMapSize];\n            targetsUsed = new TBitSet(maxMapSize);\n            copyTargets = new TBitSet(maxMapSize);\n        }\n\n        private void resetBuffers() {\n            Arrays.fill(newOrder, -1);\n            Arrays.fill(copySource, -1);\n            targetsUsed.clear();\n            copyTargets.clear();\n            opsSet1.clear();\n            ops.clear();","sourceCodeStart":407,"sourceCodeEnd":443,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/dfa/DFAGenerator.java#L407-L443","documentation":"Thrown by DFAGenerator's QuantifierMappingBuilder when bounded-quantifier tracking would need to track more than 255 (0xff) parallel NFA states inside a single DFA state. The per-state mapping table is a byte-indexed array (maxMapSize <= 0xff), so exceeding it aborts DFA generation with UnsupportedRegexException.","triggerScenarios":"Compiling (in DFA mode) a pattern where bounded quantifiers like (?:x{0,20}){0,20}, nested bounded quantifiers, or bounded quantifiers over large alternations make one DFA state represent more than 255 simultaneous NFA positions with distinct counter mappings.","commonSituations":"Complex validation patterns with stacked {n,m} quantifiers (e.g. password rules, date/phone formats); like other DFA-generation bailouts it is normally caught and silently falls back to backtracking unless forceLinearExecution or eager DFA compilation is in play.","solutions":["Unroll or flatten nested bounded quantifiers: (?:x{0,20}){0,20} approximates to x{0,400} where semantics allow","Replace bounded quantifiers with unbounded ones plus a length check in host code (e.g. 'x+' then verify count)","Split the pattern into several passes, each with simpler bounded tracking","Do not force linear execution for such patterns; let the engine use the backtracking matcher"],"exampleFix":"// before\nString p = \"(?:\\\\w{1,3}\\\\.){1,3}\\\\w{1,3}\"; // stacked bounded quantifiers\n\n// after\nString p = \"\\\\w+(?:\\\\.\\\\w+){0,3}\"; // simpler bounded structure","handlingStrategy":"fallback","validationCode":null,"typeGuard":null,"tryCatchPattern":"// Usually no caller action needed: TRegexCompilationRequest catches this and uses the\n// backtracking NFA matcher. Only handle explicitly when forceLinearExecution is set:\ntry {\n    return compile(pattern, forceLinearOptions);\n} catch (UnsupportedRegexException e) {\n    return compile(simplifyBoundedQuantifiers(pattern), forceLinearOptions);\n}","preventionTips":["Avoid deeply nested bounded quantifiers in patterns destined for DFA compilation","Verify {n,m} counts in host code instead of encoding them all in the pattern"],"tags":["regex","tregex","dfa","bounded-quantifier","limits"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}