clippy_lints/src/mut_key.rs

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