Skip to content

RecursionError during copy.deepcopy of an ast-tree with parent references #120108

Closed
@15r10nk

Description

@15r10nk

Bug report

Bug description:

python 3.13 raises an RecursionError when I try to deepcopy the ast in the following example.

import ast
import copy

code="""
('',)
while i < n:
    if ch == '':
        ch = format[i]
        if ch == '':
            if freplace is None:
                '' % getattr(object)
        elif ch == '':
            if zreplace is None:
                if hasattr:
                    offset = object.utcoffset()
                    if offset is not None:
                        if offset.days < 0:
                            offset = -offset
                        h = divmod(timedelta(hours=0))
                        if u:
                            zreplace = '' % (sign,)
                        elif s:
                            zreplace = '' % (sign,)
                        else:
                            zreplace = '' % (sign,)
        elif ch == '':
            if Zreplace is None:
                Zreplace = ''
                if hasattr(object):
                    s = object.tzname()
                    if s is not None:
                        Zreplace = s.replace('')
            newformat.append(Zreplace)
        else:
            push('')
    else:
        push(ch)

"""



tree=ast.parse(code)

# add a back reference to the parent node
for node in ast.walk(tree):
    for child in ast.iter_child_nodes(node):
        child.parent=node

tree2=copy.deepcopy(tree)

output (Python 3.13.0b1+):

Traceback (most recent call last):
  File "/home/frank/projects/cpython/../cpython_bugs/deep_copy_ast_with_parents.py", line 50, in <module>
    tree2=copy.deepcopy(tree)
  File "/home/frank/projects/cpython/Lib/copy.py", line 162, in deepcopy
    y = _reconstruct(x, memo, *rv)
  File "/home/frank/projects/cpython/Lib/copy.py", line 253, in _reconstruct
    y = func(*args)
  File "/home/frank/projects/cpython/Lib/copy.py", line 252, in <genexpr>
    args = (deepcopy(arg, memo) for arg in args)
            ~~~~~~~~^^^^^^^^^^^
  File "/home/frank/projects/cpython/Lib/copy.py", line 136, in deepcopy
    y = copier(x, memo)
  File "/home/frank/projects/cpython/Lib/copy.py", line 196, in _deepcopy_list
    append(deepcopy(a, memo))
           ~~~~~~~~^^^^^^^^^
...

  File "/home/frank/projects/cpython/Lib/copy.py", line 162, in deepcopy
    y = _reconstruct(x, memo, *rv)
  File "/home/frank/projects/cpython/Lib/copy.py", line 259, in _reconstruct
    state = deepcopy(state, memo)
  File "/home/frank/projects/cpython/Lib/copy.py", line 136, in deepcopy
    y = copier(x, memo)
  File "/home/frank/projects/cpython/Lib/copy.py", line 221, in _deepcopy_dict
    y[deepcopy(key, memo)] = deepcopy(value, memo)
                             ~~~~~~~~^^^^^^^^^^^^^
  File "/home/frank/projects/cpython/Lib/copy.py", line 162, in deepcopy
    y = _reconstruct(x, memo, *rv)
  File "/home/frank/projects/cpython/Lib/copy.py", line 253, in _reconstruct
    y = func(*args)
  File "/home/frank/projects/cpython/Lib/copy.py", line 252, in <genexpr>
    args = (deepcopy(arg, memo) for arg in args)
            ~~~~~~~~^^^^^^^^^^^
  File "/home/frank/projects/cpython/Lib/copy.py", line 136, in deepcopy
    y = copier(x, memo)
RecursionError: maximum recursion depth exceeded

The problem can be reproduced on the current main (5c02ea8)

I was able to bisect the problem down to ed4dfd8 (@JelleZijlstra may be you know more here)

The code in the example looks big but is already minimized.

I hope that this example is simple enough to find and fix the bug, I can try to find a smaller one if it is needed.

CPython versions tested on:

3.13, CPython main branch

Operating systems tested on:

No response

Linked PRs

Metadata

Metadata

Assignees

No one assigned

    Labels

    3.13bugs and security fixes3.14bugs and security fixestype-bugAn unexpected behavior, bug, or error

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions