oracle/graal · error · UnsupportedRegexException

NFA transition explosion

Error message

NFA transition explosion

What it means

Thrown when the number of NFA transitions in NFAGenerator (NFAGenerator.java:78) exceeds Short.MAX_VALUE (32767). Transition IDs are stored as short in TRegex's intermediate representation, so this is a representation-level hard limit, not a tunable knob. Patterns with many states times many outgoing edges (e.g. classes with many case-foldings) hit it before or after the state limit.

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 wide case-insensitive classes (restrict to ASCII, or split matching into case-sensitive plus normalized input).
2. Simplify the pattern to cut the state/transition product (see NFA explosion guidance).
3. Catch UnsupportedRegexException at the compile site and use a backtracking fallback for that pattern.

Example fix

// before
const re = /verylongpatternwith|many|alternations/i; // transition count > 32767

// after
const re = new RegExp(pattern, 'i');
// or, if unsupported:
try { compile(pattern, IGNORE_CASE); }
catch (UnsupportedRegexException e) { compile(normalizeCase(pattern), 0); }

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

When it happens

Trigger: Compiling a pattern where states x outgoing transitions > 32767: long case-insensitive patterns over multi-case-folding alphabets, wide character classes under IGNORE_CASE, or dense alternations. The transitionID ThresholdCounter is incremented per transition added during NFAGenerator.run.

Common situations: Case-insensitive matching of long patterns in JS/Python on GraalVM (case folding multiplies edges), Unicode-heavy classes, generated patterns. Reported as 'NFA transition explosion' even when the state count itself is under 3500.

Related errors

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

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