make generics work

fix compile error in doc example

3 files changed, 146 insertions, 49 deletions

diff --git a/clippy_lints/src/implied_bounds_in_impl.rs b/clippy_lints/src/implied_bounds_in_impl.rs
index c83153e5350..3f9f5daa6a4 100644
--- a/clippy_lints/src/implied_bounds_in_impl.rs
+++ b/clippy_lints/src/implied_bounds_in_impl.rs
@@ -1,9 +1,10 @@
 use clippy_utils::diagnostics::span_lint;
 use rustc_hir::def_id::LocalDefId;
 use rustc_hir::intravisit::FnKind;
-use rustc_hir::{Body, FnDecl, FnRetTy, GenericArgs, GenericBound, ItemKind, TraitBoundModifier, TyKind};
+use rustc_hir::{Body, FnDecl, FnRetTy, GenericArg, GenericBound, ItemKind, TraitBoundModifier, TyKind};
+use rustc_hir_analysis::hir_ty_to_ty;
 use rustc_lint::{LateContext, LateLintPass};
-use rustc_middle::ty::ClauseKind;
+use rustc_middle::ty::{self, ClauseKind, TyCtxt};
 use rustc_session::{declare_lint_pass, declare_tool_lint};
 use rustc_span::Span;
 
@@ -17,10 +18,11 @@ declare_clippy_lint! {
     /// Unnecessary complexity.
     ///
     /// ### Known problems
-    /// This lint currently does not work with generic traits (i.e. will not lint even if redundant).
+    /// This lint does not transitively look for implied bounds past the first supertrait.
     ///
     /// ### Example
     /// ```rust
+    /// # use std::ops::{Deref,DerefMut};
     /// fn f() -> impl Deref<Target = i32> + DerefMut<Target = i32> {
     /// //             ^^^^^^^^^^^^^^^^^^^ unnecessary bound, already implied by the `DerefMut` trait bound
     ///     Box::new(123)
@@ -28,6 +30,7 @@ declare_clippy_lint! {
     /// ```
     /// Use instead:
     /// ```rust
+    /// # use std::ops::{Deref,DerefMut};
     /// fn f() -> impl DerefMut<Target = i32> {
     ///     Box::new(123)
     /// }
@@ -39,6 +42,53 @@ declare_clippy_lint! {
 }
 declare_lint_pass!(ImpliedBoundsInImpl => [IMPLIED_BOUNDS_IN_IMPL]);
 
+/// This function tries to, for all type parameters in a supertype predicate `GenericTrait<U>`,
+/// check if the substituted type in the implied-by bound matches with what's subtituted in the
+/// implied type.
+///
+/// Consider this example function.
+/// ```rust,ignore
+/// trait GenericTrait<T> {}
+/// trait GenericSubTrait<T, U, V>: GenericTrait<U> {}
+///                                              ^ trait_predicate_args: [Self#0, U#2]
+/// impl GenericTrait<i32> for () {}
+/// impl GenericSubTrait<(), i32, ()> for () {}
+/// impl GenericSubTrait<(), [u8; 8], ()> for () {}
+///
+/// fn f() -> impl GenericTrait<i32> + GenericSubTrait<(), [u8; 8], ()> {
+///                             ^^^ implied_args       ^^^^^^^^^^^^^^^ implied_by_args
+///                                                                    (we are interested in `[u8; 8]` specifically, as that
+///                                                                     is what `U` in `GenericTrait<U>` is substituted with)
+///     ()
+/// }
+/// ```
+/// Here i32 != [u8; 8], so this will return false.
+fn is_same_generics(
+    tcx: TyCtxt<'_>,
+    trait_predicate_args: &[ty::GenericArg<'_>],
+    implied_by_args: &[GenericArg<'_>],
+    implied_args: &[GenericArg<'_>],
+) -> bool {
+    trait_predicate_args
+        .iter()
+        .enumerate()
+        .skip(1) // skip `Self` implicit arg
+        .all(|(arg_index, arg)| {
+            if let Some(ty) = arg.as_type()
+                && let &ty::Param(ty::ParamTy{ index, .. }) = ty.kind()
+                // Since `trait_predicate_args` and type params in traits start with `Self=0`
+                // and generic argument lists `GenericTrait<i32>` don't have `Self`,
+                // we need to subtract 1 from the index.
+                && let GenericArg::Type(ty_a) = implied_by_args[index as usize - 1]
+                && let GenericArg::Type(ty_b) = implied_args[arg_index - 1]
+            {
+                hir_ty_to_ty(tcx, ty_a) == hir_ty_to_ty(tcx, ty_b)
+            } else {
+                false
+            }
+        })
+}
+
 impl LateLintPass<'_> for ImpliedBoundsInImpl {
     fn check_fn(
         &mut self,
@@ -54,37 +104,52 @@ impl LateLintPass<'_> for ImpliedBoundsInImpl {
                 && let item = cx.tcx.hir().item(item_id)
                 && let ItemKind::OpaqueTy(opaque_ty) = item.kind
             {
-                // Get all `DefId`s of (implied) trait predicates in all the bounds.
+                // Very often there is only a single bound, e.g. `impl Deref<..>`, in which case
+                // we can avoid doing a bunch of stuff unnecessarily.
+                if opaque_ty.bounds.is_empty() {
+                    return;
+                }
+
+                // Get all the (implied) trait predicates in the bounds.
                 // For `impl Deref + DerefMut` this will contain [`Deref`].
                 // The implied `Deref` comes from `DerefMut` because `trait DerefMut: Deref {}`.
 
-                // N.B. Generic args on trait bounds are currently ignored and (G)ATs are fine to disregard,
-                // because they must be the same for all of its supertraits. Example:
+                // N.B. (G)ATs are fine to disregard, because they must be the same for all of its supertraits.
+                // Example:
                 // `impl Deref<Target = i32> + DerefMut<Target = u32>` is not allowed.
                 // `DerefMut::Target` needs to match `Deref::Target`
-                let implied_bounds = opaque_ty.bounds.iter().flat_map(|bound| {
+                let implied_bounds: Vec<_> = opaque_ty.bounds.iter().filter_map(|bound| {
                     if let GenericBound::Trait(poly_trait, TraitBoundModifier::None) = bound
                         && let [.., path]  = poly_trait.trait_ref.path.segments
                         && poly_trait.bound_generic_params.is_empty()
-                        && path.args.map_or(true, GenericArgs::is_empty)
                         && let Some(trait_def_id) = path.res.opt_def_id()
+                        && let predicates = cx.tcx.super_predicates_of(trait_def_id).predicates
+                        && !predicates.is_empty() // If the trait has no supertrait, there is nothing to add.
                     {
-                        cx.tcx.implied_predicates_of(trait_def_id).predicates
+                        Some((path.args.map_or([].as_slice(), |a| a.args), predicates))
                     } else {
-                        &[]
+                        None
                     }
-                }).collect::<Vec<_>>();
+                }).collect();
 
                 // Lint all bounds in the `impl Trait` type that are also in the `implied_bounds` vec.
+                // This involves some extra logic when generic arguments are present, since
+                // simply comparing trait `DefId`s won't be enough. We also need to compare the generics.
                 for bound in opaque_ty.bounds {
                     if let GenericBound::Trait(poly_trait, TraitBoundModifier::None) = bound
+                        && let [.., path] = poly_trait.trait_ref.path.segments
+                        && let implied_args = path.args.map_or([].as_slice(), |a| a.args)
                         && let Some(def_id) = poly_trait.trait_ref.path.res.opt_def_id()
-                        && implied_bounds.iter().any(|(clause, _)| {
-                            if let ClauseKind::Trait(tr) = clause.kind().skip_binder() {
-                                tr.def_id() == def_id
-                            } else {
-                                false
-                            }
+                        && implied_bounds.iter().any(|(implied_by_args, preds)| {
+                            preds.iter().any(|(clause, _)| {
+                                if let ClauseKind::Trait(tr) = clause.kind().skip_binder()
+                                    && tr.def_id() == def_id
+                                {
+                                    is_same_generics(cx.tcx, tr.trait_ref.args, implied_by_args, implied_args)
+                                } else {
+                                    false
+                                }
+                            })
                         })
                     {
                         span_lint(cx, IMPLIED_BOUNDS_IN_IMPL, poly_trait.span, "this bound is implied by another bound and can be removed");
diff --git a/tests/ui/implied_bounds_in_impl.rs b/tests/ui/implied_bounds_in_impl.rs
index 516f21fc795..0bc4b193d53 100644
--- a/tests/ui/implied_bounds_in_impl.rs
+++ b/tests/ui/implied_bounds_in_impl.rs
@@ -3,43 +3,45 @@
 
 use std::ops::{Deref, DerefMut};
 
-trait Trait1<T> {}
-// T is intentionally at a different position in Trait2 than in Trait1,
-// since that also needs to be taken into account when making this lint work with generics
-trait Trait2<U, T>: Trait1<T> {}
-impl Trait1<i32> for () {}
-impl Trait1<String> for () {}
-impl Trait2<u32, i32> for () {}
-impl Trait2<u32, String> for () {}
+// Only one bound, nothing to lint.
+fn normal_deref<T>(x: T) -> impl Deref<Target = T> {
+    Box::new(x)
+}
 
 // Deref implied by DerefMut
 fn deref_derefmut<T>(x: T) -> impl Deref<Target = T> + DerefMut<Target = T> {
     Box::new(x)
 }
 
-// Note: no test for different associated types needed since that isn't allowed in the first place.
-// E.g. `-> impl Deref<Target = T> + DerefMut<Target = U>` is a compile error.
-
-// DefIds of the traits match, but the generics do not, so it's *not* redundant.
-// `Trait2: Trait` holds, but not `Trait2<_, String>: Trait1<i32>`.
-// (Generic traits are currently not linted anyway but once/if ever implemented this should not
-// warn.)
-fn different_generics() -> impl Trait1<i32> + Trait2<u32, String> {
-    /* () */
+trait GenericTrait<T> {}
+trait GenericTrait2<V> {}
+// U is intentionally at a different "index" in GenericSubtrait than `T` is in GenericTrait
+trait GenericSubtrait<T, U, V>: GenericTrait<U> + GenericTrait2<V> {}
+
+impl GenericTrait<i32> for () {}
+impl GenericTrait<i64> for () {}
+impl<V> GenericTrait2<V> for () {}
+impl<V> GenericSubtrait<(), i32, V> for () {}
+impl<V> GenericSubtrait<(), i64, V> for () {}
+
+fn generics_implied<T>() -> impl GenericTrait<T> + GenericSubtrait<(), T, ()>
+where
+    (): GenericSubtrait<(), T, ()>,
+{
 }
 
-trait NonGenericTrait1 {}
-trait NonGenericTrait2: NonGenericTrait1 {}
-impl NonGenericTrait1 for i32 {}
-impl NonGenericTrait2 for i32 {}
+fn generics_implied_multi<V>() -> impl GenericTrait<i32> + GenericTrait2<V> + GenericSubtrait<(), i32, V> {}
 
-// Only one bound. Nothing to lint.
-fn normal1() -> impl NonGenericTrait1 {
-    1
+fn generics_implied_multi2<T, V>() -> impl GenericTrait<T> + GenericTrait2<V> + GenericSubtrait<(), T, V>
+where
+    (): GenericSubtrait<(), T, V> + GenericTrait<T>,
+{
 }
 
-fn normal2() -> impl NonGenericTrait1 + NonGenericTrait2 {
-    1
-}
+// i32 != i64, GenericSubtrait<_, i64, _> does not imply GenericTrait<i32>, don't lint
+fn generics_different() -> impl GenericTrait<i32> + GenericSubtrait<(), i64, ()> {}
+
+// i32 == i32, GenericSubtrait<_, i32, _> does imply GenericTrait<i32>, lint
+fn generics_same() -> impl GenericTrait<i32> + GenericSubtrait<(), i32, ()> {}
 
 fn main() {}
diff --git a/tests/ui/implied_bounds_in_impl.stderr b/tests/ui/implied_bounds_in_impl.stderr
index 2709f727acc..92d412e784f 100644
--- a/tests/ui/implied_bounds_in_impl.stderr
+++ b/tests/ui/implied_bounds_in_impl.stderr
@@ -1,5 +1,5 @@
 error: this bound is implied by another bound and can be removed
-  --> $DIR/implied_bounds_in_impl.rs:16:36
+  --> $DIR/implied_bounds_in_impl.rs:12:36
    |
 LL | fn deref_derefmut<T>(x: T) -> impl Deref<Target = T> + DerefMut<Target = T> {
    |                                    ^^^^^^^^^^^^^^^^^
@@ -7,10 +7,40 @@ LL | fn deref_derefmut<T>(x: T) -> impl Deref<Target = T> + DerefMut<Target = T>
    = note: `-D clippy::implied-bounds-in-impl` implied by `-D warnings`
 
 error: this bound is implied by another bound and can be removed
-  --> $DIR/implied_bounds_in_impl.rs:41:22
+  --> $DIR/implied_bounds_in_impl.rs:27:34
    |
-LL | fn normal2() -> impl NonGenericTrait1 + NonGenericTrait2 {
-   |                      ^^^^^^^^^^^^^^^^
+LL | fn generics_implied<T>() -> impl GenericTrait<T> + GenericSubtrait<(), T, ()>
+   |                                  ^^^^^^^^^^^^^^^
 
-error: aborting due to 2 previous errors
+error: this bound is implied by another bound and can be removed
+  --> $DIR/implied_bounds_in_impl.rs:33:40
+   |
+LL | fn generics_implied_multi<V>() -> impl GenericTrait<i32> + GenericTrait2<V> + GenericSubtrait<(), i32, V> {}
+   |                                        ^^^^^^^^^^^^^^^^^
+
+error: this bound is implied by another bound and can be removed
+  --> $DIR/implied_bounds_in_impl.rs:33:60
+   |
+LL | fn generics_implied_multi<V>() -> impl GenericTrait<i32> + GenericTrait2<V> + GenericSubtrait<(), i32, V> {}
+   |                                                            ^^^^^^^^^^^^^^^^
+
+error: this bound is implied by another bound and can be removed
+  --> $DIR/implied_bounds_in_impl.rs:35:44
+   |
+LL | fn generics_implied_multi2<T, V>() -> impl GenericTrait<T> + GenericTrait2<V> + GenericSubtrait<(), T, V>
+   |                                            ^^^^^^^^^^^^^^^
+
+error: this bound is implied by another bound and can be removed
+  --> $DIR/implied_bounds_in_impl.rs:35:62
+   |
+LL | fn generics_implied_multi2<T, V>() -> impl GenericTrait<T> + GenericTrait2<V> + GenericSubtrait<(), T, V>
+   |                                                              ^^^^^^^^^^^^^^^^
+
+error: this bound is implied by another bound and can be removed
+  --> $DIR/implied_bounds_in_impl.rs:45:28
+   |
+LL | fn generics_same() -> impl GenericTrait<i32> + GenericSubtrait<(), i32, ()> {}
+   |                            ^^^^^^^^^^^^^^^^^
+
+error: aborting due to 7 previous errors