Rollup merge of #120354 - lukas-code:metadata-normalize, r=lcnr

improve normalization of `Pointee::Metadata`

This PR makes it so that `<Wrapper<Tail> as Pointee>::Metadata` is normalized to `<Tail as Pointee>::Metadata` if we don't know `Wrapper<Tail>: Sized`. With that, the trait solver can prove projection predicates like `<Wrapper<Tail> as Pointee>::Metadata == <Tail as Pointee>::Metadata`, which makes it possible to use the metadata APIs to cast between the tail and the wrapper:

```rust
#![feature(ptr_metadata)]

use std::ptr::{self, Pointee};

fn cast_same_meta<T: ?Sized, U: ?Sized>(ptr: *const T) -> *const U
where
    T: Pointee<Metadata = <U as Pointee>::Metadata>,
{
    let (thin, meta) = ptr.to_raw_parts();
    ptr::from_raw_parts(thin, meta)
}

struct Wrapper<T: ?Sized>(T);

fn cast_to_wrapper<T: ?Sized>(ptr: *const T) -> *const Wrapper<T> {
    cast_same_meta(ptr)
}
```

Previously, this failed to compile:

```
error[E0271]: type mismatch resolving `<Wrapper<T> as Pointee>::Metadata == <T as Pointee>::Metadata`
  --> src/lib.rs:16:5
   |
15 | fn cast_to_wrapper<T: ?Sized>(ptr: *const T) -> *const Wrapper<T> {
   |                    - found this type parameter
16 |     cast_same_meta(ptr)
   |     ^^^^^^^^^^^^^^ expected `Wrapper<T>`, found type parameter `T`
   |
   = note: expected associated type `<Wrapper<T> as Pointee>::Metadata`
              found associated type `<T as Pointee>::Metadata`
   = note: an associated type was expected, but a different one was found
```

(Yes, you can already do this with `as` casts. But using functions is so much :sparkles: *safer* :sparkles:, because you can't change the metadata on accident.)

---

This PR essentially changes the built-in impls of `Pointee` from this:

```rust
// before

impl Pointee for u8 {
    type Metadata = ();
}

impl Pointee for [u8] {
    type Metadata = usize;
}

// ...

impl Pointee for Wrapper<u8> {
    type Metadata = ();
}

impl Pointee for Wrapper<[u8]> {
    type Metadata = usize;
}

// ...

// This impl is only selected if `T` is a type parameter or unnormalizable projection or opaque type.
fallback impl<T: ?Sized> Pointee for Wrapper<T>
where
    Wrapper<T>: Sized
{
    type Metadata = ();
}

// This impl is only selected if `T` is a type parameter or unnormalizable projection or opaque type.
fallback impl<T /*: Sized */> Pointee for T {
    type Metadata = ();
}
```

to this:

```rust
// after

impl Pointee for u8 {
    type Metadata = ();
}

impl Pointee for [u8] {
    type Metadata = usize;
}

// ...

impl<T: ?Sized> Pointee for Wrapper<T> {
    // in the old solver this will instead project to the "deep" tail directly,
    // e.g. `Wrapper<Wrapper<T>>::Metadata = T::Metadata`
    type Metadata = <T as Pointee>::Metadata;
}

// ...

// This impl is only selected if `T` is a type parameter or unnormalizable projection or opaque type.
fallback impl<T /*: Sized */> Pointee for T {
    type Metadata = ();
}
```

7 files changed, 148 insertions, 59 deletions

diff --git a/compiler/rustc_codegen_llvm/src/intrinsic.rs b/compiler/rustc_codegen_llvm/src/intrinsic.rs
index b4512af38e3..e3e48ecb3aa 100644
--- a/compiler/rustc_codegen_llvm/src/intrinsic.rs
+++ b/compiler/rustc_codegen_llvm/src/intrinsic.rs
@@ -1985,10 +1985,9 @@ fn generic_simd_intrinsic<'ll, 'tcx>(
 
         match in_elem.kind() {
             ty::RawPtr(p) => {
-                let (metadata, check_sized) = p.ty.ptr_metadata_ty(bx.tcx, |ty| {
+                let metadata = p.ty.ptr_metadata_ty(bx.tcx, |ty| {
                     bx.tcx.normalize_erasing_regions(ty::ParamEnv::reveal_all(), ty)
                 });
-                assert!(!check_sized); // we are in codegen, so we shouldn't see these types
                 require!(
                     metadata.is_unit(),
                     InvalidMonomorphization::CastFatPointer { span, name, ty: in_elem }
@@ -2000,10 +1999,9 @@ fn generic_simd_intrinsic<'ll, 'tcx>(
         }
         match out_elem.kind() {
             ty::RawPtr(p) => {
-                let (metadata, check_sized) = p.ty.ptr_metadata_ty(bx.tcx, |ty| {
+                let metadata = p.ty.ptr_metadata_ty(bx.tcx, |ty| {
                     bx.tcx.normalize_erasing_regions(ty::ParamEnv::reveal_all(), ty)
                 });
-                assert!(!check_sized); // we are in codegen, so we shouldn't see these types
                 require!(
                     metadata.is_unit(),
                     InvalidMonomorphization::CastFatPointer { span, name, ty: out_elem }
diff --git a/compiler/rustc_const_eval/src/interpret/terminator.rs b/compiler/rustc_const_eval/src/interpret/terminator.rs
index 85a2e4778d2..ff20fc5092c 100644
--- a/compiler/rustc_const_eval/src/interpret/terminator.rs
+++ b/compiler/rustc_const_eval/src/interpret/terminator.rs
@@ -377,12 +377,7 @@ impl<'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> InterpCx<'mir, 'tcx, M> {
                 // to fields, which can yield non-normalized types. So we need to provide a
                 // normalization function.
                 let normalize = |ty| self.tcx.normalize_erasing_regions(self.param_env, ty);
-                let (meta, only_if_sized) = ty.ptr_metadata_ty(*self.tcx, normalize);
-                assert!(
-                    !only_if_sized,
-                    "there should be no more 'maybe has that metadata' types during interpretation"
-                );
-                meta
+                ty.ptr_metadata_ty(*self.tcx, normalize)
             };
             return Ok(meta_ty(caller) == meta_ty(callee));
         }
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index d6e3385c600..f592acd4b6f 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -2279,12 +2279,12 @@ impl<'tcx> Ty<'tcx> {
     }
 
     /// Returns the type of metadata for (potentially fat) pointers to this type,
-    /// and a boolean signifying if this is conditional on this type being `Sized`.
-    pub fn ptr_metadata_ty(
+    /// or the struct tail if the metadata type cannot be determined.
+    pub fn ptr_metadata_ty_or_tail(
         self,
         tcx: TyCtxt<'tcx>,
         normalize: impl FnMut(Ty<'tcx>) -> Ty<'tcx>,
-    ) -> (Ty<'tcx>, bool) {
+    ) -> Result<Ty<'tcx>, Ty<'tcx>> {
         let tail = tcx.struct_tail_with_normalize(self, normalize, || {});
         match tail.kind() {
             // Sized types
@@ -2307,31 +2307,47 @@ impl<'tcx> Ty<'tcx> {
             | ty::Error(_)
             // Extern types have metadata = ().
             | ty::Foreign(..)
-            // `dyn*` has no metadata
+            // `dyn*` has metadata = ().
             | ty::Dynamic(_, _, ty::DynStar)
-            // If returned by `struct_tail_without_normalization` this is a unit struct
+            // If returned by `struct_tail_with_normalize` this is a unit struct
             // without any fields, or not a struct, and therefore is Sized.
             | ty::Adt(..)
-            // If returned by `struct_tail_without_normalization` this is the empty tuple,
+            // If returned by `struct_tail_with_normalize` this is the empty tuple,
             // a.k.a. unit type, which is Sized
-            | ty::Tuple(..) => (tcx.types.unit, false),
+            | ty::Tuple(..) => Ok(tcx.types.unit),
+
+            ty::Str | ty::Slice(_) => Ok(tcx.types.usize),
 
-            ty::Str | ty::Slice(_) => (tcx.types.usize, false),
             ty::Dynamic(_, _, ty::Dyn) => {
                 let dyn_metadata = tcx.require_lang_item(LangItem::DynMetadata, None);
-                (tcx.type_of(dyn_metadata).instantiate(tcx, &[tail.into()]), false)
-            },
+                Ok(tcx.type_of(dyn_metadata).instantiate(tcx, &[tail.into()]))
+            }
 
-            // type parameters only have unit metadata if they're sized, so return true
-            // to make sure we double check this during confirmation
-            ty::Param(_) |  ty::Alias(..) => (tcx.types.unit, true),
+            // We don't know the metadata of `self`, but it must be equal to the
+            // metadata of `tail`.
+            ty::Param(_) | ty::Alias(..) => Err(tail),
 
             ty::Infer(ty::TyVar(_))
             | ty::Bound(..)
             | ty::Placeholder(..)
-            | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
-                bug!("`ptr_metadata_ty` applied to unexpected type: {:?} (tail = {:?})", self, tail)
-            }
+            | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(
+                "`ptr_metadata_ty_or_tail` applied to unexpected type: {self:?} (tail = {tail:?})"
+            ),
+        }
+    }
+
+    /// Returns the type of metadata for (potentially fat) pointers to this type.
+    /// Causes an ICE if the metadata type cannot be determined.
+    pub fn ptr_metadata_ty(
+        self,
+        tcx: TyCtxt<'tcx>,
+        normalize: impl FnMut(Ty<'tcx>) -> Ty<'tcx>,
+    ) -> Ty<'tcx> {
+        match self.ptr_metadata_ty_or_tail(tcx, normalize) {
+            Ok(metadata) => metadata,
+            Err(tail) => bug!(
+                "`ptr_metadata_ty` failed to get metadata for type: {self:?} (tail = {tail:?})"
+            ),
         }
     }
 
diff --git a/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
index 47ba549022d..d177109c420 100644
--- a/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
@@ -491,6 +491,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for NormalizesTo<'tcx> {
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
         let tcx = ecx.tcx();
+        let metadata_def_id = tcx.require_lang_item(LangItem::Metadata, None);
+        assert_eq!(metadata_def_id, goal.predicate.def_id());
         ecx.probe_misc_candidate("builtin pointee").enter(|ecx| {
             let metadata_ty = match goal.predicate.self_ty().kind() {
                 ty::Bool
@@ -522,7 +524,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for NormalizesTo<'tcx> {
                 }
 
                 ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => {
-                    // FIXME(ptr_metadata): It would also be possible to return a `Ok(Ambig)` with no constraints.
+                    // This is the "fallback impl" for type parameters, unnormalizable projections
+                    // and opaque types: If the `self_ty` is `Sized`, then the metadata is `()`.
+                    // FIXME(ptr_metadata): This impl overlaps with the other impls and shouldn't
+                    // exist. Instead, `Pointee<Metadata = ()>` should be a supertrait of `Sized`.
                     let sized_predicate = ty::TraitRef::from_lang_item(
                         tcx,
                         LangItem::Sized,
@@ -536,30 +541,16 @@ impl<'tcx> assembly::GoalKind<'tcx> for NormalizesTo<'tcx> {
 
                 ty::Adt(def, args) if def.is_struct() => match def.non_enum_variant().tail_opt() {
                     None => tcx.types.unit,
-                    Some(field_def) => {
-                        let self_ty = field_def.ty(tcx, args);
-                        // FIXME(-Znext-solver=coinductive): Should this be `GoalSource::ImplWhereBound`?
-                        ecx.add_goal(
-                            GoalSource::Misc,
-                            goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty)),
-                        );
-                        return ecx
-                            .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
+                    Some(tail_def) => {
+                        let tail_ty = tail_def.ty(tcx, args);
+                        Ty::new_projection(tcx, metadata_def_id, [tail_ty])
                     }
                 },
                 ty::Adt(_, _) => tcx.types.unit,
 
                 ty::Tuple(elements) => match elements.last() {
                     None => tcx.types.unit,
-                    Some(&self_ty) => {
-                        // FIXME(-Znext-solver=coinductive): Should this be `GoalSource::ImplWhereBound`?
-                        ecx.add_goal(
-                            GoalSource::Misc,
-                            goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty)),
-                        );
-                        return ecx
-                            .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
-                    }
+                    Some(&tail_ty) => Ty::new_projection(tcx, metadata_def_id, [tail_ty]),
                 },
 
                 ty::Infer(
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs
index fd8306bbc0b..d271a0ea33b 100644
--- a/compiler/rustc_trait_selection/src/traits/project.rs
+++ b/compiler/rustc_trait_selection/src/traits/project.rs
@@ -1935,10 +1935,11 @@ fn assemble_candidates_from_impls<'cx, 'tcx>(
                         // Integers and floats are always Sized, and so have unit type metadata.
                         | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true,
 
-                        // type parameters, opaques, and unnormalized projections have pointer
-                        // metadata if they're known (e.g. by the param_env) to be sized
+                        // We normalize from `Wrapper<Tail>::Metadata` to `Tail::Metadata` if able.
+                        // Otherwise, type parameters, opaques, and unnormalized projections have
+                        // unit metadata if they're known (e.g. by the param_env) to be sized.
                         ty::Param(_) | ty::Alias(..)
-                            if selcx.infcx.predicate_must_hold_modulo_regions(
+                            if self_ty != tail || selcx.infcx.predicate_must_hold_modulo_regions(
                                 &obligation.with(
                                     selcx.tcx(),
                                     ty::TraitRef::from_lang_item(selcx.tcx(), LangItem::Sized, obligation.cause.span(),[self_ty]),
@@ -2312,7 +2313,7 @@ fn confirm_builtin_candidate<'cx, 'tcx>(
         assert_eq!(metadata_def_id, item_def_id);
 
         let mut obligations = Vec::new();
-        let (metadata_ty, check_is_sized) = self_ty.ptr_metadata_ty(tcx, |ty| {
+        let normalize = |ty| {
             normalize_with_depth_to(
                 selcx,
                 obligation.param_env,
@@ -2321,16 +2322,27 @@ fn confirm_builtin_candidate<'cx, 'tcx>(
                 ty,
                 &mut obligations,
             )
+        };
+        let metadata_ty = self_ty.ptr_metadata_ty_or_tail(tcx, normalize).unwrap_or_else(|tail| {
+            if tail == self_ty {
+                // This is the "fallback impl" for type parameters, unnormalizable projections
+                // and opaque types: If the `self_ty` is `Sized`, then the metadata is `()`.
+                // FIXME(ptr_metadata): This impl overlaps with the other impls and shouldn't
+                // exist. Instead, `Pointee<Metadata = ()>` should be a supertrait of `Sized`.
+                let sized_predicate = ty::TraitRef::from_lang_item(
+                    tcx,
+                    LangItem::Sized,
+                    obligation.cause.span(),
+                    [self_ty],
+                );
+                obligations.push(obligation.with(tcx, sized_predicate));
+                tcx.types.unit
+            } else {
+                // We know that `self_ty` has the same metadata as `tail`. This allows us
+                // to prove predicates like `Wrapper<Tail>::Metadata == Tail::Metadata`.
+                Ty::new_projection(tcx, metadata_def_id, [tail])
+            }
         });
-        if check_is_sized {
-            let sized_predicate = ty::TraitRef::from_lang_item(
-                tcx,
-                LangItem::Sized,
-                obligation.cause.span(),
-                [self_ty],
-            );
-            obligations.push(obligation.with(tcx, sized_predicate));
-        }
         (metadata_ty.into(), obligations)
     } else {
         bug!("unexpected builtin trait with associated type: {:?}", obligation.predicate);
diff --git a/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs b/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs
index 4c0c57377e0..a050b30317a 100644
--- a/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/evaluate_obligation.rs
@@ -41,7 +41,28 @@ impl<'tcx> InferCtxtExt<'tcx> for InferCtxt<'tcx> {
     /// not entirely accurate if inference variables are involved.
     ///
     /// This version may conservatively fail when outlives obligations
-    /// are required.
+    /// are required. Therefore, this version should only be used for
+    /// optimizations or diagnostics and be treated as if it can always
+    /// return `false`.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// # #![allow(dead_code)]
+    /// trait Trait {}
+    ///
+    /// fn check<T: Trait>() {}
+    ///
+    /// fn foo<T: 'static>()
+    /// where
+    ///     &'static T: Trait,
+    /// {
+    ///     // Evaluating `&'?0 T: Trait` adds a `'?0: 'static` outlives obligation,
+    ///     // which means that `predicate_must_hold_considering_regions` will return
+    ///     // `false`.
+    ///     check::<&'_ T>();
+    /// }
+    /// ```
     fn predicate_must_hold_considering_regions(
         &self,
         obligation: &PredicateObligation<'tcx>,
diff --git a/tests/ui/traits/pointee-normalize-equate.rs b/tests/ui/traits/pointee-normalize-equate.rs
new file mode 100644
index 00000000000..2e75933aca0
--- /dev/null
+++ b/tests/ui/traits/pointee-normalize-equate.rs
@@ -0,0 +1,56 @@
+// check-pass
+// revisions: old next
+//[next] compile-flags: -Znext-solver
+
+#![feature(ptr_metadata)]
+
+use std::ptr::{self, Pointee};
+
+fn cast_same_meta<T: ?Sized, U: ?Sized>(ptr: *const T) -> *const U
+where
+    T: Pointee<Metadata = <U as Pointee>::Metadata>,
+{
+    let (thin, meta) = ptr.to_raw_parts();
+    ptr::from_raw_parts(thin, meta)
+}
+
+struct Wrapper<T: ?Sized>(T);
+
+// normalize `Wrapper<T>::Metadata` -> `T::Metadata`
+fn wrapper_to_tail<T: ?Sized>(ptr: *const T) -> *const Wrapper<T> {
+    cast_same_meta(ptr)
+}
+
+// normalize `Wrapper<T>::Metadata` -> `T::Metadata` -> `()`
+fn wrapper_to_unit<T>(ptr: *const ()) -> *const Wrapper<T> {
+    cast_same_meta(ptr)
+}
+
+trait Project {
+    type Assoc: ?Sized;
+}
+
+struct WrapperProject<T: ?Sized + Project>(T::Assoc);
+
+// normalize `WrapperProject<T>::Metadata` -> `T::Assoc::Metadata`
+fn wrapper_project_tail<T: ?Sized + Project>(ptr: *const T::Assoc) -> *const WrapperProject<T> {
+    cast_same_meta(ptr)
+}
+
+// normalize `WrapperProject<T>::Metadata` -> `T::Assoc::Metadata` -> `()`
+fn wrapper_project_unit<T: ?Sized + Project>(ptr: *const ()) -> *const WrapperProject<T>
+where
+    T::Assoc: Sized,
+{
+    cast_same_meta(ptr)
+}
+
+// normalize `<[T] as Pointee>::Metadata` -> `usize`, even if `[T]: Sized`
+fn sized_slice<T>(ptr: *const [T]) -> *const str
+where
+    [T]: Sized,
+{
+    cast_same_meta(ptr)
+}
+
+fn main() {}