{"record":{"id":"986d8ccbc183f0b1","repo":"oracle/graal","slug":"purenfa-explosion","errorCode":null,"errorMessage":"PureNFA explosion","messagePattern":"PureNFA explosion","errorType":"exception","errorClass":"UnsupportedRegexException","httpStatus":null,"severity":"error","filePath":"regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/parser/Counter.java","lineNumber":91,"sourceCode":"        count -= i;\n        return ret;\n    }\n\n    public static class ThresholdCounter extends Counter {\n\n        private final int max;\n        private final String errorMsg;\n\n        public ThresholdCounter(int max, String errorMsg) {\n            this.max = max;\n            this.errorMsg = errorMsg;\n        }\n\n        @Override\n        public int inc(int i) {\n            final int ret = super.inc(i);\n            if (getCount() > max) {\n                throw new UnsupportedRegexException(errorMsg);\n            }\n            return ret;\n        }\n    }\n\n    public static class ThreadSafeCounter extends Counter {\n\n        @Override\n        public int inc() {\n            int c = count;\n            if (c < Integer.MAX_VALUE) {\n                count = c + 1;\n            }\n            return count;\n        }\n\n        @Override\n        public int inc(int i) {","sourceCodeStart":73,"sourceCodeEnd":109,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/parser/Counter.java#L73-L109","documentation":"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.","triggerScenarios":"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.","commonSituations":"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'.","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."],"exampleFix":"// before\nconst re = /^(a{0,50}){0,50}$/; // unrolls up to 2500 copies per state -> explosion\n\n// after\nconst re = /^a{0,2500}$/; // single bounded quantifier","handlingStrategy":"fallback","validationCode":"// Reject multiplicative bounded-repeat shapes before compiling\nif (pattern.matches(\"(?s).*\\\\{0?,\\\\d+\\\\}.*\\\\{0?,\\\\d+\\\\}.*\")) {\n    warnAndFallback(pattern); // nested counted repeats risk PureNFA explosion\n}","typeGuard":null,"tryCatchPattern":"try { compile(pattern); } catch (UnsupportedRegexException e) { /* 'PureNFA explosion' */ return backtrackingFallback(pattern); }","preventionTips":["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."],"tags":["regex","nfa","purenfa","quantifiers","complexity-limit","tregex"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}