Safely reading uninitialized memory

[scottmcm]

@canndrew

It doesn’t seem like it’s possible to implement this data structure in Rust because reading uninitialized bytes is always undefined behaviour.

Hmm, so reading uninitialized values in LLVM isn't UB; it's undef (LLVM Language Reference Manual — LLVM 18.0.0git documentation). But that doesn't save you, I don't think. In the code from the paper,

is-member(i):
    return sparse[i] < n && dense[sparse[i]] == i

I think that if sparse[i] is potentially undef, so that whole expression can probably become undef, since the guard just becomes undef.

I think what you need is freeze, which has been talked about for LLVM but I don't think it exists yet.