Description

steve-guillouzic-gc

opened on Dec 6, 2022

Issue body actions

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

Activity

1. steve-guillouzic-gc

   added

   type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

   on Dec 6, 2022
2. ronaldoussoren

   added

   topic-regex

   on Dec 8, 2022
4. uyw4687 commented on Mar 11, 2023

   

   uyw4687

   on Mar 11, 2023

   Contributor

   More actions

   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.
5. uyw4687 commented on Mar 11, 2023

   

   uyw4687

   on Mar 11, 2023

   Contributor

   More actions

   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
6. uyw4687

   added 3 commits that reference this issue on Mar 11, 2023

   pythongh-100061 Restore the global Input Stream pointer

   4727b47

   pythongh-100061 Restore the global Input Stream pointer

   007e7d7

   pythongh-100061 Refine comment

   43dc3cf
7. uyw4687 commented on Mar 11, 2023

   

   uyw4687

   on Mar 11, 2023

   Contributor

   More actions

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

   assigned

   uyw4687

   on Mar 12, 2023
10. uyw4687

    added 3 commits that reference this issue on Mar 13, 2023

    pythongh-100061 Add github issue number on comments

    d33c012

    pythongh-100061 Remove unneeded comment

    8a958f1

    pythongh-100061 Refine test case

    b5476e4
11. serhiy-storchaka

    added 4 commits that reference this issue on Aug 16, 2023

    Merge branch 'main' into pythongh-100061

    4c4b271

    gh-100061: Proper fix of the bug in the matching of possessive quanti…

    abd9cc5

    [3.12] pythongh-100061: Proper fix of the bug in the matching of poss…

    287c6ca

    [3.11] pythongh-100061: Proper fix of the bug in the matching of poss…

    410f5dd
12. serhiy-storchaka

    linked a pull request that will close this issue[3.12] gh-100061: Proper fix of the bug in the matching of possessive quantifiers (GH-102612) #108003on Aug 16, 2023
13. serhiy-storchaka

    added a commit that references this issue on Aug 16, 2023

    [3.11] gh-100061: Proper fix of the bug in the matching of possessive…

    26137e2
14. Yhg1s

    added a commit that references this issue on Aug 16, 2023

    [3.12] gh-100061: Proper fix of the bug in the matching of possessive…

    bd2ef82
15. serhiy-storchaka

    closed this as completedon Aug 16, 2023
16. steve-guillouzic-gc commented on Sep 12, 2023

    

    steve-guillouzic-gc

    on Sep 12, 2023

    Author

    More actions

    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.

Issue actions