microsoft / microsoft/STL

`<regex>`: (a)(\3)(c) should be accepted

Open
#6,091 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug regex
Dominant language
C++
Stars
11.2k
Forks
1.7k
Avg merge
4d 15h
Merged PRs (30d)
22

Description

Describe the bug

sorry, @muellerj2, I missed a spot when I wrote that regex test suite a while ago

https://262.ecma-international.org/5.1/#sec-15.10.2.11 "It is an error if n is greater than the total number of left capturing parentheses in the entire regular expression."

Therefore, (a)(\3)(c) is valid. (The \3 will only match the empty string, because its ) hasn't been reached yet.) (a)(\4)(c), however, is not.

Yes, that rule is absurd (much better to accept only up to the number of left parens seen - or even better, only accept backrefs that could be nonnull at this point, i.e. reject (a)|\1 and (?!(a))\1), but if the spec says so, then the spec says so.

Personally I'd implement it by compiling such impossible backrefs into absolutely nothing, just set a counter for highest backref seen. Then check that variable at compilation end, when the entire regex is analyzed.

Luckily, we don't need that JS compat hack where (a)(\4)(c) looks for a \x04 byte.

Command-line test case

Full test suite - https://godbolt.org/z/bffnYj7xT
Just this issue - https://godbolt.org/z/r6xqPKrWb

Expected behavior

See bug description

STL version

x64 msvc v19.50 VS18.2 (Godbolt)

Additional context

🦭

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the minimal case from the linked Godbolt test and compare (a)(\3)(c) with (a)(\4)(c). Read the ECMAScript 5.1 section 15.10.2.11 cited in the issue; done means the former is accepted while the latter remains rejected, with the full test suite still passing.

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
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.