implement EntitySet and iter_many_unique methods

[Victoronz]

Objective

In current Bevy, it is very inconvenient to mutably retrieve a user-provided list of entities more than one element at a time. If the list contains any duplicate entities, we risk mutable aliasing. Users of Query::iter_many_mut do not have access to Iterator trait, and thus miss out on common functionality, for instance collecting their QueryManyIter. We can circumvent this issue with validation, however that entails checking every entity against all others for inequality, or utilizing an EntityHashSet. Even if an entity list remains unchanged, this validation is/would have to be redone every time we wish to fetch with the list. This presents a lot of wasted work, as we often trivially know an entity list to be unique f.e.: QueryIter will fetch every Entity once and only once. As more things become entities – assets, components, queries – this issue will become more pronounced. get_many/many/iter_many/par_iter_many-like functionality is all affected.

Solution

The solution this PR proposes is to introduce functionality built around a new trait: EntitySet.

The goal is to preserve the property of "uniqueness" in a list wherever possible, and then rely on it as a bound within new *_many_unique methods to avoid the need for validation.

This is achieved using Iterator: EntitySet is blanket implemented for any T that implements IntoIterator<IntoIter: EntitySetIterator>. EntitySetIterator is the unsafe trait that actually guarantees an iterator to be "unique" via its safety contract.

We define an "Iterator over unique entities" as: "No two entities returned by the iterator may compare equal." For iterators that cannot return more than 1 element, this is trivially true. Whether an iterator can satisfy this is up to the EntitySetIterator implementor to ensure, hence the unsafe.

However, this is not yet a complete solution. Looking at the signature of iter_many, we find that IntoIterator::Item is not Entity, but is instead bounded by the Borrow<Entity> trait. That is because iteration without consuming the collection will often yield us references, not owned items.

Borrow<Entity> presents an issue: The Borrow docs state that x = y should equal x.borrow() = y.borrow(), but unsafe cannot rely on this for soundness. We run into similar problems with other trait implementations of any Borrow<Entity> type: PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Borrow, and BorrowMut. This PR solves this with the unsafe TrustedEntityBorrow trait: Any implementor promises that the behavior of the aforementioned traits matches that of the underlying entity.

While Borrow<Entity> was the inspiration, we use our own counterpart trait EntityBorrow as the supertrait to TrustedEntityBorrow, so we can circumvent the limitations of the existing Borrow<T> blanket impls.

All together, these traits allow us to implement *_many_unique functionality with a lone EntitySet bound. EntitySetIterator is implemented for all the std iterators and iterator adapters that guarantee or preserve uniqueness, so we can filter, skip, take, step, reverse, ... our unique entity iterators without worry!

Sadly, current HashSet iterators do not carry the necessary type information with them to determine whether the source HashSet produces logic errors; A malicious Hasher could compromise a HashSet. HashSet iteration is generally discouraged in the first place, so we also exclude the set operation iterators, even though they do carry the Hasher type parameter.

BTreeSet implements EntitySet without any problems.

If an iterator type cannot guarantee uniqueness at compile time, then a user can still attach EntitySetIterator to an individual instance of that type via UniqueEntityIter::from_iterator_unchecked. With this, custom types can use UniqueEntityIter<I> as their IntoIterator::IntoIter type, if necessary.

This PR is focused on the base concept, and expansions on it are left for follow-up PRs. See "Potential Future Work" below.

Testing

Doctests on iter_many_unique/iter_many_unique_mut + 2 tests in entity_set.rs.

Showcase

// Before:
fn system(player_list: Res<SomeUniquePlayerList>, players: Query<&mut Player>) {
    let value = 0;
    while let Some(player) = players.iter_many_mut(player_list).fetch_next() {
         value += mem::take(player.value_mut())
    }
}

// After:
fn system(player_list: Res<SomeUniquePlayerList>, players: Query<&mut Player>) {
    let value = players
        .iter_many_unique_mut(player_list)
        .map(|player| mem::take(player.value_mut()))
        .sum();
}

Changelog

• added EntityBorrow, TrustedEntityBorrow, EntitySet and EntitySetIterator traits
• added iter_many_unique, iter_many_unique_mut, iter_many_unique_unsafe methods on Query
• added iter_many_unique, iter_many_unique_mut, iter_many_unique_manual and iter_many_unique_unchecked_manual methods on QueryState
• added corresponding QueryManyUniqueIter
• added UniqueEntityIter

Migration Guide

Any custom type used as a Borrow<Entity> entity list item for an iter_many method now has to implement EntityBorrow instead. Any type that implements Borrow<Entity> can trivially implement EntityBorrow.

Potential Future Work

• ToEntitySet trait for converting any entity iterator into an EntitySetIterator
• EntityIndexSet/Map to tie in hashing with EntitySet
• add EntityIndexSetSlice/MapSlice
  • requires: EntityIndexSet/Map
• Implementing par_iter_many_unique_mut for parallel mutable iteration
  • requires: par_iter_many
• allow collecting into UniqueEntityVec to store entity sets
• add UniqueEntitySlices
  • Doesn't require, but should be done after: UniqueEntityVec
• add UniqueEntityArrays
  • Doesn't require, but should be done after: UniqueEntitySlice
• get_many/many methods
  • requires: UniqueEntityArray
• World::entity_unique to match World::entity methods
  • Doesn't require, but makes sense after: get_many/many
• implement TrustedEntityBorrow for the EntityRef family
  • Doesn't require, but makes sense after: UniqueEntityVec

[bushrat011899]

Haven't had a chance to do a review yet, but just a thought:

Sadly, current HashSet iterators do not carry the necessary type information with them to determine whether the source HashSet produces logic errors; A malicious Hasher could compromise a HashSet.

We could implement EntitySet for particular HashSet's with known-valid hashers:

impl EntitySet for HashSet<Entity, AGoodHasher> { /* ... */ }
impl EntitySet for HashSet<Entity, AnotherGoodHasher> { /* ... */ }
// ...

Or perhaps add another trait, unsafe trait EntitySetHasher: ... { } to allow any HashSet with an appropriate hasher.

[Victoronz]

EntitySet isn't a trait anyone implements! The sole blanket impl stands for: "If its IntoIterator impl produces an EntitySetIterator, it is an EntitySet".
The solution for this is to simply provide a wrapper around HashSet that produces wrapped iterators with a defaulted H = EntityHash generic. A TrustedHasher<H> trait makes sense if we want more than just EntityHash.

However, it is also a question whether/when we want HashSet to implement EntitySet. This is an iteration based trait, and introducing order instability is undesired.

The inconvenient newtyping and order instability leads me to suggest that we add an EntityIndexMap/Set first, so people can use the option with a defined order + are not broken by EntityHashSet becoming a newtype. Of course, it also makes sense to do this for EntityHashSet, but it should come after the Index version imo.

The true solution is to ask rust-lang to add a defaulted S = RandomState parameter to the HashSet/HashMap iterator types. This is not a breaking change, and just requires slapping a PhantomData onto the inside of these types.

[bushrat011899]

Ah ok, apologies for the misunderstanding, I fixated on that point! I'll give the full PR a review at some point this weekend

[chescock]

However, it is also a question whether/when we want HashSet to implement EntitySet. This is an iteration based trait, and introducing order instability is undesired.

I think we want EntityHashSet to work with these methods, since that's the canonical way to store a set of unique entities. There will be plenty of cases where you want to query data for multiple entities but don't care about the order. For example, you could have a set of inventory items and want to calculate the total weight.

Would it work to offer a safe method to create a UniqueEntityIter<_> from an &EntityHashSet? That should be sound to implement, and it means EntityHashSet is usable with these methods with just one extra method call.

[Victoronz]

I think we want EntityHashSet to work with these methods, since that's the canonical way to store a set of unique entities. There will be plenty of cases where you want to query data for multiple entities but don't care about the order. For example, you could have a set of inventory items and want to calculate the total weight.

Would it work to offer a safe method to create a UniqueEntityIter<_> from an &EntityHashSet? That should be sound to implement, and it means EntityHashSet is usable with these methods with just one extra method call.

I agree that we would like this to work with EntityHashSet. Because I'd like to bundle such an impl with EntityIndexSet, I'd like to do this/discuss it further in a follow-up PR. This one is already over 800 lines! (I've already written the code for EntityIndexSet, I intentionally stripped it here)