Why does IterMut have the wrong lifetimes?

help
1

I have a simple and straightforward implementation of an iterator over a slice:

struct Iter<'a, T> {
    slice: &'a [T],
}

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

    fn next(&mut self) -> Option<Self::Item> {
        let (first, rest) = self.slice.split_first()?;
        self.slice = rest;
        Some(first)
    }
}

The Iter struct contains a reference to a slice of T and iterates by splitting off the first element of the slice via <[T]>::split_first, setting self.slice to the remaining elements, and returning the reference to the first element inside Some. Very straightforward and understandable. Compiles fine and functions correctly.

But when I go to implement an iterator over mutable references to the elements of a slice using the same pattern, I get a lifetime error:

struct IterMut<'a, T> {
    slice: &'a mut [T],
}

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

    fn next<'next>(&'next mut self) -> Option<Self::Item> {
        let (first, rest) = self.slice.split_first_mut()?;
        self.slice = rest;
        Some(first) // Error: Lifetime may not live long enough
    }
}

(playground)

The borrow checker complains that the Iterator::next method was supposed to return data with lifetime 'a but it is returning data with lifetime 'next.

Can someone provide an in-depth explanation of exactly what is going on here? Why does the return value of IterMut::next have lifetime 'next and not 'a? Why does IterMut::next have this problem but Iter::next does not? What exactly is different about &mut T compared to &T that causes this lifetime error in the &mut T case?

I also understand that the lifetime error in the IterMut case can be solved by taking the value out of self.slice with std::mem::take and then splitting that to get the reference to the first element like so:

 impl<'a, T> Iterator for IterMut<'a, T> {
     type Item = &'a mut T;
 
     fn next<'next>(&'next mut self) -> Option<Self::Item> {
-        let (first, rest) = self.slice.split_first_mut()?;
+        let slice = std::mem::take(&mut self.slice);
+        let (first, rest) = slice.split_first_mut()?;
         self.slice = rest;
         Some(first) // Error: Lifetime may not live long enough
     }
 }

Why does this work? Can you explain this fix and how it is different from the failing implementation above?

2

We can simplify the description of the situation by ignoring struct IterMut and supposing that you're working on an &'next mut &'a mut [T]. Given that notation, the key difference between the two cases is:

  • Shared/immutable references can be copied. This means that, given a &'next mut &'a [T], you can copy out the referent to get another &'a [T]. This happens when you call split_first().

  • Exclusive/mutable references cannot be copied, only moved or reborrowed. When a reference is reborrowed, you get a reference whose lifetime does not outlive that borrow. Thus, the longest lifetime you can get out of an &'next mut &'a mut [T] by reborrowing is an &'next mut [T].

    If it were possible to get an &'a mut [T] out of &'next mut &'a mut [T] without takeing it, then you would be able to obtain multiple &'a mut [T] at the same time, breaking the exclusiveness of the reference.

Why does [std::mem::take] work?

take maintains exclusiveness by giving you the &'a mut [T] without duplicating it, and leaving the referent of the &'next mut &'a mut [T] as a placeholder empty slice reference (length 0) that provides no access to any memory. Thus, there is still only one reference that has any access to the actual [T], and exclusiveness is not broken.

3 Likes
3

I think it’s ultimately just the limits of how “smart” the borrow checker is that determine why the code is rejected without mem::take.

Basically… if you write self.slice.split_first_mut(), you need the &mut [T] reference out of the IterMut struct. However you don’t own that struct, so you can’t move out of it, unless by placing back something else (which is what mem::take does). The code still compiles though because of implicit re-borrowing. As @kpreid explained above, in general, by re-borrowing one mutable reference from behind another mutable-reference indirection/borrow, then you only get a re-borrow of the shorter (outer-borrow) lifetime.

However, in this particular case, IMHO the borrow checker could in principle be made smart enough to realize that as soon as the re-borrowed field is overwritten (with self.slice = rest) the re-borrow that we had gotten earlier could now safely be considered to be as long-lived as the inner lifetime actually.[1] For such reasoning to be sound, it probably matters that the access to the .slice field was direct (without any customizable DerefMut) and it definitely matters that the slice’s datatype (&mut [T]) doesn’t have any destructor code (“Drop glue”) that could access its value upon being over-written with the self.slice = rest; assignment.

  1. An additional degree of “trickyness” comes from the fact that this extended-lifetime knowledge is then what’s needed to accept the RHS value of the very same assignment operation as “sufficiently long lived”. An assignment consists logically of first a step of “clearing” the previous value out of the destination, then writing the new value, so in this order it’s actually not the wrong way around, and you first get the lifetime being extended, and then do the writing that requires a sufficiently long lifetime. ↩︎

3 Likes
4

Can you explain what reborrowing a &mut T is and why it happens here? The way I see it, self.slice is a &'a mut [T] as per the struct definition, and so <[T]>::split_first_mut should return a Option<(&'a mut T, &'a mut [T])>. Why is self.slice not moved into split_first_mut?

5

Can you explain what reborrowing a &mut T is and why it happens here?

Reborrowing is when you borrow part or all of the referent of a reference, creating a new reference whose lifetime is dependent on the original reference and, for exclusive references, temporarily prohibiting access to the original reference until the lifetime of the reborrow expires. Reborrowing very often happens implicitly.

Why is self.slice not moved into split_first_mut ?

You cannot move out of the referent of an &mut, only copy, borrow, or swap. self is an &mut IterMut, so you don't own the IterMut and cannot move out of its slice field.

1 Like
6

That assumes that split_first_mut won't cause an unwind though, no?

7

Ok, so let me try to get the compiler's typing logic straight when it executes this line from IterMut::next:

let (first, rest) = self.slice.split_first_mut()?;
  1. Attempt to call <[T]>::split_first_mut which receives &mut [T]
  2. Type &mut [T] does not implement Copy therefore the value passed in must be moved into split_first_mut.
  3. self.slice is a &'a mut [T] so it has the correct type, but it is not owned by the current function because self is just a reference. Therefore self.slice cannot be moved into split_first_mut.
  4. The only thing left to do is "reborrow" self.slice, which means to create a new value of type &'next mut [T] which points at the same [T] value self.slice does, but which only lives for lifetime 'next instead of 'a because the self is a &'next mut IterMut and that's just how reborrowed lifetimes work?
  5. Pass the reborrowed value created in step 4 to <[T]>::split_first_mut
  6. Since the value passed to split_first_mut is of type &'next mut [T], first is of type &'next mut T as per the function signature (fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])>) and the lifetime elision rules.
  7. Since the return value is Some(first) it has type Option<&'next mut T> but the function signature of next declares the return type as Option<&'a mut T>, the compiler message states: method was supposed to return data with lifetime 'a but it is returning data with lifetime 'next.

Is this an accurate and complete understanding of how this works? If so, do you know where I might read more about this behavior/concept? I found an explanation of this notably absent from both The Book and The Nomicon, which I think is fairly unfortunate because I think it would be pretty hard to write a Rust project with a real-word use case without running into this.

8

That all looks about right to me.

Yes, it is unfortunate. The trouble is, nobody’s actually put the work in to write that documentation.

1 Like
9

Hmm ok. Thanks so much for your help in allowing me to understand this. Maybe I'll take a stab at writing some documentation explaining this.