fuzzify `fuzzy_match_tys`

11 files changed, 68 insertions, 120 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
index 806489e057c..ac7140ca2b6 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -21,10 +21,9 @@ use rustc_hir::Item;
 use rustc_hir::Node;
 use rustc_middle::thir::abstract_const::NotConstEvaluatable;
 use rustc_middle::ty::error::ExpectedFound;
-use rustc_middle::ty::fast_reject::{self, SimplifyParams, StripReferences};
 use rustc_middle::ty::fold::TypeFolder;
 use rustc_middle::ty::{
-    self, AdtKind, SubtypePredicate, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable,
+    self, SubtypePredicate, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable,
 };
 use rustc_session::DiagnosticMessageId;
 use rustc_span::symbol::{kw, sym};
@@ -44,9 +43,7 @@ pub use rustc_infer::traits::error_reporting::*;
 #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
 pub enum CandidateSimilarity {
     Exact,
-    Simplified,
     Fuzzy,
-    Unknown,
 }
 
 #[derive(Debug, Clone, Copy)]
@@ -1158,7 +1155,7 @@ trait InferCtxtPrivExt<'hir, 'tcx> {
         error: &MismatchedProjectionTypes<'tcx>,
     );
 
-    fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>, strip_references: StripReferences) -> bool;
+    fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool;
 
     fn describe_generator(&self, body_id: hir::BodyId) -> Option<&'static str>;
 
@@ -1461,7 +1458,7 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
         });
     }
 
-    fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>, strip_references: StripReferences) -> bool {
+    fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
         /// returns the fuzzy category of a given type, or None
         /// if the type can be equated to any type.
         fn type_category(t: Ty<'_>) -> Option<u32> {
@@ -1481,19 +1478,15 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
                 ty::Param(..) => Some(12),
                 ty::Opaque(..) => Some(13),
                 ty::Never => Some(14),
-                ty::Adt(adt, ..) => match adt.adt_kind() {
-                    AdtKind::Struct => Some(15),
-                    AdtKind::Union => Some(16),
-                    AdtKind::Enum => Some(17),
-                },
-                ty::Generator(..) => Some(18),
-                ty::Foreign(..) => Some(19),
-                ty::GeneratorWitness(..) => Some(20),
+                ty::Adt(..) => Some(15),
+                ty::Generator(..) => Some(16),
+                ty::Foreign(..) => Some(17),
+                ty::GeneratorWitness(..) => Some(18),
                 ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error(_) => None,
             }
         }
 
-        let strip_reference = |mut t: Ty<'tcx>| -> Ty<'tcx> {
+        let strip_references = |mut t: Ty<'tcx>| -> Ty<'tcx> {
             loop {
                 match t.kind() {
                     ty::Ref(_, inner, _) | ty::RawPtr(ty::TypeAndMut { ty: inner, .. }) => {
@@ -1504,16 +1497,14 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
             }
         };
 
-        let (a, b) = if strip_references == StripReferences::Yes {
-            (strip_reference(a), strip_reference(b))
-        } else {
-            (a, b)
-        };
-
         match (type_category(a), type_category(b)) {
             (Some(cat_a), Some(cat_b)) => match (a.kind(), b.kind()) {
-                (&ty::Adt(def_a, _), &ty::Adt(def_b, _)) => def_a == def_b,
-                _ => cat_a == cat_b,
+                (ty::Adt(def_a, _), ty::Adt(def_b, _)) => def_a == def_b,
+                _ if cat_a == cat_b => true,
+                (ty::Ref(..), _) | (_, ty::Ref(..)) => {
+                    self.fuzzy_match_tys(strip_references(a), strip_references(b))
+                }
+                _ => false,
             },
             // infer and error can be equated to all types
             _ => true,
@@ -1533,87 +1524,33 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
         &self,
         trait_ref: ty::PolyTraitRef<'tcx>,
     ) -> Vec<ImplCandidate<'tcx>> {
-        // We simplify params and strip references here.
-        //
-        // This both removes a lot of unhelpful suggestions, e.g.
-        // when searching for `&Foo: Trait` it doesn't suggestion `impl Trait for &Bar`,
-        // while also suggesting impls for `&Foo` when we're looking for `Foo: Trait`.
-        //
-        // The second thing isn't necessarily always a good thing, but
-        // any other simple setup results in a far worse output, so 🤷
-        let simp = fast_reject::simplify_type(
-            self.tcx,
-            trait_ref.skip_binder().self_ty(),
-            SimplifyParams::Yes,
-            StripReferences::Yes,
-        );
-        let all_impls = self.tcx.all_impls(trait_ref.def_id());
-
-        match simp {
-            Some(simp) => {
-                all_impls
-                    .filter_map(|def_id| {
-                        if self.tcx.impl_polarity(def_id) == ty::ImplPolarity::Negative {
-                            return None;
-                        }
+        self.tcx
+            .all_impls(trait_ref.def_id())
+            .filter_map(|def_id| {
+                if self.tcx.impl_polarity(def_id) == ty::ImplPolarity::Negative {
+                    return None;
+                }
 
-                        let imp = self.tcx.impl_trait_ref(def_id).unwrap();
+                let imp = self.tcx.impl_trait_ref(def_id).unwrap();
 
-                        // Check for exact match.
-                        if trait_ref.skip_binder().self_ty() == imp.self_ty() {
-                            return Some(ImplCandidate {
-                                trait_ref: imp,
-                                similarity: CandidateSimilarity::Exact,
-                            });
-                        }
-
-                        // Check for match between simplified types.
-                        let imp_simp = fast_reject::simplify_type(
-                            self.tcx,
-                            imp.self_ty(),
-                            SimplifyParams::Yes,
-                            StripReferences::Yes,
-                        );
-                        if let Some(imp_simp) = imp_simp {
-                            if simp == imp_simp {
-                                return Some(ImplCandidate {
-                                    trait_ref: imp,
-                                    similarity: CandidateSimilarity::Simplified,
-                                });
-                            }
-                        }
+                // Check for exact match.
+                if trait_ref.skip_binder().self_ty() == imp.self_ty() {
+                    return Some(ImplCandidate {
+                        trait_ref: imp,
+                        similarity: CandidateSimilarity::Exact,
+                    });
+                }
 
-                        // Check for fuzzy match.
-                        // Pass `StripReferences::Yes` because although we do want to
-                        // be fuzzier than `simplify_type`, we don't want to be
-                        // *too* fuzzy.
-                        if self.fuzzy_match_tys(
-                            trait_ref.skip_binder().self_ty(),
-                            imp.self_ty(),
-                            StripReferences::Yes,
-                        ) {
-                            return Some(ImplCandidate {
-                                trait_ref: imp,
-                                similarity: CandidateSimilarity::Fuzzy,
-                            });
-                        }
+                if self.fuzzy_match_tys(trait_ref.skip_binder().self_ty(), imp.self_ty()) {
+                    return Some(ImplCandidate {
+                        trait_ref: imp,
+                        similarity: CandidateSimilarity::Fuzzy,
+                    });
+                }
 
-                        None
-                    })
-                    .collect()
-            }
-            None => all_impls
-                .filter_map(|def_id| {
-                    if self.tcx.impl_polarity(def_id) == ty::ImplPolarity::Negative {
-                        return None;
-                    }
-                    self.tcx.impl_trait_ref(def_id).map(|trait_ref| ImplCandidate {
-                        trait_ref,
-                        similarity: CandidateSimilarity::Unknown,
-                    })
-                })
-                .collect(),
-        }
+                None
+            })
+            .collect()
     }
 
     fn report_similar_impl_candidates(
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
index 979508e38ea..4e7a34d5951 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
@@ -4,7 +4,6 @@ use super::{
 use crate::infer::InferCtxt;
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
-use rustc_middle::ty::fast_reject::StripReferences;
 use rustc_middle::ty::subst::Subst;
 use rustc_middle::ty::{self, GenericParamDefKind};
 use rustc_span::symbol::sym;
@@ -57,7 +56,7 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                     trait_ref.substs.types().skip(1),
                     impl_trait_ref.substs.types().skip(1),
                 )
-                .all(|(u, v)| self.fuzzy_match_tys(u, v, StripReferences::No))
+                .all(|(u, v)| self.fuzzy_match_tys(u, v))
                 {
                     fuzzy_match_impls.push(def_id);
                 }
diff --git a/src/test/ui/associated-types/hr-associated-type-bound-object.stderr b/src/test/ui/associated-types/hr-associated-type-bound-object.stderr
index 354f5ae4597..6d19186bde4 100644
--- a/src/test/ui/associated-types/hr-associated-type-bound-object.stderr
+++ b/src/test/ui/associated-types/hr-associated-type-bound-object.stderr
@@ -4,8 +4,6 @@ error[E0277]: the trait bound `for<'b> <T as X<'b>>::U: Clone` is not satisfied
 LL | fn f<'a, T: X<'a> + ?Sized>(x: &<T as X<'a>>::U) {
    |             ^^^^^ the trait `for<'b> Clone` is not implemented for `<T as X<'b>>::U`
    |
-   = help: the following implementations were found:
-             <&T as Clone>
 note: required by a bound in `X`
   --> $DIR/hr-associated-type-bound-object.rs:3:33
    |
diff --git a/src/test/ui/block-result/issue-22645.stderr b/src/test/ui/block-result/issue-22645.stderr
index 397bdac6051..b869a70039c 100644
--- a/src/test/ui/block-result/issue-22645.stderr
+++ b/src/test/ui/block-result/issue-22645.stderr
@@ -4,8 +4,6 @@ error[E0277]: the trait bound `{integer}: Scalar` is not satisfied
 LL |   b + 3
    |     ^ the trait `Scalar` is not implemented for `{integer}`
    |
-   = help: the following implementations were found:
-             <f64 as Scalar>
 note: required because of the requirements on the impl of `Add<{integer}>` for `Bob`
   --> $DIR/issue-22645.rs:8:19
    |
diff --git a/src/test/ui/chalkify/type_inference.stderr b/src/test/ui/chalkify/type_inference.stderr
index 14d43c1474c..a05d8d6aa37 100644
--- a/src/test/ui/chalkify/type_inference.stderr
+++ b/src/test/ui/chalkify/type_inference.stderr
@@ -6,9 +6,6 @@ LL |     only_bar(x);
    |     |
    |     required by a bound introduced by this call
    |
-   = help: the following implementations were found:
-             <i32 as Bar>
-             <u32 as Bar>
 note: required by a bound in `only_bar`
   --> $DIR/type_inference.rs:12:16
    |
diff --git a/src/test/ui/chalkify/type_wf.stderr b/src/test/ui/chalkify/type_wf.stderr
index 57902efa201..d029eb2400b 100644
--- a/src/test/ui/chalkify/type_wf.stderr
+++ b/src/test/ui/chalkify/type_wf.stderr
@@ -4,9 +4,6 @@ error[E0277]: the trait bound `{float}: Foo` is not satisfied
 LL |     let s = S {
    |             ^ the trait `Foo` is not implemented for `{float}`
    |
-   = help: the following implementations were found:
-             <Option<T> as Foo>
-             <i32 as Foo>
 note: required by a bound in `S`
   --> $DIR/type_wf.rs:6:13
    |
diff --git a/src/test/ui/kindck/kindck-copy.stderr b/src/test/ui/kindck/kindck-copy.stderr
index dcee740a556..607db0d1129 100644
--- a/src/test/ui/kindck/kindck-copy.stderr
+++ b/src/test/ui/kindck/kindck-copy.stderr
@@ -5,11 +5,11 @@ LL |     assert_copy::<&'static mut isize>();
    |                   ^^^^^^^^^^^^^^^^^^ the trait `Copy` is not implemented for `&'static mut isize`
    |
    = help: the following implementations were found:
-             <isize as Copy>
+             <&T as Copy>
+             <*const T as Copy>
+             <*mut T as Copy>
              <i128 as Copy>
-             <i16 as Copy>
-             <i32 as Copy>
-           and 8 others
+           and 11 others
 note: required by a bound in `assert_copy`
   --> $DIR/kindck-copy.rs:5:18
    |
@@ -23,11 +23,11 @@ LL |     assert_copy::<&'a mut isize>();
    |                   ^^^^^^^^^^^^^ the trait `Copy` is not implemented for `&'a mut isize`
    |
    = help: the following implementations were found:
-             <isize as Copy>
+             <&T as Copy>
+             <*const T as Copy>
+             <*mut T as Copy>
              <i128 as Copy>
-             <i16 as Copy>
-             <i32 as Copy>
-           and 8 others
+           and 11 others
 note: required by a bound in `assert_copy`
   --> $DIR/kindck-copy.rs:5:18
    |
@@ -112,6 +112,10 @@ error[E0277]: the trait bound `&'a mut (dyn Dummy + Send + 'a): Copy` is not sat
 LL |     assert_copy::<&'a mut (dyn Dummy + Send)>();
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Copy` is not implemented for `&'a mut (dyn Dummy + Send + 'a)`
    |
+   = help: the following implementations were found:
+             <&T as Copy>
+             <*const T as Copy>
+             <*mut T as Copy>
 note: required by a bound in `assert_copy`
   --> $DIR/kindck-copy.rs:5:18
    |
diff --git a/src/test/ui/suggestions/mut-borrow-needed-by-trait.stderr b/src/test/ui/suggestions/mut-borrow-needed-by-trait.stderr
index d121932c842..6aaeafceb42 100644
--- a/src/test/ui/suggestions/mut-borrow-needed-by-trait.stderr
+++ b/src/test/ui/suggestions/mut-borrow-needed-by-trait.stderr
@@ -6,6 +6,12 @@ LL |     let fp = BufWriter::new(fp);
    |              |
    |              required by a bound introduced by this call
    |
+   = help: the following implementations were found:
+             <&'a UnixStream as std::io::Write>
+             <&ChildStdin as std::io::Write>
+             <&File as std::io::Write>
+             <&Sink as std::io::Write>
+           and 5 others
    = note: `std::io::Write` is implemented for `&mut dyn std::io::Write`, but not for `&dyn std::io::Write`
 note: required by a bound in `BufWriter::<W>::new`
   --> $SRC_DIR/std/src/io/buffered/bufwriter.rs:LL:COL
@@ -19,6 +25,12 @@ error[E0277]: the trait bound `&dyn std::io::Write: std::io::Write` is not satis
 LL |     let fp = BufWriter::new(fp);
    |              ^^^^^^^^^^^^^^^^^^ the trait `std::io::Write` is not implemented for `&dyn std::io::Write`
    |
+   = help: the following implementations were found:
+             <&'a UnixStream as std::io::Write>
+             <&ChildStdin as std::io::Write>
+             <&File as std::io::Write>
+             <&Sink as std::io::Write>
+           and 5 others
    = note: `std::io::Write` is implemented for `&mut dyn std::io::Write`, but not for `&dyn std::io::Write`
 note: required by a bound in `BufWriter`
   --> $SRC_DIR/std/src/io/buffered/bufwriter.rs:LL:COL
diff --git a/src/test/ui/traits/suggest-deferences/issue-62530.stderr b/src/test/ui/traits/suggest-deferences/issue-62530.stderr
index b77af7ddf47..299219431ef 100644
--- a/src/test/ui/traits/suggest-deferences/issue-62530.stderr
+++ b/src/test/ui/traits/suggest-deferences/issue-62530.stderr
@@ -8,6 +8,8 @@ LL |     takes_type_parameter(&string);  // Error
    |     |                    help: consider adding dereference here: `&*string`
    |     required by a bound introduced by this call
    |
+   = help: the following implementations were found:
+             <&str as SomeTrait>
 note: required by a bound in `takes_type_parameter`
   --> $DIR/issue-62530.rs:4:44
    |
diff --git a/src/test/ui/traits/suggest-deferences/multiple-0.stderr b/src/test/ui/traits/suggest-deferences/multiple-0.stderr
index bf9f85f1b45..c629b06ba26 100644
--- a/src/test/ui/traits/suggest-deferences/multiple-0.stderr
+++ b/src/test/ui/traits/suggest-deferences/multiple-0.stderr
@@ -8,6 +8,8 @@ LL |     foo(&baz);
    |     |   help: consider adding dereference here: `&***baz`
    |     required by a bound introduced by this call
    |
+   = help: the following implementations were found:
+             <&LDM as Happy>
 note: required by a bound in `foo`
   --> $DIR/multiple-0.rs:30:26
    |
diff --git a/src/test/ui/traits/suggest-deferences/multiple-1.stderr b/src/test/ui/traits/suggest-deferences/multiple-1.stderr
index 040fbb3e3e6..b18c297ed99 100644
--- a/src/test/ui/traits/suggest-deferences/multiple-1.stderr
+++ b/src/test/ui/traits/suggest-deferences/multiple-1.stderr
@@ -6,6 +6,8 @@ LL |     foo(&mut baz);
    |     |
    |     required by a bound introduced by this call
    |
+   = help: the following implementations were found:
+             <&mut LDM as Happy>
 note: required by a bound in `foo`
   --> $DIR/multiple-1.rs:45:26
    |