clippy_lints/src/mut_key.rs

   1 use clippy_utils::diagnostics::span_lint;
   2 use clippy_utils::trait_ref_of_method;
   3 use rustc_hir as hir;
   4 use rustc_lint::{LateContext, LateLintPass};
   5 use rustc_middle::ty::TypeFoldable;
   6 use rustc_middle::ty::{Adt, Array, Ref, Slice, Tuple, Ty};
   7 use rustc_session::{declare_lint_pass, declare_tool_lint};
   8 use rustc_span::source_map::Span;
   9 use rustc_span::symbol::sym;
  10 use std::iter;
  11
  12 declare_clippy_lint! {
  13     /// ### What it does
  14     /// Checks for sets/maps with mutable key types.
  15     ///
  16     /// ### Why is this bad?
  17     /// All of `HashMap`, `HashSet`, `BTreeMap` and
  18     /// `BtreeSet` rely on either the hash or the order of keys be unchanging,
  19     /// so having types with interior mutability is a bad idea.
  20     ///
  21     /// ### Known problems
  22     ///
  23     /// #### False Positives
  24     /// It's correct to use a struct that contains interior mutability as a key, when its
  25     /// implementation of `Hash` or `Ord` doesn't access any of the interior mutable types.
  26     /// However, this lint is unable to recognize this, so it will often cause false positives in
  27     /// theses cases.  The `bytes` crate is a great example of this.
  28     ///
  29     /// #### False Negatives
  30     /// For custom `struct`s/`enum`s, this lint is unable to check for interior mutability behind
  31     /// indirection.  For example, `struct BadKey<'a>(&'a Cell<usize>)` will be seen as immutable
  32     /// and cause a false negative if its implementation of `Hash`/`Ord` accesses the `Cell`.
  33     ///
  34     /// This lint does check a few cases for indirection.  Firstly, using some standard library
  35     /// types (`Option`, `Result`, `Box`, `Rc`, `Arc`, `Vec`, `VecDeque`, `BTreeMap` and
  36     /// `BTreeSet`) directly as keys (e.g. in `HashMap<Box<Cell<usize>>, ()>`) **will** trigger the
  37     /// lint, because the impls of `Hash`/`Ord` for these types directly call `Hash`/`Ord` on their
  38     /// contained type.
  39     ///
  40     /// Secondly, the implementations of `Hash` and `Ord` for raw pointers (`*const T` or `*mut T`)
  41     /// apply only to the **address** of the contained value.  Therefore, interior mutability
  42     /// behind raw pointers (e.g. in `HashSet<*mut Cell<usize>>`) can't impact the value of `Hash`
  43     /// or `Ord`, and therefore will not trigger this link.  For more info, see issue
  44     /// [#6745](https://github.com/rust-lang/rust-clippy/issues/6745).
  45     ///
  46     /// ### Example
  47     /// ```rust
  48     /// use std::cmp::{PartialEq, Eq};
  49     /// use std::collections::HashSet;
  50     /// use std::hash::{Hash, Hasher};
  51     /// use std::sync::atomic::AtomicUsize;
  52     ///# #[allow(unused)]
  53     ///
  54     /// struct Bad(AtomicUsize);
  55     /// impl PartialEq for Bad {
  56     ///     fn eq(&self, rhs: &Self) -> bool {
  57     ///          ..
  58     /// ; unimplemented!();
  59     ///     }
  60     /// }
  61     ///
  62     /// impl Eq for Bad {}
  63     ///
  64     /// impl Hash for Bad {
  65     ///     fn hash<H: Hasher>(&self, h: &mut H) {
  66     ///         ..
  67     /// ; unimplemented!();
  68     ///     }
  69     /// }
  70     ///
  71     /// fn main() {
  72     ///     let _: HashSet<Bad> = HashSet::new();
  73     /// }
  74     /// ```
  75     pub MUTABLE_KEY_TYPE,
  76     suspicious,
  77     "Check for mutable `Map`/`Set` key type"
  78 }
  79
  80 declare_lint_pass!(MutableKeyType => [ MUTABLE_KEY_TYPE ]);
  81
  82 impl<'tcx> LateLintPass<'tcx> for MutableKeyType {
  83     fn check_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx hir::Item<'tcx>) {
  84         if let hir::ItemKind::Fn(ref sig, ..) = item.kind {
  85             check_sig(cx, item.hir_id(), sig.decl);
  86         }
  87     }
  88
  89     fn check_impl_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx hir::ImplItem<'tcx>) {
  90         if let hir::ImplItemKind::Fn(ref sig, ..) = item.kind {
  91             if trait_ref_of_method(cx, item.hir_id()).is_none() {
  92                 check_sig(cx, item.hir_id(), sig.decl);
  93             }
  94         }
  95     }
  96
  97     fn check_trait_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx hir::TraitItem<'tcx>) {
  98         if let hir::TraitItemKind::Fn(ref sig, ..) = item.kind {
  99             check_sig(cx, item.hir_id(), sig.decl);
 100         }
 101     }
 102
 103     fn check_local(&mut self, cx: &LateContext<'_>, local: &hir::Local<'_>) {
 104         if let hir::PatKind::Wild = local.pat.kind {
 105             return;
 106         }
 107         check_ty(cx, local.span, cx.typeck_results().pat_ty(&*local.pat));
 108     }
 109 }
 110
 111 fn check_sig<'tcx>(cx: &LateContext<'tcx>, item_hir_id: hir::HirId, decl: &hir::FnDecl<'_>) {
 112     let fn_def_id = cx.tcx.hir().local_def_id(item_hir_id);
 113     let fn_sig = cx.tcx.fn_sig(fn_def_id);
 114     for (hir_ty, ty) in iter::zip(decl.inputs, fn_sig.inputs().skip_binder()) {
 115         check_ty(cx, hir_ty.span, ty);
 116     }
 117     check_ty(cx, decl.output.span(), cx.tcx.erase_late_bound_regions(fn_sig.output()));
 118 }
 119
 120 // We want to lint 1. sets or maps with 2. not immutable key types and 3. no unerased
 121 // generics (because the compiler cannot ensure immutability for unknown types).
 122 fn check_ty<'tcx>(cx: &LateContext<'tcx>, span: Span, ty: Ty<'tcx>) {
 123     let ty = ty.peel_refs();
 124     if let Adt(def, substs) = ty.kind() {
 125         let is_keyed_type = [sym::hashmap_type, sym::BTreeMap, sym::hashset_type, sym::BTreeSet]
 126             .iter()
 127             .any(|diag_item| cx.tcx.is_diagnostic_item(*diag_item, def.did));
 128         if is_keyed_type && is_interior_mutable_type(cx, substs.type_at(0), span) {
 129             span_lint(cx, MUTABLE_KEY_TYPE, span, "mutable key type");
 130         }
 131     }
 132 }
 133
 134 /// Determines if a type contains interior mutability which would affect its implementation of
 135 /// [`Hash`] or [`Ord`].
 136 fn is_interior_mutable_type<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>, span: Span) -> bool {
 137     match *ty.kind() {
 138         Ref(_, inner_ty, mutbl) => mutbl == hir::Mutability::Mut || is_interior_mutable_type(cx, inner_ty, span),
 139         Slice(inner_ty) => is_interior_mutable_type(cx, inner_ty, span),
 140         Array(inner_ty, size) => {
 141             size.try_eval_usize(cx.tcx, cx.param_env).map_or(true, |u| u != 0)
 142                 && is_interior_mutable_type(cx, inner_ty, span)
 143         },
 144         Tuple(..) => ty.tuple_fields().any(|ty| is_interior_mutable_type(cx, ty, span)),
 145         Adt(def, substs) => {
 146             // Special case for collections in `std` who's impl of `Hash` or `Ord` delegates to
 147             // that of their type parameters.  Note: we don't include `HashSet` and `HashMap`
 148             // because they have no impl for `Hash` or `Ord`.
 149             let is_std_collection = [
 150                 sym::option_type,
 151                 sym::result_type,
 152                 sym::LinkedList,
 153                 sym::vec_type,
 154                 sym::vecdeque_type,
 155                 sym::BTreeMap,
 156                 sym::BTreeSet,
 157                 sym::Rc,
 158                 sym::Arc,
 159             ]
 160             .iter()
 161             .any(|diag_item| cx.tcx.is_diagnostic_item(*diag_item, def.did));
 162             let is_box = Some(def.did) == cx.tcx.lang_items().owned_box();
 163             if is_std_collection || is_box {
 164                 // The type is mutable if any of its type parameters are
 165                 substs.types().any(|ty| is_interior_mutable_type(cx, ty, span))
 166             } else {
 167                 !ty.has_escaping_bound_vars()
 168                     && cx.tcx.layout_of(cx.param_env.and(ty)).is_ok()
 169                     && !ty.is_freeze(cx.tcx.at(span), cx.param_env)
 170             }
 171         },
 172         _ => false,
 173     }
 174 }