{"record":{"id":"7efc6b974baea47e","repo":"oracle/graal","slug":"regex-cannot-be-executed-in-linear-time","errorCode":null,"errorMessage":"regex cannot be executed in linear time","messagePattern":"regex cannot be executed in linear time","errorType":"exception","errorClass":"UnsupportedRegexException","httpStatus":null,"severity":"error","filePath":"regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/TRegexCompilationRequest.java","lineNumber":197,"sourceCode":"                    return new DeadRegexExecNode(language, source);\n                }\n                if (ast.getRoot().hasQuantifiers()) {\n                    // This branch is only taken in boolean match mode when not all quantifiers\n                    // could be unrolled. Execution of the remaining bounded quantifiers is\n                    // supported in DFA mode, but not in NFA mode.\n                    return TRegexExecNode.create(ast, nfa, compileLazyDFAExecutor(new RegexProfile(), true));\n                } else {\n                    return TRegexExecNode.create(ast, nfa, TRegexExecNode.NFARegexSearchNode.create(language, TRegexNFAExecutorNode.create(nfa)));\n                }\n            } catch (UnsupportedRegexException e) {\n                // fall back to backtracking executor\n                Loggers.LOG_MATCHING_STRATEGY.fine(() -> \"NFA generator bailout: \" + e.getReason() + \", using back-tracking matcher\");\n            }\n        } else {\n            Loggers.LOG_MATCHING_STRATEGY.fine(() -> \"using back-tracking matcher, reason: \" + ast.canTransformToDFAFailureReason());\n        }\n        if (source.getOptions().isForceLinearExecution()) {\n            throw new UnsupportedRegexException(\"regex cannot be executed in linear time\", source);\n        }\n        Loggers.LOG_MATCHING_STRATEGY.fine(() -> \"using backtracking NFA matcher\");\n        return TRegexExecNode.create(ast, nfa, TRegexExecNode.NFARegexSearchNode.create(language, compileBacktrackingExecutor()));\n    }\n\n    private static final class StackEntry {\n        private final PureNFA nfa;\n        private final TRegexExecutorBaseNode[] subExecutors;\n        private int i = 0;\n\n        private StackEntry(PureNFA nfa) {\n            this.nfa = nfa;\n            this.subExecutors = nfa.getSubtrees().length == 0 ? NO_SUB_EXECUTORS : new TRegexExecutorBaseNode[nfa.getSubtrees().length];\n        }\n    }\n\n    public TRegexBacktrackerSubExecutorNode compileBacktrackingExecutor() {\n        pureNFA = PureNFAGenerator.mapToNFA(ast);","sourceCodeStart":179,"sourceCodeEnd":215,"githubUrl":"https://github.com/oracle/graal/blob/a66e9ccd1d7bf2552883939aa0788dfd0e294aab/regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/TRegexCompilationRequest.java#L179-L215","documentation":"Thrown by TRegexCompilationRequest when the regex cannot be compiled to a linear-time automaton and the caller demanded linear execution. TRegex first tries NFA/DFA strategies; any UnsupportedRegexException from those stages is caught and normally falls back to a backtracking matcher — but if RegexOptions.isForceLinearExecution() is set (used by RE2-style/linear-time guarantees), the fallback is refused and the error propagates.","triggerScenarios":"Compiling a regex with RegexOptions.forceLinearExecution enabled (e.g. 'Automatic-Engine=force-linear-time' or the equivalent option set programmatically) where the pattern contains features the DFA cannot handle: backreferences, lookarounds, or anything that made the NFA generator bail out with a caught UnsupportedRegexException.","commonSituations":"Applications that enable force-linear-time to guarantee protection against ReDoS (untrusted pattern matching services), then receive a user-supplied pattern with backreferences or lookbehind; migrating from RE2 or Rust regex where such patterns are also rejected but with different messages.","solutions":["Remove the non-linear features from the pattern: backreferences (\\\\1), lookbehind ((?<=...)), and other constructs that cannot be expressed by a finite automaton","If the pattern is trusted, drop the forceLinearExecution option and let TRegex fall back to the backtracking NFA matcher","Replace backreference checks with post-match validation in host code (match the automaton-friendly pattern, then verify the captured groups manually)","For untrusted-pattern services, reject non-compilable patterns with a user-facing error instead of falling back"],"exampleFix":"// before: forced linear time + backreference\noptions.setForceLinearExecution(true);\ncompile(\"(\\\\w+)\\\\s\\\\1\");\n\n// after: automaton-friendly, validate in code\noptions.setForceLinearExecution(true);\ncompile(\"(\\\\w+)\\\\s(\\\\w+)\"); // then check group(1).equals(group(2))","handlingStrategy":"fallback","validationCode":"// rough pre-check for automaton-incompatible constructs before forcing linear execution\nboolean isLikelyLinearSafe(String pattern) {\n    return !java.util.regex.Pattern.compile(\"\\\\\\\\[1-9]|\\\\(\\\\?<[=!]\").matcher(pattern).find();\n}","typeGuard":null,"tryCatchPattern":"try {\n    RegexObject re = compile(pattern, forceLinearOptions);\n} catch (UnsupportedRegexException e) {\n    if (e.getReason().contains(\"linear time\")) {\n        re = compile(stripBackreferences(pattern), defaultOptions); // trusted input only\n    } else { throw e; }\n}","preventionTips":["Only enable forceLinearExecution for patterns you have vetted to be automaton-friendly (no backreferences, no lookbehind)","For untrusted patterns, treat a linear-time bailout as an input rejection, not an engine failure","Watch Loggers.LOG_MATCHING_STRATEGY fine logs to see why the NFA/DFA strategies bail out"],"tags":["regex","tregex","linear-time","redos","engine-selection"],"backgroundTag":null,"analyzedSha":"a66e9ccd1d7bf2552883939aa0788dfd0e294aab","analyzedAt":"2026-08-14T13:58:47.161Z","schemaVersion":2},"datasetVersion":"2026-08-15T22:17:37.221Z"}