Lifetime error in implementation of (mutable) `Iterator` for custom linked list

Question

I'm following the tutorial Learn Rust With Entirely Too Many Linked Lists to learn Rust. The aim is to learn the various aspects of Rust by implementing various levels of linked lists. I'm stuck at implementing the (mutable) Iterator trait (here). These are my type definitions:

pub struct List<T> {
    head: Link<T>,
}
struct Node<T> {
    elem: T,
    next: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;

pub struct IntoIter<T>(List<T>);
pub struct Iter<'link, T>(&'link Link<T>);
pub struct IterMut<'link, T>(&'link mut Link<T>);

The tutorial has the following definitions for Iter and IterMut (everything else is the same as above):

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

So the difference in the iterator structs is that rather than storing optional (mutable) reference to nodes, as in the tutorial, I'm storing references to links instead.

Here is the implementation of the Iterator trait as in the tutorial:

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

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

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

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

And here is my implementation of the Iterator trait as per my type definitions:

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

    fn next(&mut self) -> Option<&'link T> {
        self.0.as_ref().map(|boxed_node: &'link Box<Node<T>>| {
            self.0 = &boxed_node.next;
            &boxed_node.elem
        })
    }
}

impl<'link, T> Iterator for IterMut<'link, T> {
    type Item = &'link mut T;

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

Here is the error on compiling my implementation:

error: lifetime may not live long enough
  --> src/second.rs:96:9
   |
92 | impl<'link, T> Iterator for ListIterMut<'link, T> {
   |      ----- lifetime `'link` defined here
...
95 |     fn next(&mut self) -> Option<Self::Item> {
   |             - let's call the lifetime of this reference `'1`
96 |         self.0.as_mut().map(|boxed_node| {
   |         ^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'link`
   |
help: consider adding 'move' keyword before the nested closure
   |
96 |         self.0.as_mut().map(move |boxed_node| {
   |                             ++++

error[E0500]: closure requires unique access to `self.0` but it is already borrowed
  --> src/second.rs:96:29
   |
92 | impl<'link, T> Iterator for ListIterMut<'link, T> {
   |      ----- lifetime `'link` defined here
...
96 |         self.0.as_mut().map(|boxed_node| {
   |         ---------------     ^^^^^^^^^^^^ closure construction occurs here
   |         |
   |         borrow occurs here
   |         argument requires that `*self.0` is borrowed for `'link`
97 |             self.0 = &mut boxed_node.next;
   |             ------ second borrow occurs due to use of `self.0` in closure

If I compare my implementation and the tutorial's, then I guess what I'm missing is a version of Option::take for mutable references. I'm not even sure such a thing exists. Here are my queries:

1. Does a version of Option::take for mutable references exist?
2. I'm not able to understand the lifetime error.
3. How do I fix my code without having to change my type definitions (while staying in safe-land)? Or is there no way to do that with the current type definitions?

To understand the lifetime error, I tried desugaring the code, adding explicit lifetimes everywhere, but I'm still not able to understand what's going wrong. Honestly, I'm still struggling with lifetimes a bit. I think I understand it and then something comes and knocks me off.

Answer 1

This is indeed the problem.

Does a version of Option::take for mutable references exist?

No and yes. No, because something has to stay in place, or otherwise a panic could expose uninitialized memory. And yes, because you can put something else in place (quite hard in this case) or just handle panics differently.

I'm not able to understand the lifetime error.

The essence of it is that &'short mut &'long mut T (in this case, &mut self where Self = IterMut<'link, T> can only give you &'short mut T, not &'long mut T. Which means that the references you get from next and elem do not have the expected lifetime.

How do I fix my code without having to change my type definitions (while staying in safe-land)?

I'll leave that to you, with the information provided above.