Too-many-lists: Elaborate on lifetime in iter.next() in 3.6 IterMut

[louy2]

The signature of next establishes _no_ constraint between the lifetime of the input and the output! Why do we care? It means we can call next over and over unconditionally!

I feel there's a gap of logic here. IIUC lifetime is meant to restrain the scope of output relative to input, and it is not intuitive how it would prevent next() to be called consecutively.

The specific example of

fn next<'b>(&'b mut self) -> Option<&'a T> { /* stuff */ }

would directly lead to the conclusion that Option<&'a T> lives as long as T lives, which is until that element is drop()ed or the whole list is dead. The key difference from Option<&'b T> would be when the element is drop()ed.

What happens when next() is called the second (and third) time?

[jtepe]

Are you asking a question or do you want the article to include more clarification? In other words, are you unsure what is meant here, or do you already know and just want to extend the article? I am not entirely sure. :smile:

[louy2]

@jonastepe
Kinda both. I could only go so far in the OP and couldn't get from lifetime restriction to function call restriction. I believe clarification is needed, but I only know part of it.

[jtepe]

Maybe I should first repost my deleted former post ... Does that help you?

IIUC lifetime is meant to restrain the scope of output relative to input, ...

That is not the sole purpose of specifying lifetimes. Mainly, it is to relate how _borrows_ in a function/method call or complex type are related to another. You communicate your intention to the compiler, so it can reason with your intentions in mind and decide if those comply with its safety rules.

In the desugared example provided here:

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

    fn next<'b>(&'b mut self) -> Option<&'a T> { /* stuff */ }
}

We can see that the borrow of self is not linked to the returned reference. The lifetimes are named differently and they are not related in any way.

The borrow of self happens when we call next(), but it is not extended by storing the returned reference in a variable, as here:

let x = iter.next().unwrap();

The returned reference is of the lifetime 'a and not 'b. Thus, the borrow of self only lasts for that moment of the call to next(). And therefore, I can subsequently call next() again, since the mutable borrow of self only lasted for that moment.

Let's assume it would last longer and the method signature looked like this (Note, that you cannot do that with today's Rust, since the Iterator trait specifies the above signature):

fn next<'a>(&'a mut self) -> Option<&'a T>;

Now I convey to the compiler, that I want the two lifetimes/borrows to be linked. So, if I call next() and store the returned reference/borrow in a variable, that will extend the borrow of self to last as long as that variable is in scope. Then I cannot do this:

let x = iter.next().unwrap();
let y = iter.next().unwrap(); // error, more than one mutable borrow of iter!

The x is still in scope by the time I call the next() a second time, and therefore a mutable borrow of iter (which is the self in the signature of next()) is also still in scope. You can see how this would be very limiting. The x would have to go out of scope before we could resume calling next().

It is also unnecessary. Iter borrows a T (or some collection of T), it does not own the T, so I am not borrowing from Iter (which the second example above conveys to the compiler). I am borrowing from T. Iter is just another borrower of T and I am using it to aquire another borrow of T. Mutably borrowing Iter in the process would be totally overkill.

What the author, @Gankro, does here, is setting the stage in order to emphasize the difference to IterMut. That one returns mutable references (&mut T). With Iter you get multiple shared references to the underlying data. This is trivial with shared references; there can be multiple of those in scope at the same time. The amazing thing is that this is also possible for mutable references, as long as the underlying datastructure you're borrowing from easily partitions into _disjoint_ substructures.

[louy2]

@jonastepe
Thank you a lot! I suspected the assignment and &mut would together prevent a second function call, but failed to fit lifetime into the puzzle. I'd very much like your explanation added to the book. Could you submit a PR? If not may I?

[jtepe]

Sure you may :wink:. I think the book as it stands need a lot more content and explanations. Datastructures in Rust are a kind of a special topic because of its ownership rules. I think in the future we should provide implementation examples for other datastructures as well.