Incorrect fix for (?0) with endanchored

[addisoncrump]

Discovered by #322.

Found another case where (?0) is improperly handled:

  re> /(?0)*./endanchored,ungreedy
data> abcd
 0: abcd
data> abcd\=no_jit
Failed: error -52: nested recursion at the same subject position

I think this is related, if not a corner case of, #331.

[carenas]

I know this is coming from a fuzzer, but any random combination of symbols are not a valid regular expression, and IMHO "undefined behaviour" is a valid response, as PCRE2 is not a "validating" compiler.

What does the expression even mean?, and while you might be right that this might be a case where endanchored is not properly handled (at least by one of the matching engines), I am not sure if the added complexity actually help with real use cases.

[zherczeg]

There is no undefined behaviour here. This pattern is simply an infinite loop, which can be detected at compile time. Of course the compiler cannot detect all cases, but it detects many. This is useful for the user since the pattern is probably wrong.

[addisoncrump]

any random combination of symbols are not a valid regular expression

Understood, which is why I am filtering and manually reducing these testcases to representative, smallest reproducing testcases. As for why inconsistent behaviour is undesirable: this fuzzing strategy allows us to automatically and systematically discover incorrectness in either representation based on the other. While many of these bugs appear to be wild atypical usages on their own, resolving these issues allows for the automatic discovery of truly problematic cases, even if they do not appear in the test suite (see: #336).

IMO, if the behaviour is undefined, it should not be allowed. There is no reason to offer it to end users if there is no intent to keep it consistent. If it was truly the case that endanchored should not be used with recursive patterns, then it should produce a compile error.

[PhilipHazel]

I agree with @zherczeg that this is an infinite loop. The interpreter diagnoses this, but JIT does not. Is this a bug in JIT?

[addisoncrump]

Here's a non-infinite-loop version with the same behaviour:

  re> /|(?0)./auto_callout,endanchored
data> abcd
--->abcd
 +0 ^        |
 +1 ^        (?0)
 +0 ^        |
 +5 ^        .
 +6 ^^       End of pattern
 +1 ^        (?0)
 +0 ^        |
 +5 ^        .
 +6 ^^       End of pattern
 +5 ^^       .
 +6 ^ ^      End of pattern
 +1 ^        (?0)
 +0 ^        |
 +5 ^        .
 +6 ^^       End of pattern
 +5 ^^       .
 +6 ^ ^      End of pattern
 +5 ^ ^      .
 +6 ^  ^     End of pattern
 +1 ^        (?0)
 +0 ^        |
 +5 ^        .
 +6 ^^       End of pattern
 +5 ^^       .
 +6 ^ ^      End of pattern
 +5 ^ ^      .
 +6 ^  ^     End of pattern
 +5 ^  ^     .
 +6 ^   ^    End of pattern
 0: abcd
data> abcd\=no_jit
--->abcd
 +0 ^        |
 +1 ^        (?0)
 +0 ^        |
 +1 ^        (?0)
Failed: error -52: nested recursion at the same subject position

[addisoncrump]

It does seem that the JIT does exhibit some infinite loop behaviour on /|(?0)/endanchored, though. It does terminate ("JIT stack limit reached").

[zherczeg]

This is something I will definitely not change. It will fail with stack exhaustion.

[addisoncrump]

I note that the behaviour of the interpreter and the JIT also differs here; see especially:

data> abcd
--->abcd
 +0 ^        |
 +1 ^        (?0)
 +0 ^        |
 +5 ^        .

vs

data> abcd\=no_jit
--->abcd
 +0 ^        |
 +1 ^        (?0)
 +0 ^        |
 +1 ^        (?0)

Is this difference expected/permissible? It seems that any left-recursing pattern will pass in JIT, but fail in the interpreter. Does the JIT strip out (?0) when recursing inwards, then only if the match fails, recurses inward again?

[carenas]

I think it goes back to what I was saying originally (albeit not in a clear enough way) and that I though we needed to clarify to align better with expectations.

PCRE2 detects MOST misuses and returns an error that could be helpful to a user to identify the problem they had with their expressions, but it doesn't validate that the given expression is proper, so then it might end up showing different behaviour between the interpreter and JIT and that might not be a bug (specially when the only difference is the error code returned).

FWIW, that previous comment might not apply to this specific case, where we might have a bug, and Perl returns an error from a "translated" expression, which ironically also shows an error if applied to PCRE2.

% perl -Mre -e 'print "match\n" if shift =~ /(?0)*?.$/' abcd
Infinite recursion in regex at -e line 1.
% pcre2test -jit 
PCRE2 version 10.42 2022-12-11
  re> /(?0)*?.$/
data> abcd
Failed: error -46: JIT stack limit reached
data> abcd\=no_jit
Failed: error -52: nested recursion at the same subject position
data>
 re> /(?0)*.$/ungreedy
data> abcd
Failed: error -46: JIT stack limit reached
data> abcd\=no_jit
Failed: error -52: nested recursion at the same subject position

but generates different code when endanchored is involved, although also "consistent"

  re> /(?0)*?./BI,endanchored
------------------------------------------------------------------
        Bra
        Braminzero
        SBra
        Recurse
        KetRmin
        Any
        Ket
        End
------------------------------------------------------------------
Capture group count = 0
Options: endanchored
Subject length lower bound = 1
data> abcd
 0: abcd
data> abcd\=no_jit
 0: abcd
data> 
  re> /(?0)*?.$/BI
------------------------------------------------------------------
        Bra
        Braminzero
        SBra
        Recurse
        KetRmin
        Any
        $
        Ket
        End
------------------------------------------------------------------
Capture group count = 0
Subject length lower bound = 1
data> abcd
Failed: error -46: JIT stack limit reached
data> abcd\=no_jit
Failed: error -52: nested recursion at the same subject position

[zherczeg]

If the example is correct, the internal recursion is not called for some reason. Probably another typo somewhere. However, I will never add nested recursion check for the jit, it will simply fail with stack exhaustion.

[addisoncrump]

@carenas: See #331; this behaviour is expected to be different, because (?0) doesn't behave the same way (and shouldn't) when putting a $ at the end vs using endanchored, because (?0) includes $ in the recursed pattern, whereas endanchored is not part of the pattern. In this case, $ is strictly infinitely recursive/not matching.

Curiously, I do not see /(?0)*?./BI,endanchored successfully executing without JIT on the git version, but it does on 10.42? The behaviour must have changed between 10.42 and now.

[addisoncrump]

Aha, I just git bisected the revisions: this behaviour difference was introduced in ce5b604!

$ git checkout ce5b604ebf7bf8fdd46b3026e19e1ea4792ca3a7
Note: switching to 'ce5b604ebf7bf8fdd46b3026e19e1ea4792ca3a7'.
$ make && (echo "/(?0)*?./BI,endanchored"; echo "abcd") | ./pcre2test | grep Failed
make  all-am
...
Failed: error -52: nested recursion at the same subject position
$ git checkout f5c4eb77f3ee473c85ce46f498a2485e1c73b180
Previous HEAD position was ce5b604 Fix PCRE2_ENDANCHORED behaviour in recursion in pcre2_match(). Fixes #331.
HEAD is now at f5c4eb7 jit: disable ASAN for arm64 SIMD helper (#306)
$ make && (echo "/(?0)*?./BI,endanchored"; echo "abcd") | ./pcre2test | grep Failed
make  all-am
...

[addisoncrump]

In the meantime, here's another example of a recursive pattern where the current behaviour is correct and reflects what I think is intended with endanchored:

  re> /((?1)*?a)$/   
data> aaaa
 0: aaaa
 1: aaaa
data> aaaa\=no_jit
 0: aaaa
 1: aaaa

Perl agrees:

$ perl -Mre -e 'print "match\n" if shift =~ /((?1)*?.)$/' abcd
match

I think the behaviour with endanchored is just slightly off is all. It is otherwise consistent.