https://github.com/python/cpython/commit/b5cbbb288f2e0d48e1b0c36a82825e14965c983e commit: b5cbbb288f2e0d48e1b0c36a82825e14965c983e branch: 3.15 author: Miss Islington (bot) <[email protected]> committer: pablogsal <[email protected]> date: 2026-09-19T22:37:33Z summary:
[3.15] gh-155525: Fix quadratic f-string tokenization (GH-156756) (#157828) * [ 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 <[email protected]> * 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]> Co-authored-by: Pablo Galindo Salgado <[email protected]> --------- Co-authored-by: Pablo Galindo Salgado <[email protected]> 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 Lib/test/test_tstring.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 aa837a3289d7045..4cda471b29db980 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' @@ -822,6 +824,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 @@ -1338,6 +1352,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, @@ -1792,6 +1809,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/Lib/test/test_tstring.py b/Lib/test/test_tstring.py index 046cc1e58346089..1e5f14ca007d1e6 100644 --- a/Lib/test/test_tstring.py +++ b/Lib/test/test_tstring.py @@ -1,5 +1,9 @@ +import subprocess import unittest +from test import support +from test.support.os_helper import temp_cwd +from test.support.script_helper import assert_python_ok, spawn_python from test.test_string._support import TStringBaseCase, fstring @@ -79,6 +83,44 @@ def upper(self): ) self.assertEqual(fstring(t), "Name: Bob, Age: 30") + @support.requires_subprocess() + def test_expression_in_interactive_after_buffer_resize(self): + expression = "(\n" + (" " * 64 + "\n") * 256 + "1\n)" + source = ( + f"result = t'''{{{expression}}}'''\n" + "print(repr(result.interpolations[0].expression))\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)) + + def test_interpolation_expression_in_file_after_buffer_resize(self): + expression = "(\n" + (" " * 64 + "\n") * 256 + "1\n)" + with temp_cwd(): + script = 'script.py' + source = ( + f"template = t'''{{{expression}}}'''\n" + "interpolation = template.interpolations[0]\n" + f"assert interpolation.expression == {expression!r}\n" + ) + with open(script, 'w') as f: + f.write(source) + assert_python_ok(script) + + @support.requires_resource('cpu') + def test_many_tstrings_in_module(self): + fields = ''.join(f'{{x{i}}}' for i in range(100)) + source = ''.join( + f"value_{i} = t'{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(fstring(namespace['value_0']), expected) + self.assertEqual(fstring(namespace['value_999']), expected) + def test_format_specifiers(self): # Test basic format specifiers value = 3.14159 @@ -88,6 +130,14 @@ def test_format_specifiers(self): ) self.assertEqual(fstring(t), "Pi: 3.14") + a = 3 + b = 4 + t = t"{a!=b:>10}" + self.assertTStringEqual( + t, ("", ""), [(a != b, "a!=b", None, ">10")] + ) + self.assertEqual(fstring(t), " 1") + def test_conversions(self): # Test !s conversion (str) obj = object() 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..9da3c38ce4691b1 --- /dev/null +++ b/Misc/NEWS.d/next/Core_and_Builtins/2026-09-01-07-15-20.gh-issue-155525.A7kP2m.rst @@ -0,0 +1,2 @@ +Fix quadratic-time tokenization of modules containing many f-strings or +t-strings. diff --git a/Parser/lexer/buffer.c b/Parser/lexer/buffer.c index e122fd0d9878ea2..4539a1dce6fd547 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->start_offset = mode->start == NULL ? -1 : mode->start - tok->buf; mode->multi_line_start_offset = mode->multi_line_start == NULL ? -1 : mode->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->start = mode->start_offset < 0 ? NULL : tok->buf + mode->start_offset; mode->multi_line_start = mode->multi_line_start_offset < 0 ? NULL : tok->buf + mode->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 b8fb29e98117f82..58cba8207757822 100644 --- a/Parser/lexer/lexer.c +++ b/Parser/lexer/lexer.c @@ -119,6 +119,10 @@ set_ftstring_expr(struct tok_state* tok, struct token *token, char c) { if (!(tok_mode->in_debug || tok_mode->string_kind == TSTRING) || 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 @@ -126,8 +130,8 @@ set_ftstring_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 == '\\') { @@ -163,7 +167,7 @@ set_ftstring_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; } @@ -174,16 +178,16 @@ set_ftstring_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]; // Copy escaped characters without interpreting the escaped // character as a quote or comment marker. if (ch == '\\') { result[j++] = ch; i++; - if (i < tok_mode->last_expr_size - tok_mode->last_expr_end) { - result[j++] = tok_mode->last_expr_buffer[i]; + if (i < expression_size) { + result[j++] = expression[i]; } } // Handle string quotes @@ -199,11 +203,11 @@ set_ftstring_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'; } } @@ -219,8 +223,8 @@ set_ftstring_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 ); } @@ -232,61 +236,6 @@ set_ftstring_expr(struct tok_state* tok, struct token *token, char c) { return 0; } -int -_PyLexer_update_ftstring_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) { @@ -1103,9 +1052,8 @@ tok_get_normal_mode(struct tok_state *tok, tokenizer_mode* current_tok, struct t the_current_tok->first_line = tok->lineno; the_current_tok->start_offset = -1; the_current_tok->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->in_debug = 0; @@ -1270,9 +1218,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->in_debug || in_format_spec); int cursor_valid = cursor == 0 || cursor_in_format_with_debug; - if ((cursor_valid) && !_PyLexer_update_ftstring_expr(tok, c)) { - return MAKE_TOKEN(ENDMARKER); - } if ((cursor_valid) && c != '{' && set_ftstring_expr(tok, token, c)) { return MAKE_TOKEN(ERRORTOKEN); } @@ -1416,6 +1361,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++; @@ -1440,13 +1388,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--; @@ -1531,12 +1472,10 @@ tok_get_fstring_mode(struct tok_state *tok, tokenizer_mode* current_tok, struct } if (c == '{') { - if (!_PyLexer_update_ftstring_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 1d97ac57b745b09..73781eaa60cea88 100644 --- a/Parser/lexer/lexer.h +++ b/Parser/lexer/lexer.h @@ -3,8 +3,6 @@ #include "state.h" -int _PyLexer_update_ftstring_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 5cf9b4d768c3ebb..d74e2c4501bcc97 100644 --- a/Parser/lexer/state.c +++ b/Parser/lexer/state.c @@ -66,24 +66,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) @@ -105,7 +87,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 9cd196a114c7cb1..43e2ef11da68097 100644 --- a/Parser/lexer/state.h +++ b/Parser/lexer/state.h @@ -61,9 +61,10 @@ typedef struct _tokenizer_mode { Py_ssize_t start_offset; Py_ssize_t 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 in_debug; int in_format_spec; diff --git a/Parser/tokenizer/file_tokenizer.c b/Parser/tokenizer/file_tokenizer.c index a11702557a07af3..bfef284a3b5a760 100644 --- a/Parser/tokenizer/file_tokenizer.c +++ b/Parser/tokenizer/file_tokenizer.c @@ -240,7 +240,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); @@ -275,9 +275,6 @@ tok_underflow_interactive(struct tok_state *tok) { return 0; } - if (tok->tok_mode_stack_index && !_PyLexer_update_ftstring_expr(tok, 0)) { - return 0; - } return 1; } @@ -328,10 +325,6 @@ tok_underflow_file(struct tok_state *tok) tok->implicit_newline = 1; } - if (tok->tok_mode_stack_index && !_PyLexer_update_ftstring_expr(tok, 0)) { - return 0; - } - ADVANCE_LINENO(); if (tok->decoding_state != STATE_NORMAL) { if (!_PyTokenizer_check_coding_spec(tok->cur, strlen(tok->cur), diff --git a/Parser/tokenizer/readline_tokenizer.c b/Parser/tokenizer/readline_tokenizer.c index 917f7b40cfbbfed..84aeeefa129c669 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_ftstring_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]
