How to implement iterator where next elements depends on previous elements mutation?

help
#1

Heya, I'm trying to implement a function that returns an iterator over mutable references of Things, where subsequent Things may be returned based on mutated state of previously returned Things.

Code probably expresses this better than English (playground):

struct Thing {
    related_things_processed: bool,
}
struct Things(Vec<Thing>);

// Trying to implement this
fn iterate(things: &mut Things) -> impl Iterator<Item = &mut Thing> + '_ {
    std::iter::repeat_with(|| {
        things
            .0
            .iter_mut()
            .filter(|item| item.related_things_processed)
        
        // based on things[0] changing state, things[1] may be returned in the next iteration
    })
    .flatten()
}

fn main() {
    iterate(&mut Things(vec![
        Thing {
            related_things_processed: true,
        },
        Thing {
            // this may be set to true between iterations of things
            related_things_processed: false,
        },
    ]));
}

The error message:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/main.rs:9:9
   |
9  | /         things
10 | |             .0
   | |______________^
   |
note: first, the lifetime cannot outlive the lifetime `'_` as defined on the body at 8:28...
  --> src/main.rs:8:28
   |
8  |     std::iter::repeat_with(|| {
   |                            ^^
note: ...so that closure can access `things`
  --> src/main.rs:9:9
   |
9  | /         things
10 | |             .0
   | |______________^
note: but, the lifetime must be valid for the anonymous lifetime #1 defined on the function body at 7:1...
  --> src/main.rs:7:1
   |
7  | fn iterate(things: &mut Things) -> impl Iterator<Item = &mut Thing> + '_ {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that return value is valid for the call
  --> src/main.rs:7:36
   |
7  | fn iterate(things: &mut Things) -> impl Iterator<Item = &mut Thing> + '_ {
   |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

As I understand it, the problem is the lifetime of the inner iterator value is different from closure invocations, and I haven't managed to convince Rust it's okay. I've tried implementing Iterator on a struct, but pretty much get the same error.

#2

If you have a mutable reference to some memory, you can have no other references to that memory. (Exclusive reference would be a more accurate description than mutable reference.) So to begin with, once you return a mutable reference to part of the slice, your iterator can no longer be able to reference that part of the slice. (split_at_mut() can be used to do this safely if you're implementing something yourself, but you're just using repeat_with. The closure captures the mutable reference to things.)

Next we'll consider the iterator overall. Let's consider what would happen if the compiler allowed this with your example case. Let's also give your example input to iterate() a name, input. Because the field of input[0] is true, the first thing returned from the iterator is a mutable reference to input[0]. Let's say we don't change the value of the field; it remains true. The next return from the iterator will also be a mutable reference to input[0]:

// as in your main function
let mut input: Things = ...;
let mut iter = iterate(&mut input);
let one = iter.next(); // &mut input[0]
let two = iter.next(); // &mut input[0], again

And again, this is not allowed. That's why you can't convince Rust that it's okay :slight_smile:.

1 Like
#3

ah! Thank you :bowing_man: -- I think I get it. The iterator created from iter::repeat_with(..) may be invoked twice, and I have to tell Rust "don't let RepeatWith::next() be called until the previous element has been released", which probably means iter::repeat_with isn't the right thing to use.

I guess that means it should be a method on Things, which produces the &mut Thing iterator, and the caller repeatedly calls that (until it's happy that there wouldn't be any more Thing objects in subsequent iterators).

#4

This pattern is referred to as a "lending iterator" (or "streaming", but that usually means something different now due to async). Unfortunately it is not yet possible in Rust. More about why can be found in the beginningof RFC 1598.

You can do something like that, though it won't be a proper iterator (e.g. you can't use it with for, which consumes the iterator): playground example.

If you want a proper iterator, you would need interior mutability, if that's even an option for your use case.

2 Likes
#5

If your Things are simple enough to implement Copy, you can do something like this, which doesn't require you to have Cells everywhere:

fn iterate(things: &mut Things) -> impl Iterator<Item = &Cell<Thing>> + '_ {
    let thing_cells: &[Cell<Thing>] =
        Cell::from_mut(&mut *things.0).as_slice_of_cells();

    std::iter::repeat_with(move || {
        thing_cells.iter()
            .filter(|item| item.get().related_things_processed )
        
        // based on things[0] changing state, things[1] may be returned in the next iteration
    })
    .flatten()
}

(Playground)

2 Likes