What causes "nested look-behind assertions" in oracle/graal?

Flatten the look-behind's entry step to a single deterministic path, e.g. rewrite (?<=(?:a|b|c)x) as a character class (?<=[abc]x).

oracle/graal · error · UnsupportedRegexException

nested look-behind assertions

Error message

nested look-behind assertions

What it means

Thrown by ASTSuccessor.mergeLookArounds while merging look-around assertions into the successor's transitions: a look-behind's entry step must have exactly one successor and must not itself contain look-arounds. If lookBehind.getSuccessors().size() > 1 or that successor has nested look-arounds, the merge is undefined for the linear engine and the regex is rejected.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/tregex/nfa/ASTSuccessor.java:127

        }
        lookBehinds.addAll(addLookBehinds);
    }

    public ArrayList<TransitionBuilder<RegexAST, Term, ASTTransition>> getMergedStates(ASTTransitionCanonicalizer canonicalizer, CompilationBuffer compilationBuffer) {
        if (!lookAroundsMerged) {
            mergeLookArounds(canonicalizer, compilationBuffer);
            lookAroundsMerged = true;
        }
        return mergedStates;
    }

    private void mergeLookArounds(ASTTransitionCanonicalizer canonicalizer, CompilationBuffer compilationBuffer) {
        assert mergedStates.isEmpty();
        canonicalizer.addArgument(initialTransition, getInitialTransitionCharSet(compilationBuffer), initialTransition.getConstraints(), initialTransition.getOperations());
        for (ASTStep lookBehind : lookBehinds) {
            ASTSuccessor lb = lookBehind.getSuccessors().get(0);
            if (lookBehind.getSuccessors().size() > 1 || lb.hasLookArounds()) {
                throw new UnsupportedRegexException("nested look-behind assertions");
            }
            CodePointSet intersection = getInitialTransitionCharSet(compilationBuffer).createIntersection(lb.getInitialTransitionCharSet(compilationBuffer), compilationBuffer);
            if (intersection.matchesSomething()) {
                canonicalizer.addArgument(lb.getInitialTransition(), intersection, lb.getInitialTransition().getConstraints(), lb.getInitialTransition().getOperations());
            }
        }
        TransitionBuilder<RegexAST, Term, ASTTransition>[] mergedLookBehinds = canonicalizer.run(compilationBuffer);
        Collections.addAll(mergedStates, mergedLookBehinds);
        ArrayList<TransitionBuilder<RegexAST, Term, ASTTransition>> newMergedStates = new ArrayList<>();
        for (ASTStep lookAhead : lookAheads) {
            for (TransitionBuilder<RegexAST, Term, ASTTransition> state : mergedStates) {
                addAllIntersecting(canonicalizer, state, lookAhead, newMergedStates, compilationBuffer);
            }
            ArrayList<TransitionBuilder<RegexAST, Term, ASTTransition>> tmp = mergedStates;
            mergedStates = newMergedStates;
            newMergedStates = tmp;
            newMergedStates.clear();
        }

View on GitHub (pinned to a66e9ccd1d)

Solutions

Flatten the look-behind's entry step to a single deterministic path, e.g. rewrite (?<=(?:a|b|c)x) as a character class (?<=[abc]x).
Remove nested look-arounds: pull the inner assertion out of the look-behind or restructure with capture groups checked after the match.
Rely on engine fallback: the exception is caught in TRegexCompilationRequest/TRegexCompiler and the pattern is retried on the backtracking NFA executor, which supports these constructs — do not force linear-only options.
Do the look-behind check in application code on the matched substring instead of in the pattern.

Example fix

// before
String pattern = "(?<=(?:foo|bar)baz)quux";

// after
String pattern = "(?<=(?:foo|bar)baz)quux"; // kept, but compiled by backtracking engine
// or: match "quux", then verify preceding text manually with startsWith on the input

Defensive patterns

Strategy: try-catch

Validate before calling

if (pattern.contains("(?<=") && pattern.matches(".*\\(\\?<[:=].*(?<=.*\\).*")) { // nested look-around present
    throw new IllegalArgumentException("nested look-behind not supported by the linear engine");
}

Type guard

null

Try / catch

try { linearEngine.compile(pattern); } catch (UnsupportedRegexException e) { backtrackingEngine.compile(pattern); } // nested look-behinds work on the backtracking executor

Prevention

Avoid nesting look-arounds; keep look-behinds single-branch and flat.
Prefer character classes inside look-behinds over alternations.
When porting PCRE patterns, re-check every look-behind for branching or nesting.

When it happens

Trigger: Compiling (in linear/DFA-capable mode) a regex containing a look-behind whose first step branches into multiple successors, e.g. (?<=(?:a|b|c)x), or a look-behind nested inside another look-around such as (?<=(?<=a)b).

Common situations: Porting PCRE/Perl-heavy patterns to GraalVM regex (e.g. Espresso/Java or another guest language) that rely on nested look-behinds; variable-width look-behinds written as alternations; look-behind inside look-ahead patterns from log-parsing or syntax-highlighting grammars.

Related errors

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