Ben Usman Ben Usman - 4 days ago 4
Python Question

__deepcopy__ object with cyclic references

from copy import deepcopy

class DoubleLinkedListNeedsDeepCopy:
def __init__(self, val, tail=None):
self.val = val
self._next_node = None
self._tail = tail or self

def append(self, new_val):
next_node = type(self)(new_val, self._tail)
self._next_node = next_node
return next_node

def __deepcopy__(self, memo):
new_copy = type(self)(self.val)
new_copy._next_node = deepcopy(self._next_node, memo)
new_copy._tail = deepcopy(self._tail, memo)
return new_copy

@property
def next(self):
return self._next_node

@property
def tail(self):
return self._tail

@property
def is_last(self):
return self._next_node == None

linked_list = head = DoubleLinkedListNeedsDeepCopy(1)
for i in range(2, 5):
head = head.append(i)

def print_list(linked_list):
cur = linked_list
for i in range(20):
print(cur.val, end=' ')

if cur.is_last:
break
else:
cur = cur.next
print()

import sys
sys.setrecursionlimit(10000)

print_list(linked_list)
linked_list.next.next.val = 5
print_list(linked_list)
list_copy = deepcopy(linked_list)
list_copy.next.next.val = 8
print_list(list_copy)
print_list(linked_list)


Expected output is:

1 2 3 4
1 2 5 4
1 2 8 4
1 2 5 4


However it fails with
RecursionError
after following a recursive path:
linked_list.next.next.next.tail.next.next.next...


(that is of course a toy example, I need a complicated tree-like structure to be copied in real-life scenario)

Answer

It turned out that in most cases (if you don't need to explicitly exclude certain fields from your copy), you can just do deepcopy(obj) even if obj has self-links or other else nasty properties.

Comments