Which unstable feature would you use to implement type inequality?

I wrote a type inequality trait today and I encountered unstable features at every turn but ended up using none of them. I'm wondering if any of them will be stabilized soon. (I am using type inequality to compute the union of two lists at compile time.)

  1. Type inequality can easily be implemented using specialization but that is unsound. min_specialization is used by the standard library but it seems that it is too weak.

There were some discussions about specialization that made it seem like type equality would be problematic due to lifetimes. What confuses me about this is that you can require type equality in stable rust. But maybe they meant static dispatching based on equality, which is what I'm doing. I would happily use a solution that completely ignores lifetimes in the comparison but couldn't find anything like that.

Thus I ended up writing the traits linked in the first paragraph and a proc macro that implements IdType.

  1. Instead of the encoding involving nested types that I used, I could have saved the compile-time id as a const generic. But == on const generics seems to require an unstable feature.

I wanted to make the id a hash of type name and module but it turns out there is no clean way to get the current module in a proc macro. I found caller_modpath but its approach seems extremely slow and dirty.

  1. There is experimental support for getting the source file's name in a proc macro. That is almost as good as getting the module path but it fails when there are multiple modules in one file. It also feels weird that the id would be different on different machines due to different location of source folder.

I could also hash the whole definition of a type, not just its name but that wouldn't completely solve the issue either.

Finally, it would be cool to have nice error messages in the rare case when type inequality fails. Is it possible to customize trait inference failures other than by changing the names of the traits?

I'd appreciate any ideas on how to improve my solution.

EDIT: I realized while writing this that my proc macro gives the same id to A<T> and A<U>. Fixing that is somewhat involved. The user will have to derive the macro on all types that go in A as well, and there must be a macro that is able to wrap foreign types. And I might have to use const generics to compute the xor of two hashes.

So, you're trying to reimplement TypeId via some sort of reimplementation of symbol mangling I think. Source code files and paths aren't really enough, because you can include the same file as different modules. You need the full Rust-code-based path [1] to the type. Unfortunately I don't know how to query the symbol nor canonical path of a type offhand. (Maybe someone else does.)

Why can't you just use TypeId? Probably because it's only for 'static types and also because it's not const (callable at compile time). Ignoring the former, why can't you get a TypeId at compile time? Coherence and TypeId use different definitions of what it means for two types to be equal, and allowing the two to mix is unsound.

A specification of what type inequality means hasn't been made yet as far as I'm aware, and I imagine the story around equality will get cleaned up before that happens. (But I'm not on any teams.)

std can use rustc_on_unimplemented to customize trait bound failures, but I don't think there's anyway to do so in your own library yet.


  1. i.e. not a filesystem path ↩︎

1 Like

I tried TypeId at compile time. The problem is that you are allowed to get a TypeId at compile time but they don't implement PartialEq. According to an issue thread the only thing that works is transmuting to u64 and I don't want to do that, as that is clearly wrong.

Coherence and TypeId use different definitions of what it means for two types to be equal, and allowing the two to mix is unsound.

I read that thread earlier and was a bit disappointed because I would be perfectly happy with the behavior described in it. If two types are not considered equal by the trait system but equal by TypeId, then code using those types just will not compile because the types aren't equal or unequal. If they are equal according to the trait system but unequal according to TypeId, then my code again doesn't compile because then there are multiple valid impls to choose from.

BTW the aforementioned situations can also be caused by hash collisions, as the current implementation of TypeId has no protection against them.

My point is, there is no real danger involved, just a failure to compile. I'd be very happy with a solution that is otherwise solid but just doesn't compile on some edge cases.

I probably should transmute TypeId, at least until something better is stabilized. The problem is I can't even compare integers! Maybe there is a better way but at least my first attempt showed that generic_const_exprs is very buggy.

Do you mean, on nightly? And it does implement PartialEq (on stable), but perhaps you mean the fact that it doesn't have a const implementation of PartialEq, even on nightly. Or in the current output terminology, "the trait ~const PartialEq<_> is not implemented". (I guess that error currently inhibits this one; maybe that's where the confusion comes in.)

You can use structural equality instead, but I didn't find a way to do this with both types being generic. But maybe it helps.

The behavior described within (i.e. the OP) demonstrated unsoundness (a memory violation using safe Rust), so I'm not sure I follow. Unless just you mean, TypeId being more strict than coherence is fine when you're considering type inequality specifically.

Anyway, the resolution of that issue isn't settled yet, but it's not going to be the current behaviors which allow unsoundness.

It has some protection, but not 100%, and I'm disappointed they've decided to just eventually (hopefully) go with some bigger hash instead of some form of eddyb's symbol-based version.

The hash collision improvements they have settled on, but not yet implemented, are going to intentionally cause (at least the current set of) transmute on TypeId to fail (unless they've changed course again recently). The alternative is to silently miscompile those who transmute.

Not that I have any better idea until const_type_id with a const PartialEq implementation stabilizes... other than seeing if there's some way to get the symbol or type path in a proc macro, etc, to implement it manually.

u64 does implement ~const PartialEq, so this works on nightly with const_type_id and associated_const_equality. I didn't play with it beyond what you see.

2 Likes

The behavior described within (i.e. the OP) demonstrated unsoundness (a memory violation using safe Rust), so I'm not sure I follow. Unless just you mean, TypeId being more strict than coherence is fine when you're considering type inequality specifically.

Oh, I should have read the thread more carefully. The sample code is indeed dangerous unlike mine.

Not that I have any better idea until const_type_id with a const PartialEq implementation stabilizes... other than seeing if there's some way to get the symbol or type path in a proc macro, etc, to implement it manually.

I'm pretty fine with the proc macro I currently have, except that I think it need to do some const computations in order to differentiate A<T> from A<U>.

u64 does implement ~const PartialEq, so this works on nightly with const_type_id and associated_const_equality. I didn't play with it beyond what you see.

Thanks! This is very useful. I didn't know that you could avoid generic_const_exprs. But what do you mean with the comment "You can optionally drop the const_trait stuff"? It won't compile if I remove the annotation.

I found a strange bug. If the type parameters to test are inferred, the code doesn't compile. Strangely, most of my library works; only this one case doesn't.

Huh, yeah, looks like some sort of normalization bug. Order dependent, too. Worth filing an issue for; let me know if you do or I'll probably play with it more later.

Didn't file an issue, I'll let you do it.

I found another way to do type inequality, though. https://crates.io/crates/spidermeme

This one uses an auto trait for inequality and adds a negative impl for the equal case. It is a lot cleaner looking but this one will probably be patched out, too. According to forbid conditional, negative impls · Issue #79098 · rust-lang/rust · GitHub negative impls for auto traits will have the same restrictions as Drop.