Incorrect backtracking over lookahead with captures which are later backreferenced

[liquidcake1]

This does not match:

PCRE2 version 10.42 2022-12-11
  re> /(?=.*(.))(?=.*\1.*\1).*(?!\1)(.).*\2/ 
data> 22331
No match

This matches:

  re> /(?=.*(.).*\1)(?=.*\1.*\1).*(?!\1)(.).*\2/ 
data> 22331
 0: 22
 1: 3
 2: 2

The only difference is an additional constraint which forces the initial lookahead not to pick 1.

Basically I think PCRE doesn't understand that the initial lookahead is a dependency of subsequent behaviour, and hence the matcher must exhaust its possible matches before declaring a failure. Interestingly, changing the matcher does seem to support backtracking to some extent, as for example the following works:

PCRE2 version 10.42 2022-12-11
  re> /(?=.*(.))(?=(.)).*\2(?!.*\1$)/
data> 23321
 0: 1
 1: 1
 2: 1

Weirdly, moving the \2 to the end, which shouldn't affect the match (again, this should in principle actually increase the options available to the matcher as it allows the .* in the negative lookahead to start with the \2 while in the matching variant, it couldn't) causes this to no longer match.

I assume I'm hitting some kind of backtracking safety mechanism, but if so it'd be preferable for the engine to just refuse to compile such monstrosities, or at least error at runtime when the constraint is hit. Better that than execute them incorrectly.

Also tested on latest master (10.43-DEV 2023-04-14). Same results.

[liquidcake1]

Simpler example:

Works:

  re> /(?=.*(.)).*\1(?!1)/
data> 21
 0: 21
 1: 1

Doesn't work:

  re> /(?=.*(.)).*(?!1)\1/  
data> 21
No match

[zherczeg]

Do you know how atomic operations work? You probably want Non-Atomic Positive LookAhead magic called napla.

PCRE2 version 10.43-DEV 2023-04-14 (8-bit)
  re> /(?=.*(.)).*(?!1)\1/
data> 21
No match
data>
  re> /(*napla:.*(.)).*(?!1)\1/
data> 21
 0: 2
 1: 2
data>

[liquidcake1]

Hmmm, my assumption was that all of the backtracking control stuff was purely to optimise slow searches by hinting at where to prune the search tree. As a user, I'd assume the default behaviour would be "correct even if slow, or crash".

Am I wrong?

[liquidcake1]

Aha, I think I've just figured out what's going on here:

• (?= and (?<= are essentially broken when used with captures that can vary, because of the examples I've outlined.
• (?* and (?<* are drop-in replacements which are not atomic.

This is somewhat confusing, especially as my Debian system uses the pcrepattern manpage to detail the old pcre3 behaviour, which still talks about atomic groups but doesn't mention that lookahead is atomic.

I can see how this is a pain. Is there any mechanism by which the library could explain to the user that they're doing something that is likely to result in incorrect behaviour? For instance:

$ grep -P '(?=.*(.))\1' > /dev/null # Show stderr
libpcre2: Use of capture expressions for backtracking inside variable-length atomic
libpcre2: lookahead is unlikely to work as expected. Consider (?*EXPR) in place of
libpcre2: (?=EXPR). Silence this warning while retaining behaviour by explicitly
libpcre2: specifying (?*EXPR(*PRUNE)).

I don't think many people would see the warning, and those who do would surely learn from it -- though I'm not sure how controversial it would be to have one at all.

[zherczeg]

Backward compatibility is > everything in regex world. Assertions were first done this way in perl, so this is their expected behavior.

Please read this before using regexes:
https://www.pcre.org/current/doc/html/pcre2pattern.html

[PhilipHazel]

PCRE2 has no mechanism for issuing textual messages. With regard to Debian: you should be looking at pcre2pattern, not pcrepattern.

[liquidcake1]

Mmmm, I recognise you can't just go change historic behaviours. Warnings like this would be super-helpful though -- perhaps if you've an aspirational TODO they could go there...?

Apologies for not saying -- I mentioned the manpage thing because I then found pcre2pattern; I should have written that and saved you the effort of linking it.

I guess it's just a case of getting users educated, and given I didn't see many clues online about this, not many of us are brave enough to try the things that'd need us to know!

Thanks for the helpful and speedy response; I at least know how to avoid this now. Feel free to close the ticket if you don't intend further work.