RegexOptions.NonBacktracking isn't always matching semantics of backtracking engines

[stephentoub]

We recently tried to instill the NonBacktracking engine with the ability to match the semantics of the backtracking engine, in terms of returning the same matches it would under the same circumstances. We've missed some circumstances, though. Here's an example from @olsaarik:

var r = new Regex(".{4}x|ab");
var r2 = new Regex(".{4}x|ab", RegexOptions.NonBacktracking);
Assert.Equal(r.Match("aabax").Value, r2.Match("aabax").Value); // fails

"the problem here is that the first phase stops when it matches on ab, then the reverse second phase extends the match backwards from there, but since there's no x it can't go all the way back to the beginning and then the third phase will start from the wrong point"

Tagging subscribers to this area: @dotnet/area-system-text-regularexpressions
See info in area-owners.md if you want to be subscribed.

Issue Details

---

We recently tried to install the NonBacktracking engine with the ability to match the semantics of the backtracking engine, in terms of returning the same matches it would under the same circumstances. We've missed some circumstances, though. Here's an example from @olsaarik:

var r = new Regex(".{4}x|ab");
var r2 = new Regex(".{4}x|ab", RegexOptions.NonBacktracking);
Assert.Equal(r.Match("aabax").Value, r2.Match("aabax").Value); // fails

"the problem here is that the first phase stops when it matches on ab, then the reverse second phase extends the match backwards from there, but since there's no x it can't go all the way back to the beginning and then the third phase will start from the wrong point"

Author:	stephentoub
Assignees:	-
Labels:	area-System.Text.RegularExpressions
Milestone:	7.0.0

[stephentoub]

@olsaarik, this is fixed by #68199 and can be closed, yes?