https://github.com/python/cpython/commit/ac86e12d747dacd7008cd55691b2944aaae3e6b1
commit: ac86e12d747dacd7008cd55691b2944aaae3e6b1
branch: main
author: Pablo Galindo Salgado <[email protected]>
committer: pablogsal <[email protected]>
date: 2026-09-14T11:41:14-04:00
summary:
gh-153568: Stop re-walking memo lists when growing left-recursive rules
(#153574)
The left-recursion driver now keeps a direct reference to its memo
entry and updates it in place on every iteration.
files:
A
Misc/NEWS.d/next/Core_and_Builtins/2026-07-11-14-59-17.gh-issue-153568.leftrec.rst
M Parser/parser.c
M Parser/pegen.c
M Parser/pegen.h
M Tools/peg_generator/pegen/c_generator.py
diff --git
a/Misc/NEWS.d/next/Core_and_Builtins/2026-07-11-14-59-17.gh-issue-153568.leftrec.rst
b/Misc/NEWS.d/next/Core_and_Builtins/2026-07-11-14-59-17.gh-issue-153568.leftrec.rst
new file mode 100644
index 000000000000000..8302aae4cb8ca2a
--- /dev/null
+++
b/Misc/NEWS.d/next/Core_and_Builtins/2026-07-11-14-59-17.gh-issue-153568.leftrec.rst
@@ -0,0 +1,2 @@
+Speed up parsing of left-recursive rules by updating their memoization
+entries in place.
diff --git a/Parser/parser.c b/Parser/parser.c
index 800db5b490fea98..71cee7c00d4103f 100644
--- a/Parser/parser.c
+++ b/Parser/parser.c
@@ -4204,12 +4204,14 @@ dotted_name_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, dotted_name_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_0 = _PyPegen_update_memo(p, _mark, dotted_name_type, _res);
- if (tmpvar_0) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = dotted_name_raw(p);
if (p->error_indicator) {
@@ -9646,12 +9648,14 @@ attr_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, attr_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_1 = _PyPegen_update_memo(p, _mark, attr_type, _res);
- if (tmpvar_1) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = attr_raw(p);
if (p->error_indicator) {
@@ -13517,12 +13521,14 @@ bitwise_or_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, bitwise_or_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_2 = _PyPegen_update_memo(p, _mark, bitwise_or_type, _res);
- if (tmpvar_2) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = bitwise_or_raw(p);
if (p->error_indicator) {
@@ -13658,12 +13664,14 @@ bitwise_xor_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, bitwise_xor_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_3 = _PyPegen_update_memo(p, _mark, bitwise_xor_type, _res);
- if (tmpvar_3) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = bitwise_xor_raw(p);
if (p->error_indicator) {
@@ -13780,12 +13788,14 @@ bitwise_and_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, bitwise_and_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_4 = _PyPegen_update_memo(p, _mark, bitwise_and_type, _res);
- if (tmpvar_4) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = bitwise_and_raw(p);
if (p->error_indicator) {
@@ -13921,12 +13931,14 @@ shift_expr_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, shift_expr_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_5 = _PyPegen_update_memo(p, _mark, shift_expr_type, _res);
- if (tmpvar_5) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = shift_expr_raw(p);
if (p->error_indicator) {
@@ -14082,12 +14094,14 @@ sum_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, sum_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_6 = _PyPegen_update_memo(p, _mark, sum_type, _res);
- if (tmpvar_6) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = sum_raw(p);
if (p->error_indicator) {
@@ -14268,12 +14282,14 @@ term_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, term_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_7 = _PyPegen_update_memo(p, _mark, term_type, _res);
- if (tmpvar_7) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = term_raw(p);
if (p->error_indicator) {
@@ -14904,12 +14920,14 @@ primary_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, primary_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_8 = _PyPegen_update_memo(p, _mark, primary_type, _res);
- if (tmpvar_8) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = primary_raw(p);
if (p->error_indicator) {
@@ -20067,12 +20085,14 @@ t_primary_rule(Parser *p)
}
int _mark = p->mark;
int _resmark = p->mark;
+ Memo *_memo = _PyPegen_insert_memo_direct(p, _mark, t_primary_type);
+ if (_memo == NULL) {
+ p->level--;
+ return NULL;
+ }
while (1) {
- int tmpvar_9 = _PyPegen_update_memo(p, _mark, t_primary_type, _res);
- if (tmpvar_9) {
- p->level--;
- return _res;
- }
+ _memo->node = _res;
+ _memo->mark = p->mark;
p->mark = _mark;
void *_raw = t_primary_raw(p);
if (p->error_indicator) {
diff --git a/Parser/pegen.c b/Parser/pegen.c
index e709031ae781598..003c505de0c4a2d 100644
--- a/Parser/pegen.c
+++ b/Parser/pegen.c
@@ -102,6 +102,17 @@ _PyPegen_insert_memo(Parser *p, int mark, int type, void
*node)
return 0;
}
+// Like _PyPegen_insert_memo(), but returns the inserted Memo so callers
+// can update it in place without re-walking the token's memo list.
+Memo *
+_PyPegen_insert_memo_direct(Parser *p, int mark, int type)
+{
+ if (_PyPegen_insert_memo(p, mark, type, NULL) < 0) {
+ return NULL;
+ }
+ return p->tokens[mark]->memo;
+}
+
// Like _PyPegen_insert_memo(), but updates an existing node if found.
int
_PyPegen_update_memo(Parser *p, int mark, int type, void *node)
diff --git a/Parser/pegen.h b/Parser/pegen.h
index 5ebf6aded852787..308fb0d62974097 100644
--- a/Parser/pegen.h
+++ b/Parser/pegen.h
@@ -148,6 +148,7 @@ PyObject *_PyPegen_get_memo_statistics(void);
int _PyPegen_insert_memo(Parser *p, int mark, int type, void *node);
int _PyPegen_update_memo(Parser *p, int mark, int type, void *node);
+Memo *_PyPegen_insert_memo_direct(Parser *p, int mark, int type);
int _PyPegen_is_memoized(Parser *p, int type, void *pres);
int _PyPegen_lookahead(int, void *(func)(Parser *), Parser *);
diff --git a/Tools/peg_generator/pegen/c_generator.py
b/Tools/peg_generator/pegen/c_generator.py
index d9236dfb22835bd..812dd4a19d82f7b 100644
--- a/Tools/peg_generator/pegen/c_generator.py
+++ b/Tools/peg_generator/pegen/c_generator.py
@@ -572,11 +572,15 @@ def _set_up_rule_memoization(self, node: Rule,
result_type: str) -> None:
self.print("}")
self.print("int _mark = p->mark;")
self.print("int _resmark = p->mark;")
+ self.print(f"Memo *_memo = _PyPegen_insert_memo_direct(p, _mark,
{node.name}_type);")
+ self.print("if (_memo == NULL) {")
+ with self.indent():
+ self.add_return("NULL")
+ self.print("}")
self.print("while (1) {")
with self.indent():
- self.call_with_errorcheck_return(
- f"_PyPegen_update_memo(p, _mark, {node.name}_type, _res)",
"_res"
- )
+ self.print("_memo->node = _res;")
+ self.print("_memo->mark = p->mark;")
self.print("p->mark = _mark;")
self.print(f"void *_raw = {node.name}_raw(p);")
self.print("if (p->error_indicator) {")
_______________________________________________
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]
