Issue with lifetimes when implementing `Iterator`

[andrepd]

Hi, I ran into a lifetime issue while implementing Iterator for my type. I narrowed it down to the following MWE:

pub struct Foo ([u32; 10]);

struct FooIter<'a> {
  idx: usize,
  x: &'a Foo,
}

impl<'a> Iterator for FooIter<'a> {
  type Item = &'a u32;

  fn next<'b>(&'b mut self) -> Option<Self::Item> {
    let reference: &'a Foo = self.x;
    todo!()
  }
}

struct FooIterMut<'a> {
  idx: usize,
  x: &'a mut Foo,
}

impl<'a> Iterator for FooIterMut<'a> {
  type Item = &'a mut u32;

  fn next<'b>(&'b mut self) -> Option<Self::Item> {
    let reference: &'a mut Foo = self.x;
    todo!()
  }
}

(Playground)

Why does FooIter::next() compile, but FooIterMut::next() doesn't?

My reasoning is this: FooIter* contain a lifetime parameter 'a. In next, I am taking a mut ref (of lifetime 'b) to FooIter*, therefore this 'b must life at least as long as 'a. Therefore, I can get a reference with lifetime 'a to self.x from a reference to self with lifetime 'b. Also, since the argument is a mut ref, I have an exclusive borrow and so there shouldn't be a problem to get mut references to its fields.

Where am I going wrong? And why does this compile (as expected to me) for the & case but not for the &mut case? Thanks!

[jofas]

I'm pretty sure it is because &'a T is covariant in T while &'a mut T is invariant in T. What the compiler suggests is that 'b must outlive 'a. However the "outliving" doesn't make much sense. If 'b were to outlive 'a, your reference variable could be dangling. So what the compiler really means is that you should provide a &'a mut FooIterMut<'a>. &'a mut T<'a> is a red flag, for it means that you need to pass a mutable reference to T that lives as long as T itself (due to invariance). It also goes against the interface of Iterator, so I don't think your FooIterMut will ever work with a mutable reference to Foo inside. You could have a look at how the standard library solves this in IterMut.
(I'm sure @quinedot will pass this topic by shortly and explain it better than I did )

[quinedot]

You can't reborrow a &'long mut through a &'short &'long mut, because once 'short expires, that would leave you with two aliasing &'long muts, which is undefined behavior. (Despite the spelling, &mut references are exclusive references, not just mutable ones.)

The shared case works not only due to variance, but also because shared references implement Copy -- you can just copy the inner reference out. &mut _ doesn't implement Copy.

If you want to get the &'long mut out, you have to have another &'long mut on hand that you can replace the original with. That's possible when you have &mut [T] for example, because you can just swap in an empty &mut [] that doesn't alias with anything. But in your playground you effectively have an array, and you can't swap in some &mut local_array in there, because it would dangle when the local_array goes out of scope.

You could use a custom DST here...

#[repr(transparent)]
struct Foo<T: ?Sized>(T);
type FooArray = Foo<[u32; 10]>;
type FooSlice = Foo<[u32]>;

...but DST support is still pretty lacking, so to make this really useful you need some unsafe conversions still.

Rust Playground

So you might be better off sticking to built-in slices if possible. They have both more library support, and more magical compiler support (like you can pull a &'static mut [] out of nowhere).

---

You have to use slices (or similar) and not arrays, because you can't both retain your entire &mut [u32; 10] and hand out &mut u32 to the contents. That would be aliasing &muts again (instant UB). So you need something like a slice where you can split the borrow, keeping hold of only those elements you haven't returned yet.

(Or you need a "Lending Iterator" trait, which std doesn't have so far.)

With slices, you use split_first_mut or similar, swap the remainder back in, and return the &mut u32. If you have more problems with the implementation, let us know.