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.

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.

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