BlockClosure>>deepCopy recursion error

Hi!

Which is the problem behind this piece of code on Dolphin 6?

(Compiler evaluate: '[:c | Smalltalk]') deepCopy

#deepCopy implementation in BlockClosure or not enough space in the stack??

Cheers
Jose Sebastian Calvo

Jose Sebastian Calvo wrote:
> #deepCopy implementation in BlockClosure or not enough space in the stack??
I assume this is independent of BlockClosure as "Smalltalk deepCopy" has
the same effect.

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

Just out of interest ... why do you want to make a deep copy of the
SystemDictionary?

CU,

Udo

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).

    -- chris

Udo Schneider escribió:
> Jose Sebastian Calvo wrote:
>> #deepCopy implementation in BlockClosure or not enough space in the
>> stack??
> I assume this is independent of BlockClosure as "Smalltalk deepCopy" has
> the same effect.

Yes, you are right
>
> I assume that some cyclic "stuff" is going on there (Smalltalk at:
> #Smalltalk = Smalltalk) which leads to recursion.
>
> Just out of interest ... why do you want to make a deep copy of the
> SystemDictionary?

Why not? :D
We have some stuff that works with many user defined blocks. For editing
purposes (buffering) we are making a deep copy of the collection that
holds all those objects. We should use a more specialized mechanism here
but already is implemented using #deepCopy. I think it is a bad
implementation but, as Chris says, #deepCopy should respond consistently
as for any other Dictionary.

Cheers
Jose Sebastian Calvo
>
> CU,
>
> Udo

Jose Sebastian Calvo wrote:
> Why not? :D
> We have some stuff that works with many user defined blocks. For editing
> purposes (buffering) we are making a deep copy of the collection that
> holds all those objects. We should use a more specialized mechanism here
> but already is implemented using #deepCopy. I think it is a bad
> implementation but, as Chris says, #deepCopy should respond consistently
> as for any other Dictionary.
Understood. Although taking SystemDictionary as your toy might have been
"suboptimal". :-)

As Chris pointed out LookupTable just works fine (even with circular
references) and the same is true for Dictionary (checked it).

CI,

Udo

"Chris Uppal" <[hidden email]> wrote in message
news:44f465fe$0$640$[hidden email]...
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! !

Support at Object Arts wrote:

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

Is there any significance in the fact that the resulting stack overflow (in D6)
isn't debuggable from the walkback, although stack overflows normally don't
cause problems ?   (That's the stack overflow from copying Smalltalk or:
    (Object parseTreeFor: #deepCopy) deepCopy
).


> It's because of a flaw in #deepCopy, also present in D5 but it doesn't
> show up in normal use.

Thanks for the explanation.  For what little it's worth I agree with your
proposed fix.

It doesn't fix all the problems with #deepCopy though.  I managed to find a
class of my own which has back-pointers and supports a copy operation, and
wondered how it would respond to the fix.  It turns out that although #copy
works fine, and preserves the integrity of the back-pointers, #deepCopy (new or
old version) breaks.  The way I have #postCopy implemented is something like:

    postCopy
        parent := nil.    "will be reinstated by parent"
        children := children collect: [:each | each copy].
        children do: [:each | each beChildOf: self].

That has the effect of orphaning the root of any #copy operation -- which is
correct for this application since it is not legal for a node to have a parent
which doesn't "know" about it. Both implementations of #deepCopy cause this to
fail, since the second invocation of #postCopy via #_deepenShallowCopy:trail:
replaces the already-copied children with new ones which have no parent, and
the parent never is given a chance to fix them up.

I don't know whether you would consider that a problem in the #deepCopy
framework. And, even if you do, I don't see a simple solution.  For now, since
I've noticed this issue, I've just overridden #deepCopy on the objects in
question to answer #copy, since that is already as deep a copy as is
appropriate.

    -- chris

"Chris Uppal" <[hidden email]> wrote in message
news:44fff01e$0$635$[hidden email]...
This is a general problem in D6. I suspect it doesn't allow enough headroom
on the stack above the "high water" mark to allow the debugger to open when
running in the context of that process. The workaround is to use the Process
Monitor (or some other way of locating the process) to open a debugger on
it. Since this runs up the debugger in the context of another process (the
new main process) it will work.

>
>> It's because of a flaw in #deepCopy, also present in D5 but it doesn't
>> show up in normal use.
>
> Thanks for the explanation.  For what little it's worth I agree with your
> proposed fix.
>
> It doesn't fix all the problems with #deepCopy though.... [snip]....

One problem here is with the overloaded use of #postCopy. The deepCopy
framework assumes it just tidies up, rather than actually deepens the copy.
As it turns out #postCopy is routinely used to deepen the copy. In the early
days of Dolphin (when the deepCopy implementation was designed) we only
every used it to clean up references to external resources, etc, but this
wasn't really the established meaning. Even if that were addressed, there
would still be cases where the generic approach doesn't create the right
result, and so specialised deepCopy overrides are needed. As I said though,
I think the provision of a #deepCopy is a fundamentally flawed concept,
because it can very easily degenerate into copying the entire world,
especially as objects get modified over time to include new instance
variables. I would suggest avoiding it altogether.

Regards

OA