I'm reading how to write a linked list in rust in this website https://rust-unofficial.github.io/too-many-lists/. Almost everything is fine, but for the following code, I'm confused with the lifetime in this kind of complex scenario. Note the commented code which shows a borrow checker error, and it also shows that iter.next()
will mutably borrow list
. So why is the code as it is now valid even when val_3
is within the duration of val_1
? I understand from the usage of a liked list or almost any iterator that it's definitely the desired behaviour. But after reading lots of materials about lifetime (annotation), I still can't figure out how does the borrow checker work this out. Does it annotate lots of 'a
'b
and 'others
and see whether there is an overlap of the same annotation symbol to work it out? Or does it simply check whether the list
is mutably borrowed while there is another borrow still going on? If it does so via analyzing all the annotations, how can I write the rough annotations by hand despite thinking of all the difficulties doing so? I mean if I can't figure out the non-trivial annotations, how can I know without the hint of the compiler that what I've designed is correct?
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut { next: self.head.as_deref_mut() }
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut cur_link = self.head.take();
while let Some(mut boxed_node) = cur_link {
cur_link = boxed_node.next.take();
}
}
}
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
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
})
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn iter_mut() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.iter_mut();
// let mut iter_2 = list.iter_mut();
// ERROR if uncommented, because "cannot borrow `list` as mutable more than once at a time", and
// the first borrow of `list` is later used in the next line `let val_1 = iter.next();`
let val_1 = iter.next();
let val_2 = iter.next();
let val_3 = iter.next();
if let Some(val) = val_3 {
*val = 10;
}
assert_eq!(val_1, Some(&mut 3));
}
}