oracle/graal · error · UnsupportedRegexException

recursive subexpression calls are not supported

Error message

recursive subexpression calls are not supported

What it means

Thrown by RubySubexpressionCalls when inlining Ruby subexpression calls (\\g<name> / (?<name>) calls) would recurse. TRegex inlines called groups at compile time; it first runs a topological sort (Kahn's algorithm) over the call graph, and if the graph is not empty after processing — i.e. calls form a cycle such as a group calling itself — it throws UnsupportedRegexException because an infinitely-sized inlined AST cannot be built.

Source

Thrown at regex/src/com.oracle.truffle.regex/src/com/oracle/truffle/regex/flavor/ruby/RubySubexpressionCalls.java:96

                replace(subexpressionCall, ast.getGroup(subexpressionCall.getGroupNr()).get(0), copyVisitor);
            }
            if (callGraph.containsKey(node)) {
                for (CallGraphNode dependent : callGraph.get(node)) {
                    int dependentInDegree = inDegree.getOrDefault(dependent, 0);
                    if (dependentInDegree == 1) {
                        expansionStack.add(dependent);
                        inDegree.remove(dependent);
                    } else {
                        inDegree.put(dependent, dependentInDegree - 1);
                    }
                }
                callGraph.remove(node);
            }
        }

        assert callGraph.isEmpty() == inDegree.isEmpty();
        if (!callGraph.isEmpty()) {
            throw new UnsupportedRegexException("recursive subexpression calls are not supported");
        }
    }

    private static void replace(SubexpressionCall caller, Group callee, CopyVisitor copyVisitor) {
        Group copy = (Group) copyVisitor.copy(callee);
        MarkAsAliveVisitor.markAsAlive(copy);
        copy.setQuantifier(caller.getQuantifier());
        Sequence callerSeq = caller.getParent();
        int callerSeqIndex = caller.getSeqIndex();
        callerSeq.replace(callerSeqIndex, copy);
    }

    private abstract static class CallGraphNode {
    }

    private static final class SubexpressionCallNode extends CallGraphNode {

        private final SubexpressionCall subexpressionCall;

View on GitHub (pinned to a66e9ccd1d)

Solutions

Replace recursion with iterative matching in host code: match one nesting level per regex pass and drive the recursion in a loop
For balanced-delimiter matching, use a counter-based scan of the input instead of a regex
If only bounded nesting depth is needed, unroll the group a fixed number of times instead of calling it recursively

Example fix

# before (Ruby flavor)
/(?<paren>\\(\\g<paren>*\\))/x

# after: match one level, recurse in code
/(\((?:[^()]|\\((?<i>)|\\)(?<-i>))*(?\(i>\\))?\))/ # or simply loop with /\([^()]*\)/

Defensive patterns

Strategy: try-catch

Validate before calling

boolean usesRecursiveSubexpressionCall(String rubyPattern) {
    // crude check: named call \\g<name> where <name> is also a defined group in the same pattern
    return java.util.regex.Pattern.compile("\\\\g<[^>]+>").matcher(rubyPattern).find()
        && java.util.regex.Pattern.compile("\\(\\?<[^>]+>").matcher(rubyPattern).find();
}

Try / catch

begin
  re = TRegex.compile_ruby(pattern)
rescue UnsupportedRegexException => e
  raise if e.reason !~ /recursive/
  # fall back to an iterative, level-by-level matching loop
end

Prevention

Avoid \\g<name> self-calls in Ruby-flavor patterns for TRegex; express recursive structure in host code
For balanced-delimiter matching, use counting scans instead of recursive regexes

When it happens

Trigger: Compiling a Ruby-flavor regex where a group calls itself directly or through a chain: (?(?<a>a|\\g<a>)) or (?<x>a\\g<y>)(?<y>b\\g<x>). After topological sorting, callGraph is non-empty (nodes with permanent in-degree), and the exception is thrown.

Common situations: Porting recursive matching patterns for balanced constructs (nested parentheses, HTML-ish trees) from Oniguruma/PCRE, where recursion is the idiomatic tool; Ruby guest applications on GraalVM/TruffleRuby using recursive regexes.

Related errors

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