Feasibility of automatic cycle breaker for `std::shared_ptr`
Question: C++11 introduced reference-counted smart pointers, `std::shared_ptr`. Being
reference counted, these pointers are unable to automatically reclaim cyclic
data structures. However, automatic collection of reference cycles was shown
to be possible, for example by [Python](http://arctrix.com/nas/python/gc/) and
[PHP](http://php.net/manual/en/features.gc.collecting-cycles.php). To
distinguish this technique from garbage collection, the rest of the question
will refer to it as _cycle breaking_.

Given that there seem to be no proposals to add equivalent functionality to
C++, is there a fundamental reason why a cycle breaker similar to the ones
already deployed in other languages wouldn't work for `std::shared_ptr`?

Note that this question doesn't boil down to "why isn't there a GC for C++",
which [has been asked before](http://stackoverflow.com/q/147130/1600898). A
C++ GC normally refers to a system that automatically manages _all_
dynamically allocated objects, typically implemented using some form of
Boehm's conservative collector. It has been [pointed
out](http://stackoverflow.com/a/19466425/1600898) that such a collector is not
a good match for RAII. Since a garbage collector primarily manages memory, and
might not even be called until there is a memory shortage, and C++ destructors
manage other resources, relying on the GC to run destructors would introduce
non-determinism at best and resource starvation at worst. It has also bee
pointed out that a full-blown GC is largely unnecessary in the presence of the
more explicit and predictable smart pointers.

However, a library-based cycle breaker for smart pointers (analogous to the
one used by reference-counted interpreters) would have important differences
from a general-purpose GC:

  * It only cares about objects managed through `shared_ptr`. Such objects _already_ participate in shared ownership, and thus have to handle delayed destructor invocation, whose exact timing depends on ownership structure.
  * Due to its limited scope, a cycle breaker is unconcerned with patterns that break or slow down Boehm GC, such as pointer masking or huge opaque heap blocks that contain an occasional pointer.
  * It can be opt-in, like `std::enable_shared_from_this`. Objects that don't use it don't have to pay for the additional space in the control block to hold the cycle breaker metadata.
  * A cycle breaker doesn't require a comprehensive list of "root" objects, which is hard to obtain in C++. Unlike a mark-sweep GC which finds all live objects and discards the rest, a cycle breaker only traverses objects that can form cycles. In existing implementations, the type needs to provide help in the form of a function that enumerates references (direct or indirect) to other objects that can participate in a cycle.
  * It relies on regular "destroy when reference count drops to zero" semantics to destroy cyclic garbage. Once a cycle is identified, the objects that participate in it are requested to clear their strongly-held references, for example by calling `reset()`. This is enough to break the cycle and would automatically destroy the objects. Asking the objects to provide and clear its strongly-held references (on request) makes sure that the cycle breaker does not break encapsulation.

Lack of proposals for automatic cycle breaking indicates that the idea was
rejected for practical or philosophical reasons. I am curious as what the
reasons are. For completeness, here are some possible objections:

  * "It would introduce non-deterministic destruction of cyclic `shared_ptr` objects." If the programmer were in control of the cycle breaker's invocation, it would not be non-deterministic. Also, once invoked, the cycle breaker's behavior would be predictable - it would destroy all currently known cycles. This is akin to how `shared_ptr` destructor destroys the underlying object once its reference count drops to zero, despite the possibility of this causing a "non-deterministic" cascade of further destructions.

  * "A cycle breaker, just like any other form of garbage collection, would introduce pauses in program execution." Experience with runtimes that implement this feature shows that the pauses are minimal because the GC only handles cyclic garbage, and all other objects are reclaimed by reference counting. If the cycle detector is never invoked automatically, the cycle breaker's "pause" could be a predictable consequence of running it, similar to how destroying a large `std::vector` might run a large number of destructors. (In Python, the cyclic gc is run automatically, but there is API to [disable it](https://docs.python.org/2/library/gc.html#gc.disable) temporarily in code sections where it is not needed. Re-enabling the GC later will pick up all cyclic garbage created in the meantime.)

  * "A cycle breaker is unnecessary because cycles are not that frequent and they can be easily avoided using `std::weak_ptr`." Cycles in fact turn up easily in many simple data structures - e.g. a tree where children have a back-pointer to the parent, or a doubly-linked list. In some cases, cycles between heterogenous objects in complex systems are formed only occasionally with certain patterns of data and are hard to predict and avoid. In some cases it is far from obvious which pointer to replace with the weak variant.


Answer: There are a number of issues to be discussed here, so I've rewritten my post
to better condense this information.

## Automatic cycle detection

Your idea is to have a `circle_ptr` smart pointer (I know you want to add it
to `shared_ptr`, but it's easier to talk about a new type to compare the two).
The idea is that, if the type that the smart pointer is bound to derives from
some `cycle_detector_mixin`, this activates automatic cycle detection.

This mixin also requires that the type implement an interface. It must provide
the ability to enumerate all of the `circle_ptr` instances directly owned by
that instance. And it must provide the means to invalidate one of them.

I submit that this is a highly impractical solution to this problem. It is
excessively fragile and requires immense amounts of manual work from the user.
And therefore, it is not appropriate for inclusion in the standard library.
And here are some reasons why.

### Determinism and cost

> "It would introduce non-deterministic destruction of cyclic `shared_ptr`
> objects." Cycle detection only happens when a `shared_ptr`'s reference count
> drops to zero, so the programmer is in control of when it happens. It would
> therefore not be non-deterministic. Its behavior would be predictable - it
> would destroy all currently known cycles from that pointer. This is akin to
> how `shared_ptr` destructor destroys the underlying object once its
> reference count drops to zero, despite the possibility of this causing a
> "non-deterministic" cascade of further destructions.

This is true, but not in a helpful way.

There is a substantial difference between the determinism of regular
`shared_ptr` destruction and the determinism of what you suggest. Namely:
`shared_ptr` is cheap.

`shared_ptr`'s destructor does an atomic decrement, followed by a conditional
test to see if the value was decremented to zero. If so, a destructor is
called and memory is freed. That's it.

What you suggest makes this more complicated. Worst-case, every time a
`circle_ptr` is destroyed, the code will have to walk through data structures
to determine if there's a cycle. Most of the time, cycles won't exist. But it
still has to look for them, just to make sure. And it must do so _every single
time_ you destroy a `circle_ptr`.

Python et. al. get around this problem because they are built into the
language. They are able to see _everything_ that's going on. And therefore,
they can detect when a pointer is assigned at the time those assignments are
made. In this way, such systems are constantly doing small amounts of work to
build up cyclic chains. Once a reference goes away, it can look at its data
structures and take action if that creates a cyclical chain.

But what you're suggesting is a _library feature_ , not a language feature.
And library types can't really do that. Or rather, they can, but only with
help.

Remember: an instance of `circle_ptr` cannot know the subobject it is a member
of. It cannot _automatically_ transform a pointer to itself into a pointer to
its owning class. And without that ability, it cannot update the data
structures in the `cycle_detector_mixin` that owns it if it is reassigned.

Now, it could _manually_ do this, but only with help from its owning instance.
Which means that `circle_ptr` would need a set of constructors that are given
a pointer to its owning instance, which derives from `cycle_detector_mixin`.
And then, its `operator=` would be able to inform its owner that it has been
updated. Obviously, the copy/move assignment would _not_ copy/move the owning
instance pointer.

Of course, this requires the owning instance to give a pointer to itself to
_every`circle_ptr`_ that it creates. In every constructor&function that
creates `circle_ptr` instances. Within itself and any classes it owns which
are not also managed by `cycle_detection_mixin`. Without fail. This creates a
degree of fragility in the system; manual effort must be expended for each
`circle_ptr` instance owned by a type.

This also requires that `circle_ptr` contain 3 pointer types: a pointer to the
object you get from `operator*`, a pointer to the actual managed storage, and
a pointer to that instance's owner. The reason that the instance must contain
a pointer to its owner is that it is per-instance data, not information
associated with the block itself. It is the instance of `circle_ptr` that
needs to be able to tell its owner when it is rebound, so the instance needs
that data.

And this must be _static_ overhead. You can't know when a `circle_ptr`
instance is within another type and when it isn't. So every `circle_ptr`, even
those that don't use the cycle detection features, must bear this 3 pointer
cost.

So not only does this require a large degree of fragility, it's also
expensive, bloating the type's size by 50%. Replacing `shared_ptr` with this
type (or more to the point, augmenting `shared_ptr` with this functionality)
is just not viable.

On the plus side, you no longer need users who derive from
`cycle_detector_mixin` to implement a way to fetch the list of `circle_ptr`
instances. Instead, you have the class register itself with the `circle_ptr`
instances. This allows `circle_ptr` instances that could be cyclic to talk
directly to their owning `cycle_detector_mixin`.

So there's something.

### Encapsulation and invariants

The need to be able to tell a class to invalidate one of its `circle_ptr`
objects fundamentally changes the way the class can interact with any of its
`circle_ptr` members.

An invariant is some state that a piece of code assumes is true because it
should be logically impossible for it to be false. If you check that a `const
int` variable is > 0, then you have established an invariant for later code
that this value is positive.

Encapsulation exists to allow you to be able to build invariants within a
class. Constructors alone can't do it, because external code could modify any
values that the class stores. Encapsulation allows you to prevent external
code from making such modifications. And therefore, you can develop invariants
for various data stored by the class.

This is what encapsulation is _for_.

With a `shared_ptr`, it is possible to build an invariant around the existence
of such a pointer. You can design your class so that the pointer is never
null. And therefore, nobody has to check for it being null.

That's not the case with `circle_ptr`. If you implement the
`cycle_detector_mixin`, then your code _must_ be able to handle the case of
any of those `circle_ptr` instances becoming null. Your destructor therefore
cannot assume that they are valid, nor can any code that your destructor calls
make that assumption.

Your class therefore _cannot_ establish an invariant with the object pointed
to by `circle_ptr`. At least, not if it's part of a `cycle_detector_mixin`
with its associated registration and whatnot.

You can argue that your design does not _technically_ break encapsulation,
since the `circle_ptr` instances can still be private. But the class is
willingly _giving up_ encapsulation to the cycle detection system. And
therefore, the class can no longer ensure certain kinds of invariants.

That sounds like breaking encapsulation to me.

### Thread safety

In order to access a `weak_ptr`, the user must `lock` it. This returns a
`shared_ptr`, which ensures that the object will remain alive (if it still
was). Locking is an atomic operation, just like reference
incrementing/decrementing. So this is all thread-safe.

`circle_ptr`s may not be very thread safe. It may be possible for a
`circle_ptr` to become invalid from another thread, if the other thread
released the last non-circular reference to it.

I'm not entirely sure about this. It may be that such circumstances only
appear if you've already had a data race on the object's destruction, or are
using a non-owning reference. But I'm not sure that your design can be thread
safe.

### Virulence factors

This idea is incredibly viral. _Every other type_ where cyclic references can
happen must implement this interface. It's not something you can put on one
type. In order to get the benefits, every type that could participate in a
cyclical reference must use it. Consistently and correctly.

If you try to make `circle_ptr` require that the object it manages implement
`cycle_detector_mixin`, then you make it impossible to use such a pointer with
any other type. It wouldn't be a replacement of (or augmentation for)
`shared_ptr`. So there is no way for a compiler to help detect accidental
misuse.

Sure, there are accidental misuses of `make_shared_from_this` that cannot be
detected by compilers. However, that is not a viral construct. It is therefore
only a problem for those who _need_ this feature. By contrast, the only way to
get a benefit from `cycle_detector_mixin` is to use it as comprehensively as
possible.

Equally importantly, because this idea is so viral, you will be using it a
lot. And therefore, you are far more likely to encounter the multiple-
inheritance problem than users of `make_shared_from_this`. And that's not a
minor issue. Especially since `cycle_detector_mixin` will likely use
`static_cast` to access the derived class, so you won't be able to use virtual
inheritance.

### Summation

So here is what you must do, without fail, in order to detect cycles, none of
which the compiler will verify:

  1. Every class participating in a cycle must be derived from `cycle_detector_mixin`.

  2. Anytime a `cycle_detector_mixin`-derived class constructs a `circle_ptr` instance within itself (either directly or indirectly, but not within a class that itself derives from `cycle_detector_mixin`), pass a pointer to yourself to that `cycle_ptr`.

  3. Don't assume that any `cycle_ptr` subobject of a class is valid. Possibly even to the extent of becoming invalid within a member function thanks to threading issues.

And here are the costs:

  1. Cycle-detecting data structures within `cycle_detector_mixin`.

  2. Every `cycle_ptr` must be 50% bigger, even the ones that aren't used for cycle detection.

## Misconceptions about ownership

Ultimately, I think this whole idea comes down to a misconception about what
`shared_ptr` is actually for.

> "A cycle detector is unnecessary because cycles are not that frequent and
> they can be easily avoided using `std::weak_ptr`." Cycles in fact turn up
> easily in many simple data structures - e.g. a tree where children have a
> back-pointer to the parent, or a doubly-linked list. In some cases, cycles
> between heterogenous objects in complex systems are formed only occasionally
> with certain patterns of data and are hard to predict and avoid. In some
> cases it is far from obvious which pointer to replace with the weak variant.

This is a very common argument for general-purpose GC. The problem with this
argument is that it usually makes an assumption about the use of smart
pointers that just isn't valid.

To use a `shared_ptr` _means something_. If a class stores a `shared_ptr`,
that represents that the class has _ownership_ of that object.

So explain this: why does a node in a linked list need to _own_ both the next
and previous nodes? Why does a child node in a tree need to _own_ its parent
node? Oh, they need to be able to _reference_ the other nodes. But they do not
need to control the lifetime of them.

For example, I would implement a tree node as an array of `unique_ptr` to
their children, with a single pointer to the parent. A _regular_ pointer, not
a smart pointer. After all, if the tree is constructed correctly, the parent
will own its children. So if a child node exists, it's parent node _must
exist_ ; the child cannot exist without having a valid parent.

With a double linked list, I might have the left pointer be a `unique_ptr`,
with the right being a regular pointer. Or vice-versa; one way is no better
than the other.

Your mentality seems to be that we should always be using `shared_ptr` for
things, and just let the automatic system work out how to deal with the
problems. Whether it's circular references or whatever, just let the system
figure it out.

That's not what `shared_ptr` is for. The goal of smart pointers is _not_ that
you don't think about ownership anymore; it's that you can _express_ ownership
relationships directly in code.

## Overall

How is any of this an improvement over using `weak_ptr` to break cycles?
Instead of recognizing when cycles might happen and doing extra work, you now
do a bunch of extra work _everywhere_. Work that is exceedingly fraglile; if
you do it wrong, you're no better off than if you missed a place where you
should have used `weak_ptr`. Only it's worse, because you probably think your
code is safe.

The illusion of safety is worse than no safety at all. At least the latter
makes you careful.

Could you implement something like this? Possibly. Is it an appropriate type
for the standard library? No. It's just too fragile. You must implement it
correctly, at all times, in all ways, everywhere that cycles might appear...
or you get nothing.

## Authoritative references

There can be no authoritative references for something that was [never
proposed, suggested, or even imagined](http://www.open-
std.org/JTC1/SC22/WG21/docs/papers/) for standardization. Boost has no such
type, and such constructs were [never even
considered](http://www.boost.org/doc/libs/1_60_0/libs/smart_ptr/smart_ptr.htm#History)
for `boost::shared_ptr`. Even the [very first smart pointer paper
(PDF)](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/1994/N0555.pdf)
never considered the possibility. The subject of expanding `shared_ptr` to
automatically be able to handle cycles through some manual effort has [never
been discussed even on the standard proposal
forums](https://groups.google.com/a/isocpp.org/forum/#!forumsearch/) where
**_far_** stupider ideas have been deliberated.

The closest to a reference I can provide is [this paper from 1994 about a
reference-counted smart
pointer](https://www.usenix.org/legacy/publications/library/proceedings/c++94/full_papers/ellis.a).
This paper basically talks about making the equivalent of `shared_ptr` and
`weak_ptr` part of the language (this was in the _early_ days; they didn't
even think it was possible to write a `shared_ptr` that allowed casting a
`shared_ptr<T>` to a `shared_ptr<U>` when `U` is a base of `T`). But even so,
it specifically says that cycles would not be collected. It doesn't spend much
time on why not, but it does state this:

> However, cycles of collected objects with clean-up functions are
> problematic. If A and B are reachable from each other, then destroying
> either one first will violate the ordering guarantee, leaving a dangling
> pointer. If the collector breaks the cycle arbitrarily, programmers would
> have no real ordering guarantee, and subtle, time-dependent bugs could
> result. To date, no one has devised a safe, general solution to this problem
> [Hayes 92].

This is essentially the encapsulation/invariant issue I pointed out: making a
pointer member of a type invalid breaks an invariant.

So basically, few people have even considered the possibility, and those few
who did quickly discarded it as being impractical. If you truly believe that
they're wrong, the single best way to prove it is by implementing it yourself.
Then propose it for standardization.

