Ordered destruction and object graph traversal

[Jeff Clites]

As mentioned in a previous post, I've been working on getting ordered 
destruction working. I actually have a mostly-working version of this 
now, which will merit its own discussion, but there's a particular 
aspect which I wanted to call out in light of Dan's recent post on 
"Object freezing".

A key aspect of getting destruction-ordering right is doing an object 
graph traversal to determine which objects are reachable from objects 
which need to have their vtable->destroy() methods called--these 
objects can't safely go away until these destroy's have been called. 
This amounts to doing exactly what trace_children() does, except that 
(1) you start with a different base set of objects to trace out from, 
and (2) you need to set a different flag on the objects you reach.

For PMC's with custom vtable->mark() methods, this posed a 
problem--that method sets the live flag, but now I needed to repeat 
that logic almost exactly, but setting a different flag. Hmm--that was 
telling me something, namely that we needed to generalize. In 
particular, what was needed in both cases was simply a way to find out 
what other objects are referenced by a particular object.

Since this is to be used in the middle of a DOD run, I thought it 
crucial that this not require the allocation of additional memory 
(which rules out an iterator object or method which returns something 
like a flat array of referenced objects).

My solution was to define a new vtable method--I've called it visit(), 
though the name's not the important part--to which you pass a callback 
(plus an optional context argument). It's job is to invoke that 
callback on each of it's referenced "children" (also passing the 
context object with each invocation), and that's it. The PMC doesn't 
know or care what the callback does--in a GC context the callback may 
set a flag on what's passed in and stash it for later processing; in 
another context it may be used inside of an iterator which vends out 
objects one-by-one and guards against loops.

With this method, you end up not needing vtable->mark() -- all you need 
to do is call vtable->visit() and pass it a callback which wraps 
pobject_lives(). To do the destruction ordering which I need, you pass 
it a different callback, which sets a different flag. And finally (the 
reason I bring this up now), I expect that this method will serve as 
the primitive which a vtable->traverse() implementation would leverage.

To be clear, this vtable->visit() isn't an object traversal 
method--it's a tell-me-what-you-directly-point-to method, and often a 
building block for traversal strategies or for iterator 
implementations. I'm fairly convinced that a separate vtable->mark() is 
unnecessary; at most, I'd say that the default implementation (which 
calls visit() to do its work) would rarely need to be overridden. 
Similarly for vtable->traverse(), although it's too soon to tell for 
sure.

Again, I'm bringing this up now so that anyone diving into freeze/thaw 
or traversal can leverage the work/thought I've put into this so far. 
(I have some other thoughts on how to do traversals, but I'll save 
those for another post.)

(My ordered-destruction implementation not quite ready for general 
consumption yet--there are quite a few existing PMCs with custom mark 
methods which need to be converted to custom visit methods. It's 
straightforward to do but is taking a bit of time, and I want to finish 
that before submitting this to make sure that I haven't overlooked 
anything. All you really have to do to turn a mark() method into a 
visit() method is change the prototype and change the call to 
pobject_lives into a call to the callback.)

JEff