Please, explain Rc<T> to me

I'm reading about Rc<T> here, and can't understand, what it's all about. I'm understand the point of counter in languages, where we have to manually free memory. But Rust is different.

We use the Rc<T> type when we want to allocate some data on the heap for multiple parts of our program to read and we can’t determine at compile time which part will finish using the data last.

Problem is, there is no examples on page, which demonstrates this strength of Rc<T>. And I can't imagine it for myself. I'm just learning. There is only this:

enum List {
    Cons(i32, Rc<List>),
    Nil,
}

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

fn main() {
    let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil)))));
    let b = Cons(3, Rc::clone(&a));
    let c = Cons(4, Rc::clone(&a));
}

There is also such statement:

The borrow checker wouldn’t let us compile let a = Cons(10, &Nil); for example, because the temporary Nil value would be dropped before a could take a reference to it.

Well, borrow checker allows this for me:

enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil,
}
    
use List::{Cons, Nil};
    
fn example() {
    let a = Cons(10, &Nil);
    let a = Cons(5, &Cons(10, &Nil));
    let b = Cons(3, &a);
    let c = Cons(4, &a);
}

Maybe it differs in important way, but I can't see it, since I'm just try to repeat this simple example. I just can see, that it is compiles.

Right, that seems like a confusing description. In the case of &Nil, the compiler notices that Nil is a compile-time constant, so it compiles down to this:

static NIL: List<'static> = Nil;

let a = Cons(10, &NIL);

The same applies to the &Cons(10, &Nil) case, where it gets turned into two immutable globals:

static NIL: List<'static> = Nil;
static CONS: List<'static> = Cons(10, &NIL);

let a = Cons(5, &CONS);

As for b and c, they are holding references to the a variable, so as long as they do not outlive a, it is fine. The point where you run into trouble is when b outlives a, such as here:

fn create_b<'a>() -> List<'a> {
    let a = Cons(5, &Cons(10, &Nil));
    let b = Cons(3, &a);
    
    return b;
}
error[E0515]: cannot return value referencing local variable `a`
  --> src/lib.rs:13:12
   |
11 |     let b = Cons(3, &a);
   |                     -- `a` is borrowed here
12 |     
13 |     return b;
   |            ^ returns a value referencing data owned by the current function

In this case, an Rc would help you, because unlike with an ordinary reference, the fact that b holds an Rc pointing at a is enough to keep a alive, so it is not invalid to return b from the function. Hence, this compiles:

use std::rc::Rc;

enum List {
    Cons(i32, Rc<List>),
    Nil,
}
    
use List::{Cons, Nil};

fn create_b() -> List {
    let a = Cons(5, Rc::new(Cons(10, Rc::new(Nil))));
    let b = Cons(3, Rc::new(a));
    
    return b;
}
1 Like

So just to summarize:

  1. The advantage of Rc<T> over &T is that an Rc<T> will keep the T it points at alive.
  2. The advantage of Rc<T> over Box<T> is that you can only have a single Box<T> to a value, but you can have multiple Rc<T> to a value.
2 Likes

Why did you used Rc::new(a) on this line, unlike Rc::clone(&a) in example from The Book? Is it a typo? As far, as I'm understand, in that way b took ownership on a.

When you use Rc::new, you perform the conversion T → Rc<T>. When you use Rc::clone, you already have a Rc<T>, and want to obtain another Rc<T> that contains the same value.

Oh. Now I noticed, that you have
let a = Cons(5, Rc::new(Cons(10, Rc::new(Nil))));
on previous line in your example.

If you had
let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil)))));
on that line instead, like in The Book, you would had to use Rc::clone(&a) instead of Rc::new(a), right?

1 Like

Yeah, then I would need Rc::clone.

1 Like

Thanks. I think, I'm understand better now. It just feels a bit weird. There is quote from The Book:

To enable multiple ownership, Rust has a type called Rc<T> , which is an abbreviation for reference counting .

It seems like, it is overriding borrowing rules, and it do so with unsafe Rust, right? If I'm understand right, it was done this way, so user would understand overhead related to the counter.

To understand better, I want to ask, how counter is stored. Is it stored on the heap near the data, each Rc<T> is pointing to, or there is copy of counter on the stack in each instance of Rc<T>, which points to specific data on the heap? If second is truth, then, when one instance of Rc<T> cloned or dropped, how it is trigger other instances to update counter?

It’s stored on the heap, next to the data.

3 Likes