oracle/graal · error · UnsupportedRegexException

TraceFinder NFA explosion

Error message

TraceFinder NFA explosion

What it means

Thrown by the TraceFinder NFA generator (NFATraceFinderGenerator.java:97) when the backward-search NFA built to accelerate substring search (TraceFinder) exceeds TRegexMaxNFASize (3500) states. TRegex builds a separate NFA for prefix/suffix tracing of patterns containing lookarounds; that auxiliary automaton is separately capped. Rejection means only the optimization is lost or the pattern is unsupported, depending on caller fallback.

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. Rewrite the lookbehind as an alternation or capture-and-check when feasible, avoiding the TraceFinder path.
2. Shorten the prefix portion of the pattern that the TraceFinder must encode.
3. Catch UnsupportedRegexException and fall back to a backtracking engine for that pattern.

Example fix

// before
const re = /(?<=prefixA|prefixB|...|prefixZ)target/; // TraceFinder NFA too big

// after
const re = /(?:prefixA|prefixB|...|prefixZ)(target)/; // check group 1 manually

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

When it happens

Trigger: Compiling patterns with lookbehind/lookahead or anchored-prefix constructs that trigger TraceFinder generation (typically backward matching), where the trace NFA exceeds 3500 states — e.g. long alternation prefixes inside a pattern that also uses lookbehind.

Common situations: Guest-language code using lookbehind ((?<=...)) or large leading alternations on GraalVM JS/Python; the same pattern compiles fine without the lookaround because the TraceFinder path is not taken.

Related errors

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

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