Iterator of mutable iterators is hard!

Hello!

I am facing the infamous IterMut is hard issue and need some of your help!

Basically:

  • A trait method gives me an iterator -> I can give implementors an iterator of thoses
  • A trait method gives me an iterator with &mut items -> I cannot provide Iterator<Item = Iterator<Item = &mut T>

I read this and that to no avail. Those technique applies well in type land but not in trait land in this context.

playground

// I am working with 2D grids

// The grid cell type,
// also Copy in real life
type Cell = u8;

// ======================== //
// The non-mutable world    //
// where everything is fine //
// ======================== //

// I have a trait for 2D grid types
trait Grid<'a>: Sized {
    type Row: Iterator<Item = Cell>;

    // 2D, I told you
    fn size(&'a self) -> (u16, u16);

    // Implementors will give an iterator for a given row,
    // potentially cropped
    fn row(&'a self, row: u16 /* , ... */) -> Self::Row;

    // With that, I want to impl an iterator of thoses.
    fn rows(&'a self /* , ... */) -> Rows<'a, Self> {
        // Ignoring the crop
        Rows { grid: self }
    }
}

// Having an non-mutable iterator is pretty straightforward
// and works great

struct Rows<'a, T> {
    grid: &'a T,
    // Omitting crop info
}

impl<'a, T: Grid<'a>> Iterator for Rows<'a, T> {
    type Item = <T as Grid<'a>>::Row;

    fn next(&mut self) -> Option<Self::Item> {
        // Lets ignore bound checks and everything
        
        // Compiler happy, me happy
        Some(self.grid.row(0))
    }
}

// ===================== //
// The mutable world     //
// where things go OWWWW //
// ===================== //

// Same, but with mutable iterator
trait GridMut<'a>: Sized {
    type RowMut: Iterator<Item = &'a mut Cell>;

    fn row_mut(&'a mut self, row: u16) -> Self::RowMut;

    fn rows_mut(&'a mut self) -> RowsMut<'a, Self> {
        RowsMut { grid: self }
    }
}

// However, the mutating iterator is another beast

struct RowsMut<'a, T> {
    grid: &'a mut T,
}

impl<'a, T: GridMut<'a>> Iterator for RowsMut<'a, T> {
    type Item = <T as GridMut<'a>>::RowMut;

    fn next(&mut self) -> Option<Self::Item> {
        // Cannot infer an appropriate lifetime
        Some(self.grid.row_mut(0))
        // must... resist... unsafe...
    }
}

I understood that '_ and 'a are incompatible for the borrow checker. And that sucked up all the juice in my brain.
Bad design? Unsafe unavoidable?
In the end I could let go the default impl and write iterators for all my types, but...

Please make me clever.
Thanks!

Trying the Option::take trick:

    struct RowsMut<'a, T> {
        grid: Option<&'a mut T>,
    }

    impl<'a, T: GridMut<'a>> Iterator for RowsMut<'a, T> {
        type Item = <T as GridMut<'a>>::RowMut;

        fn next(&mut self) -> Option<Self::Item> {
            if let Some(grid) = self.grid.take() {
                let item = grid.row_mut(0);
                self.grid = Some(grid); // Nop!
                Some(item)
            } else {
                unreachable!()
            }
        }
    }

The stupid solution here is to collect to yield back again...

Wait, are generators what I want?

Pretty much.. the problem lies here:

fn row_mut(&'a mut self, row: u16) -> Self::RowMut;

With this kind of interface, you can only access a single row at a time (due to the mutable borrow). On the other hand, if you want to make an iterator out of it, it needs to allow all those rows to be accessed in parallel. (Note that you can always .collect() an iterator into a Vec and then do random access to all the items however you want.)

In order to think about what’s the nicest way fix this, it would help if you had a concrete type that you want to implement the GridMut trait for.

2 Likes

Hey bro thanks for the quick anwser!

Collecting is not the thing I want. What I really want is to provide this:

for row in grid.rows_mut(/* crop */) {
    for cell in row { *cell = /* stuff */;}
}

from that Grid::row_mut method implementors gave me. Not only it looks neat, but also it factorizes the bound checks. Compare to:

for row in grid.list_rows(/* Y crop */) {
    for cell in grid.row(row, /* X crop */ ) { // Unwanted bound checks from 2nd iteration onward
        // ...
    }
}

One of my concrete type is pretty much VecGrid(Vec<Cell>, u16, u16). I guess I can make (maybe not, will try that after diner) an Iterator<Item = Iterator<Item = &mut Cell>> out of that with the Option::take trick.
I also have something like Fill(Cell, u16, u16), I was thinking of using std::iter::Repeats.

Unfortunately, the for syntax in Rust only works with the Iterator trait. Since the Iterator trait does include the collect() method, it can't be implemented on top of an interface like GridMut which provides access to only one item at a time.

If your iterable object can only provide access to one item at a time, you can implement a different trait, like StreamingIterator, but this won't work with the built-in for syntax.

With these method signatures, you need a way to iterate over rows that ensures there aren't multiple exclusive references to the same row[0]. Since you don't control the data type, the implementors will have to provide the iterator over some row type. Then another row-like function would need to take the row (not the whole grid) and a row number and return a cropped row. Or, the row iterator could inherantly iterate over cropped rows and not entire rows. At that point, I'm not sure you're saving the implementors much, just a flatten or flat_map.

Alternatively you could look into some sort of run-time system, mutexes or whatever, to ensure unique write access. It would probably be messy.

[0]: With a flat Vec this would probably be ChunksExactMut.[1]

[1]: If you're wondering how this is accomplished, split_at_mut turns a single &mut [T] into two non-overlapping &mut [T]s, thus providing a way to safely partition mutable access. A generalized row iterator would need to do something similar to itself -- split off a row from itself to be returned while "forgetting about" the row internally (to avoid holding on to any duplicate reference to the returned row).

Is that true that an iterator (just like any other types) cannot outlive its borrowed content? If that is true, why rust does not lifetime elision on

type Item = &mut Cell;
fn next(&mut self) -> Option<&mut Cell>;

?

Why couldn't I unsafely convert the lifetimes?

The iterator can't outlive things that it borrows, but items returned by the iterator can outlive the iterator.

If that is true, why rust does not lifetime elision on

type Item = &mut Cell;
fn next(&mut self) -> Option<&mut Cell>;

With generic associated types you will be able to define a trait where the lifetimes work like this. But this is not how the existing Iterator trait is defined. If next could borrow the iterator for the lifetime of the item it returns, methods like Iterator::collect would be impossible.

If you were implementing this iterator for a specific concrete type, then you could likely use unsafe code to convert the lifetimes, as long as you uphold all the aliasing rules. It's somewhat common to need some unsafe code when implementing mutable iterators for Rust data structures.

However, if you are implementing for a generic <T: GridMut> type, there's no way for you to guarantee that T::row_mut is implemented in such a way that it's legal to keep multiple T::RowMut alive at the same time. For example, I could create a GridMut implementation where row_mut(0) and row_mut(1) contain overlapping references. Returning these from the same Iterator would allow undefined behavior in safe code.

One practical solution might be to require each implementer of GridMut to provide its own RowsMut type, rather than writing a generic one for all GridMut.

2 Likes

Thanks everyone!
I ended up with a solution where implementors provide the whole thing. Why bother in the end?

@quinedot: I am using this trick now (from Iterator for ChunksExactMut):

mem::replace(&mut self.v, &mut []);

This sorcery tricks the lifetimes somehow.

@mbrubeck Thanks for the clear and detailed explanation. I have to hack thoses ideas by myself to get a better grasp:

The iterator can't outlive things that it borrows, but items returned by the iterator can outlive the iterator .

If next could borrow the iterator for the lifetime of the item it returns, methods like Iterator::collect would be impossible.

...aliasing...overlapping references...