In Rust, how do I create a mutable iterator?

Question

I'm having difficulty with lifetimes when trying to create a mutable iterator in safe Rust.

Here is what I have reduced my problem to:

struct DataStruct<T> {
    inner: Box<[T]>,
}

pub struct IterMut<'a, T> {
    obj: &'a mut DataStruct<T>,
    cursor: usize,
}

impl<T> DataStruct<T> {
    fn iter_mut(&mut self) -> IterMut<T> {
        IterMut { obj: self, cursor: 0 }
    }
}

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

    fn next(&mut self) -> Option<Self::Item> {
        let i = f(self.cursor);
        self.cursor += 1;
        self.obj.inner.get_mut(i)
    }
}

fn f(i: usize) -> usize {
   // some permutation of i
}

The structure of my DataStruct will never change, but I need to be able to mutate the contents of the elements stored within. For example,

let mut ds = DataStruct{ inner: vec![1,2,3].into_boxed_slice() };
for x in ds {
  *x += 1;
}

The compiler is giving me an error about conflicting lifetimes for the reference I am trying to return. The lifetime it finds that I am not expecting is the scope of the next(&mut self) function.

If I try to annotate the lifetime on next(), then the compiler, instead, tells me I haven't satisfied the Iterator trait. Is this solvable in safe rust?

Here is the error:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/iter_mut.rs:25:24
   |
25 |         self.obj.inner.get_mut(i)
   |                        ^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 22:5...
  --> src/iter_mut.rs:22:5
   |
22 | /     fn next(&mut self) -> Option<Self::Item> {
23 | |         let i = self.cursor;
24 | |         self.cursor += 1;
25 | |         self.obj.inner.get_mut(i)
26 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/iter_mut.rs:25:9
   |
25 |         self.obj.inner.get_mut(i)
   |         ^^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 19:6...
  --> src/iter_mut.rs:19:6
   |
19 | impl<'a, T> Iterator for IterMut<'a, T> {
   |      ^^
note: ...so that the types are compatible
  --> src/iter_mut.rs:22:46
   |
22 |       fn next(&mut self) -> Option<Self::Item> {
   |  ______________________________________________^
23 | |         let i = self.cursor;
24 | |         self.cursor += 1;
25 | |         self.obj.inner.get_mut(i)
26 | |     }
   | |_____^
   = note: expected  `std::iter::Iterator`
              found  `std::iter::Iterator`

edits:

changed implementation of next() so that iteration order is a permutation of original sequence.

`slice::IterMut` is implemented using `unsafe` for this very reason. If you can, I encourage you to alias or wrap `slice::IterMut` instead of writing your own. — trent, Aug 16 '20 at 14:31
This is a simplification of my actual problem to make it easier to consume as a question on StackOverflow. I was hoping there was a way to do this without resorting to unsafe. — Barnaby Dalton, Aug 16 '20 at 14:41
How do you guarantee that `self.cursor` will never be the same value twice? And if the answer is "there's no way to change `cursor` except by calling `next()`" then why can't you just wrap `slice::IterMut` instead? — trent, Aug 16 '20 at 14:53
maybe I simplified too much. My usecase has the equivalent of `let i = f(self.cursor)` where f is a permutation of the indices. — Barnaby Dalton, Aug 16 '20 at 14:56
So you're relying on properties (of `f`, `self.cursor` and `[T]::index`) that *you know but the compiler doesn't*, and if they are broken your code has undefined behavior, which is exactly when you need `unsafe`. — trent, Aug 16 '20 at 15:00

Peter Hall · Accepted Answer · 2020-08-16T15:28:45.793

The borrow checker is unable to prove that subsequent calls to next() won't access the same data. The reason why this is a problem is because the lifetime of the borrow is for the duration of the life of the iterator, so it can't prove that there won't be two mutable references to the same data at the same time.

There really isn't a way to solve this without unsafe code - or changing your data structures. You could do the equlivant of slice::split_at_mut but, given that you can't mutate the original data, you'd have to implement that in unsafe code anyway. An unsafe implementation could look something like this:

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

    fn next(&mut self) -> Option<Self::Item> {
        let i = self.cursor;
        self.cursor += 1;
        if i < self.obj.inner.len() {
            let ptr = self.obj.inner.as_mut_ptr();
            unsafe {
                Some(&mut *ptr.add(i))
            }
        } else {
            None
        }
    }
}

My confusion before this answer was what the undefined behaviour I was violating was. This explained that as well as the solution. Thank you — Barnaby Dalton, Aug 16 '20 at 15:16

In Rust, how do I create a mutable iterator?

1 Answers1

Related