Lifetime of the returned `Ref<'b, T>`

help
1

I'm reading how to write a linked list in rust in this website Introduction - Learning Rust With Entirely Too Many Linked Lists. Although I've asked a lifetime question in https://users.rust-lang.org/t/mutable-references-lifetimes-in-itermut/117154, I ran into a new problem which I can't figure out. In this chapter: https://rust-unofficial.github.io/too-many-lists/fourth-peek.html, the writer showed an incorrect implementation:

pub fn peek_front(&self) -> Option<&T> {
    self.head.as_ref().map(|node| {
        &node.borrow().elem
    })
}

, which is invalid because it creates a temporary value by the node.borrow().elem and then returns a reference to it, which means returning a value referencing data owned by the current function. The signature of borrow is

fn borrow<'a>(&'a self) -> Ref<'a, T>

And the guide says " But as soon as we return the reference from peek, the function is over and the Ref goes out of scope."

But by my reckoning, the lifetime 'a of Ref is the same as that of node, which in turn is the same as the self in peek, meaning as long as the List itself is valid, the returned reference should be valid. What's wrong with my conclusion here?

The basic structure of the code is listed below:

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>,
}

impl<T> List<T> {
    pub fn peek_front<'b>(&'b self) -> Option<Ref<'b, T>> {
        self.head.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }
}

The correct version of peek is also included.

2

And by comparing the correct version and the first version, I can't see the difference from the point of view of lifetime annotation. I can just see that one returns a Ref itself and the other returns a reference to a field of a value pointed by Ref.

3

Ref<'_, T> must never allow &T to escape out of it past its own existence. This is because Ref has a destructor that "unlocks" the RefCell. If &T could outlive Ref, then you could keep a reference to inside of the RefCell while the RefCell could be borrowed again mutably, and having an immutable and a mutable reference to the same thing at the same time causes Rust's universe to collapse.

When you use Ref::map, you get another Ref that still guards correct use of the RefCell.

3 Likes
4

"The returned reference should be valid" does not follow from "the lifetime 'a of Ref is the same as that of node". Borrowing the Node<T> happens through std::ops::Deref implemented for Ref, which has the signature

pub trait Deref {
    type Target: ?Sized;

    // Required method
    fn deref(&self) -> &Self::Target;
}

So, the &T that you get via &(<instance of Ref>).elem is an &'as_long_as_the_Ref_exists T, not an &'a T, and the Ref is dropped before peek_front() returns, so you cannot return a borrow from it.

3 Likes
5

So is it just another separate rule of Ref that disallows this or is it still related to the annotations of the borrow checker? If it's related to the annotations, I can't see how it's done.

6

There are no such extra rules, Ref is not special. Why you get the error has been derived above.

The signature of Deref::deref() is, desugared:

fn deref<'this>(&'this self) -> &'this Self::Taget;

which ties the lifetime in the return value to the lifetime of the reference-to-self; it has nothing to do with any lifetime annotations inside the Self type.

Put it another way, the upper bound on the returned lifetime is the validity scope of the self instance itself; it's not the (possibly longer) validity of any other objects pointed to by references contained in self.

5 Likes
7

I'm saying what others have already said in slower motion with different words, but perhaps that's useful.

Just a guess, but one possible point of confusion is if you're thinking that what Rust calls lifetimes ('_ things) are the same as the liveness scopes of values, and that the peek_from signature is conveying that somehow.

I guessed this because you said this specifically:

same as the self in peek, meaning as long as the List itself is valid

But that's not the case, the lifetime on &self can be (and typically is and typically must be) much shorter than the validity of self. Rust lifetimes are generally about the duration of some borrow, in contrast with the validity or liveness scopes of values.

Let's walk through the code in slow motion.[1]

    pub fn peek_front<'b>(&'b self) -> Option<&'b T> {
        // `r1: Ref<'b, Node<T>` -- some local value we create and own
        let Some(r1): Option<Ref<'b, Node<T>>> = 
            self.head.as_ref().map(|node| node.borrow())
            else { return None };
        
        // We give away ownership of `r1` and get back ownership of `r2`
        let r2: Ref<'b, T> = Ref::map(r1, |node| &node.elem);
        
        // Here's the key part:
        //
        // This is a `fn deref<'a>(self: &'a Ref<'b, T>) -> &'a T`
        //
        // `r2` itself is being borrowed here.  We can't borrow the local `r2`
        // for longer than the function body, because `r2` will go out of scope
        // (or otherwise be moved) by the end of the function body, and being
        // borrowed is not compatible with going out of scope (or being moved).
        let r3 = Deref::deref(&r2); // aka `let r3 = &*r2;`
        
        // This return is what attempts to make `'a` be as long as `'b`, but
        // as outlined above, that's not possible.  You can never borrow
        // a local for a caller-provided lifetime (those are always longer
        // than the function body).
        Some(r3)
    }

It's not something magic about Ref<'b, T>, and it's not about the fact that Ref<'b, T> contains some borrow 'b either. You can't return a reference to a local period; you can never borrow a local for a caller-provided lifetime.

    pub fn not_special_to_cell_ref<'b>(&'b self) -> &'b &'b Link<T> {
        // Putting &'b Link<T> in some local
        let ref_head = &self.head;
        // Trying to return a borrow of said local
        &ref_head
    }
    
    pub fn not_about_nested_lifetimes<'b>(&'b self) -> &'b i32 {
        let local = 0;
        &local
    }

    pub fn not_just_about_returns<'b>(&'b self) {
        let local = 0;
        let _borrowed_a_long_time: &'b i32 = &local;
    }

  1. Slightly restructured to aide annotation. ↩ī¸Ž

5 Likes
8

I didn't realize there was a deref involved. Your answer certainly fixed my question. Thanks a lot!

9

For most purposes, I understand that lifetime annotation is about references, not about values. But your thorough reply still refines my understanding of lifetime. I sometimes just don't know for calling fn<'a>(self: &'a Self, ..) whether I should annotate each call separately as 'a 'b, etc. according to fn<> or should I treat them all the same 'a according to self. Thanks a lot!

10

Lifetime elision is described in an algorithmic way, which tells you how to expand the signature you see in the source: Lifetime Elision - The Rustonomicon

After expanding all lifetimes, just look at where the lifetimes in the output type come from. As long as the return value of the function is kept around, the borrows those lifetimes originated from will also be.

2 Likes
11

Yes. After thinking about this topic in my mind for a long time today, I finally kind of managed to understand it reasonably and "completely". Thank you!

1 Like
12

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.