Issue #20225 has been updated by make_now_just (Hiroya Fujinami). On dev meeting, matz concluded that, but I also think a null-loop bug must be fixed. However, there are still remaining issues: - I'm not sure "what the correct behavior of capture-aware null-loop detection". (I also am not sure TruffleRegex's behavior is correct.) - Additionally, I'm not sure it is possible to implement such correct behavior to Onigmo in an efficient way. - I also wonder if it can work with memoization. This issue is complex. ---------------------------------------- Bug #20225: Inconsistent behavior of regex matching for a regex has a null loop https://bugs.ruby-lang.org/issues/20225#change-107280 * 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/r...). 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/