RefMut borrowed from Option does not live long enough (Option<Rc<RefCell<Node>>>)

Question

First of all, I apologize if this question has been asked before. The only similar problem I could find was this (but it seems different) :

Cyclic reference does not live long enough

My code is :

use std::cell::RefCell;
use std::rc::Rc;

type NodePointer = Option<Rc<RefCell<Node>>>;

#[derive(Debug)]
struct Node {
    pub value : i32,
    pub next : NodePointer
}

fn main() {
    let mut vector = vec![None; 2];
    let new_node = Rc::new(RefCell::new(Node {
                value : 0,
                next : None
            }));
    vector[1] = Some(Rc::clone(&new_node));
    let new_node = Rc::new(RefCell::new(Node {
                value : 0,
                next : Some(Rc::clone(&new_node))
            }));
    vector[0] = Some(new_node);
    println!("{:?}", vector);

    // the following 3 lines would represent a body of the loop
    let mut a = vector[0].as_ref(); // Option<&Rc<RefCell<Node>>>
    let b = a.take().unwrap().borrow_mut(); // RefMut<Node>
    a = b.next.as_ref(); //ERROR : borrowed value 'b' does not live long enough

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

The code below presents a short excerpt of my complete code. It is a bit weird, but variable 'a' would be used for looping over a vector (more than 2 values in complete code).

What I am trying to do is to make sure that variable 'a' is replaced with 'next' argument from vector[0] without modifying vector.

Compiler complains that 'b' does not live long enough, but I don't see why this is the case.

According to my understanding :

• vector[0] is Option<Rc<...>>
• variable 'a' is Option<&Rc<...>>
• a.take() does not modify vector[0]
• a.take() instead replaces 'a' with None
• borrow_mut() should give a reference to vector[0], but for some reason it doesn't (?) <- I think this is the problem here
• something happened to b, but I don't see what.

I am also aware that I could make use of Option::take() method instead of take_ref() (and it works in my complete code together with some additional modifications), but I would like to keep vector unmodified in-between 2 println statements

EDIT : for information, the following loop body would compile, but it modifies vector...

let mut a = vector[0].take(); // Option<&Rc<RefCell<Node>>>
let temp = a.unwrap();
let mut b = temp.borrow_mut(); // RefMut<Node>
a = b.next.take(); //ERROR : borrowed value 'b' does not live long enough

Answer 1

I may be wrong (still not 100% confident about the borrow checker), but I think the issue is this:

    // b borrows from a
    let b = a.take().unwrap().borrow_mut();
    // now, a borrows from b
    // note that the lifetime of `a` doesn't magically change just because you're not using the original value anymore
    // so from the type checker's perspective, a and b borrow from each other at the same time – not allowed
    a = b.next.as_ref();
    
    // btw, if you replace `a =` with `let c =` or even `let a =`, creating a new variable with a new lifetime, it compiles
    // let a = b.next.as_ref();
    // but doesn't work for us since you want to put it in a loop

And I think it makes sense. In the first iteration, you get a Option<&Rc<_>> by borrowing from vector. But if you had a Option<&Rc<_>> in the second iteration, where would it be borrowed from? You didn't take it from vector, you took it from stuff that only lived during the last iteration – it might be invalid. Or otherwise you would somehow need to ensure that all of the intermediate RefMuts somehow lived for the duration of the loop.

I don't think you can borrow something from one iteration to bring it to the next.

Instead, you should take advantage of the reference counting that you already have:

    let mut next = vector[0].clone();
    while let Some(node) = next {
        next = node.borrow_mut().next.clone();
    }

Now, next has type Option<Rc<_>> – shared ownership instead of a borrow.

Answer 2

I'd just like to expand on the answer given by Reinis Mazeiks a bit. I've modified your code slightly to remove some of the non-critical stuff.

let mut a = vector[0].as_deref();
let b = a.unwrap().borrow();
a = b.next.as_deref();

The yields the same error of "b does not live long enough." The variable a is borrowing from vector, and b is transitively borrowing from vector as well. For instance, the following will compile:

let b: Ref<'_, Node>;
{
    let a = vector[0].as_deref();
    b = a.unwrap().borrow();
} // a is dropped
// This is okay because b's lifetime is tied to vector
println!("{}", b.value);

However, borrow returns an owned value, a Ref<'_, T>. On the third line in the first code block, the compiler doesn't see us borrowing from a, or vector, is sees us borrowing from b. This is because Deref (which is implicitly called when you call as_ref in your code), takes an &self, so we can only borrow something through Deref for at most as long as it lives, and that Ref lives only as long as b.

Now we run into a pickle here. Let's label some lifetimes and unpack things a bit:

let mut a = vector[0].as_deref(); // Option<&'a RefCell<Node>>
let b = a.unwrap().borrow(); // Ref<'b, Node>
let temp = b.next.as_deref(); // Option<&'c RefCell<Node>>
a = temp;

The second line requires that 'a: 'b (read 'a lives at least as long as 'b). This is because that Ref is borrowing from the reference held by a, and that reference must be valid for as long as b lives. When creating temp, we then borrow from b, so the lifetime 'b must satisfy 'b: 'c, but more importantly 'c also cannot outlive the variable b, since it's borrowing through the owned Ref which must be dropped. However the fourth line requires that 'c: 'a in order to follow the rules of variance and sub-typing. Since we're assigning something that lives for 'c to something that lives for 'a, it follows that 'c must be at least as long as 'a. Overall this comes full-circle to say that 'a = 'c. But this is a problem because 'a and 'c come from different values which are dropped at different times, and because Ref does not allows its generic arguments to dangle in its drop implementation, our program gets rejected by the drop check.

For fun, I copied the relevant parts of std's RefCell implementation, but changed the drop implementation of BorrowRef (which Ref contains) to the following:

unsafe impl<#[may_dangle] 'a> Drop for BorrowRef<'a> {
    #[inline]
    fn drop(&mut self) {
        // This is UB
        let borrow = self.borrow.get();
        debug_assert!(is_reading(borrow));
        // This is also UB
        self.borrow.set(borrow - 1);
    }
}

Using the custom RefCell with this modification allows the three problematic lines to compile, validating the theoretical argument above. However, do not even think about doing this because the drop implementation uses references which live for 'a, so this is undefined behavior, and hence why your program was rejected.