Iterator lifetime error only when using a mutable reference

[Mokuz]

I need to iterate over a collection both mutably and immutably. The immutable version works fine, but mutable does not!

Here's the smallest case which causes the error: IterMut - Rust Playground

struct IterMut<'a, T> {
    r: &'a mut T,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    
    // NOTE: changing the output type to `Option<Self::Item>`
    // the error message changes a bit
    fn next(&mut self) -> Option<&'a mut T> {
        Some(self.r)
    }
}

Here's what I'm trying to do: Playground

[alice]

You are not allowed to have multiple mutable references that overlap in any way, but the returned mutable reference overlaps with the one in the iterator.

[Michael-F-Bryan]

This pattern is often called a Streaming Iterator in Rust and is hard to implement because the iterator has a &mut borrow on the entire collection while also handing out &mut references to part of that data every time the next() method is invoked.

Someone wrote a really well thought out article on the topic which gives a lot more information on why you get the compile errors you are getting.

Solving the Generalized Streaming Iterator Problem without GATs · Lukasʼ Blog

[Phlopsi]

The following pattern will never work out the way you want:

fn …<'a>(&'a self) -> &'a …

You use this pattern here:

fn get_mut<'a>(&'a mut self, x: usize, y: usize) -> Option<&'a mut T> { … }
fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> { … }

The moment you reach out to this pattern, what you'd have to do instead is using a closure with higher-rank trait bounds (HRTB):

fn get_mut(&mut self, x: usize, y: usize, f: F)
where
    for<'scope_only> F: FnOnce(Option<&'scope_only mut T>)
{
    f(self.data.get_mut(y)?.get_mut(x))
}

fn iter_mut(&mut self, f: F)
where
    for<'scope_only> F: FnOnce(IterMut<'scope_only, T>)
{
    f(IterMut {
        grid: self,
        step: 0..AREA,
    })
}

The lifetime 'scope_only defined by for<'scope_only> only lives inside the closure, i.e. it cannot escape the closure.

If you try to change your remaining code to use these functions as I've changed, you'll either see it works or you'll realize, that you're trying to extend the lifetime beyond its scope, which is impossible, e.g. because you're trying to return the lifetime from a function.

You can try to apply the closure trick recursively (move the return type into a closure as an argument) until you either have working code or you get to the point where your code really begs for having the lifetime escape its prison and you cannot put your code inside the closure. The latter case means, you have to search for a different solution, because HRTB can only get you so far.

[quinedot]

It's still possible to get what you want in this case, because slices can be broken up into multiple multiple parts by (for example) slice.split_at_mut(index). (The two returned splices don't overlap so there's no aliasing.)

Getting all the lifetimes and ownership to work out within an iterator is still tricky though. However, here's an alternative that may work for your case (n.b. I didn't rigorously check that I got the indexing order correct):

Rust Playground

[kornel]

The Iterator interface promises that this is always valid code:

let a = iter.next().unwrap();
let b = iter.next().unwrap();
drop(iter);
use_both(a, b);

Your iterator returns exclusive reference self.r twice, which means you can get a and b existing at the same time and both claim to be the only way access to whatever self.r referenced. That's a logical contradiction, so it can't be allowed.

Second problem is that even if your code was technically correct (e.g. you set a flag or used split_at_mut() to ensure you never return same reference twice), the lifetimes aren't precise enough to express that. The borrow checker doesn't look at what the code actually does, only at what it declares via type annotations.

So in practice it means all mutable iterators in Rust have to use unsafe (or reuse an existing mutable iterator that is going to have unsafe in it) to overcome that limitation of the borrow checker, and the programmer is responsible for ensuring that exclusive references remain exclusive.