Instead of using a 128-bit hash as a TypeId, it uses a function pointer in the vtable for the same purpose. This means that you skip one indirection and also only have to use usize-width bits for the comparison, rather than 128 (a bit win on 32-bit or lower).
I'm sure I'm not the first person to consider this (IIRC, C++ puts its RTTI key directly in the vtable to avoid the indirection too). But what do people think?
Right now there are two ugly parts to it:
For correctness it relies on the compiler generating exactly one version of the type_ptr function for each type, so there is a one-to-one correspondence between vtable entries for type_ptr and the type. I'm pretty confident this should be the case even across translation units, but I've not found a guarantee that it is.
I couldn't find a stable way of getting a function pointer from a vtable, so had to manually hack around what I understand to be the current vtable structure. This isn't a fundamental problem (since the compiler knows how to get that function pointer by name) I just couldn't find a nicer way of doing it.
I'm not sure why this would be true. You can just have a generic type that's instantiated, along with its trait implementations, in different codegen units, thus duplicating its functions. If the linker could solve this problem why can't it also solve the problem for vtable duplication?
Remember that you also need to consider dynamic libraries (at least the dylib crate type) on different platforms. Overall this feels like the same problem as generic statics.
Given the circular nature of your definitions, and that the &self argument is completely unused, I don't see anything that would prevent TypePointer::of::<T> being unified to the same function for all T, which then means that you no longer have a type-unique id.
No, this is a circular argument. type_ptr uses T only for TypePointer::of::<T>(), but TypePointer::of::<T>() uses T only for getting the address of the T::type_ptr, so we're back at the initial claim.
Viewed from another point of view: if you inline TypePointer::of::<T>() inside type_ptr it just becomes TypePointer(<Self as PointerAny>::type_ptr as _), where <Self as PointerAny>::type_ptr is the function we're implementing. Hence type_ptr only uses itself, and nothing from T and thus every instance is the same.
I swear I'm not being obtuse, but I just don't see that this follows. In your example type_ptr uses Self (which isT), therefore it does use T.
Moreover, I can't find a way of writing this such that the compiler does that "optimisation". For example this and this clearly show two different functions being generated. Obviously this is empirical and not a guarantee, but if you're right then this should be a pretty easy place for that optimisation to be applied.
It uses <T as PointerAny>::type_ptr, but that's not enough to show it uses T, for that you also need to prove that <T as PointerAny>::type_ptr's implementation actually depends on T. But this is what you wanted to prove in the first place, and you can't assume it's true in order to prove it .
Doing circular reasoning is not the easiest/fastest thing, so that might be why it doesn't optimize that case. For example here are two examples where the compiler succeed and fails at a similar optimization https://rust.godbolt.org/z/jzTP1qr3E
You didn't properly share it, that's just godbolt's homepage.
This would work when dealing with coinduction, but this is not the case. ↩︎
I don't doubt the optimisation exists as a concept. What is not obvious to me is whether it would ever apply to the code I posted.
In any case, since actually calling type_ptr is not really necessary nor desirable, we could replace that function with literally anything. In the blog post I even suggest using the address of Any::type_id (which obviously could never be optimised as identical). The general approach would still work. The remaining issue being whether there is a way to guarantee uniqueness of a function pointer used in a vtable (and getting the pointer from the vtable, but that's more of an implementation detail).
Sorry, I edited the link after you opened in apparently.
In any case, this potential issue could be avoided by using the address of Any::type_id rather than the current type_ptr (since that function is never really meant to be called). That would eliminate false-positive type equality.
For false negatives, I think you're right that in the face of dynamic linking that can never be addressed with this method. Within a compilation unit though (or potentially statically linked) I think this is interesting though).
I was hopeful that the linker would eliminate duplicates across (statically linked) compilation units because they are functions that should have the same symbol per-type. Surely the linker deduplicates symbols? As to why vtables aren't given symbols that the linker could deduplicate similarly, I think that's an interesting question which I'm not qualified to answer. I'll continue to think about it though.