CURLYX v CURLYM disagreement

[hvds]

As part of an unrelated experiment I tried disabling the CURLYX -> CURLYM regexp optimization with the following patch:

diff --git a/regcomp.c b/regcomp.c
index 169272e1dd..2dac74fecd 100644
--- a/regcomp.c
+++ b/regcomp.c
@@ -5807,7 +5807,7 @@ S_study_chunk(pTHX_
               nogo:
 
                 /* Try optimization CURLYX => CURLYM. */
-                if (  OP(oscan) == CURLYX && data
+                if (0 && OP(oscan) == CURLYX && data
                       && !(data->flags & SF_HAS_PAR)
                       && !(data->flags & SF_HAS_EVAL)
                       && !deltanext    /* atom is fixed width */

I expected this to disable a pure optimization, but was surprised to find that with this change we get some test failures.

The first failure is t/re/pat.t test 104 "monster, length = 300000 at re/pat.t line 373" with the pattern /(?^:b(?:a|b)+=)/; I think this one is understandable if CURLYM can match more repeats than CURLYX can (though I hope we can lift the restriction some day).

The remainder are three tests (two newly added for the *ACCEPT work) failing in each of t/re/regexp.t and its variants. I think these show that CURLYX and CURLYM disagree on how captures inside a quantifier should be filled (which I think we also recently discussed). I infer that one or other case has a bug:

not ok 966 () ^(aa(bb)?)+$:aabbaa:y:-$1-$2-:-aa-- => '-aa-bb-', match=1
# $subject = "aabbaa";
# 
#                 
#                 $match = ($subject =~ m'^(aa(bb)?)+$') while $c--;
#                 $got = "-$1-$2-";
# 
# $got = "-aa-bb-";
# 
# $expected = "-aa--";

not ok 2080 - ACCEPT with CurlyM optimization GH #19484 () /(A(A|B(*ACCEPT)|C)+D)(E)/:ABDE:y:$1-$2:AB-B => '-B', match=1
# $subject = "ABDE";
# 
#                 
#                 $match = ($subject =~ m/(A(A|B(*ACCEPT)|C)+D)(E)/) while $c--;
#                 $got = "$1-$2";
# 
# $got = "-B";
# 
# $expected = "AB-B";

not ok 2082 - ACCEPT with CurlyM optimization GH #19484 () /(A(A|B(*ACCEPT)|C)+D)(E)/:ABCDE:y:$1-$2:AB-B => '-B', match=1
# $subject = "ABCDE";
# 
#                 
#                 $match = ($subject =~ m/(A(A|B(*ACCEPT)|C)+D)(E)/) while $c--;
#                 $got = "$1-$2";
# 
# $got = "-B";
# 
# $expected = "AB-B";

[demerphq]

Hi, I can confirm these bugs are still present in blead:

$ ./perl -ilib t/re/regexp.t 2>&1 | grep -P '^#|^not ok'
not ok 966 () ^(aa(bb)?)+$:aabbaa:y:-$1-$2-:-aa-- => '-aa-bb-', match=1
# $subject = "aabbaa";
# 
#                 
#                 $match = ($subject =~ m'^(aa(bb)?)+$') while $c--;
#                 $got = "-$1-$2-";
# 
# $got = "-aa-bb-";
# 
# $expected = "-aa--";
not ok 2080 - ACCEPT with CurlyM optimization GH #19484 () /(A(A|B(*ACCEPT)|C)+D)(E)/:ABDE:y:$1-$2:AB-B => '-B', match=1
# $subject = "ABDE";
# 
#                 
#                 $match = ($subject =~ m/(A(A|B(*ACCEPT)|C)+D)(E)/) while $c--;
#                 $got = "$1-$2";
# 
# $got = "-B";
# 
# $expected = "AB-B";
not ok 2082 - ACCEPT with CurlyM optimization GH #19484 () /(A(A|B(*ACCEPT)|C)+D)(E)/:ABCDE:y:$1-$2:AB-B => '-B', match=1
# $subject = "ABCDE";
# 
#                 
#                 $match = ($subject =~ m/(A(A|B(*ACCEPT)|C)+D)(E)/) while $c--;
#                 $got = "$1-$2";
# 
# $got = "-B";
# 
# $expected = "AB-B";
# 1 iterations

The fact that the two ACCEPT tests fail is interesting to me. They were added when I fixed #19484, which suggests to me that CURLYX has a similar issue to CURLYM in terms of early accept.

The other test however suggests something deeper is wrong. Basically CURLYM and CURLYX are not doing the same thing as far as resetting capture buffers.

We dont have clear rules for what is right or wrong here afaik, so the discrepancy is somewhat understandable. Eg, the failing test result is arguably not wrong, but the same thing applies for the expected result. The fact that they differ however is just wrong, whatever they do do, they should do the same thing.

Thank you @hvds, this was a very helpful experiment, and one i will try to figure out how to build on and standardize in our test suite. You have mentioned being able to disable individual optimizations previously, which seemed at first of only abstract interest, but now I see your point much more clearly.

I likely will start with ACCEPT on this ticket as I think i understand that one properly, and hope that maybe @iabyn speaks up about the state machine for the other case. I have a few tickets where he has spoken of a "better way to do this" and maybe we just need to implement it or something like it.

[demerphq]

I have looked into this more, and I think I have a fix for the ACCEPT stuff although its clear we aren't testing things properly.

The discrepancy in matching between CURLYX and CURLYM can be seen here without disabling the optimization in the code. Changing (bb)? into (?:(bb)|) is enough to disable the CURLYM optimization (in fact it only creates one CURLYX loop, which allows us to understand what is going on better):

"aabbaa"=~/(aa(?:(bb)|))+/ and print "-$1-$2-"; #-aa-bb-
"aabbaa"=~/(aa(bb)?)+/ and print "-$1-$2-";     #-aa--

I tend to think this equivalence is helpful in deciding what the right here. the output should be "-aa--", because otherwise we end up nonsensical mixes of data from different iterations of the + operator.

What seems to happen is that CURLYX saves the paren state before it starts matching, and if it fails it restores them. So when we enter the CURLYX we save $2, which previously was "bb". it fails, and we restore it back to "bb".

What I /think/ should happen is that curlyx should save the buffer state when it starts, clear the buffer state that might be changed by it, and then try to match, if the iteration is successful, it should update the saved state, and clear it, and then match again. That way when the inner CURLYX is first executed it is in an "unmatched" state.

In previous commits I did a lot of work to harden the regex engine internals to changes in size of the regops. I have created some new regnode types that give me room to store the min/max as I32, and to add another I32 or two I16's to represent the paren range each CURLY needs. Currently we track paren floor, and seemingly only up to 255 (we use a U8 to store it), but no paren-ceiling. So I am thinking that if I store the parenfloor and parenceiling of the curly then we can make this work consistently.

This does mean a series of nested of capture buffers would be copying and clearing the same buffers over and over, but im not sure that can be helped. Maybe @iabyn has a clever idea here.

I keep thinking of a comment @iabyn made elsewhere about how we could teach a bunch of the capture buffer restoration logic how to use the backtracking engine to manage all of this cleanly, but I need to find it and put it into context with this. @iabyn please speak up if you have ideas. Also please be aware we effectively now have the ability to cleanly resize ops without carnage breaking out. If we need new properties or whatever that is doable. the only problem is that data must be 32 bit aligned and sized. You mentioned in a previous post how useful it would be to have BRANCH nodes know how many parens are to the left of them, and things like that, which is totally doable now. (It was the test case for introducing the REGNODE_AFTER stuff).

[demerphq]

I have created #20661 to centralize and collect all the various bug reports that boil down to the same problem.

[demerphq]

#20677 should fix this.