Extra characters erroneously matched when using possessive quantifier with negative lookahead

[steve-guillouzic-gc]

Bug report

Regular expressions that combine a possessive quantifier with a negative lookahead match extra erroneous characters in re module 2.2.1 of Python 3.11. (The test was run on Windows 10 using the official distribution of Python 3.11.0.)

For example, the following regular expression aims to match consecutive characters that are not 'C' in string 'ABC'. (There are simpler ways to do this, but this is just an example to illustrate the problem.)

import re

text = 'ABC'
print('Possessive quantifier, negative lookahead:', 
      re.findall('(((?!C).)++)', text))

Output:

Possessive quantifier, negative lookahead: [('ABC', 'B')]

The first subgroup of the match is the entire match, while the second subgroup is the last character that was matched. They should be 'AB' and 'B', respectively. While the last matched character is correctly identified as 'B', the complete match is erroneously set to 'ABC'.

Replacing the negative lookahead with a positive lookahead eliminates the problem:

print('Possessive quantifier, positive lookahead:',
      re.findall('(((?=[^C]).)++)', text))

Output:

Possessive quantifier, positive lookahead: [('AB', 'B')]

Alternately, keeping the negative lookahead but replacing the possessive quantifier with a greedy quantifier also eliminates the problem:

print('Greedy quantifier, negative lookahead:',
      re.findall('(((?!C).)+)', text))

Output:

Greedy quantifier, negative lookahead: [('AB', 'B')]

While this example uses the ++ quantifier, the *+ and ?+ quantifiers exhibit similar behaviour. Also, using a longer pattern in the negative lookahead leads to even more characters being erroneously matched.

Thank you for adding possessive quantifiers to the re module! It is a very useful feature!

Environment

• re module 2.2.1 in standard library
• CPython versions tested on: 3.11.0
• Operating system and architecture: Windows 10

Linked PRs

• gh-100061: Restore the global Input Stream pointer #102612
• [3.12] gh-100061: Proper fix of the bug in the matching of possessive quantifiers (GH-102612) #108003
• [3.11] gh-100061: Proper fix of the bug in the matching of possessive quantifiers (GH-102612) #108004

[ghost]

This should fix the bug.
I don't have time. Welcome others to investigate and submit a PR.

--- a/Modules/_sre/sre_lib.h
+++ b/Modules/_sre/sre_lib.h
@@ -1333,7 +1333,7 @@ SRE(match)(SRE_STATE* state, const SRE_CODE* pattern, int toplevel)
                        state. */
                     MARK_POP(ctx->lastmark);
                     LASTMARK_RESTORE();
-
+                    state->ptr = ptr;
                     /* We have sufficient matches, so exit loop. */
                     break;
                 }

[uyw4687]

Can you kindly tell me why if it's valid to use lookahead not lookbehind(?<!) for backward checks?
I'm referring to https://www.regular-expressions.info/lookaround.html and I thought we might need to use lookbehind since it says Lookbehind has the same effect, but works backwards. It tells the regex engine to temporarily step backwards in the string.

[uyw4687]

But still, while looking into this issue, moving (?!C) up front still have similar problem,
giving following result for the command re.match('((.(?!C))++)', 'ABC')
<re.Match object; span=(0, 3), match='ABC'>

unlike java giving A

[uyw4687]

I also agree with @animalize's solution. Please review :)

[ghost]

Can you kindly tell me why if it's valid to use lookahead not lookbehind(?<!) for backward checks? I'm referring to https://www.regular-expressions.info/lookaround.html and I thought we might need to use lookbehind since it says Lookbehind has the same effect, but works backwards. It tells the regex engine to temporarily step backwards in the string.

IIRC, sre's lookbehind can only match fixed length pattern, so it can use lookahead with an offset to handle it.

[steve-guillouzic-gc]

Thank you for the fix! It works perfectly. To belatedly answer @uyw4687's question, as @animalize mentioned, I use a lookahead because the lookbehind in sre is fixed width only.