add a QueryManyUniqueIter by Victoronz · Pull Request #13477 · bevyengine/bevy

Victoronz · 2024-05-22T17:51:34Z

Objective

~~Requires #13476~~.

Currently we cannot iterate mutably over QueryManyIter even if all entities we pass are unique.

Solution

Add a QueryManyUniqueIter wrapper around QueryManyIter for full Iterator trait iteration.
It can be constructed via either the dedup_entities or entities_all_unique method on QueryManyIter.
dedup_entities deduplicates the internal entity_iter, retaining order.
entities_all_unique takes self, checks for uniqueness, returns QueryManyUniqueIter on success, and QueryManyIter (Self) on failure.
Since QueryManyUniqueIter can iterate over mutable QueryData , it does not expose a fetch_next method.

Testing

The example/doc test shows the method in use, also making sure expect can be called on the return Result.

Changelog

Added dedup_entities and entities_all_unique methods on QueryManyIter.
Added QueryManyUniqueIter struct.

# Objective The current query iterators cannot be used in positions with a `Debug` bound. F.e. when they are packaged in `Result` in the error position, `expect` cannot be called on them. Required for `QueryManyIter::entities_all_unique` in #13477. ## Solution Add simple `Debug` impls that print the query iterator names. ## Changelog `QueryIter`, `QueryManyIter`, `QueryCombinationIter`, and `QuerySortedIter` now implement `Debug`.

chescock · 2024-06-30T21:41:05Z

crates/bevy_ecs/src/query/iter.rs

+{
+    // Entities are guaranteed to be unique, so no lifetime shrinking needed for mutable iteration.
+    #[inline(always)]
+    fn fetch_next(&mut self) -> Option<D::Item<'w>> {


This duplicates the code in QueryManyIter::fetch_next_aliased_unchecked(). Could you share the implementation by having QueryManyUniqueIter wrap a whole QueryManyIter, and then implement Iterator::next() by calling fetch_next_aliased_unchecked() on the inner QueryManyIter?

IIRC, I was not sure whether the uniqueness property could simplify the next() call, so I kept them separate, but looking at it again, you're right, this can just be wrapper type! Good idea.

chescock · 2024-06-30T21:49:37Z

crates/bevy_ecs/src/query/iter.rs

+    /// # schedule.run(&mut world);
+    /// ```
+    #[inline(always)]
+    pub fn entities_all_unique(


It might be useful to have methods to construct a QueryManyUniqueIter directly from a few iterator types that can already guarantee uniqueness, such as HashSet. That could let users skip the overhead of the uniqueness check.

It might also be useful to have a method that removes duplicates instead of returning Err, by doing something like

entity_iter: self .entity_iter .map(|e| *e.borrow()) .collect::<EntityHashSet>() .into_iter(),

(Those could always be done in future PRs, of course.)

I agree with the methods to construct from unique iterators. What other source iterator types would you suggest?

Deduplication can already be done on the iterator itself with itertools, so isn't as important to have as the others. Still a nice to have though.
I wonder whether a sort + dedup would be faster than your HashSet version.
Edit: Actually just collecting into a BTreeSet might be simpler and faster. None of these retain input order however, that would be more expensive.

I think I'll make these separate follow-up PRs, since I have to keep these changes in line with #13443.

I have added dedup_entities on QueryManyIter to this PR anyway.

also adds: a Debug impl associated type bounds in the struct and impl definitions a missing unsafe block in QueryManyIter

chescock · 2024-07-02T17:42:31Z

crates/bevy_ecs/src/query/iter.rs

-                .get(location.archetype_id)
-                .debug_checked_unwrap();
-            let table = self.tables.get(location.table_id).debug_checked_unwrap();
+            let (archetype, table);


This is good cleanup, but could probably be a separate PR.

Fair, I'll put it in a different PR.

Victoronz · 2024-07-02T17:49:30Z

I wonder whether it might be easier to have a direct Query::iter_many_unique method instead of these roundabout conversions on QueryManyIter.

Victoronz · 2024-07-13T19:00:11Z

I have come up with a more powerful, general solution, which I think I will put in a different PR. I'll keep this open as the simpler alternative.

This PR would also need to be updated with a TrustedEq: Eq trait, because even though we only use it for Entity, unsafe code must not rely on an Eq trait impl for correctness, because Eq itself does not contain a logical correctness guarantee.
That being said, this would be a simple unsafe marker trait impl on Entity stating the safety contract.

Victoronz · 2024-11-28T21:18:21Z

This PR is now superseded by the concept of #16547, though the actual conversion API would be a follow-up to that PR.

Victoronz · 2024-12-20T18:09:18Z

#16547 has merged.

Victoronz mentioned this pull request May 22, 2024

simple Debug impls for query iterators #13476

Merged

Victoronz force-pushed the entities_all_unique branch from f4f433e to cabaf73 Compare May 22, 2024 17:54

add entities_all_unique to QueryManyIter

3c502c4

Victoronz force-pushed the entities_all_unique branch from cabaf73 to 3c502c4 Compare May 22, 2024 19:33

Victoronz added S-Needs-Review Needs reviewer attention (from anyone!) to move forward and removed S-Blocked This cannot move forward until something else changes labels May 22, 2024

chescock reviewed Jun 30, 2024

View reviewed changes

Victoronz added 2 commits July 2, 2024 19:28

make QueryManyUniqueIter a wrapper around QueryManyIter

1d63a3e

also adds: a Debug impl associated type bounds in the struct and impl definitions a missing unsafe block in QueryManyIter

add dedup_entities method

122dc8d

chescock approved these changes Jul 2, 2024

View reviewed changes

Victoronz changed the title ~~add entities_all_unique to QueryManyIter~~ add a QueryManyUniqueIter Jul 2, 2024

Victoronz added S-Waiting-on-Author The author needs to make changes or address concerns before this can be merged and removed S-Needs-Review Needs reviewer attention (from anyone!) to move forward labels Jul 14, 2024

chescock mentioned this pull request Nov 1, 2024

implement the full set of sorts on QueryManyIter #13443

Merged

Victoronz closed this Dec 20, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

add a QueryManyUniqueIter#13477

add a QueryManyUniqueIter#13477
Victoronz wants to merge 3 commits intobevyengine:mainfrom
Victoronz:entities_all_unique

Victoronz commented May 22, 2024 •

edited

Loading

Uh oh!

chescock Jun 30, 2024

Uh oh!

Victoronz Jul 1, 2024

Uh oh!

chescock Jun 30, 2024

Uh oh!

Victoronz Jul 1, 2024 •

edited

Loading

Uh oh!

Victoronz Jul 2, 2024

Uh oh!

chescock Jul 2, 2024

Uh oh!

Victoronz Jul 2, 2024

Uh oh!

Victoronz commented Jul 2, 2024

Uh oh!

Victoronz commented Jul 13, 2024 •

edited

Loading

Uh oh!

Victoronz commented Nov 28, 2024

Uh oh!

Victoronz commented Dec 20, 2024 •

edited

Loading

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Uh oh!

Conversation

Victoronz commented May 22, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Objective

Solution

Testing

Changelog

Uh oh!

chescock Jun 30, 2024

Choose a reason for hiding this comment

Uh oh!

Victoronz Jul 1, 2024

Choose a reason for hiding this comment

Uh oh!

chescock Jun 30, 2024

Choose a reason for hiding this comment

Uh oh!

Victoronz Jul 1, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Victoronz Jul 2, 2024

Choose a reason for hiding this comment

Uh oh!

chescock Jul 2, 2024

Choose a reason for hiding this comment

Uh oh!

Victoronz Jul 2, 2024

Choose a reason for hiding this comment

Uh oh!

Victoronz commented Jul 2, 2024

Uh oh!

Victoronz commented Jul 13, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Victoronz commented Nov 28, 2024

Uh oh!

Victoronz commented Dec 20, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Victoronz commented May 22, 2024 •

edited

Loading

Victoronz Jul 1, 2024 •

edited

Loading

Victoronz commented Jul 13, 2024 •

edited

Loading

Victoronz commented Dec 20, 2024 •

edited

Loading