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.

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

gh-93671: Avoid exponential backtracking in deeply nested sequence patterns in match statements #93680

Merged
merged 2 commits into from Jun 10, 2022
Merged

gh-93671: Avoid exponential backtracking in deeply nested sequence patterns in match statements #93680

merged 2 commits into from Jun 10, 2022
+36 −3

Conversation

pablogsal
Copy link
Member

@pablogsal pablogsal commented Jun 10, 2022 •
edited

closes: #93671

@pablogsal pablogsal requested a review from lysnikolaou as a code owner Jun 10, 2022
@pablogsal pablogsal requested a review from brandtbucher Jun 10, 2022
@Fidget-Spinner
Copy link
Member

@Fidget-Spinner Fidget-Spinner commented Jun 10, 2022

Should there be a test for this?

@pablogsal
Copy link
Member Author

@pablogsal pablogsal commented Jun 10, 2022

Should there be a test for this?

I submitted the PR so we can start checking that it works in other cases.

I will be adding a bunch of cases, but the tests are limited because there is nothing crashing, although I can add a bunch of cases that would take years to succeed.

@ambv
Copy link
Contributor

@ambv ambv commented Jun 10, 2022

I can confirm that the new test just doesn't finish on main without the patch. Since this is in the parser, it's also not something you can easily CTRL-C out of 😆

@ambv ambv merged commit 53a8b17 into python:main Jun 10, 2022
13 checks passed
@miss-islington
Copy link
Contributor

@miss-islington miss-islington commented Jun 10, 2022

Thanks @pablogsal for the PR, and @ambv for merging it 🌮🎉.. I'm working now to backport this PR to: 3.10, 3.11.
🐍🍒⛏🤖

@miss-islington
Copy link
Contributor

@miss-islington miss-islington commented Jun 10, 2022

Sorry, @pablogsal and @ambv, I could not cleanly backport this to 3.10 due to a conflict.
Please backport using cherry_picker on command line.
cherry_picker 53a8b17895e91d08f76a2fb59a555d012cd85ab4 3.10

miss-islington pushed a commit to miss-islington/cpython that referenced this issue Jun 10, 2022
@pablogsal @miss-islington
pythongh-93671: Avoid exponential backtracking in deeply nested seque…
af70c4f 
…nce patterns in match statements (pythonGH-93680)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit 53a8b17)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
@bedevere-bot
Copy link

@bedevere-bot bedevere-bot commented Jun 10, 2022

GH-93689 is a backport of this pull request to the 3.11 branch.

miss-islington added a commit that referenced this issue Jun 10, 2022
@miss-islington @pablogsal
gh-93671: Avoid exponential backtracking in deeply nested sequence pa…
f9d0240 
…tterns in match statements (GH-93680)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit 53a8b17)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
@pablogsal
Copy link
Member Author

@pablogsal pablogsal commented Jun 10, 2022

Are you preparing the backport or should I do it? @ambv

@pablogsal pablogsal deleted the gh-93671 branch Jun 10, 2022
pablogsal added a commit to pablogsal/cpython that referenced this issue Jun 10, 2022
@pablogsal
[3.10] pythongh-93671: Avoid exponential backtracking in deeply neste…
fd56269 
…d sequence patterns in match statements (pythonGH-93680)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>.
(cherry picked from commit 53a8b17)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
@bedevere-bot
Copy link

@bedevere-bot bedevere-bot commented Jun 10, 2022

GH-93690 is a backport of this pull request to the 3.10 branch.

pablogsal added a commit that referenced this issue Jun 10, 2022
@pablogsal
[3.10] gh-93671: Avoid exponential backtracking in deeply nested sequ…
8f36c73 
…ence patterns in match statements (GH-93680) (#93690)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>.
(cherry picked from commit 53a8b17)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
@brandtbucher
Copy link
Member

@brandtbucher brandtbucher commented Jun 10, 2022

Thanks for the quick fix, @pablogsal!

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

@lysnikolaou lysnikolaou

@brandtbucher brandtbucher

Assignees

@ambv ambv

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Python3.10.5 Pattern Matching Excessive Memory Consumption
6 participants
@pablogsal @Fidget-Spinner @ambv @miss-islington @bedevere-bot @brandtbucher