{"record":{"id":"04e05aea3e7639e6","repo":"oracle/graal","slug":"nfa-transition-explosion","errorCode":null,"errorMessage":"NFA transition explosion","messagePattern":"NFA 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 when the number of NFA transitions in NFAGenerator (NFAGenerator.java:78) exceeds Short.MAX_VALUE (32767). Transition IDs are stored as short in TRegex's intermediate representation, so this is a representation-level hard limit, not a tunable knob. Patterns with many states times many outgoing edges (e.g. classes with many case-foldings) hit it before or after the state limit.","triggerScenarios":"Compiling a pattern where states x outgoing transitions > 32767: long case-insensitive patterns over multi-case-folding alphabets, wide character classes under IGNORE_CASE, or dense alternations. The transitionID ThresholdCounter is incremented per transition added during NFAGenerator.run.","commonSituations":"Case-insensitive matching of long patterns in JS/Python on GraalVM (case folding multiplies edges), Unicode-heavy classes, generated patterns. Reported as 'NFA transition explosion' even when the state count itself is under 3500.","solutions":["Shrink wide case-insensitive classes (restrict to ASCII, or split matching into case-sensitive plus normalized input).","Simplify the pattern to cut the state/transition product (see NFA explosion guidance).","Catch UnsupportedRegexException at the compile site and use a backtracking fallback for that pattern."],"exampleFix":"// before\nconst re = /verylongpatternwith|many|alternations/i; // transition count > 32767\n\n// after\nconst re = new RegExp(pattern, 'i');\n// or, if unsupported:\ntry { compile(pattern, IGNORE_CASE); }\ncatch (UnsupportedRegexException e) { compile(normalizeCase(pattern), 0); }","handlingStrategy":"fallback","validationCode":null,"typeGuard":null,"tryCatchPattern":"try { compile(pattern); } catch (UnsupportedRegexException e) { /* 'NFA transition explosion' */ return backtrackingFallback(pattern); }","preventionTips":["Avoid very wide case-insensitive character classes in long patterns; fold input instead.","Note the 32767 (Short.MAX_VALUE) transition ceiling is structural and cannot be raised at runtime.","Add a regression test compiling your real-world pattern set to catch limit regressions early."],"tags":["regex","nfa","transitions","complexity-limit","tregex"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}