Auto merge of #137944 - davidtwco:sized-hierarchy, r=oli-obk

Sized Hierarchy: Part I

This patch implements the non-const parts of rust-lang/rfcs#3729. It introduces two new traits to the standard library, `MetaSized` and `PointeeSized`. See the RFC for the rationale behind these traits and to discuss whether this change makes sense in the abstract.

These traits are unstable (as is their constness), so users cannot refer to them without opting-in to `feature(sized_hierarchy)`. These traits are not behind `cfg`s as this would make implementation unfeasible, there would simply be too many `cfg`s required to add the necessary bounds everywhere. So, like `Sized`, these traits are automatically implemented by the compiler.

RFC 3729 describes changes which are necessary to preserve backwards compatibility given the introduction of these traits, which are implemented and as follows:

- `?Sized` is rewritten as `MetaSized`
- `MetaSized` is added as a default supertrait for all traits w/out an explicit sizedness supertrait already.

There are no edition migrations implemented in this,  as these are primarily required for the constness parts of the RFC and prior to stabilisation of this (and so will come in follow-up PRs alongside the const parts). All diagnostic output should remain the same (showing `?Sized` even if the compiler sees `MetaSized`) unless the `sized_hierarchy` feature is enabled.

Due to the use of unstable extern types in the standard library and rustc, some bounds in both projects have had to be relaxed already - this is unfortunate but unavoidable so that these extern types can continue to be used where they were before. Performing these relaxations in the standard library and rustc are desirable longer-term anyway, but some bounds are not as relaxed as they ideally would be due to the inability to relax `Deref::Target` (this will be investigated separately).

It is hoped that this is implemented such that it could be merged and these traits could exist "under the hood" without that being observable to the user (other than in any performance impact this has on the compiler, etc). Some details might leak through due to the standard library relaxations, but this has not been observed in test output.

**Notes:**

- Any commits starting with "upstream:" can be ignored, as these correspond to other upstream PRs that this is based on which have yet to be merged.
- This best reviewed commit-by-commit. I've attempted to make the implementation easy to follow and keep similar changes and test output updates together.
  - Each commit has a short description describing its purpose.
  - This patch is large but it's primarily in the test suite.
- I've worked on the performance of this patch and a few optimisations are implemented so that the performance impact is neutral-to-minor.
- `PointeeSized` is a different name from the RFC just to make it more obvious that it is different from `std::ptr::Pointee` but all the names are yet to be bikeshed anyway.
- `@nikomatsakis` has confirmed [that this can proceed as an experiment from the t-lang side](https://rust-lang.zulipchat.com/#narrow/channel/435869-project-goals/topic/SVE.20and.20SME.20on.20AArch64.20.28goals.23270.29/near/506196491)
- FCP in https://github.com/rust-lang/rust/pull/137944#issuecomment-2912207485

Fixes rust-lang/rust#79409.

r? `@ghost` (I'll discuss this with relevant teams to find a reviewer)

10 files changed, 97 insertions, 37 deletions

diff --git a/compiler/rustc_middle/src/lib.rs b/compiler/rustc_middle/src/lib.rs
index 667361b3ca0..6cb1d8c5fc4 100644
--- a/compiler/rustc_middle/src/lib.rs
+++ b/compiler/rustc_middle/src/lib.rs
@@ -28,6 +28,7 @@
 #![allow(internal_features)]
 #![allow(rustc::diagnostic_outside_of_impl)]
 #![allow(rustc::untranslatable_diagnostic)]
+#![cfg_attr(not(bootstrap), feature(sized_hierarchy))]
 #![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")]
 #![doc(rust_logo)]
 #![feature(allocator_api)]
diff --git a/compiler/rustc_middle/src/query/keys.rs b/compiler/rustc_middle/src/query/keys.rs
index 9ed1f10455a..4d914c42cfc 100644
--- a/compiler/rustc_middle/src/query/keys.rs
+++ b/compiler/rustc_middle/src/query/keys.rs
@@ -328,6 +328,14 @@ impl Key for (DefId, SimplifiedType) {
     }
 }
 
+impl Key for (DefId, ty::SizedTraitKind) {
+    type Cache<V> = DefaultCache<Self, V>;
+
+    fn default_span(&self, tcx: TyCtxt<'_>) -> Span {
+        self.0.default_span(tcx)
+    }
+}
+
 impl<'tcx> Key for GenericArgsRef<'tcx> {
     type Cache<V> = DefaultCache<Self, V>;
 
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index 63312eff490..930d9fba433 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -137,8 +137,8 @@ use crate::ty::layout::ValidityRequirement;
 use crate::ty::print::{PrintTraitRefExt, describe_as_module};
 use crate::ty::util::AlwaysRequiresDrop;
 use crate::ty::{
-    self, CrateInherentImpls, GenericArg, GenericArgsRef, PseudoCanonicalInput, Ty, TyCtxt,
-    TyCtxtFeed,
+    self, CrateInherentImpls, GenericArg, GenericArgsRef, PseudoCanonicalInput, SizedTraitKind, Ty,
+    TyCtxt, TyCtxtFeed,
 };
 use crate::{dep_graph, mir, thir};
 
@@ -910,9 +910,10 @@ rustc_queries! {
         cache_on_disk_if { key.is_local() }
         separate_provide_extern
     }
-
-    query adt_sized_constraint(key: DefId) -> Option<ty::EarlyBinder<'tcx, Ty<'tcx>>> {
-        desc { |tcx| "computing the `Sized` constraint for `{}`", tcx.def_path_str(key) }
+    query adt_sizedness_constraint(
+        key: (DefId, SizedTraitKind)
+    ) -> Option<ty::EarlyBinder<'tcx, Ty<'tcx>>> {
+        desc { |tcx| "computing the sizedness constraint for `{}`", tcx.def_path_str(key.0) }
     }
 
     query adt_dtorck_constraint(
diff --git a/compiler/rustc_middle/src/ty/adt.rs b/compiler/rustc_middle/src/ty/adt.rs
index d92b4f9c06b..6d5a3abf665 100644
--- a/compiler/rustc_middle/src/ty/adt.rs
+++ b/compiler/rustc_middle/src/ty/adt.rs
@@ -229,8 +229,12 @@ impl<'tcx> rustc_type_ir::inherent::AdtDef<TyCtxt<'tcx>> for AdtDef<'tcx> {
         )
     }
 
-    fn sized_constraint(self, tcx: TyCtxt<'tcx>) -> Option<ty::EarlyBinder<'tcx, Ty<'tcx>>> {
-        self.sized_constraint(tcx)
+    fn sizedness_constraint(
+        self,
+        tcx: TyCtxt<'tcx>,
+        sizedness: ty::SizedTraitKind,
+    ) -> Option<ty::EarlyBinder<'tcx, Ty<'tcx>>> {
+        self.sizedness_constraint(tcx, sizedness)
     }
 
     fn is_fundamental(self) -> bool {
@@ -634,10 +638,15 @@ impl<'tcx> AdtDef<'tcx> {
         tcx.adt_async_destructor(self.did())
     }
 
-    /// Returns a type such that `Self: Sized` if and only if that type is `Sized`,
-    /// or `None` if the type is always sized.
-    pub fn sized_constraint(self, tcx: TyCtxt<'tcx>) -> Option<ty::EarlyBinder<'tcx, Ty<'tcx>>> {
-        if self.is_struct() { tcx.adt_sized_constraint(self.did()) } else { None }
+    /// If this ADT is a struct, returns a type such that `Self: {Meta,Pointee,}Sized` if and only
+    /// if that type is `{Meta,Pointee,}Sized`, or `None` if this ADT is always
+    /// `{Meta,Pointee,}Sized`.
+    pub fn sizedness_constraint(
+        self,
+        tcx: TyCtxt<'tcx>,
+        sizedness: ty::SizedTraitKind,
+    ) -> Option<ty::EarlyBinder<'tcx, Ty<'tcx>>> {
+        if self.is_struct() { tcx.adt_sizedness_constraint((self.did(), sizedness)) } else { None }
     }
 }
 
diff --git a/compiler/rustc_middle/src/ty/codec.rs b/compiler/rustc_middle/src/ty/codec.rs
index e0f70737add..3d7965f6cfe 100644
--- a/compiler/rustc_middle/src/ty/codec.rs
+++ b/compiler/rustc_middle/src/ty/codec.rs
@@ -13,7 +13,7 @@ use std::marker::DiscriminantKind;
 use rustc_abi::{FieldIdx, VariantIdx};
 use rustc_data_structures::fx::FxHashMap;
 use rustc_hir::def_id::LocalDefId;
-use rustc_serialize::{Decodable, Encodable};
+use rustc_serialize::{Decodable, Encodable, PointeeSized};
 use rustc_span::source_map::Spanned;
 use rustc_span::{Span, SpanDecoder, SpanEncoder};
 
@@ -96,7 +96,7 @@ impl<'tcx, E: TyEncoder<'tcx>> EncodableWithShorthand<'tcx, E> for ty::Predicate
 ///
 /// `Decodable` can still be implemented in cases where `Decodable` is required
 /// by a trait bound.
-pub trait RefDecodable<'tcx, D: TyDecoder<'tcx>> {
+pub trait RefDecodable<'tcx, D: TyDecoder<'tcx>>: PointeeSized {
     fn decode(d: &mut D) -> &'tcx Self;
 }
 
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index fe4dd8d080b..f1395c242f2 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -43,6 +43,7 @@ use rustc_macros::{HashStable, TyDecodable, TyEncodable};
 use rustc_query_system::cache::WithDepNode;
 use rustc_query_system::dep_graph::DepNodeIndex;
 use rustc_query_system::ich::StableHashingContext;
+use rustc_serialize::PointeeSized;
 use rustc_serialize::opaque::{FileEncodeResult, FileEncoder};
 use rustc_session::config::CrateType;
 use rustc_session::cstore::{CrateStoreDyn, Untracked};
@@ -774,7 +775,9 @@ bidirectional_lang_item_map! {
     FutureOutput,
     Iterator,
     Metadata,
+    MetaSized,
     Option,
+    PointeeSized,
     PointeeTrait,
     Poll,
     Sized,
@@ -1616,16 +1619,17 @@ impl<'tcx> TyCtxt<'tcx> {
         self.reserve_and_set_memory_dedup(alloc, salt)
     }
 
+    /// Traits added on all bounds by default, excluding `Sized` which is treated separately.
     pub fn default_traits(self) -> &'static [rustc_hir::LangItem] {
-        match self.sess.opts.unstable_opts.experimental_default_bounds {
-            true => &[
-                LangItem::Sized,
+        if self.sess.opts.unstable_opts.experimental_default_bounds {
+            &[
                 LangItem::DefaultTrait1,
                 LangItem::DefaultTrait2,
                 LangItem::DefaultTrait3,
                 LangItem::DefaultTrait4,
-            ],
-            false => &[LangItem::Sized],
+            ]
+        } else {
+            &[]
         }
     }
 
@@ -2538,17 +2542,17 @@ impl<'tcx> TyCtxt<'tcx> {
 // this type just holds a pointer to it, but it still effectively owns it. It
 // impls `Borrow` so that it can be looked up using the original
 // (non-arena-memory-owning) types.
-struct InternedInSet<'tcx, T: ?Sized>(&'tcx T);
+struct InternedInSet<'tcx, T: ?Sized + PointeeSized>(&'tcx T);
 
-impl<'tcx, T: 'tcx + ?Sized> Clone for InternedInSet<'tcx, T> {
+impl<'tcx, T: 'tcx + ?Sized + PointeeSized> Clone for InternedInSet<'tcx, T> {
     fn clone(&self) -> Self {
         InternedInSet(self.0)
     }
 }
 
-impl<'tcx, T: 'tcx + ?Sized> Copy for InternedInSet<'tcx, T> {}
+impl<'tcx, T: 'tcx + ?Sized + PointeeSized> Copy for InternedInSet<'tcx, T> {}
 
-impl<'tcx, T: 'tcx + ?Sized> IntoPointer for InternedInSet<'tcx, T> {
+impl<'tcx, T: 'tcx + ?Sized + PointeeSized> IntoPointer for InternedInSet<'tcx, T> {
     fn into_pointer(&self) -> *const () {
         self.0 as *const _ as *const ()
     }
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index 0402d098822..97408e31854 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -60,6 +60,7 @@ pub use rustc_type_ir::fast_reject::DeepRejectCtxt;
 )]
 use rustc_type_ir::inherent;
 pub use rustc_type_ir::relate::VarianceDiagInfo;
+pub use rustc_type_ir::solve::SizedTraitKind;
 pub use rustc_type_ir::*;
 #[allow(hidden_glob_reexports, unused_imports)]
 use rustc_type_ir::{InferCtxtLike, Interner};
diff --git a/compiler/rustc_middle/src/ty/print/pretty.rs b/compiler/rustc_middle/src/ty/print/pretty.rs
index 673a89a8134..c10277c75a7 100644
--- a/compiler/rustc_middle/src/ty/print/pretty.rs
+++ b/compiler/rustc_middle/src/ty/print/pretty.rs
@@ -1069,24 +1069,35 @@ pub trait PrettyPrinter<'tcx>: Printer<'tcx> + fmt::Write {
 
         let mut traits = FxIndexMap::default();
         let mut fn_traits = FxIndexMap::default();
+        let mut lifetimes = SmallVec::<[ty::Region<'tcx>; 1]>::new();
+
         let mut has_sized_bound = false;
         let mut has_negative_sized_bound = false;
-        let mut lifetimes = SmallVec::<[ty::Region<'tcx>; 1]>::new();
+        let mut has_meta_sized_bound = false;
 
         for (predicate, _) in bounds.iter_instantiated_copied(tcx, args) {
             let bound_predicate = predicate.kind();
 
             match bound_predicate.skip_binder() {
                 ty::ClauseKind::Trait(pred) => {
-                    // Don't print `+ Sized`, but rather `+ ?Sized` if absent.
-                    if tcx.is_lang_item(pred.def_id(), LangItem::Sized) {
-                        match pred.polarity {
+                    // With `feature(sized_hierarchy)`, don't print `?Sized` as an alias for
+                    // `MetaSized`, and skip sizedness bounds to be added at the end.
+                    match tcx.as_lang_item(pred.def_id()) {
+                        Some(LangItem::Sized) => match pred.polarity {
                             ty::PredicatePolarity::Positive => {
                                 has_sized_bound = true;
                                 continue;
                             }
                             ty::PredicatePolarity::Negative => has_negative_sized_bound = true,
+                        },
+                        Some(LangItem::MetaSized) => {
+                            has_meta_sized_bound = true;
+                            continue;
+                        }
+                        Some(LangItem::PointeeSized) => {
+                            bug!("`PointeeSized` is removed during lowering");
                         }
+                        _ => (),
                     }
 
                     self.insert_trait_and_projection(
@@ -1255,8 +1266,13 @@ pub trait PrettyPrinter<'tcx>: Printer<'tcx> + fmt::Write {
             })?;
         }
 
+        let using_sized_hierarchy = self.tcx().features().sized_hierarchy();
         let add_sized = has_sized_bound && (first || has_negative_sized_bound);
-        let add_maybe_sized = !has_sized_bound && !has_negative_sized_bound;
+        let add_maybe_sized =
+            has_meta_sized_bound && !has_negative_sized_bound && !using_sized_hierarchy;
+        // Set `has_pointee_sized_bound` if there were no `Sized` or `MetaSized` bounds.
+        let has_pointee_sized_bound =
+            !has_sized_bound && !has_meta_sized_bound && !has_negative_sized_bound;
         if add_sized || add_maybe_sized {
             if !first {
                 write!(self, " + ")?;
@@ -1265,6 +1281,16 @@ pub trait PrettyPrinter<'tcx>: Printer<'tcx> + fmt::Write {
                 write!(self, "?")?;
             }
             write!(self, "Sized")?;
+        } else if has_meta_sized_bound && using_sized_hierarchy {
+            if !first {
+                write!(self, " + ")?;
+            }
+            write!(self, "MetaSized")?;
+        } else if has_pointee_sized_bound && using_sized_hierarchy {
+            if !first {
+                write!(self, " + ")?;
+            }
+            write!(self, "PointeeSized")?;
         }
 
         if !with_forced_trimmed_paths() {
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index cbf545c01c5..58829f72a72 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -15,6 +15,7 @@ use rustc_hir::def_id::DefId;
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, extension};
 use rustc_span::{DUMMY_SP, Span, Symbol, sym};
 use rustc_type_ir::TyKind::*;
+use rustc_type_ir::solve::SizedTraitKind;
 use rustc_type_ir::walk::TypeWalker;
 use rustc_type_ir::{self as ir, BoundVar, CollectAndApply, DynKind, TypeVisitableExt, elaborate};
 use tracing::instrument;
@@ -1677,7 +1678,7 @@ impl<'tcx> Ty<'tcx> {
         let Some(pointee_ty) = self.builtin_deref(true) else {
             bug!("Type {self:?} is not a pointer or reference type")
         };
-        if pointee_ty.is_trivially_sized(tcx) {
+        if pointee_ty.has_trivial_sizedness(tcx, SizedTraitKind::Sized) {
             tcx.types.unit
         } else {
             match pointee_ty.ptr_metadata_ty_or_tail(tcx, |x| x) {
@@ -1778,17 +1779,17 @@ impl<'tcx> Ty<'tcx> {
         }
     }
 
-    /// Fast path helper for testing if a type is `Sized`.
+    /// Fast path helper for testing if a type is `Sized` or `MetaSized`.
     ///
-    /// Returning true means the type is known to implement `Sized`. Returning `false` means
-    /// nothing -- could be sized, might not be.
+    /// Returning true means the type is known to implement the sizedness trait. Returning `false`
+    /// means nothing -- could be sized, might not be.
     ///
     /// Note that we could never rely on the fact that a type such as `[_]` is trivially `!Sized`
     /// because we could be in a type environment with a bound such as `[_]: Copy`. A function with
     /// such a bound obviously never can be called, but that doesn't mean it shouldn't typecheck.
     /// This is why this method doesn't return `Option<bool>`.
     #[instrument(skip(tcx), level = "debug")]
-    pub fn is_trivially_sized(self, tcx: TyCtxt<'tcx>) -> bool {
+    pub fn has_trivial_sizedness(self, tcx: TyCtxt<'tcx>, sizedness: SizedTraitKind) -> bool {
         match self.kind() {
             ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
             | ty::Uint(_)
@@ -1811,13 +1812,20 @@ impl<'tcx> Ty<'tcx> {
             | ty::Error(_)
             | ty::Dynamic(_, _, ty::DynStar) => true,
 
-            ty::Str | ty::Slice(_) | ty::Dynamic(_, _, ty::Dyn) | ty::Foreign(..) => false,
+            ty::Str | ty::Slice(_) | ty::Dynamic(_, _, ty::Dyn) => match sizedness {
+                SizedTraitKind::Sized => false,
+                SizedTraitKind::MetaSized => true,
+            },
+
+            ty::Foreign(..) => match sizedness {
+                SizedTraitKind::Sized | SizedTraitKind::MetaSized => false,
+            },
 
-            ty::Tuple(tys) => tys.last().is_none_or(|ty| ty.is_trivially_sized(tcx)),
+            ty::Tuple(tys) => tys.last().is_none_or(|ty| ty.has_trivial_sizedness(tcx, sizedness)),
 
             ty::Adt(def, args) => def
-                .sized_constraint(tcx)
-                .is_none_or(|ty| ty.instantiate(tcx, args).is_trivially_sized(tcx)),
+                .sizedness_constraint(tcx, sizedness)
+                .is_none_or(|ty| ty.instantiate(tcx, args).has_trivial_sizedness(tcx, sizedness)),
 
             ty::Alias(..) | ty::Param(_) | ty::Placeholder(..) | ty::Bound(..) => false,
 
diff --git a/compiler/rustc_middle/src/ty/util.rs b/compiler/rustc_middle/src/ty/util.rs
index 461d92f8006..51f57e71ce9 100644
--- a/compiler/rustc_middle/src/ty/util.rs
+++ b/compiler/rustc_middle/src/ty/util.rs
@@ -16,6 +16,7 @@ use rustc_index::bit_set::GrowableBitSet;
 use rustc_macros::{HashStable, TyDecodable, TyEncodable, extension};
 use rustc_session::Limit;
 use rustc_span::sym;
+use rustc_type_ir::solve::SizedTraitKind;
 use smallvec::{SmallVec, smallvec};
 use tracing::{debug, instrument};
 
@@ -1132,7 +1133,8 @@ impl<'tcx> Ty<'tcx> {
     /// strange rules like `<T as Foo<'static>>::Bar: Sized` that
     /// actually carry lifetime requirements.
     pub fn is_sized(self, tcx: TyCtxt<'tcx>, typing_env: ty::TypingEnv<'tcx>) -> bool {
-        self.is_trivially_sized(tcx) || tcx.is_sized_raw(typing_env.as_query_input(self))
+        self.has_trivial_sizedness(tcx, SizedTraitKind::Sized)
+            || tcx.is_sized_raw(typing_env.as_query_input(self))
     }
 
     /// Checks whether values of this type `T` implement the `Freeze`