// 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...
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.
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).
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.