boostorg / boostorg/regex

Top-level recursion ignores top-level alternatives

Open
#177 1 comment 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.