Cyclic reference of RefCell borrows in traversal

Question

I'm learning Rust and tried coding a doubly-linked list. However, I'm stuck already at a typical iterative traversal implementation. I'm getting the impression that the borrow checker / drop checker is too strict and cannot infer the correct lifetime for the borrow when it crosses the function boundary from RefCell. I need to repeatedly set a variable binding (curr in this case) to the borrow of its current contents:

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

pub struct LinkedList<T> {
    head: Option<Rc<RefCell<LinkedNode<T>>>>,
    // ...
}

struct LinkedNode<T> {
    value: T,
    next: Option<Rc<RefCell<LinkedNode<T>>>>,
    // ...
}

impl<T> LinkedList<T> {
    pub fn insert(&mut self, value: T, idx: usize) -> &mut LinkedList<T> {
        // ... some logic ...

        // This is the traversal that fails to compile.
        let mut curr = self.head.as_ref().unwrap();
        for _ in 1..idx {
            curr = curr.borrow().next.as_ref().unwrap()
        }

        // I want to use curr here.
        // ...
        unimplemented!()
    }
}

The compiler complains:

Without NLL

error[E0597]: borrowed value does not live long enough
  --> src/lib.rs:22:20
   |
22 |             curr = curr.borrow().next.as_ref().unwrap()
   |                    ^^^^^^^^^^^^^ temporary value does not live long enough
23 |         }
   |         - temporary value dropped here while still borrowed
...
28 |     }
   |     - temporary value needs to live until here
   |
   = note: consider using a `let` binding to increase its lifetime

With NLL

error[E0716]: temporary value dropped while borrowed
  --> src/lib.rs:22:20
   |
22 |             curr = curr.borrow().next.as_ref().unwrap()
   |                    ^^^^^^^^^^^^^
   |                    |
   |                    creates a temporary which is freed while still in use
   |                    a temporary with access to the borrow is created here ...
23 |         }
   |         -
   |         |
   |         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<'_, LinkedNode<T>>`
   |
   = note: consider using a `let` binding to create a longer lived value
   = note: The temporary is part of an expression at the end of a block. Consider adding semicolon after the expression so its temporaries are dropped sooner, before the local variables declared by the block are dropped.

I would really appreciate a iterative solution (non-recursive) to this problem.

Note: the borrow checker is not too strict, it prevents aliasing to occur here. If not for this, you could have mutability + aliasing, and thus crashes or memory corruption. — Matthieu M., Apr 13 '16 at 13:01
Have you had an opportunity to read [*Learning Rust With Entirely Too Many Linked Lists*](http://cglab.ca/~abeinges/blah/too-many-lists/book/)? — Shepmaster, Apr 13 '16 at 13:19
@Shepmaster: If you can get `curr` without borrowing `self`, what prevents you from getting `curr` again in the same method body? Nothing. This is dynamically prevented by getting `RefCell::borrow` to only lend references valid during the lifetime of its result. — Matthieu M., Apr 13 '16 at 13:20

score 2 · Accepted Answer · edited May 09 '19 at 14:51

2

You can clone Rc to avoid lifetime issues:

let mut curr = self.head.as_ref().unwrap().clone();
for _ in 1..idx {
    let t = curr.borrow().next.as_ref().unwrap().clone();
    curr = t;
}

edited May 09 '19 at 14:51

Shepmaster

388,571
95
1,107
1,366

answered Apr 14 '16 at 05:47

aSpex

4,790
14
25

Thanks, that worked! However, when I need to borrow mut from `curr` in the following lines, I had to do `let next = curr.borrow_mut().next.take(); match next {...}` instead of simply `match curr.borrow_mut().next.take() {...}`. The compiler doesn't try hard to infer things eh. – Tsukki Apr 15 '16 at 06:16

score 1 · Answer 2 · answered Apr 13 '16 at 13:05

Here's a smaller reproduction that I believe shows the same problem:

use std::cell::RefCell;

fn main() {
    let foo = RefCell::new(Some(42));
    let x = foo.borrow().as_ref().unwrap();
}

As I read it:

foo.borrow() returns a cell::Ref, a type of smart pointer. In this case, the smart pointer acts like an &Option<i32>.
as_ref() creates an Option<&i32> where the inner reference has the same lifetime as the smart pointer.
The Option is discarded, yielding only an &i32, still with a lifetime of the smart pointer.

Notably, the smart pointer Ref only lasts for the statement, but the code attempts to return a reference into the Ref that would outlive the statement.

Generally, the solution would be to do something like this:

let foo_borrow = foo.borrow();
let x = foo_borrow.as_ref().unwrap();

This keeps the smart pointer around longer, allowing the lifetime of the reference to be valid for as long as foo_borrow (representing the borrow itself) exists.

In the case of a loop, there's not much you can do, as you essentially want to borrow every previous node until you get to the next one.

Thanks for the answer. Are you saying that there is no way to do this in a loop? I'm not sure if your example is a solution to my problem. — Tsukki, Apr 13 '16 at 13:09
@Tsukki I wouldn't say no way, but **I** don't know it. When you do it recursively, I assume that there is an implicit hierarchy of outstanding borrows that allows it to proceed. — Shepmaster, Apr 13 '16 at 13:27

Cyclic reference of RefCell borrows in traversal

2 Answers2

Linked

Related