Deep copy and recursive references

Quick one about coding a deep copy and avoiding recursive references…

Let’s say we have an instance a which has a reference to an instance b and we have to do a deep copy of a. To do this, we need a deep copy of b as well.

But let’s say b had a reference back to a.

Here it is in Python (I know Python has its own __deepcopy__() method but the below is for illustrative purposes).

class A:                                                                                                                                                                                                            
    def __init__(self,b=None):
        self.b=b
    def deepcopy(self):
        newA=A()
        newA.b=self.b.deepcopy()
        return newA
class B:
    def __init__(self,a=None):
        self.a=a
    def deepcopy(self):
        newB=B()
        newB.a=self.a.deepcopy()
        return newB

class A:                                                                                                                                                                                                            
    def __init__(self,b=None):
        self.b=b
    def deepcopy(self):
        newA=A()
        newA.b=self.b.deepcopy()
        return newA
class B:
    def __init__(self,a=None):
        self.a=a
    def deepcopy(self):
        newB=B()
        newB.a=self.a.deepcopy()
        return newB

Now let’s execute this:

>>> a=A()
>>> b=B()
>>> a.b=b
>>> b.a=a
>>> newA=a.deepcopy()

>>> a=A()
>>> b=B()
>>> a.b=b
>>> b.a=a
>>> newA=a.deepcopy()

What happens? Not pretty – a recursion limit error.

To fix this, we can keep track in a as to whether that instance has already created a copy of itself, so when it is called back from b it can just return that instance. This is sometimes called the “memo” copy. See amended code below.

class A:                                                                                                                                                                                                            
    def __init__(self,b=None):
        self.b=b
        self.memo=None
    def deepcopy(self):
        if self.memo==None:
            newA=A()
            self.memo=newA
            newA.b=self.b.deepcopy()
            self.memo=None
            return newA
        else:
            return self.memo
class B:
    def __init__(self,a=None):
        self.a=a
    def deepcopy(self):
        newB=B()
        newB.a=self.a.deepcopy()
        return newB

class A:                                                                                                                                                                                                            
    def __init__(self,b=None):
        self.b=b
        self.memo=None
    def deepcopy(self):
        if self.memo==None:
            newA=A()
            self.memo=newA
            newA.b=self.b.deepcopy()
            self.memo=None
            return newA
        else:
            return self.memo
class B:
    def __init__(self,a=None):
        self.a=a
    def deepcopy(self):
        newB=B()
        newB.a=self.a.deepcopy()
        return newB

Now when we execute:

>>> a=A()
>>> b=B()
>>> a.b=b
>>> b.a=a
>>> newA=a.deepcopy()
>>> newA
<__main__.A instance at 0x00D53A30>
>>> newA.b.a
<__main__.A instance at 0x00D53A30>
>>> newA2=a.deepcopy()
>>> newA2
<__main__.A instance at 0x00D53AF8>
>>> newA2.b.a
<__main__.A instance at 0x00D53AF8>
>>> 

>>> a=A()
>>> b=B()
>>> a.b=b
>>> b.a=a
>>> newA=a.deepcopy()
>>> newA
<__main__.A instance at 0x00D53A30>
>>> newA.b.a
<__main__.A instance at 0x00D53A30>
>>> newA2=a.deepcopy()
>>> newA2
<__main__.A instance at 0x00D53AF8>
>>> newA2.b.a
<__main__.A instance at 0x00D53AF8>
>>> 

Note that the memo is removed just before the copy is handed back so that if you call deepcopy again you’ll get a new copy of a.