trait_sel: `{Meta,Pointee}Sized` on `Sized` types

Introduce the `MetaSized` and `PointeeSized` traits as supertraits of
`Sized` and initially implement it on everything that currently
implements `Sized` to isolate any changes that simply adding the
traits introduces.

15 files changed, 253 insertions, 1 deletions

diff --git a/compiler/rustc_feature/src/unstable.rs b/compiler/rustc_feature/src/unstable.rs
index bd6ea850147..5e42b919f9d 100644
--- a/compiler/rustc_feature/src/unstable.rs
+++ b/compiler/rustc_feature/src/unstable.rs
@@ -237,6 +237,8 @@ declare_features! (
     (internal, profiler_runtime, "1.18.0", None),
     /// Allows using `rustc_*` attributes (RFC 572).
     (internal, rustc_attrs, "1.0.0", None),
+    /// Introduces a hierarchy of `Sized` traits (RFC 3729).
+    (unstable, sized_hierarchy, "CURRENT_RUSTC_VERSION", None),
     /// Allows using the `#[stable]` and `#[unstable]` attributes.
     (internal, staged_api, "1.0.0", None),
     /// Added for testing unstable lints; perma-unstable.
diff --git a/compiler/rustc_hir/src/lang_items.rs b/compiler/rustc_hir/src/lang_items.rs
index 21d36ed54cd..3a08e5ae336 100644
--- a/compiler/rustc_hir/src/lang_items.rs
+++ b/compiler/rustc_hir/src/lang_items.rs
@@ -165,6 +165,8 @@ pub fn extract(attrs: &[impl AttributeExt]) -> Option<(Symbol, Span)> {
 language_item_table! {
 //  Variant name,            Name,                     Getter method name,         Target                  Generic requirements;
     Sized,                   sym::sized,               sized_trait,                Target::Trait,          GenericRequirement::Exact(0);
+    MetaSized,               sym::meta_sized,          meta_sized_trait,           Target::Trait,          GenericRequirement::Exact(0);
+    PointeeSized,            sym::pointee_sized,       pointee_sized_trait,        Target::Trait,          GenericRequirement::Exact(0);
     Unsize,                  sym::unsize,              unsize_trait,               Target::Trait,          GenericRequirement::Minimum(1);
     /// Trait injected by `#[derive(PartialEq)]`, (i.e. "Partial EQ").
     StructuralPeq,           sym::structural_peq,      structural_peq_trait,       Target::Trait,          GenericRequirement::None;
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index fe4dd8d080b..6565d09936f 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -774,7 +774,9 @@ bidirectional_lang_item_map! {
     FutureOutput,
     Iterator,
     Metadata,
+    MetaSized,
     Option,
+    PointeeSized,
     PointeeTrait,
     Poll,
     Sized,
diff --git a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
index 0c267feefbe..434e2a818bd 100644
--- a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
@@ -212,6 +212,24 @@ where
         goal: Goal<I, Self>,
     ) -> Result<Candidate<I>, NoSolution>;
 
+    /// A type is `MetaSized` if its tail component is `MetaSized`.
+    ///
+    /// These components are given by built-in rules from
+    /// [`structural_traits::instantiate_constituent_tys_for_sized_trait`].
+    fn consider_builtin_meta_sized_candidate(
+        ecx: &mut EvalCtxt<'_, D>,
+        goal: Goal<I, Self>,
+    ) -> Result<Candidate<I>, NoSolution>;
+
+    /// A type is `PointeeSized` if its tail component is `PointeeSized`.
+    ///
+    /// These components are given by built-in rules from
+    /// [`structural_traits::instantiate_constituent_tys_for_sized_trait`].
+    fn consider_builtin_pointee_sized_candidate(
+        ecx: &mut EvalCtxt<'_, D>,
+        goal: Goal<I, Self>,
+    ) -> Result<Candidate<I>, NoSolution>;
+
     /// A type is `Copy` or `Clone` if its components are `Copy` or `Clone`.
     ///
     /// These components are given by built-in rules from
@@ -467,6 +485,12 @@ where
         } else {
             match cx.as_lang_item(trait_def_id) {
                 Some(TraitSolverLangItem::Sized) => G::consider_builtin_sized_candidate(self, goal),
+                Some(TraitSolverLangItem::MetaSized) => {
+                    G::consider_builtin_meta_sized_candidate(self, goal)
+                }
+                Some(TraitSolverLangItem::PointeeSized) => {
+                    G::consider_builtin_pointee_sized_candidate(self, goal)
+                }
                 Some(TraitSolverLangItem::Copy | TraitSolverLangItem::Clone) => {
                     G::consider_builtin_copy_clone_candidate(self, goal)
                 }
diff --git a/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs b/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs
index 8413c2abbb9..dda00a0a2c5 100644
--- a/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs
@@ -205,6 +205,20 @@ where
         unreachable!("Sized is never const")
     }
 
+    fn consider_builtin_meta_sized_candidate(
+        _ecx: &mut EvalCtxt<'_, D>,
+        _goal: Goal<I, Self>,
+    ) -> Result<Candidate<I>, NoSolution> {
+        unreachable!("MetaSized is never const")
+    }
+
+    fn consider_builtin_pointee_sized_candidate(
+        _ecx: &mut EvalCtxt<'_, D>,
+        _goal: Goal<I, Self>,
+    ) -> Result<Candidate<I>, NoSolution> {
+        unreachable!("PointeeSized is never const")
+    }
+
     fn consider_builtin_copy_clone_candidate(
         _ecx: &mut EvalCtxt<'_, D>,
         _goal: Goal<I, Self>,
diff --git a/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs
index 2fddc0044cb..42aeb170d6b 100644
--- a/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs
@@ -420,6 +420,20 @@ where
         panic!("`Sized` does not have an associated type: {:?}", goal);
     }
 
+    fn consider_builtin_meta_sized_candidate(
+        _ecx: &mut EvalCtxt<'_, D>,
+        goal: Goal<I, Self>,
+    ) -> Result<Candidate<I>, NoSolution> {
+        panic!("`MetaSized` does not have an associated type: {:?}", goal);
+    }
+
+    fn consider_builtin_pointee_sized_candidate(
+        _ecx: &mut EvalCtxt<'_, D>,
+        goal: Goal<I, Self>,
+    ) -> Result<Candidate<I>, NoSolution> {
+        panic!("`PointeeSized` does not have an associated type: {:?}", goal);
+    }
+
     fn consider_builtin_copy_clone_candidate(
         _ecx: &mut EvalCtxt<'_, D>,
         goal: Goal<I, Self>,
diff --git a/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs
index 110c67a8e21..50a7647be62 100644
--- a/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs
@@ -260,6 +260,36 @@ where
         )
     }
 
+    fn consider_builtin_meta_sized_candidate(
+        ecx: &mut EvalCtxt<'_, D>,
+        goal: Goal<I, Self>,
+    ) -> Result<Candidate<I>, NoSolution> {
+        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
+            return Err(NoSolution);
+        }
+
+        ecx.probe_and_evaluate_goal_for_constituent_tys(
+            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
+            goal,
+            structural_traits::instantiate_constituent_tys_for_sized_trait,
+        )
+    }
+
+    fn consider_builtin_pointee_sized_candidate(
+        ecx: &mut EvalCtxt<'_, D>,
+        goal: Goal<I, Self>,
+    ) -> Result<Candidate<I>, NoSolution> {
+        if goal.predicate.polarity != ty::PredicatePolarity::Positive {
+            return Err(NoSolution);
+        }
+
+        ecx.probe_and_evaluate_goal_for_constituent_tys(
+            CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
+            goal,
+            structural_traits::instantiate_constituent_tys_for_sized_trait,
+        )
+    }
+
     fn consider_builtin_copy_clone_candidate(
         ecx: &mut EvalCtxt<'_, D>,
         goal: Goal<I, Self>,
diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs
index cb9ccf4cc3f..baadff16120 100644
--- a/compiler/rustc_span/src/symbol.rs
+++ b/compiler/rustc_span/src/symbol.rs
@@ -1355,6 +1355,7 @@ symbols! {
         memtag,
         message,
         meta,
+        meta_sized,
         metadata_type,
         min_const_fn,
         min_const_generics,
@@ -1613,6 +1614,7 @@ symbols! {
         plugin_registrar,
         plugins,
         pointee,
+        pointee_sized,
         pointee_trait,
         pointer,
         pointer_like,
@@ -2016,6 +2018,7 @@ symbols! {
         size_of,
         size_of_val,
         sized,
+        sized_hierarchy,
         skip,
         slice,
         slice_from_raw_parts,
diff --git a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
index 97ecf9702e6..93ffea3b031 100644
--- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs
@@ -89,6 +89,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 Some(LangItem::Sized) => {
                     self.assemble_builtin_sized_candidate(obligation, &mut candidates);
                 }
+                Some(LangItem::MetaSized) => {
+                    self.assemble_builtin_sized_candidate(obligation, &mut candidates);
+                }
+                Some(LangItem::PointeeSized) => {
+                    self.assemble_builtin_sized_candidate(obligation, &mut candidates);
+                }
                 Some(LangItem::Unsize) => {
                     self.assemble_candidates_for_unsizing(obligation, &mut candidates);
                 }
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index 786afd7cf48..93d3e3ba2a8 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -252,6 +252,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             let trait_def = obligation.predicate.def_id();
             let conditions = match tcx.as_lang_item(trait_def) {
                 Some(LangItem::Sized) => self.sized_conditions(obligation),
+                Some(LangItem::MetaSized) => self.sized_conditions(obligation),
+                Some(LangItem::PointeeSized) => self.sized_conditions(obligation),
                 Some(LangItem::Copy | LangItem::Clone) => self.copy_clone_conditions(obligation),
                 Some(LangItem::FusedIterator) => self.fused_iterator_conditions(obligation),
                 other => bug!("unexpected builtin trait {trait_def:?} ({other:?})"),
diff --git a/compiler/rustc_type_ir/src/lang_items.rs b/compiler/rustc_type_ir/src/lang_items.rs
index 699dd82fb22..3ee6e07b7a5 100644
--- a/compiler/rustc_type_ir/src/lang_items.rs
+++ b/compiler/rustc_type_ir/src/lang_items.rs
@@ -30,7 +30,9 @@ pub enum TraitSolverLangItem {
     FutureOutput,
     Iterator,
     Metadata,
+    MetaSized,
     Option,
+    PointeeSized,
     PointeeTrait,
     Poll,
     Sized,
diff --git a/library/core/src/marker.rs b/library/core/src/marker.rs
index 9991b76cd0a..d7cf8955f26 100644
--- a/library/core/src/marker.rs
+++ b/library/core/src/marker.rs
@@ -151,11 +151,48 @@ unsafe impl<T: Sync + ?Sized> Send for &T {}
 #[rustc_specialization_trait]
 #[rustc_deny_explicit_impl]
 #[rustc_do_not_implement_via_object]
+// `Sized` being coinductive, despite having supertraits, is okay as there are no user-written impls,
+// and we know that the supertraits are always implemented if the subtrait is just by looking at
+// the builtin impls.
 #[rustc_coinductive]
-pub trait Sized {
+pub trait Sized: MetaSized {
     // Empty.
 }
 
+/// Types with a size that can be determined from pointer metadata.
+#[unstable(feature = "sized_hierarchy", issue = "none")]
+#[lang = "meta_sized"]
+#[diagnostic::on_unimplemented(
+    message = "the size for values of type `{Self}` cannot be known",
+    label = "doesn't have a known size"
+)]
+#[fundamental]
+#[rustc_specialization_trait]
+#[rustc_deny_explicit_impl]
+#[rustc_do_not_implement_via_object]
+// `MetaSized` being coinductive, despite having supertraits, is okay for the same reasons as
+// `Sized` above.
+#[rustc_coinductive]
+pub trait MetaSized: PointeeSized {
+    // Empty
+}
+
+/// Types that may or may not have a size.
+#[unstable(feature = "sized_hierarchy", issue = "none")]
+#[lang = "pointee_sized"]
+#[diagnostic::on_unimplemented(
+    message = "values of type `{Self}` may or may not have a size",
+    label = "may or may not have a known size"
+)]
+#[fundamental]
+#[rustc_specialization_trait]
+#[rustc_deny_explicit_impl]
+#[rustc_do_not_implement_via_object]
+#[rustc_coinductive]
+pub trait PointeeSized {
+    // Empty
+}
+
 /// Types that can be "unsized" to a dynamically-sized type.
 ///
 /// For example, the sized array type `[i8; 2]` implements `Unsize<[i8]>` and
diff --git a/tests/ui/attributes/dump-preds.stderr b/tests/ui/attributes/dump-preds.stderr
index bdfcbed71e9..fe662dd48f4 100644
--- a/tests/ui/attributes/dump-preds.stderr
+++ b/tests/ui/attributes/dump-preds.stderr
@@ -34,6 +34,7 @@ LL |     type Assoc<P: Eq>: std::ops::Deref<Target = ()>
    = note: Binder { value: ProjectionPredicate(AliasTerm { args: [Alias(Projection, AliasTy { args: [Self/#0, T/#1, P/#2], def_id: DefId(..), .. })], def_id: DefId(..), .. }, Term::Ty(())), bound_vars: [] }
    = note: Binder { value: TraitPredicate(<<Self as Trait<T>>::Assoc<P> as std::ops::Deref>, polarity:Positive), bound_vars: [] }
    = note: Binder { value: TraitPredicate(<<Self as Trait<T>>::Assoc<P> as std::marker::Sized>, polarity:Positive), bound_vars: [] }
+   = note: Binder { value: TraitPredicate(<<Self as Trait<T>>::Assoc<P> as std::marker::MetaSized>, polarity:Positive), bound_vars: [] }
 
 error: aborting due to 3 previous errors
 
diff --git a/tests/ui/feature-gates/feature-gate-sized-hierarchy.rs b/tests/ui/feature-gates/feature-gate-sized-hierarchy.rs
new file mode 100644
index 00000000000..bc81a7e6c38
--- /dev/null
+++ b/tests/ui/feature-gates/feature-gate-sized-hierarchy.rs
@@ -0,0 +1,32 @@
+#![feature(extern_types)]
+#![feature(sized_hierarchy)]
+
+use std::marker::{MetaSized, PointeeSized};
+
+fn needs_pointeesized<T: ?Sized + PointeeSized>() {}
+fn needs_metasized<T: ?Sized + MetaSized>() {}
+fn needs_sized<T: Sized>() {}
+
+fn main() {
+    needs_pointeesized::<u8>();
+    needs_metasized::<u8>();
+    needs_sized::<u8>();
+
+    needs_pointeesized::<str>();
+//~^ ERROR values of type `str` may or may not have a size
+    needs_metasized::<str>();
+//~^ ERROR the size for values of type `str` cannot be known
+    needs_sized::<str>();
+//~^ ERROR the size for values of type `str` cannot be known at compilation time
+
+    extern "C" {
+        type Foo;
+    }
+
+    needs_pointeesized::<Foo>();
+//~^ ERROR values of type `main::Foo` may or may not have a size
+    needs_metasized::<Foo>();
+//~^ ERROR the size for values of type `main::Foo` cannot be known
+    needs_sized::<Foo>();
+//~^ ERROR the size for values of type `main::Foo` cannot be known at compilation time
+}
diff --git a/tests/ui/feature-gates/feature-gate-sized-hierarchy.stderr b/tests/ui/feature-gates/feature-gate-sized-hierarchy.stderr
new file mode 100644
index 00000000000..64f544c5d8f
--- /dev/null
+++ b/tests/ui/feature-gates/feature-gate-sized-hierarchy.stderr
@@ -0,0 +1,81 @@
+error[E0277]: values of type `str` may or may not have a size
+  --> $DIR/feature-gate-sized-hierarchy.rs:15:26
+   |
+LL |     needs_pointeesized::<str>();
+   |                          ^^^ may or may not have a known size
+   |
+   = help: the trait `PointeeSized` is not implemented for `str`
+note: required by a bound in `needs_pointeesized`
+  --> $DIR/feature-gate-sized-hierarchy.rs:6:35
+   |
+LL | fn needs_pointeesized<T: ?Sized + PointeeSized>() {}
+   |                                   ^^^^^^^^^^^^ required by this bound in `needs_pointeesized`
+
+error[E0277]: the size for values of type `str` cannot be known
+  --> $DIR/feature-gate-sized-hierarchy.rs:17:23
+   |
+LL |     needs_metasized::<str>();
+   |                       ^^^ doesn't have a known size
+   |
+   = help: the trait `MetaSized` is not implemented for `str`
+note: required by a bound in `needs_metasized`
+  --> $DIR/feature-gate-sized-hierarchy.rs:7:32
+   |
+LL | fn needs_metasized<T: ?Sized + MetaSized>() {}
+   |                                ^^^^^^^^^ required by this bound in `needs_metasized`
+
+error[E0277]: the size for values of type `str` cannot be known at compilation time
+  --> $DIR/feature-gate-sized-hierarchy.rs:19:19
+   |
+LL |     needs_sized::<str>();
+   |                   ^^^ doesn't have a size known at compile-time
+   |
+   = help: the trait `Sized` is not implemented for `str`
+note: required by a bound in `needs_sized`
+  --> $DIR/feature-gate-sized-hierarchy.rs:8:19
+   |
+LL | fn needs_sized<T: Sized>() {}
+   |                   ^^^^^ required by this bound in `needs_sized`
+
+error[E0277]: values of type `main::Foo` may or may not have a size
+  --> $DIR/feature-gate-sized-hierarchy.rs:26:26
+   |
+LL |     needs_pointeesized::<Foo>();
+   |                          ^^^ may or may not have a known size
+   |
+   = help: the trait `PointeeSized` is not implemented for `main::Foo`
+note: required by a bound in `needs_pointeesized`
+  --> $DIR/feature-gate-sized-hierarchy.rs:6:35
+   |
+LL | fn needs_pointeesized<T: ?Sized + PointeeSized>() {}
+   |                                   ^^^^^^^^^^^^ required by this bound in `needs_pointeesized`
+
+error[E0277]: the size for values of type `main::Foo` cannot be known
+  --> $DIR/feature-gate-sized-hierarchy.rs:28:23
+   |
+LL |     needs_metasized::<Foo>();
+   |                       ^^^ doesn't have a known size
+   |
+   = help: the trait `MetaSized` is not implemented for `main::Foo`
+note: required by a bound in `needs_metasized`
+  --> $DIR/feature-gate-sized-hierarchy.rs:7:32
+   |
+LL | fn needs_metasized<T: ?Sized + MetaSized>() {}
+   |                                ^^^^^^^^^ required by this bound in `needs_metasized`
+
+error[E0277]: the size for values of type `main::Foo` cannot be known at compilation time
+  --> $DIR/feature-gate-sized-hierarchy.rs:30:19
+   |
+LL |     needs_sized::<Foo>();
+   |                   ^^^ doesn't have a size known at compile-time
+   |
+   = help: the trait `Sized` is not implemented for `main::Foo`
+note: required by a bound in `needs_sized`
+  --> $DIR/feature-gate-sized-hierarchy.rs:8:19
+   |
+LL | fn needs_sized<T: Sized>() {}
+   |                   ^^^^^ required by this bound in `needs_sized`
+
+error: aborting due to 6 previous errors
+
+For more information about this error, try `rustc --explain E0277`.