Add basic system for specifying and validating archetype invariants

[sixfold-origami]

trafficstars

Objective

Closes #1481

Impulse

Often, when adding components and bundles to entities, there are implicit rules about which components can or can't appear with each other. For example, in most projects, an entity with a Player component should never have a Camera component. Users would like to be able to specify these rules (invariants) more explicitly, both for static analysis, and soundness.

Current Way

If a user wants to codify these rules, they must roll their own implementation, mostly likely by adding a System which checks each of these rules against the World's Archetypes.

Struggle

There are several difficulties with the current way:

• Building an invariant checking system from scratch is annoying
• Checking invariants naively in systems is (likely) inefficient
• Because archetype invariants aren't a first-class feature, many users will not think to add such a system, even if it would be beneficial to them
• Because users are writing their own systems for this, we (at the engine level) cannot leverage these invariants. In particular, it is appealing to use these invariants to more accurately evaluate which system parameters conflict. (This would both reduce the need for Without clauses in systems with multiple queries, and prevent false positives when checking system order ambiguities.)

New Way

We will add a first-class system for specifying and validating archetype invariants:

• We will provide a type, ArchetypeInvariant, which represents a structured logical statement that must hold true for all Archetypes
• Whenever an ArchetypeInvariant is invalidated, the engine panics, and outputs a nice error message:
  • 'Archetype invariant violated! The following invariants were violated for archetype ["B", "A"]: {Premise: AnyOf(A), Consequence: NoneOf(C, B)}'
• We will store a list of ArchetypeInvariants on the World.
• Users can add archetype invariants either using the methods on the world, or with helper methods on App
• Whenever a new Archetype is added to the World, we will check it against the existing invariants
• We will provide additional helper methods to easily construct common invariants

---

Changelog

• Added ArchetypeStatment, and associated methods for construction and testing archetypes
• Added ArchetypeInvariant, and associated methods for construction and testing archetypes
• Added a blanket impl for Bundle with helper methods for constructing common invariants
• Added UntypedArchetypeStatement and UntypedArchetypeInvariant, to act as a type-erased version of the above. (See design justifications below for details.)
• Added ArchetypeInvariants, to store a list of ArchetypeInvariants.
• Added World.archetype_invariants: ArchetypeInvariants, to store archetype invariants
• Added World::add_archetype_invariant and World::add_untyped_archetype_invariant, to add new invariants to a world
• Added App::add_archetype_invariant and App::add_untyped_archetype_invariant, to add new invariants to a app's world.
• Added the archetype_invariants example.
• Changed Archetype::new to check against the list of invariants from the World before returning the constructed archetype

Design Justifications

• We include both a typed (ArchetypeInvariant) and untyped (UntypedArchetypeInvariant) API. The typed API allows for very convenient specification of invariants that use only Rust types. The untyped API is required to support dynamic components.
• Archetype invariants are stored on the World, as different worlds may have wildly different archetypes and rules. Additionally, this provides more natural support for headless worlds.
• New archetypes are checked on creation. We recognize that this can cause problems when adding components sequentially. However, we believe that this is the best design for several reasons:
  • It ensures that no archetypes are ever "missed". There are many ways for commands to add new archetypes to the world. Checking whenever Archetype::new is called ensures that all commands and methods (including future ones) will include invariant validation.
  • It also ensures that there is never an invalid archetype, even transitively. Since this feature is planned to be used for soundness, a stronger promise of validity is desirable.
  • As long as the empty entity is considered valid, it is always possible to perform entity mutation operations in an order that preserves validity at every step. Furthermore, using insert_bundle instead of insert will likely solve the majority of these cases.

Trait-based API

We use an explicit type for archetype invariants instead of a trait, as using a trait would cause problems when attempting to use archetype invariants to resolve system parameter conflicts (and execution order ambiguities, which follow similar logic). Reasoning:

1. On any sensible trait-based API, we would need to provide some kind of test method that takes an archetype and outputs a boolean for whether it is valid. It is natural to want to use this to catch disjoint system parameters that overlap, such as Query<&Transform, With<Player>> and Query<&mut Transform, With<Camera>>. One might want to just take the union of the two queries to construct a minimal archetype and check them against the invariant. Then, if the invariant fails, we know the archetype will never appear and the queries are disjoint, right? Unfortunately, no.
2. It is possible (and, in fact, desired) to create archetype invariants which cannot be used to resolve param sets if only the basic testing method is provided. For example, consider the two queries from (1), and the invariant Player::requires::<Life>(). These queries, when combined, would fail the invariant (since Life is not present), making the queries look disjoint when they are not necessarily.
3. As a result of (2), the archetype invariant trait would require the implementer to provide additional information about the structure of the invariant, so we can more accurately determine which parts of the invariant apply to which parts of the queries. (Specifically, we would need to know whether the invariant restricts which components appear together, or requires additional components to appear together.)
4. If the additional information is incorrect, then it could lead to soundness issues, as conflicting parameter sets would erroneously run in parallel. This means that the trait would have to be unsafe.

This means that the trait approach locks us into one of two options:

1. Make the trait unsafe. This means that users would need to either use only the provided helper types, or manually implement an unsafe trait.
2. Don't use archetype invariants to resolve system parameters or execution order ambiguities.

Option 1 is unappealing for fairly obvious reasons. Although we may be able to provide helper types for all reasonable invariants, I doubt this is likely to happen. Furthermore, I'd rather avoid manual implementation of unsafe traits entirely if possible. Option 2 is more palatable but restricts important use cases in ways that will surprise users and leave frustrating edges in the engine. Debatably-prettier APIs aren't worth it.

Future Work

• Benchmarking and optimizing invariant checking. In particular, it is theoretically faster to cache component containment in a bit array, then use only bit manipulation operations to determine the truth value of ArchetypeStatments and ArchetypeInvariants. We decided that this optimization is premature for this PR.
• Using archetype invariants to more accurately evaluate if two sets of system parameters conflict. (As mentioned, this would have benefits both in system scheduling and query syntax cleanliness.)
• Adding a variant on ArchetypeStatement that allows the user to provide an arbitrary function. This should not be used commonly, but may be helpful as a safety valve when working with strange or uncommon invariants.
• Once this feature starts seeing use, performing a more thorough audit of common invariants, so that the API can make these easy to specify.
• Swapping sets of archetype invariants at runtime. This is appealing to do, as different scenes may have different invariants that must be validated. Supporting this, however, provides several challenges. Namely: how do we know which archetypes need to be re-checked under the new set of invariants, and how do we do that in a performant manner?

[alice-i-cecile]

(As mentioned, this would have benefits both in system parallelization and query syntax cleanliness.)

This will not actually impact system parallelization; this is done on the basis of factual rather than hypothetical compatibility by checking the bitset of created archetypes.

[Nilirad]

Changed Archetype::new to check against the list of invariants from the World before returning the constructed archetype

I recognize that this action would increase the cost of adding a new archetype. Are archetypes cached so that they aren't immediatly deleted when there are no entities? I'm concerned of the case where an entity with a unique archetype that has a marker component that rapidly gets added and removed over time. This would cause creating that archetype and the archetype without the marker many times over a short time frame if there is no caching.

Also would it be a good idea to disable archetype invariant checks on release builds?

[sixfold-origami]

I recognize that this action would increase the cost of adding a new archetype. Are archetypes cached so that they aren't immediatly deleted when there are no entities?

In short, yes. The world's archetype list stores all archetypes, past and present. This means that your "flickering marker" example would only incur two archetype checks :).

Also would it be a good idea to disable archetype invariant checks on release builds?

I considered this, but since this is planned to be used for soundness (with system parameters), I think it should always be on. That being said, I am open to including a setting to disable it in release mode, depending on how that system parameter integration ends up looking.

[Nilirad]

I think that the lines “This may include empty archetypes: archetypes that contain no entities.” can be kept for now, so you can resolve them for now. Be sure to double-check that all methods that states that actually triggers the re-check though, maybe by adding some tests.

I think that changes to Components docs can stay, since they are really small and not functional.

[Nilirad]

I think that the lines “This may include empty archetypes: archetypes that contain no entities.” can be kept for now, so you can resolve them for now. Be sure to double-check that all methods that states that actually triggers the re-check though, maybe by adding some tests.

Just added these tests on my end, and they fail: I added a failing condition for the archetype (A,) after archetype insertion, and it doesn't panic where it should.

    #[test]
    #[should_panic]
    fn re_check_all_archetypes_on_invariant_insertion() {
        let mut world = World::new();

        world.spawn().insert_bundle((A,));

        let untyped_archetype_invariant = super::ArchetypeInvariant {
            predicate: super::ArchetypeStatement::<(A,)>::all_of(),
            consequence: super::ArchetypeStatement::<(A,)>::none_of(),
        }
        .into_untyped(&mut world);

        world.archetype_invariants.add(untyped_archetype_invariant);
    }

    #[test]
    #[should_panic]
    fn re_check_all_archetypes_on_untyped_invariant_insertion() {
        let mut world = World::new();

        world.spawn().insert_bundle((A,));

        let untyped_archetype_invariant = super::ArchetypeInvariant {
            predicate: super::ArchetypeStatement::<(A,)>::all_of(),
            consequence: super::ArchetypeStatement::<(A,)>::none_of(),
        }
        .into_untyped(&mut world);

        world.add_untyped_archetype_invariant(untyped_archetype_invariant);
    }

So either the doc comment about re-checking in Archetype_invariants::add and World::add_untyped_archetype_invariant should be removed, or the check should be enabled.

[Nilirad]

Wondering if we can use const generics to generalize “at least” and “at most” statements:

pub enum ArchetypeStatement<B: Bundle, N: usize> {
    // ...
    AtLeast(PhantomData<B>, PhantomData<N>),
    AtMost(PhantomData<B>, PhantomData<N>),
}

Something like that, I don't know how the exact syntax would be.

[sixfold-origami]

I think that the lines “This may include empty archetypes: archetypes that contain no entities.” can be kept for now, so you can resolve them for now. Be sure to double-check that all methods that states that actually triggers the re-check though, maybe by adding some tests.

Just added these tests on my end, and they fail: I added a failing condition for the archetype (A,) after archetype insertion, and it doesn't panic where it should.

...

So either the doc comment about re-checking in Archetype_invariants::add and World::add_untyped_archetype_invariant should be removed, or the check should be enabled.

That's because you're calling add on the World's ArchetypeInvariants directly, instead of using World.add_archetype_invariant. Normally, the pattern you used would be impossible, as the archetype invariants field is pub(crate), and we only expose a getter method. Regardless, you are right, and the docstring on ArchetypeInvariants.add is incorrect. Fixed as of 9770862584143c455375d5e74d5bfe3898a8104e. Good catch!

[sixfold-origami]

Wondering if we can use const generics to generalize “at least” and “at most” statements:

We could do that, but I don't think it's helpful to add at this stage. I actually considered doing this, but I think that the increased complexity isn't worth the potential gain, especially because it would make the common case less readable. It would be very cool, but I can't think of many cases where you'd actually want or need that kind of arbitrary checking. I would be open to adding this later if it's a requested pattern though.

[alice-i-cecile]

FYI @PROMETHIA-27 the helper methods for True and False are needed here because of failures in type inference ultimately driven by https://github.com/rust-lang/rust/issues/27336 😢 Otherwise we'd just set () as the default type and everything would work fine.

(Thanks @devil-ira)

[sixfold-origami]

I spent some time exploring a trait-based API with @alice-i-cecile, but we came to the conclusion that it would likely cause more problems than it solves. See the PR description for a full justification

[alice-i-cecile]

bors try

[bors[bot]]

try

Build succeeded:

• run-examples
• check-doc
• check-compiles
• build (windows-latest)
• build (ubuntu-latest)
• build (macos-latest)
• build-wasm
• build-android
• markdownlint
• run-examples-on-wasm
• check-missing-examples-in-docs
• ci
• build-and-install-on-iOS
• run-examples-on-windows-dx12

[sixfold-origami]

Changes from #2974 have been merged in and accounted for! At this point, the only thing left to resolve is the exact name of ArchetypeInvariant, which I think we'll just leave to @cart for the final say on.

[mockersf]

I don't think this would close #1481. Of the three use cases mentioned there (helping system ambiguity checker, checking assumptions, allowing overlapping queries), it would only close the second one.

[sixfold-origami]

I don't think this would close #1481. Of the three use cases mentioned there (helping system ambiguity checker, checking assumptions, allowing overlapping queries), it would only close the second one.

That's a good point. Personally, I think #1481 should still be closed, and those two tasks should be split into two newer issues, now that so much has changed. I don't feel too strongly though. I'll remove the closing language from the PR description for now.