Lifetime annotations

help
1

I am trying to understand requirements for lifetime annotations and I cannot understand why in the example from the book "Too many linked lists" annotations are required. The structure Iter is generic over only one lifetime, and it is returned from a method, so automatically receives the lifetime of self, so there is no any ambiguity that the lifetime of Iter is related to the lifetime of List.

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

impl List {
pub fn iter(&self) -> Iter {
Iter { next: self.head.map(|node| &node) }
}
}

impl Iterator for Iter {
type Item = &T;

fn next(&mut self) -> Option<Self::Item> {
    self.next.map(|node| {
        self.next = node.next.map(|node| &node);
        &node.elem
    })
}
}```
1 Like
2

I assume you have next: Box<Node> or similar.

option.map() moves the argument by value, so what's happening is:

  • node.next.map(…) moves the next instance out of node.next, making node invalid and contain uninitialized field, which it can't allow unless it's destroyed before the "hole" where the field was could be observed.
  • the instance of the next node is passed by value as an argument to the closure, making the closure own it exclusively.
  • the closure tries to return a reference to a value it owns
  • before returning, the closure destroys all local variables, invalidating all references to them, so returning a reference to the node argument is impossible, because it ceases to exist before the reference is returned.
    Note that Rust doesn't have a garbage collector, so it will never extend lifetime of any object for you. It runs destructors as always, using fixed rules, and it's up to you to rearchitect the code to prevent objects from being destroyed if you need them to live longer.

Here you just need node.next.as_ref(). This changes &Option<T> to Option<&T>. These two types are identical in memory, but map on Option<&T> "moves" only &T which is trivially copyable, and doesn't destroy the original T.

1 Like
3

Thank you, sorry for misunderstanding, this code is from the book and the correct version is this:

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

impl List {
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.as_deref() }
}
}

impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;

fn next(&mut self) -> Option<Self::Item> {
    self.next.map(|node| {
        self.next = node.next.as_deref();
        &node.elem
    })
}

}
Here there are lifetime annotations, my previous question is why are they still needed?
The structure Iter is generic over only one lifetime, and it is returned from a method, so automatically receives the lifetime of self, so there is no any ambiguity that the lifetime of Iter is related to the lifetime of List.

4

No need to apologize, we're here to help you learn.

.as_deref() is very similar to .as_ref(), but goes even a step further and changes Option<Box<T>> to Option<&T>, which is exactly what you need in this case. With just .as_ref() you'd still need .map() to change &Box<Node> to &Node.

5

I cannot understand why the compiler cannot figure out itself that the 'a lifetime of structure Iter (and then the 'a lifetime of the associated type) is related to the 'a lifetime of self in method on List? I think this is why the 'a lifetime annotations are needed here?

6

The lifetime annotation in the signature of the iter function is not necessary, because the lifetime elision rules will produce an equivalent result. The lifetime annotations on struct Iter and impl Iterator for Iter are necessary because there are no elision rules that apply to those situations.

On a quick review, the book seems to be wrong on this point. “We need to add lifetimes only in function and type signatures” isn't correct — none of the functions in this particular code need lifetime annotations.

2 Likes
7

Thank you, I understood there is no lifetime elision for structures and if a struct contains a reference, lifetime should be always annotated.

8

I am curious, why there are no elision rules for structures, for example, like Iter, which is generic over a single lifetime?

9

I don’t know if there's a specific rationale for not doing so, but to make one up: in very early Rust, there were no lifetime elision rules at all; they were added to simplify extremely common patterns of lifetime annotations on functions. Lifetime annotations on structs, on the other hand, are not common — very few structs do, or should, have lifetime parameters. This means there is less value in having elision rules, and that people are less likely to quickly gain practice writing and reading code which uses those rules.

Also, elided lifetimes in uses of a struct type are a common trap for beginners:

struct SomeLibraryType<'a> {...}
...
impl Foo {
    fn my_func(&self) -> SomeLibraryType {...}

“Help, I’m getting an error that says Foo is still borrowed when I try to mutate it after my_func().”
“Yep, you’re borrowing it in -> SomeLibraryType, even though you can't see that.”

To address this confusion, the elided_lifetimes_in_paths lint was created (though, unfortunately, not enabled by default yet). Now, imagine if the declaration of the struct could also hid the fact that it had a lifetime parameter — then people could write this trap for themselves without even noticing any lifetimes were involved anywhere.

4 Likes
10

Thank you for your reply. As a beginner I feel I need to understand it thoroughly.
I played with iterators now, and found out that even if iter or iter_mut structures are created from a collection, and then exhausted, they still continue to exist and prevent any mutable borrow if you try to access them, even if they return None.

11

Yes, because “has returned None” is a dynamic (run-time) property of the code, which the borrow checker never looks at in any way. (The borrow checker does make use of control flow information, but only which branches exist, not whether one will be taken.)

3 Likes
12

Thank you very much, your answers bring a lot of clarity!