Writing an `impl Iterator<Item=&T>` for a `Ref<Vec<T>>`

Hello!

I'm making a struct that holds a std::cell::Ref to a data structure. This struct will then implement Iterator and return references to the elements contained in the data structure.

The usage of Ref is a constraint that other parts of my codebase require. To make this thread easier to reason about, I will skim over these details and focus on the particular issue.

I've tried a couple of solutions but I just cannot get it to compile.

Here's a minimal example: Rust Playground

As I understand it: I cannot return references from next that live as long as the iterator because they cannot outlive the reference &mut self from which they are created.

Reasoning about it, I would say there should be some way to do this right? I mean, as long as the iterator is alive, then the std::cell::Ref to the data structure is alive, therefore I should be able to return references that live that long.

To make things more confusing, as soon as I hold the datastructure as a &'a T instead of a Ref<'a ,T, everything suddenly works: Rust Playground

The problem is that Iterator requires that the emitted items are able to both coexist and outlive the iterator. Because the Ref is a guard object, it can't be destroyed until after all of the references it's generated are gone and there's no place to keep it-- Otherwise, there's nothing preventing code from calling borrow_mut() on the original RefCell while the iterator's results are still alive.

What you can do is return a Ref<'a, i32> from the iterator:

impl<'a> Iterator for Iter<'a> {
    type Item = Ref<'a,i32>;
    
    fn next(&mut self) -> Option<Self::Item> {
        if self.at < self.vec.len() {
            self.at += 1;
            Some(Ref::map(Ref::clone(&self.vec), |vec| &vec[self.at - 1]))
        } else {
            None
        }
    }
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=be8cae011b1f71c64afc29574c9657bb

3 Likes

Oh that makes sense, my iterator would definitely return items that outlive it.

Unfortunately I was trying to do something that would be applicable to a mutable iterator as well, with minimal modifications. And RefMut does not have clone. So I will have to look for another solution.

To give more details: basically I have a struct (let's call it World) that holds several data structures (let's call them Pool<T>) and I need to iterate over their intersection, both immutably and mutably.

Originally I used references but I moved to RefCell thinking that it was the only way to mutably borrow more than one pool at a time because I could implement a World::get_pool_mut<T>(&self) -> RefMut<Pool<T>> instead of a World::get_pool_mut<T>(&mut self) -> RefMut<Pool<T>>

I keep hitting roadblocks though and I'm starting to feel like RefCell isn't the right tool for the job.

Maybe I should write some unsafe code to take in a &mut World, split it into many &mut Pool<T> and then split those into many &mut T and iterate over them?

It's possible to do a mutable version in safe code!

First, here's a modification of Iter that's built on splitting a slice:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=72bb92b58547408de1ed507dac4da112

Now we can do the same for an IterMut, but as you noted there's no RefMut::clone. Instead, we can store that as an Option<RefMut<..>>, then take() it to split and write back the remainder.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=18e45c551d8ebe2325e26cc2ff11b7bd

3 Likes

This is really cool! Thank you a ton :heart_eyes:

I eventually got it to work without using unsafe code. I just needed to wrap in RefCell each individual element of the pools instead of each pool as a whole.

This way I can mutably borrow each element of a pool without needing to mutably borrow from the pool multiple times (wouldn't be allowed).

The usage of RefCell is hidden from the outside by using impl Deref and impl DerefMut. Also, the iterators are the only ones allowed to take multiple mutable references to the pools' elements. The user of the crate would use get<T: Component>(&mut self) even though the mut is not strictly necessary. This should prevent runtime borrowing errors.

1 Like