Subroutine support by keith-hall · Pull Request #230 · fancy-regex/fancy-regex

keith-hall · 2026-02-17T21:56:50Z

Add support for subroutine calls (including recursion) using Oniguruma syntax \g<1>

I have deliberately kept the VM changes minimal for this initial work, and chose to expand the subroutine calls inline in the compiler, up to the recursion depth limit of 20. I also haven't added any unit tests in the compiler to assert how the program looks with recursive calls, to reduce friction and give us more flexibility to change the implementation later when we work on relative recursion level backreferences. Simple subroutine call compilation is tested, and many matching tests have been added, including passing lots of Oniguruma test cases.

Also, huge effort was put into documentation, to explain how subroutines work.

as it fixes a bug with passing a Vec with more slots than is necessary for the number of capture groups

Add detection in analyzer to throw an error when a backreference is used inside a capture group being recursed and refers to the same capture group. This would currently exhibit undefined (or rather, plain wrong) behavior.

keith-hall · 2026-02-17T21:58:16Z

-  x2("\\g<1>|\\zEND(.a.)", "bac", 0, 3);
-
-  // Compile failed: CompileError(FeatureNotYetSupported("Subroutine Call")
+  // Expected group to exist


this failure occurs due to Oniguruma by default ignoring numbered capture groups (treating them as non-capture groups) when named groups are defined, and doesn't reflect subroutine call support being lacking in any way. I made a test specifically to prove this.

keith-hall · 2026-02-17T21:58:50Z

-  x2("(?<n>|\\g<m>\\g<n>)\\z|\\zEND (?<m>a|(b)\\g<m>)", "bbbbabba", 0, 8);
-
-  // Compile failed: CompileError(FeatureNotYetSupported("Subroutine Call"))
+  // Match found at start 0 and end 1 (expected 2 and 3)


same cause here for the failure

robinst

I've only had time to read the documentation so far, some feedback on that. But in general great to have good docs with lots of examples :).

robinst · 2026-03-07T07:14:59Z

@@ -0,0 +1,52 @@
+# Subroutines: reusable patterns with stable meaning
+
+Subroutines in fancy-regex are not "inline expansions" and not "dynamic calls".


What are "inline expansions" and "dynamic calls"? It would probably make sense to leave that for later, instead of starting with what they aren't.

Also, as an intro to someone who doesn't know subroutines, it's a lot to read without any context. I would start with an example straight away. And I'm not sure that (\d)\g<1>\1 is a good one, because it already brings the complexity of updating the capture. I think (?<word>[a-z]+) ... is better, but some people might think "I can just use [a-z]+ again instead of using a subroutine".

How about something like this: (?<num>\d+\.\d+|\d+) x \g<num>

It's fairly simple and shows how reuse works.

Nice, updated to your simple example and removed the first line. (I think it is covered by 2_flags.md)

robinst · 2026-03-07T07:15:52Z

+- executed exactly the way the capture group was originally defined
+- reusable from multiple places
+
+>> Calling a subroutine does not recompile it in the caller's context.


Double blockquote? Also, not sure what this sentence means, sorry :).

removed it as it doesn't contain any new information not covered in 2_flags.md

robinst · 2026-03-07T07:17:45Z

+```rust
+use fancy_regex::Regex;
+
+let re = Regex::new(r"(\d)\g<1>\1").expect("expected compilation to be successful");


To make this less verbose/distracting, can you turn the expect(...) into plain unwrap() or maybe even ? (not sure if/how possible in examples).

robinst · 2026-03-07T07:19:04Z

+
+Let's imagine a pattern which will match a digit and capture it into group 1. Then it will call that capture group as a subroutine. Then it will do a backref to group 1.
+
+This will match only when a digit is followed by another digit and then itself.


"itself" here is not clear. It refers to "another digit", right?

clarified the wording

robinst · 2026-03-07T07:38:58Z

+- Makes performance predictable
+- Shifts errors from runtime to compile time (note that this refers to when the regex is compiled to a VM, which is not done by the rust compiler, but when the regex is instanciated/parsed from a string)
+
+The result is a regex engine that is both expressive and safe - without relying on fragile heuristics or input-dependent behavior.


I think this last section here is not necessary, it was pretty clear from the previous sections already. (Is this AI btw?)

removed the last section. Yes, I used ChatGPT to get me started, as it was quite daunting initially to document it all

robinst · 2026-03-07T07:40:35Z

+`\g<name>`
+: call the subroutine defined in capture group named *name* \
+`\g<1>`
+: call the subroutine defined in capture group 1


Can you mention the recursion limit here? Some people might not read on to the subroutines section.

robinst · 2026-03-07T07:41:02Z

 - Add support for more `\p{...}` and `\P{...}` aliases, for Oniguruma compatibility (#207)
 - Add support for word boundaries and zero-length fancy patterns inside variable lookbehinds (at top level) (#216)
 - Add support for `\R` to mean general newline, matching all common line break characters, treating `\r\n` atomically (#220)
+- Add support for subroutine calls (including recursion) `\g<1>` (#230)


Let's also mention the recursion limit here.

- add ordinal numbers, to reflect the same order they are included from `lib.rs` - remove spaces from filenames

- don't start with what subroutines are not - start with a simple example - clarify instead of referring to a digit as `itself`

it just duplicates what was already mentioned

This follows the suggestion documented at https://doc.rust-lang.org/rustdoc/write-documentation/documentation-tests.html#using--in-doc-tests - using `#` to hide lines - explicitly mentioning the error type

robinst

LGTM, awesome work! Just some minor comments/questions.

robinst · 2026-03-29T04:31:11Z

+                    if let Some(calls) = self.subroutine_calls.get(&group) {
+                        if calls.iter().any(|call| call.target_group == group) {
+                            return Err(Error::CompileError(Box::new(
+                                CompileError::FeatureNotYetSupported(


Is this "not yet" supported or an error that will stay an error?

this one is apparently not needed for Giallo - none of the TextMate syntaxes seem to use this feature in the regex patterns, but Oniguruma seems to support it, so it is something I would like to eventually tackle, for proper (implicit recursion level aware?) backreference support, so we can support matching palindromes that way etc. Until I work on it, I don't entirely understand how it is supposed to work, but I think it makes sense for it to stay as a not yet supported feature error for now

robinst · 2026-03-29T04:33:18Z

+                        // If empty, this is an error in the analysis phase
+                        if target_info.children.is_empty() {
+                            return Err(Error::CompileError(Box::new(
+                                CompileError::FeatureNotYetSupported(format!(


Same here, this shouldn't be "not yet", right?

indeed, thanks, fixed

robinst · 2026-03-29T04:35:22Z

+                        }
+                        self.b.add(Insn::SaveCaptureGroupStart(target_group));
+                        self.visit(&target_info.children[0], hard)?;
+                        self.b.add(Insn::Save(target_group * 2 + 1));


Do we need/want a SaveCaptureGroupEnd?

not sure, for consistency it makes sense, but at the same time, right now (until we implement recursion level backrefs and see if we need it to behave differently) it would be essentially identical to the Save instruction, except the slot lookup would then be at runtime instead of compile time...

robinst · 2026-03-29T04:35:44Z

+                    // The target group doesn't exist (invalid group reference)
+                    // This should have been caught by analysis, but be defensive
+                    return Err(Error::CompileError(Box::new(
+                        CompileError::FeatureNotYetSupported(format!(


(Same comment here.)

thanks, fixed

robinst · 2026-03-29T04:42:32Z


-The main author is Raph Levien, with many contributions from Robin Stocker
-and Keith Hall.
+The main authors are Raph Levien, Robin Stocker and Keith Hall.


robinst · 2026-03-29T04:45:20Z

+                    .iter()
+                    .filter(|&&g| g == target_group)
+                    .count();
+                if recursion_count >= MAX_SUBROUTINE_RECURSION_DEPTH {


A bit confused by this doing >= 19 but the release notes saying "including recursion up to 20 levels deep". Shouldn't 20 still be ok? Or am I reading it wrong?

The first execution of the capture group technically isn't a recursion, but should count towards the recursion depth, so the count is off by one. As it stands, we match Oniguruma behavior, which also has a limit of 20, so I think the documentation is correct, even though it is admittedly a little confusing.

(I think Oniguruma counts like this because the initial visit of a capture group via the normal flow is compiled identically to subroutine call visits.)

The first execution of the capture group technically isn't a recursion, but should count towards the recursion depth, so the count is off by one.

Aah I see, that's what I was missing.

don't use FeatureNotYetSupported CompileError when it isn't a feature that will ever be supported

keith-hall added 5 commits February 17, 2026 23:54

initial work on subroutine support, with supporting documentation

18fcfb9

ensure regex-automata 0.4.14 is used

b47c11b

as it fixes a bug with passing a Vec with more slots than is necessary for the number of capture groups

Skip building group info map in compiler when no subroutines are present

7620147

Update changelog

c429f14

keith-hall requested a review from robinst February 17, 2026 21:56

keith-hall commented Feb 17, 2026

View reviewed changes

Add additional documentation note

1b8efb8

This was referenced Feb 17, 2026

How similar to Oniguruma do we aim to be? #162

Open

panic with regex-fancy feature on one line JS files sharkdp/bat#3156

Open

Recursive Expressions (?R) in Rust's fancy-regex #141

Closed

ludovitkramar mentioned this pull request Feb 24, 2026

Fix non-deterministic language detection with BTreeSet and fancy-regex drshade/linguist#1

Merged

Merge branch 'main' into subroutine_support

0a060d7

keith-hall mentioned this pull request Mar 4, 2026

Implement sublime-syntax Build 4075 features trishume/syntect#610

Merged

robinst reviewed Mar 7, 2026

View reviewed changes

keith-hall added 6 commits March 7, 2026 20:43

rename subroutine docs

18ae4cb

- add ordinal numbers, to reflect the same order they are included from `lib.rs` - remove spaces from filenames

improve intro documentation

a59f9e0

- don't start with what subroutines are not - start with a simple example - clarify instead of referring to a digit as `itself`

improve intro documentation

0ca777d

remove key takeaways section from left recursion documentation

b497923

it just duplicates what was already mentioned

mention recursion limit

50fd8f2

remove distracting expects from examples

126b17d

This follows the suggestion documented at https://doc.rust-lang.org/rustdoc/write-documentation/documentation-tests.html#using--in-doc-tests - using `#` to hide lines - explicitly mentioning the error type

keith-hall mentioned this pull request Mar 13, 2026

fancy-regex: problems with patterns in some syntaxes trishume/syntect#287

Open

robinst approved these changes Mar 29, 2026

View reviewed changes

improvements from PR review

4ff4226

don't use FeatureNotYetSupported CompileError when it isn't a feature that will ever be supported

keith-hall merged commit 5e322f0 into main Mar 29, 2026
10 of 12 checks passed

keith-hall deleted the subroutine_support branch March 29, 2026 19:07

		@@ -0,0 +1,52 @@
		# Subroutines: reusable patterns with stable meaning

		Subroutines in fancy-regex are not "inline expansions" and not "dynamic calls".


		Let's imagine a pattern which will match a digit and capture it into group 1. Then it will call that capture group as a subroutine. Then it will do a backref to group 1.

		This will match only when a digit is followed by another digit and then itself.

Uh oh!

Conversation

keith-hall commented Feb 17, 2026

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

robinst left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

robinst left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

keith-hall Mar 29, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

keith-hall Mar 29, 2026 •

edited

Loading