Lifetime Confusion for iterator

Question

I am new to Rust and currently have been following Learning Rust With Entirely Too Many Linked Lists examples. Before section IterMut everything makes sense to me. Yet when implementing IterMut(in a differrnt way from the tutorial), I got totally confused by lifetime mechanism in Rust. Here is the case, first I'd just define the stack to be implemented:

pub struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

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

Ok then when I try to implement iterator in the following way:

pub struct IterMut<'a, T>{
    this: &'a mut Link<T>
}

impl<T> List<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            this: &mut self.head
        }
    }
}

impl<'a, T> Iterator for IterMut<'a, T>{
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(node) = self.this {
            Some(&mut node.elem)
        } else {
            None
        }
    }
}

It won't compile, the result says:

error: lifetime may not live long enough
impl<'a, T> Iterator for IterMut<'a, T>{
    -- lifetime `'a` defined here
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
            - let's call the lifetime of this reference `'1`
        if let Some(node) = self.this {
            Some(&mut node.elem)
            ^^^^^^^^^^^^^^^^^^^^ returning this value requires that `'1` must outlive `'a`

Originally, I implement function next in this way, using as_mut and map:

// function body in the fn next
self.this.as_mut().map(|node|{
    self.this = &mut node.next;
    &mut node.elem
})

This also triggers compilation error (incompatible lifetime).

Therefore I wonder what is going on here, shouldn't self in fn next have the same lifetime as IterMut ('a)? And is there any workaround for this situation?

Answer 1

The principal problem lies in trying to take a reference to the whole head. While that reference lives, you can't hand out mutable references to anything inside it. You only need access to the Node that's inside head, though. So first, we refactor IterMut to only keep a reference into any given Node:

pub struct IterMut<'a, T>{
    this: Option<&'a mut Node<T>>
}

Now, to get that out of the head we use the convenience method as_deref_mut() that Option provides. It just gives us a mutable reference to whatever was inside it (if anything):

impl<T> List<T> {
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            this: self.head.as_deref_mut(),
        }
    }
}

Now, 'a is only tied to that Node and we can do what we want with it, like takeing it:

impl<'a, T> Iterator for IterMut<'a, T>{
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(node) = self.this.take() {
            self.this = node.next.as_deref_mut();
            Some(&mut node.elem)
        } else {
            None
        }
    }
}

And we can simplify that with a simple map call:

impl<'a, T> Iterator for IterMut<'a, T>{
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.this.take().map(|node| {
            self.this = node.next.as_deref_mut();
            &mut node.elem
        })
    }
}