oracle/graal · error · UnsupportedRegexException

Regex has unsupported bounded quantifier

Error message

Regex has unsupported bounded quantifier

What it means

Thrown by DFAGenerator.checkIfAllQuantifierOperationsAreSupported when a bounded-quantifier tracking operation is not supported by its counter tracker. Bounded quantifiers are tracked in DFAs with counters; each CounterTracker.support(op) check validates that the counter layout (number of counters, increment/reset semantics needed by the op) is representable. If any op is unsupported, the whole pattern is rejected with UnsupportedRegexException('Regex has unsupported bounded quantifier').

Source

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

                    }
                }
                for (int i = 0; i < inc.size(); i++) {
                    inc.get(i).subtract(set1.get(i));
                    bqTrivialAlwaysReEnter.subtract(inc.get(i));
                    inc.get(i).clear();
                    set1.get(i).clear();
                }
            }
        }
    }

    private static void checkIfAllQuantifierOperationsAreSupported(ObjectArrayBuffer<DFAAbstractNode> nodes, CounterTracker[] counterTrackers) {
        for (DFAAbstractNode node : nodes) {
            if (node instanceof DFABQTrackingTransitionOpsNode t) {
                for (long op : t.getOperations()) {
                    int qId = TransitionOp.getQuantifierID(op);
                    if (!counterTrackers[qId].support(op)) {
                        throw new UnsupportedRegexException("Regex has unsupported bounded quantifier");
                    }
                }
            }
        }
    }

    private void createInitialStatesForward() {
        final int numberOfEntryPoints = nfa.getAnchoredEntry().length;
        entryStates = new DFAStateNodeBuilder[numberOfEntryPoints * 2];
        nfa.setInitialLoopBack(isSearching() && !nfa.getAst().getFlags().isSticky());
        for (int i = 0; i < numberOfEntryPoints; i++) {
            if (nfa.getAnchoredEntry()[i] == null) {
                assert nfa.getUnAnchoredEntry()[i] == null;
                entryStates[i] = null;
                entryStates[numberOfEntryPoints + i] = null;
            } else if (nfa.getUnAnchoredEntry()[i] == null) {
                entryStates[i] = createInitialState(createTransitionBuilder(createNFATransitionSet(nfa.getAnchoredEntry()[i])));
                entryStates[numberOfEntryPoints + i] = null;

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Reduce the number of distinct bounded quantifiers in the pattern, especially interleaved/nested ones
2. Replace inner bounded quantifiers with unbounded '+' or '*' plus explicit count validation after matching
3. Unroll small fixed repetitions literally (a{3} -> aaa) where feasible
4. Let the engine fall back to backtracking (do not force linear execution) if the pattern is trusted

Example fix

// before
String p = "(\\d{2,4}-){2,3}\\d{1,2}"; // several interleaved bounded quantifiers

// after
String p = "(\\d+-){2,3}\\d+"; // then verify digit counts in code

try {
    return compile(pattern, forceLinearOptions);
} catch (UnsupportedRegexException e) {
    if (e.getReason().contains("bounded quantifier")) {
        return compile(unrollBoundedQuantifiers(pattern), forceLinearOptions);
    }
    throw e;
}

When it happens

Trigger: Compiling in DFA mode a pattern whose bounded quantifier combination exceeds the counter-tracker model — e.g. more interleaved bounded quantifiers than the tracker has counters, or quantifier nesting whose increment/reset ordering the chosen tracker cannot express ((a{2,4}b{3,5}){2,3}c{1,2}...).

Common situations: Validation-style patterns stacking several {n,m} quantifiers; usually invisible because the default pipeline catches this and falls back to backtracking — it becomes user-visible with forceLinearExecution, eager DFA compilation, or in 'NFA generator bailout' log lines.

Related errors

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

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