Top-level recursion ignores top-level alternatives
- Dominant language
- C++
- Stars
- 119
- Forks
- 113
- PR merge metrics
- No merged PRs in 30d
Description
A top-level recursive call, i.e. `(?R)` or `(?0)`, only uses the first alternative, and ignores all subsequent ones.
As a simple example, `a(?R)|z` will only match `z`, but it is supposed to be able to also match `az`. The workaround is to use `(?:a(?R)|z)` or `(a(?R)|z)` or `(a(?1)|z)`, which can match either `az` or `z`.
The regex which actually led to discovery of this bug was [(?=(xx+?)\1*(?=\1$)((?R)))(?=(x+)\3*(?=\3$)((?R)))\2\4|x\B(?R)|](https://codegolf.stackexchange.com/questions/79644/how-many-steps-does-it-take-from-n-to-1-by-subtracting-the-greatest-divisor/249872#249872), which calculates the [OEIS A064097](https://oeis.org/A064097) number sequence in unary. But to make it work in the current version of Boost, the entire regex must be enclosed in parentheses.
I have tested and confirmed this to be happening in the latest version of Notepad++, [v8.4.4 (released yesterday)](https://notepad-plus-plus.org/downloads/v8.4.4/), which uses presumably the latest (or at least a very recent) version of Boost as its regex engine.
Sample program demonstrating the bug:
```
#include
#include
int main()
{
boost::smatch what;
if (boost::regex_search(std::string("az"), what, boost::regex( "a(?R)|z" ))) std::cout << what[0] << '\n';
if (boost::regex_search(std::string("az"), what, boost::regex("(?:a(?R)|z)"))) std::cout << what[0] << '\n';
if (boost::regex_search(std::string("az"), what, boost::regex( "(a(?1)|z)"))) std::cout << what[0] << '\n';
return 0;
}
```
This should print three identical lines of `az`, but instead prints `z` followed by two lines of `az`.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by compiling and running the sample program using boost/regex.hpp, boost::regex, and boost::regex_search, then trace how top-level (?R) and (?0) calls are parsed and executed. Compare the three expressions in the example; done means all produce the expected az match without changing the grouped-recursion behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- tooling
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100