# Adding recursion to regex
**URL:** https://es.discourse.group/t/adding-recursion-to-regex/2091
**Category:** 💡 Ideas
**Tags:** proposal
**Created:** [July 21, 2024, 8:39am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091 "2024-07-21T08:39:09Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [July 21, 2024, 8:39am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/1 "2024-07-21T08:39:09Z")
It is probably the most important what JavaScript regex doesn't have.
The most famous task - to find closing parenthesis. No way to do this with regex now.
Also, it opens up a new horizon of possibilities and is easy to implement in regex engines.
(?R) - the whole regex pattern.
(?1) - the first group pattern (not result).
(?R) should always be used with "?" or "\*" to avoid infinite loop and find something.
Many regex engines support this (if not all except JavaScript).
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [July 25, 2024, 9:43am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/2 "2024-07-25T09:43:13Z")
Please.
---
### Author:  [@WebReflection](https://es.discourse.group/u/WebReflection)
#### Post date: [July 28, 2024, 2:30pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/3 "2024-07-28T14:30:04Z")
imagine tons of projects actually ditched JS RegExp in favor of [RE2](https://github.com/google/re2#readme) due possible deadlocks some RegExp can cause already ... you are kinda asking to make RegExp more dangerous than they are already when it comes to too complex logic, with performance penalties and a new "infinite recursion" potential issue there ... I am not sure this is wise, I'd rather ask browsers to expose RE2 instead as native builtin alternative.
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [July 29, 2024, 1:15pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/4 "2024-07-29T13:15:13Z")
Infinite recursions may be blocked. `(?R)` should always be with `?` or `*`.
It is quite easy to implement since it only should replace with some regex pattern.
People should test how long it is going. It is their fault if it has incredible sizes and a lot of backtracks. So test it before using and it will be ok.
Maybe without adding group patterns, only `(?R)`...
---
### Author:  [@WebReflection](https://es.discourse.group/u/WebReflection)
#### Post date: [July 29, 2024, 2:10pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/5 "2024-07-29T14:10:28Z")
> [@oleedd](#):
>
> It is their fault if it has incredible sizes and a lot of backtracks
often it's the unknown input that might cause backtracks, not necessarily the RegExp for "_desired_" or tested use cases ... _RE2_ exists for this reason too.
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [July 29, 2024, 2:18pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/6 "2024-07-29T14:18:27Z")
As I know, catastrophic backtracking is caused mostly or only by `(.+)+` etc. It should be avoided.
If not only, I think catastrophic backtracking reasons are quite researched. They should be avoided.
Also, possessive quantifiers may be added to fix this.
---
### Author:  [@WebReflection](https://es.discourse.group/u/WebReflection)
#### Post date: [July 29, 2024, 2:58pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/7 "2024-07-29T14:58:22Z")
I have no voice in TC39 so I am just sharing what I've worked with in the past (RE2 for ad blocks filters and investigated all the reasons for that) and today I'd rather have RE2 exposed as API than have more harakiri prone features to the current RegExp. This is also just my opinion, I hope somebody else from TC39 will actually answer you at some point.
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [July 30, 2024, 1:45pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/8 "2024-07-30T13:45:46Z")
I see that many engines give an error "Catastrophic backtracking" (Catastrophic backtracking has been detected and the execution of your expression has been halted.). Why not add this to JavaScript? Then people will see that there is catastrophic backtracking, not think that JavaScript is too slow.
And recursion could be added without concerns.
Goland and Rust got it done without delays.
---
### Author:  [@claudiameadows](https://es.discourse.group/u/claudiameadows)
#### Post date: [July 31, 2024, 3:15am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/9 "2024-07-31T03:15:33Z")
@oleedd Citation needed for recursive regexps in Rust. Their `regex` crate uses an algorithm very similar to RE2, just better optimized. In particular, it's also immune to catastrophic backtracking, and like RE2, it does not and cannot support recursion.
Rust does of course have full C interop, so you can easily just link against one providing recursive regexp support, but the broad community default would require a complete ground up rewrite to support it.
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [July 31, 2024, 7:43am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/10 "2024-07-31T07:43:21Z")
I meant Rust got done without delays a task with catastrophic backtracking (about 1 ms).
> [@claudiameadows](#):
>
> it does not and cannot support recursion
Why can't if it is so fast? It just has to replace `(?R)` and others.
If to specify the need for immunity in the standard, Google will find opportunities to make it in V8 and others will do after.
---
### Author:  [@claudiameadows](https://es.discourse.group/u/claudiameadows)
#### Post date: [July 31, 2024, 3:26pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/11 "2024-07-31T15:26:35Z")
It's not about the speed, but how the regexps are represented. [RE2](https://swtch.com/~rsc/regexp/regexp3.html) and Rust's regex crate both lower them into finite state machines: [Finite-state machine - Wikipedia](https://en.wikipedia.org/wiki/Finite-state_machine)
There's no stack or anything in this construction, thus no way to recognize general recursion. [Thompson's algorithm](https://swtch.com/~rsc/regexp/regexp2.html) can be modified to support stacks for a limited amount of recursion, but that mostly precludes SIMD optimization (which the regex crate uses extensively).
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [July 31, 2024, 5:50pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/12 "2024-07-31T17:50:24Z")
Why should they handle with returns (stack)? Why not replace `(?R)` with the whole pattern extending the expression?
For example: /t(?R)\*y/ =\> /tt(?R)yy/ and so on.
---
### Author:  [@lightmare](https://es.discourse.group/u/lightmare)
#### Post date: [July 31, 2024, 10:07pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/13 "2024-07-31T22:07:39Z")
> [@oleedd](#):
>
> Why not replace `(?R)` with the whole pattern extending the expression?
> For example: /t(?R)\*y/ =\> /tt(?R)yy/ and so on.
You mean ad infinitum? Or what is the example about?
`/t(?R)*y/` matches "ttytyy", `/tt(?R)yy/` doesn't, I don't see how the patterns are related.
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [August 1, 2024, 7:25am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/14 "2024-08-01T07:25:20Z")
It just displayed the idea, if to be precise, it should be:
/t(?R)\*y/ =\> /t(?:t(?R)\*y)\*y/ and so on.
Finite-state machines seem to be ok for this.
---
### Author:  [@lightmare](https://es.discourse.group/u/lightmare)
#### Post date: [August 1, 2024, 8:40pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/15 "2024-08-01T20:40:39Z")
> [@oleedd](#):
>
> Finite-state machines seem to be ok for this.
No, a finite state machine cannot recognize `/t(?R)*y/`.
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [August 2, 2024, 8:51am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/16 "2024-08-02T08:51:02Z")
I mean it could replace... With additional code. It is not a recursion already. It is extending regex.
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [August 2, 2024, 9:05am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/17 "2024-08-02T09:05:09Z")
There are pushdown automata. With stack.
> **[Pushdown automaton](https://en.wikipedia.org/wiki/Pushdown_automaton)**
>
> In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is
> a type of automaton that employs a stack.
> Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines (see below).
> Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former o...
---
### Author:  [@claudiameadows](https://es.discourse.group/u/claudiameadows)
#### Post date: [August 2, 2024, 3:15pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/18 "2024-08-02T15:15:27Z")
Yeah, but the mere presence of added state interferes with many SIMD-based optimizations.
---
### Author:  [@oleedd](https://es.discourse.group/u/oleedd)
#### Post date: [August 2, 2024, 4:56pm UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/19 "2024-08-02T16:56:45Z")
What about adding to JavaScript?
---
### Author:  [@claudiameadows](https://es.discourse.group/u/claudiameadows)
#### Post date: [August 3, 2024, 3:31am UTC](https://es.discourse.group/t/adding-recursion-to-regex/2091/20 "2024-08-03T03:31:55Z")
V8's Irregexp falls back to a similar algorithm of their own after a certain number of backtracks within a given match (100 IIRC).
Also worth noting this would slow down a lot. Thompson's NFA algorithm would require each "thread" have its own stack, and this could result in significant overhead for regexps with it. You could avoid it by using one loop for regexps with an `(?R)` and one loop for those without, but then you're rolling two regexp implementations And _that_ is inefficient and a regexp vulnerability surface unto itself.
* * *
In addition to all this implementation complexity, how do you feel nested results be returned from `exec`? The current API offers no clear answer here.
[Next page](https://es.discourse.group/t/adding-recursion-to-regex/2091.md?page=2)