[boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)

From: Chuck Messenger (chuckm_at_[hidden])
Date: 2003-05-30 10:56:08

Schoenborn, Oliver wrote:
>>From: Chuck Messenger [mailto:chuckm_at_[hidden]]
>>
>>>>No.  A and B are completely symmetrical.  They each equally 
>>>>"own" the other.
>>>
>>>
>>>Not possible. This has nothing to do with NoPtr or 
>>>boost::shared_ptr, it's even true for raw pointers. E.g.
>>>...
>>
>>Just look at my Node example -- you'll see that there is 
>>indeed complete symmetry of ownership.  There is a cyclic 
>>ownership graph -- hence the 
>>trouble with traditional smart pointers.
> 
> 
> ... Strict ownership means that only one object at any
> given time can be the owner. This is pretty straightforward and the raw
> pointer example shows that there is no such thing as cyclic strict ownership
> that works, at least within the above definition of ownership, 

Which is why the strict ownership paradigm doesn't work with cyclic 
structures.  Inherently, in the general case, cyclic structures 
*require* garbage collection (or to be more precise, some dynammic 
programming cycle-finding algorithm, whether or not you call it "garbage 
collection") to harvest stranded cycles of objects.

Yes, as Peter Dimov suggested, you can sort of "game" the problem by 
dividing your structures into Vertex and Edge types, allowing for a 
classic strict ownership hierarchy.  But that just leaves the garbage 
collection problem to the programmer.

What I'm trying to develop (or even better, find) is a workable C++ 
library which supports cyclic structures, handling garbage collection 
for you, without resorting to a systemic (and non-portable) approach 
like the Boehm collector.  I want to build regular-old, C++ standard 
libraries upon this cyclic library -- I don't want to require users of 
my libraries to use my garbage collection system.  It needs to be 
perfectly invisible to the user (and ideally, as invisible as possible 
to the library writer).

> and the
> common definition of cyclic (i.e. A uses B uses "the A that uses the B",
> where "uses" would be "owns" or "refers to", depending on your case). Not
> even a garbage collector could do it, because the gc is then an owner and
> you end up with shared ownership of A.

On the contrary, garbage collectors work fine with cyclic structures. 
Had I been using the Boehm collector, it would have found and freed my 
stranded cycle of objects, in the very example code I provided.

     - Chuck Messenger