Add a Removed query filter

[alice-i-cecile]

What problem does this solve or what need does it fill?

The existing RemovedComponent API is somewhat unclear and cumbersome. It also commonly requires a manual query filtering step to make use of, which is both slow and full of boilerplate.

What solution would you like?

I want to be able to add Removed<T> to my queries as a filter to only include entities that have had the component removed since the system last ran using reliable change detection.

What alternative(s) have you considered?

We could also store the values of the removed components, but that won't be feasible with reliable change detection.

Additional context

With the addition of subworlds / multiple worlds (bevyengine/rfcs#16), we could move removed components to a parallel purgatory subworld for two frames using a double-buffer pattern, allowing us the ability to access removed data.

#13928 offers another way to remove RemovedComponents, which should be pursued. It may still be worth having a Removed filter after that, but its value is much less clear.

[lukewestby]

Could this be implemented prior to subworlds just as a filter, in such a way that Query<&MyComponent, Removed<MyComponent>> would be empty? I think that such an implementation would be useful - as you said, Query<Entity, (Removed<MyComponent>, OtherFilter)> is a lot nicer than RemovedComponents<MyComponent> and manual filtering. However, it could be confusing to later totally change the semantics of the query using subworlds so that Query<&MyComponent, Removed<MyComponent>> does return data.

[alice-i-cecile]

Yep, this should be totally feasible before subworlds. I think that only allowing it in the filter position for now is just fine; we're always going to want that ability.

Once we can access the removed data I think that the correct approach is to do something like Query<MyData, (), Purgatory> with the third type parameter representing the world it's drawing from rather than trying to implicitly overload the Removed type with different durations based on which position it's in.

[alice-i-cecile]

From my draft of the relevant section of the book:

1. While Added and Changed operate on the basis of "since the last time this system ran", removal detection only works for the last frame. This distinction is very important if your system does not run every frame due to states or run criteria.
2. RemovedComponents does not return the value of the component that was removed, due to performance concerns. If you need this, you will need to include your own change-detecting system to cache the values before they are removed.
3. RemovedComponents is a system parameter, not a query filter. As a result, you will have to manually compare it to the results of a query if you only need to handle some subset of component removal events.

[viridia]

This was brought up recently in #22332

I think the existing example serves as an excellent illustration of why RemovedComponents is painful: not only can you not use regular change detection to detect removed components, you can't even use RemovedComponents in combination with a query that also uses other change detection (like added or changed) - instead, you have to use two independent queries. While it's possible to paper over these differences, the cost is increasing abstraction that makes the code harder to understand.

The right solution, of course, is to make component removal work like a regular query filter. This is difficult, however: it's hard for Bevy to filter on a component that no longer exists, which means that you have to keep around some auxiliary data, a journal of removals (which is what RemovedComponents basically does). Building this journal isn't free, and it needs to be kept around long enough to be polled by systems that want to know about removals. With regular change detection, we can poll the last change tick of a component at any point in the future, even across frame boundaries, but obviously we can't keep the journal of removed items indefinitely.

RemovedComponents keeps the costs of building the journal low by building it sequentially; however, this means that it has to be read sequentially as well, making it unsuitable as a query filter. To solve this, we would need a fast random-access set membership test. For example, if the removed components journal was a hash set, this would work, but would make building the journal more expensive (a cost which gets paid even if the journal is never read). Bloom filters might be one way to have both fast building and fast querying of the journal, but this would make performance highly non-deterministic, which I don't think Bevy users would appreciate very much.

It would be helpful, in solving this, if we could nail down some of the ambiguities in the requirements:

• What guarantees around ordering do we plan to have? For example, if a component is removed in a system in, say, PostUpdate in frame N, can the removal be detected by a system in PreUpdate in frame N+1? Or can removals only be detected within the same frame, by systems that run later in the schedule? This affects both the length of time we need to keep the journal around, and makes it more or less complicated for the developer to reason about. That is, if we dispose of the journal at the end of every frame, that simplifies the implementation, but makes the developer's scheduling decisions trickier. Alternatively, if we say that removal can be detected at frame N+1, but not later, then a double-buffering strategy might work.
• If we use a hashing approach, how good does the hashing function need to be? The keys of the removal set are (entity id, component id), what's the statistical distribution of these numbers? We don't want to spend a lot of time hashing these values.
• Do we need to know the tick for the time of removal, or is the mere fact of removal enough. This determines where we would use a HashSet<(entity id, component id)> vs HashMap<(entity id, component id), Tick>.

What I am thinking is that we replace RemovedComponents with a HashSet<(Entity, Component)>, this is stored globally in the world and double buffered, each component removal adds to the set. Then the query filter does set membership tests: Removed<Foo> checks the hash set for the (Entity, Component) tuple for each row. To keep memory allocations down, we can give the hash set a generous initial capacity, say, 1024 entries.