oracle/graal · error · UnsupportedRegexException

regex cannot be executed in linear time

Error message

regex cannot be executed in linear time

What it means

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.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/TRegexCompilationRequest.java:197

                    return new DeadRegexExecNode(language, source);
                }
                if (ast.getRoot().hasQuantifiers()) {
                    // This branch is only taken in boolean match mode when not all quantifiers
                    // could be unrolled. Execution of the remaining bounded quantifiers is
                    // supported in DFA mode, but not in NFA mode.
                    return TRegexExecNode.create(ast, nfa, compileLazyDFAExecutor(new RegexProfile(), true));
                } else {
                    return TRegexExecNode.create(ast, nfa, TRegexExecNode.NFARegexSearchNode.create(language, TRegexNFAExecutorNode.create(nfa)));
                }
            } catch (UnsupportedRegexException e) {
                // fall back to backtracking executor
                Loggers.LOG_MATCHING_STRATEGY.fine(() -> "NFA generator bailout: " + e.getReason() + ", using back-tracking matcher");
            }
        } else {
            Loggers.LOG_MATCHING_STRATEGY.fine(() -> "using back-tracking matcher, reason: " + ast.canTransformToDFAFailureReason());
        }
        if (source.getOptions().isForceLinearExecution()) {
            throw new UnsupportedRegexException("regex cannot be executed in linear time", source);
        }
        Loggers.LOG_MATCHING_STRATEGY.fine(() -> "using backtracking NFA matcher");
        return TRegexExecNode.create(ast, nfa, TRegexExecNode.NFARegexSearchNode.create(language, compileBacktrackingExecutor()));
    }

    private static final class StackEntry {
        private final PureNFA nfa;
        private final TRegexExecutorBaseNode[] subExecutors;
        private int i = 0;

        private StackEntry(PureNFA nfa) {
            this.nfa = nfa;
            this.subExecutors = nfa.getSubtrees().length == 0 ? NO_SUB_EXECUTORS : new TRegexExecutorBaseNode[nfa.getSubtrees().length];
        }
    }

    public TRegexBacktrackerSubExecutorNode compileBacktrackingExecutor() {
        pureNFA = PureNFAGenerator.mapToNFA(ast);

View on GitHub (pinned to a66e9ccd1d)

Solutions

1. Remove the non-linear features from the pattern: backreferences (\\1), lookbehind ((?<=...)), and other constructs that cannot be expressed by a finite automaton
2. If the pattern is trusted, drop the forceLinearExecution option and let TRegex fall back to the backtracking NFA matcher
3. Replace backreference checks with post-match validation in host code (match the automaton-friendly pattern, then verify the captured groups manually)
4. For untrusted-pattern services, reject non-compilable patterns with a user-facing error instead of falling back

Example fix

// before: forced linear time + backreference
options.setForceLinearExecution(true);
compile("(\\w+)\\s\\1");

// after: automaton-friendly, validate in code
options.setForceLinearExecution(true);
compile("(\\w+)\\s(\\w+)"); // then check group(1).equals(group(2))

// rough pre-check for automaton-incompatible constructs before forcing linear execution
boolean isLikelyLinearSafe(String pattern) {
    return !java.util.regex.Pattern.compile("\\\\[1-9]|\\(\\?<[=!]").matcher(pattern).find();
}

try {
    RegexObject re = compile(pattern, forceLinearOptions);
} catch (UnsupportedRegexException e) {
    if (e.getReason().contains("linear time")) {
        re = compile(stripBackreferences(pattern), defaultOptions); // trusted input only
    } else { throw e; }
}

When it happens

Trigger: 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.

Common situations: 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.

Related errors

• Too much additional capture group tracking overhead
• too many capture group transitions
• too many parallel NFA states in one DFA state for bounded qu
• dependency cycle
• Regex has unsupported bounded quantifier

AI-assisted analysis of oracle/graal@a66e9ccd1d (2026-08-14). Data as JSON: /api/errors/7efc6b974baea47e. Report an issue: GitHub.