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

Issue #20225 has been updated by Eregon (Benoit Daloze).


What is the decision, to return 0 in both cases (like TruffleRegex behaves), and fix the behavior in Onigmo?

As @jirkamarsik explained above, that is the correct and intended behavior for the null loop optimization, which like any optimization should be transparent and not change semantics.
Memoization can be fixed to deal with this, see https://bugs.ruby-lang.org/issues/20225#note-6, alternatively memoization could be not used for such regexps if it's too difficult.

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

* Author: make_now_just (Hiroya Fujinami)
* Status: Open
* 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 -- [e-mail]
 To unsubscribe send an email to [e-mail]
 ruby-core info -- https://ml.ruby-lang.org/mailman3/postorius/lists/ruby-core.ml.ruby-lang.org/