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.