{"record":{"id":"f314c2b078964fd0","repo":"oracle/graal","slug":"tracefinder-nfa-explosion","errorCode":null,"errorMessage":"TraceFinder NFA explosion","messagePattern":"TraceFinder 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 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.","triggerScenarios":"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.","commonSituations":"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.","solutions":["Rewrite the lookbehind as an alternation or capture-and-check when feasible, avoiding the TraceFinder path.","Shorten the prefix portion of the pattern that the TraceFinder must encode.","Catch UnsupportedRegexException and fall back to a backtracking engine for that pattern."],"exampleFix":"// before\nconst re = /(?<=prefixA|prefixB|...|prefixZ)target/; // TraceFinder NFA too big\n\n// after\nconst re = /(?:prefixA|prefixB|...|prefixZ)(target)/; // check group 1 manually","handlingStrategy":"fallback","validationCode":null,"typeGuard":null,"tryCatchPattern":"try { compile(pattern); } catch (UnsupportedRegexException e) { /* 'TraceFinder NFA explosion' */ return backtrackingFallback(pattern); }","preventionTips":["Prefer rewriting lookbehind into capture groups plus a post-match offset check.","Keep the prefix portion of lookbehind patterns short and simple.","Test lookaround-heavy patterns explicitly on GraalVM before rollout."],"tags":["regex","nfa","tracefinder","lookbehind","complexity-limit","tregex"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}