boostorg / boostorg/regex

Subroutine call backtracking bug

Open
#178 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
119
Forks
113
PR merge metrics
No merged PRs in 30d

Description

A pared-down example is matching `(12)3` with the regex `((\d|\((?1)\)){2})`. It matches `(12)`, but should match `(12)3`.

PCRE deals with it correctly: https://regex101.com/r/tVAmEt/1
Perl, Ruby/Onigmo, and the Python library mrab-regex also deal with it properly.

The regex that led to the discovery of this bug was the looped substitution [`s~([*-/]( *(\d++|\((?1)\))){2})(?!\))~($1)~`](https://codegolf.stackexchange.com/questions/250861/add-parentheses-to-polish-notation/250875#250875), which adds parentheses to Polish notation.

I have tested and confirmed this to be happening in the latest version of Notepad++, [v8.4.4](https://notepad-plus-plus.org/downloads/v8.4.4/), which uses Boost as its regex engine.

Sample program demonstrating the bug:

```
#include
#include
int main()
{
boost::smatch what;
if (boost::regex_search(std::string("(12)3"), what, boost::regex( "((\\d|\\((?1)\\)){2})" ))) std::cout << what[0] << '\n';
if (boost::regex_search(std::string("(12)3"), what, boost::regex( "((?>\\d|\\((?1)\\)){2})" ))) std::cout << what[0] << '\n';
if (boost::regex_search(std::string("(12)3"), what, boost::regex("((\\d|\\(((\\d|\\((?1)\\)){2})\\)){2})"))) std::cout << what[0] << '\n';
return 0;
}
```

This should print three identical lines of `(12)3`, but instead prints `(12)` followed by two lines of `(12)3`. The third case demonstrates the regex "extruded" to an extra level of depth, by substituting itself in place of `(?1)`.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.