Tracking Issue for const fn type_id

[KodrAus]

This is a tracking issue for using TypeId::of in constant contexts.
The feature gate for the issue is #![feature(const_type_id)].

About tracking issues

Tracking issues are used to record the overall progress of implementation.
They are also used as hubs connecting to other relevant issues, e.g., bugs or open design questions.
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.

Steps

• Come up with a new scheme for collision resistant type ids
• Figure out any safeguards we need to prevent messing with the bits of type id directly
• Adjust documentation (see instructions on rustc-dev-guide)
• Stabilization PR (see instructions on rustc-dev-guide)

Unresolved Questions

• How can we prevent abuses of transmuting type ids into integers at compile time (where we have fewer tools to deal with them)? See the discussion in Widen TypeId from 64 bits to 128. #75923
• We need a new scheme for building type ids that's collision resistant. We'd like to do this before stabilizing type ids in constant contexts. Collisions in type_id #10389, type_id is not sufficiently collision-resistant #129014

Implementation history

• Initial const implementation Turn type_id into a constant intrinsic #47892
• Initial stabilization Stabilize const_type_id feature #72488
• Reverted stabilization revert const_type_id stabilization #77083

[benkay86]

I'm not sure I totally understand the steps needed to re-stabilize const fn TypeId::of().

• Come up with a new scheme for collision resistant type ids
• We need a new scheme for building type ids that's collision resistant. We'd like to do this before stabilizing type ids in constant contexts

Does this affect the soundness of const fn TypeId::of()? If we are really worried about collisions, then shouldn't the entirety of TypeId be unstable, and not just the const version? Or are we worried that a future collision-resistant implementation of TypeId may not satisfy const, i.e. we want to keep open the possibility of a non-const implementation in the future?

• Figure out any safeguards we need to prevent messing with the bits of type id directly
• How can we prevent abuses of transmuting type ids into integers at compile time (where we have fewer tools to deal with them)? See the discussion in Widen TypeId from 64 bits to 128. #75923

This seems impossible. If someone wants to transmute() to the type of the private implementation (i.e. u64) in an unsafe code block, even though the documentation for TypeId explicitly says not to do this, can we really stop them? (They can already do it at runtime, not sure what "tools" prevent this.) Can we really stop anyone from doing unsafe things with unsafe code?

Motivation: It would be extremely useful to make const comparisons between TypeId in order to infer whether two types are equal at compile time. Currently this only appears to be possible using specialization (#31844), which is unsound and will not be stabilized anytime soon.

A perhaps related concern (may need a separate tracking issue) is that #derive[(PartialEq, Eq, ...)] struct TypeId does not generate const impl for these traits (see #77695), so even if const fn TypeId::of() gets re-stabilized we still won't be able to compare types at compile time without writing a const impl PartialEq for TypeId, etc.

[jmeggitt]

Can this be re-stabilized now?

@KodrAus Going through the comment that was the basis of reverting stabilization (#75923 (comment)):

Part 1

TypeId is one a few types (mem::Discriminant is the only other one I can think of) that's a thin wrapper for a private integer, at least right now. This is ripe for abuse no matter what we say/document it as.

Sure, but this suggests that retrieving a TypeId should be unsafe not unstable. Any is currently both stable and safe despite heavily relying on const fn TypeId::of(). If there are serious concerns that const fn TypeId::of() may result in collisions then Any should be unstable as well.

Part 2

I'm not saying we should cater to this, but rather avoid stabilizing even worse abuse-enabling tools like const fn TypeId::of.
Like I said, I am already aware of usecases where compile-time transmute(TypeId::of::<T>()) is an uniquely useful tool and someone might not think twice before releasing a crate which uses it somewhere internally and becomes widely-used.

I think @benkay86 summed this up fairly well.

If someone wants to transmute() to the type of the private implementation (i.e. u64) in an unsafe code block, even though the documentation for TypeId explicitly says not to do this, can we really stop them? (They can already do it at runtime, not sure what "tools" prevent this.) Can we really stop anyone from doing unsafe things with unsafe code?

Part 3

And finally, @eddyb remarks that we could potentially re-stabilize it if we are unlikely to change it.

If we decide we're unlikely to change the implementation of TypeId, then we can re-stabilize the const fn aspect, and live with the consequences. But if we do want to change the implementation away from a hash, we have to either do that first, or at least teach miri about it somehow so that it disallows using the value as a plain integer (for arithmetic or e.g. as an array type length).

It has been nearly 10 months since it was marked unstable and there have been no changes regarding this issue. At this point it seems like the implementation of TypeId is unlikely to change any time in the near future.

TL;DR

Plus even if we assume all of these points are true, these concerns only apply to intrinsics::type_id::<T>() -> u64 not const fn TypeId::of::<T>() -> TypeId.

If anything, the heavy reliance on const fn TypeId::of() inside Any suggests that it is stable but could potentially be unsafe to use directly. If there are concerns that TypeId can be abused without unsafe code then const fn TypeId::of() should be marked as unsafe instead. However I do not think this is necessary since you would need to use transmute() to extract the raw type id integer from TypeId.

intrinsics::type_id::<T>() should remain unstable as it provides access to the raw type id integer, but const fn TypeId::of() should be stabilized as it provides adequate protection.

[eddyb]

At this point it seems like the implementation of TypeId is unlikely to change any time in the near future.

Nobody tried AFAIK. 10 months is pretty short on the scale of Rust evolution, especially when you take into account the year 2020.

But also I believe it got stalled because of this potential breakage: #75923 (comment)

In order to guarantee code that transmutes to u64 gets broken, we can't just replace TypeId with a pointer, but because we still want the 64-bit hash (for both "fast reject (!=)" and Hash, see #75923 (comment)), we can probably do this:

struct TypeId {
    hash: u64,
    // `str` can be replaced with a length-prefixed string to keep `TypeId`'s size down
    v0_mangled_type: &'static str,
}
impl PartialEq for TypeId {
    fn eq(&self, other: &TypeId) -> bool {
        self.hash == other.hash // fast reject (!=)
        && (
            self.v0_mangled_type as *const str == other.v0_mangled_type as *const str // fast accept (==)
            || self.v0_mangled_type == other.v0_mangled_type
        )
    }
}

That way, it's always more than 8 bytes, no matter the target pointer size, and so a transmute to u64 will always error.

As for the linker concerns, if we take this specific approach, the only difference relying on their features would make is increasingly the situations in which the "fast accept (==)" path gets taken, i.e. an optimization.

I could try make a PR for this, but it would likely at least require #87194 (to avoid breaking when unstable const generic features are used).

If there are concerns that TypeId can be abused without unsafe code then const fn TypeId::of() should be marked as unsafe instead.

But we don't want that. You can't change TypeId or Any to be unsafe, they're stable, and nearly-sound.

[programmerjake]

struct TypeId {
    hash: u64,
    // `str` can be replaced with a length-prefixed string to keep `TypeId`'s size down
    v0_mangled_type: &'static str,
}
impl PartialEq for TypeId {
    fn eq(&self, other: &TypeId) -> bool {
        self.hash == other.hash // fast reject (!=)
        && (
            self.v0_mangled_type as *const str == other.v0_mangled_type as *const str // fast accept (==)
            || self.v0_mangled_type == other.v0_mangled_type
        )
    }
}

Maybe it would be better to use this to shrink TypeId to only 16 bytes on 64-bit platforms:

use core::{ptr, slice};

#[repr(C)]
struct StrWithLen<T: ?Sized> {
    len: u16, // assume all TypeId strings are <64kB
    text: T,
}

pub struct TypeId {
    hash: u64,
    text: &'static StrWithLen<()>, // actually StrWithLen<str>
}

impl PartialEq for TypeId {
    fn eq(&self, rhs: &Self) -> bool {
        if self.hash != rhs.hash {
            false
        } else if ptr::eq(self.text, rhs.text) {
            true
        } else {
            unsafe {
                let lhs_text = slice::from_raw_parts(
                    &self.text.text as *const _ as *const u8,
                    self.text.len as usize,
                );
                let rhs_text = slice::from_raw_parts(
                    &rhs.text.text as *const _ as *const u8,
                    rhs.text.len as usize,
                );
                lhs_text == rhs_text
            }
        }
    }
}

[eddyb]

Yeah, that's what I meant by "length-prefixed". There's a "standard" way to do that using extern { type }, I just didn't want to type it in.

[eddyb]

Update: finally opened #95845 with a (v0) mangling-based TypeId representation (should unblock const fn TypeId::of, while at the same time making specific uses of TypeId incompatible with CTFE, for now).

[lcnr]

blocking the stabilization of this on #97156

[yshui]

This would generally serve the use case of "I should probably be using an enum, but there are a lot of variants and it is a pain to write it out".
but there are some use cases where an enum can be more cumbersome such as when dealing with highly generic systems and associating resources with anonymous traits.

I actually am just writing such a system, and that's how I found out about this issue. And given the prospect that structural matching of TypeId could be gone in the future, I ended up using a set of macros to generate a big enum and a set of helper function to make working with it easier.

Not arguing for keeping it, just want to provide a data point.

[benkay86]

It seems const fn type_id() is going to take a long time to stabilize due to many concerns about soundness and corner cases of people doing something with the returned TypeId other than testing equality against another TypeId. Would it be possible instead to make Any::is<T>(&self) const? This way all the internals of TypeId stay inside the standard library.

[KodrAus]

I think a const-enabled Any::is that hid the specific equality mechanism would satisfy my use-case for const type ids too.

@eddyb did we have any lingering objection to being able to do this kind of type inspection at all in CTFE, or was it just the issue of structural match on TypeId that was the blocker?

[zakarumych]

I guess that most of the other use-cases would be covered by allowing TypeId::of::<T>() in const context, without allowing to do anything with it but assigning to a constant.

[Pr0methean]

Looks like TypeId suddenly stopped implementing StructuralEq. Why? I was previously able to use this function without a problem:

const PIXMAP_TYPE_ID: TypeId = TypeId::of::<Pixmap>();
const MASK_TYPE_ID: TypeId = TypeId::of::<Mask>();
const VEC_U8_TYPE_ID: TypeId = TypeId::of::<Vec<u8>>();

fn type_name_for_id(id: TypeId) -> &'static str {
    match id {
        PIXMAP_TYPE_ID => "Pixmap",
        MASK_TYPE_ID => "Mask",
        VEC_U8_TYPE_ID => "Vec<u8>",
        _ => "Unknown"
    }
}

[madsmtm]

Removing structural match for TypeId was done in #103291 in part to unblock exactly this feature, see the discussion above for reasoning behind the removal (shortened in #77125 (comment)).

[Pr0methean]

Would it be possible to restore backward compatibility by having the compiler convert a match with TypeId constants into an else if chain when there were only a handful of branches, and a lookup in a const std::collections::HashMap otherwise?

[oli-obk]

Yes, but that will require stabilization of const_trait_impls first, as otherwise we can't call PartialEq methods inside the const fn.

[KodrAus]

Most discussion about type ids in const contexts is happening here (naturally, since there's nothing to do with a type id except compare them), but there's also #101871 tracking using == in const contexts.

[briansmith]

I think #10389 needs to be resolved first, becuase depending on the resolution, it may not be possible to calculate the TypeId at compile time; it might end up like C++ std::type_index that uses the address of the RTTI structure as the ID.

[oli-obk]

We can compute and equate type ids that are addresses just fine at compile time. You just can't inspect the address (so no sorting type ids, no hashing them, no printing them)

[tgross35]

blocking the stabilization of this on #97156

This was recently marked fixed with #118247

Edit: started a discussion https://rust-lang.zulipchat.com/#narrow/stream/219381-t-libs/topic/Const.20.60TypeId.3A.3Aof.60.2C.20.60TypeId.3A.3Amatches.60.2C.20.60type_name.60.2C

Edit2: From the discussion, this is still blocked by the possibility of collision #10389

[avhz]

Any further updates on this ?

[bjorn3]

Still blocked on #10389.

[MarcGuiselin]

It looks like while #10389 was closed, there's still some ongoing discussion about the soundness/collision of type ids:

• type_id is not sufficiently collision-resistant #129014
• Incremental compilation relies on hashes for soundness #129016
• Language vs. implementation threat models and implications for TypeId collision resistance #129030

Is there anything else blocking?

There's still something that isn't clear to me:

We need a new scheme for building type ids that's collision resistant. We'd like to do this before stabilizing type ids in constant contexts.

I understand why #101871 might be blocked due to collision issues but why this one? Ensuring TypeIds are collision resistant and being able to use TypeIds in const contexts seem like separate problems to me. The use case for this feature (such as in the case of bevyengine/bevy#3365) of simply retrieving and including a TypeId as a field in a struct isn't unsound anymore afaik. Would it be okay to solve the collision issues after this feature and #63084 have been stabilized?

[RalfJung]

The problem is that the scheme we end up using might involve pointers, but currently TypeId contains no pointers. If people transmute TypeId to integers in const, their code would stop compiling when we start having pointers in TypeId.

[bjoernager]

Is there any reason for allowing such casts to begin with? Skimming the docs, I see no mention of TypeId having a specific layout (in fact, it is explicitely stated that the type is opaque). Unless I am overlooking something important, I would say it would seem the most senseful to just declare that it has an unspecified representation and that transmutations would be undefined.

[RalfJung]

That's already the case, but it does not stop unsafe code from doing it anyway.

We could say "if you do that and your build breaks later, it's your own fault", but well, that often just doesn't work -- people will have their build broken on a Rust update because a dependency did something like this, and they will blame Rust, not the dependency.

[Jules-Bertholet]

I’m also worried about the interaction with const fn pointers/dyn const. Ideally, const-related errors in non-const contexts should be as rare as possible. To accomplish that, const types should smoothly degrade into their non-const versions in non-const contexts. I don’t know how that should best be modeled in TypeId, but it’s another reason to hold off on stabilizing this.