How do I implement a container with support for a mutable iterator? [duplicate]

Question

I want to design a toy container class with support for mutable iterators, but I'm having trouble sorting out the lifetimes of the iterator and its reference to the container.

I've tried to create a minimal non-compiling example:

struct Payload {
    value: i32,
}

struct Container {
    val: Payload,
}

struct IterMut<'a> {
    cont: &'a mut Container,
    cnt: i32,
}

impl<'a> Container {
    fn new() -> Container {
        Container { val: Payload { value: 42 } }
    }
    fn iter_mut(&'a mut self) -> IterMut<'a> {
        IterMut {
            cont: self,
            cnt: 10,
        }
    }
}

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

    fn next<'b>(&'b mut self) -> Option<Self::Item> {
        self.cnt -= 1;

        if self.cnt < 0 {
            return None;
        } else {
            Some(&mut self.cont.val)
        }
    }
}

fn main() {
    let mut cont = Container::new();

    let mut it = cont.iter_mut();
    it.next();
}

The above is intended to implement a real stupid container that returns the same item 10 times when iterated over using iter_mut().

I can't figure out how to implement Iterator::next.

I did manage to write a regular function that implements the same semantics as what I want for next:

fn manual_next<'a, 'b>(i: &'a mut IterMut<'b>) -> Option<&'a mut Payload> {
    i.cnt -= 1;

    if i.cnt < 0 {
        return None;
    } else {
        Some(&mut i.cont.val)
    }
}

This doesn't help, because I can't manage to adapt it to implement Iterator::next, and without implementing Iterator, my container can't be iterated over in for-loops, which I want.

Answer 1

It's not possible to implement the iterator as is, because it would allow you to get more than one mutable reference to the same item, breaking Rust's aliasing/borrowing rules. Good thing the borrow checker caught the error! :-)

For example, extending your main example:

fn main() {
    let mut cont = Container::new();

    let mut it = cont.iter_mut();
    let alias_1 = it.next();
    let alias_2 = it.next();
    // alias_1 and alias_2 both would have mutable references to cont.val!
}

Other iter_mut iterators (for example the one one on vectors/slices) return references to different items on each step, so don't have this problem.

If you really need to iterate over something logically mutable, you may be able to iterate immutably but use interior mutability via RefCell or Cell.

The reason the manual_next function compiles is that you're not constrained to the Iterator::next signature, and it is in fact perfectly safe to call once (or more if you don't keep the result). However if you try to save the result, it keeps the IterMut borrowed mutably and you couldn't call it again:

let mut cont = Container::new();

let mut it = cont.iter_mut();
let x = manual_next(&mut it);
manual_next(&mut it);  // Error: `it` is still borrowed mutably

Playground

In contrast, Iterator::next has a type which makes things like collecting into a vector possible.