const-eval can construct uninhabited values via recursive static initialization

[RalfJung]

Based on an example by @theemathas:

enum Never {}

static X: &Never = weird(&X);

const fn weird(a: &&Never) -> &'static Never {
    // SAFETY: our argument type has an unsatisfiable
    // library invariant; therefore, this code is unreachable.
    unsafe { std::hint::unreachable_unchecked() };
}

error[E0080]: could not evaluate static initializer
   --> src/lib.rs:3:20
    |
3   | static X: &Never = weird(&X);
    |                    ^^^^^^^^^ entering unreachable code
    |
note: inside `weird`
   --> src/lib.rs:8:14
    |
8   |     unsafe { std::hint::unreachable_unchecked() };
    |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `unreachable_unchecked`
   --> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/hint.rs:109:14
    |
109 |     unsafe { intrinsics::unreachable() }
    |              ^^^^^^^^^^^^^^^^^^^^^^^^^ the failure occurred here

I can't see anything wrong about weird. Therefore, this is UB from entirely sound code.

See below for an example that involves a library invariant instead of an uninhabited type.

Cc @rust-lang/opsem @rust-lang/wg-const-eval

[theemathas]

Of note, a static with uninhabited type currently hits an FCW:

enum Never {}

static X: Never = panic!();

Error:

warning: static of uninhabited type
 --> src/lib.rs:3:1
  |
3 | static X: Never = panic!();
  | ^^^^^^^^^^^^^^^
  |
  = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
  = note: for more information, see issue #74840 <https://github.com/rust-lang/rust/issues/74840>
  = note: uninhabited statics cannot be initialized, and any access would be an immediate error
  = note: `#[warn(uninhabited_static)]` on by default

error[E0080]: evaluation panicked: explicit panic
 --> src/lib.rs:3:19
  |
3 | static X: Never = panic!();
  |                   ^^^^^^^^ evaluation of `X` failed here

For more information about this error, try `rustc --explain E0080`.
warning: `playground` (lib) generated 1 warning
error: could not compile `playground` (lib) due to 1 previous error; 1 warning emitted

The FCW links to #74840

[oli-obk]

😆 so what is the root issue here? Being able to construct a &X of &Never type in reachable code?

[theemathas]

I think the issue is that a library that has a type Thing can't assume that a value of type &Thing points to a thing constructed via the library's public API. I'm struggling to imagine a case where that matters though.

[RalfJung]

I would say the problem is that we can construct references to uninitialized memory in safe code, and just the mere presence of such a reference could cause unsafe code to make assumptions that have not actually been proven

[oli-obk]

Since this is only ever an issue for statics, would it be sufficient to look at the type of the static before passing out AllocIds for it?

[lcnr]

Since this is only ever an issue for statics, would it be sufficient to look at the type of the static before passing out AllocIds for it?

as in, require the type of the static to not contain any reachable uninhabited types, both directly and behind references?

[oli-obk]

Hmm... we don't have preexisting logic for the behind references part I think, so that may indeed be a bit annoying, as you'd also want to catch struct Foo(&'static Never) types and so on, but we can't just walk all struct fields and go behind references and boxes and stuff, as that will quickly lead to cycle errors.

[RalfJung]

I don't think that really helps, since a type can have a safety invariant without the compiler knowing about that.

[asquared31415]

As an example of being able to bypass library invariants, particularly the invariant "this type can only be constructed by its public new function which has validation"

// for privacy
mod mrow {
    pub struct InBoundsIndex<const N: usize>(());

    impl<const N: usize> InBoundsIndex<N> {
        pub const fn new() -> Option<InBoundsIndex<N>> {
            if N < 32 {
                Some(Self(()))
            } else {
                None
            }
        }
    }
}

use mrow::InBoundsIndex;

static IDX: InBoundsIndex<64> = {
    index([0; 32], &IDX);
    // THIS SHOULD PANIC!!! but we do UB first on the line above
    InBoundsIndex::<64>::new().unwrap()
};


const fn index<const N: usize>(arr: [u8; 32], _: &InBoundsIndex<N>) -> u8 {
    // SAFETY: InBoundsIndex can only be created by its new, which ensures N is < 32
    unsafe { arr.as_ptr().add(N).read() }
}

error[E0080]: could not evaluate static initializer
   --> src/lib.rs:20:5
    |
20  |     index([0; 32], &IDX);
    |     ^^^^^^^^^^^^^^^^^^^^ in-bounds pointer arithmetic failed: attempting to offset pointer by 64 bytes, but got alloc4 which is only 32 bytes from the end of the allocation
    |
note: inside `index::<64>`
   --> src/lib.rs:28:14
    |
28  |     unsafe { arr.as_ptr().add(N).read() }
    |              ^^^^^^^^^^^^^^^^^^^
note: inside `std::ptr::const_ptr::<impl *const u8>::add`
   --> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/const_ptr.rs:965:18
    |
965 |         unsafe { intrinsics::offset(self, count) }
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the failure occurred here

[asquared31415]

Oh better yet, you could construct a version of this that has no public constructor!!! As long as the type is nameable, you can make a &T to it by using never-to-any coercion in the initializer instead of a constructor that may fail.