{"record":{"id":"5520e124c0574640","repo":"oracle/graal","slug":"nfa-explosion","errorCode":null,"errorMessage":"NFA explosion","messagePattern":"NFA 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 when the NFA generator (NFAGenerator.java:77) would create more NFA states than TRegexOptions.TRegexMaxNFASize (3500). TRegex compiles the AST to an NFA before DFA conversion; patterns whose NFA representation grows beyond the fixed threshold are rejected with UnsupportedRegexException to bound compile time and DFA memory. The limit is a static constant, not a runtime option.","triggerScenarios":"Compiling (via the Truffle regex language) a pattern whose AST expansion yields >3500 NFA states: large alternations, many groups with quantifiers, character-class ranges combined with case-insensitive folding, or nested optional groups. Every state creation calls Counter.inc and the ThresholdCounter trips once the count passes 3500.","commonSituations":"Guest-language apps (JS, Python, Ruby on GraalVM) compiling generated or data-derived patterns; patterns that were fine in a backtracking engine (PCRE, Ruby) but exceed TRegex's DFA-oriented NFA budget; also patterns that force the non-TraceFinder NFA path (forward matching without lookbehind).","solutions":["Reduce pattern complexity: factor out common prefixes of alternations, remove redundant groups, use character classes instead of single-char alternations.","Move huge literal alternations out of the regex into application logic (set/trie lookup).","Catch UnsupportedRegexException and fall back to a backtracking regex engine for that one pattern."],"exampleFix":"// before\nconst re = new RegExp(hugeGeneratedAlternation); // throws at compile\n\n// after\ntry {\n    const re = new RegExp(pattern);\n} catch (e if e instanceof UnsupportedRegexException) {\n    const re = compileWithFallbackEngine(pattern);\n}","handlingStrategy":"fallback","validationCode":"// Cheap static check before compiling: reject obviously huge patterns\nif (pattern.length() > PATTERN_LENGTH_BUDGET || countTopLevelAlternatives(pattern) > ALT_BUDGET) {\n    return fallbackMatcher(pattern);\n}","typeGuard":null,"tryCatchPattern":"try { compile(pattern); } catch (UnsupportedRegexException e) { /* message contains 'NFA explosion' */ return backtrackingFallback(pattern); }","preventionTips":["Lint generated regexes for alternation count and nesting depth before shipping.","Remember TRegexMaxNFASize (3500) is a compile-time constant — the only fix is simplifying the pattern, not tuning.","Always pair TRegex compilation with a documented fallback engine for unsupported patterns."],"tags":["regex","nfa","complexity-limit","truffle","tregex"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}