Statically preventing reference cycles

[arielb1]

Some people on rust-lang/rfcs#1066 asked about preventing reference cycles.

The last time we had a way of preventing reference cycles, it used Freeze, which prevented all use of RefCell. I think that with OIBIT we can have a better way: gist

Assuming an implementation of #[inductive], this prevents all T > RefCell > Rc > T cycles.

[Diggsey]

It’s generally impossible to distinguish memory leaks from correct behaviour without knowing the intention of the programmer. By making it harder, all you do is annoy the programmer who will then find some other way to do it.

A better approach is to actually find real cases where leaks can actually lead to memory unsafety - so far the only example given has been “scoped”. If there are examples like “scoped” which cannot be as easily fixed, then we can introduce a “Leak” marker trait (similar to Sync in that it is implemented for all types which only consist of Sync fields). We then add “Leak” bounds to “Rc” and “mem::forget”, and potentially provide stronger guarantee about when !Leak types’ destructors will run.

[arielb1]

If you are creating a graph you know to be acyclic, you can go ahead and do unsafe impl Acyclic for YourDAGNode {}.

If you don’t know your graph is acyclic, you should use an Arena or Vec to limit leaks.

[glaebhoerl]

Gist gives me 404 and this post must be at least 20 characters.

[arielb1]

Copy-paste error. Fixed.

[Diggsey]

Unsafety is supposed to be encapsulated, all you’re doing by adding that “impl” is moving the unsafety into the (supposedly safe) code which actually manipulates the graph.

[arielb1]

If your graph is :Drop<'static> then leaking parts of it is not unsafe anyway. Maybe we should also support that.

[Diggsey]

Right, but you’re proposing making everything unsafe to leak, without even a single example of something that actually IS unsafe to leak. IMO, the things that are unsafe to leak are the special case, and should be handled as such. One reason is that there are extra restrictions you have to place on such things if you want to guarantee that their destructors run (eg. destructors of these special types probably should never panic)

[pcwalton]

Very much no. Cycles are an extremely important feature of reference counted objects, as long as you tear them down properly. There’s no reason to try to forbid them.

[glaebhoerl]

There’s no reason to try to forbid them.

This is plainly not true. Ruling out cycles has benefits, such as (if the other sources of leaks can also be patched) being able to write APIs like the current incarnation of thread::scope with the knowledge that it is safe.

(Saying “the tradeoffs are not worth it” is of course a different matter.)

[oli-obk]

Maybe there should be different types.

1. forbid type-cycles (no T > RefCell > RcNoTypeCycle > T cycles)
2. forces type-cycles but forbids actual cycles at runtime (T > RefCell > RcNoRuntimeCycle > T is a requirement, checks inserted to the assignment of the RcNoRuntimeCycle<RefCell<U>> field of T to check for cycles)
3. allow arbitrary cycles, but risk memory leaks.

This is a completely backwards compatible change, since 3 is already implemented by Rc + RefCell.

[bluss]

For “type-cycles” I agree, because those are just the parts of a tree, DAG or custom composable object DAG of including Rc pointers. For actual cycles we have Weak pointers.

Now I do understand that there is no practical way to distinguish a sprawling Rc DAG from a cyclic graph.

[pcwalton]

As I posted in the RFC:

Suppose you want to create cycles and use a cycle collector to clean up cycles (for example, when making something scriptable in a dynamic language, as Firefox does). I can’t imagine any reasonable type system extension that could possibly allow for this while simultaneously forbidding reference cycles.

[llogiq]

I can’t imagine any reasonable type system extension that could possibly allow for this while simultaneously forbidding reference cycles.

I can imagine having not two, but three solutions existing:

• RC without cycles (and a lint that rules them out via broad static analysis, e.g. FindBugs has something similar)
• RC with cycle detection on drop (probably sloooooow?)
• unsafe RawRC where you have to deal with cycles yourself

Also the three types probably should not (cannot?) be mixed in working code.

[oli-obk]

Also the three types probably should not (cannot?) be mixed in working code.

sure they can be mixed. They even must be allowed to mix. Otherwise you cannot ever use crates that have functions returning boxed trait objects

Also it’s not an issue since at every use-location you have to decide on what to do… Maybe this would work better as a derived trait with a cleanup function. You could then not create ´Rc´s of types that do not implement the trait

[iopq]

Swift has cycle detection in their RC types. They probably do batch some of these things so that you don’t have to check for cycles on every reference decremeent, you just wait until a few more things are dropped, because your reference count might drop to 0 anyway (at which point you can skip the cycle check)

[llogiq]

Yes, this is what I thought, too. But cycle detection costs a lot of cycles – CPU cycles, that is. So if we want zero-cost abstraction, it should probably be opt-in. Also batching doesn’t work very well if you depend on dropping a value before returning, which is IMHO the central part of the problem with thread::scoped.

[iopq]

Yeah, so you shouldn’t depend on it if you want an efficient RcCycle implementation because you want to delay collecting cycles as long as possible (maybe you don’t have a cycle anyway and that object gets dropped)

Then you’d just use RcNoCycle for scoped threads and current Rc doesn’t care about whether there are cycles so that’s your RawRc in your example

[llogiq]

Ok, I have to take back my statement: AcyclicRcs and CyclycRCs can be mixed, but once a CyclicRC comes in, the whole structure must be deemed potentially cyclic, so one can no longer rely on timely drop.

The distinction between AcyclicRC and RawRC is compile-time only: If we had static analysis / extended requirements to avoid cycles altogether, a RawRC type would provide an unsafe escape hatch.

[ssheldon]

Swift has cycle detection in their RC types.

Is this true? Objective-C definitely doesn’t have cycle detection in its reference counting. And I’m not finding anything to indicate Swift does (especially given that Objective-C object can be Swift objects). Apple has a part of their Swift reference counting documentation titled “Resolving Strong Reference Cycles Between Class Instances”, and if you need to resolve cycles it would imply the language won’t handle them automatically for you.