Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Possessive quantifier matches where an ordinary quantifier doesn't #106052

Closed
benrg opened this issue Jun 24, 2023 · 7 comments
Closed

Possessive quantifier matches where an ordinary quantifier doesn't #106052

benrg opened this issue Jun 24, 2023 · 7 comments
Assignees
@serhiy-storchaka
Labels
3.11 only security fixes 3.12 bugs and security fixes 3.13 new features, bugs and security fixes topic-regex type-bug An unexpected behavior, bug, or error

Comments

@benrg
Copy link

benrg commented Jun 24, 2023 •
edited by bedevere-bot 

>>> import re
>>> re.fullmatch('(?:ab?c)*', 'a')
>>> re.fullmatch('(?:ab?c)*+', 'a')
<re.Match object; span=(0, 1), match='a'>
>>>

I'm not sure that I completely understand the behavior of the possessive quantifiers, but I think that if R* doesn't match a string then R*+ shouldn't match it, where R is any regex.

Versions tested:

3.12.0b3 (tags/v3.12.0b3:f992a60, Jun 20 2023, 12:25:40) [MSC v.1936 64 bit (AMD64)]
3.11.4 (tags/v3.11.4:d2340ef, Jun  7 2023, 05:45:37) [MSC v.1934 64 bit (AMD64)]
3.11.4 (tags/v3.11.4:d2340ef, Jun  7 2023, 05:30:09) [MSC v.1934 32 bit (Intel)]
3.11.4 (main, Jun 14 2023, 18:33:43) [GCC 10.2.1 20210110]

Linked PRs
@benrg benrg added the type-bug An unexpected behavior, bug, or error label Jun 24, 2023
@ferdnyc
Copy link
Contributor

ferdnyc commented Jun 24, 2023

If nothing else, the docs claim that

x*+, x++ and x?+ are equivalent to (?>x*), (?>x+) and (?>x?) correspondingly.

And,

>>> import re
>>> re.fullmatch('(?>(?:ab?c)*)', 'a')
>>>

So, that seems a clear discrepancy.

@arhadthedev
Copy link
Member

@ezio-melotti, @serhiy-storchaka (as re module experts)

@serhiy-storchaka serhiy-storchaka self-assigned this Jun 24, 2023
@serhiy-storchaka
Copy link
Member

It is definitely a bug.

The simplest fix would be implementing possessive quantifiers via atomic groups. It may be less efficient, but gives us time to fix the specialized opcode.

serhiy-storchaka added a commit to serhiy-storchaka/cpython that referenced this issue Jul 7, 2023
@serhiy-storchaka
pythongh-106052: Fix bug in the matching of possessive quantifiers
4374d46 
It did not work in the case of a subpattern containing backtraces.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups.
serhiy-storchaka added a commit to serhiy-storchaka/cpython that referenced this issue Jul 7, 2023
@serhiy-storchaka
pythongh-106052: Fix bug in the matching of possessive quantifiers
d73d88e 
It did not work in the case of a subpattern containing backtraces.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups.
@bedevere-bot bedevere-bot mentioned this issue Jul 7, 2023
Merged
@serhiy-storchaka serhiy-storchaka added 3.11 only security fixes 3.12 bugs and security fixes 3.13 new features, bugs and security fixes labels Jul 7, 2023
serhiy-storchaka added a commit to serhiy-storchaka/cpython that referenced this issue Jul 7, 2023
@serhiy-storchaka
pythongh-106052: Fix bug in the matching of possessive quantifiers
1a420c0 
It did not work in the case of a subpattern containing backtraces.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups.
serhiy-storchaka added a commit to serhiy-storchaka/cpython that referenced this issue Jul 10, 2023
@serhiy-storchaka
pythongh-106052: Fix bug in the matching of possessive quantifiers
89bf9dc 
It did not work in the case of a subpattern containing backtracking.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups.
@serhiy-storchaka
Copy link
Member

#106515 is a last resort. It should be merged if better solution not be found before the next releases.

@Yhg1s
Copy link
Member

Yhg1s commented Jul 11, 2023

FYI, per comments in #106515, I'm not treating this as a release blocker in 3.12 beta 4.

@gpshead gpshead mentioned this issue Jul 26, 2023
Closed
@gpshead
Copy link
Member

gpshead commented Jul 26, 2023

(per comment on the PR, I don't think this is really a release blocker given the bug shipped in 3.11)

serhiy-storchaka added a commit that referenced this issue Aug 9, 2023
@serhiy-storchaka
gh-106052: Fix bug in the matching of possessive quantifiers (gh-106515)
7b6e34e 
It did not work in the case of a subpattern containing backtracking.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups.
serhiy-storchaka added a commit to serhiy-storchaka/cpython that referenced this issue Aug 9, 2023
@serhiy-storchaka
[3.11] pythongh-106052: Fix bug in the matching of possessive quantif…
d9686c0 
…iers (pythongh-106515)

It did not work in the case of a subpattern containing backtracking.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups..
(cherry picked from commit 7b6e34e)

Co-authored-by: Serhiy Storchaka <storchaka@gmail.com>
@bedevere-bot bedevere-bot mentioned this issue Aug 9, 2023
Merged
serhiy-storchaka added a commit to serhiy-storchaka/cpython that referenced this issue Aug 9, 2023
@serhiy-storchaka
[3.12] pythongh-106052: Fix bug in the matching of possessive quantif…
bfcee6c 
…iers (pythongh-106515)

It did not work in the case of a subpattern containing backtracking.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups..
(cherry picked from commit 7b6e34e)

Co-authored-by: Serhiy Storchaka <storchaka@gmail.com>
@bedevere-bot bedevere-bot mentioned this issue Aug 9, 2023
Merged
serhiy-storchaka added a commit that referenced this issue Aug 9, 2023
@serhiy-storchaka
[3.11] gh-106052: Fix bug in the matching of possessive quantifiers (G…
5b76eaf 
…H-106515) (GH-107795)

It did not work in the case of a subpattern containing backtracking.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups.
(cherry picked from commit 7b6e34e)
Yhg1s pushed a commit that referenced this issue Aug 9, 2023
@serhiy-storchaka
[3.12] gh-106052: Fix bug in the matching of possessive quantifiers (G…
3bb43b7 
…H-106515) (#107796)

[3.12] gh-106052: Fix bug in the matching of possessive quantifiers (gh-106515)

It did not work in the case of a subpattern containing backtracking.

Temporary implement possessive quantifiers as equivalent greedy qualifiers
in atomic groups..
(cherry picked from commit 7b6e34e)
@serhiy-storchaka serhiy-storchaka mentioned this issue Aug 16, 2023
Merged
@serhiy-storchaka
Copy link
Member

It is actually a duplicate of #100061 for which there is a proper fix.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@serhiy-storchaka serhiy-storchaka

Labels
3.11 only security fixes 3.12 bugs and security fixes 3.13 new features, bugs and security fixes topic-regex type-bug An unexpected behavior, bug, or error
Projects
Release and Deferred blockers 🚫
Archived in project
Milestone
No milestone
Development

No branches or pull requests
7 participants
@gpshead @ferdnyc @benrg @serhiy-storchaka @Yhg1s @arhadthedev @AlexWaygood