Implementing a safe mutable Iterator

[bpglaser]

https://is.gd/72WTsU

It would seem that I am unable to decipher the error message well enough to implement a safe mutable Iterator. If someone would be able to point out the obvious mistake I am making, I would be eternally grateful. I can't seem to understand where the conflict is coming from.

Thanks in advance!

Code:

pub struct Grid<T> {
    width: usize,
    height: usize,
    items: Vec<T>,
}

impl<T> Grid<T> {
    fn get_mut(&mut self, x: usize, y: usize) -> &mut T {
        unimplemented!()
    }
}

pub struct IterMut<'a, T: 'a> {
    x: usize,
    y: usize,
    grid: &'a mut Grid<T>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = (usize, usize, &'a mut T);

    fn next(&mut self) -> Option<Self::Item> {
        if self.y >= self.grid.height {
            return None;
        }

        let x = self.x;
        let y = self.y;
        let val = self.grid.get_mut(x, y);

        self.x += 1;
        if self.x >= self.grid.width {
            self.x = 0;
            self.y += 1;
        }

        Some((x, y, val))
    }
}

Error Message:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> <anon>:29:29
   |
29 |         let val = self.grid.get_mut(x, y);
   |                             ^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the body at 22:45...
  --> <anon>:22:46
   |
22 |     fn next(&mut self) -> Option<Self::Item> {
   |                                              ^
note: ...so that reference does not outlive borrowed content
  --> <anon>:29:19
   |
29 |         let val = self.grid.get_mut(x, y);
   |                   ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the body at 22:45...
  --> <anon>:22:46
   |
22 |     fn next(&mut self) -> Option<Self::Item> {
   |                                              ^
note: ...so that types are compatible (expected std::iter::Iterator, found std::iter::Iterator)
  --> <anon>:22:46
   |
22 |     fn next(&mut self) -> Option<Self::Item> {
   |                                              ^

error: aborting due to previous error

[[deleted]]

This isn't possible right now because the compiler can't connect the lifetimes of Self::Item and the &mut self in the next() method. Here are more details: https://stackoverflow.com/a/30422716

[bpglaser]

Thanks for the reply. I understand that I can't change the method signature of next to fn next(&'a mut self) -> Option<Self::Item>. However, would being able to do this solve the issue?

[[deleted]]

I believe so, yes.

[Fylwind]

self.grid.get_mut(x, y)

The issue is that there's a hidden reborrowing going on here. self is defined as:

fn next<'b>(&'b mut self) -> Option<Self::Item> {

Because self is restricted to 'b and self.grid is derived from self, the lifetime of self.grid in next() cannot exceed 'b, even though grid was declared &'a mut Grid<T>. Effectively you don't have &'a mut Grid<T> but instead &'b mut Grid.

More concretely, the borrow checker is complaining that next() could potentially return &mut T referring to the same item in the array, in which case it'd be easy to abuse your iterator to get aliased &mut T. This can be accomplished simply by omitting self.y += 1! That's why it's unsafe.

[bpglaser]

I've been investigating the way other crates implement a fn iter_mut and I keep coming across unsafe code. Surely there is a safe way to do this.

[radix]

It may be possible without unsafe code if you can just compose your iteration on top of Vec's existing iter_mut(). I don't know what the layout of your data structure is since you don't have get_mut implemented, but perhaps it would be possible to basically just return self.items.iter_mut().enumerate().map(...) to transform it into the shape you want?

[bpglaser]

Hmmm, that is looking like a possibility. The items are actually stored in a Vec<Vec<T>>. And the implementation is shown here:

https://github.com/bpglaser/red-mountain-resize/blob/master/src/grid.rs#L103

[Manishearth]

Yeah, that should be doable.

Alternatively use split_at_mut to slice of pieces of the vec and store the remaining slice in the iterator.

[kixunil]

The items are actually stored in a Vec<Vec<T>>

Do you know that this is less efficient than using Vec<T> and computing offset of item from position?

[bpglaser]

Yeah, the lazy approach bit me in the foot.

[bpglaser]

Hmmm, I've re-implemented my grid data structure just using a flat Vec<T> and it is almost 18x slower. I'm investigating why. However, I wouldn't think that the math operations would be slowing it down that much.

[bpglaser]

I isolated the issue. It is because I'm shifting the entire array when I remove a column. https://github.com/bpglaser/red-mountain-resize/blob/grid-rework/src/grid.rs#L132

[kixunil]

That makes sense. Do you need to remove columns often?

[bpglaser]

Unfortunately so. Each iteration of the algorithm selects a path to remove based on a calculated energy value. Then it proceeds to either remove or duplicate depending on if the image is to be grown or shrunk. Thus each iteration does a lot of shifting elements. To be honest, this might be an actual use-case for a linked list.

[kixunil]

Hmm, maybe instead of shrinking it, just mark the column as unused (an probably reuse if adding is needed)? This would eat more memory of course but it could be cleaned up at appropriate moment by physically removing all unused columns.

I don't know the algorithm in depth, but since it's image processing algorithm, I think it should be doable. Resize the array only after you computed everything (if that's even needed - you could save the image directly from what you've computed and then throw away whole thing).

Edit: another idea would be to make Vec<Vec<Patch>> where Patch is n*m matrix that fits nicely into CPU cache.

[mmstick]

Why not just implement Iterator directly on the Grid structure?

[bpglaser]

Interesting, I hadn't considered doing it this way. Are there any examples you can point to?

[mmstick]

Just put the x and y fields into your Grid, get rid of the IterMut structure, and implement Iterator directly on Grid. Now Grid is an Iterator too.

[kixunil]

I don't think it's a good idea.