Mutable references' lifetimes in IterMut

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));
    }
}

An important aspect of Rust's borrow checking is that it is entirely function-local. So, it is always possible to borrow-check each function in isolation, given the signatures of all the functions it calls.

Let's look at the commented out part first:

let mut list = List::new();

let mut iter = list.iter_mut();
let mut iter_2 = list.iter_mut();

dbg!(iter);
dbg!(iter_2);

The signature of iter_mut is the following:

fn iter_mut(&mut self) -> IterMut<'_, T>

Let me write out the elided lifetimes:

fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> 

What this is saying is that:

            For an arbitrary lifetime 'a the caller chooses...
            |    ...it borrows the List given as argument mutably for 'a
            |    |                        ...and returns an IterMut<'a, T> (which means that the IterMut lives at most as long as 'a)
            |    |                        |
            vv   vv                       vv
fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> 

The compiler will then remember these constraints, and checks whether it is possible to find concrete lifetimes that satisfy all constraints.

So, looking back at our example

let mut list = List::new();

let mut iter /* : IterMut<'1, i32> */ = list.iter_mut(); // Let's call the lifetime of this borrow '1
let mut iter_2 /* : IterMut<'2, i32> */ = list.iter_mut(); // Let's call the lifetime of this borrow '2

dbg!(iter); // '1 must be alive here
dbg!(iter_2); // '2 must be alive here

...we can see that there is no way to choose lifetimes '1 and '2 such that they do not overlap, and we get our error.

Now check the case that compiles:

let mut list = List::new();
list.push(1); list.push(2); list.push(3);

let mut iter = list.iter_mut();

let val_1 = iter.next();
let val_2 = iter.next();
let val_3 = iter.next();

The signature of next is the following:

fn next(&mut self) -> Option<Self::Item>

Expanded and unelided:

fn next<'b>(self: &'b mut IterMut<'a, T>) -> Option<&'a mut T>

Note that here we borrow the input for 'b, but the returned reference lives for 'a, the lifetime inside IterMut!

This means that the borrow 'b can be arbitrarily short, and the reference we get still lives as long as our iterator!

This is one of the weirder things about std's Iterator trait: it requires that all returned values must have the same type, and so must have the same lifetime associated with them. This is what makes methods like collect work, so all the returned values can be live at the same time.

The implementors of the Iterator trait can make this work my making sure their iterator never repeats values: all returned borrows must be disjoint.

With this in mind, let's look at how our implementation of Iterator actually works:

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

    fn next<'b>(self: &'b mut IterMut<'a, T>) -> Option<&'a mut T> {
        self.next.take().map(|node| {
            self.next = node.next.as_deref_mut();
            &mut node.elem
        })
    }
}

A big part of the magic happens inside Option::take:

fn take(&mut self) -> Option<T>

Or, in our case:

fn take<'b>(self: &'b mut Option<&'a mut Node<T>>) -> Option<&'a mut Node<T>>

The reason this works is that it moves the value out of the input, leaving a None in its place, so it doesn't need to keep it borrowed after the swap is over.

The other part of the magic is happening inside the map closure. Both node.next and node.elem are borrowed mutably for 'a in an overlapping manner! What makes that work?

The Rust compiler is smart enough to figure out that different fields of the same struct are disjoint, and allows us to "split" a single borrow of the whole struct into separate borrows of each field. This is where it's "proven" to the compiler, that we indeed didn't create two references to the same value.

5 Likes

(I will use '1, '2 etc. to refer to lifetime variables which are introduced by the compiler and not present in the source code.)

The iterator iter has type IterMut<'1, i32>, which implements Iterator<Item = &'1 mut i32>. Therefore, its next()'s signature with the generics substituted is essentially:

fn next<'2>(&'2 mut self) -> Option<&'1 mut i32>

Notice that '2 is not used in the output type. Therefore, while calling next() does take a borrow of iter(), there is no obligation for that borrow to last longer than the call. Therefore, you can call next() repeatedly (with a distinct borrow each time, &'3 mut Self, &'4 mut Self, ...), and obtain many &'1 mut i32s.

The reason that adding a second .iter_mut() fails is because that signature does link the borrow of list to the returned IterMut type.

You can think of it roughly like this:

  • Every time the & or &mut operator is used (including implicitly via method call auto-ref or reborrowing of an &mut), introduce a new lifetime variable for the lifetime which that borrow has.
  • Every time a value whose type has a lifetime (such as &'lt mut i32 or, just the same, `IterMut<'lt, i32>) is used, a constraint is recorded, specifying such that the lifetime must be valid at that instant, and it might be required to be equal to, outlive, or outlived by some other lifetime variable.
  • Every time a previously-borrowed value is borrowed, moved, or dropped, add a constraint that its previous borrow’s lifetime must end by then (unless both things are & borrows which can coexist).
  • A borrow checking error is produced if and only if those constraints, considered as a whole, contradict each other.

You could try following the procedure above: every time there is an & in the program, implicit or explicit, add a lifetime name for it; then look at where it is used, and determine how long it therefore must live. This will be tedious.

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?

Well, for one thing, the compiler is there to help you. And, it is even occasionally possible that you can write a program which is sound in principle, but which the compiler will reject (most notoriously, NLL Problem Case #3) because it isn't capable of all reasoning one might want it to perform. So, in practice, you have to write a program that works with the compiler you've got, not just a program that is sound.

Other than that, I think Rust programmers largely work on experience of patterns that work and patterns that don't. You don't need to calculate the steps by which a borrow conflict is detected in order to know that adding let mut iter_2 = list.iter_mut(); will be rejected, and must be rejected for soundness.

6 Likes

Good tools really help. Using a good IDE (e.g., vscode or an editor like vim or emacs) with LSP/Rust-Analyzer integration will show the compiler errors immediately and make them easy to read. I often use this immediate feedback to quickly do experiments to find the best solution to a lifetime error.

1 Like

Thank you! That's a really useful and concise way of thinking about it.

Based on both your explanations, I think that if there are multiple same lifetime annotations (such as many 'a s) at the same time, it's OK. But if one function call generates a '1 and recalling it generates a '2, and '1 '2 overlaps with each other, it's an error. Previously I thought the same lifetime annotation at multiple places will cause an error, but now I understand that different calls of a function have different lifetime annotations, so that they can generate an error if they violate the rules; and the same annotation definitely won't induce any borrow checker error.

Thank you both for your explanations, they make a thorough answer together!

2 Likes

This is important note for me because it's then much easier to work out the annotation "by hand".

1 Like

These rules are a great reminder, because I just find out it's easy for me to get confused. Thanks a lot!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.