[ruby-core:116570] [Ruby master Bug#20225] Inconsistent behavior of regex matching for a regex has a null loop

["jirkamarsik (Jirka Marsik) via ruby-core" <ruby-core@ml.ruby-lang.org>]

Issue #20225 has been updated by jirkamarsik (Jirka Marsik).


As I understand it, the idea behind the null check is for the regex matcher to be able to identify unproductive branches in the regex execution, branches which are guaranteed to never terminate. When executing the expression `X*`, where `X` is some subexpression, the greedy `*` quantifier will always prefer to enter and execute `X` and will only stop when `X` can no longer be matched. The null check lets the regex matcher know that no part of the execution state has changed since the last iteration of the loop. At that point, the regex matcher knows that continuing the loop will never produce a match and so it can afford to terminate the loop. This is because the state of the matcher is now at a state (matcher position, matched capture groups...) such that no other alternative with higher priority could produce a different state. In other words, this is the highest-priority state which could still yield a match.

We can look at a simplified example from the spec:
```
/(a|\2b|())*/.match("ab").to_a.should == ["ab", "", ""]
```
and we can look at traces of 3 possible executions of this regular expression: 
```
A: ENTER * -> ALTERNATIVE 1 -> ENTER * -> ALTERNATIVE 3 -> ENTER * -> ALTERNATIVE 2 -> ENTER * -> ALTERNATIVE 3 -> ENTER * -> ALTERNATIVE 3 -> ENTER * -> ALTERNATIVE 3 -> ENTER * -> ...
B: ENTER * -> ALTERNATIVE 1 -> ENTER * -> ALTERNATIVE 3 -> ENTER * -> ALTERNATIVE 2 -> ENTER * -> ALTERNATIVE 3 -> ENTER * -> ALTERNATIVE 3 -> EXIT *
C: ENTER * -> ALTERNATIVE 1 -> ENTER * -> ALTERNATIVE 3 -> EXIT *
```
Trace `A` corresponds to the endless "naive" traversal with no null check, where we always choose the highest-priority option (alternatives are tried from left to right, greedy quantifiers always try to match). In trace `B`, we identify the endless loop of `ENTER * LOOP -> ALTERNATIVE 3 -> ...` and use the null check that's implemented currently in Ruby to terminate the loop after alternative 3 is takes 2 times in a row (the first time it updates capture group 2, the second time it doesn't update any state). Note that trace `B` has lower priority than trace `A` because at one point, it chooses `EXIT *` instead of `ENTER *`. However, trace `A` never finishes the match and even though there exists an infinity of traces that have higher priority than `B` (those that would decide to terminate the loop in some later iteration than `B`), because of the null check, we know that they are all observably equivalent to `B` and so the regex matcher can proceed with `B` as the highest-priority ma
 tch. In contrast, `C` represents the trace that would be produced by a regex implementation whose null check would ignore updates to the state of capture groups and would terminate the loop after the first iteration that matches the empty string. However, the result of `C` is not the highest priority match, because there exists `B`, which has higher priority, since it chose to execute the body of a greedy quantifier instead of skipping it. I would argue that since the semantics of regular expression search is to return the highest priority match, where priority is determined by the ordering of alternatives and the greediness of quantifiers, the correct answer is the result of executing `B`.

Now for the example from your issue, this is clearly a bug and not intended behavior of the null check. The null check should never cause an expression not to match, since it should only prune branches which are known to not terminate.

This expression should evaluate to `0`:
```
/(?:.B.(?<a>(?:[C-Z]|.)*)+){2}/ =~ "ABCABC"
```
and this expression should terminate:
```
/((?=(a)))*/ =~ "a"
```
The fact that neither of these is true means that there is a bug (or two bugs) in Ruby's implementation of regular expressions, quite possibly in the null check. However, it shouldn't be the reason to strengthen the null check so that it starts killing branches that could produce a valid match.

From my experience working on regular expression implementations, Ruby's null check behavior is not uncommon. Python regular expression's null checks take into account capture groups too, as do the null checks in Oracle Database regular expressions.

----------------------------------------
Bug #20225: Inconsistent behavior of regex matching for a regex has a null loop
https://bugs.ruby-lang.org/issues/20225#change-106586

* Author: make_now_just (Hiroya Fujinami)
* Status: Open
* Priority: Normal
* Assignee: make_now_just (Hiroya Fujinami)
* Backport: 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN, 3.3: UNKNOWN
----------------------------------------
Usually, in Ruby (Onigmo), when a null loop (a loop consuming no characters) occurs on regex matching, this loop is terminated. But, if a loop has a capture and some complex condition is satisfied, this causes backtracking. This behavior invokes unexpected results, for example,

```ruby
p /(?:.B.(?<a>(?:[C-Z]|.)*)+){2}/ =~ "ABCABC" # => nil
p /(?:.B.(?:(?:[C-Z]|.)*)+){2}/ =~ "ABCABC"   # => 0
```

Because the above regex has a capture and the below does not, different matching results are returned. It is not very intuitive that the presence of a capture changes the matching result.

The detailed condition for changing the null-loop behavior is 1) a previous capture in this loop holds the empty string, and 2) this capture's position is different from the current matching position. This condition is checked in `STACK_NULL_CHECK_MEMST` (https://github.com/ruby/ruby/blob/bbb7ab906ec64b963bd4b5d37e47b14796d64371/regexec.c#L1766-L1778).

Perhaps, you cannot understand what this condition means. Don't worry, I also cannot understand. This condition has been introduced for at least 20 years, and no one may remember the reason for this necessity. (If you know, please tell me!) Even if there is a reason, I believe that there is no reasonable authority for allowing counter-intuitive behavior, such as the above example.

This behavior can also cause memoization to be buggy. Memoization relies on the fact that backtracking only depends on positions and states (byte-code offsets of a regex). However, this condition additionally refers to captures, and the memoization is broken.

My proposal is to **correct this inconsistent behavior**. Specifically, a null loop should be determined solely on the basis of whether the matching position has changed, without referring to captures.

This fix changes the behavior of regex matching, but I believe that the probability that this will actually cause backward compatibility problems is remarkably low. This is because I have never seen any mention of this puzzling behavior before.



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- ruby-core@ml.ruby-lang.org
 To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org
 ruby-core info -- https://ml.ruby-lang.org/mailman3/postorius/lists/ruby-core.ml.ruby-lang.org/