Fix FN for collections/smart ptrs in `std`

3 files changed, 161 insertions, 37 deletions

diff --git a/clippy_lints/src/mut_key.rs b/clippy_lints/src/mut_key.rs
index bdb6fc505f7..cb17e4dbfd0 100644
--- a/clippy_lints/src/mut_key.rs
+++ b/clippy_lints/src/mut_key.rs
@@ -3,7 +3,7 @@ use clippy_utils::trait_ref_of_method;
 use rustc_hir as hir;
 use rustc_lint::{LateContext, LateLintPass};
 use rustc_middle::ty::TypeFoldable;
-use rustc_middle::ty::{Adt, Array, RawPtr, Ref, Slice, Tuple, Ty, TypeAndMut};
+use rustc_middle::ty::{Adt, Array, Ref, Slice, Tuple, Ty};
 use rustc_session::{declare_lint_pass, declare_tool_lint};
 use rustc_span::source_map::Span;
 use rustc_span::symbol::sym;
@@ -19,10 +19,29 @@ declare_clippy_lint! {
     /// so having types with interior mutability is a bad idea.
     ///
     /// ### Known problems
-    /// It's correct to use a struct, that contains interior mutability
-    /// as a key, when its `Hash` implementation doesn't access any of the interior mutable types.
-    /// However, this lint is unable to recognize this, so it causes a false positive in theses cases.
-    /// The `bytes` crate is a great example of this.
+    ///
+    /// #### False Positives
+    /// It's correct to use a struct that contains interior mutability as a key, when its
+    /// implementation of `Hash` or `Ord` doesn't access any of the interior mutable types.
+    /// However, this lint is unable to recognize this, so it will often cause false positives in
+    /// theses cases.  The `bytes` crate is a great example of this.
+    ///
+    /// #### False Negatives
+    /// For custom `struct`s/`enum`s, this lint is unable to check for interior mutability behind
+    /// indirection.  For example, `struct BadKey<'a>(&'a Cell<usize>)` will be seen as immutable
+    /// and cause a false negative if its implementation of `Hash`/`Ord` accesses the `Cell`.
+    ///
+    /// This lint does check a few cases for indirection.  Firstly, using some standard library
+    /// types (`Option`, `Result`, `Box`, `Rc`, `Arc`, `Vec`, `VecDeque`, `BTreeMap` and
+    /// `BTreeSet`) directly as keys (e.g. in `HashMap<Box<Cell<usize>>, ()>`) **will** trigger the
+    /// lint, because the impls of `Hash`/`Ord` for these types directly call `Hash`/`Ord` on their
+    /// contained type.
+    ///
+    /// Secondly, the implementations of `Hash` and `Ord` for raw pointers (`*const T` or `*mut T`)
+    /// apply only to the **address** of the contained value.  Therefore, interior mutability
+    /// behind raw pointers (e.g. in `HashSet<*mut Cell<usize>>`) can't impact the value of `Hash`
+    /// or `Ord`, and therefore will not trigger this link.  For more info, see issue
+    /// [#6745](https://github.com/rust-lang/rust-clippy/issues/6745).
     ///
     /// ### Example
     /// ```rust
@@ -103,43 +122,52 @@ fn check_sig<'tcx>(cx: &LateContext<'tcx>, item_hir_id: hir::HirId, decl: &hir::
 fn check_ty<'tcx>(cx: &LateContext<'tcx>, span: Span, ty: Ty<'tcx>) {
     let ty = ty.peel_refs();
     if let Adt(def, substs) = ty.kind() {
-        let is_map_type = [sym::hashmap_type, sym::BTreeMap, sym::hashset_type, sym::BTreeMap]
+        let is_keyed_type = [sym::hashmap_type, sym::BTreeMap, sym::hashset_type, sym::BTreeSet]
             .iter()
             .any(|diag_item| cx.tcx.is_diagnostic_item(*diag_item, def.did));
-        if is_map_type && is_mutable_type(cx, substs.type_at(0), span, true) {
+        if is_keyed_type && is_interior_mutable_type(cx, substs.type_at(0), span) {
             span_lint(cx, MUTABLE_KEY_TYPE, span, "mutable key type");
         }
     }
 }
 
-fn is_mutable_type<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>, span: Span, is_top_level_type: bool) -> bool {
+/// Determines if a type contains interior mutability which would affect its implementation of
+/// [`Hash`] or [`Ord`].
+fn is_interior_mutable_type<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>, span: Span) -> bool {
     match *ty.kind() {
-        RawPtr(TypeAndMut { ty: inner_ty, mutbl }) => {
-            if is_top_level_type {
-                // Raw pointers are hashed by the address they point to, not what is pointed to.
-                // Therefore, using a raw pointer to any type as the top-level key type is OK.
-                // Using raw pointers _in_ the key type is not, because the wrapper type could
-                // provide a custom `impl` for `Hash` (which could deref the raw pointer).
-                //
-                // see:
-                // - clippy issue: https://github.com/rust-lang/rust-clippy/issues/6745
-                // - std code: https://github.com/rust-lang/rust/blob/1.54.0/library/core/src/hash/mod.rs#L717-L736
-                false
-            } else {
-                mutbl == hir::Mutability::Mut || is_mutable_type(cx, inner_ty, span, false)
-            }
-        },
-        Ref(_, inner_ty, mutbl) => mutbl == hir::Mutability::Mut || is_mutable_type(cx, inner_ty, span, false),
-        Slice(inner_ty) => is_mutable_type(cx, inner_ty, span, false),
+        Ref(_, inner_ty, mutbl) => mutbl == hir::Mutability::Mut || is_interior_mutable_type(cx, inner_ty, span),
+        Slice(inner_ty) => is_interior_mutable_type(cx, inner_ty, span),
         Array(inner_ty, size) => {
             size.try_eval_usize(cx.tcx, cx.param_env).map_or(true, |u| u != 0)
-                && is_mutable_type(cx, inner_ty, span, false)
+                && is_interior_mutable_type(cx, inner_ty, span)
         },
-        Tuple(..) => ty.tuple_fields().any(|ty| is_mutable_type(cx, ty, span, false)),
-        Adt(..) => {
-            !ty.has_escaping_bound_vars()
-                && cx.tcx.layout_of(cx.param_env.and(ty)).is_ok()
-                && !ty.is_freeze(cx.tcx.at(span), cx.param_env)
+        Tuple(..) => ty.tuple_fields().any(|ty| is_interior_mutable_type(cx, ty, span)),
+        Adt(def, substs) => {
+            // Special case for collections in `std` who's impl of `Hash` or `Ord` delegates to
+            // that of their type parameters.  Note: we don't include `HashSet` and `HashMap`
+            // because they have no impl for `Hash` or `Ord`.
+            let is_std_collection = [
+                sym::option_type,
+                sym::result_type,
+                sym::LinkedList,
+                sym::vec_type,
+                sym::vecdeque_type,
+                sym::BTreeMap,
+                sym::BTreeSet,
+                sym::Rc,
+                sym::Arc,
+            ]
+            .iter()
+            .any(|diag_item| cx.tcx.is_diagnostic_item(*diag_item, def.did));
+            let is_box = Some(def.did) == cx.tcx.lang_items().owned_box();
+            if is_std_collection || is_box {
+                // The type is mutable if any of its type parameters are
+                substs.types().any(|ty| is_interior_mutable_type(cx, ty, span))
+            } else {
+                !ty.has_escaping_bound_vars()
+                    && cx.tcx.layout_of(cx.param_env.and(ty)).is_ok()
+                    && !ty.is_freeze(cx.tcx.at(span), cx.param_env)
+            }
         },
         _ => false,
     }
diff --git a/tests/ui/mut_key.rs b/tests/ui/mut_key.rs
index 75b1618d82a..1c0ba664580 100644
--- a/tests/ui/mut_key.rs
+++ b/tests/ui/mut_key.rs
@@ -1,7 +1,9 @@
 use std::cell::Cell;
-use std::collections::{HashMap, HashSet};
+use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
 use std::hash::{Hash, Hasher};
+use std::rc::Rc;
 use std::sync::atomic::{AtomicUsize, Ordering::Relaxed};
+use std::sync::Arc;
 
 struct Key(AtomicUsize);
 
@@ -64,4 +66,20 @@ fn main() {
 
     raw_ptr_is_ok(&mut HashMap::new());
     raw_mut_ptr_is_ok(&mut HashMap::new());
+
+    let _map = HashMap::<Cell<usize>, usize>::new();
+    let _map = HashMap::<&mut Cell<usize>, usize>::new();
+    let _map = HashMap::<&mut usize, usize>::new();
+    // Collection types from `std` who's impl of `Hash` or `Ord` delegate their type parameters
+    let _map = HashMap::<Vec<Cell<usize>>, usize>::new();
+    let _map = HashMap::<BTreeMap<Cell<usize>, ()>, usize>::new();
+    let _map = HashMap::<BTreeMap<(), Cell<usize>>, usize>::new();
+    let _map = HashMap::<BTreeSet<Cell<usize>>, usize>::new();
+    let _map = HashMap::<Option<Cell<usize>>, usize>::new();
+    let _map = HashMap::<Option<Vec<Cell<usize>>>, usize>::new();
+    let _map = HashMap::<Result<&mut usize, ()>, usize>::new();
+    // Smart pointers from `std` who's impl of `Hash` or `Ord` delegate their type parameters
+    let _map = HashMap::<Box<Cell<usize>>, usize>::new();
+    let _map = HashMap::<Rc<Cell<usize>>, usize>::new();
+    let _map = HashMap::<Arc<Cell<usize>>, usize>::new();
 }
diff --git a/tests/ui/mut_key.stderr b/tests/ui/mut_key.stderr
index 8da1262f0f1..25dd029b16e 100644
--- a/tests/ui/mut_key.stderr
+++ b/tests/ui/mut_key.stderr
@@ -1,5 +1,5 @@
 error: mutable key type
-  --> $DIR/mut_key.rs:28:32
+  --> $DIR/mut_key.rs:30:32
    |
 LL | fn should_not_take_this_arg(m: &mut HashMap<Key, usize>, _n: usize) -> HashSet<Key> {
    |                                ^^^^^^^^^^^^^^^^^^^^^^^^
@@ -7,22 +7,100 @@ LL | fn should_not_take_this_arg(m: &mut HashMap<Key, usize>, _n: usize) -> Hash
    = note: `-D clippy::mutable-key-type` implied by `-D warnings`
 
 error: mutable key type
-  --> $DIR/mut_key.rs:28:72
+  --> $DIR/mut_key.rs:30:72
    |
 LL | fn should_not_take_this_arg(m: &mut HashMap<Key, usize>, _n: usize) -> HashSet<Key> {
    |                                                                        ^^^^^^^^^^^^
 
 error: mutable key type
-  --> $DIR/mut_key.rs:29:5
+  --> $DIR/mut_key.rs:31:5
    |
 LL |     let _other: HashMap<Key, bool> = HashMap::new();
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 error: mutable key type
-  --> $DIR/mut_key.rs:56:22
+  --> $DIR/mut_key.rs:58:22
    |
 LL | fn tuples_bad<U>(_m: &mut HashMap<(Key, U), bool>) {}
    |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
-error: aborting due to 4 previous errors
+error: mutable key type
+  --> $DIR/mut_key.rs:70:5
+   |
+LL |     let _map = HashMap::<Cell<usize>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:71:5
+   |
+LL |     let _map = HashMap::<&mut Cell<usize>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:72:5
+   |
+LL |     let _map = HashMap::<&mut usize, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:74:5
+   |
+LL |     let _map = HashMap::<Vec<Cell<usize>>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:75:5
+   |
+LL |     let _map = HashMap::<BTreeMap<Cell<usize>, ()>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:76:5
+   |
+LL |     let _map = HashMap::<BTreeMap<(), Cell<usize>>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:77:5
+   |
+LL |     let _map = HashMap::<BTreeSet<Cell<usize>>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:78:5
+   |
+LL |     let _map = HashMap::<Option<Cell<usize>>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:79:5
+   |
+LL |     let _map = HashMap::<Option<Vec<Cell<usize>>>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:80:5
+   |
+LL |     let _map = HashMap::<Result<&mut usize, ()>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:82:5
+   |
+LL |     let _map = HashMap::<Box<Cell<usize>>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:83:5
+   |
+LL |     let _map = HashMap::<Rc<Cell<usize>>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: mutable key type
+  --> $DIR/mut_key.rs:84:5
+   |
+LL |     let _map = HashMap::<Arc<Cell<usize>>, usize>::new();
+   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to 17 previous errors