Why do we need Rc<T> when immutable references can do the job?

Question

To illustrate the necessity of Rc<T>, the Book presents the following snippet (spoiler: it won't compile) to show that we cannot enable multiple ownership without Rc<T>.

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

use crate::List::{Cons, Nil};

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

It then claims (emphasis mine)

We could change the definition of Cons to hold references instead, but then we would have to specify lifetime parameters. By specifying lifetime parameters, we would be specifying that every element in the list will live at least as long as the entire list. 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, not quite. The following snippet compiles under rustc 1.52.1

enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil,
}

use crate::List::{Cons, Nil};

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

Note that by taking a reference, we no longer need a Box<T> indirection to hold the nested List. Furthermore, I can point both b and c to a, which gives a multiple conceptual owners (which are actually borrowers).

Question: why do we need Rc<T> when immutable references can do the job?

Retiarius

You can certainly do that, but since the List only borrows its values you're going to have trouble returning a populated List from a function for example. – Manly

@Manly That makes sense. Now let me try if I can have something like Cons(i32, &'a Box<List<'a>>),... – Retiarius

Answer 1

With "ordinary" borrows you can very roughly think of a statically proven order-by-relationship, where the compiler needs to prove that the owner of something always comes to life before any borrows and always dies after all borrows died (a owns String, it comes to life before b which borrows a, then b dies, then a dies; valid). For a lot of use-cases, this can be done, which is Rust's insight to make the borrow-system practical.

There are cases where this can't be done statically. In the example you've given, you're sort of cheating, because all borrows have a 'static-lifetime; and 'static items can be "ordered" before or after anything out to infinity because of that - so there actually is no constraint in the first place. The example becomes much more complex when you take different lifetimes (many List<'a>, List<'b>, etc.) into account. This issue will become apparent when you try to pass values into functions and those functions try to add items. This is because values created inside functions will die after leaving their scope (i.e. when the enclosing function returns), so we cannot keep a reference to them afterwards, or there will be dangling references.

Rc comes in when one can't prove statically who is the original owner, whose lifetime starts before any other and ends after any other(!). A classic example is a graph structure derived from user input, where multiple nodes can refer to one other node. They need to form a "born after, dies before" relationship with the node they are referencing at runtime, to guarantee that they never reference invalid data. The Rc is a very simple solution to that because a simple counter can represent these relationships. As long as the counter is not zero, some "born after, dies before" relationship is still active. The key insight here is that it does not matter in which order the nodes are created and die because any order is valid. Only the points on either end - where the counter gets to 0 - are actually important, any increase or decrease in between is the same (0=+1+1+1-1-1-1=0 is the same as 0=+1+1-1+1-1-1=0) The Rc is destroyed when the counter reaches zero. In the graph example this is when a node is not being referred to any longer. This tells the owner of that Rc (the last node referring) "Oh, it turns out I am the owner of the underlying node - nobody knew! - and I get to destroy it".

Gwendagwendolen

By because all borrows have a 'static-lifetime, did you mean both Cons(10, &Nil) and a have 'static-lifetime? I don't follow: they are the return values of functions, so how could they be known at compile time? – Retiarius

Yes, this is known as "static promotion". If you do let x = &42, x will be of type &'static {integer}. Likewise, the a carries a 'static lifetime because the borrow in &Nil is done using a statically allocated Nil; so the problem that Rc solves is mute. It becomes more apparent if you think about creating the structure your are describing from external input. – Gwendagwendolen

Interesting. Does “static promotion” mean all literal struct/enum values whose fields are also literals are stored in the .TEXT segment and given 'static-lifetime? – Retiarius

Not necessarily, because a &'static is similar to a const in practical terms, so in reality, the compiler will either const-fold the value and/or put it into the instruction stream directly. But in general, yes, you can think of it as if you do let x = &Some(42), there is a Some(42) baked into the executable and x is a &'static to it. – Gwendagwendolen

Answer 2

The answer of user2722968 helped me to understand the issue and to create a super simple example to explain the logic to myself.

The original reference solution of nalzok would not work, if the owner of a goes out of scope:

#[derive(Debug)]
enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil,
}

use crate::List::{Cons, Nil};

fn main() {
    let b;
    {
        let a = Cons(5, &Cons(10, &Nil));
        b = Cons(3, &a);
//                  ^^ borrowed value does not live long enough
    }
//  - `a` dropped here while still borrowed

    println!("{:?}", b);
//                   - borrow later used here
}

You will get the exact same code running when using Rc, because then you don't have to care about lifetimes of owners and borrows:

use std::rc::Rc;

#[derive(Debug)]
enum List {
    Cons(i32, Rc<List>),
    Nil,
}

use crate::List::{Cons, Nil};

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

    println!("{:?}", b);
}

Jackstay

Answer 3

Even single-threaded, there are still times the destruction order is determined dynamically, whereas for the borrow checker to work, there must be a determined lifetime tree (stack).

fn run() {
    let writer = Rc::new(std::io::sink());
    let mut counters = vec![
        (7, Rc::clone(&writer)),
        (7, writer),
    ];
    while !counters.is_empty() {
        let idx = read_counter_index();
        counters[idx].0 -= 1;
        if counters[idx].0 == 0 {
            counters.remove(idx);
        }
    }
}

fn read_counter_index() -> usize {
    unimplemented!()
}

As you can see in this example, the order of destruction is determined by user input.

Another reason to use smart pointers is simplicity. The borrow checker does incur some code complexity. For example, using smart pointer, you are able to maneuver around the self-referential struct problem with a tiny overhead.

struct SelfRefButDynamic {
    a: Rc<u32>,
    b: Rc<u32>,
}

impl SelfRefButDynamic {
    pub fn new() -> Self {
        let a = Rc::new(0);
        let b = Rc::clone(&a);
        Self { a, b }
    }
}

This is not possible with static (compile-time) references:

struct WontDo {
    a: u32,
    b: &u32,
}

Larghetto