Rc smart pointers and the impossibility of reference passing

Trying to understand Rust through the "Rust Programming Language" book, I got to a point where I have another (begginer) question.

In chapter 15, section 15.4 ("Rc, the Reference Counted Smart Pointer") the author first try to implement a shared ownership Cons list without the Rc pointer with the following code:

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));
}

Which yields to a compiler error due to the move of variable "a".

To which he/she states:

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.

Not fully undertanding what he/she meant by 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., I tried to implement it myself:

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

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

fn main() {
    let test = Cons(10, &Nil);
    println!("test: {:?}", test);

    let a = Cons(3, &Cons(2, &Cons(1, &Nil)));
    let b = Cons(4, &a);
    let c = Cons(5, &a);
    println!("a: {:?}", a);
    println!("b: {:?}", b);
    println!("c: {:?}", c);
}

Which I successfully compiled and got the following output:

test: Cons(10, Nil)
a: Cons(3, Cons(2, Cons(1, Nil)))
b: Cons(4, Cons(3, Cons(2, Cons(1, Nil))))
c: Cons(5, Cons(3, Cons(2, Cons(1, Nil))))

So what did the author mean by
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.
?

This is simply no longer true due to the feature called rvalue 'static promotion. Basically, the Nil temporary can only ever have a single value/instance, so the compiler is allowed to (and does in fact) replace &Nil with the address of an anonymous global static constant containing the value Nil.

I think the example is not very good, overall. Even if 'static promotion didn't exist as a piece of automatic compiler magic, it would be possible to implement it by hand, and it's certainly possible to do the same with local variables as well, and therefore have multiple immutable references to either local or global variables.

It's just that when you are writing actual code with actual, non-trivial data structures, doing this quickly gets impractical, because references describe short-lived pointers (primarily locals within functions) well, but they are somewhat harder to use when describing relationships between data structures, and they can't express shared ownership. This has nothing to do with whether static promotion exists, so the provided example isn't really indicative of, or specific to, the most important problem.

1 Like

They really should fix this eventually, the issue is known for almost 3 years…

1 Like

To give an example of what wouldn’t work anymore: You could not implement a function like

fn shared_two_element_lists(first_a: i32, first_b: i32, second: i32) -> (List, List) {
    let tail = Rc::new(Cons(second, Rc::new(Nil)));
    let list_a = Cons(first_a, Rc::clone(&tail));
    let list_b = Cons(first_b, Rc::clone(&tail));
    (list_a, list_b)
}

(playground)

if you were using Box<List> or &List.

You couldn’t write a function like

impl List {
    fn push(&mut self, x: i32) {
        let tail = std::mem::replace(self, Nil);
        *self = Cons(x, Rc::new(tail));
    }
}

(playground)

either with Cons(i32, &List). Much if not most useful functionality from linked lists wouldn’t work.

While the former example raises the question as to what lifetimes to write in the (List, List) return type, before you even get to seeing what else the compiler wouldn’t like if &List was used instead of Rc<List, the latter example can be “converted” straightforwardly, so you can see an actual the error message

impl List<'_> {
    fn push(&mut self, x: i32) {
        let tail = std::mem::replace(self, Nil);
        *self = Cons(x, &tail);
    }
}
   Compiling playground v0.0.1 (/playground)
error[E0597]: `tail` does not live long enough
  --> src/lib.rs:12:25
   |
10 |     fn push(&mut self, x: i32) {
   |             --------- has type `&mut List<'1>`
11 |         let tail = std::mem::replace(self, Nil);
12 |         *self = Cons(x, &tail);
   |         ----------------^^^^^-
   |         |               |
   |         |               borrowed value does not live long enough
   |         assignment requires that `tail` is borrowed for `'1`
13 |     }
   |     - `tail` dropped here while still borrowed

For more information about this error, try `rustc --explain E0597`.
error: could not compile `playground` due to previous error

(playground)

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.