How to rewind or recreate an iterator trait object?

help
1

Background

I have a vector of boxed trait objects

trait Structure{
  fn frame_proc(&mut self) -> Result<(), ()>;
}

// ...

structures: Vec<Box<dyn Structure>>

and I want to call a mutable method of each of the trait object in the vector.

for structure in &mut structures {
   structure.frame_proc()?;
}

However, the problem is that I want to refer to the other trait objects inside frame_proc.
It might mutate the other objects, depending on the implementation of the trait.

Obviously, I can't pass a mutable reference to the vector at the same time as the trait's &mut self. So I came up with a method to split the vector into mutable slices and exclude the one that I will invoke trait method on.

trait Structure{
    fn frame_proc(
        &mut self,
        structures: &mut dyn Iterator<Item = &mut Box<dyn Structure>>,
    ) -> Result<(), ()>;
}

// ...

for i in 0..structures.len() {
    if 0 < i {
        let (front, mid) = structures.split_at_mut(i);
        let (center, last) = mid
            .split_first_mut()
            .ok_or(())?;
        center.frame_proc(&mut front.into_iter().chain(last.into_iter())),
    } else {
        let (center, last) = structures
            .split_first_mut()
            .ok_or(())?;
        center.frame_proc(&mut last.iter_mut())?;
    }
}

The new frame_proc takes an Iterator trait object, which iterates over the vector except itself, so that the borrow checker is happy.

The problem

This worked well and nice, but there is a small issue. I can't use the iterator more than once in frame_proc. Once the iterator returns the other structures, it remains exhausted. Because it is an iterator, I can't rewind or recreate the iterator from original slice.

I tried to put a Fn trait object as an argument, which returns new iterator every time it is called, but in order to make it work, the Iterator has to be inside a Box (because it is a trait object). But now I can't prove that the boxed iterator won't outlive original slice.

trait Structure{
    fn frame_proc(
        &mut self,
        _iter_structures: &dyn Fn() -> Box<dyn Iterator<Item = &mut Box<dyn Structure>>>,
    );
}
let (front, mid) = structures.split_at_mut(i);
let (center, last) = mid
let mut iter = front.into_iter().chain(last.into_iter());
let mut iter_copy = || Box::new(iter);

What I don't want to do is to create a new vector of references to the original structures. It would surely work, but the vector can be hundreds or thousands long. I don't want to copy the whole vector into temporary buffer every time I iterate.

trait Structure{
    fn frame_proc(
        &mut self,
        _structures: &Vec<&mut Box<dyn Structure>>,
    ) -> Result<(), ()>;
}

let vec = front.into_iter().chain(last.into_iter())
            .collect::<Vec<_>>();
center.frame_proc(self, &vec)?;

All I need is just rewind or recreate the iterator behind the mutable reference. Does someone have a good solution?

2

I think you can just keep your slices around and do something like this:

let chain_iter = front.iter_mut().chain(last.iter_mut());
center.frame_proc(&mut chain_iter);
let chain_iter = front.iter_mut().chain(last.iter_mut());
center.frame_proc(&mut chain_iter);
3

I'm sorry I didn't make myself clear. I want to use the iterator multiple times inside frame_proc.

impl Structure for SomeTypeThatImplementsStrcuture{
    fn frame_proc(
        &mut self,
        structures: &mut dyn Iterator<Item = &mut Box<dyn Structure>>,
    ) -> Result<(), ()> {
        for structure in structures {
            do_something(structure);
        }
        for structure in structures {
            do_something_else(structure);
        }
        Ok(())
    }
}

How many times it iterates is up to the implementation of the Structure trait, so the calling site has no knowledge.

4

I don't think that's possible given the semantics of the Iterator trait and the Iterator::next() method in particular.

On the other hand, if you pass the slices around, you can recreate the iterators whenever you need them.

2 Likes
5

Ah ok, sorry.

To expand on @jjpe's comment, consider this modification of your example:

        // next line is new
        let x = structures.next().unwrap();

        for structure in structures {
            do_something(structure);
        }

        // structures somehow resets here
        for structure in structures {
            // First time in this loop, we get `x == structure`
            // That's an only-one-mutable-reference violation
            do_something_else(structure);
        }
6

Yes, I understand it would violate borrow checking rules. I wouldn't store the reference until next loop. All the necessary side effect should be applied to the structures' states in do_something before I go to do_something_else.

That would be the same if I iterate twice in the caller side, like below, right?

let chain_iter = front.iter_mut().chain(last.iter_mut());
let x = chain_iter.next().unwrap();
center.frame_proc(&mut chain_iter);
let chain_iter = front.iter_mut().chain(last.iter_mut());
center.frame_proc(&mut chain_iter);
7

As others already noted... [took me a while to finish the playground below]: As long as it’s an iterator returning mutable references you cannot restart it, otherwise you’d be able to get a second copy of the same mutable references.

You can however create an abstraction around creating an iterator from a re-borrow of structures, e.g. like this: (playground)

3 Likes
8

Wow, thank you for thorough solution. I was about to give up and use two slices in the argument, which is ugly solution.

fn frame_proc(
        &mut self,
        front: &mut [Box<dyn Structure>],
        last: &mut [Box<dyn Structure>],
    ) -> Result<(), ()>;

I will try your solution and if it doesn't work well I will consider giving 2 slices.

One thing I didn't understand:

As long as it’s an iterator returning mutable references you cannot restart it, otherwise you’d be able to get a second copy of the same mutable references.

Isn't it ok if I drop all the references before restarting? The compiler should be able to observe all possible references are dropped, right?

9

Hmm, maybe if I re-phrase it and elaborate a bit, that helps.

In my solution you can observe that if structures has type &'big_lifetime mut dyn ..., then .dyn_iter_mut() gets called on a re-borrow of type &'smaller_lifetime_a mut dyn ... and returns an iterator with item type &'smaller_lifetime_a mut Item. After one finishes using this iterator (and the references it yielded), the iterator can be dropped and the re-borrow can end; then a second re-borrow with lifetime 'smaller_lifetime_b that doesn’t overlap the 'smaller_lifetime_a can produce a second iterator with item type &'smaller_lifetime_b mut Item.

So in my code, the item type of the iterators changes between different iterations (since the lifetime changes).

If however structures itself already had an iterator type then its item type would be fixed to some &'some_lifetime mut Item. Thus some kind of fn(&mut self)-typed "restart" function on such an iterator is not possible since everything would still be happening withing the 'some_lifetime scope and thus the compiler can not prevent the references from the first iteration being kept around.

10

It's fundamentally impossible. Iterator is not a collection. It has no guarantee that any data you iterated over will still exist at the end of the iteration (e.g. when item ownership is passed to you).

In Rust, iterators are just a single function that returns the next element or nothing (all other Iterator methods are sugar built on top of that).

Rust doesn't have a trait that is a generic abstraction over collections. For contiguous data, slices are the closest one. Otherwise you'll need to make your own iterator factory.

11

I think I misunderstood iterators like begin/end pairs of C++. What I needed is a bit more than an iterator, but also a bit more general than slices.

Now @steffahn's solution works quite well for my application. However there is still one thing missing.

I tried to implement immutable version of the iterator:

pub(crate) trait DynIter {
    type Item;
    fn dyn_iter(&mut self) -> Box<dyn Iterator<Item = &Self::Item> + '_>;
}
impl<T, Item> DynIter for T
where
    for<'a> &'a mut T: IntoIterator<Item = &'a Item>,
{
    type Item = Item;
    fn dyn_iter(&mut self) -> Box<dyn Iterator<Item = &Self::Item> + '_> {
        Box::new(self.into_iter())
    }
}

and it works for immutable methods,

trait Structure{
    fn draw(&self, structures: &mut dyn DynIter<Item = Box<dyn Structure>>);
}

but when I tried to pass DynIterMut to an immutable method from mutable method, I can't convert it to DynIter.

fn frame_proc(
    &mut self,
    structures: &mut dyn DynIterMut<Item = Box<dyn Structure>>,
) -> Result<(), ()> {
    self.draw(structures); //!!!
    Ok(())
}

The only difference is the immutability of iterated type, so it should be able to convert, right?

Of course, if I have to call the immutable method from where I have original vector, I can just pass the slice without splitting into weird pieces.

    fn draw(&self, structures: &[Box<dyn Structure>]);

But it would lose the genericity of being able to call from mutable method.

12

Without having read your whole post in detail, here’s how I’d add an immutable variant: (playground).

Edit: wait.. perhaps the conversion still doesn’t work 100%, one moment...
Edit2: This should work out for you: (playground)

2 Likes
13

Wow. Awesome. It worked perfectly. With slices and DynRefMut.

Thank you so much for your help!
Now I have to trace and understand the wizardly..

14

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.