Iterator design pattern for mutable reference

help
1

I'm having problem with implementation iterator design pattern for mutable reference. Note that analog code works fine for ordinary reference but doesn't for mutable given in the following code. There is an error regarding lifetimes you may find it in the line comment in the implementation of the next() method. I've read other similar topics but failed to find solution. Is this a bug?

#[derive(Debug)]
struct MyCollection {
    data: Vec<i32>,
}

struct MyCollectionRefMutIterator<'a> {
    current_index: usize,
    data: &'a mut Vec<i32>,
}

impl <'a> Iterator for MyCollectionRefMutIterator<'a> {
    type Item = &'a mut i32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current_index < self.data.len() {
            let item = &mut self.data[self.current_index];
            self.current_index += 1;
            Some(item) // Error! lifetime may not live long enough
                       // method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`
        } else {
            None
        }
    }
}

impl <'a> IntoIterator for &'a mut MyCollection {
    type Item = &'a mut i32;
    type IntoIter = MyCollectionRefMutIterator<'a>;

    fn into_iter(self) -> Self::IntoIter {
        MyCollectionRefMutIterator {
            current_index: 0,
            data: &mut self.data,
        }
    }
}

fn main() {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn mut_reference_collection() {
        let mut collection = MyCollection { data: vec![1, 2, 3] };
        for item in &mut collection {
            *item += 10;
            println!("{}", item);
        }
        assert_eq!(vec![11, 12, 13], collection.data);
    }
}
2

This is often referred to as lending iterators. The standard library's Iterator trait can't be used for implementing lending iterators, you'd need to define your own LendingIterator trait (see Niko's blog post I linked for how such a trait can be defined) or implement one that already provides useful methods, like lending_iterator::LendingIterator.

1 Like
3

Instead of storing a &'a mut Vec<T> and an index, store a std::slice::IterMut<'a, T>. It's more flexible and allows you to create an iterator that yields mutable references.

The problem with your version is that the compiler can't prove that you don't return multiple mutable references to the same value in the vector. This is needed to ensure that mutable reference remain exclusive.

1 Like
4

The problem with your version is that the compiler can't prove that you don't return multiple mutable references to the same value in the vector.

This is true, but the compiler doesn't even get to that point.
The error at hand is caused by the fact that &'a mut Vec<i32> is accessed through a &'1 mut self, which bounds the reference to an element acquired in this way to '1 instead of 'a, leading to a trivial type mismatch error.

5

That's how the error is expressed. :slight_smile:

6

Put another way, &mut Struct(&'a mut X) does not give you &'a mut access.

3 Likes
7

For &mut _ iterators based on slices specifically, it is possible with safe code. Or here's a slower walkthrough.

3 Likes
8

Thanks for the solution and for the article, it was very clearly explained. But, for the last three days I was struggling with some variation on it. Namely, I wanted to implement Iterator pattern strictly, i.e. I wanted to wrap iterable MyCollection in Iterator MyCollectionRefMutIterator<'a> and not its iterable field data. Of course I didn't succeed, otherwise I wouldn't be asking now how to do it. I succeeded for owned and reference values, but again failed for mutable reference.

This is just a starting version for you to see what I'm after. I had tried many others and always ran into problems.

#[derive(Debug)]
struct MyCollection<'a> {
    data: &'a mut Vec<i32>,
}

struct MyCollectionRefMutIterator<'a> {
    collection: &'a mut MyCollection<'a>,
    //data: &'a mut [i32], // from previous solution
}

impl <'a> Iterator for MyCollectionRefMutIterator<'a> {
    type Item = &'a mut i32;

    fn next(&mut self) -> Option<Self::Item> {
        match std::mem::take(&mut self.collection.data.as_mut_slice()) {
            [] => None,
            [first, rest @ ..] => {
                self.collection.data = rest; // Error! mismatched types expected mutable  reference `&'a mut Vec<i32>`    found mutable reference `&mut [i32]`
                Some(first)
            }
        }
    }
}

impl <'a> IntoIterator for &'a mut MyCollection<'a> {
    type Item = &'a mut i32;
    type IntoIter = MyCollectionRefMutIterator<'a>;

    fn into_iter(self) -> Self::IntoIter {
        MyCollectionRefMutIterator {
            collection: self,
            //data: &mut self.data, // from previous solution
        }
    }
}

fn main() {
}

// ----------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    
    #[test]
    fn mut_reference_collection() {
        let mut collection = MyCollection { data: &mut vec![1, 2, 3] };
           for item in &mut collection {
            *item += 10;
            println!("{}", item);
        }
        assert_eq!(vec![11, 12, 13], collection.data);
    }
}
9

It is not possible to do this without unsafe code making use of raw pointers. You should not do this unless it is unavoidable.

What do you mean by “strictly” here? What property of the code are you trying to achieve?

10

Vec is an iterable and I believe that MyCollection is also an iterable so its object could be used to create an Iterator. It has one vector field data but that is less important; could be something else, even a simple counter. So, I want this:

struct MyCollectionRefMutIterator<'a> {
    collection: &'a mut MyCollection<'a>,
}

instead of this:

struct MyCollectionRefMutIterator<'a> {
    data: &'a mut [i32],
}

Iterator design pattern says that iterator should be created around iterable structure and not around its iterable field as was shawn previously. That's what I meant when I said "strictly".

11

The closest workable design with the standard Iterator trait and without unsafe is probably storing actual iterators like @RustyYato suggested. Holding on to &mut Collection means next has exclusive access to the entire collection, which conflicts with the handing out exclusive access to the contents with the Iterator API (where items can persist across calls to next).

(Incidentally, you never want &'a mut Thing<'a>.)

12

This is a difficult thing to do, requiring unsafe code, and you should not do it unless it serves some purpose that is not just “I want the code to be organized this way”.