What causes "TraceFinder NFA transition explosion" in oracle/graal?

Narrow character classes inside lookbehind (e.g. replace \p{Any} with the actual expected alphabet).

oracle/graal · error · UnsupportedRegexException

TraceFinder NFA transition explosion

Error message

TraceFinder NFA transition explosion

What it means

Thrown by NFATraceFinderGenerator.java:98 when the TraceFinder NFA's transition count exceeds TRegexMaxNFASize (3500; the TraceFinder variant caps transitions by the same constant, unlike the main NFA which uses Short.MAX_VALUE). It bounds the auxiliary backward-search automaton used for substring tracing. Exceeding it raises UnsupportedRegexException during compilation.

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

Narrow character classes inside lookbehind (e.g. replace \p{Any} with the actual expected alphabet).
Move the length/lookbehind check into guest code, keeping the regex simple.
Catch UnsupportedRegexException and use a backtracking fallback.

Example fix

// before
const re = /(?<=.{100})token/; // trace NFA transitions > 3500

// after
const re = /token/g; // verify offset >= 100 in JS after match

Defensive patterns

Strategy: fallback

Try / catch

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

Prevention

Narrow character classes inside lookbehind to the actual alphabet.
Avoid quantified wide classes inside lookarounds ((?<=\p{L}{50,})).
Verify each lookaround pattern compiles in a startup smoke test.

When it happens

Trigger: Compiling a pattern that takes the TraceFinder path (lookbehind/backward search) whose trace NFA accumulates more than 3500 transitions — e.g. lookbehind containing wide character classes or long alternations.

Common situations: Lookbehind patterns with big classes (\p{L}{10,}, wide Unicode classes) on GraalVM guest languages; works when the class is narrowed or the lookbehind shortened.

Related errors

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