Create and use StableTypeId instead of TypeId

[cart]

std::any::TypeId is not stable across binaries. This makes it unsuitable for use in scene files, networking, or dynamic plugins.

In the short term we get around this by just using std::any::type_name. But this isn't particularly efficient for certain serialization cases and Eq / Hash traits. Legion uses TypeIds extensively and we've (in the short term) replaced those with type_name to allow for dynamic plugin loading. But that probably incurs measurable overhead.

Its worth exploring the idea of a StableTypeId, which is just a wrapped integer. I think it makes sense to use a const-hashing algorithm on type_name to produce StableTypeIds

[cart]

This is even more important now that we're using bevy_ecs instead of legion. Dynamic plugin loading will be broken until we add this.

[Plecra]

How would a hashing algorithm deal with collisions? Obvious question, but I don't see how this issue can be addressed without resolving it 😶

[cart]

If you are discussing hash collisions where "a" and "b" hash to the same thing, i think we can choose one that is effectively "collision free" for the type names we would be using. The world runs on hashing strings.

For the case where there are two types that have the same "type name": I don't think thats a problem in practice. Within a crate there cannot be collisions. Across crates, crates.io enforces uniqueness.

I'd love your thoughts on this!

[Plecra]

I'm concerned about unsafe code making assumptions that any given TypeId must only have one representation, since I can't tell how that'd be avoided.

I think Rust's safety is best thought of as a binary property, and wouldn't like a solution that just made it really unlikely that you manage to write two types with the same hash (which could then proceed to cause UB). Especially as the algorithm would be public, and crates.io is an amazing attack vector.

That said, I could be completely unaware of some way of proving an algorithm "collision free" for type names, or there really is a way of verifying the hashes. (On second thought, can the StableTypeId just contain a pre-hashed &'static str? Yea, probably...) Ahw, same issue with the serialization

[cart]

Back when bevy used a legion fork, i solved the type id problem with &'static str. It definitely worked, but there are two issues:

1. Performance. Comparison (and hashing) is expensive and both are relatively common operations in the ECS implementation
2. We'd still be hashing the string because aspects of hecs rely on a hashed type id. The only difference between &'static str and StableTypeId is where the hash happens (run time vs compile time).

I think the cost/benefit here is quite low. The cost is "very very very unlikely collisions" and the benefit is dynamic plugin loading and no additional runtime cost. On the "malicious code" side, if you are taking a dependency on something, that is already trusted code. We will never be able to protect against malicious dependencies.

[Plecra]

What do you mean by that? There's a lot that can be done to defend from dangerous code, and Rust is an effort to empower developers in that sense.

As far as I'm aware, there shouldn't be any way for a forbid_unsafe, no_std crate to interact with the host machine, or mess with any memory I don't give it. That's incredibly useful for managing dependencies in a Foss context.

A soundness hole allows those otherwise sandboxed dependencies to trigger UB, and get up to whatever they like.

Instead, could this be done with a derive macro? The uniqueness of the IDs could then be verified at compile time, and compilation can fail if a collision is found. I do understand why you don't consider a priority - the chances are incredibly low. It's just a disappointing sacrifice to make (Side note: this flaw would mean that properly reviewing dependencies for safety would require a manual verification step anyway since a human can't know that a name is safe for their project)

[cart]

I actually wasn't thinking about the forbid_unsafe and no_std combo providing "sandboxing" capabilities. I'll need to look in to that (and the safety guarantees the combo provides). As a brief aside, its worth noting that currently Bevy has no goal to be no_std, although I'm not against that either (provided it doesn't impact the user experience).

"Sandboxed dependencies" is a nice feature thats may be worth pursuing, but Bevy's primary goals are not "running untrusted dependencies" or even "memory safety". Usability and productivity will take priority over almost everything. I don't think the concerns you have will be encountered in the "common case" (or even the top 99% of cases) and the cost of resolving them (appears to be) either major runtime overhead or major ergonomics costs.

I do want to resolve these problems, but ideally we find a way to do it that doesn't require high run time costs, macros, or user facing "boilerplate".

For example, a blunt force tool would be to add an opt-in cargo feature that uses TypeIds instead of StableTypeId. The cost there is that you wouldn't be able to use dynamic plugin loading.

Another option is exploring the "compile time dupe detection", but im afraid that breaks down in a world with dynamic dependency loading. "Run time dupe detection" seems reasonable though.

[Plecra]

It'd be a shame to have to use some kind of boilerplate. The ease of use of components at the moment is just brilliant.

And given a decent hashing algorithm, I'd be surprised if this issue ever actually mattered. However much I like the idea, you're probably right that it isn't worth it.

Could this decision be added to the documentation if a better solution isn't found? I think it's only fair to users to make the choice visible, since it does contradict the technical meaning of the safe API. Hopefully it'd also give traction to an RFC for a real StableTypeId 😁

[kazimuth]

fyi, different versions of a single crate can be included in a dependency tree, so even without plugin loading I believe you can have multiple types with the same type_name but different layouts :/ you can't directly depend on multiple versions of the same crate but your dependencies can, which could cause an issue with e.g. third-party plugins.

one solution to speed up comparison + hashing would be to have a global type name interner at run time. it's not going to be written often so it doesn't need to be particularly fancy. it wouldn't speed up serialization, though. it also doesn't solve the uniqueness issue.

you could potentially reduce the chance of conflicts by checking mem::size_of, mem::align_of, etc, and hashing those when you intern types. if you get a mismatch, panic. obviously that won't catch all issues though.

oh, alternative strategy: you could add something to the Properties derive that creates a more unique type name. like

impl Properties for $T {
    fn unique_name() -> &'static str {
         concat!(env!("CARGO_PKG_NAME"), "@", env!("CARGO_PKG_VERSION"), "::", std::module_path!(), "::$T"))
    }
}

or whatever, and then require that all types that are serialized / pass through plugins implement Property. Would just need to make sure that wouldn't slow down incremental compiles.

[mrobakowski]

I agree with @kazimuth. The docs for type_name specifically mention that multiple different types can have the same name and so the name cannot be considered a unique identifier. The unique_name that has been proposed above could include even more info, like which features of the crate were enabled (because afaik you can even include a single crate version multiple times with different features). There's a nice list of available env vars in the cargo book.

[zicklag]

Relevant to this discussion is #142. In order to have dynamically registered components, TypeId would need to become more of a ComponentId and would have to be suitable for components created outside of the Rust ecosystem as well.

[zicklag]

I opened a forum topic to find out if there is a way, without using specialization, to automatically implement a Component trait using the TypeId approach ( which I think could be adjusted to use const hash function and the type_name or something like that ) for any Rust type, but allow manually implementing it for things like scripted components. I'm trying to reduce the boilerplate as much as possible while allowing for custom component ids.

Unfortunately I think its the exact definition of the use-case for specialization: Any way to do this without specialization?.

[cart]

I'm thinking we could do something like this (pseudo-code):

StableTypeId(u64)

StableTypeId::of::<T>() == HashOf("actual::type::name::of::T")

let custom_type_id = StableTypeId::new(rand::<u64>())

[zicklag]

Oh, OK. That works. 😄 👍

I think that's easy, then. What do you think of renaming it ComponentId? That is what it is really for right? To uniquely identify components types, which with the advent of dynamic components are not necessarily synonymous with Rust types.

Also I think it is a good idea to add some of the Cargo env vars to the type_name like @kazimuth suggested. It won't solve all problems associated to collisions, but I think it will do a very close job of it.

I'll try to implement this.

[cart]

I'd love that! I think "approximately unique" is fine, especially while we are in the experimentation phase. We will soon learn if the problems stated above are actual problems in practice. At the end of the day, I think a good user experience requires a stable version of the TypeId interface. How we generate that can change, but we need to start somewhere.

I think I would prefer to keep the name a generic StableTypeId or something similar, as the "TypeId instability problem" will likely surface in other places too. This is a Rust ecosystem gap, so other non-bevy folks might want to use what we come up with.

Also definitely try to make the StableTypeId::of::<T>() a const hash of std::any::type_name::<T>(). Otherwise we're back to expensive runtime hashing.

[cart]

I also do like adding the cargo metadata to the path to help with ambiguity (provided it doesnt prevent us from const hashing).

[Plecra]

So btw, using the cargo metadata will require a procedural macro (since env::var is not a const fn).

Since this will force StableTypeId::of to be evaluated in the procedural macro anyway, we can have the macro check for collisions and have a properly bullet proof implementation. Which would effectively mean the only reason to use a "real" TypeId API is to avoid the impossibly rare collisions that this implementation could encounter

[zicklag]

So btw, using the cargo metadata will require a procedural macro (since env::var is not a const fn).

Actually we can just use the env!() macro which grabs environment variables at compile time.

we can have the macro check for collisions

How would the macro check for collisions?

I suppose if the procedural macro would log every id to a file as it was compiling hashing out the ids and then checked to make sure every id that it hashed was not one that was previously hashed maybe? I think I'm going to start just by keeping it simple and using env!() and a const fn. If we want to add an extremely bulletproof solution later with a proc macro we could, maybe putting it behind a feature flag because it would probably increase ( cold? ) compile times.

[zicklag]

Oh, well, unfortunately, type_name() is not stable as a const fn yet, it's an unstable nightly feature, which throws a wrench in the whole compile time type name hashing idea. The only thing I can think of then is to use a proc macro, but that requires you to add a derive to all your components which is not cool. Not horrible, but not cool. 😕

Any ideas?

[kabergstrom]

Have you considered a UUID as type ID as per https://docs.rs/type-uuid/0.1.2/type_uuid/ ?
Especially when it comes to persisted data, it can be rather troublesome to use a type's name as ID, since it prohibits moving or renaming the type. I can see a hash of the name working OK for the dynamic plugin and networking use-cases, but it may require some more care for persisted data.

[zicklag]

Yeah, I'm thinking that to get all the features we want we are just going to need to require a #[derive(Component)] for all components. It's kind of nice for demos, examples, tutorials, etc. to not need it, but I can't see a way around it if we want solid StableTypId's that will not conflict.

Question: do we need to change the TypeId every time there is a change to its layout? That makes it even more inconvenient. Otherwise I could just have the proc macro generate a uuid and save it to a file in the CARGO_DIR with a mapping of all of the types to their uuids.

At this point it seems like the type_uuid crate approach is the most effective, again, from a feature standpoint. We just need to come up with every way possible we can make it as convenient as we can.

Maybe something like this:

#[derive(Component)]
#[component(generation = 1)]
struct Mycomponent;

When you derive component the proc macro will create or update a file in you CARGO_DIR called type_ids.toml. It will map the type_name() to a uuid that it generates every time the component generation is changed. If you change the component's layout you then just have to update the generation and it will be sure to generate you a new type ID for the component.

[cart]

I've considered type_uuid, but I have a strong preference to make things work without additional derives (especially ones that require users to generate UUIDs. theres a lot of friction there).

UUIDs are also not human readable, which means if we use them in Scenes that basically eliminates the "html-like" scene composition we're shooting for here: https://gist.github.com/cart/3e77d6537e1a0979a69de5c6749b6bcb.

The "moving components" problem is resolvable if we use "short names" by default (which we currently do) and "long names" to resolve ambiguity. To do this properly and avoid accidental name stomping we need runtime collision checks that force developers to resolve ambiguity.

I'm fine with adding optional UUID support for folks that need explicit uniqueness and are willing to deal with the overhead, but in my head the cure is worse than the disease for the common case. I will likely be pretty stubborn here, but I'll try to be as reasonable as I can be.

Imo if rust paths are suitable for importing types in the rust language (and trusting that those imports are what we want them to be), then they should be suitable for "importing" things into a game's "component namespace".

[cart]

@zicklag's "component generation + file" idea is very clever and worth considering, but I'm still biased toward making paths work.

[BERADQ]

This is how the crate looks so far. It has a basic idea, but it needs more work on the implementation.
StableTypeId

[BERADQ]

I tried the Stable TypeId in my organization Kokoro,

and while it might not be ideal yet,

it worked and performed well.

[Fidius-jko]

How do you like the idea of ​​creating a TypeId not only from the name and path, but also from fields?

[BERADQ]

How do you like the idea of ​​creating a TypeId not only from the name and path, but also from fields?

Yes, that is the implementation of stable typeid.

[Fidius-jko]

Hello, an off-topic question, why did github automatically mention my issue? When did I add the comment there?

[Fidius-jko]

How do you like the idea of ​​storing not only the TypeId but also the TypeId type in the StableTypeId? Because if someone wants to use bevy in Java, then the question arises: how to synchronize the TypeId from Java and the TypeId from Rust so that there are as few conflicts as possible, and just It would be possible to indicate which TypeId is used, for Rust, for example, 0, and for Java 1 (or whichever user wants)?

pub struct StableTypeId(/*TypeId*/, TypeOfTypeId)

[cactusdualcore]

TL;DR: stable type resolution might be impossible to make use-case agnostic, opt for a customizable (possible with defaults) and use-case-specific approach.

I think a stable type id is a fundamentally ill-based concept, because it relies on a nebulous at best, undefinable at worst notion of type identity.

use std::any::*;

mod new_module {
    pub struct A { _foo: u32 }
}

struct A { _foo: u32 }

fn main() {
    assert_ne!(TypeId::of::<A>(), TypeId::of::<new_module::A>());
}

On a programming language level, type identity is well defined! The above snippet compiles and runs perfectly. Now, the given code isn't very interesting: The two types are indeed distinct! But now consider that code is malleable and will change over time. The same type might move from one module two another, possibly across crate boundaries (consider #13945).

But the previous sentence defined a notion of type identity? Isn't that contradictory to what I first stated? No! In fact, there are many ways to define type identity.

• Conceptual: A type is identified by it's corresponding model entity, completely independent of implementation. To give an example of this, think about multiple libraries (or even modules in a single lib!) having a distinct Image type each. Conceptually, they all represent an image of
  unspecified encoding. Often enough the language disagrees though, and users have to do conversions (some fully without real work on the CPU). This is because many statically typed languages use...
• Static/Formal: This notion of types considers two values to be of the same type if the they're types were created from the same declaration (this might seem trivial, but it's a whole other beast: Think about imports, types as values and generics). This notion (actually, this group
  of notions) is probably what most programmers are used to by now. This is exactly what Rust's std::any::TypeId identifies. It's inadequacy here stems from its weird temporal location. A value's type doesn't have a "when", because there only is "now" (a.k.a. the current compilation).
  Side Note: I would love to see a vcs-similar programming language that keeps track of declarations' histories. Sounds horrible enough.
• Structural: This is what TypeScript does. A type is uniquely identified by it's recursive composition of primitive types.
• Locational: This is what the TypePath trait does. It's kinda related to static type declarations. Usually this can be seen as where a type was first declared.

And there are lots more, like compositons or arbitrary relations (think subtyping, which - when reasoning - can have non-obvious "is type" relations).

Please be aware that I completely made up all of the above names and that this is not even distantly related to maths or type theory. It's just my descript of how I found myself reasoning about typing.

I assume the discussed derive macro composes "maybe locational" and structural reasoning. "maybe locational" because if it's anything like TypePath it gracefully handles moving types (yay!), which messes with locational uniqueness.
This is semantically very different from std::any::type_name (mentioned in the original issue), it's modern alternative in bevy, TypePath and std::any::TypeId (which can't be stable across binaries, because how would the compiler know that it hasn't changed? This is even worse if thinking about architectures. A i64 on 64 and 32 bit systems are just plain different).

All this put together, there might be no good way to uniquely identify a type for multiple different purposes. If this is just for scenes (I assume plugin loading is not important, after all: It was deprecated), that's kinda similar to the serde model of reason: Just try to make it fit somehow (including dynamicly structured value (read: DynamicScene), otherwise fail. If this is for serializable dynamic typ

[JohnTheCoolingFan]

Why not just use TypeUuid? Yes, you need to specify the type in the code itself, but it is a universally unique identifier. Then, if some other way of identifying a subset of types is needed, a mapping could be made, like the type path and such.

[JohnTheCoolingFan]

After pondering about this more, I suggest a following scheme: TypeRegistry<K> can be a collection generic over the key used for identifying the type registration entry. Suck a key can be anything: TypeId, type path, Uuid, etc. Analogoulsy, types can implement optional RegisterType<K> traits for registering using a specific type of a key. Not a replacement of GetTypeRegistration, the latter handles the value while the former is for the mapping key. For different applications different types of keys are best, I doubt there can be a universal one that works for every case, and I doubt, although much less, that there can be a type that can be used somewhat universally for purposes of bevy_reflect.

[JohnTheCoolingFan]

Drafted an RFC based on those thoughts: bevyengine/rfcs#83

[Lubba-64]

@BERADQ I gave implementing stable id in a PR a shot, and it seems like there are 2 issues:
1: Requires implementing StableID for types, annoying but probably necessary.
2: derive macro doesnt work with tuple structs for some reason, which is a flaw that has made me drop the attempt for now.

[Lubba-64]

1: Requires implementing StableID for types, annoying but probably necessary.

this is probably false on further reflection, but the only example provided was a derive and not a regular macro for passing in primitives and std types.

[Lubba-64]

I have updated the derive macro to actually work for tuple structs.

I will continue working on this throughout the week and see what I run into.

this is probably false on further reflection, but the only example provided was a derive and not a regular macro for passing in primitives and std types.

needless to say...

impl StableID for () {
    const _STABLE_ID: &'static StableId = &StableId(0);
}

is unbelieveably unsafe and stupid. this will not be in the final implementation.

[Lubba-64]

this is better for those pesky std and foreign types. will need that api stabilized though so not sure what to do about that for now. I think that type_name const fn issue is worth bumping.

macro_rules! impl_with_type_name {
    ($name:ident) => {
        impl StableAny for $name {
            fn stable_id(&self) -> &'static StableId
            where
                Self: Sized,
            {
                $name::_STABLE_ID
            }
        }

        impl StableID for $name {
            const _STABLE_ID: &'static StableId =
                &StableId(fnv1a_hash_64(type_name::<$name>().as_bytes(), None));
        }
    };
}

impl_with_type_name!(bool);
impl_with_type_name!(char);
impl_with_type_name!(u8);
impl_with_type_name!(u16);
impl_with_type_name!(u32);
impl_with_type_name!(u64);
impl_with_type_name!(u128);
impl_with_type_name!(usize);
impl_with_type_name!(i8);

[SkiFire13]

@Lubba-64 relying on type_name is still very unsound. Type names can easily conflict (e.g. when using two different versions of the same crate, or with different feature flags, which can easily happen with dynamic loading), and don't take into account other potential differences in the type fields and methods.

[Lubba-64]

I did not consider methods. thats going to be an issue. How would we go about primitives then? How would we go about STD types? we need their syntax tree to fulfill these requirements...

[Lubba-64]

Looks like we're gonna need to hash feature flags as well?

[Lubba-64]

Ideally we would run the derive macro @BERADQ created (or an analog) directly on the std and foreign types we need to implement stable-id for. the latest stuff in my fork still needs:

• methods
• crate features
  according to the new requirements in that post, which @BERADQ did not account for in the macro I am pretty sure.

According to bjorn on discord:

• #repr(u16) doesn't work / is unencodeable.
• we cannot get the syntax tree for std/foreign types.

Bevy has a finite number of std and foreign types. for those types, I cannot move forward without doing the best I can with what is possible currently. apparently we cannot check features or versions of dependencies without going into a Cargo.lock file. So it seems like for a large set of types the only possible solution is something incredibly unsound. not good.

The current state of affairs is quite unacceptable. I can understand why this is the second oldest issue now.

I am probably going to finish my branch's implementation because this is a hard requirement for multiple projects I am working on, and I think the additional unsoundness is something I'll have to put up with until the situation improves in my fork.

[Lubba-64]

Actually I can add CARGO_PKG_VERSION to the hash to stabilize the package versions, and dependency versions since any given bevy version will be using the same rustc and dependency versions.

[Lubba-64]

Actually I can add CARGO_PKG_VERSION to the hash to stabilize the package versions, and dependency versions since any given bevy version will be using the same rustc and dependency versions.

If I could concat const strings with const fn generics! which you cannot!

[SkiFire13]

since any given bevy version will be using the same rustc and dependency versions.

This is not true, you can compile the same bevy version with both a different rustc and different dependencies versions.

[Lubba-64]

This is not true, you can compile the same bevy version with both a different rustc and different dependencies versions.

Good to know 🤦
Looks like we're even more screwed than I thought. But we can get the rustc version though cfg directives I believe, which should solve one of our issues. bevy versions and rustc versions and typenames being the same is helpful but not sound enough, as we need dependency and feature flags.

[Lubba-64]

If I could concat const strings with const fn generics! which you cannot!

Someone would probably have to do something pretty messy to get this to work but I believe it may be possible.

[bjorn3]

For plugins really the only thing guaranteed to work is TypeId + ensuring that you use the exact same bevy dylib (and dylib for whatever dependencies and game specific types you have that you want to use in your plugin) in the plugin as in the main game executable.

[cart]

I personally haven't felt the need for a "stable type id" in awhile. Iirc I created this issue back when I was first doing dynamic linking and I noticed the TypeIds didn't match across binaries. Turns out that was a sign that the binaries weren't compatible in the first place (see all of @bjorn3's messages).

In the context of scenes and networking I'm totally cool with using type path to establish identity. In both of those cases to save space we can exchange full type paths for short temporary ids.

Ex: within the context of a specific scene file, create the mapping some::type::Path -> SOME_INDEX
And then use SOME_INDEX to avoid the cost of dealing with the path

In the context of scenes and networking I'm totally cool with using type path to establish identity

In theory this can have correctness issues across binaries. But in practice (1) in the cross-binary context we can / should / do rely on TypeId when working with actual references to the type and (2) for scene / networking contexts, the mismatch is still "sound" because we are (attempting) to translate that "other" context to the current runtime source of truth. If there is a mismatch, there will likely be a runtime error of some kind (ex: because a field is missing / one was provided that doesn't exist). In theory TypeUuid is the "better" fix here. But imo the UX cost of defining that everywhere is not worth it. People defining types in Rust already largely rely on TypePath for identity in practice, and notably we get it for free. Using TypePath in things like scenes and networking also has the benefit of being self-documenting.

I'm closing this out to prevent us from trying to tackle something that I don't think is the right path forward. Feel free to keep discussing here / make the case to reopen if you have different opinions.