oracle/graal · error · UnsupportedRegexException

too many parallel NFA states in one DFA state for bounded qu

Error message

too many parallel NFA states in one DFA state for bounded quantifier tracking

What it means

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.

Source

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

         * every DFA state.
         */
        private int[] newOrder;
        private int[] copySource;
        private TBitSet targetsUsed;
        private TBitSet copyTargets;
        private final LongArrayBuffer ops = new LongArrayBuffer();
        private final LongArrayBuffer opsSet1 = new LongArrayBuffer();

        private QuantifierMappingBuilder(StateMapping[] stateMappings) {
            this.stateMappings = stateMappings;
        }

        private void addState(DFAStateNodeBuilder state, NFAState mapState) {
            StateSet<NFA, NFAState> states = stateMappings[state.getId()].states;
            if (states.add(mapState)) {
                maxMapSize = Math.max(maxMapSize, states.size());
                if (maxMapSize > 0xff) {
                    throw new UnsupportedRegexException("too many parallel NFA states in one DFA state for bounded quantifier tracking");
                }
            }
        }

        private void initBuffers() {
            newOrder = new int[maxMapSize];
            copySource = new int[maxMapSize];
            targetsUsed = new TBitSet(maxMapSize);
            copyTargets = new TBitSet(maxMapSize);
        }

        private void resetBuffers() {
            Arrays.fill(newOrder, -1);
            Arrays.fill(copySource, -1);
            targetsUsed.clear();
            copyTargets.clear();
            opsSet1.clear();
            ops.clear();

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Unroll or flatten nested bounded quantifiers: (?:x{0,20}){0,20} approximates to x{0,400} where semantics allow
2. Replace bounded quantifiers with unbounded ones plus a length check in host code (e.g. 'x+' then verify count)
3. Split the pattern into several passes, each with simpler bounded tracking
4. Do not force linear execution for such patterns; let the engine use the backtracking matcher

Example fix

// before
String p = "(?:\\w{1,3}\\.){1,3}\\w{1,3}"; // stacked bounded quantifiers

// after
String p = "\\w+(?:\\.\\w+){0,3}"; // simpler bounded structure

// Usually no caller action needed: TRegexCompilationRequest catches this and uses the
// backtracking NFA matcher. Only handle explicitly when forceLinearExecution is set:
try {
    return compile(pattern, forceLinearOptions);
} catch (UnsupportedRegexException e) {
    return compile(simplifyBoundedQuantifiers(pattern), forceLinearOptions);
}

When it happens

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

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

Related errors

• too many capture group transitions
• Regex has unsupported bounded quantifier
• too many branches in capture group tracking DFA
• Too much additional capture group tracking overhead
• dependency cycle

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