oracle/graal · error · UnsupportedRegexException

NFA explosion

Error message

NFA explosion

What it means

Thrown when the NFA generator (NFAGenerator.java:77) would create more NFA states than TRegexOptions.TRegexMaxNFASize (3500). TRegex compiles the AST to an NFA before DFA conversion; patterns whose NFA representation grows beyond the fixed threshold are rejected with UnsupportedRegexException to bound compile time and DFA memory. The limit is a static constant, not a runtime option.

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. Reduce pattern complexity: factor out common prefixes of alternations, remove redundant groups, use character classes instead of single-char alternations.
2. Move huge literal alternations out of the regex into application logic (set/trie lookup).
3. Catch UnsupportedRegexException and fall back to a backtracking regex engine for that one pattern.

Example fix

// before
const re = new RegExp(hugeGeneratedAlternation); // throws at compile

// after
try {
    const re = new RegExp(pattern);
} catch (e if e instanceof UnsupportedRegexException) {
    const re = compileWithFallbackEngine(pattern);
}

// Cheap static check before compiling: reject obviously huge patterns
if (pattern.length() > PATTERN_LENGTH_BUDGET || countTopLevelAlternatives(pattern) > ALT_BUDGET) {
    return fallbackMatcher(pattern);
}

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

When it happens

Trigger: Compiling (via the Truffle regex language) a pattern whose AST expansion yields >3500 NFA states: large alternations, many groups with quantifiers, character-class ranges combined with case-insensitive folding, or nested optional groups. Every state creation calls Counter.inc and the ThresholdCounter trips once the count passes 3500.

Common situations: Guest-language apps (JS, Python, Ruby on GraalVM) compiling generated or data-derived patterns; patterns that were fine in a backtracking engine (PCRE, Ruby) but exceed TRegex's DFA-oriented NFA budget; also patterns that force the non-TraceFinder NFA path (forward matching without lookbehind).

Related errors

• parse tree explosion
• NFA transition explosion
• TraceFinder NFA explosion
• TraceFinder NFA transition explosion
• PureNFA explosion

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