How to interpret the compile errors on borrowing

help
1

I come across this code in a tutorial (irrelevant parts removed):

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

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

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

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

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| {
            self.0 = node_ref.next.as_ref().map(|head| head.borrow());
            Ref::map(node_ref, |node| &node.elem)
        })
    }
}

(Playground)

Compiling it produces these errors:

   Compiling playground v0.0.1 (/playground)
error[E0521]: borrowed data escapes outside of closure
  --> src/lib.rs:18:13
   |
16 |     fn next(&mut self) -> Option<Self::Item> {
   |             --------- `self` declared here, outside of the closure body
17 |         self.0.take().map(|node_ref| {
18 |             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:19:22
   |
16 |     fn next(&mut self) -> Option<Self::Item> {
   |             --------- lifetime `'1` appears in the type of `self`
17 |         self.0.take().map(|node_ref| {
18 |             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`
19 |             Ref::map(node_ref, |node| &node.elem)
   |                      ^^^^^^^^ move out of `node_ref` occurs here

Some errors have detailed explanations: E0505, E0521.
For more information about an error, try `rustc --explain E0505`.
error: could not compile `playground` due to 2 previous errors

What I understand from the errors is that a reference to node_ref is assigned to self.0, but self.0 outlives node_ref itself. But I don't understand how that borrow of node_ref happens.

My potentially very wrong reasoning about the assignment to self.0 is:

  • node_ref.next leverages Deref to access the next field.
  • .as_ref() creates a temporary Option<&Rc<RefCell<Node<T>>>>.
  • .map() consumes the temporary Option and creates a new Option<Ref<'_, Node<T>>>.
  • The new Option in the previous step is assigned to self.0.

I must have missed something. How does the borrow of node_ref happen here?

3

The reference to head is derived from node_ref, and borrow returns a Ref that's tied to the lifetime of the &RefCell the method takes.

Most of the time when you obtain a reference from inside another reference, the lifetime of the inner reference is tied to the lifetime of the outer reference.

4

You're taking a reference to the field node_ref.next when you call the as_ref method. Because you are borrowing a field, it requires that node_ref is also (at least partially) borrowed for the same duration as the field. Additionally, every function in the chain also forwards that lifetime onward- at some point, you need to entirely decouple the lifetimes, and that doesn't happen there.

5

@semicoleon @Aiden2207 Thanks for your replies!

If I'm not mistaken, both of you mentioned the passing of lifetime along a chain. I think this is what confuses me. Regarding the code above, what I was intuitively thinking is that self.0 is given the reference to the next node so it is the next node that is borrowed rather than node_ref. To call as_ref(), node_ref is borrowed, but that seems to me a temporary thing. Can you please elaborate on that?

Also, is there anything - a section in the reference, or a blog post somewhere - I should read on that topic?

6

There is something going on here that I don't think anyone has mentioned yet: auto-deref. If something implements Deref and you use the . operator for field access or a method call, the language will insert a call to deref() if it needs to. This is how you can use . on a Ref<'_, T> and act upon the inner T.

Next, let me point out that the signatures of Deref::deref, Option::as_ref, and RefCell::borrow are all similar:

fn deref(&self) -> &Self::Target
fn as_ref(&self) -> Option<&T>
fn borrow(&self) -> Ref<'_, T>

By the lifetime elision rules, the output lifetimes are the same as the input lifetimes. This is the "chaining" of lifetimes that tends to happen.

Here's the code in slower motion.

This is a more complicated version of a common learning scenario: you can't borrow a local variable for some lifetime that is generic on your function, because those lifetimes are (a) decided by the caller, not the function body, and (b) always at least as long as the function body [1].

So here:

fn foo<'a>() {
    let local = 0;
    let _: &'a i32 = &local;
}

It's never possible to borrow the local for 'a because that would create a reference that lasts longer than its referent -- a dangling reference (instant UB).

I don't know of a comprehensive borrowing guide unfortunately, it's something I think people tend to pick up with experience. I will note that the linked list article exists in part to make the point that linked lists and other graph-like data structures are a poor way to first learn Rust. If you're still just starting out, have you read the book?

  1. otherwise using any arguments with said lifetime in the function body would be using them after they become invalid, e.g. a dangling reference ↩ī¸Ž

1 Like
7

Taking a look at Option::as_ref it has the following signature:

pub const fn as_ref(&self) -> Option<&T>

or if we desugar the lifetimes:

pub const fn as_ref<'a>(&'a self) -> Option<&'a T>

There is an implicit chain of the lifetimes from the input of the function to the output of the function. As long as that chain is not broken, the original borrow will still be considered live. It's a similar story for every other method in the chain.

Basically, because the next node in the chain is considered part of the current one, traveling down the chain via borrowing still leaves the original borrow live unless you introduce an explicit break of that chain via Rc::clone or something.

1 Like
8

Thank you for the detailed explanation, much appreciated!
I've read (15/21 chapters of) the book. I think I need more practice to comprehensively use the language features/concepts in actual code. Thanks for the link too :slight_smile:

1 Like
9

:+1::+1::+1:
I think I get it now. Thank you!

10

Actually, a few Rc-related ownership-and-borrowing posts did come to mind.

1 Like
11

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.