Iterate over items with same index in different arrays

Question

I'm having a hard time doing this, and every attemps, I am getting issues I can't manage to resolve.

for context :

I'm building an entity component system, where the components are packed arrays in an anymap. What I call a packed array is a data structure that would look like an array with lots of empty slots, with index being entity id: for instance, the component at index 5 is the component attached to the entity of id 5. Since not all entities have all components, there are lots of empty slots, so a packed array is a Vec of IndexedElem to keep the data tight in memory:

pub struct PackedArray {
    data: Vec>,
}

pub struct IndexedElem {
    pub index: usize,
    pub elem: T
}

Now, the component table itself is an AnyMap of these PackedArray:

pub struct ComponentTable {
    components: anymap::Map,
}

So I have all the basics, like creating entities, adding / removing / getting components.

But now, I want to be able to iterate over components (that is the whole point of keeping components in a table of packed arrays).

It's easy to iterate over 1 component, I simply iterate over the Vec. Where I'm struggling, is to iterate over several components:

Let's say I want to iterate over all pairs of components C1 and C2 (meaning all entities that have both C1 and C2)

The idea is to get iterators of these two packed arrays, then I have a current_entity_id that starts at 0, I look if the IndexedElem of both iterator is the same as the id, returns the two elems if it's the case, go to the next one if not.

In theory, I will now how to build this, but I'm struggling a lot implementing it in rust, with lifetimes, ownerships, etc...

Here is my last attempt :

I have a ComponentIterator_2 struct, implementing the iterator trait with type being (C1, C2) :

pub struct ComponentIterator_2<'a, C1, C2> {
    iterator_1: std::slice::IterMut<'a, IndexedElem>,
    iterator_2: std::slice::IterMut<'a, IndexedElem>,
    current_entity: usize,
}

But when I try to build it like so :

    pub fn iterate_over_2_component<'a, C1: 'static, C2: 'static>(&'a mut self) -> Option> {
        return Some(ComponentIterator_2:: {
            iterator_1: match self.components.get_mut::>() {
                None => return None,
                Some(packed_array) => packed_array.iter_mut(),
            },
            iterator_2: match self.components.get_mut::>() {
                None => return None,
                Some(packed_array) => packed_array.iter_mut(),
            },
            current_entity: 0,
        });
    }

Here I can't borrow self.components twice, which I understand, but I can't get around it.

I've tried many other things, but I've struggled enough to ask for help here now !

So I would be really pleased if anyone could give me hints on ho to implement this properly, and if possible in an efficient way.

The whole project (The ecs, nothing more around it) is available on my GitHub.

user_7884305 · Answer

You need to use interior mutability.

This sounds a good place for RefCell, but unfortunately I don't think you can use it. You don't have where to store the guard.

So, you need to use UnsafeCell. But you need to be careful and ensure the component types are unique, otherwise you would get undefined behavior! This can be done by comparing their TypeIds.

pub struct PackedArray {
    data: UnsafeCell>>,
}

pub fn iterate_over_2_component<'a, C1: 'static, C2: 'static>(&'a mut self) -> Option> {
    assert_ne!(TypeId::of::(), TypeId::of::(), "cannot use a component twice for `iterate_over_2_component()`");

    return Some(ComponentIterator_2:: {
        iterator_1: match self.components.get::>() {
            None => return None,
            // SAFETY: We have a `&mut` reference, so the only borrow that can coexist is 
            // the second component, and we verified they're distinct types so they
            // have distinct entries.
            Some(packed_array) => unsafe { &mut *packed_array.get() }.iter_mut(),
        },
        iterator_2: match self.components.get::>() {
            None => return None,
            // SAFETY: See the comment on the previous component.
            Some(packed_array) => unsafe { &mut *packed_array.get() }.iter_mut(),
        },
        current_entity: 0,
    });
}

user_16092107 · Answer

After lots of trial and error, I've done it !

I've added a ComponentArray That is a wrapper for an UnsafeCell>,as suggested. This allow to borrow multiple vectors from the component table, then I keep track of every index in these vectors to iterate over them.

I've even braught this a step forward, as I've implemented a macro that allows to iterate over any number of components. Here it is (it's a bit a pack of nonsense at this point)


#[macro_export]
macro_rules! fn_internal_get_next_elem {
    ($elem_type:ty; $first:path, $($elems:path),*) => {
        fn macro_generated_return_next(elem: $elem_type) -> $elem_type {
            match elem {
                $first => 
                $($elems, $elems =>)*
                $first
            }
        }

        fn macro_generated_reset() -> $elem_type {
            $first
        }
    }
}

#[macro_export]
macro_rules! iterate_over_component {
    ($ecs:expr; $($comp:ident),+) => {
        {
            // use statments to import everything that is needed
            use crate::utils::collections::packed_array::IndexedElem;
            use crate::ecs::component_array::ComponentArray;

            // use an enum to get an id per component !
            #[derive(Copy, Clone)]
            enum MacroGeneratedComponentsEnum {
                $(
                    $comp,
                )+
                EndOfIterator
            }

            // generate methods to go to next components enum
            fn_internal_get_next_elem!(MacroGeneratedComponentsEnum; $(MacroGeneratedComponentsEnum::$comp, )+ MacroGeneratedComponentsEnum::EndOfIterator);

            // struct to pack both a vec and a index
            struct MacroGeneratedIterableVec<'a, T> {
                vec: Option<&'a Vec>>,
                index: usize,
            }
            // create the result struct that will act as an iterator
            struct MacroGeneratedComponentIterator<'a, $($comp),+> {
                current_iterator: MacroGeneratedComponentsEnum,
                current_entity: usize,
                $(
                    $comp: MacroGeneratedIterableVec<'a, $comp>,
                )+
            }

            // implement the iterator 
            impl<'a, $($comp),+> Iterator for MacroGeneratedComponentIterator<'a, $($comp),+> {
                type Item = ($(&'a $comp),+);
                fn next(&mut self) -> Option {
                    // a bit tricky but allows static enums as values :
                    // create usize vars of name comp that store their enums values
                    $(
                        let $comp: usize = MacroGeneratedComponentsEnum::$comp as usize;
                    )+
                    loop {
                        match self.current_iterator {
                            $(
                                MacroGeneratedComponentsEnum::$comp => {
                                    // checking for first component
                                    while match self.$comp.vec {
                                        None => return None,
                                        Some(array) => {
                                            match array.get(self.$comp.index) {
                                                None => return None, // out of element on first vec, end of iterator
                                                Some(i_elem) => {
                                                    // use this to update values
                                                    if i_elem.index < self.current_entity {
                                                        // true to keep the while loop and increment index
                                                        true
                                                    }
                                                    else {
                                                        // if we are bigger than current entity, update entity to match ourselves
                                                        if i_elem.index > self.current_entity {
                                                            // update entity to align to our component
                                                            self.current_entity = i_elem.index;
                                                            // reset current iterator because we went to next entity, so need to get again all components
                                                            self.current_iterator = macro_generated_reset();
                                                            // note that the while loop will end, so the loop will come back to this point
                                                            // except it will then go to the else and increment the current iterator
                                                            // this is a design choice so this code is similar in every arm of the match on self.current_iterator
                                                        }
                                                        else {
                                                            // check next iterator, we are at the component of current entity
                                                            self.current_iterator = macro_generated_return_next(self.current_iterator);
                                                        }
                                                        false // go to next iterator, so end while loop
                                                    }
                                                },
                                            }
                                        }
                                    } {
                                        // advance current index of array 1 to match with current entity
                                        self.$comp.index += 1;
                                    }
                                }
                            )+
                            _ =>{
                                                    // here, all arrays index have matched the entity, so let's return the components !
                                let result = Some((
                                    $(
                                        match self.$comp.vec {
                                            None => return None, // shouldn't happen, but safety
                                            Some(array) => match array.get(self.$comp.index) {
                                                None => return None, // shouldn't happen, but safety
                                                Some(i_elem) => &i_elem.elem,
                                            }
                                        }
                                    ),+
                                ));
                                // update to next entity for iterator
                                self.current_entity += 1;
                                // reset iterator counter
                                self.current_iterator = macro_generated_reset();
                            
                                return result;
                            }
                        }
                    }
                }
            }

            // get the comp map once to avoid multi borrow issues (we have unsafe cell for vectors)
            let mut comp_map = ECS::get_unsafe_component_map($ecs);

            MacroGeneratedComponentIterator::<$($comp),+> {
                current_iterator: macro_generated_reset(),
                current_entity: 0,
                $(
                    $comp: MacroGeneratedIterableVec {
                        vec: match comp_map.get::>() {
                            None => None,
                            Some(comp_arr) => Some(comp_arr.get_array()),
                        },
                        index: 0,
                    },
                )+
            }
        }
    };
}

Anyway, it works well ! the code of the whole project is available on my git.

Iterate over items with same index in different arrays

2 Answers