The key thing is that you need to be able to somehow extract an Option<&'a mut T> from a &'b mut IterMut<'a, T>.
To understand why IterMut<'a, T> := &'a mut Link<T> can't work, you need to understand what exactly you can do with a mutable reference. The answer, of course, is almost everything. You can copy data out of it, change its value, and lots of other things. The one thing you can't do is invalidate it. If you want to move the data under the mutable reference out, it has to be replaced with something of the same type (including lifetimes).
Inside the body of next, self is (essentially) &'b mut &'a mut Link<T>. Unless we know something about T (and we can't in this context), there's simply no way to produce something of type &'a mut Link<T> from this. For example, if this were possible in general, we'd be able to do
fn bad<'a, 'b, T>(_x: &'b mut &'a mut T) -> &'a mut T {
todo!()
}
fn do_stuff<'a>(x: &'a mut i32, y: &'a mut i32) {
// lots of stuff that only works if x and y don't alias
*x = 13;
*y = 42;
}
fn main() {
let mut x: &mut i32 = &mut 0;
let y: &mut i32 = {
let z: &mut &mut i32 = &mut x;
bad(z)
};
// `x` and `y` are aliasing mutable references
// and we can use both at once!
do_stuff(x, y);
}
(playground link)
The point is that if we were able to borrow something for a short (generic) lifetime 'b and return something that allowed modification during the longer lifetime 'a, we'd be able to use multiple short lifetimes (shorter than 'a and non-overlapping) to get multiple mutable references with the same lifetime 'a.
This also explains why the immutable version works. With immutable references, it's trivial to go from &'b &'a T to &'a T: just deference and copy the immutable reference. By contrast, mutable references don't implement Copy.
So if we can't produce a &'a mut Link<T> from a &'b mut &'a mut Link<T>, we certainly can't get an Option<&'a mut T out of it either (other than None). (Note that we can produce a &'b mut Link<T> and hence an Option<'b mut T>. That's what your code does right now.)
So what does work? Remember our goal is to be able to produce an Option<&'a mut T> from a &'b mut IterMut<'a, T>.
If we were able to produce a IterMut<'a, T> unconditionally, we'd be able to (temporarily) replace self with it and hence be able to directly access the IterMut<'a, T> associated to our list.
// This actually type-checks!
fn next<'b>(&'b mut self) -> Option<&'a mut T> {
let mut temp: IterMut<'a, T> = todo!(); // obviously this won't work
std::mem::swap(&mut self.0, &mut temp.0);
temp.0.as_mut().map(|node| {
self.0 = &mut node.next;
&mut node.elem
})
}
(playground link)
The easiest way to set things up so that this all works is by transposing IterMut<'a, T> a bit. Rather than having the mutable reference outside the option, make it inside! Now you'll always be able to produce an IterMut<'a, T> with None!
struct IterMut<'a, T>(Option<&mut Box<Node<T>>>);
Translating next, we get
fn next<'b>(&'b mut self) -> Option<&'a mut T> {
let mut temp: IterMut<'a, T> = IterMut(None);
std::mem::swap(&mut self.0, &mut temp.0);
temp.0.map(|node| {
self.0 = node.next.as_mut();
&mut node.elem
})
}
More idiomatically, we can use Option::take rather than std::mem::swap (This is mentioned earlier in Too Many Linked Lists).
fn next<'b>(&'b mut self) -> Option<&'a mut T> {
self.0.take().map(|node| {
self.0 = node.next.as_mut();
&mut node.elem
})
}
(playground link)
This actually ends up being slightly different than the implementation in Too Many Linked Lists. That implementation removes the double indirection of &mut Box<Node<T>> and replaces it with simply &mut Node<T>. However, I'm not sure how much you gain since that implementation still has a double deref in List::iter_mut and Iterator::next.
