gh-155525: Cover quadratic f-string tokenization regression by gwosti · Pull Request #156756 · python/cpython · GitHub

Add regression coverage for modules containing many f-string or t-string replacement fields, expression text after tokenizer buffer growth, and != followed by a format specifier.

The tokenizer refactor in gh-156484 already removed the quadratic copying on main. This PR now retains that implementation and adds the original regression tests. The release-branch backports also need the original expression-span fix, adapted to their older tokenizer layout.

Closes gh-155525.

All commit authors signed the Contributor License Agreement.

Thanks @gwosti for the PR, and @pablogsal for merging it 🌮🎉.. I'm working now to backport this PR to: 3.13, 3.14, 3.15.
🐍🍒⛏🤖

GH-157828 is a backport of this pull request to the 3.15 branch.

Sorry, @gwosti and @pablogsal, I could not cleanly backport this to 3.13 due to a conflict.
Please backport using cherry_picker on command line.

cherry_picker c1df6843d36233ec1da71a1d5f9b74dd6ebc9b97 3.13

GH-157829 is a backport of this pull request to the 3.14 branch.

GH-157828 is a backport of this pull request to the 3.15 branch.

GH-157829 is a backport of this pull request to the 3.14 branch.

GH-157830 is a backport of this pull request to the 3.13 branch.

…57830) [3.13] gh-155525: Cover quadratic f-string tokenization regression (GH-156756) * gh-155525: Avoid quadratic f-string tokenization * fixup! gh-155525: Avoid quadratic f-string tokenization --------- (cherry picked from commit c1df684) Co-authored-by: gwosti <322952417+gwosti@users.noreply.github.com>

…57829) * [ 3.14 ] gh-155525: Avoid quadratic f-string tokenization Adapt the original expression-span fix to the release tokenizer and retain interactive buffers while a formatted string is open. Co-authored-by: gwosti <322952417+gwosti@users.noreply.github.com> * gh-155525: Cover quadratic f-string tokenization regression (GH-156756) * gh-155525: Avoid quadratic f-string tokenization * fixup! gh-155525: Avoid quadratic f-string tokenization --------- (cherry picked from commit c1df684) Co-authored-by: gwosti <322952417+gwosti@users.noreply.github.com> Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com> --------- Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com> Co-authored-by: gwosti <322952417+gwosti@users.noreply.github.com>

…57828) * [ 3.15 ] gh-155525: Avoid quadratic f-string tokenization Adapt the original expression-span fix to the release tokenizer and retain interactive buffers while a formatted string is open. Co-authored-by: gwosti <322952417+gwosti@users.noreply.github.com> * gh-155525: Cover quadratic f-string tokenization regression (GH-156756) * gh-155525: Avoid quadratic f-string tokenization * fixup! gh-155525: Avoid quadratic f-string tokenization --------- (cherry picked from commit c1df684) Co-authored-by: gwosti <322952417+gwosti@users.noreply.github.com> Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com> --------- Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com> Co-authored-by: gwosti <322952417+gwosti@users.noreply.github.com>

⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️

Hi! The buildbot AMD64 Windows11 Non-Debug 3.13 (tier-1) has failed when building commit 3dcc324.

What do you need to do:

Don't panic.
Check the buildbot page in the devguide if you don't know what the buildbots are or how they work.
Go to the page of the buildbot that failed (https://buildbot.python.org/#/builders/1419/builds/1334) and take a look at the build logs.
Check if the failure is related to this commit (3dcc324) or if it is a false positive.
If the failure is related to this commit, please, reflect that on the issue and make a new Pull Request with a fix.

You can take a look at the buildbot page here:

https://buildbot.python.org/#/builders/1419/builds/1334

Failed tests:

test_int

Summary of the results of the build (if available):

==

Click to see traceback logs

Traceback (most recent call last):
  File "b:\uildarea\3.13.ware-win11.nondebug\build\Lib\test\test_int.py", line 729, in test_denial_of_service_prevented_str_to_int
    self.assertLessEqual(sw_fail_huge.seconds, sw_convert.seconds/2)
    ~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError: 0.015625 not less than or equal to 0.0078125


Traceback (most recent call last):
  File "b:\uildarea\3.13.ware-win11.nondebug\build\Lib\test\test_int.py", line 740, in test_denial_of_service_prevented_str_to_int
    self.assertLessEqual(sw_fail_extra_huge.seconds, sw_convert.seconds/2)
    ~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError: 0.015625 not less than or equal to 0.0078125

pythongh-155525 : Avoid quadratic f-string tokenization

7b88fd4

gwosti requested review from lysnikolaou and pablogsal as code owners September 1, 2026 08:33

bedevere-app Bot mentioned this pull request Sep 1, 2026

Quadratic compile() / ast.parse() time for modules with many f-strings (PEP 701 tokenizer update_fstring_expr rescans the whole remaining buffer per replacement field) #155525

Closed

bedevere-app Bot added the awaiting review label Sep 1, 2026

pablogsal reviewed Sep 1, 2026

View reviewed changes

Comment thread Parser/lexer/string.c Outdated

Comment thread Lib/test/test_fstring.py Outdated

Comment thread Parser/lexer/state.h Outdated

fixup! pythongh-155525 : Avoid quadratic f-string tokenization

f39a8eb

gwosti requested a review from pablogsal September 19, 2026 19:40

pablogsal approved these changes Sep 19, 2026

View reviewed changes

bedevere-app Bot added awaiting merge and removed awaiting review labels Sep 19, 2026

Merge main and retain regression coverage after tokenizer refactor

8606edc

pablogsal changed the title gh-155525: Fix quadratic complexity in f-string tokenization gh-155525: Cover quadratic f-string tokenization regression Sep 19, 2026

pablogsal added needs backport to 3.13 only security fixes needs backport to 3.14 bugs and security fixes needs backport to 3.15 bugs and security fixes labels Sep 19, 2026

pablogsal enabled auto-merge (squash) September 19, 2026 21:35

pablogsal merged commit c1df684 into python:main Sep 19, 2026
58 checks passed

bedevere-app Bot removed the awaiting merge label Sep 19, 2026

bedevere-app Bot removed the needs backport to 3.15 bugs and security fixes label Sep 19, 2026

miss-islington-app Bot assigned pablogsal Sep 19, 2026

bedevere-app Bot removed the needs backport to 3.14 bugs and security fixes label Sep 19, 2026

This was referenced Sep 19, 2026

[3.15] gh-155525: Fix quadratic f-string tokenization (GH-156756) #157828

Merged

[3.14] gh-155525: Fix quadratic f-string tokenization (GH-156756) #157829

Merged

pablogsal mentioned this pull request Sep 19, 2026

[3.13] gh-155525: Fix quadratic f-string tokenization (GH-156756) #157830

Merged

bedevere-app Bot removed the needs backport to 3.13 only security fixes label Sep 19, 2026

gh-155525: Cover quadratic f-string tokenization regression by gwosti · Pull Request #156756 · python/cpython · GitHub

Repository navigation

gh-155525: Cover quadratic f-string tokenization regression - #156756

gh-155525: Cover quadratic f-string tokenization regression#156756
pablogsal merged 3 commits into
python:mainfrom
gwosti:perf/fstring-expression-span

gwosti commented Sep 1, 2026 •
edited by pablogsal
Loading

Uh oh!

Uh oh!

python-cla-bot Bot commented Sep 1, 2026 •
edited
Loading

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

miss-islington-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

miss-islington-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

bedevere-bot commented Sep 19, 2026

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

gh-155525: Cover quadratic f-string tokenization regression by gwosti · Pull Request #156756 · python/cpython · GitHub

Repository navigation

gh-155525: Cover quadratic f-string tokenization regression - #156756

gh-155525: Cover quadratic f-string tokenization regression#156756pablogsal merged 3 commits intopython:mainpython/cpython:mainfrom gwosti:perf/fstring-expression-spangwosti/cpython:perf/fstring-expression-spanCopy head branch name to clipboard

Conversation

gwosti commented Sep 1, 2026 • edited by pablogsal Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

python-cla-bot Bot commented Sep 1, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

miss-islington-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

miss-islington-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

bedevere-app Bot commented Sep 19, 2026

Uh oh!

bedevere-bot commented Sep 19, 2026

⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

gh-155525: Cover quadratic f-string tokenization regression#156756
pablogsal merged 3 commits into
python:mainfrom
gwosti:perf/fstring-expression-span

gwosti commented Sep 1, 2026 •
edited by pablogsal
Loading

python-cla-bot Bot commented Sep 1, 2026 •
edited
Loading