What causes "PureNFA explosion" in oracle/graal?

Rewrote nested bounded quantifiers into a single bound: (a{0,100}){0,100} -> a{0,10000} (single unroll) or use a loop in guest code.

oracle/graal · error · UnsupportedRegexException

PureNFA explosion

Error message

PureNFA explosion

What it means

Thrown by the PureNFA compiler (PureNFAGenerator.java:58) when the NFA built for patterns that cannot be handled by the DFA engine (e.g. large bound quantifiers, backreferences-adjacent constructs unrolled by the pure NFA) exceeds TRegexMaxPureNFASize (1,000,000 states). The PureNFA budget is much larger than the DFA NFA budget because the NFA is executed directly. Exceeding it throws UnsupportedRegexException.

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

Rewrote nested bounded quantifiers into a single bound: (a{0,100}){0,100} -> a{0,10000} (single unroll) or use a loop in guest code.
Reduce the repetition bounds to what the data actually requires.
Catch UnsupportedRegexException and fall back to a backtracking engine.

Example fix

// before
const re = /^(a{0,50}){0,50}$/; // unrolls up to 2500 copies per state -> explosion

// after
const re = /^a{0,2500}$/; // single bounded quantifier

Defensive patterns

Strategy: fallback

Validate before calling

// Reject multiplicative bounded-repeat shapes before compiling
if (pattern.matches("(?s).*\\{0?,\\d+\\}.*\\{0?,\\d+\\}.*")) {
    warnAndFallback(pattern); // nested counted repeats risk PureNFA explosion
}

Try / catch

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

Prevention

Never nest bounded quantifiers ((x{m}){n}); flatten to a single bound.
Cap repetition bounds to what data requires, not maximal theoretical sizes.
Push large counted-repetition checks into guest-language loops instead of regex.

When it happens

Trigger: Compiling patterns that are routed to the pure NFA engine and unroll combinatorially: nested quantifiers with large bounds like (a{0,100}){0,100} or (a|b)*{large} repetitions; each unrolled copy adds states until the 1e6 threshold trips.

Common situations: Bounded-repeat patterns with multiplicative expansion ((x{m}){n} style), generated validators, or patterns ported from PCRE that rely on huge counted repetitions. GraalVM guest-language RegExp compilation fails at compile time with 'PureNFA explosion'.

Related errors

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