Using `Ref` in double linked list and get `error borrowed data escapes outside of closure`

When reading
Learning Rust With Entirely Too Many Linked Lists > A Bad Safe Deque > Iteration Chapter, I'm confused.

For singly linked list,

    pub struct List<T> {
        head: Link<T>,
    }

    type Link<T> = Option<Box<Node<T>>>;

    struct Node<T> {
        elem: T,
        next: Link<T>,
    }

    pub struct Iter<'a, T> {
        next: Option<&'a Node<T>>,
    }

    impl<'a, T> Iterator for Iter<'a, T> {
        type Item = &'a T;
        fn next(&mut self) -> Option<Self::Item> {
            self.next.map(|node| { // &'a Node<T>
                self.next = node.next.as_deref();
                &node.elem
            })
        }
    }

it's natural for me to understand self.next = node.next.as_deref(); works: the lifetime of reference doesn't change when passing. i.e.

node: &'a Node<T>
&node.next: &'a Link<T>
node.next.as_deref(): Option<&'a Node<T>>

But for double linked list,

    pub struct List<T> {
        head: Link<T>,
        tail: Link<T>,
    }

    type Link<T> = Option<Rc<RefCell<Node<T>>>>;

    struct Node<T> {
        elem: T,
        next: Link<T>,
        prev: Link<T>,
    }

    pub struct Iter<'a, T>(Option<Ref<'a, Node<T>>>);

    impl<T> List<T> {
        pub fn iter(&self) -> Iter<T> {
            Iter(self.head.as_ref().map(|head| head.borrow()))
        }
    }

    impl<'a, T> Iterator for Iter<'a, T> {
        type Item = Ref<'a, T>;
        fn next(&mut self) -> Option<Self::Item> {
            self.0.take().map(|node_ref| { // Ref<'a, Node<T>>
                self.0 = node_ref.next.as_ref().map(|head| head.borrow());
                Ref::map(node_ref, |node| &node.elem)
            })
        }
    }

the error is:

error[E0521]: borrowed data escapes outside of closure
  --> src/lib.rs:59:17
   |
57 |         fn next(&mut self) -> Option<Self::Item> {
   |                 --------- `self` declared here, outside of the closure body
58 |             self.0.take().map(|node_ref| {
59 |                 self.0 = node_ref.next.as_ref().map(|head| head.borrow());
   |                 ^^^^^^   -------- borrow is only valid in the closure body
   |                 |
   |                 reference to `node_ref` escapes the closure body here

error[E0505]: cannot move out of `node_ref` because it is borrowed
  --> src/lib.rs:60:26
   |
57 |         fn next(&mut self) -> Option<Self::Item> {
   |                 --------- lifetime `'1` appears in the type of `self`
58 |             self.0.take().map(|node_ref| {
59 |                 self.0 = node_ref.next.as_ref().map(|head| head.borrow());
   |                 ------   -------- borrow of `node_ref` occurs here
   |                 |
   |                 assignment requires that `node_ref` is borrowed for `'1`
60 |                 Ref::map(node_ref, |node| &node.elem)
   |                          ^^^^^^^^ move out of `node_ref` occurs here

Rust failed to understand the reference-passing relation

node_ref: Ref<'a, Node<T>>
&node_ref.next: &'a Link<T>
node_ref.next.as_ref(): Option<&'a Rc<RefCell<Node<T>>>>
node_ref.next.as_ref().map(|head| head.borrow()): Option<Ref<'a, Node<T>>>

I've searched around, and only to conclude that Rust seems to reborrow[1] in &node_ref.next: &'b Link<T> (where 'a: 'b).

I tried narrowing it with a function:

    fn f<'a, T>(opt: &mut Option<Ref<'a, Node<T>>>, node_ref: Ref<'a, Node<T>>) {
        *opt = node_ref.next.as_ref().map(|head| head.borrow());
    }

error[E0597]: `node_ref` does not live long enough
  --> src/lib.rs:66:16
   |
65 |     fn f<'a, T>(opt: &mut Option<Ref<'a, Node<T>>>, node_ref: Ref<'a, Node<T>>) {
   |          -- lifetime `'a` defined here
66 |         *opt = node_ref.next.as_ref().map(|head| head.borrow());
   |                ^^^^^^^^                          ------------- returning this value requires that `node_ref` is borrowed for `'a`
   |                |
   |                borrowed value does not live long enough
67 |     }
   |     - `node_ref` dropped here while still borrowed

Well, hard to understand again...

The code of interest is on playground.


  1. if this is the case, I suspect the code regarding singly linked list should fail too. ↩ī¸Ž

The function owns node_ref and drops it at the end. It's a local variable.

In order to get a 'a Node<T> in order to ... in order to get another Ref<'a, Node<T>> out from deep inside of it, you have to borrow node_ref for 'a via Deref::deref.

But you can't borrow a local variable for some outside lifetime 'a.


What would happen to the RefCell's state if you could drop the Ref but keep a reference around to its contents?

1 Like

The issue is that RefCell::borrow is fn(&self) -> Ref<'_, T>. This means that the returned Ref cannot outlive the reference-to-RefCell it came from, combined with that when you dereference the Ref<'a, T>, you don't get &'a T, you get a short-lived reference tied to the Ref, fn(&'r Ref<'a, T>) -> &'r T. Thus when you drop the Ref, the lock is freed and you can't use the inner reference anymore.

3 Likes

I see now :laughing:

node_ref: Ref<'a, Node<T>>
Deref::deref(&node_ref): &'r Node<T>
&node_ref.next: &'r Link<T>

it makes sense!