1 use clippy_utils::diagnostics::span_lint;
2 use clippy_utils::trait_ref_of_method;
4 use rustc_lint::{LateContext, LateLintPass};
5 use rustc_middle::ty::TypeVisitable;
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;
12 declare_clippy_lint! {
14 /// Checks for sets/maps with mutable key types.
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.
21 /// ### Known problems
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.
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`.
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
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).
48 /// use std::cmp::{PartialEq, Eq};
49 /// use std::collections::HashSet;
50 /// use std::hash::{Hash, Hasher};
51 /// use std::sync::atomic::AtomicUsize;
54 /// struct Bad(AtomicUsize);
55 /// impl PartialEq for Bad {
56 /// fn eq(&self, rhs: &Self) -> bool {
58 /// ; unimplemented!();
62 /// impl Eq for Bad {}
64 /// impl Hash for Bad {
65 /// fn hash<H: Hasher>(&self, h: &mut H) {
67 /// ; unimplemented!();
72 /// let _: HashSet<Bad> = HashSet::new();
75 #[clippy::version = "1.42.0"]
78 "Check for mutable `Map`/`Set` key type"
81 declare_lint_pass!(MutableKeyType => [ MUTABLE_KEY_TYPE ]);
83 impl<'tcx> LateLintPass<'tcx> for MutableKeyType {
84 fn check_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx hir::Item<'tcx>) {
85 if let hir::ItemKind::Fn(ref sig, ..) = item.kind {
86 check_sig(cx, item.hir_id(), sig.decl);
90 fn check_impl_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx hir::ImplItem<'tcx>) {
91 if let hir::ImplItemKind::Fn(ref sig, ..) = item.kind {
92 if trait_ref_of_method(cx, item.def_id).is_none() {
93 check_sig(cx, item.hir_id(), sig.decl);
98 fn check_trait_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx hir::TraitItem<'tcx>) {
99 if let hir::TraitItemKind::Fn(ref sig, ..) = item.kind {
100 check_sig(cx, item.hir_id(), sig.decl);
106 cx: &LateContext<'_>,
107 local: &hir::Local<'_>,
108 _: Option<&hir::Block<'_>>,
110 if let hir::PatKind::Wild = local.pat.kind {
113 check_ty(cx, local.span, cx.typeck_results().pat_ty(local.pat));
117 fn check_sig<'tcx>(cx: &LateContext<'tcx>, item_hir_id: hir::HirId, decl: &hir::FnDecl<'_>) {
118 let fn_def_id = cx.tcx.hir().local_def_id(item_hir_id);
119 let fn_sig = cx.tcx.fn_sig(fn_def_id);
120 for (hir_ty, ty) in iter::zip(decl.inputs, fn_sig.inputs().skip_binder()) {
121 check_ty(cx, hir_ty.span, *ty);
123 check_ty(cx, decl.output.span(), cx.tcx.erase_late_bound_regions(fn_sig.output()));
126 // We want to lint 1. sets or maps with 2. not immutable key types and 3. no unerased
127 // generics (because the compiler cannot ensure immutability for unknown types).
128 fn check_ty<'tcx>(cx: &LateContext<'tcx>, span: Span, ty: Ty<'tcx>) {
129 let ty = ty.peel_refs();
130 if let Adt(def, substs) = ty.kind() {
131 let is_keyed_type = [sym::HashMap, sym::BTreeMap, sym::HashSet, sym::BTreeSet]
133 .any(|diag_item| cx.tcx.is_diagnostic_item(*diag_item, def.did()));
134 if is_keyed_type && is_interior_mutable_type(cx, substs.type_at(0), span) {
135 span_lint(cx, MUTABLE_KEY_TYPE, span, "mutable key type");
140 /// Determines if a type contains interior mutability which would affect its implementation of
141 /// [`Hash`] or [`Ord`].
142 fn is_interior_mutable_type<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>, span: Span) -> bool {
144 Ref(_, inner_ty, mutbl) => mutbl == hir::Mutability::Mut || is_interior_mutable_type(cx, inner_ty, span),
145 Slice(inner_ty) => is_interior_mutable_type(cx, inner_ty, span),
146 Array(inner_ty, size) => {
147 size.try_eval_usize(cx.tcx, cx.param_env).map_or(true, |u| u != 0)
148 && is_interior_mutable_type(cx, inner_ty, span)
150 Tuple(fields) => fields.iter().any(|ty| is_interior_mutable_type(cx, ty, span)),
151 Adt(def, substs) => {
152 // Special case for collections in `std` who's impl of `Hash` or `Ord` delegates to
153 // that of their type parameters. Note: we don't include `HashSet` and `HashMap`
154 // because they have no impl for `Hash` or `Ord`.
155 let is_std_collection = [
167 .any(|diag_item| cx.tcx.is_diagnostic_item(*diag_item, def.did()));
168 let is_box = Some(def.did()) == cx.tcx.lang_items().owned_box();
169 if is_std_collection || is_box {
170 // The type is mutable if any of its type parameters are
171 substs.types().any(|ty| is_interior_mutable_type(cx, ty, span))
173 !ty.has_escaping_bound_vars()
174 && cx.tcx.layout_of(cx.param_env.and(ty)).is_ok()
175 && !ty.is_freeze(cx.tcx.at(span), cx.param_env)