Pegen improperly memoizes loop rules

Bug report

In the following part of pegen, the memoized result is only used if self._should_memoize(node) is true. Since loop rules are autogenerated, they are not marked with (memo), so this is always false. Despite that, in the end the result is memoized based on the different condition if node.name. Because of that, in the generated parser loop rules' results are always stored in the cache, but never accessed later.

cpython/Tools/peg_generator/pegen/c_generator.py

Lines 608 to 647 in 8de59c1

    
           def _handle_loop_rule_body(self, node: Rule, rhs: Rhs) -> None: 
        
               memoize = self._should_memoize(node) 
        
               is_repeat1 = node.name.startswith("_loop1") 
        
               with self.indent(): 
        
                   self.add_level() 
        
                   self._check_for_errors() 
        
                   self.print("void *_res = NULL;") 
        
                   if memoize: 
        
                       self.print(f"if (_PyPegen_is_memoized(p, {node.name}_type, &_res)) {{") 
        
                       with self.indent(): 
        
                           self.add_return("_res") 
        
                       self.print("}") 
        
                   self.print("int _mark = p->mark;") 
        
                   self.print("int _start_mark = p->mark;") 
        
                   self.print("void **_children = PyMem_Malloc(sizeof(void *));") 
        
                   self.out_of_memory_return(f"!_children") 
        
                   self.print("Py_ssize_t _children_capacity = 1;") 
        
                   self.print("Py_ssize_t _n = 0;") 
        
                   if any(alt.action and "EXTRA" in alt.action for alt in rhs.alts): 
        
                       self._set_up_token_start_metadata_extraction() 
        
                   self.visit( 
        
                       rhs, 
        
                       is_loop=True, 
        
                       is_gather=node.is_gather(), 
        
                       rulename=node.name, 
        
                   ) 
        
                   if is_repeat1: 
        
                       self.print("if (_n == 0 || p->error_indicator) {") 
        
                       with self.indent(): 
        
                           self.print("PyMem_Free(_children);") 
        
                           self.add_return("NULL") 
        
                       self.print("}") 
        
                   self.print("asdl_seq *_seq = (asdl_seq*)_Py_asdl_generic_seq_new(_n, p->arena);") 
        
                   self.out_of_memory_return(f"!_seq", cleanup_code="PyMem_Free(_children);") 
        
                   self.print("for (int i = 0; i < _n; i++) asdl_seq_SET_UNTYPED(_seq, i, _children[i]);") 
        
                   self.print("PyMem_Free(_children);") 
        
                   if node.name: 
        
                       self.print(f"_PyPegen_insert_memo(p, _start_mark, {node.name}_type, _seq);") 
        
                   self.add_return("_seq")

Your environment

Does not matter - discovered through manual code analysis

Linked PRs

@pablogsal

cc @pablogsal

@abel1502

Thanks for the report @abel1502 and @sobolevn for the ping!

Opened #102467

gh-102416: Do not memoize incorrectly loop rules in the parser (#102467)

[3.11] pythongh-102416: Do not memoize incorrectly loop rules in the …

[3.10] pythongh-102416: Do not memoize incorrectly loop rules in the …

[3.10] gh-102416: Do not memoize incorrectly loop rules in the parser (…

[3.11] gh-102416: Do not memoize incorrectly loop rules in the parser (…

Merge branch 'main' into nodeaddict

Merge branch 'main' into inlinecomp2

Navigation Menu

Repository navigation

Pegen improperly memoizes loop rules #102416

Bug report

Your environment

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	def _handle_loop_rule_body(self, node: Rule, rhs: Rhs) -> None:
	memoize = self._should_memoize(node)
	is_repeat1 = node.name.startswith("_loop1")

	with self.indent():
	self.add_level()
	self._check_for_errors()
	self.print("void *_res = NULL;")
	if memoize:
	self.print(f"if (_PyPegen_is_memoized(p, {node.name}_type, &_res)) {{")
	with self.indent():
	self.add_return("_res")
	self.print("}")
	self.print("int _mark = p->mark;")
	self.print("int _start_mark = p->mark;")
	self.print("void *_children = PyMem_Malloc(sizeof(void ));")
	self.out_of_memory_return(f"!_children")
	self.print("Py_ssize_t _children_capacity = 1;")
	self.print("Py_ssize_t _n = 0;")
	if any(alt.action and "EXTRA" in alt.action for alt in rhs.alts):
	self._set_up_token_start_metadata_extraction()
	self.visit(
	rhs,
	is_loop=True,
	is_gather=node.is_gather(),
	rulename=node.name,
	)
	if is_repeat1:
	self.print("if (_n == 0 \|\| p->error_indicator) {")
	with self.indent():
	self.print("PyMem_Free(_children);")
	self.add_return("NULL")
	self.print("}")
	self.print("asdl_seq _seq = (asdl_seq)_Py_asdl_generic_seq_new(_n, p->arena);")
	self.out_of_memory_return(f"!_seq", cleanup_code="PyMem_Free(_children);")
	self.print("for (int i = 0; i < _n; i++) asdl_seq_SET_UNTYPED(_seq, i, _children[i]);")
	self.print("PyMem_Free(_children);")
	if node.name:
	self.print(f"_PyPegen_insert_memo(p, _start_mark, {node.name}_type, _seq);")
	self.add_return("_seq")

Pegen improperly memoizes loop rules #102416

Description

Bug report

Your environment

Linked PRs

Activity

sobolevn commented on Mar 4, 2023

pablogsal commented on Mar 6, 2023

pablogsal commented on Mar 6, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions