How implement an iterator over a growing collection?

AI gives me an example, but unfortunately a collection growing should happen inside the iterator next().

struct GrowingIter {
    data: Vec<String>,
    index: usize,
}

impl Iterator for GrowingIter {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index == self.data.len() {
            return None;
        }

        let item = self.data.get(self.index).unwrap().to_string();
        self.index += 1;
        Some(item)
    }
}

fn main() {
    let data = ["drt".to_string(), "more".to_string(), "tup".to_string()];
    let ads = ["fok".to_string(), "bara".to_string()];
    let mut grow = GrowingIter {
        data: data.to_vec(),
        index: 0,
    };
    let mut ads_i = ads.iter();
    for x in grow {
        println!("{x}");
        if let Some(el) = ads_i.next() {
            grow.data.push(el.clone())
        }
    }
}

If I try to grow the collection outside, I'm getting the error:

error[E0382]: borrow of moved value: `grow`
  --> /media/exhdd/Dev/modu/fp/main.rs:31:13
   |
23 |     let mut grow = GrowingIter {
   |         -------- move occurs because `grow` has type `GrowingIter`, which does not implement the `Copy` trait
...
28 |     for x in grow {
   |              ---- `grow` moved due to this implicit call to `.into_iter()`
...
31 |             grow.data.push(el.clone())
   |             ^^^^^^^^^ value borrowed here after move
   |
note: the `for` loop is desugared into a call to `std::iter::IntoIterator::into_iter`, which takes ownership of the receiver `self`, which moves `grow`
  --> /rustc/fb6531d550e0075b9eb9a51464f404805eec87d9/library/core/src/iter/traits/collect.rs:312:17

error: aborting due to 1 previous error

Obviously, it should be easy to do everything without an iterator, but I believe it can be done using an iterator with a simple fix. Please advise.

Provide an accessor for data in the iterator.

In short, don't do this. Mutating a collection you're iterating over is pretty much the exact example of what the borrow checker is trying to prevent.

The simplest fix is to just not use for syntax:

while let Some(x) = grow.next() {

but I would probably instead use something like:

for index in 0.. {
  let Some(x) = data.get(index) else {break};
  ...

Which of course doesn't need an Iterator implementation at all

Is there a more specific example if why you would need to use items from this iterator at the same time as you push to it?

I do it for Rust analyzer implementation. The main Rust module has a list of used modules, so I follow to the files implementing modules. however the files may have includes pushing me to analyze more files. Those includes are the source of the Rust files collection grow. I assume that there are more use case when analyzing an initial collection requires itts grow. Sure, I have a guard preventing duplicate entries, so more precisely, the collection should be a set, however iteration over growing set is another story.

Yeah, I use the index pattern for that, it's the simplest approach.


Edit:
Alternatively, you can separate the result/visited collection from the "to do" collection, the latter can be a stack or queue, depending on what you're after.

To have the result collection be visited in addition order, take a look at the indexmap crate which provides IndexSet: this is a collection that allows to to both look up entries by value like a set and visit them in insert order.

yes, you can do it with an iterator. no, not with a for loop.

a for loop consumes the iterable collection (i.e. the type implementing IntoIterator). which means one of these cases:

  • the data is moved, when the iterator owns the data,
  • the data is inaccessible, when the iterator borrows the data exclusively,
  • the data is immutable, when the iterator borrows the data shared,
    • unless you cheat, by using interior mutability

if you don't use for, e.g. with while let, as suggested, then you can access the iterator and the data however you like.

but the real question is, why do you want to do this?

I already explained that. As we found, an iterator gives the fastest access to a collection elements. Regarding a code complexity, a simple loop over a collection does the job with minimal coding overhead. So I implemented that and it already has been tested.

It's doable in principle. You can make the Vec shared mutable, e.g. with a RefCell. The index doesn't also need shared mutation so it might make sense to separate things out a little bit between an iterable/collection type and the iterator itself, e.g.

use std::cell::RefCell;

struct GrowingIterable {
    data: RefCell<Vec<String>>,
}
struct GrowingIter<'a> {
    data: &'a RefCell<Vec<String>>,
    index: usize,
}
impl<'a> IntoIterator for &'a GrowingIterable {
    type IntoIter = GrowingIter<'a>;
    type Item = String;
    fn into_iter(self) -> GrowingIter<'a> {
        GrowingIter {
            data: &self.data,
            index: 0,
        }
    }
}

impl Iterator for GrowingIter<'_> {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        let data = self.data.borrow();
        if self.index == data.len() {
            return None;
        }

        let item = data.get(self.index).unwrap().to_string();
        self.index += 1;
        Some(item)
    }
}

fn main() {
    let data = ["drt".to_string(), "more".to_string(), "tup".to_string()];
    let ads = ["fok".to_string(), "bara".to_string()];
    let grow = GrowingIterable {
        data: data.to_vec().into(),
    };
    let mut ads_i = ads.iter();
    for x in &grow {
        println!("{x}");
        if let Some(el) = ads_i.next() {
            grow.data.borrow_mut().push(el.clone())
        }
    }
}

(playground)


That being said, I would probably just follow the approach in this case of using a while let loop. Those aren't much syntactic overhead anyway. I've used while let replacing for loop before for somewhat comparable cases: for example, if you sometimes want to skip or consume additional items within one loop iteration (by additional calls to .next), that's a simple approach. In my view, pushing extra items to the iterator is similarly affecting the iterator while it's being iterated on in a way that the use of while let syntax can be a good indicator for "careful, we're doing some slightly more complex iteration/loop pattern here".


If you want Iterator-like combinators, another option could be to use some sort of "lending iterator" primitive; and pass a mutable view of the whole data alongside the item. No true for loops, but at least you get a for_each method (and you could do other things like map, filter, and more... with it):

// [dependencies]
// lending-iterator = "0.1.7"

use lending_iterator::prelude::*;

struct GrowingIter {
    data: Vec<String>,
    index: usize,
}

#[gat]
impl LendingIterator for GrowingIter {
    type Item<'a> = (String, &'a mut Vec<String>);

    fn next(&mut self) -> Option<Self::Item<'_>> {
        if self.index == self.data.len() {
            return None;
        }

        let item = self.data.get(self.index).unwrap().to_string();
        self.index += 1;
        Some((item, &mut self.data))
    }
}

fn main() {
    let data = ["drt".to_string(), "more".to_string(), "tup".to_string()];
    let ads = ["fok".to_string(), "bara".to_string()];
    let grow = GrowingIter {
        data: data.to_vec(),
        index: 0,
    };
    let mut ads_i = ads.iter();
    grow.for_each(|(x, data)| {
        println!("{x}");
        if let Some(el) = ads_i.next() {
            data.push(el.clone())
        }
    });
}

Last but not least, for the specific case of appending things to the end of a Vec<String>, this one has an additional property that makes the shared mutability particularly harmless: if you only push new String items to the end of the Vec, that action itself will never affect any of the other existing items (besides possibly moving the String if the Vec grows) so then in particular any &str references stay valid. There are crates that offer APIs to make use of this property, in particular e.g. the elsa crate. With it, you can do the same kind of thing as the RefCell version above, but with less overhead both syntactically, and implementation wise (and no possibility to accidentally hold a "guard" value for too long that it'd produce run-time errors).

Notably, it basically comes with the iterator type you're trying to make here already pre-included :slight_smile:

// [dependencies]
// elsa = "1.11.2"

use elsa::FrozenVec;

fn main() {
    let data = ["drt".to_string(), "more".to_string(), "tup".to_string()];
    let ads = ["fok".to_string(), "bara".to_string()];
    let grow = FrozenVec::from(data.to_vec());
    let mut ads_i = ads.iter();
    for x in grow.iter() {
        println!("{x}");
        if let Some(el) = ads_i.next() {
            grow.push(el.clone())
        }
    }
}

(above, x will be &str)

Thanks for the detailed analysis and several possible solutions. As for now, I follow Occam's Razor rule and replaced

for file in rs_files {

by

for index in 0.. {
                let Some(file) = ext_files.get(index) else {
                    break;
                };