HAhaberman·Apr 27, 2015
I don't know enough about how Rc is used to know if this is an acceptable possibility, I just wanted to mention it in case it is possibly helpful.
I developed a reference-counting system in my library "upb" that handles cycles and never leaks objects. It is precise for no-longer-mutable objects (objects which may no longer change the set of other refcounted objects pointed to) and less precise for mutable objects.
The basic idea is to reference-count groups of objects instead of single objects, and define the groups such that no reference cycle spans groups.
If you introduce a link between two refcounted objects A -> B, then A and B's groups are merged. Now refs/unrefs of A or B ref/unref the (merged) group. Nothing in the group is freed until both A and B's refcounts both fall to zero. This conservative group-merging whenever you cre
Read the rest
ate a link ensures that no reference cycle spans groups.
This is imprecise and relatively wasteful if the group grows really large. But you can make it totally precise for any subgraph of refcounted objects that you're willing to freeze. At freeze time, compute strongly-connected components, and each SCC becomes a refcounted group. For any frozen subgraphs, the refcounting is totally precise. And unfrozen objects can reference frozen ones (but not the other way around).
If your application ends up freezing most of the graph, this works great. Or if you're ok with the collection being pretty coarse for your groups of objects, it also works great. If you have an application that can't freeze the graph and wants pretty precise collection, this doesn't work so well.
More info about my scheme is in comments in these headers:
https://github.com/haberman/upb/blob/master/upb/refcounted.h
https://github.com/haberman/upb/blob/master/upb/refcounted.c
I always was curious if the semantics of this scheme would play nicely with the ownership system in Rust.