1. https://en.wikipedia.org/wiki/Curiously_recurring_template_p...
2. https://david.alvarezrosa.com/posts/devirtualization-and-sta...
3. https://llvm.org/docs/ProgrammersManual.html#the-isa-cast-an...
I had thought you need the pointer-sized integer types and mustn't do this directly to an actual pointer, but maybe I was wrong (in theory, obviously practice doesn't follow but that's a dangerous game)
In modern C++, the technically "correct" and safe way to spell this trick is exactly as you suggested: using uintptr_t (or intptr_t).
Maybe that is not the correct C++ terminology, I'm more familiar with how provenance works in Rust, where large parts of it got stabilised a little over a year ago. (What was stabilised was "strict provenance", which is a set of rules that if you abide them will definitely be correct, but it is possible the rules might be loosened in the future to be more lenient.)
The problem of pointer provenance is more finding a workable theoretical model rather than one causing miscompiles on realistic code. While there are definitely miscompiles on carefully constructed examples, I'm not aware of any bugs on actual code. This is in comparison to topics like restrict(/noalias) semantics or lifetime semantics, where there is a steady drip of bug reports that turn out to be actual optimization failures.
But the likely destiny of C++ is to inherit the provenance rules that are an adjunct to C23, PNVI-ae-udi, Provenance Not Via Integers, Addresses Exposed, User Disambiguates
As that name suggests, in this model provenance is not transmitted via integers. Every 123456 is always just the integer 123456 and there aren't magic 123456 values which are different and transmit some form of provenance from a pointer to some value which happened perhaps to be stored at address 123456 in memory.
However, PNVI-ae-udi has Exposure, which means if we exposed the pointer in an approved way then the associated provenance is somehow magically "out there" in the ether, as a result if we have exposed this pointer then just having that integer 123456 works fine because we combined that integer 123456 with that provenance from the ether and make a working pointer. User disambiguation means that the compiler has to give you "benefit of the doubt" e.g. if you could mean to make a pointer to that Doodad which no longer exists as of a minute ago or to this other Doodad which does exist, well, benefit of the doubt means it was the latter and so your pointer is valid even though the addresses of both Doodads were the same.
https://doc.rust-lang.org/std/primitive.pointer.html#method....
Rust's MIRI is able to run code which uses this (a strict provenance API) because although MIRI's pointers are some mysterious internal type, it can track that we mapped them to hide our tags, and then later mapped back from the tagged pointer to recover our "real" pointer and see that's fine.
This isn't an unsafe operation. Dereferencing a pointer is unsafe, but twiddling the bits is fine, it just means whoever writes the unsafe dereferencing part of your codebase needs to be very careful about these pointers e.g. making sure the ones you've smuggled a tag in aren't dereferenced 'cos that's Undefined Behaviour.
It's clear to me how this works in Rust, it's just unclear still in C++
If you don't care about portability or using every theoretically available bit then it is trivial. A maximalist implementation must be architecture aware and isn't entirely knowable at compile-time. This makes standardization more complicated since the lowest common denominator is unnecessarily limited.
In C++ this really should be implemented through a tagged pointer wrapper class that abstracts the architectural assumptions and limitations.
Btw, is this representation the reason why OCaml's ints are not as big as C ints?
Also interesting that the Haskell pointer tagging you link to[0] was done the way it was to avoid CPU branch misprediction, and that the old way which it replaced was "the source of half of the branch misprediction events". I wonder how "branch prediction friendly" current Haskell is.
But it's really just an implementation difference, the idea is still to have a lightweight RTTI.
