Repository navigation
Extra characters erroneously matched when using possessive quantifier with negative lookahead #100061
Description
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
Activity
uyw4687 commentedon Mar 11, 2023
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 commentedon Mar 11, 2023
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
Apythongh-100061 Restore the global Input Stream pointer
pythongh-100061 Restore the global Input Stream pointer
pythongh-100061 Refine comment
uyw4687 commentedon Mar 11, 2023
I also agree with @animalize's solution. Please review :)
pythongh-100061 Add github issue number on comments
pythongh-100061 Remove unneeded comment
pythongh-100061 Refine test case
Merge branch 'main' into pythongh-100061
gh-100061: Proper fix of the bug in the matching of possessive quanti…
[3.12] pythongh-100061: Proper fix of the bug in the matching of poss…
[3.11] pythongh-100061: Proper fix of the bug in the matching of poss…
[3.11] gh-100061: Proper fix of the bug in the matching of possessive…
[3.12] gh-100061: Proper fix of the bug in the matching of possessive…
steve-guillouzic-gc commentedon Sep 12, 2023
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.