[Solved] Iterator over mutable subslices

#1

I’m implementing an iterator over a mutable slice S that returns subslices of variable length, depending on the content of S.
This is what I would like to accomplish (playground):

struct Iter<'a> {
    pub slice: &'a mut [i32],
}

impl<'a> Iterator for Iter<'a> {
    type Item = &'a mut [i32];
    
    fn next<'s>(&'s mut self) -> Option<Self::Item> {
        if let Some(first) = self.slice.first().cloned() {
            let count = self.slice.iter().skip(1).take_while(|i| **i == first).count();
            let (result, new_slice) = self.slice.split_at_mut(count);
            self.slice = new_slice;
            Some(result)
        } else {
            None
        }
    }
}

fn main() {
    let mut input = vec![3, 4, 0, 0, 4, 4, 5, 0, 7, 7, 7, 0];
    let iter = Iter {slice: &mut input};
    
    for slice in iter {
        println!("{:?}", slice);
    }

    println!("Done");
}

From my knowledge so far, implementing an iterator with mutable elements is done by repeatedly splitting the slice into a prefix that is returned, and the rest that is kept in the iterator.

But this gives me problems with the borrow checker. The lifetimes 's and 'a are in conflict.
The compiler error is the following:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/main.rs:11:50
   |
11 |             let (result, new_slice) = self.slice.split_at_mut(count);
   |                                                  ^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime 's as defined on the method body at 8:13...
  --> src/main.rs:8:13
   |
8  |     fn next<'s>(&'s mut self) -> Option<Self::Item> {
   |             ^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:11:39
   |
11 |             let (result, new_slice) = self.slice.split_at_mut(count);
   |                                       ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 5:6...
  --> src/main.rs:5:6
   |
5  | impl<'a> Iterator for Iter<'a> {
   |      ^^
   = note: ...so that the types are compatible:
           expected std::iter::Iterator
              found std::iter::Iterator

Apparently, split_at_mut does not just borrow the reference slice with lifetime 'a, but also the reference to self with lifetime 's. As a result, the lifetime 'r of result and new_slice cannot be inferred.

First of all, due to the borrow of 's, it must hold that 'r < 's. But, it must also hold that 'a < 'r, since result is returned with a lifetime of 'a.
From these two conditions, it follows that 'a < 's. This is my understanding of the compiler error.

What the compiler error doesn’t tell us, but what I think creates the conflict is, that since the struct Iter actually contains the reference with lifetime 's, it holds that 's < 'a.

As a result, 'a < 's && 's < 'a == false.

When changing the return of Some(result) to Some(Default::default()), which effectively uncouples 'r and 'a, then I get the same error message, but with the assignment of self.slice = new_slice; causing 'a < 'r.

What I would like to achieve is to cut off a prefix of self.slice, in the way that the prefix is extracted from self.slice and has a lifetime that is only restricted by 'a. It should be independent of the struct Iter and not be restricted by lifetime 's.
The leftover self.slice should not contain the prefix anymore, otherwise there would be two mutable references to the same elements.

I hope what I wrote is somewhat understandable, as I am having a hard time figuring out what is going on. Any help, also completely different variants to implement the iterator from the example, is appreciated.

#2

Hi, I used the definition of ChunksMut and came up with this playground, what do you think ?
I also added 1 to count, it was stuck in an infinite loop otherwise.

1 Like
#3

Hi @leudz, thank you, this works for me! And thank you for fixing the bug with the offset!
This is exactly what I needed.