Borrowed RefCell does not last long enough when iterating over a list

Question

I'm trying to implement a linked list to understand smart pointers in Rust. I defined a Node:

use std::{cell::RefCell, rc::Rc};

struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

and iterate like

fn iterate(node: Option<&Rc<RefCell<Node>>>) -> Vec<i32> {
    let mut p = node;
    let mut result = vec![];

    loop {
        if p.is_none() {
            break;
        }

        result.push(p.as_ref().unwrap().borrow().val);

        p = p.as_ref().unwrap().borrow().next.as_ref();
    }

    result
}

the compiler reports an error:

error[E0716]: temporary value dropped while borrowed
  --> src/main.rs:27:13
   |
27 |         p = p.as_ref().unwrap().borrow().next.as_ref();
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^              -
   |             |                                         |
   |             |                                         temporary value is freed at the end of this statement
   |             |                                         ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `std::cell::Ref<'_, Node>`
   |             creates a temporary which is freed while still in use
   |             a temporary with access to the borrow is created here ...
   |
   = note: consider using a `let` binding to create a longer lived value

What happened? Can't we use a reference to iterate on a node defined this way?

The recently updated [Learning Rust with Entirely Too Many Linked Lists](https://rust-unofficial.github.io/too-many-lists/) contains [a section](https://rust-unofficial.github.io/too-many-lists/fourth-iteration.html) that attempts to solve this *exact* problem. I *strongly* recommend you read it. The [chapter introduction](https://rust-unofficial.github.io/too-many-lists/fourth.html) contains the disclaimer: "[T]his chapter is basically a demonstration that this is a very bad idea." — trent, Mar 25 '19 at 14:40

score 5 · Answer 1 · edited Mar 25 '19 at 15:27

Instead of assigning p the borrowed reference, you need to clone the Rc:

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

struct Node {
    val: i32,
    next: Option<Rc<RefCell<Node>>>,
}

fn iterate(node: Option<Rc<RefCell<Node>>>) -> Vec<i32> {
    let mut p = node;
    let mut result = vec![];

    loop {
        let node = match p {
            None => break,
            Some(ref n) => Rc::clone(n), // Clone the Rc
        };

        result.push(node.as_ref().borrow().val); //works because val is Copy
        p = match node.borrow().next {
            None => None,
            Some(ref next) => Some(Rc::clone(next)), //clone the Rc
        };
    }

    result
}

fn main() {
    let node = Some(Rc::new(RefCell::new(Node {
        val: 0,
        next: Some(Rc::new(RefCell::new(Node { val: 1, next: None }))),
    })));

    let result = iterate(node);
    print!("{:?}", result)
}

This is necessary because you are trying to use a variable with a shorter lifespan in a context that requires a longer lifespan. The result of p.as_ref().unwrap().borrow() is dropped (i.e. freed, de-allocated) after the loop iteration, but you are trying to use its members in the next loop (this is called use after free and one of the design goals of Rust is to prevent that).

The issue is that borrows do not own the object. If you want to use the next as p in the next loop, then p will have to own the object. This can be achieved with Rc (i.e. 'reference counted') and allows for multiple owners in a single thread.

What if the definition of Node::next is Option<Box<RefCell<Node>>>, how to iterate over this list?

Yes, I'm also very confused with RefCell, without RefCell we can iterate over list using reference only, but will fail with RefCell. I even tried to add a vector of Ref to save the reference, but still can not success.

If you drop the RefCell you can iterate it like this:

struct Node {
    val: i32,
    next: Option<Box<Node>>,
}

fn iterate(node: Option<Box<Node>>) -> Vec<i32> {
    let mut result = vec![];
    let mut next = node.as_ref().map(|n| &**n);

    while let Some(n) = next.take() {
        result.push(n.val);

        let x = n.next.as_ref().map(|n| &**n);
        next = x;
    }

    result
}

fn main() {
    let node = Some(Box::new(Node {
        val: 0,
        next: Some(Box::new(Node { val: 1, next: None })),
    }));

    let result = iterate(node);
    print!("{:?}", result)
}

Maybe it's possible with a RefCell as well, but I was not able to work around the lifetime issues.

What if the definition of Node.next is `Option>>`, how to iterate over this list? — xudifsd, Mar 25 '19 at 08:07
Yes, I'm also very confused with RefCell, without RefCell we can iterate over list using reference only, but will fail with RefCell. I even tried to add a vector of Ref to save the reference, but still can not success. — xudifsd, Mar 25 '19 at 09:50
@xudifsd if you try to preserve all the individual `Ref`s then you essentially create a self-referential struct, see [here](https://stackoverflow.com/a/66400083/2189130) for a bit more info about iterating over nested `Rc`s. — kmdreko, Feb 27 '21 at 15:06

score 0 · Answer 2 · answered Nov 02 '20 at 11:28

I bring a little different code from above answer, one match expression in the loop.

fn iterate(node: Option<Rc<RefCell<ListNode>>>) -> Vec<i32>{
    let mut result = vec![];

    let mut p = match node{
        Some(x) => Rc::clone(&x),
        None => return result,
    };

    loop {
        result.push(p.as_ref().borrow().val); //works because val is Copy

        let node = match &p.borrow().next{
            Some(x) => Rc::clone(&x),
            None => break,
        };
        p = node;
    }

    result
}

Borrowed RefCell does not last long enough when iterating over a list

2 Answers2

Linked