https://github.com/python/cpython/commit/3dcc324a945e792aa32c141bad23c481b0974d07 commit: 3dcc324a945e792aa32c141bad23c481b0974d07 branch: 3.13 author: Pablo Galindo Salgado <[email protected]> committer: pablogsal <[email protected]> date: 2026-09-19T22:31:16Z summary:
[3.13] gh-155525: Fix quadratic f-string tokenization (GH-156756) (#157830) [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 c1df6843d36233ec1da71a1d5f9b74dd6ebc9b97) Co-authored-by: gwosti <[email protected]> files: A Misc/NEWS.d/next/Core_and_Builtins/2026-09-01-07-15-20.gh-issue-155525.A7kP2m.rst M Lib/test/test_fstring.py M Parser/lexer/buffer.c M Parser/lexer/lexer.c M Parser/lexer/lexer.h M Parser/lexer/state.c M Parser/lexer/state.h M Parser/tokenizer/file_tokenizer.c M Parser/tokenizer/readline_tokenizer.c diff --git a/Lib/test/test_fstring.py b/Lib/test/test_fstring.py index d86977c55c3b904..b47e906ce351c74 100644 --- a/Lib/test/test_fstring.py +++ b/Lib/test/test_fstring.py @@ -14,11 +14,13 @@ import re import types import decimal +import subprocess import unittest import warnings from test import support from test.support.os_helper import temp_cwd -from test.support.script_helper import assert_python_failure, assert_python_ok +from test.support.script_helper import ( + assert_python_failure, assert_python_ok, spawn_python) a_global = 'global variable' @@ -800,6 +802,18 @@ def build_fstr(n, extra=''): s = "f'{1}' 'x' 'y'" * 1024 self.assertEqual(eval(s), '1xy' * 1024) + @support.requires_resource('cpu') + def test_many_fstrings_in_module(self): + fields = ''.join(f'{{x{i}}}' for i in range(100)) + source = ''.join( + f"value_{i} = f'{fields}'\n" for i in range(1_000) + ) + namespace = {f'x{i}': str(i) for i in range(100)} + expected = ''.join(str(i) for i in range(100)) + exec(source, namespace) + self.assertEqual(namespace['value_0'], expected) + self.assertEqual(namespace['value_999'], expected) + def test_format_specifier_expressions(self): width = 10 precision = 4 @@ -1316,6 +1330,9 @@ def test_not_equal(self): self.assertEqual(f'{3!=4:}', 'True') self.assertEqual(f'{3!=4!s}', 'True') self.assertEqual(f'{3!=4!s:.3}', 'Tru') + a = 3 + b = 4 + self.assertEqual(f'{a!=b=:>10}', 'a!=b= 1') def test_equal_equal(self): # Because an expression ending in = has special meaning, @@ -1760,6 +1777,32 @@ def test_debug_in_file(self): self.assertEqual(stdout.decode('utf-8').strip().replace('\r\n', '\n').replace('\r', '\n'), "3\n=3") + @support.requires_subprocess() + def test_expression_in_interactive_after_buffer_resize(self): + expression = "(\n" + (" " * 64 + "\n") * 256 + "1\n)" + source = ( + f"result = f'''{{{expression}=}}'''\n" + "print(repr(result))\n" + ) + with spawn_python('-i', '-q', stderr=subprocess.PIPE) as process: + stdout, stderr = process.communicate( + source.encode(), timeout=support.SHORT_TIMEOUT) + self.assertEqual(process.returncode, 0, stderr) + self.assertEqual(stdout.decode().strip(), repr(expression + "=1")) + + def test_debug_in_file_after_buffer_resize(self): + expression = "(\n" + (" " * 64 + "\n") * 256 + "1\n)" + expected = expression + "=1" + with temp_cwd(): + script = 'script.py' + source = ( + f"result = f'''{{{expression}=}}'''\n" + f"assert result == {expected!r}\n" + ) + with open(script, 'w') as f: + f.write(source) + assert_python_ok(script) + def test_syntax_warning_infinite_recursion_in_file(self): with temp_cwd(): script = 'script.py' diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2026-09-01-07-15-20.gh-issue-155525.A7kP2m.rst b/Misc/NEWS.d/next/Core_and_Builtins/2026-09-01-07-15-20.gh-issue-155525.A7kP2m.rst new file mode 100644 index 000000000000000..1a67289d595d6a4 --- /dev/null +++ b/Misc/NEWS.d/next/Core_and_Builtins/2026-09-01-07-15-20.gh-issue-155525.A7kP2m.rst @@ -0,0 +1 @@ +Fix quadratic-time tokenization of modules containing many f-strings. diff --git a/Parser/lexer/buffer.c b/Parser/lexer/buffer.c index 6815e055d24c60d..f4db20206a2bf55 100644 --- a/Parser/lexer/buffer.c +++ b/Parser/lexer/buffer.c @@ -15,6 +15,8 @@ _PyLexer_remember_fstring_buffers(struct tok_state *tok) mode = &(tok->tok_mode_stack[index]); mode->f_string_start_offset = mode->f_string_start == NULL ? -1 : mode->f_string_start - tok->buf; mode->f_string_multi_line_start_offset = mode->f_string_multi_line_start == NULL ? -1 : mode->f_string_multi_line_start - tok->buf; + mode->last_expr_start_offset = mode->last_expr_start == NULL + ? -1 : mode->last_expr_start - tok->buf; } } @@ -29,6 +31,8 @@ _PyLexer_restore_fstring_buffers(struct tok_state *tok) mode = &(tok->tok_mode_stack[index]); mode->f_string_start = mode->f_string_start_offset < 0 ? NULL : tok->buf + mode->f_string_start_offset; mode->f_string_multi_line_start = mode->f_string_multi_line_start_offset < 0 ? NULL : tok->buf + mode->f_string_multi_line_start_offset; + mode->last_expr_start = mode->last_expr_start_offset < 0 + ? NULL : tok->buf + mode->last_expr_start_offset; } } diff --git a/Parser/lexer/lexer.c b/Parser/lexer/lexer.c index dd5f9e7a8d1ea6f..e528f2252dd57d4 100644 --- a/Parser/lexer/lexer.c +++ b/Parser/lexer/lexer.c @@ -100,6 +100,10 @@ set_fstring_expr(struct tok_state* tok, struct token *token, char c) { if (!tok_mode->f_string_debug || token->metadata) { return 0; } + const char *expression = tok_mode->last_expr_start; + assert(expression != NULL); + assert(expression <= tok->start); + Py_ssize_t expression_size = tok->start - expression; PyObject *res = NULL; // Look for a # character outside of string literals @@ -107,8 +111,8 @@ set_fstring_expr(struct tok_state* tok, struct token *token, char c) { int in_string = 0; char quote_char = 0; - for (Py_ssize_t i = 0; i < tok_mode->last_expr_size - tok_mode->last_expr_end; i++) { - char ch = tok_mode->last_expr_buffer[i]; + for (Py_ssize_t i = 0; i < expression_size; i++) { + char ch = expression[i]; // Skip escaped characters if (ch == '\\') { @@ -144,7 +148,7 @@ set_fstring_expr(struct tok_state* tok, struct token *token, char c) { // If we found a # character in the expression, we need to handle comments if (hash_detected) { // Allocate buffer for processed result - char *result = (char *)PyMem_Malloc((tok_mode->last_expr_size - tok_mode->last_expr_end + 1) * sizeof(char)); + char *result = (char *)PyMem_Malloc((expression_size + 1) * sizeof(char)); if (!result) { return -1; } @@ -155,8 +159,8 @@ set_fstring_expr(struct tok_state* tok, struct token *token, char c) { quote_char = 0; // Current string quote char // Process each character - while (i < tok_mode->last_expr_size - tok_mode->last_expr_end) { - char ch = tok_mode->last_expr_buffer[i]; + while (i < expression_size) { + char ch = expression[i]; // Handle string quotes if (ch == '"' || ch == '\'') { @@ -171,11 +175,11 @@ set_fstring_expr(struct tok_state* tok, struct token *token, char c) { } // Skip comments else if (ch == '#' && !in_string) { - while (i < tok_mode->last_expr_size - tok_mode->last_expr_end && - tok_mode->last_expr_buffer[i] != '\n') { + while (i < expression_size && + expression[i] != '\n') { i++; } - if (i < tok_mode->last_expr_size - tok_mode->last_expr_end) { + if (i < expression_size) { result[j++] = '\n'; } } @@ -191,8 +195,8 @@ set_fstring_expr(struct tok_state* tok, struct token *token, char c) { PyMem_Free(result); } else { res = PyUnicode_DecodeUTF8( - tok_mode->last_expr_buffer, - tok_mode->last_expr_size - tok_mode->last_expr_end, + expression, + expression_size, NULL ); } @@ -204,61 +208,6 @@ set_fstring_expr(struct tok_state* tok, struct token *token, char c) { return 0; } -int -_PyLexer_update_fstring_expr(struct tok_state *tok, char cur) -{ - assert(tok->cur != NULL); - - Py_ssize_t size = strlen(tok->cur); - tokenizer_mode *tok_mode = TOK_GET_MODE(tok); - - switch (cur) { - case 0: - if (!tok_mode->last_expr_buffer || tok_mode->last_expr_end >= 0) { - return 1; - } - char *new_buffer = PyMem_Realloc( - tok_mode->last_expr_buffer, - tok_mode->last_expr_size + size - ); - if (new_buffer == NULL) { - PyMem_Free(tok_mode->last_expr_buffer); - goto error; - } - tok_mode->last_expr_buffer = new_buffer; - strncpy(tok_mode->last_expr_buffer + tok_mode->last_expr_size, tok->cur, size); - tok_mode->last_expr_size += size; - break; - case '{': - if (tok_mode->last_expr_buffer != NULL) { - PyMem_Free(tok_mode->last_expr_buffer); - } - tok_mode->last_expr_buffer = PyMem_Malloc(size); - if (tok_mode->last_expr_buffer == NULL) { - goto error; - } - tok_mode->last_expr_size = size; - tok_mode->last_expr_end = -1; - strncpy(tok_mode->last_expr_buffer, tok->cur, size); - break; - case '}': - case '!': - tok_mode->last_expr_end = strlen(tok->start); - break; - case ':': - if (tok_mode->last_expr_end == -1) { - tok_mode->last_expr_end = strlen(tok->start); - } - break; - default: - Py_UNREACHABLE(); - } - return 1; -error: - tok->done = E_NOMEM; - return 0; -} - static int lookahead(struct tok_state *tok, const char *test) { @@ -1023,9 +972,8 @@ tok_get_normal_mode(struct tok_state *tok, tokenizer_mode* current_tok, struct t the_current_tok->f_string_line_start = tok->lineno; the_current_tok->f_string_start_offset = -1; the_current_tok->f_string_multi_line_start_offset = -1; - the_current_tok->last_expr_buffer = NULL; - the_current_tok->last_expr_size = 0; - the_current_tok->last_expr_end = -1; + the_current_tok->last_expr_start = NULL; + the_current_tok->last_expr_start_offset = -1; the_current_tok->in_format_spec = 0; the_current_tok->f_string_debug = 0; @@ -1179,9 +1127,6 @@ tok_get_normal_mode(struct tok_state *tok, tokenizer_mode* current_tok, struct t int cursor_in_format_with_debug = cursor == 1 && (current_tok->f_string_debug || in_format_spec); int cursor_valid = cursor == 0 || cursor_in_format_with_debug; - if ((cursor_valid) && !_PyLexer_update_fstring_expr(tok, c)) { - return MAKE_TOKEN(ENDMARKER); - } if ((cursor_valid) && c != '{' && set_fstring_expr(tok, token, c)) { return MAKE_TOKEN(ERRORTOKEN); } @@ -1322,6 +1267,9 @@ tok_get_fstring_mode(struct tok_state *tok, tokenizer_mode* current_tok, struct if (start_char == '{') { int peek1 = tok_nextc(tok); tok_backup(tok, peek1); + if (peek1 != '{') { + current_tok->last_expr_start = tok->cur; + } tok_backup(tok, start_char); if (peek1 != '{') { current_tok->curly_bracket_expr_start_depth++; @@ -1345,13 +1293,6 @@ tok_get_fstring_mode(struct tok_state *tok, tokenizer_mode* current_tok, struct } } - if (current_tok->last_expr_buffer != NULL) { - PyMem_Free(current_tok->last_expr_buffer); - current_tok->last_expr_buffer = NULL; - current_tok->last_expr_size = 0; - current_tok->last_expr_end = -1; - } - p_start = tok->start; p_end = tok->cur; tok->tok_mode_stack_index--; @@ -1434,12 +1375,10 @@ tok_get_fstring_mode(struct tok_state *tok, tokenizer_mode* current_tok, struct } if (c == '{') { - if (!_PyLexer_update_fstring_expr(tok, c)) { - return MAKE_TOKEN(ENDMARKER); - } int peek = tok_nextc(tok); if (peek != '{' || in_format_spec) { tok_backup(tok, peek); + current_tok->last_expr_start = tok->cur; tok_backup(tok, c); current_tok->curly_bracket_expr_start_depth++; if (current_tok->curly_bracket_expr_start_depth >= MAX_EXPR_NESTING) { diff --git a/Parser/lexer/lexer.h b/Parser/lexer/lexer.h index 7f21bf56bba2d19..73781eaa60cea88 100644 --- a/Parser/lexer/lexer.h +++ b/Parser/lexer/lexer.h @@ -3,8 +3,6 @@ #include "state.h" -int _PyLexer_update_fstring_expr(struct tok_state *tok, char cur); - int _PyTokenizer_Get(struct tok_state *, struct token *); #endif diff --git a/Parser/lexer/state.c b/Parser/lexer/state.c index 7d3b9e9ae59cbc4..0e09fc8f8f35e1f 100644 --- a/Parser/lexer/state.c +++ b/Parser/lexer/state.c @@ -65,24 +65,6 @@ _PyTokenizer_tok_new(void) return tok; } -static void -free_fstring_expressions(struct tok_state *tok) -{ - int index; - tokenizer_mode *mode; - - for (index = tok->tok_mode_stack_index; index >= 0; --index) { - mode = &(tok->tok_mode_stack[index]); - if (mode->last_expr_buffer != NULL) { - PyMem_Free(mode->last_expr_buffer); - mode->last_expr_buffer = NULL; - mode->last_expr_size = 0; - mode->last_expr_end = -1; - mode->in_format_spec = 0; - } - } -} - /* Free a tok_state structure */ void _PyTokenizer_Free(struct tok_state *tok) @@ -103,7 +85,6 @@ _PyTokenizer_Free(struct tok_state *tok) if (tok->interactive_src_start != NULL) { PyMem_Free(tok->interactive_src_start); } - free_fstring_expressions(tok); PyMem_Free(tok); } diff --git a/Parser/lexer/state.h b/Parser/lexer/state.h index 7df24d571d558e6..7e246ee4d3cd6d6 100644 --- a/Parser/lexer/state.h +++ b/Parser/lexer/state.h @@ -57,9 +57,10 @@ typedef struct _tokenizer_mode { Py_ssize_t f_string_start_offset; Py_ssize_t f_string_multi_line_start_offset; - Py_ssize_t last_expr_size; - Py_ssize_t last_expr_end; - char* last_expr_buffer; + /* Points into tok->buf, which is retained while INSIDE_FSTRING(tok). */ + const char* last_expr_start; + Py_ssize_t last_expr_start_offset; + int f_string_debug; int in_format_spec; } tokenizer_mode; diff --git a/Parser/tokenizer/file_tokenizer.c b/Parser/tokenizer/file_tokenizer.c index 3e711eb8792c1ed..6d203cd7eab37fa 100644 --- a/Parser/tokenizer/file_tokenizer.c +++ b/Parser/tokenizer/file_tokenizer.c @@ -238,7 +238,7 @@ tok_underflow_interactive(struct tok_state *tok) { PyMem_Free(newtok); tok->done = E_EOF; } - else if (tok->start != NULL) { + else if (tok->start != NULL || INSIDE_FSTRING(tok)) { Py_ssize_t cur_multi_line_start = tok->multi_line_start - tok->buf; _PyLexer_remember_fstring_buffers(tok); size_t size = strlen(newtok); @@ -273,9 +273,6 @@ tok_underflow_interactive(struct tok_state *tok) { return 0; } - if (tok->tok_mode_stack_index && !_PyLexer_update_fstring_expr(tok, 0)) { - return 0; - } return 1; } @@ -320,10 +317,6 @@ tok_underflow_file(struct tok_state *tok) { tok->implicit_newline = 1; } - if (tok->tok_mode_stack_index && !_PyLexer_update_fstring_expr(tok, 0)) { - return 0; - } - ADVANCE_LINENO(); if (tok->decoding_state != STATE_NORMAL) { if (tok->lineno > 2) { diff --git a/Parser/tokenizer/readline_tokenizer.c b/Parser/tokenizer/readline_tokenizer.c index b325cbd6d1cd51d..05fb589fe5f9812 100644 --- a/Parser/tokenizer/readline_tokenizer.c +++ b/Parser/tokenizer/readline_tokenizer.c @@ -90,10 +90,6 @@ tok_underflow_readline(struct tok_state* tok) { tok->implicit_newline = 1; } - if (tok->tok_mode_stack_index && !_PyLexer_update_fstring_expr(tok, 0)) { - return 0; - } - ADVANCE_LINENO(); /* The default encoding is UTF-8, so make sure we don't have any non-UTF-8 sequences in it. */ _______________________________________________ Python-checkins mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3//lists/python-checkins.python.org Member address: [email protected]
