Can we make AllocId actually uniquely "identify" an allocation?

[RalfJung]

The way AllocId works right now is super counter-intuitive: they are entirely a per-crate identifier, and when loading the metadata of another crate, we generate a fresh "local AllocId" for each ID we encounter in the other crate and re-map everything we load. (At least I think that's what happens, @oli-obk please correct me if I am wrong.)

Unfortunately this means that a ConstValue that holds a pointer isn't actually a "value" in the usual sense of the world: if the value is computed in one crate and then used in another crate, its AllocId gets re-mapped. During code generation, when we encounter such an AllocId, we just always generate a local copy of that allocation and point to there. This means the "same" ConstValue, codegen'd in different crates, can result in observably different values! That's extremely confusing for users and compiler devs alike (#84581, #123670). In many cases this will get de-duplicated later but we can't always rely on that.

So... I'd like to consider switching how AllocIds work, with the goal of making ConstValue actually be a value. This will make #121644 unnecessary: we can just evaluate the static once, store its final value, and use that in all crates without running into issues like this. This requires not re-mapping AllocId, and instead when crate B receives a ConstValue from crate A it should be able to point to the allocation already generates by crate A. Unfortunately I am largely unfamiliar with how we manage "cross-crate identity of objects" so I don't know what the possible options here look like.

Some first rough ideas that popped into my head:

1. We could pick AllocId uniformly at random and fail when loading two crates that happened to get the same ID. That's fundamentally non-reproducible so either we have to make sure these AllocId don't matter for anything except the question whether they are equal or not (that seems hard to enforce) or we have to pick some deterministic scheme based on this. Also, curing codegen, how would we know whether the allocation has been previously already generated or whether it is our job to generate it? We'd have to keep track of which AllocId are "local", or so.
2. Use the first 32bits of AllocId to store the CrateNum of the crate that generated the allocation, and the rest to store some sort of per-crate allocation ID. I guess this still has to be remapped on load, but then during codegen when we encounter another crate's allocation we'd import it instead of generating a copy.
3. When interning an allocation, we always generate something akin to a DefId. AllocId outside of an interpreter session basically becomes DefId (or a new kind of ID with the same properties). We don't even need an alloc_map in tcx any more, we just have a new kind of "definition" that represents "global allocations" and a query taking a DefId and returning a GlobalAlloc. (That query would mostly, if not exclusively, be computed by feeding, maybe except for statics that it could evaluate directly. I guess if it is exclusively feeding it doesn't make much sense to make this a query rather than a normal hash map.)
   Inside the interpreter, we certainly don't want to generate a DefId for each allocation. I can imagine two schemes here:
   1. Reserve a CrateNum value to indicate "local interpreter instance" so that we can just make up DefIndexes locally while the interpreter runs and still know which allocations need to be looked up where. During interning, we generate proper DefId inside LOCAL_CRATE and remap everything we encounter.
   2. Still use the same AllocId type that we do now, but make it valid only inside an interpreter instance, and track a per-interpreter-instance mapping between global DefId and local AllocId. Unfortunately this means extra work whenever we "import" a global allocation into an interpreter instance as we need to apply that mapping (and then map back during interning).

The last two schemes (2 and 3) seem fairly similar, given that DefId is just CrateNum + per-crate DefIndex. The only difference is whether there's a single shared "index" namespace for everything or a dedicated namespace for allocations. My main concern with the single shared namespace is that we'd quite like to use some bits for other purposes inside AllocId: we want it to have a niche. We also probably need to distinguish allocations inside the current interpreter instance from "global allocations" (and do a remapping during interning), and at least inside an interpreter instance we are using some bits to track whether the pointer is derived from a shared reference and whether that shared reference had interior mutability. Option 2 could possibly entirely avoid doing any kind of mapping during interning, if we think that 2^30 total allocations are enough for every crate -- though I assume interning is already quite expensive so maybe it's not worth optimizing for that. It does seem worth optimizing for "no remapping when accessing previously interned global allocations", which excludes 3ii (which might otherwise be my favorite as it keeps everything fairly clear).

@oli-obk @rust-lang/wg-const-eval any thoughts?
@compiler-errors @wesleywiser I know you're not const-eval experts but maybe you know the query system sufficiently well to provide some helpful input. :)

[oli-obk]

Fun fact: DefIds are also created on the fly during deserialization. Tho they do handle their crate as you said. A DefId (or specifically the non-CrateNum part) is an interned DefPath (or DefPathData unsure about the exact data structure).

We can reuse def ids, which is quite convenient, but may cause us to run out of identifiers if we ever end up with const heap, as DefIds assume you don't have more than 2^32 definitions. Probably not gonna be a problem in practice.

Or we add a true interning scheme, mirroring the DefId scheme (create_def). Annoying as it's a lot of duplication.

[RalfJung]

Fun fact: DefIds are also created on the fly during deserialization.

So the concrete integer stored in a DefIndex can be different for the very same item when it is referenced in different crates? That seems surprising given than only one crate can create these items so I figured it could assign proper indices once that never need to be remapped.

Or is only the CrateNum part re-mapped?

A DefId (or specifically the non-CrateNum part) is an interned DefPath (or DefPathData unsure about the exact data structure).

Looking at the types there I see a DisambiguatedDefPathData, very interesting. "A pair of DefPathData and an integer disambiguator. The integer is normally 0, but in the event that there are multiple defs with the same parent and data, we use this field to disambiguate between them. This introduces some artificial ordering dependency but means that if you have, e.g., two impls for the same type in the same module, they do get distinct DefIds."
Is that what nested statics use? They have the same DefPathData as the item they come from but the disambiguator gets incremented for each one?

We can reuse def ids, which is quite convenient, but may cause us to run out of identifiers if we ever end up with const heap, as DefIds assume you don't have more than 2^32 definitions. Probably not gonna be a problem in practice.

If we only use DefIds during interning, then only the allocations that actually reach the final value count. I hope 2^32 is enough for that...

But that means a DefId alone is not enough to give us what we need, right? The crux is that when we encounter a pointer in a constant while lowering to LLVM, we need to be able to reference the pointed-to allocation with some globally unique name. If DefId are also remapped on-the-fly, we can't use that to compute the name, right? OTOH this somehow works for nested statics and I can't figure out where their names get generated... in a quick test, the name was _ZN10playground3FOO29_$u7b$$u7b$constant$u7d$$u7d$17h1e3e061caadeb6f0E. The 1e3e061caadeb6f0 part looks like some kind of hash or so?

[bjorn3]

The disambiguator is used for cases like

fn foo() {
    {
        fn bar() {}
    }
    {
        fn bar() {}
    }
}

where the two bar functions would be called crate[hash]::foo[0]::bar[0] and crate[hash]::foo[0]::bar[1] respectively.

Or is only the CrateNum part re-mapped?

Yes

[RalfJung]

The disambiguator is used for cases like

Sure, but is it also used for nested statics? Or how do those get their unique ID? It uses create_def for that which unfortunately does not have a very useful doc comment.

[bjorn3]

Yes, Definitions::create_def() (which is called by tcx.create_def()) is what ensures that the disambiguator increments every time you have two definitions with the same parent DefId and same name.

[RalfJung]

Ah right, I see there's a name as well. It's nested here. So I guess it then becomes STATIC::nested[0], STATIC::nested[1], etc. And these names are then later mangled to compute globally unique names for these nested allocations in LLVM, which means when they occur during codegen in any other crate we can refer to them properly.

So... that should work in general, not just for statics, right? Interning is always in the context of a DefId (the const/static we are evaluating), so we can create child definitions of that DefId for each allocation that needs a globally unique, stable identifier.

[oli-obk]

It breaks down when you have generic constants, as you'd then also need the generic params in the name. We don't have the same issues as generic statics, so two different crates independently creating the same constant allocation, naming it the same and giving it the same data would be fine if we use the right kind of linkage. Just using the same linkage as statics would cause linker errors due to duplicate symbols.

[oli-obk]

We also cannot create child definitions of a DefId of another crate, so evaluating a constant from a different crate would need some different logic in general

[RalfJung]

It breaks down when you have generic constants,

Ah, right... we want to synthesize a monomorphic DefId...

We also cannot create child definitions of a DefId of another crate

... in the local crate.

So it sounds more like we'll want to use create_def on the crate root of the local crate, like root::const_alloc[N] for a fresh N each time. The crate root has a DefId, right? And it has no generics. So this should be possible, or is it too silly?