Newbie question on Iterators

help
1

Hi, I'm learning about iterators and thought I'd test myself with a trivial example, but I'm having problems.

The challenge I set myself was to write 3 iterators (consuming, immutable reference and mutable reference) for this simple struct:

    #[derive(Debug)]
    struct FullName {
      first: String,
      middle: String,
      last: String,
    }

Here's the 'consuming' iterator, which seems to work OK:

    struct IntoIter {
        name: FullName,
        i: u8,
    }

    impl Iterator for IntoIter {
        type Item = String;

        fn next(&mut self) -> Option<Self::Item> {
            self.i += 1;
            match self.i {
                1 => Some(self.name.first.clone()),
                2 => Some(self.name.middle.clone()),
                3 => Some(self.name.last.clone()),
                _ => None,
            }
        }
    }

    impl IntoIterator for FullName {
        type Item = String;

        type IntoIter = IntoIter;

        fn into_iter(self) -> Self::IntoIter {
            IntoIter { name: self, i: 0 }
        }
    }

And here's the immutable reference iterator, which also seems to be OK:

    struct Iter<'a> {
        name: &'a FullName,
        i: u8,
    }

    impl<'a> Iterator for Iter<'a> {
        type Item = &'a str;

        fn next(&mut self) -> Option<Self::Item> {
            self.i += 1;
            match self.i {
                1 => Some(&self.name.first),
                2 => Some(&self.name.middle),
                3 => Some(&self.name.last),
                _ => None,
            }
        }
    }

    impl<'a> IntoIterator for &'a FullName {
        type Item = &'a str;

        type IntoIter = Iter<'a>;

        fn into_iter(self) -> Self::IntoIter {
            Iter { name: self, i: 0 }
        }
    }

But I can't figure out how to do the mutable reference iterator. I've tried letting the compiler guide me, but I can't get the code to compile, let alone work correctly. This is as far as I get:

    struct IterMut<'a> {
        name: &'a mut FullName,
        i: u8,
    }

    impl <'a> Iterator for IterMut<'a> {
        type Item = &'a mut String;
        
        // does NOT compile
        fn next(&mut self) -> Option<Self::Item> {
            self.i += 1;
            match self.i {
                1 => Some(&mut self.name.first),
                2 => Some(&mut self.name.middle),
                3 => Some(&mut self.name.last),
                _ => None,
            }
        }
    }

    impl <'a> IntoIterator for &'a mut FullName {
        type Item = &'a mut String;

        type IntoIter = IterMut<'a>;

        fn into_iter(self) -> Self::IntoIter {
            IterMut { name: self, i: 0 }
        }
    }

How can I fix this?

2

The root problem is that the compiler can't see that your iterator will only borrow each field once. (If it returned the same field twice, this would violate the uniqueness rule for &mut references.) You'll have a similar problem if you try to remove the clone calls from your consuming iterator.

One option is to use raw pointers and unsafe code. This is sometimes required when implementing mutable iterators for custom data structures in Rust. There are also ways to work around the problem in safe Rust; see this recent thread for some examples:

And in the future, generators will make it a bit easier to write iterators like this in safe Rust.

3

Since mbrubeck gave you the root cause of your problem, let me offer a solution.

You can just treat your fields as a collection, and re-use e.g. the iterators of Vec (playground):

impl IntoIterator for FullName {
    type IntoIter = std::vec::IntoIter<String>;
    type Item = String;

    fn into_iter(self) -> Self::IntoIter {
        vec![self.first, self.middle, self.last].into_iter()
    }
}

impl<'a> IntoIterator for &'a FullName {
    type IntoIter = std::vec::IntoIter<&'a String>;
    type Item = &'a String;

    fn into_iter(self) -> Self::IntoIter {
        vec![&self.first, &self.middle, &self.last].into_iter()
    }
}

impl<'a> IntoIterator for &'a mut FullName {
    type IntoIter = std::vec::IntoIter<&'a mut String>;
    type Item = &'a mut String;

    fn into_iter(self) -> Self::IntoIter {
        vec![&mut self.first, &mut self.middle, &mut self.last].into_iter()
    }
}
4

Thanks for the speedy response :grinning:

Not sure I follow your comment about the compiler not knowing that each field will be borrowed only once. Suppose I forget about the Iterator trait and instead implement my own next_item() method.

impl<'a> IterMut<'a> {
    fn next_item(&mut self) -> Option<&mut String> {
        self.i += 1;
        match self.i {
            1 => Some(&mut self.name.first),
            2 => Some(&mut self.name.middle),
            3 => Some(&mut self.name.last),
            _ => None,
        }
    }
}

I can then write:

fn main() {

    let full_name = &mut FullName {
        first: "wolfgang".to_string(),
        middle: "amadeus".to_string(),
        last: "mozart".to_string(),
    };

    let mut i = IterMut { name: full_name, i: 0 };

    while let Some(name) = i.next_item() {
        *name = (*name.clone().to_uppercase()).to_string();
    }

    // prints: FullName { first: "WOLFGANG", middle: "AMADEUS", last: "MOZART" }
    println!("{:?}", full_name); 
}

Wouldn't you expect the compiler to reject this code on the same grounds as it rejected my mutable iterator?

5

Yeah, I kinda guessed that I could do it by leveraging the iterators of built-in structs like vec . I wanted to see how easily it could be done from first principles.

6

Your next_item method has a different signature than Iterator::next. It returns a reference with the same lifetime as its self argument, so the iterator remains borrowed as long as this reference is still alive.

This means that you can't continue to iterate while previous results are still alive (playground):

let a = i.next_item();
let b = i.next_item(); // error[E0499]: cannot borrow `i` as mutable more than once at a time
println!("{:?} {:?}", a, b);

So it's fine if next_item borrows the same field twice, because the borrow checker will prevent those borrows from overlapping.

In contrast, Iterator::next only borrows the iterator for a temporary lifetime, which is not connected to its return type. This means you can continue using the same iterator while storing its previous results, which enables methods like Iterator::collect. But it also means that the iterator must be guaranteed to not return the same &mut reference twice.

7

OK I need to take this away and think about it. :thinking:

Thanks very much for the help.

8

What I wrote is pretty much first principles – I'm using the Vec iterators for not having to reinvent memory management, but that's somewhat of a secondary, convenience feature. The point in my code is that 1. the Iterator trait has the correct signature (as explained above), and 2. the iterated elements are stored permanently in a manner so that they can be returned without violating that signature.

9

Actually it may borrow them more than once since in release mode IterMut::i could overflow