Re: BlockClosure>>deepCopy recursion error

"Chris Uppal" <chris.uppal@xxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message news:44f465fe$0$640$bed64819@xxxxxxxxxxxxxxxxxxxx
Udo, Jose

I assume that some cyclic "stuff" is going on there (Smalltalk at:
#Smalltalk = Smalltalk) which leads to recursion.

It's still a bit odd, though. The default #deepCopy implementation allows for
cycles.

d := LookupTable new.
d at: #D put: d.
d deepCopy

Which works fine.

On D5:

Smalltalk deepCopy

whirs for a second or two but completes normally. On D6 we get a stack
overflow. I wonder whether it's just a coincidental difference in the layouts
of the two dictionaries, or whether D6 runs with less stack space by default
(or, conversely, uses more stack space per call).

Actually its not due to any fundamental difference between D5 and D6, but something much simpler. Well perhaps not simpler, but less sinister.

It's because of a flaw in #deepCopy, also present in D5 but it doesn't show up in normal use. The issue arises when an object has an implementation of #postCopy that copies subcomponents and those subcomponents have a backpointer to the parent where that parent pointer is correctly updated to point to the new copy. An example is StMethodNode. This contains a sequence of statement nodes held in an StSequenceNode. It StMethodNode implements #postCopy to copy the StSequenceNode it contains, and sets this as its body through its #body: accessor. This in turn instructs the new StSequenceNode of its method which the sequence node stores in a parent backpointer. The result is that the method node copy has a sequence node copy that points back to the method node copy. This is correct, but it breaks #_deepCopy:, because the deep copy algorithm guards against recursion by inserting only the original object that it is currently copying into the "visited" dictionary. It then goes and expands the shallow copied/post copied clone. If it turns out that the object graph below the clone has already had references updated to point to the clone, then an infinite recursion can result because it will keep expanding the clone. It's probably easier to debug through copying an StMethodNode to understand what is going on than it is to try and explain/understand it in words, e.g.

(Object parseTreeFor: #deepCopy) deepCopy

Now this can be fixed by modifying #_deepCopy: to also insert the newly cloned object into the trail dictionary before deepening the copy as below. I've partially convinced myself that this is a general solution to the problem, and it does allow "Smalltalk deepCopy" to complete. Of course it makes #deepCopy even slower, but frankly I'm not too concerned about that because its not really a sensible idea to use #deepCopy anyway.

Regards

OA

-----------------
!Object methodsFor!

_deepCopy: copiesDictionary
"Private - Answer a 'deep copy' of the receiver, cloning only those parts not already included
in the IdentityDictionary argument, copiesDictionary. This method implements the
body of #deepCopy, and is sufficient for all objects except those holding external
resources (where that resource should probably be cloned too), and those where there
are circular references from an object to a child and vice versa, and that reference must be
correctly maintained. In general you should override #deepenShallowCopies:trail: as that
is easier."

^copiesDictionary at: self
ifAbsent:
[| clone |
clone := self shallowCopy postCopy.
copiesDictionary at: self put: clone.
(clone == self or: [self class isBytes])
ifTrue: [clone "no further copying required"]
ifFalse:
[copiesDictionary at: clone put: clone.
self _deepenShallowCopy: clone trail: copiesDictionary]]! !
!Object categoriesFor: #_deepCopy:!copying!private! !




.

Relevant Pages

  • Re: Semi-newbie, rolling my own __deepcopy__
    ... But I now have succeeded in making deepcopy work for a simple class ... print "clone, should be deepcopy of foo:", clone.show ... from array import array ... bundled into a dictionary with numerics first, ...
    (comp.lang.python)
  • Re: More On - deepcopy, Tkinter
    ... called to implement the shallow copy operation; ... So, if you have a class with attributes a, b, and c, and you want to ensure that deepcopy copies a and b, but doesn't copy c, I guess you could do ... As you can see, the deepcopy only creates deep copies of 2 of the 3 attributes, 'c' is simply copied across as a shallow copy. ...
    (comp.lang.python)
  • Re: deep copy quesiton
    ... > class Type1 implements deepCopy ... > public Object createDeepCopy() ... Using clone() in place of ... > Method1. ...
    (comp.lang.java.programmer)
  • Re: More On - deepcopy, Tkinter
    ... > called to implement the shallow copy operation; ... it should call the deepcopy() function with the component ... return clone ... the deepcopy only creates deep copies of 2 of the 3 ...
    (comp.lang.python)
  • Re: BlockClosure>>deepCopy recursion error
    ... I assume this is independent of BlockClosure as "Smalltalk deepCopy" has the same effect. ... #Smalltalk = Smalltalk) which leads to recursion. ... For editing purposes we are making a deep copy of the collection that holds all those objects. ...
    (comp.lang.smalltalk.dolphin)