Reference Cycle and strong count

[anon75658756]

I am trying to understand an example of cyclical references.

First take this non-cyclical snippet and comments within:

use crate::List::{Cons, Nil};
use std::rc::Rc;


fn main() {
    // comments are the Rc strong counts.   
    let a = Rc::new(5); // a = 1
    let b = Rc::new([Rc::clone(&a)]); // a = 2, b = 1
} // a = 1, b = 0      --- b is dropped
// a = 0               --- a dropped

That's how I expect things to happen at a conceptual level.

Here, the Rust Book gives an example of cyclical references.

The main bit is (with stripped out comments):

What I expected is (in comments again):

fn main() {
    let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil)))); // a = 1

    let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a)))); // a = 2, b = 1

    if let Some(link) = a.tail() {
        *link.borrow_mut() = Rc::clone(&b); // b = 2
    }
} // b = 1, a = 1
// a = 0, b = 0

I am aware this is wrong, but I don't know how should I think about this.

The explanation in the book did not click for me.

This is just for understanding, so don't worry about fixes.

[kpreid]

@anon75658756

I am aware this is wrong, but I don't know how should I think about this.

There is nothing that can or will cause the transition from "a = 1, b = 1" to "a = 0, b = 0".

1. In order for a reference count to decrease, Rc::drop() needs to be called.

2. In order for Rc::drop() to be called, something has to call it.

3. Each of the two Rcs will call drop()^[1] on its contents when its reference count decreases to 0.

4. Each of the two Rcs refer to each other, so each one’s reference count will not drop below 1 unless the other is dropped.

5. Therefore, neither will be dropped.

---

1. technically std::ptr::drop_in_place() ↩︎

[anon75658756]

It is possible that I simply don't know what exact rules can decrease the count. I rephrase how I think about it below.

---

• I assume drops / count decreases happen every time it exits a scope.
• I assume that the drop process descends to the internal/children references.

Example

In the first snippet, we had let b = Rc::new([Rc::clone(&a)]). At the end of the scope, it drops b and descends into a to also decrease its count. The former —given that the count is 0— is also deallocated. That's b: 1->0 and a: 2->1.

Now comes a. The count decreases from 1 to 0 and is hence also deallocated (after b).

Going back to the bullet point, drop is called at end of scope, and if a count reaches 0 the data it points to is deallocated (and the stack is freed)

I interpret your "contents" as the children references. And maybe since it can not reach the end in this "descend process", the compiler whichever mechanism does not see one count it should decrease, and simply loops?

I need to re-read the section on Rc.

[SkiFire13]

@anon75658756

fn main() {
    let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil)))); // a = 1

    let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a)))); // a = 2, b = 1

    if let Some(link) = a.tail() {
        *link.borrow_mut() = Rc::clone(&b); // b = 2
    }
}

At the end of the scope, but before a and b are dropped, the refcount of a's Rc is 2: one for the Rc held in the stack and one for the Rc held in the RefCell inside b (and same for b).

Once the scope ends a and b are dropped. b is dropped first, and decreases the refcount of its Rc, which goes from 2 to 1. Since it did not reach 0, the contents of the Rc are not dropped. Then a is dropped, and decreases the refcount of its Rc, which also goes from 2 to 1, and again it does not reach 0. In the end you get two Rcs with refcount of 1 and the contents of none of them are dropped.

@anon75658756

I interpret your "contents" as the children references.

Whenever you do Rc::new(foo) then foo is the "content" of the Rc. It doesn't matter whether this is or contains another Rc, neither the compiler nor Rc itself handle that case in any special way.

[quinedot]

It ended up being quite large, but here's what happens in graphical form.

let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));

Rc (a)
+-----+
| ptr |
+-----+
   |
   v
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 1 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+
                                                         |
(call this `TempRcContent`)                              v
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 1 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Nil                         | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+

let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));

Rc (b)
+-----+
| ptr |
+-----+
   |
   v
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 1 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+
                                                         |
Rc (a)                                                   |
+-----+                                                  |
| ptr |                                                  |
+-----+                                                  |
   |                                                     |
   v  (strong count increased)                           v
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 2 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+
                                                         |
(call this `TempRcContent`)                              v
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 1 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Nil                         | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+

if let Some(link) = a.tail() {
    *link.borrow_mut() = Rc::clone(&b);
}

Rc (b)
+-----+
| ptr |
+-----+
   |
   v (strong count increased)
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 2 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+
                                                         ^
Rc (a)                  (these point at each other now)  |
+-----+                                                  |
| ptr |                                                  |
+-----+                                                  |
   |                                                     |
   v                                                     v
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 2 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+

(TmpRcContent counts dropped to 0, will drop List and deallocate)
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 0 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Nil                         | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+

The unnamed Rc that was originally in a drops because it got overwritten, and this is what decreases the strong count in TmpRcContent to 0, ultimately resulting in it going away as expected.

// b drops (goes out of scope)

     (strong count decreased)
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 1 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+
                                                         ^
Rc (a)                (these point at each other still)  |
+-----+                                                  |
| ptr |                                                  |
+-----+                                                  |
   |                                                     |
   v                                                     v
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 2 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+

The strong count pointed to by a remains 2 -- there are still two Rcs pointing at the contents, a and the Rc in what was originally pointed to by b.

// a drops (goes out of scope)

+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 1 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+
                                                         ^
                      (these point at each other still)  |
                                                         |
   (strong count decreased)                              v
+----------+------------+-------------------------------------------------+
| weak = 0 | strong = 1 | List                                            |
|          |            | +---------+-----------------------------------+ |
|          |            | | discrim | List::Cons                        | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | |         | | value = 5 | RefCell<Rc> (tmp) | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | | | ptr | |       | | |
|          |            | |         | |           | | +-----+ |       | | |
|          |            | |         | |           | +---------+       | | |
|          |            | |         | +-----------+-------------------+ | |
|          |            | +---------+-----------------------------------+ |
+----------+------------+-------------------------------------------------+

The strong counts of both instances remain one -- there is still an Rc pointing at each one (they are pointing at each other).

There's nothing else to drop by going out of scope after this, and no way to overwrite the Rcs to cause a drop, etc. So those two Rc allocations remain on the heap pointing at each other (they are leaked). They never tried to drop their Lists as their strong counts never reached 0.

[anon75658756]

How would a b containing many clones of a ever reach 0 if clones are only dropped when they are directly assigned to a variable?

(Which is how I read your reply at least.)

[kpreid]

Are you asking about a non-circular case? Then if b contained many clones of a, then when b's reference count reaches zero, b would drop its contained value, which owns all those many clones and therefore drops all of them.

Perhaps some broader explanations would help:

• Every value’s owner is responsible for dropping that value when it is known to no longer be needed. That's what ownership is.

• The default behavior is that types (in particular, any struct or enum you define) drop the values they own when they are dropped. That’s the default way for a type to be an owner, but there can be others.

• Rc introduces shared ownership by implementing the rule that “Rc<T> drops T when all clones of this Rc<T> are dropped”; we define all the clones collectively as the owner, rather than any single value.

  (When I say ‘all the clones’ I include the original Rc that never actually got clone() called on it. That one is not different in any way.)

[zirconium-n]

@anon75658756

• I assume drops / count decreases happen every time it exits a scope.
• I assume that the drop process descends to the internal/children references.

You are mixing places here.

When b exits it's scope, b is dropped, and what b points to (let's call it bp) decreases strong count.
When and only when bp's strong count reach zero, bp's content is dropped. If dropping b does not bring down bp's strong count to zero, nothing will be dropped afterwards.