Rollup merge of #94057 - lcnr:simplify_type-uwu, r=nikomatsakis

improve comments for `simplify_type`

Should now correctly describe what's going on. Experimented with checking the invariant for projections
but that ended up requiring fairly involved changes. I assume that it is not possible to get unsoundness here,
at least for now and I can pretty much guarantee that it's impossible to trigger it by accident.

r? `````@nikomatsakis````` cc #92721

7 files changed, 66 insertions, 60 deletions

diff --git a/compiler/rustc_metadata/src/rmeta/encoder.rs b/compiler/rustc_metadata/src/rmeta/encoder.rs
index c3e168c4727..06f73c1c916 100644
--- a/compiler/rustc_metadata/src/rmeta/encoder.rs
+++ b/compiler/rustc_metadata/src/rmeta/encoder.rs
@@ -26,7 +26,7 @@ use rustc_middle::mir::interpret;
 use rustc_middle::thir;
 use rustc_middle::traits::specialization_graph;
 use rustc_middle::ty::codec::TyEncoder;
-use rustc_middle::ty::fast_reject::{self, SimplifiedType, SimplifyParams};
+use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams};
 use rustc_middle::ty::query::Providers;
 use rustc_middle::ty::{self, SymbolName, Ty, TyCtxt};
 use rustc_serialize::{opaque, Encodable, Encoder};
@@ -2043,7 +2043,7 @@ impl<'tcx, 'v> ItemLikeVisitor<'v> for ImplsVisitor<'tcx> {
                     let simplified_self_ty = fast_reject::simplify_type(
                         self.tcx,
                         trait_ref.self_ty(),
-                        SimplifyParams::No,
+                        TreatParams::AsPlaceholders,
                     );
 
                     self.impls
diff --git a/compiler/rustc_middle/src/ty/fast_reject.rs b/compiler/rustc_middle/src/ty/fast_reject.rs
index 3c1ac66e2d1..c0dd4db2945 100644
--- a/compiler/rustc_middle/src/ty/fast_reject.rs
+++ b/compiler/rustc_middle/src/ty/fast_reject.rs
@@ -49,9 +49,14 @@ where
 }
 
 #[derive(PartialEq, Eq, Debug, Clone, Copy)]
-pub enum SimplifyParams {
-    Yes,
-    No,
+pub enum TreatParams {
+    /// Treat parameters as bound types in the given environment.
+    ///
+    /// For this to be correct the input has to be fully normalized
+    /// in its param env as it may otherwise cause us to ignore
+    /// potentially applying impls.
+    AsBoundTypes,
+    AsPlaceholders,
 }
 
 /// Tries to simplify a type by only returning the outermost injective¹ layer, if one exists.
@@ -59,26 +64,21 @@ pub enum SimplifyParams {
 /// The idea is to get something simple that we can use to quickly decide if two types could unify,
 /// for example during method lookup.
 ///
-/// A special case here are parameters and projections. Projections can be normalized to
-/// a different type, meaning that `<T as Trait>::Assoc` and `u8` can be unified, even though
-/// their outermost layer is different while parameters like `T` of impls are later replaced
-/// with an inference variable, which then also allows unification with other types.
+/// A special case here are parameters and projections, which are only injective
+/// if they are treated as bound types.
 ///
-/// When using `SimplifyParams::Yes`, we still return a simplified type for params and projections²,
-/// the reasoning for this can be seen at the places doing this.
+/// For example when storing impls based on their simplified self type, we treat
+/// generic parameters as placeholders. We must not simplify them here,
+/// as they can unify with any other type.
 ///
+/// With projections we have to be even more careful, as even when treating them as bound types
+/// this is still only correct if they are fully normalized.
 ///
-/// ¹ meaning that if two outermost layers are different, then the whole types are also different.
-/// ² FIXME(@lcnr): this seems like it can actually end up being unsound with the way it's used during
-///   candidate selection. We do not consider non blanket impls for `<_ as Trait>::Assoc` even
-///   though `_` can be inferred to a concrete type later at which point a concrete impl
-///   could actually apply. After experimenting for about an hour I wasn't able to cause any issues
-///   this way so I am not going to change this until we actually find an issue as I am really
-///   interesting in getting an actual test for this.
-pub fn simplify_type(
-    tcx: TyCtxt<'_>,
-    ty: Ty<'_>,
-    can_simplify_params: SimplifyParams,
+/// ¹ meaning that if the outermost layers are different, then the whole types are also different.
+pub fn simplify_type<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    ty: Ty<'tcx>,
+    treat_params: TreatParams,
 ) -> Option<SimplifiedType> {
     match *ty.kind() {
         ty::Bool => Some(BoolSimplifiedType),
@@ -91,7 +91,7 @@ pub fn simplify_type(
         ty::Array(..) => Some(ArraySimplifiedType),
         ty::Slice(..) => Some(SliceSimplifiedType),
         ty::RawPtr(ptr) => Some(PtrSimplifiedType(ptr.mutbl)),
-        ty::Dynamic(ref trait_info, ..) => match trait_info.principal_def_id() {
+        ty::Dynamic(trait_info, ..) => match trait_info.principal_def_id() {
             Some(principal_def_id) if !tcx.trait_is_auto(principal_def_id) => {
                 Some(TraitSimplifiedType(principal_def_id))
             }
@@ -100,24 +100,21 @@ pub fn simplify_type(
         ty::Ref(_, _, mutbl) => Some(RefSimplifiedType(mutbl)),
         ty::FnDef(def_id, _) | ty::Closure(def_id, _) => Some(ClosureSimplifiedType(def_id)),
         ty::Generator(def_id, _, _) => Some(GeneratorSimplifiedType(def_id)),
-        ty::GeneratorWitness(ref tys) => {
-            Some(GeneratorWitnessSimplifiedType(tys.skip_binder().len()))
-        }
+        ty::GeneratorWitness(tys) => Some(GeneratorWitnessSimplifiedType(tys.skip_binder().len())),
         ty::Never => Some(NeverSimplifiedType),
-        ty::Tuple(ref tys) => Some(TupleSimplifiedType(tys.len())),
-        ty::FnPtr(ref f) => Some(FunctionSimplifiedType(f.skip_binder().inputs().len())),
-        ty::Projection(_) | ty::Param(_) => {
-            if can_simplify_params == SimplifyParams::Yes {
-                // In normalized types, projections don't unify with
-                // anything. when lazy normalization happens, this
-                // will change. It would still be nice to have a way
-                // to deal with known-not-to-unify-with-anything
-                // projections (e.g., the likes of <__S as Encoder>::Error).
+        ty::Tuple(tys) => Some(TupleSimplifiedType(tys.len())),
+        ty::FnPtr(f) => Some(FunctionSimplifiedType(f.skip_binder().inputs().len())),
+        ty::Param(_) | ty::Projection(_) => match treat_params {
+            // When treated as bound types, projections don't unify with
+            // anything as long as they are fully normalized.
+            //
+            // We will have to be careful with lazy normalization here.
+            TreatParams::AsBoundTypes => {
+                debug!("treating `{}` as a bound type", ty);
                 Some(ParameterSimplifiedType)
-            } else {
-                None
             }
-        }
+            TreatParams::AsPlaceholders => None,
+        },
         ty::Opaque(def_id, _) => Some(OpaqueSimplifiedType(def_id)),
         ty::Foreign(def_id) => Some(ForeignSimplifiedType(def_id)),
         ty::Placeholder(..) | ty::Bound(..) | ty::Infer(_) | ty::Error(_) => None,
diff --git a/compiler/rustc_middle/src/ty/trait_def.rs b/compiler/rustc_middle/src/ty/trait_def.rs
index 6100eb48a18..8ebeca50c41 100644
--- a/compiler/rustc_middle/src/ty/trait_def.rs
+++ b/compiler/rustc_middle/src/ty/trait_def.rs
@@ -1,5 +1,5 @@
 use crate::traits::specialization_graph;
-use crate::ty::fast_reject::{self, SimplifiedType, SimplifyParams};
+use crate::ty::fast_reject::{self, SimplifiedType, TreatParams};
 use crate::ty::fold::TypeFoldable;
 use crate::ty::{Ident, Ty, TyCtxt};
 use rustc_hir as hir;
@@ -150,7 +150,7 @@ impl<'tcx> TyCtxt<'tcx> {
         self_ty: Ty<'tcx>,
     ) -> impl Iterator<Item = DefId> + 'tcx {
         let impls = self.trait_impls_of(def_id);
-        if let Some(simp) = fast_reject::simplify_type(self, self_ty, SimplifyParams::No) {
+        if let Some(simp) = fast_reject::simplify_type(self, self_ty, TreatParams::AsPlaceholders) {
             if let Some(impls) = impls.non_blanket_impls.get(&simp) {
                 return impls.iter().copied();
             }
@@ -180,14 +180,14 @@ impl<'tcx> TyCtxt<'tcx> {
             }
         }
 
-        // Note that we're using `SimplifyParams::Yes` to query `non_blanket_impls` while using
-        // `SimplifyParams::No` while actually adding them.
+        // Note that we're using `TreatParams::AsBoundTypes` to query `non_blanket_impls` while using
+        // `TreatParams::AsPlaceholders` while actually adding them.
         //
         // This way, when searching for some impl for `T: Trait`, we do not look at any impls
         // whose outer level is not a parameter or projection. Especially for things like
         // `T: Clone` this is incredibly useful as we would otherwise look at all the impls
         // of `Clone` for `Option<T>`, `Vec<T>`, `ConcreteType` and so on.
-        if let Some(simp) = fast_reject::simplify_type(self, self_ty, SimplifyParams::Yes) {
+        if let Some(simp) = fast_reject::simplify_type(self, self_ty, TreatParams::AsBoundTypes) {
             if let Some(impls) = impls.non_blanket_impls.get(&simp) {
                 for &impl_def_id in impls {
                     if let result @ Some(_) = f(impl_def_id) {
@@ -247,7 +247,7 @@ pub(super) fn trait_impls_of_provider(tcx: TyCtxt<'_>, trait_id: DefId) -> Trait
         }
 
         if let Some(simplified_self_ty) =
-            fast_reject::simplify_type(tcx, impl_self_ty, SimplifyParams::No)
+            fast_reject::simplify_type(tcx, impl_self_ty, TreatParams::AsPlaceholders)
         {
             impls.non_blanket_impls.entry(simplified_self_ty).or_default().push(impl_def_id);
         } else {
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 018d1eefef7..63efa951f96 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -20,7 +20,7 @@ use rustc_hir::CRATE_HIR_ID;
 use rustc_infer::infer::TyCtxtInferExt;
 use rustc_infer::traits::TraitEngine;
 use rustc_middle::traits::specialization_graph::OverlapMode;
-use rustc_middle::ty::fast_reject::{self, SimplifyParams};
+use rustc_middle::ty::fast_reject::{self, TreatParams};
 use rustc_middle::ty::fold::TypeFoldable;
 use rustc_middle::ty::subst::Subst;
 use rustc_middle::ty::{self, Ty, TyCtxt};
@@ -87,8 +87,8 @@ where
         impl2_ref.iter().flat_map(|tref| tref.substs.types()),
     )
     .any(|(ty1, ty2)| {
-        let t1 = fast_reject::simplify_type(tcx, ty1, SimplifyParams::No);
-        let t2 = fast_reject::simplify_type(tcx, ty2, SimplifyParams::No);
+        let t1 = fast_reject::simplify_type(tcx, ty1, TreatParams::AsPlaceholders);
+        let t2 = fast_reject::simplify_type(tcx, ty2, TreatParams::AsPlaceholders);
 
         if let (Some(t1), Some(t2)) = (t1, t2) {
             // Simplified successfully
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 092ef5f11e9..8af4606db85 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -36,7 +36,7 @@ use rustc_infer::infer::LateBoundRegionConversionTime;
 use rustc_middle::dep_graph::{DepKind, DepNodeIndex};
 use rustc_middle::mir::interpret::ErrorHandled;
 use rustc_middle::thir::abstract_const::NotConstEvaluatable;
-use rustc_middle::ty::fast_reject::{self, SimplifyParams};
+use rustc_middle::ty::fast_reject::{self, TreatParams};
 use rustc_middle::ty::print::with_no_trimmed_paths;
 use rustc_middle::ty::relate::TypeRelation;
 use rustc_middle::ty::subst::{GenericArgKind, Subst, SubstsRef};
@@ -2176,8 +2176,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
     fn fast_reject_trait_refs(
         &mut self,
-        obligation: &TraitObligation<'_>,
-        impl_trait_ref: &ty::TraitRef<'_>,
+        obligation: &TraitObligation<'tcx>,
+        impl_trait_ref: &ty::TraitRef<'tcx>,
     ) -> bool {
         // We can avoid creating type variables and doing the full
         // substitution if we find that any of the input types, when
@@ -2193,10 +2193,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         let simplified_obligation_ty = fast_reject::simplify_type(
                             self.tcx(),
                             obligation_ty,
-                            SimplifyParams::Yes,
+                            TreatParams::AsBoundTypes,
+                        );
+                        let simplified_impl_ty = fast_reject::simplify_type(
+                            self.tcx(),
+                            impl_ty,
+                            TreatParams::AsPlaceholders,
                         );
-                        let simplified_impl_ty =
-                            fast_reject::simplify_type(self.tcx(), impl_ty, SimplifyParams::No);
 
                         simplified_obligation_ty.is_some()
                             && simplified_impl_ty.is_some()
diff --git a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
index e31a9b200e8..8b23dcfe380 100644
--- a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
+++ b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
@@ -2,7 +2,7 @@ use super::OverlapError;
 
 use crate::traits;
 use rustc_hir::def_id::DefId;
-use rustc_middle::ty::fast_reject::{self, SimplifiedType, SimplifyParams};
+use rustc_middle::ty::fast_reject::{self, SimplifiedType, TreatParams};
 use rustc_middle::ty::print::with_no_trimmed_paths;
 use rustc_middle::ty::{self, TyCtxt, TypeFoldable};
 
@@ -49,7 +49,9 @@ impl ChildrenExt<'_> for Children {
     /// Insert an impl into this set of children without comparing to any existing impls.
     fn insert_blindly(&mut self, tcx: TyCtxt<'_>, impl_def_id: DefId) {
         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
-        if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), SimplifyParams::No) {
+        if let Some(st) =
+            fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsPlaceholders)
+        {
             debug!("insert_blindly: impl_def_id={:?} st={:?}", impl_def_id, st);
             self.non_blanket_impls.entry(st).or_default().push(impl_def_id)
         } else {
@@ -64,7 +66,9 @@ impl ChildrenExt<'_> for Children {
     fn remove_existing(&mut self, tcx: TyCtxt<'_>, impl_def_id: DefId) {
         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
         let vec: &mut Vec<DefId>;
-        if let Some(st) = fast_reject::simplify_type(tcx, trait_ref.self_ty(), SimplifyParams::No) {
+        if let Some(st) =
+            fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsPlaceholders)
+        {
             debug!("remove_existing: impl_def_id={:?} st={:?}", impl_def_id, st);
             vec = self.non_blanket_impls.get_mut(&st).unwrap();
         } else {
@@ -312,7 +316,8 @@ impl GraphExt for Graph {
 
         let mut parent = trait_def_id;
         let mut last_lint = None;
-        let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), SimplifyParams::No);
+        let simplified =
+            fast_reject::simplify_type(tcx, trait_ref.self_ty(), TreatParams::AsPlaceholders);
 
         // Descend the specialization tree, where `parent` is the current parent node.
         loop {
diff --git a/compiler/rustc_typeck/src/check/method/suggest.rs b/compiler/rustc_typeck/src/check/method/suggest.rs
index 1a345a303ca..0ae2dfa180b 100644
--- a/compiler/rustc_typeck/src/check/method/suggest.rs
+++ b/compiler/rustc_typeck/src/check/method/suggest.rs
@@ -12,7 +12,7 @@ use rustc_hir::lang_items::LangItem;
 use rustc_hir::{ExprKind, Node, QPath};
 use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
 use rustc_middle::traits::util::supertraits;
-use rustc_middle::ty::fast_reject::{simplify_type, SimplifyParams};
+use rustc_middle::ty::fast_reject::{simplify_type, TreatParams};
 use rustc_middle::ty::print::with_crate_prefix;
 use rustc_middle::ty::ToPolyTraitRef;
 use rustc_middle::ty::{self, DefIdTree, ToPredicate, Ty, TyCtxt, TypeFoldable};
@@ -1777,7 +1777,8 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 // FIXME: Even though negative bounds are not implemented, we could maybe handle
                 // cases where a positive bound implies a negative impl.
                 (candidates, Vec::new())
-            } else if let Some(simp_rcvr_ty) = simplify_type(self.tcx, rcvr_ty, SimplifyParams::Yes)
+            } else if let Some(simp_rcvr_ty) =
+                simplify_type(self.tcx, rcvr_ty, TreatParams::AsBoundTypes)
             {
                 let mut potential_candidates = Vec::new();
                 let mut explicitly_negative = Vec::new();
@@ -1792,7 +1793,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                         .any(|imp_did| {
                             let imp = self.tcx.impl_trait_ref(imp_did).unwrap();
                             let imp_simp =
-                                simplify_type(self.tcx, imp.self_ty(), SimplifyParams::Yes);
+                                simplify_type(self.tcx, imp.self_ty(), TreatParams::AsBoundTypes);
                             imp_simp.map_or(false, |s| s == simp_rcvr_ty)
                         })
                     {