Equivalent Code for Iter and IterMut, IterMut does not compile

help
1

Hey there,

I just ran into a borrow-checker problem which I cannot solve. I got an Iter and IterMut implementation for a custom collection type. Both implementation use equivalent code, just the type of the reference is changed. And somehow, the immutable version compiles, while the mutable does not.

I simplified to code, still resulting in basically the same error message (Playground)

/// Iterator over immutable references, compiles
pub struct Iter<'a, T> {
    source: &'a Vec<T>,
    next_index: usize,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(value) = self.source.get(self.next_index) {
            self.next_index += 1;
            Some(value)
        } else {
            None
        }
    }
}

// Iterator over mutable references, does not compile
pub struct IterMut<'a, T> {
    source: &'a mut Vec<T>,
    next_index: usize,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(value) = self.source.get_mut(self.next_index) {
            self.next_index += 1;
            Some(value)
        } else {
            None
        }
    }
}

Error message:

error: lifetime may not live long enough
  --> src/lib.rs:32:13
   |
26 | impl<'a, T> Iterator for IterMut<'a, T> {
   |      -- lifetime `'a` defined here
...
29 |     fn next(&mut self) -> Option<Self::Item> {
   |             - let's call the lifetime of this reference `'1`
...
32 |             Some(value)
   |             ^^^^^^^^^^^ method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

If I comment out IterMut, the code compiles.

I even tried to add the 'a lifetime to self, but that does not seem to change anything. The compiler still tells me, that self is '1

impl<'a, T> Iterator for IterMut<'a, T> where Self: 'a

It would be great, if someone could help me in solving this error. It is not obvious to me, why the mutable version should not work. Thanks in advance :slight_smile:

2

This actually comes up all the time, and the reason is simple. The issue is that you can't extend a lifetime by reborrowing – being able to obtain a &'long (mut) T from a &'short (mut) T would obviously be unsound.

The immutable version only works because immutable references are Clone-able and Copy-able, so you can just copy the inner reference from behind *self without reborrowing.

The usual solution for wrapping iterators that return mutable references is moving into and out of the wrapped field using mem::replace() or similar. (But you'll have to use a slice for that, and split it, instead of indexing into it.) Playground.

2 Likes
3

Thank you for your answer. I am still trying to understand it, but I think I am starting to get it.

My explanation would now be the following, using a practical example, why such a borrow must not be allowed:

If I were allowed to return a reference to an entry inside the mutably borrowed vector with the same lifetime, then I would be allowed to change the vector in the meantime. E.g., clearing the vector would draw the previously returned reference to the entry invalid.

Such a method on the iterator would then be allowed, which would cause dangling references.

impl<'a, T> for IterMut<'a, T> {
    fn clear(&mut self) {
        self.source.clear();
    }
}

Am I on the right track?

4

Thank you for adding the example code.

I found another solution (inspired by the generational-arena crate's IterMut implementation):

(Playground)

pub struct IterMut<'a, T> {
    source: std::slice::IterMut<'a, T>,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        self.source.next()
    }
}
5

Yes; the pattern you tried essentially means duplicating aliasing references. For immutable references that's OK, for mutable references it would be wrong.

6

There are two points to consider.

  1. If you took the line self.next_index += 1 out, what would happen? If the borrow checker allowed this code and you ran next twice, you'd get two mutable references to the same entry. The borrow checker can't rule this out even though we can. Overall, what you are doing is sound (you found another implementation that works in safe Rust) but the borrow checker can't prove that.
  2. The next method has some elided lifetimes. It's taking a &'short mut IterMut<'long, T> and returning a &'long T. The reborrow @H2CO3 is talking about is when you write self.value.get_mut. To return a &'long mut T you need a &'long mut Vec<T> but you only have a &'short mut reference to the latter. You can't move out of it, only reborrow.
2 Likes
7

Okay, thank you. Seems like, that whole reference aliasing thing was something I wasn't consciously aware of, just taking it for granted...

The exact definition of the term is still not completely clear to me, i.e. what exactly does or is it? Is it on borrowing in general, or is it specifically about borrowing from borrowed values?

8
  1. That is another nice proof-by-example, why this should not work. Thank you :slight_smile:
  2. That was the thing I did not understand, that my reference to the vector is not and cannot be 'a, but something shorter.
9

Aliasing references means that more than one reference points to the same place. That's only allowed for immutable references. Mutable borrows must not alias, ie., no two independent mutable references must point to the same place.

Reborrows of mutable references do not alias by construction, because the compiler renders the original reference unusable as long as there are outstanding reborrows. That's exactly what the "can't extend lifetime using a reborrow" part is about. The lifetime of the reborrow is tied to the original, and this is precisely how the compiler can perform the temporary invalidation of the original, and track when the reborrow ends.

In contrast, if what you originally wrote compiled, there would be no such relationship between lifetimes, ie. the mutable reference would be copied, not reborrowed.

1 Like
10

That helps, thank you very much for the explanation and your time.

It is amazing, how simple and complex the borrowing concept is at the same time. Not perfect in allowing everything that's safe, but definitely great in catching all of those pesky edge cases I would not have thought of...

11

Mind you, that would be theoretically impossible.

12

As a meta-point, you should absolutely expect this.

One of the major ways Rust provides its value is the "one &mut or many &s" rule, so the types working differently is fundamentally necessary to giving the guarantees that are Rust's raison d'être.

You might be interested in Splitting Borrows - The Rustonomicon.

1 Like
13 
        let Some((head, tail)) = tmp.split_first_mut() else {
             return None;
        };

ahh! Is this the new, let-else powered, desugaring of the ? operator (on Option)!? :grin:

let (head, tail) = tmp.split_first_mut()?;

(to be fair, your version is more explicit… so does let-else now allow us to make teaching material like this easier to comprehend, by means of not relying on terse complex operators like ?, without needing to fall back to overly/unbearably long code?)

1 Like
14

Yeah, fair enough – I periodically keep forgetting to use ? in Option context :sweat_smile:

1 Like