Make `find_similar_impl_candidates` a little fuzzier.

10 files changed, 147 insertions, 33 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 f80fad19528..806489e057c 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -40,6 +40,21 @@ use suggestions::InferCtxtExt as _;
 
 pub use rustc_infer::traits::error_reporting::*;
 
+// When outputting impl candidates, prefer showing those that are more similar.
+#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
+pub enum CandidateSimilarity {
+    Exact,
+    Simplified,
+    Fuzzy,
+    Unknown,
+}
+
+#[derive(Debug, Clone, Copy)]
+pub struct ImplCandidate<'tcx> {
+    pub trait_ref: ty::TraitRef<'tcx>,
+    pub similarity: CandidateSimilarity,
+}
+
 pub trait InferCtxtExt<'tcx> {
     fn report_fulfillment_errors(
         &self,
@@ -1143,18 +1158,18 @@ trait InferCtxtPrivExt<'hir, 'tcx> {
         error: &MismatchedProjectionTypes<'tcx>,
     );
 
-    fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool;
+    fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>, strip_references: StripReferences) -> bool;
 
     fn describe_generator(&self, body_id: hir::BodyId) -> Option<&'static str>;
 
     fn find_similar_impl_candidates(
         &self,
         trait_ref: ty::PolyTraitRef<'tcx>,
-    ) -> Vec<ty::TraitRef<'tcx>>;
+    ) -> Vec<ImplCandidate<'tcx>>;
 
     fn report_similar_impl_candidates(
         &self,
-        impl_candidates: Vec<ty::TraitRef<'tcx>>,
+        impl_candidates: Vec<ImplCandidate<'tcx>>,
         err: &mut DiagnosticBuilder<'_>,
     );
 
@@ -1446,7 +1461,7 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
         });
     }
 
-    fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
+    fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>, strip_references: StripReferences) -> 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> {
@@ -1478,6 +1493,23 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
             }
         }
 
+        let strip_reference = |mut t: Ty<'tcx>| -> Ty<'tcx> {
+            loop {
+                match t.kind() {
+                    ty::Ref(_, inner, _) | ty::RawPtr(ty::TypeAndMut { ty: inner, .. }) => {
+                        t = inner
+                    }
+                    _ => break t,
+                }
+            }
+        };
+
+        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,
@@ -1500,7 +1532,7 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
     fn find_similar_impl_candidates(
         &self,
         trait_ref: ty::PolyTraitRef<'tcx>,
-    ) -> Vec<ty::TraitRef<'tcx>> {
+    ) -> Vec<ImplCandidate<'tcx>> {
         // We simplify params and strip references here.
         //
         // This both removes a lot of unhelpful suggestions, e.g.
@@ -1518,32 +1550,67 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
         let all_impls = self.tcx.all_impls(trait_ref.def_id());
 
         match simp {
-            Some(simp) => all_impls
-                .filter_map(|def_id| {
-                    let imp = self.tcx.impl_trait_ref(def_id).unwrap();
-                    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 {
+            Some(simp) => {
+                all_impls
+                    .filter_map(|def_id| {
+                        if self.tcx.impl_polarity(def_id) == ty::ImplPolarity::Negative {
                             return None;
                         }
-                    }
-                    if self.tcx.impl_polarity(def_id) == ty::ImplPolarity::Negative {
-                        return None;
-                    }
-                    Some(imp)
-                })
-                .collect(),
+
+                        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 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,
+                            });
+                        }
+
+                        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)
+                    self.tcx.impl_trait_ref(def_id).map(|trait_ref| ImplCandidate {
+                        trait_ref,
+                        similarity: CandidateSimilarity::Unknown,
+                    })
                 })
                 .collect(),
         }
@@ -1551,7 +1618,7 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
 
     fn report_similar_impl_candidates(
         &self,
-        impl_candidates: Vec<ty::TraitRef<'tcx>>,
+        impl_candidates: Vec<ImplCandidate<'tcx>>,
         err: &mut DiagnosticBuilder<'_>,
     ) {
         if impl_candidates.is_empty() {
@@ -1575,13 +1642,24 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
         };
 
         // Sort impl candidates so that ordering is consistent for UI tests.
-        let mut normalized_impl_candidates =
-            impl_candidates.iter().copied().map(normalize).collect::<Vec<String>>();
-
-        // Sort before taking the `..end` range,
         // because the ordering of `impl_candidates` may not be deterministic:
         // https://github.com/rust-lang/rust/pull/57475#issuecomment-455519507
-        normalized_impl_candidates.sort();
+        //
+        // Prefer more similar candidates first, then sort lexicographically
+        // by their normalized string representation.
+        let mut normalized_impl_candidates_and_similarities = impl_candidates
+            .into_iter()
+            .map(|ImplCandidate { trait_ref, similarity }| {
+                let normalized = normalize(trait_ref);
+                (similarity, normalized)
+            })
+            .collect::<Vec<_>>();
+        normalized_impl_candidates_and_similarities.sort();
+
+        let normalized_impl_candidates = normalized_impl_candidates_and_similarities
+            .into_iter()
+            .map(|(_, normalized)| normalized)
+            .collect::<Vec<_>>();
 
         err.help(&format!(
             "the following implementations were found:{}{}",
@@ -1744,7 +1822,11 @@ impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
                     return;
                 }
 
-                let impl_candidates = self.find_similar_impl_candidates(trait_ref);
+                let impl_candidates = self
+                    .find_similar_impl_candidates(trait_ref)
+                    .into_iter()
+                    .map(|candidate| candidate.trait_ref)
+                    .collect();
                 let mut err = self.emit_inference_failure_err(
                     body_id,
                     span,
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 4e7a34d5951..979508e38ea 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,6 +4,7 @@ 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;
@@ -56,7 +57,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))
+                .all(|(u, v)| self.fuzzy_match_tys(u, v, StripReferences::No))
                 {
                     fuzzy_match_impls.push(def_id);
                 }
diff --git a/src/test/ui/associated-types/associated-types-path-2.stderr b/src/test/ui/associated-types/associated-types-path-2.stderr
index b3bb58f7814..f56631b12aa 100644
--- a/src/test/ui/associated-types/associated-types-path-2.stderr
+++ b/src/test/ui/associated-types/associated-types-path-2.stderr
@@ -15,6 +15,8 @@ error[E0277]: the trait bound `u32: Foo` is not satisfied
 LL |     f1(2u32, 4u32);
    |     ^^ the trait `Foo` is not implemented for `u32`
    |
+   = help: the following implementations were found:
+             <i32 as Foo>
 note: required by a bound in `f1`
   --> $DIR/associated-types-path-2.rs:13:14
    |
@@ -26,6 +28,9 @@ error[E0277]: the trait bound `u32: Foo` is not satisfied
    |
 LL |     f1(2u32, 4u32);
    |              ^^^^ the trait `Foo` is not implemented for `u32`
+   |
+   = help: the following implementations were found:
+             <i32 as Foo>
 
 error[E0277]: the trait bound `u32: Foo` is not satisfied
   --> $DIR/associated-types-path-2.rs:35:8
@@ -35,6 +40,8 @@ LL |     f1(2u32, 4i32);
    |     |
    |     required by a bound introduced by this call
    |
+   = help: the following implementations were found:
+             <i32 as Foo>
 note: required by a bound in `f1`
   --> $DIR/associated-types-path-2.rs:13:14
    |
@@ -46,6 +53,9 @@ error[E0277]: the trait bound `u32: Foo` is not satisfied
    |
 LL |     f1(2u32, 4i32);
    |              ^^^^ the trait `Foo` is not implemented for `u32`
+   |
+   = help: the following implementations were found:
+             <i32 as Foo>
 
 error[E0308]: mismatched types
   --> $DIR/associated-types-path-2.rs:41:18
diff --git a/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.stderr b/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.stderr
index 8ce70b1ac06..5755778fef2 100644
--- a/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.stderr
+++ b/src/test/ui/auto-traits/typeck-default-trait-impl-precedence.stderr
@@ -4,6 +4,8 @@ error[E0277]: the trait bound `u32: Signed` is not satisfied
 LL |     is_defaulted::<&'static u32>();
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Signed` is not implemented for `u32`
    |
+   = help: the following implementations were found:
+             <i32 as Signed>
 note: required because of the requirements on the impl of `Defaulted` for `&'static u32`
   --> $DIR/typeck-default-trait-impl-precedence.rs:10:19
    |
diff --git a/src/test/ui/const-generics/defaults/rp_impl_trait_fail.stderr b/src/test/ui/const-generics/defaults/rp_impl_trait_fail.stderr
index 8c8bfdc0e48..19813a491c9 100644
--- a/src/test/ui/const-generics/defaults/rp_impl_trait_fail.stderr
+++ b/src/test/ui/const-generics/defaults/rp_impl_trait_fail.stderr
@@ -15,6 +15,7 @@ LL | fn uwu<const N: u8>() -> impl Traitor<N> {
    |
    = help: the following implementations were found:
              <u32 as Traitor<N, 2_u8>>
+             <u64 as Traitor<1_u8, 2_u8>>
 
 error[E0277]: the trait bound `u64: Traitor<1_u8, 1_u8>` is not satisfied
   --> $DIR/rp_impl_trait_fail.rs:22:13
@@ -24,6 +25,7 @@ LL | fn owo() -> impl Traitor {
    |
    = help: the following implementations were found:
              <u64 as Traitor<1_u8, 2_u8>>
+             <u32 as Traitor<N, 2_u8>>
 
 error: aborting due to 3 previous errors
 
diff --git a/src/test/ui/did_you_mean/issue-39802-show-5-trait-impls.stderr b/src/test/ui/did_you_mean/issue-39802-show-5-trait-impls.stderr
index 5381a717dc3..dff98030191 100644
--- a/src/test/ui/did_you_mean/issue-39802-show-5-trait-impls.stderr
+++ b/src/test/ui/did_you_mean/issue-39802-show-5-trait-impls.stderr
@@ -11,7 +11,7 @@ LL |     Foo::<i32>::bar(&1i8);
              <i8 as Foo<u16>>
              <i8 as Foo<u32>>
              <i8 as Foo<u64>>
-             <i8 as Foo<u8>>
+           and 5 others
 
 error[E0277]: the trait bound `u8: Foo<i32>` is not satisfied
   --> $DIR/issue-39802-show-5-trait-impls.rs:25:21
@@ -26,6 +26,7 @@ LL |     Foo::<i32>::bar(&1u8);
              <u8 as Foo<u16>>
              <u8 as Foo<u32>>
              <u8 as Foo<u64>>
+           and 5 others
 
 error[E0277]: the trait bound `bool: Foo<i32>` is not satisfied
   --> $DIR/issue-39802-show-5-trait-impls.rs:26:21
diff --git a/src/test/ui/kindck/kindck-copy.stderr b/src/test/ui/kindck/kindck-copy.stderr
index 6977804708d..dcee740a556 100644
--- a/src/test/ui/kindck/kindck-copy.stderr
+++ b/src/test/ui/kindck/kindck-copy.stderr
@@ -6,6 +6,10 @@ LL |     assert_copy::<&'static mut isize>();
    |
    = help: the following implementations were found:
              <isize as Copy>
+             <i128 as Copy>
+             <i16 as Copy>
+             <i32 as Copy>
+           and 8 others
 note: required by a bound in `assert_copy`
   --> $DIR/kindck-copy.rs:5:18
    |
@@ -20,6 +24,10 @@ LL |     assert_copy::<&'a mut isize>();
    |
    = help: the following implementations were found:
              <isize as Copy>
+             <i128 as Copy>
+             <i16 as Copy>
+             <i32 as Copy>
+           and 8 others
 note: required by a bound in `assert_copy`
   --> $DIR/kindck-copy.rs:5:18
    |
diff --git a/src/test/ui/suggestions/issue-71394-no-from-impl.stderr b/src/test/ui/suggestions/issue-71394-no-from-impl.stderr
index 355f2038df8..79724377713 100644
--- a/src/test/ui/suggestions/issue-71394-no-from-impl.stderr
+++ b/src/test/ui/suggestions/issue-71394-no-from-impl.stderr
@@ -4,6 +4,9 @@ error[E0277]: the trait bound `&[i8]: From<&[u8]>` is not satisfied
 LL |     let _: &[i8] = data.into();
    |                         ^^^^ the trait `From<&[u8]>` is not implemented for `&[i8]`
    |
+   = help: the following implementations were found:
+             <[T; LANES] as From<Simd<T, LANES>>>
+             <[bool; LANES] as From<Mask<T, LANES>>>
    = note: required because of the requirements on the impl of `Into<&[i8]>` for `&[u8]`
 
 error: aborting due to previous error
diff --git a/src/test/ui/traits/issue-79458.stderr b/src/test/ui/traits/issue-79458.stderr
index 3e83db142e0..b9700128373 100644
--- a/src/test/ui/traits/issue-79458.stderr
+++ b/src/test/ui/traits/issue-79458.stderr
@@ -9,6 +9,8 @@ LL |     bar: &'a mut T
    |
    = help: the following implementations were found:
              <&T as Clone>
+             <*const T as Clone>
+             <*mut T as Clone>
    = note: `Clone` is implemented for `&T`, but not for `&mut T`
    = note: this error originates in the derive macro `Clone` (in Nightly builds, run with -Z macro-backtrace for more info)
 
diff --git a/src/test/ui/try-trait/bad-interconversion.stderr b/src/test/ui/try-trait/bad-interconversion.stderr
index 80c5e6f529c..6fc5f94f5f1 100644
--- a/src/test/ui/try-trait/bad-interconversion.stderr
+++ b/src/test/ui/try-trait/bad-interconversion.stderr
@@ -10,6 +10,9 @@ LL |     Ok(Err(123_i32)?)
    = help: the following implementations were found:
              <u8 as From<NonZeroU8>>
              <u8 as From<bool>>
+             <i128 as From<NonZeroI128>>
+             <i128 as From<bool>>
+           and 60 others
    = note: required because of the requirements on the impl of `FromResidual<Result<Infallible, i32>>` for `Result<u64, u8>`
 
 error[E0277]: the `?` operator can only be used on `Result`s, not `Option`s, in a function that returns `Result`