2D grid with iterators: borrow and lifetime questions [solved]

[medusacle]

I created a straightforward data structure for dense 2D grids — see https://gitlab.com/snippets/1777276 — which works, but as I’m fairly new to the Rust language I have a few questions as to things that could be done better

• The iterators GridIter and MutGridIter share all of the fields and most of their code, is there a way to write this more concisely (without macros)?

• In MutGridiIter::next(&mut self) I needed to use an unsafe section to get around a lifetime issue (I think because there are two mutable references: one held by the iterator itself and one by the returnvalue). I’d strongly prefer not to do this, but I don’t see another option.

            // TODO cannot get rid of the unsafe here?
            //   error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in
            //   function call due to conflicting requirements
            let ret = Some(((self.x, self.y), unsafe {
                &mut *(&mut self.owner.grid[self.ofs] as *mut T)
            }));

• In Grid2D::get_mut I couldn’t use the more elegant closure-based approach as in the get function. The compiler error mentions that the closure might outlive the current function but I don’t think this is true? [solved]

Suggestions very welcome !

[hellow]

Sadly, your code does not compile (playground) (ps. provide a link to the playground next time, we love playground links ), but that is very easy to fix

pub struct GridIter<'a, T: 'a> { ...
pub struct MutGridIter<'a, T: 'a> { ...

Your closure problem can be solved with move.

pub fn get_mut(&mut self, x: i32, y: i32) -> Option<&mut T> {
    self.to_offset(x, y).map(move |ofs| &mut self.grid[ofs])
}

IMHO, when you need unsafe code you are probably doing something wrong.

[medusacle]

Sadly, your code does not compile (playground) (ps. provide a link to the playground next time, we love playground links ), but that is very easy to fix

Strange, it compiled locally. Maybe a Rust version difference?

Thanks for the suggestion, will add the lifetime and fix the closure !

Edit: link to working playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=e23f0b4e157ab8ec5d30af573035ccf0

[parasyte]

You are running into this issue with the type system on the mutable iterator. The article has some outdated Rust syntax, but the concept still holds. In short, unsafe is the only way to yield mutable borrows from an iterator.

[medusacle]

You are running into this issue with the type system on the mutable iterator. The article has some outdated Rust syntax, but the concept still holds. In short, unsafe is the only way to yield mutable borrows from an iterator.

Thank you! Yes, that seems to be exactly the issue. I’ve thought about this a bit, as this is a fairly old issue it’s unlikely to change any time soon, and I might abandon mutable iterators completely in my design.

Another option, as the base data structure is a Vec, might be to return a flattened iterator of vec.iter_mut for every 1D span (using their unsafe code!), though this sounds like a borrow-checking nightmare too.

Edit: the latter is also out of the question, I think

    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
        let (y1, y2) = (0, self.height);
        (y1..y2).map(move |y| self.grid.iter_mut()).flatten()
    }

gives me the same error as before:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements

(but maybe I need to be more creative here with lifetime specifications)

[daboross]

The problem in the article only occurs if you’re returning overlapping slices, though, right? I skimmed the article but it seems to be mostly about “streaming iterators” which return data that originates within the iterator itself, or overlaps from previous slices. If I understand your example correctly, you are returning non-overlapping data from a vec not owned by the iterator (if you weren’t it would be unsound to work around the bug and implement iterator anyway)

For cases where you are returning unique indices from a borrowed source, you should be able to implement a mutable iterator using only split_at_mut

There’s an example doing this for a plain iterator in the nomicon (ctrl+f for “mutable slice”): https://doc.rust-lang.org/nomicon/borrow-splitting.html

Saw this after looking at this x-post.

[medusacle]

If I understand your example correctly, you are returning non-overlapping data from a vec not owned by the iterator (if you weren’t it would be unsound to work around the bug and implement iterator anyway)

This is definitely supposed to concern non-overlapping slices—for each cell in a region of a 2D grid it should yield ((x,y), &mut T). if it can be made to return overlapping rows that’d be a bug, the rectangle is clipped to avoid this.

My example in the previous was off the mark in that regard, I was quickly trying whether the principle would work, was planning to offset/restrict the iterators later!

For cases where you are returning unique indices from a borrowed source, you should be able to implement a mutable iterator using only split_at_mut

Thank you! I had no idea that it was possible to use split_at_mut multiple times recursively, but that makes a lot of sense, I’ll try this.

[parasyte]

I don’t see any mention of overlapping in the article at all. In fact, it clearly points out that the iterator interface can only return unique references. The mere existence of the &mut data field on VecMutIterator is what causes the borrow checker to raise an error. In this case, it’s the &mut owner field on MutGridIter. Returning a mutable borrow from data that is already mutable borrowed by this struct is mutable aliasing.

The nomicon link does describe a way to resolve the aliasing though, and that’s by updating the mutable slice held in the owned field, and returning the other half of the split. I wasn’t aware of this technique, seems like it should work!

[medusacle]

Tried to do this; instead of keeping a reference to the containing structure and an offset, the iterator now only has a mutable slice

pub struct MutGridIter<'a, T: 'a> {
    slice: &'a mut [T],
    ...
}

I’ve changed the next function to split up the slice, return a mutable reference to the current cell, and store (part of) the rest

   type Item = ((i32, i32), &'a mut T);
   fn next(&mut self) -> Option<Self::Item> {
        if self.y < self.y2 {
            let (cell, rest) = self.slice.split_at_mut(1);
            let ret = Some(((self.x, self.y), &mut cell[0]));
            self.slice = rest;

            // Advance
            self.x += 1;
            if self.x >= self.x2 {
                self.x = self.x1;
                self.y += 1;
                if self.y < self.y2 { // don't advance out of slice
                    self.slice = self.slice.split_at_mut(self.stride).1;
                }
            }

            ret
        } else {
            // out of range
            None
        }
    }

I’ve tested that this approach works for the non-mutable iterator, however for the mutable one there are lifetime errors error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements;

https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=34d40a1eb816bf6ad44bc1063a7a1750

It might be a matter of being more explicit about lifetimes, but this is way above my head.

[medusacle]

Ohh I only see now that you posted a working solution on reddit! thank you!

For reference: https://play.rust-lang.org/?version=beta&mode=debug&edition=2018&gist=6254ca1faa2af152e740379327dee661

[medusacle]

I… found out that there’s such a thing as slice.chunks_mut, allowing the whole iterator to be written in one statement:

    /// Iterate over a rectangle (mutable)
    pub fn iter_region_mut(
        &mut self,
        x1: i32,
        y1: i32,
        x2: i32,
        y2: i32,
    ) -> impl Iterator<Item = ((i32, i32), &mut T)> {
        let (x1, y1, x2, y2) = self.clip_rect(x1, y1, x2, y2);
        let ofs = self.to_offset(x1, y1).unwrap_or(0);
        let rwidth = (x2 - x1) as usize;
        let end = cmp::min(ofs + self.width * (y2 - y1) as usize, self.grid.len());
        (y1..y2)
            .zip(self.grid[ofs..end].chunks_mut(self.width))
            .flat_map(move |(y, row)| (x1..x2).map(move |x| (x, y)).zip(row[0..rwidth].iter_mut()))
    }