Rollup merge of #133681 - RalfJung:niches, r=wesleywiser

improve TagEncoding::Niche docs, sanity check, and UB checks

Turns out the `niche_variants` range can actually contain the `untagged_variant`. We should report this as UB in Miri, so this PR implements that.

Also rename `partially_check_layout` to `layout_sanity_check` for better consistency with how similar functions are called in other parts of the compiler.

Turns out my adjustments to the transmutation logic also fix https://github.com/rust-lang/rust/issues/126267.

13 files changed, 177 insertions, 92 deletions

diff --git a/compiler/rustc_abi/src/lib.rs b/compiler/rustc_abi/src/lib.rs
index 2e51753ede6..15a27c0b6ee 100644
--- a/compiler/rustc_abi/src/lib.rs
+++ b/compiler/rustc_abi/src/lib.rs
@@ -1215,6 +1215,15 @@ impl Scalar {
             Scalar::Union { .. } => true,
         }
     }
+
+    /// Returns `true` if this is a signed integer scalar
+    #[inline]
+    pub fn is_signed(&self) -> bool {
+        match self.primitive() {
+            Primitive::Int(_, signed) => signed,
+            _ => false,
+        }
+    }
 }
 
 // NOTE: This struct is generic over the FieldIdx for rust-analyzer usage.
@@ -1401,10 +1410,7 @@ impl BackendRepr {
     #[inline]
     pub fn is_signed(&self) -> bool {
         match self {
-            BackendRepr::Scalar(scal) => match scal.primitive() {
-                Primitive::Int(_, signed) => signed,
-                _ => false,
-            },
+            BackendRepr::Scalar(scal) => scal.is_signed(),
             _ => panic!("`is_signed` on non-scalar ABI {self:?}"),
         }
     }
@@ -1499,7 +1505,11 @@ impl BackendRepr {
 #[cfg_attr(feature = "nightly", derive(HashStable_Generic))]
 pub enum Variants<FieldIdx: Idx, VariantIdx: Idx> {
     /// Single enum variants, structs/tuples, unions, and all non-ADTs.
-    Single { index: VariantIdx },
+    Single {
+        /// Always 0 for non-enums/generators.
+        /// For enums without a variant, this is an invalid index!
+        index: VariantIdx,
+    },
 
     /// Enum-likes with more than one variant: each variant comes with
     /// a *discriminant* (usually the same as the variant index but the user can
@@ -1528,14 +1538,22 @@ pub enum TagEncoding<VariantIdx: Idx> {
     /// The variant `untagged_variant` contains a niche at an arbitrary
     /// offset (field `tag_field` of the enum), which for a variant with
     /// discriminant `d` is set to
-    /// `(d - niche_variants.start).wrapping_add(niche_start)`.
+    /// `(d - niche_variants.start).wrapping_add(niche_start)`
+    /// (this is wrapping arithmetic using the type of the niche field).
     ///
     /// For example, `Option<(usize, &T)>`  is represented such that
     /// `None` has a null pointer for the second tuple field, and
     /// `Some` is the identity function (with a non-null reference).
+    ///
+    /// Other variants that are not `untagged_variant` and that are outside the `niche_variants`
+    /// range cannot be represented; they must be uninhabited.
     Niche {
         untagged_variant: VariantIdx,
+        /// This range *may* contain `untagged_variant`; that is then just a "dead value" and
+        /// not used to encode anything.
         niche_variants: RangeInclusive<VariantIdx>,
+        /// This is inbounds of the type of the niche field
+        /// (not sign-extended, i.e., all bits beyond the niche field size are 0).
         niche_start: u128,
     },
 }
diff --git a/compiler/rustc_const_eval/src/const_eval/mod.rs b/compiler/rustc_const_eval/src/const_eval/mod.rs
index 8cbdcd68e13..34f795bda75 100644
--- a/compiler/rustc_const_eval/src/const_eval/mod.rs
+++ b/compiler/rustc_const_eval/src/const_eval/mod.rs
@@ -2,6 +2,7 @@
 
 use rustc_abi::VariantIdx;
 use rustc_middle::query::{Key, TyCtxtAt};
+use rustc_middle::ty::layout::LayoutOf;
 use rustc_middle::ty::{self, Ty, TyCtxt};
 use rustc_middle::{bug, mir};
 use tracing::instrument;
@@ -85,5 +86,6 @@ pub fn tag_for_variant_provider<'tcx>(
         crate::const_eval::DummyMachine,
     );
 
-    ecx.tag_for_variant(ty, variant_index).unwrap().map(|(tag, _tag_field)| tag)
+    let layout = ecx.layout_of(ty).unwrap();
+    ecx.tag_for_variant(layout, variant_index).unwrap().map(|(tag, _tag_field)| tag)
 }
diff --git a/compiler/rustc_const_eval/src/interpret/discriminant.rs b/compiler/rustc_const_eval/src/interpret/discriminant.rs
index f94d0cbb42b..6faac1582ab 100644
--- a/compiler/rustc_const_eval/src/interpret/discriminant.rs
+++ b/compiler/rustc_const_eval/src/interpret/discriminant.rs
@@ -1,7 +1,7 @@
 //! Functions for reading and writing discriminants of multi-variant layouts (enums and coroutines).
 
 use rustc_abi::{self as abi, TagEncoding, VariantIdx, Variants};
-use rustc_middle::ty::layout::{LayoutOf, PrimitiveExt};
+use rustc_middle::ty::layout::{LayoutOf, PrimitiveExt, TyAndLayout};
 use rustc_middle::ty::{self, CoroutineArgsExt, ScalarInt, Ty};
 use rustc_middle::{mir, span_bug};
 use tracing::{instrument, trace};
@@ -21,17 +21,7 @@ impl<'tcx, M: Machine<'tcx>> InterpCx<'tcx, M> {
         variant_index: VariantIdx,
         dest: &impl Writeable<'tcx, M::Provenance>,
     ) -> InterpResult<'tcx> {
-        // Layout computation excludes uninhabited variants from consideration
-        // therefore there's no way to represent those variants in the given layout.
-        // Essentially, uninhabited variants do not have a tag that corresponds to their
-        // discriminant, so we cannot do anything here.
-        // When evaluating we will always error before even getting here, but ConstProp 'executes'
-        // dead code, so we cannot ICE here.
-        if dest.layout().for_variant(self, variant_index).is_uninhabited() {
-            throw_ub!(UninhabitedEnumVariantWritten(variant_index))
-        }
-
-        match self.tag_for_variant(dest.layout().ty, variant_index)? {
+        match self.tag_for_variant(dest.layout(), variant_index)? {
             Some((tag, tag_field)) => {
                 // No need to validate that the discriminant here because the
                 // `TyAndLayout::for_variant()` call earlier already checks the
@@ -80,7 +70,7 @@ impl<'tcx, M: Machine<'tcx>> InterpCx<'tcx, M> {
                 if ty.is_enum() {
                     // Hilariously, `Single` is used even for 0-variant enums.
                     // (See https://github.com/rust-lang/rust/issues/89765).
-                    if matches!(ty.kind(), ty::Adt(def, ..) if def.variants().is_empty()) {
+                    if ty.ty_adt_def().unwrap().variants().is_empty() {
                         throw_ub!(UninhabitedEnumVariantRead(index))
                     }
                     // For consistency with `write_discriminant`, and to make sure that
@@ -188,6 +178,11 @@ impl<'tcx, M: Machine<'tcx>> InterpCx<'tcx, M> {
                             let variants =
                                 ty.ty_adt_def().expect("tagged layout for non adt").variants();
                             assert!(variant_index < variants.next_index());
+                            if variant_index == untagged_variant {
+                                // The untagged variant can be in the niche range, but even then it
+                                // is not a valid encoding.
+                                throw_ub!(InvalidTag(Scalar::from_uint(tag_bits, tag_layout.size)))
+                            }
                             variant_index
                         } else {
                             untagged_variant
@@ -236,10 +231,18 @@ impl<'tcx, M: Machine<'tcx>> InterpCx<'tcx, M> {
     ///   given field index.
     pub(crate) fn tag_for_variant(
         &self,
-        ty: Ty<'tcx>,
+        layout: TyAndLayout<'tcx>,
         variant_index: VariantIdx,
     ) -> InterpResult<'tcx, Option<(ScalarInt, usize)>> {
-        match self.layout_of(ty)?.variants {
+        // Layout computation excludes uninhabited variants from consideration.
+        // Therefore, there's no way to represent those variants in the given layout.
+        // Essentially, uninhabited variants do not have a tag that corresponds to their
+        // discriminant, so we have to bail out here.
+        if layout.for_variant(self, variant_index).is_uninhabited() {
+            throw_ub!(UninhabitedEnumVariantWritten(variant_index))
+        }
+
+        match layout.variants {
             abi::Variants::Single { .. } => {
                 // The tag of a `Single` enum is like the tag of the niched
                 // variant: there's no tag as the discriminant is encoded
@@ -260,7 +263,7 @@ impl<'tcx, M: Machine<'tcx>> InterpCx<'tcx, M> {
                 // raw discriminants for enums are isize or bigger during
                 // their computation, but the in-memory tag is the smallest possible
                 // representation
-                let discr = self.discriminant_for_variant(ty, variant_index)?;
+                let discr = self.discriminant_for_variant(layout.ty, variant_index)?;
                 let discr_size = discr.layout.size;
                 let discr_val = discr.to_scalar().to_bits(discr_size)?;
                 let tag_size = tag_layout.size(self);
@@ -286,11 +289,13 @@ impl<'tcx, M: Machine<'tcx>> InterpCx<'tcx, M> {
                 ..
             } => {
                 assert!(variant_index != untagged_variant);
+                // We checked that this variant is inhabited, so it must be in the niche range.
+                assert!(
+                    niche_variants.contains(&variant_index),
+                    "invalid variant index for this enum"
+                );
                 let variants_start = niche_variants.start().as_u32();
-                let variant_index_relative = variant_index
-                    .as_u32()
-                    .checked_sub(variants_start)
-                    .expect("overflow computing relative variant idx");
+                let variant_index_relative = variant_index.as_u32().strict_sub(variants_start);
                 // We need to use machine arithmetic when taking into account `niche_start`:
                 // tag_val = variant_index_relative + niche_start_val
                 let tag_layout = self.layout_of(tag_layout.primitive().to_int_ty(*self.tcx))?;
diff --git a/compiler/rustc_const_eval/src/lib.rs b/compiler/rustc_const_eval/src/lib.rs
index 2a7408f1c70..b5adf06b300 100644
--- a/compiler/rustc_const_eval/src/lib.rs
+++ b/compiler/rustc_const_eval/src/lib.rs
@@ -10,6 +10,7 @@
 #![feature(never_type)]
 #![feature(rustdoc_internals)]
 #![feature(slice_ptr_get)]
+#![feature(strict_overflow_ops)]
 #![feature(trait_alias)]
 #![feature(try_blocks)]
 #![feature(unqualified_local_imports)]
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index dfa62d875b3..df110fdc20a 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -1081,6 +1081,8 @@ rustc_queries! {
     }
 
     /// Computes the tag (if any) for a given type and variant.
+    /// `None` means that the variant doesn't need a tag (because it is niched).
+    /// Will panic for uninhabited variants.
     query tag_for_variant(
         key: (Ty<'tcx>, abi::VariantIdx)
     ) -> Option<ty::ScalarInt> {
diff --git a/compiler/rustc_transmute/src/layout/tree.rs b/compiler/rustc_transmute/src/layout/tree.rs
index f19a567cd84..83463babc4f 100644
--- a/compiler/rustc_transmute/src/layout/tree.rs
+++ b/compiler/rustc_transmute/src/layout/tree.rs
@@ -319,38 +319,35 @@ pub(crate) mod rustc {
         ) -> Result<Self, Err> {
             assert!(def.is_enum());
 
-            // Computes the variant of a given index.
-            let layout_of_variant = |index, encoding: Option<TagEncoding<VariantIdx>>| {
-                let tag = cx.tcx().tag_for_variant((cx.tcx().erase_regions(ty), index));
-                let variant_def = Def::Variant(def.variant(index));
-                let variant_layout = ty_variant(cx, (ty, layout), index);
-                Self::from_variant(
-                    variant_def,
-                    tag.map(|tag| (tag, index, encoding.unwrap())),
-                    (ty, variant_layout),
-                    layout.size,
-                    cx,
-                )
-            };
+            // Computes the layout of a variant.
+            let layout_of_variant =
+                |index, encoding: Option<TagEncoding<VariantIdx>>| -> Result<Self, Err> {
+                    let variant_layout = ty_variant(cx, (ty, layout), index);
+                    if variant_layout.is_uninhabited() {
+                        return Ok(Self::uninhabited());
+                    }
+                    let tag = cx.tcx().tag_for_variant((cx.tcx().erase_regions(ty), index));
+                    let variant_def = Def::Variant(def.variant(index));
+                    Self::from_variant(
+                        variant_def,
+                        tag.map(|tag| (tag, index, encoding.unwrap())),
+                        (ty, variant_layout),
+                        layout.size,
+                        cx,
+                    )
+                };
 
-            // We consider three kinds of enums, each demanding a different
-            // treatment of their layout computation:
-            // 1. enums that are uninhabited ZSTs
-            // 2. enums that delegate their layout to a variant
-            // 3. enums with multiple variants
             match layout.variants() {
-                Variants::Single { .. } if layout.is_uninhabited() && layout.size == Size::ZERO => {
-                    // The layout representation of uninhabited, ZST enums is
-                    // defined to be like that of the `!` type, as opposed of a
-                    // typical enum. Consequently, they cannot be descended into
-                    // as if they typical enums. We therefore special-case this
-                    // scenario and simply return an uninhabited `Tree`.
-                    Ok(Self::uninhabited())
-                }
                 Variants::Single { index } => {
-                    // `Variants::Single` on enums with variants denotes that
-                    // the enum delegates its layout to the variant at `index`.
-                    layout_of_variant(*index, None)
+                    // Hilariously, `Single` is used even for 0-variant enums;
+                    // `index` is just junk in that case.
+                    if ty.ty_adt_def().unwrap().variants().is_empty() {
+                        Ok(Self::uninhabited())
+                    } else {
+                        // `Variants::Single` on enums with variants denotes that
+                        // the enum delegates its layout to the variant at `index`.
+                        layout_of_variant(*index, None)
+                    }
                 }
                 Variants::Multiple { tag, tag_encoding, tag_field, .. } => {
                     // `Variants::Multiple` denotes an enum with multiple
@@ -369,7 +366,7 @@ pub(crate) mod rustc {
                         },
                     )?;
 
-                    return Ok(Self::def(Def::Adt(def)).then(variants));
+                    Ok(Self::def(Def::Adt(def)).then(variants))
                 }
             }
         }
diff --git a/compiler/rustc_ty_utils/src/layout.rs b/compiler/rustc_ty_utils/src/layout.rs
index 66134b81b2a..0d656f1b63b 100644
--- a/compiler/rustc_ty_utils/src/layout.rs
+++ b/compiler/rustc_ty_utils/src/layout.rs
@@ -81,7 +81,7 @@ fn layout_of<'tcx>(
         record_layout_for_printing(&cx, layout);
     }
 
-    invariant::partially_check_layout(&cx, &layout);
+    invariant::layout_sanity_check(&cx, &layout);
 
     Ok(layout)
 }
diff --git a/compiler/rustc_ty_utils/src/layout/invariant.rs b/compiler/rustc_ty_utils/src/layout/invariant.rs
index 26ea81daf78..f39b87622f4 100644
--- a/compiler/rustc_ty_utils/src/layout/invariant.rs
+++ b/compiler/rustc_ty_utils/src/layout/invariant.rs
@@ -1,11 +1,11 @@
 use std::assert_matches::assert_matches;
 
-use rustc_abi::{BackendRepr, FieldsShape, Scalar, Size, Variants};
+use rustc_abi::{BackendRepr, FieldsShape, Scalar, Size, TagEncoding, Variants};
 use rustc_middle::bug;
 use rustc_middle::ty::layout::{HasTyCtxt, LayoutCx, TyAndLayout};
 
 /// Enforce some basic invariants on layouts.
-pub(super) fn partially_check_layout<'tcx>(cx: &LayoutCx<'tcx>, layout: &TyAndLayout<'tcx>) {
+pub(super) fn layout_sanity_check<'tcx>(cx: &LayoutCx<'tcx>, layout: &TyAndLayout<'tcx>) {
     let tcx = cx.tcx();
 
     // Type-level uninhabitedness should always imply ABI uninhabitedness.
@@ -241,7 +241,17 @@ pub(super) fn partially_check_layout<'tcx>(cx: &LayoutCx<'tcx>, layout: &TyAndLa
 
     check_layout_abi(cx, layout);
 
-    if let Variants::Multiple { variants, .. } = &layout.variants {
+    if let Variants::Multiple { variants, tag, tag_encoding, .. } = &layout.variants {
+        if let TagEncoding::Niche { niche_start, untagged_variant, niche_variants } = tag_encoding {
+            let niche_size = tag.size(cx);
+            assert!(*niche_start <= niche_size.unsigned_int_max());
+            for (idx, variant) in variants.iter_enumerated() {
+                // Ensure all inhabited variants are accounted for.
+                if !variant.is_uninhabited() {
+                    assert!(idx == *untagged_variant || niche_variants.contains(&idx));
+                }
+            }
+        }
         for variant in variants.iter() {
             // No nested "multiple".
             assert_matches!(variant.variants, Variants::Single { .. });
diff --git a/src/tools/miri/tests/fail/enum-untagged-variant-invalid-encoding.rs b/src/tools/miri/tests/fail/enum-untagged-variant-invalid-encoding.rs
new file mode 100644
index 00000000000..bd02e7f5fb4
--- /dev/null
+++ b/src/tools/miri/tests/fail/enum-untagged-variant-invalid-encoding.rs
@@ -0,0 +1,27 @@
+// Validity makes this fail at the wrong place.
+//@compile-flags: -Zmiri-disable-validation
+use std::mem;
+
+// This enum has untagged variant idx 1, with niche_variants being 0..=2
+// and niche_start being 2.
+// That means the untagged variants is in the niche variant range!
+// However, using the corresponding value (2+1 = 3) is not a valid encoding of this variant.
+#[derive(Copy, Clone, PartialEq)]
+enum Foo {
+    Var1,
+    Var2(bool),
+    Var3,
+}
+
+fn main() {
+    unsafe {
+        assert!(Foo::Var2(false) == mem::transmute(0u8));
+        assert!(Foo::Var2(true) == mem::transmute(1u8));
+        assert!(Foo::Var1 == mem::transmute(2u8));
+        assert!(Foo::Var3 == mem::transmute(4u8));
+
+        let invalid: Foo = mem::transmute(3u8);
+        assert!(matches!(invalid, Foo::Var2(_)));
+        //~^ ERROR: invalid tag
+    }
+}
diff --git a/src/tools/miri/tests/fail/enum-untagged-variant-invalid-encoding.stderr b/src/tools/miri/tests/fail/enum-untagged-variant-invalid-encoding.stderr
new file mode 100644
index 00000000000..759dbc36380
--- /dev/null
+++ b/src/tools/miri/tests/fail/enum-untagged-variant-invalid-encoding.stderr
@@ -0,0 +1,15 @@
+error: Undefined Behavior: enum value has invalid tag: 0x03
+  --> tests/fail/enum-untagged-variant-invalid-encoding.rs:LL:CC
+   |
+LL |         assert!(matches!(invalid, Foo::Var2(_)));
+   |                          ^^^^^^^ enum value has invalid tag: 0x03
+   |
+   = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
+   = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
+   = note: BACKTRACE:
+   = note: inside `main` at tests/fail/enum-untagged-variant-invalid-encoding.rs:LL:CC
+
+note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
+
+error: aborting due to 1 previous error
+
diff --git a/tests/crashes/126267.rs b/tests/crashes/126267.rs
deleted file mode 100644
index 728578179ed..00000000000
--- a/tests/crashes/126267.rs
+++ /dev/null
@@ -1,30 +0,0 @@
-//@ known-bug: rust-lang/rust#126267
-
-#![feature(transmutability)]
-#![crate_type = "lib"]
-
-pub enum ApiError {}
-pub struct TokioError {
-    b: bool,
-}
-pub enum Error {
-    Api { source: ApiError },
-    Ethereum,
-    Tokio { source: TokioError },
-}
-
-mod assert {
-    use std::mem::TransmuteFrom;
-
-    pub fn is_transmutable<Src, Dst>()
-    where
-        Dst: TransmuteFrom<Src>, // safety is NOT assumed
-    {
-    }
-}
-
-fn test() {
-    struct Src;
-    type Dst = Error;
-    assert::is_transmutable::<Src, Dst>();
-}
diff --git a/tests/ui/transmutability/uninhabited.rs b/tests/ui/transmutability/uninhabited.rs
index 74f7a1a2e89..274104ffb39 100644
--- a/tests/ui/transmutability/uninhabited.rs
+++ b/tests/ui/transmutability/uninhabited.rs
@@ -91,3 +91,19 @@ fn distant_void() {
     assert::is_maybe_transmutable::<DistantVoid, &'static Void>();
     assert::is_maybe_transmutable::<u128, DistantVoid>(); //~ ERROR: cannot be safely transmuted
 }
+
+fn issue_126267() {
+    pub enum ApiError {}
+    pub struct TokioError {
+        b: bool,
+    }
+    pub enum Error {
+        Api { source: ApiError }, // this variant is uninhabited
+        Ethereum,
+        Tokio { source: TokioError },
+    }
+
+    struct Src;
+    type Dst = Error;
+    assert::is_maybe_transmutable::<Src, Dst>(); //~ERROR: cannot be safely transmuted
+}
diff --git a/tests/ui/transmutability/uninhabited.stderr b/tests/ui/transmutability/uninhabited.stderr
index 3fa02f0867c..f112d2fbe44 100644
--- a/tests/ui/transmutability/uninhabited.stderr
+++ b/tests/ui/transmutability/uninhabited.stderr
@@ -110,7 +110,29 @@ LL | |             }
 LL | |         }>
    | |__________^ required by this bound in `is_maybe_transmutable`
 
-error: aborting due to 7 previous errors
+error[E0277]: `Src` cannot be safely transmuted into `issue_126267::Error`
+  --> $DIR/uninhabited.rs:108:42
+   |
+LL |     assert::is_maybe_transmutable::<Src, Dst>();
+   |                                          ^^^ the size of `Src` is smaller than the size of `issue_126267::Error`
+   |
+note: required by a bound in `is_maybe_transmutable`
+  --> $DIR/uninhabited.rs:10:14
+   |
+LL |       pub fn is_maybe_transmutable<Src, Dst>()
+   |              --------------------- required by a bound in this function
+LL |       where
+LL |           Dst: TransmuteFrom<Src, {
+   |  ______________^
+LL | |             Assume {
+LL | |                 alignment: true,
+LL | |                 lifetimes: true,
+...  |
+LL | |             }
+LL | |         }>
+   | |__________^ required by this bound in `is_maybe_transmutable`
+
+error: aborting due to 8 previous errors
 
 Some errors have detailed explanations: E0080, E0277.
 For more information about an error, try `rustc --explain E0080`.