oracle/graal · error · UnsupportedRegexException

PureNFA transition explosion

Error message

PureNFA transition explosion

What it means

Thrown by PureNFAGenerator.java:59 when the pure NFA's transition count exceeds TRegexMaxPureNFATransitions (1,000,000). Like the state limit, it guards against combinatorial unrolling, but counts edges: wide classes under quantifiers multiply transitions. Exceeding it throws UnsupportedRegexException at compile time.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/parser/Counter.java:91

        count -= i;
        return ret;
    }

    public static class ThresholdCounter extends Counter {

        private final int max;
        private final String errorMsg;

        public ThresholdCounter(int max, String errorMsg) {
            this.max = max;
            this.errorMsg = errorMsg;
        }

        @Override
        public int inc(int i) {
            final int ret = super.inc(i);
            if (getCount() > max) {
                throw new UnsupportedRegexException(errorMsg);
            }
            return ret;
        }
    }

    public static class ThreadSafeCounter extends Counter {

        @Override
        public int inc() {
            int c = count;
            if (c < Integer.MAX_VALUE) {
                count = c + 1;
            }
            return count;
        }

        @Override
        public int inc(int i) {

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Shrink repetition bounds and class width (ASCII-only classes, no case folding where possible).
2. Replace the regex check with an arithmetic/length check in guest code.
3. Catch UnsupportedRegexException and use a backtracking fallback engine.

Example fix

// before
const re = /^[a-zA-Z0-9]{0,100000}$/; // ~6.2M transitions

// after
const ok = str.length <= 100000 && /^[a-zA-Z0-9]+$/.test(str); // engine streams, no unroll

try { compile(pattern); } catch (UnsupportedRegexException e) { /* 'PureNFA transition explosion' */ return backtrackingFallback(pattern); }

When it happens

Trigger: Compiling pure-NFA-routed patterns where states x character-class edges exceed 1e6: e.g. [a-z]{0,1000} with case folding, or alternation of classes inside a large bounded repeat.

Common situations: Large bounded repeats over multi-character classes with IGNORE_CASE on GraalVM; generated patterns for range validation; works after shrinking bounds or alphabet.

Related errors

• NFA transition explosion
• TraceFinder NFA transition explosion
• PureNFA explosion
• NFA explosion
• TraceFinder NFA explosion

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