Got lifetime error for mut iterator and no errors for ref. Why?

help
1

Hi all. I'm playing with iterators trying to get comfortable with them in Rust.
I want to build an iterator for heterogeneous Vector which does unboxing before returning the reference. My code compiles for constant Refs, but fails with strange message about lifetimes for &mut.

It basically says:

error: lifetime may not live long enough
  --> src/bin/debox_ref_and_mut.rs:46:13
   |
38 | impl<'a, T: ?Sized> Iterator for DeBoxIterMut<'a, T> {
   |      -- lifetime `'a` defined here
39 |     type Item=&'a mut T;
40 |     fn next(self: &mut Self) -> Option<&'a mut T> {
   |                   - let's call the lifetime of this reference `'1`
...
46 |             Some(elt)
   |             ^^^^^^^^^ associated function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

What puzzles the most, is that I got Mut version by just copy-pasting and adding the mut keywords in several places. Whats the reason for that lifetime issue?

// This Works
struct DeBoxIter<'a, T: ?Sized> {
    abs: &'a Vec<Box<T>>,
    pos: usize
}

impl<'a, T: ?Sized> DeBoxIter<'a, T> {
    fn from_vec(vec: &'a Vec<Box<T>>) -> DeBoxIter<'a, T> {
        DeBoxIter{abs: vec, pos:0}
    }
}

impl<'a, T: ?Sized> Iterator for DeBoxIter<'a, T> {
    type Item=&'a T;
    fn next(self: & mut Self) -> Option<&'a T> {
        if self.pos >= self.abs.len() {
            None
        } else {
            let elt = self.abs[self.pos].as_ref();
            self.pos += 1;
            Some(elt)
        }
    }
}

// This doesn't
struct DeBoxIterMut<'a, T: ?Sized> {
    abs: &'a mut Vec<Box<T>>,
    pos: usize
}

impl<'a, T: ?Sized> DeBoxIterMut<'a, T> {
    fn from_vec(vec: &'a mut Vec<Box<T>>) -> DeBoxIterMut<'a, T> {
        DeBoxIterMut{abs: vec, pos:0}
    }
}

impl<'a, T: ?Sized> Iterator for DeBoxIterMut<'a, T> {
    type Item=&'a mut T;
    fn next(self: &mut Self) -> Option<&'a mut T> {
        if self.pos >= self.abs.len() {
            None
        } else {
            let elt = self.abs[self.pos].as_mut();
            self.pos += 1;
            Some(elt)
        }
    }
}

Here is the playground link:

2

Immutable references are not unique, and implement Copy. Mutable references are unique, and do not implement Copy; they can still be reborrowed but this is necessarily stricter. This is why simply changing mutability doesn't work:

  • In DeBoxIter, self.abs[self.pos].as_ref() implicitly copies (or, if you like, reborrows — the conclusions are the same) the self.abs reference, producing another &'a Vec<Box<T>> and then deriving a &'a T from that. Because immutable references are not unique, this puts no constraints on further use of the &'a Vec<Box<T>>.

  • In DeBoxIterMut, self.abs[self.pos].as_mut() cannot copy self.abs; it is instead a sequence of reborrows, and for as long as the reborrow exists, to preserve uniqueness, the reference they reborrow from (self.abs) must be held inactive, unusable, until the borrow is released.

    The lifetime rules for these reborrows (that are necessary to ensure soundness) end up saying that the borrow checker must require that a reborrrow of self.abs is a reborrow of self in particular— the mutable reference declared in fn next(self: &mut Self) — not a borrow "with lifetime 'a".

Your next() method is trying to return a reborrow of self, which has an implicit lifetime that is not 'a, so it doesn't match the return type &'a mut T.

Here is a simple example that does compile, with the longest lifetimes you can return in the mutable and immutable case:

pub struct Foo<T>(T);

impl<'a, T> Foo<&'a T> {
    pub fn get<'b>(&'b mut self) -> &'a T { self.0 }
}

impl<'a, T> Foo<&'a mut T> {
    pub fn get<'b>(&'b mut self) -> &'b mut T { self.0 }
}

Note that in the first case, a borrow of lifetime 'a is returned, and in the second case a borrow of lifetime 'b is returned.

Another, higher-level way to look at this problem is that it is stopping you from writing an unsound iterator. Suppose your next() were:

    fn next(self: &mut Self) -> Option<&'a mut T> {
        let elt = self.abs[self.pos].as_mut();
        Some(elt)
    }

I've deleted self.pos += 1; so the iterator returns the same mutable reference every time. But then, I could write DeBoxIterMut::from_vec(...).take(2).collect() and get two simultaneous mutable references to the same thing, which is Undefined Behavior. So, the borrow checker's rules are set up to ensure you cannot do that, because the borrow checker is not nearly smart enough to know that self.pos += 1 makes the code sound (it never cares about indexes at all).

The practical solution to this problem is to call .iter_mut() on the Vec, obtaining a std::slice::IterMut, and store that iterator in your iterator, and call it in your Iterator::next() implementation. That way, you benefit from the work std has already done to provide you with an iterator that works despite the borrow checking rules, and is also sound.

In the end, it does all come down to using unsafe to tell the borrow checker “trust me, I'm doing something that is sound but which you do not understand”, but best practice is to avoid writing any unsafe code you don't have to; no unsafe code is the simplest case, but the second-best option is using unsafe that the Rust standard library developers wrote, and the third best, an existing non-std library that is well tested and reviewed.

5 Likes
3

Usually custom mutable iterators cannot be implemented in safe Rust. This is expected, because the requirement to return unique elements requires code analysis that is beyond what borrow checking can do (it requires reasoning about values like self.pos rather than just scopes).

You can leverage existing safe iterators. For example, this can be done with vec.iter_mut().map(|c| &mut **c).