{"record":{"id":"048a34b151be63b3","repo":"oracle/graal","slug":"purenfa-transition-explosion","errorCode":null,"errorMessage":"PureNFA transition explosion","messagePattern":"PureNFA transition 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 PureNFAGenerator.java:59 when the pure NFA's transition count exceeds TRegexMaxPureNFATransitions (1,000,000). Like the state limit, it guards against combinatorial unrolling, but counts edges: wide classes under quantifiers multiply transitions. Exceeding it throws UnsupportedRegexException at compile time.","triggerScenarios":"Compiling pure-NFA-routed patterns where states x character-class edges exceed 1e6: e.g. [a-z]{0,1000} with case folding, or alternation of classes inside a large bounded repeat.","commonSituations":"Large bounded repeats over multi-character classes with IGNORE_CASE on GraalVM; generated patterns for range validation; works after shrinking bounds or alphabet.","solutions":["Shrink repetition bounds and class width (ASCII-only classes, no case folding where possible).","Replace the regex check with an arithmetic/length check in guest code.","Catch UnsupportedRegexException and use a backtracking fallback engine."],"exampleFix":"// before\nconst re = /^[a-zA-Z0-9]{0,100000}$/; // ~6.2M transitions\n\n// after\nconst ok = str.length <= 100000 && /^[a-zA-Z0-9]+$/.test(str); // engine streams, no unroll","handlingStrategy":"fallback","validationCode":null,"typeGuard":null,"tryCatchPattern":"try { compile(pattern); } catch (UnsupportedRegexException e) { /* 'PureNFA transition explosion' */ return backtrackingFallback(pattern); }","preventionTips":["Estimate transitions mentally: states x class-width x folds; keep under ~1e6.","Prefer ASCII classes and avoid needless IGNORE_CASE on huge repeats.","Replace full-string length validation regexes with length checks in code."],"tags":["regex","nfa","purenfa","transitions","complexity-limit","tregex"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}