Why does changing mutability cause lifetime errors?

help
1

I have a program that does not compile because a return value has the wrong lifetime, and I cannot change the lifetime it came from because the method becomes incompatible with the Iterator trait. The most confusing part is that a version of the exact same code with non-mutable references compiles perfectly fine.
What is the difference, and what can I do to fix this?

Mutable version that does not compile:

pub struct IterMut<'a, T> {
    next: &'a mut List<T>
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if let Cons(val, next) = self.next {
            self.next = next.as_mut();
            Some(val)
        } else { None }
    }
}

List<T> definition:

pub enum List<T> {
    Cons(T, Box<List<T>>),
    Nil
}
2

This is really a loaded question. Let's unwrap it one piece at a time:

  1. This code is rejected because next cannot return a value with a lifetime that is "disconnected" from the lifetime in &mut self (the error message calls this lifetime '1 as in &'1 mut self). There is no trait bound indicating that '1: 'a.

  2. The general form of this API is known as a "lending" or "streaming" iterator. E.g. an iterator that lends contents that it owns. You can read more about this pattern (and problems and workarounds) in:

  3. Don't write a linked list. The standard library already has one. There's a whole book explaining why this is a difficult task.

    • This is probably Mistake number 3 from the excellent list of how not to learn Rust.
1 Like
3

Immutable references can be copied (and cloned), mutable references cannot. You can only return a mutable reference from behind another mutable reference if you re-borrow it, but the re-borrow cannot live longer than its "source".

The Iterator trait requires that the lifetime of the Item be unrelated to the lifetime of Self, otherwise it would not be possible to handle multiple items simultaneously (e.g. collect()). This can be achieved by copying out immutable references from behind an iterator, but it doesn't work with mutable references.

And indeed, if you think about it: handing out multiple simultaneous mutable references to nodes of a linked list would be unsound if it were possible (a parent transitively points to all of its children, so a mutable parent reference co-existing with mutable child references would lead to mutable aliasing, hence UB).

4 Likes
4

You can't reborrow a &'short mut &'long mut X as a &'long mut X, so when writing iterators that return &mut, you need some way to get the &'a mut X "out from behind" the &mut self.

Option is one way to do that:

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

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

    fn next(&mut self) -> Option<Self::Item> {
        let list = self.next.take()?;
        match list {
            List::Cons(item, bx) => {
                self.next = Some(&mut *bx);
                Some(item)
            }
            List::Nil => {
                None
            }
        }
    }
}

(There's no overrlapping &mut as it splits an occupied &mut List [n items] into a &mut T and a &mut List [n-1 items], never reusing the longer &mut List.)

3 Likes
5

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.