Firstly, Kudos to Gankro for his extremely insightful tutorial Learning Rust with Entirely Too Many Linked Lists. After his "Ok Stack" chapter, I waited a day or two and tried to implement everything from scratch myself and I ended up doing iterators differently, which worked fine until I got to the mutable iterator, which has been shockingly insightful to struggle with, but I'm stuck.
Gankro's mutable iterator reproduced below (in fully-compilable form) stores a borrowed reference to a linked list Node.
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
pub struct IterMut<'a, T: 'a> {
next: Option<&'a mut Node<T>>,
}
impl<T> List<T> {
fn iter_mut(&mut self) -> IterMut<T> {
IterMut { next: self.head.as_mut().map(|node| &mut **node) }
}
}
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_mut().map(|node| &mut **node);
&mut node.elem
})
}
}
In contrast, my implementation below stores a borrowed reference to the reference to the node. Yea, this sounds silly in hindsight, but failures of previous incarnations of it (eg. trying next: &'a mut Link<T>) which worked fine for immutable-reference iterators have been very insightful about lifetime requirements for mutable iterators. So I just want to run this through to the end.
pub struct IterMut<'a, T: 'a> {
next: Option<&'a mut Link<T>>, // (Link<T> = Option<Box<Node<T>>>)
}
impl<T> List<T> {
fn iter_mut(&mut self) -> IterMut<T> {
IterMut { next: Some(&mut self.head) }
}
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().and_then(|link| {
// link has type: &mut Link<T> (= &mut Option<Box<Node<T>>>)
link.as_mut().map(|node| {
self.next = Some(&mut node.next);
&mut node.elem
})
})
}
}
The code above gives the following error
error: cannot borrow `node` (here through borrowing `node.elem`) as mutable more than once at a time
which is a bit perplexing given that Gankro's implementation successfully does similar mutable borrows to two disjoint sub-fields. So why can't mine?
