Mutable iterator - Creates a temporary which is freed while still in use

[BoogalooJB]

I try to implement a mutable iterator over a linked list. I first read the too many linked list tutorial and then tried it myself slightly differently, but it seems that the difference is in fact very important.

In the tutorial, the iterator keeps track of its position with Option<&'a Node<T>> while I tried to do it with &mut Option<Box<Node>> (because I had a type alias called Link used in the list definition, and it seems natural to me to say that the position was indeed a Link).

Here is a minimal example:

type Link = Option<Box<Node>>;
struct Node {
    val: u8,
    next: Link,
}

struct IterMutWorking<'a> {
    next: Option<&'a mut Node>,
}

fn next_working<'a>(iter: &'a mut IterMutWorking<'a>) -> Option<&'a mut u8> {
    iter.next.take().map(|node| {
        iter.next = node.next.as_mut().map(|node| &mut **node);
        &mut node.val
    })
}

struct IterMutNotWorking<'a> {
    next: &'a mut Link,
}

fn next_not_working<'a>(iter: &'a mut IterMutNotWorking<'a>) -> Option<&'a mut u8> {
    iter.next.take().as_mut().map(|node| {
// ^^^^^^^^^^^^^^^^ creates a temporary which is freed while still in use   
        iter.next = &mut node.next;
        &mut node.val
    })
}

I think I understand the message, but I don't really understand why it's so different from the tutorial solution.

I also tried to get rid of take (see playground link), but then I have a "cannot infer appropriate lifetime for autoref".

Here some code with more context on the playground.

Thank you for reading.

[Yandros]

Hello @BoogalooJB, and welcome to this forum

I'm afraid your "minimal example" does not really correspond to the issue from the Playground, so we'll see them both.

The Playground problem

Basically there are two lifetimes at play here:

• The lifetime 'a of the borrow of your list by the iterator, which appears in &'a mut Node directly; let's call it 'iter.

• The (short) (unnamed) lifetime '_ of the &'_ mut borrow over the iterator itself; let's call it 'next.

The only thing we know about both lifetimes is that 'iter must be at least as "big" as 'next, i.e., 'iter ≥ 'next, noted 'iter : 'next (and from a purely conservative point of view, we can even consider the "worst" case scenario of 'iter > 'next).

So, the input to the next() function is a &'next mut Iter<'iter> i.e.,

• a &'next mut (Option<&'iter mut Node>) in the tutorial,

• a &'next mut (&'iter mut Option<Box<Node>>) in your version,

and you want to return a &'iter mut u8.

As you can see, we have "nested" borrows, which, "by default", are un-nested / collapsed by reborrowing: you can get a direct borrow but with the shorter (outer) lifetime:

• a &'next mut (&'iter mut Something) can be reborrowed as &'next mut Something. This happens implicitly, but you can "annotate" this happening for readers using &mut ** as the "explicit reborrowing".

So, in your example, one must be careful to avoid reborrowing, since you'd end up with the short 'next lifetime rather than the longer 'iter one.

The other option, when nested borrows are involved, is to use other properties of the borrows:

• For shared references (not your case):

  given that T = &'iter _ is Copy, you can go from a &'next T to a T by simple dereference, i.e., from &'next (&'iter _) to &'iter _. (This is why these reborrowing porblems only truly appear with &mut references: Copying can also be done implicitly (by Deref coercion), so Rust will use that rather than reborrowing).

• For unique / excusive and thus mutable references:

  Mutation allows you to obtain a T out of &'next mut T by replaceing the pointee T with another instance. With T = &'iter mut _, you do get the wanted &'iter mut _ out of &'next (&'iter mut _) by putting a dummy T = &'iter mut _ in its stead.

But you'll realise that such "dummy" values are not easy to come by. That's where Option comes into play: T = Option<_> has always a trivial dummy value of None.

So, out of a &'next mut (Option<&'iter mut _>), you just replace the Option with a None, and get the previous Option<&'iter mut _>. This is what the tutorial did.

Now, let's look at your case: you had a &'next mut (&'iter mut Option<Box<Node>>).

To be able to replace the pointee &'iter mut Option<Box<Node>>, you'd need to be able to forge an instance of that type out of thin air, which you cannot do (unless you start leaking memory, which isn't a real solution). Hence the problem.

---

The "minimal example"

here you are using the same lifetime 'a for the next() call and the iterator itself, so with our notation you have a situation where 'next = 'iter:

fn next_not_working<'a>(iter: &'a mut IterMutNotWorking<'a>) -> Option<&'a mut u8> {
-   iter.next.take().as_mut().map(|node| {
+   iter.next       .as_mut().map(|node| {  
-       iter.next = &mut node.next;
        &mut node.val
    })
}

solves your lifetime issue. Indeed, by doing .take(), you were creating a temporary and the rest of your work was based on a 'local borrow of this temporary, so we were back at the previous case but with 'local being even smaller than 'next.

You will notice that I have removed the line that sets up the iterator for the next iteration.
Indeed, since we have reborrowed &'a mut ... &'a mut _ as a &'a mut _, it means that iter.next is borrowed while the returned value exists / is used, which implies it is borrowed beyond the return point of this function. So you will not be able to touch iter.next to "fix it".

And anyways, there is no point in so doing, because it will be impossible to call next two times in a row given the signature, since you require that the lifetime of the 'next borrow be as big as the lifetime of the iterator itself, meaning you will not be able to call it a second time.

So, this is one of the cases where we have defined a function that compiles, but which is not really usable in practice, or at least one that does not do what we want it to do. For it to be usable, you need a distinct lifetime parameter for the next call:

- fn next_not_working<       'iter>(iter: &'iter mut IterMutNotWorking<'iter>) -> Option<&'iter mut u8> {
+ fn next_not_working<'next, 'iter>(iter: &'next mut IterMutNotWorking<'iter>) -> Option<&'iter mut u8> {

and we are back to your initial case.

---

For the sake of completeness know that there is an interesting signature to write, which does not correspond to Iterator::next, but to StreamingIterator's:

fn streaming_next<'next, 'iter>(iter: &'next mut IterMutNotWorking<'iter>) -> Option<&'next mut u8> {

this is a signature that says that the yielded value can only live as long as the 'next borrow. This means that as long as you are done with the yielded value, you are allowed to call streaming_next() again (this is different from iterator::next(), whose values can all be .collected together and coexist).

[BoogalooJB]

Thank you very much for this very clear explanation and the additional information provided along the way.