How to implement a safe mutable iterator for Vec<T>?

Hi,

I was trying to implement a custom iterator for Vec, that has a alternative iteration scheme, but I lost to the borrow checker while doing so. I tried to debug the issue and turns out, I don't even know how to implement a normal iterator for Vec. So the task is basically to re-implement Vec<T>::iter_mut() using safe code. I tried a very naive approach, keeping a mutable reference to the vector and an index, but that fails. I don't know exactly why and how to fix this. The code is on rust playground and also here:

use std::ops::IndexMut;

struct CustomIter<'a, T> {
    i: usize,
    v: &'a mut Vec<T>,
}

impl<'a, T> Iterator for CustomIter<'a, T> {
    type Item = &'a mut T;
    
    fn next(&mut self) -> Option<&'a mut T> {
        if self.i == self.v.len() {
            None
        } else {
            self.i += 1;
            Some(self.v.index_mut(self.i - 1))
        }
    }
}

I am getting the following error:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:16:25
   |
16 |             Some(self.v.index_mut(self.i - 1))
   |                         ^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 11:5...
  --> src/lib.rs:11:5
   |
11 | /     fn next(&mut self) -> Option<&'a mut T> {
12 | |         if self.i == self.v.len() {
13 | |             None
14 | |         } else {
...  |
17 | |         }
18 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:16:18
   |
16 |             Some(self.v.index_mut(self.i - 1))
   |                  ^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 8:6...
  --> src/lib.rs:8:6
   |
8  | impl<'a, T> Iterator for CustomIter<'a, T> {
   |      ^^
   = note: ...so that the expression is assignable:
           expected std::option::Option<&'a mut T>
              found std::option::Option<&mut T>

Can someone enlighten me, what is going on and also how to fix CustomIter to make it work?

Thanks a lot! :slight_smile:

The way I usually do this is like so

struct Thing(Vec<String>);
impl Thing {
    fn iter_mut(&mut self) -> impl Iterator<Item=&mut String> {
        self.0.iter_mut()
    }
}

so if your struct is just a wrapper just pass the functionality up. If you can't do this I found IterMut really helpful

2 Likes

A combination of Rc and RefCell might help out. Just did a quick example

You can than use the it as ref and borrow it as mutable in your e.g. closure...

Hope it helps

If you wanna do this as an exercise, do not do iter_mut() but just plain old .iter(). The semantics of shared references (& _) and unique references (&mut _), combined with the fact that the items an Iterator yields can coexist, lead to iter_mut iterators having to prove that despite the different values coexisting their "uniqueness" (non-aliasing) guarantee is not broken. This is almost never expressible with non-unsafe Rust, so that's why these .iter_mut() variants are unsafe. So the trick to avoid using unsafe is to rely on these "primitive" constructions already present in the standard library, as @DevinR528 showed. Which sadly does not lead to learning much :sweat_smile:.

So go and try a non-unsafe .iter() first.


To better see how implementing an .iter_mut() would go, it would be something like this (note that .iter_mut() does not work on a vector but on the slice of heap-allocated elements it points to):

fn my_slice_iter_mut<'iterator, T : 'iterator> (
    slice: &'iterator mut [T]
) -> impl Iterator<Item = &'iterator mut T> + 'iterator
{
    MySliceIterMut(slice)
}

struct MySliceIterMut<'iterator, T : 'iterator> /* = */ (
    &'iterator mut [T],
);

impl<'iterator, T : 'iterator> Iterator
    for MySliceIterMut<'iterator, T>
{
    type Item = &'iterator mut T;
    
    fn next (self: &'_ mut MySliceIterMut<'iterator, T>)
      -> Option<Self::Item>
    {Some({
        // reborrow for lifetime '_ < 'iterator => Error
        let (head, tail) = self.0.split_first_mut()?;
        self.0 = tail;
        head
    })}
}

So, as you can see, there is a &'_ mut &'iterator mut ... double reference from the .next() function API, and this can only be always collapsed in the mut case as &'_mut ..., since it would otherwise be possible to break the unicity guarantee which would be unsound.

  • In this particular case it would be sound, so it would be a valid use of unsafe (to extend the lifetime).

In the non-mut case however, that is, a &'_ mut &'iterator ... as input; since &'iterator ... is Copy, the inner reference can be "copied", leading to the double reference being allowed to "collapse" into &'iterator ... (resulting in '_ being extended to 'iterator, by dropping the mut), as needed.

So there is a big difference between &'iterator mut ... and &'iterator ....

3 Likes

Thanks for all the replies! :slight_smile:

Honestly I don't like RefCell, it's safe but runtime checks, isn't it? that feels like tricking the compiler for something me or the compile should be able to do better :wink:

What seems to work is combining @Yandros's code with @DevinR528's link. Wrapping a mutable splice reference in an Option and using take to prevent to keep two mutable references seems to produce safe code:

fn my_slice_iter_mut<'iterator, T : 'iterator> (
    slice: &'iterator mut [T]
) -> impl Iterator<Item = &'iterator mut T> + 'iterator
{
    MySliceIterMut(Some(slice))
}

struct MySliceIterMut<'iterator, T : 'iterator> /* = */ (
    Option<&'iterator mut [T]>,
);

impl<'iterator, T : 'iterator> Iterator
    for MySliceIterMut<'iterator, T>
{
    type Item = &'iterator mut T;
    
    fn next (self: &'_ mut MySliceIterMut<'iterator, T>)
      -> Option<Self::Item>
    {
        self.0.take().and_then(|v| {
            let (head, tail) = v.split_first_mut()?;
            self.0 = Some(tail);
            Some(head)
        })
    }
}  

This completely depends on the ability to do a safe split of a slice, which again is just unsafe code, just one layer deeper. Though I have to admin I don't understand the difference to @Yandros's solution completely :confused:

3 Likes

Using .take() is a great trick to go from &'_ mut Option<&'iterator mut ...> to &'iterator mut, nice idea!

Yes, you end up relying on .split_[first]_mut(), which uses unsafe in its implementation since it cannot otherwise prove the returned references are disjoint, but it is such an abviously safe and sound function that it is fine :slight_smile:

2 Likes

Heh, I discuss how to go from slices to safe iterators in this lecture, starting from slide 19. The text is unfortunately in Russian, but the code examples might be helpful.

2 Likes

Instead of adding Option and take(), you can also just replace it with an empty slice temporarily:

playground

impl<'iterator, T: 'iterator> Iterator for MySliceIterMut<'iterator, T> {
    type Item = &'iterator mut T;

    fn next(self: &'_ mut Self) -> Option<Self::Item> {
        let slice = std::mem::replace(&mut self.0, &mut []);
        let (head, tail) = slice.split_first_mut()?;
        self.0 = tail;
        Some(head)
    }
}
5 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.