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').

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…
• Cannot compile regex with empty state to DFA/NFA
• dependency cycle
• DFA transition size explosion
• empty path with look-ahead assertion in expression with…

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

Appendix: 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)