clippy_lints/src/types/mod.rs

   1 #![allow(rustc::default_hash_types)]
   2
   3 mod borrowed_box;
   4 mod box_vec;
   5 mod linked_list;
   6 mod option_option;
   7 mod rc_buffer;
   8 mod redundant_allocation;
   9 mod utils;
  10 mod vec_box;
  11
  12 use std::borrow::Cow;
  13 use std::cmp::Ordering;
  14 use std::collections::BTreeMap;
  15
  16 use clippy_utils::diagnostics::{multispan_sugg, span_lint, span_lint_and_then};
  17 use clippy_utils::source::{snippet, snippet_opt};
  18 use clippy_utils::ty::is_type_diagnostic_item;
  19 use if_chain::if_chain;
  20 use rustc_errors::DiagnosticBuilder;
  21 use rustc_hir as hir;
  22 use rustc_hir::intravisit::{walk_body, walk_expr, walk_ty, FnKind, NestedVisitorMap, Visitor};
  23 use rustc_hir::{
  24     Body, Expr, ExprKind, FnDecl, FnRetTy, FnSig, GenericArg, GenericParamKind, HirId, ImplItem, ImplItemKind, Item,
  25     ItemKind, Local, MutTy, QPath, TraitFn, TraitItem, TraitItemKind, TyKind,
  26 };
  27 use rustc_lint::{LateContext, LateLintPass, LintContext};
  28 use rustc_middle::hir::map::Map;
  29 use rustc_middle::lint::in_external_macro;
  30 use rustc_middle::ty::{self, IntTy, Ty, TyS, TypeckResults, UintTy};
  31 use rustc_session::{declare_lint_pass, declare_tool_lint, impl_lint_pass};
  32 use rustc_span::source_map::Span;
  33 use rustc_span::symbol::sym;
  34 use rustc_target::abi::LayoutOf;
  35 use rustc_target::spec::abi::Abi;
  36 use rustc_typeck::hir_ty_to_ty;
  37
  38 use crate::consts::{constant, Constant};
  39 use clippy_utils::paths;
  40 use clippy_utils::{comparisons, differing_macro_contexts, match_path, sext};
  41
  42 declare_clippy_lint! {
  43     /// **What it does:** Checks for use of `Box<Vec<_>>` anywhere in the code.
  44     /// Check the [Box documentation](https://doc.rust-lang.org/std/boxed/index.html) for more information.
  45     ///
  46     /// **Why is this bad?** `Vec` already keeps its contents in a separate area on
  47     /// the heap. So if you `Box` it, you just add another level of indirection
  48     /// without any benefit whatsoever.
  49     ///
  50     /// **Known problems:** None.
  51     ///
  52     /// **Example:**
  53     /// ```rust,ignore
  54     /// struct X {
  55     ///     values: Box<Vec<Foo>>,
  56     /// }
  57     /// ```
  58     ///
  59     /// Better:
  60     ///
  61     /// ```rust,ignore
  62     /// struct X {
  63     ///     values: Vec<Foo>,
  64     /// }
  65     /// ```
  66     pub BOX_VEC,
  67     perf,
  68     "usage of `Box<Vec<T>>`, vector elements are already on the heap"
  69 }
  70
  71 declare_clippy_lint! {
  72     /// **What it does:** Checks for use of `Vec<Box<T>>` where T: Sized anywhere in the code.
  73     /// Check the [Box documentation](https://doc.rust-lang.org/std/boxed/index.html) for more information.
  74     ///
  75     /// **Why is this bad?** `Vec` already keeps its contents in a separate area on
  76     /// the heap. So if you `Box` its contents, you just add another level of indirection.
  77     ///
  78     /// **Known problems:** Vec<Box<T: Sized>> makes sense if T is a large type (see [#3530](https://github.com/rust-lang/rust-clippy/issues/3530),
  79     /// 1st comment).
  80     ///
  81     /// **Example:**
  82     /// ```rust
  83     /// struct X {
  84     ///     values: Vec<Box<i32>>,
  85     /// }
  86     /// ```
  87     ///
  88     /// Better:
  89     ///
  90     /// ```rust
  91     /// struct X {
  92     ///     values: Vec<i32>,
  93     /// }
  94     /// ```
  95     pub VEC_BOX,
  96     complexity,
  97     "usage of `Vec<Box<T>>` where T: Sized, vector elements are already on the heap"
  98 }
  99
 100 declare_clippy_lint! {
 101     /// **What it does:** Checks for use of `Option<Option<_>>` in function signatures and type
 102     /// definitions
 103     ///
 104     /// **Why is this bad?** `Option<_>` represents an optional value. `Option<Option<_>>`
 105     /// represents an optional optional value which is logically the same thing as an optional
 106     /// value but has an unneeded extra level of wrapping.
 107     ///
 108     /// If you have a case where `Some(Some(_))`, `Some(None)` and `None` are distinct cases,
 109     /// consider a custom `enum` instead, with clear names for each case.
 110     ///
 111     /// **Known problems:** None.
 112     ///
 113     /// **Example**
 114     /// ```rust
 115     /// fn get_data() -> Option<Option<u32>> {
 116     ///     None
 117     /// }
 118     /// ```
 119     ///
 120     /// Better:
 121     ///
 122     /// ```rust
 123     /// pub enum Contents {
 124     ///     Data(Vec<u8>), // Was Some(Some(Vec<u8>))
 125     ///     NotYetFetched, // Was Some(None)
 126     ///     None,          // Was None
 127     /// }
 128     ///
 129     /// fn get_data() -> Contents {
 130     ///     Contents::None
 131     /// }
 132     /// ```
 133     pub OPTION_OPTION,
 134     pedantic,
 135     "usage of `Option<Option<T>>`"
 136 }
 137
 138 declare_clippy_lint! {
 139     /// **What it does:** Checks for usage of any `LinkedList`, suggesting to use a
 140     /// `Vec` or a `VecDeque` (formerly called `RingBuf`).
 141     ///
 142     /// **Why is this bad?** Gankro says:
 143     ///
 144     /// > The TL;DR of `LinkedList` is that it's built on a massive amount of
 145     /// pointers and indirection.
 146     /// > It wastes memory, it has terrible cache locality, and is all-around slow.
 147     /// `RingBuf`, while
 148     /// > "only" amortized for push/pop, should be faster in the general case for
 149     /// almost every possible
 150     /// > workload, and isn't even amortized at all if you can predict the capacity
 151     /// you need.
 152     /// >
 153     /// > `LinkedList`s are only really good if you're doing a lot of merging or
 154     /// splitting of lists.
 155     /// > This is because they can just mangle some pointers instead of actually
 156     /// copying the data. Even
 157     /// > if you're doing a lot of insertion in the middle of the list, `RingBuf`
 158     /// can still be better
 159     /// > because of how expensive it is to seek to the middle of a `LinkedList`.
 160     ///
 161     /// **Known problems:** False positives – the instances where using a
 162     /// `LinkedList` makes sense are few and far between, but they can still happen.
 163     ///
 164     /// **Example:**
 165     /// ```rust
 166     /// # use std::collections::LinkedList;
 167     /// let x: LinkedList<usize> = LinkedList::new();
 168     /// ```
 169     pub LINKEDLIST,
 170     pedantic,
 171     "usage of LinkedList, usually a vector is faster, or a more specialized data structure like a `VecDeque`"
 172 }
 173
 174 declare_clippy_lint! {
 175     /// **What it does:** Checks for use of `&Box<T>` anywhere in the code.
 176     /// Check the [Box documentation](https://doc.rust-lang.org/std/boxed/index.html) for more information.
 177     ///
 178     /// **Why is this bad?** Any `&Box<T>` can also be a `&T`, which is more
 179     /// general.
 180     ///
 181     /// **Known problems:** None.
 182     ///
 183     /// **Example:**
 184     /// ```rust,ignore
 185     /// fn foo(bar: &Box<T>) { ... }
 186     /// ```
 187     ///
 188     /// Better:
 189     ///
 190     /// ```rust,ignore
 191     /// fn foo(bar: &T) { ... }
 192     /// ```
 193     pub BORROWED_BOX,
 194     complexity,
 195     "a borrow of a boxed type"
 196 }
 197
 198 declare_clippy_lint! {
 199     /// **What it does:** Checks for use of redundant allocations anywhere in the code.
 200     ///
 201     /// **Why is this bad?** Expressions such as `Rc<&T>`, `Rc<Rc<T>>`, `Rc<Box<T>>`, `Box<&T>`
 202     /// add an unnecessary level of indirection.
 203     ///
 204     /// **Known problems:** None.
 205     ///
 206     /// **Example:**
 207     /// ```rust
 208     /// # use std::rc::Rc;
 209     /// fn foo(bar: Rc<&usize>) {}
 210     /// ```
 211     ///
 212     /// Better:
 213     ///
 214     /// ```rust
 215     /// fn foo(bar: &usize) {}
 216     /// ```
 217     pub REDUNDANT_ALLOCATION,
 218     perf,
 219     "redundant allocation"
 220 }
 221
 222 declare_clippy_lint! {
 223     /// **What it does:** Checks for `Rc<T>` and `Arc<T>` when `T` is a mutable buffer type such as `String` or `Vec`.
 224     ///
 225     /// **Why is this bad?** Expressions such as `Rc<String>` usually have no advantage over `Rc<str>`, since
 226     /// it is larger and involves an extra level of indirection, and doesn't implement `Borrow<str>`.
 227     ///
 228     /// While mutating a buffer type would still be possible with `Rc::get_mut()`, it only
 229     /// works if there are no additional references yet, which usually defeats the purpose of
 230     /// enclosing it in a shared ownership type. Instead, additionally wrapping the inner
 231     /// type with an interior mutable container (such as `RefCell` or `Mutex`) would normally
 232     /// be used.
 233     ///
 234     /// **Known problems:** This pattern can be desirable to avoid the overhead of a `RefCell` or `Mutex` for
 235     /// cases where mutation only happens before there are any additional references.
 236     ///
 237     /// **Example:**
 238     /// ```rust,ignore
 239     /// # use std::rc::Rc;
 240     /// fn foo(interned: Rc<String>) { ... }
 241     /// ```
 242     ///
 243     /// Better:
 244     ///
 245     /// ```rust,ignore
 246     /// fn foo(interned: Rc<str>) { ... }
 247     /// ```
 248     pub RC_BUFFER,
 249     restriction,
 250     "shared ownership of a buffer type"
 251 }
 252
 253 pub struct Types {
 254     vec_box_size_threshold: u64,
 255 }
 256
 257 impl_lint_pass!(Types => [BOX_VEC, VEC_BOX, OPTION_OPTION, LINKEDLIST, BORROWED_BOX, REDUNDANT_ALLOCATION, RC_BUFFER]);
 258
 259 impl<'tcx> LateLintPass<'tcx> for Types {
 260     fn check_fn(&mut self, cx: &LateContext<'_>, _: FnKind<'_>, decl: &FnDecl<'_>, _: &Body<'_>, _: Span, id: HirId) {
 261         // Skip trait implementations; see issue #605.
 262         if let Some(hir::Node::Item(item)) = cx.tcx.hir().find(cx.tcx.hir().get_parent_item(id)) {
 263             if let ItemKind::Impl(hir::Impl { of_trait: Some(_), .. }) = item.kind {
 264                 return;
 265             }
 266         }
 267
 268         self.check_fn_decl(cx, decl);
 269     }
 270
 271     fn check_field_def(&mut self, cx: &LateContext<'_>, field: &hir::FieldDef<'_>) {
 272         self.check_ty(cx, &field.ty, false);
 273     }
 274
 275     fn check_trait_item(&mut self, cx: &LateContext<'_>, item: &TraitItem<'_>) {
 276         match item.kind {
 277             TraitItemKind::Const(ref ty, _) | TraitItemKind::Type(_, Some(ref ty)) => self.check_ty(cx, ty, false),
 278             TraitItemKind::Fn(ref sig, _) => self.check_fn_decl(cx, &sig.decl),
 279             TraitItemKind::Type(..) => (),
 280         }
 281     }
 282
 283     fn check_local(&mut self, cx: &LateContext<'_>, local: &Local<'_>) {
 284         if let Some(ref ty) = local.ty {
 285             self.check_ty(cx, ty, true);
 286         }
 287     }
 288 }
 289
 290 impl Types {
 291     pub fn new(vec_box_size_threshold: u64) -> Self {
 292         Self { vec_box_size_threshold }
 293     }
 294
 295     fn check_fn_decl(&mut self, cx: &LateContext<'_>, decl: &FnDecl<'_>) {
 296         for input in decl.inputs {
 297             self.check_ty(cx, input, false);
 298         }
 299
 300         if let FnRetTy::Return(ref ty) = decl.output {
 301             self.check_ty(cx, ty, false);
 302         }
 303     }
 304
 305     /// Recursively check for `TypePass` lints in the given type. Stop at the first
 306     /// lint found.
 307     ///
 308     /// The parameter `is_local` distinguishes the context of the type.
 309     fn check_ty(&mut self, cx: &LateContext<'_>, hir_ty: &hir::Ty<'_>, is_local: bool) {
 310         if hir_ty.span.from_expansion() {
 311             return;
 312         }
 313         match hir_ty.kind {
 314             TyKind::Path(ref qpath) if !is_local => {
 315                 let hir_id = hir_ty.hir_id;
 316                 let res = cx.qpath_res(qpath, hir_id);
 317                 if let Some(def_id) = res.opt_def_id() {
 318                     let mut triggered = false;
 319                     triggered |= box_vec::check(cx, hir_ty, qpath, def_id);
 320                     triggered |= redundant_allocation::check(cx, hir_ty, qpath, def_id);
 321                     triggered |= rc_buffer::check(cx, hir_ty, qpath, def_id);
 322                     triggered |= vec_box::check(cx, hir_ty, qpath, def_id, self.vec_box_size_threshold);
 323                     triggered |= option_option::check(cx, hir_ty, qpath, def_id);
 324                     triggered |= linked_list::check(cx, hir_ty, def_id);
 325
 326                     if triggered {
 327                         return;
 328                     }
 329                 }
 330                 match *qpath {
 331                     QPath::Resolved(Some(ref ty), ref p) => {
 332                         self.check_ty(cx, ty, is_local);
 333                         for ty in p.segments.iter().flat_map(|seg| {
 334                             seg.args
 335                                 .as_ref()
 336                                 .map_or_else(|| [].iter(), |params| params.args.iter())
 337                                 .filter_map(|arg| match arg {
 338                                     GenericArg::Type(ty) => Some(ty),
 339                                     _ => None,
 340                                 })
 341                         }) {
 342                             self.check_ty(cx, ty, is_local);
 343                         }
 344                     },
 345                     QPath::Resolved(None, ref p) => {
 346                         for ty in p.segments.iter().flat_map(|seg| {
 347                             seg.args
 348                                 .as_ref()
 349                                 .map_or_else(|| [].iter(), |params| params.args.iter())
 350                                 .filter_map(|arg| match arg {
 351                                     GenericArg::Type(ty) => Some(ty),
 352                                     _ => None,
 353                                 })
 354                         }) {
 355                             self.check_ty(cx, ty, is_local);
 356                         }
 357                     },
 358                     QPath::TypeRelative(ref ty, ref seg) => {
 359                         self.check_ty(cx, ty, is_local);
 360                         if let Some(ref params) = seg.args {
 361                             for ty in params.args.iter().filter_map(|arg| match arg {
 362                                 GenericArg::Type(ty) => Some(ty),
 363                                 _ => None,
 364                             }) {
 365                                 self.check_ty(cx, ty, is_local);
 366                             }
 367                         }
 368                     },
 369                     QPath::LangItem(..) => {},
 370                 }
 371             },
 372             TyKind::Rptr(ref lt, ref mut_ty) => {
 373                 if !borrowed_box::check(cx, hir_ty, lt, mut_ty) {
 374                     self.check_ty(cx, &mut_ty.ty, is_local);
 375                 }
 376             },
 377             TyKind::Slice(ref ty) | TyKind::Array(ref ty, _) | TyKind::Ptr(MutTy { ref ty, .. }) => {
 378                 self.check_ty(cx, ty, is_local)
 379             },
 380             TyKind::Tup(tys) => {
 381                 for ty in tys {
 382                     self.check_ty(cx, ty, is_local);
 383                 }
 384             },
 385             _ => {},
 386         }
 387     }
 388 }
 389
 390 declare_clippy_lint! {
 391     /// **What it does:** Checks for types used in structs, parameters and `let`
 392     /// declarations above a certain complexity threshold.
 393     ///
 394     /// **Why is this bad?** Too complex types make the code less readable. Consider
 395     /// using a `type` definition to simplify them.
 396     ///
 397     /// **Known problems:** None.
 398     ///
 399     /// **Example:**
 400     /// ```rust
 401     /// # use std::rc::Rc;
 402     /// struct Foo {
 403     ///     inner: Rc<Vec<Vec<Box<(u32, u32, u32, u32)>>>>,
 404     /// }
 405     /// ```
 406     pub TYPE_COMPLEXITY,
 407     complexity,
 408     "usage of very complex types that might be better factored into `type` definitions"
 409 }
 410
 411 pub struct TypeComplexity {
 412     threshold: u64,
 413 }
 414
 415 impl TypeComplexity {
 416     #[must_use]
 417     pub fn new(threshold: u64) -> Self {
 418         Self { threshold }
 419     }
 420 }
 421
 422 impl_lint_pass!(TypeComplexity => [TYPE_COMPLEXITY]);
 423
 424 impl<'tcx> LateLintPass<'tcx> for TypeComplexity {
 425     fn check_fn(
 426         &mut self,
 427         cx: &LateContext<'tcx>,
 428         _: FnKind<'tcx>,
 429         decl: &'tcx FnDecl<'_>,
 430         _: &'tcx Body<'_>,
 431         _: Span,
 432         _: HirId,
 433     ) {
 434         self.check_fndecl(cx, decl);
 435     }
 436
 437     fn check_field_def(&mut self, cx: &LateContext<'tcx>, field: &'tcx hir::FieldDef<'_>) {
 438         // enum variants are also struct fields now
 439         self.check_type(cx, &field.ty);
 440     }
 441
 442     fn check_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx Item<'_>) {
 443         match item.kind {
 444             ItemKind::Static(ref ty, _, _) | ItemKind::Const(ref ty, _) => self.check_type(cx, ty),
 445             // functions, enums, structs, impls and traits are covered
 446             _ => (),
 447         }
 448     }
 449
 450     fn check_trait_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx TraitItem<'_>) {
 451         match item.kind {
 452             TraitItemKind::Const(ref ty, _) | TraitItemKind::Type(_, Some(ref ty)) => self.check_type(cx, ty),
 453             TraitItemKind::Fn(FnSig { ref decl, .. }, TraitFn::Required(_)) => self.check_fndecl(cx, decl),
 454             // methods with default impl are covered by check_fn
 455             TraitItemKind::Type(..) | TraitItemKind::Fn(_, TraitFn::Provided(_)) => (),
 456         }
 457     }
 458
 459     fn check_impl_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx ImplItem<'_>) {
 460         match item.kind {
 461             ImplItemKind::Const(ref ty, _) | ImplItemKind::TyAlias(ref ty) => self.check_type(cx, ty),
 462             // methods are covered by check_fn
 463             ImplItemKind::Fn(..) => (),
 464         }
 465     }
 466
 467     fn check_local(&mut self, cx: &LateContext<'tcx>, local: &'tcx Local<'_>) {
 468         if let Some(ref ty) = local.ty {
 469             self.check_type(cx, ty);
 470         }
 471     }
 472 }
 473
 474 impl<'tcx> TypeComplexity {
 475     fn check_fndecl(&self, cx: &LateContext<'tcx>, decl: &'tcx FnDecl<'_>) {
 476         for arg in decl.inputs {
 477             self.check_type(cx, arg);
 478         }
 479         if let FnRetTy::Return(ref ty) = decl.output {
 480             self.check_type(cx, ty);
 481         }
 482     }
 483
 484     fn check_type(&self, cx: &LateContext<'_>, ty: &hir::Ty<'_>) {
 485         if ty.span.from_expansion() {
 486             return;
 487         }
 488         let score = {
 489             let mut visitor = TypeComplexityVisitor { score: 0, nest: 1 };
 490             visitor.visit_ty(ty);
 491             visitor.score
 492         };
 493
 494         if score > self.threshold {
 495             span_lint(
 496                 cx,
 497                 TYPE_COMPLEXITY,
 498                 ty.span,
 499                 "very complex type used. Consider factoring parts into `type` definitions",
 500             );
 501         }
 502     }
 503 }
 504
 505 /// Walks a type and assigns a complexity score to it.
 506 struct TypeComplexityVisitor {
 507     /// total complexity score of the type
 508     score: u64,
 509     /// current nesting level
 510     nest: u64,
 511 }
 512
 513 impl<'tcx> Visitor<'tcx> for TypeComplexityVisitor {
 514     type Map = Map<'tcx>;
 515
 516     fn visit_ty(&mut self, ty: &'tcx hir::Ty<'_>) {
 517         let (add_score, sub_nest) = match ty.kind {
 518             // _, &x and *x have only small overhead; don't mess with nesting level
 519             TyKind::Infer | TyKind::Ptr(..) | TyKind::Rptr(..) => (1, 0),
 520
 521             // the "normal" components of a type: named types, arrays/tuples
 522             TyKind::Path(..) | TyKind::Slice(..) | TyKind::Tup(..) | TyKind::Array(..) => (10 * self.nest, 1),
 523
 524             // function types bring a lot of overhead
 525             TyKind::BareFn(ref bare) if bare.abi == Abi::Rust => (50 * self.nest, 1),
 526
 527             TyKind::TraitObject(ref param_bounds, _, _) => {
 528                 let has_lifetime_parameters = param_bounds.iter().any(|bound| {
 529                     bound
 530                         .bound_generic_params
 531                         .iter()
 532                         .any(|gen| matches!(gen.kind, GenericParamKind::Lifetime { .. }))
 533                 });
 534                 if has_lifetime_parameters {
 535                     // complex trait bounds like A<'a, 'b>
 536                     (50 * self.nest, 1)
 537                 } else {
 538                     // simple trait bounds like A + B
 539                     (20 * self.nest, 0)
 540                 }
 541             },
 542
 543             _ => (0, 0),
 544         };
 545         self.score += add_score;
 546         self.nest += sub_nest;
 547         walk_ty(self, ty);
 548         self.nest -= sub_nest;
 549     }
 550     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 551         NestedVisitorMap::None
 552     }
 553 }
 554
 555 declare_clippy_lint! {
 556     /// **What it does:** Checks for comparisons where the relation is always either
 557     /// true or false, but where one side has been upcast so that the comparison is
 558     /// necessary. Only integer types are checked.
 559     ///
 560     /// **Why is this bad?** An expression like `let x : u8 = ...; (x as u32) > 300`
 561     /// will mistakenly imply that it is possible for `x` to be outside the range of
 562     /// `u8`.
 563     ///
 564     /// **Known problems:**
 565     /// https://github.com/rust-lang/rust-clippy/issues/886
 566     ///
 567     /// **Example:**
 568     /// ```rust
 569     /// let x: u8 = 1;
 570     /// (x as u32) > 300;
 571     /// ```
 572     pub INVALID_UPCAST_COMPARISONS,
 573     pedantic,
 574     "a comparison involving an upcast which is always true or false"
 575 }
 576
 577 declare_lint_pass!(InvalidUpcastComparisons => [INVALID_UPCAST_COMPARISONS]);
 578
 579 #[derive(Copy, Clone, Debug, Eq)]
 580 enum FullInt {
 581     S(i128),
 582     U(u128),
 583 }
 584
 585 impl FullInt {
 586     #[allow(clippy::cast_sign_loss)]
 587     #[must_use]
 588     fn cmp_s_u(s: i128, u: u128) -> Ordering {
 589         if s < 0 {
 590             Ordering::Less
 591         } else if u > (i128::MAX as u128) {
 592             Ordering::Greater
 593         } else {
 594             (s as u128).cmp(&u)
 595         }
 596     }
 597 }
 598
 599 impl PartialEq for FullInt {
 600     #[must_use]
 601     fn eq(&self, other: &Self) -> bool {
 602         self.partial_cmp(other).expect("`partial_cmp` only returns `Some(_)`") == Ordering::Equal
 603     }
 604 }
 605
 606 impl PartialOrd for FullInt {
 607     #[must_use]
 608     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 609         Some(match (self, other) {
 610             (&Self::S(s), &Self::S(o)) => s.cmp(&o),
 611             (&Self::U(s), &Self::U(o)) => s.cmp(&o),
 612             (&Self::S(s), &Self::U(o)) => Self::cmp_s_u(s, o),
 613             (&Self::U(s), &Self::S(o)) => Self::cmp_s_u(o, s).reverse(),
 614         })
 615     }
 616 }
 617
 618 impl Ord for FullInt {
 619     #[must_use]
 620     fn cmp(&self, other: &Self) -> Ordering {
 621         self.partial_cmp(other)
 622             .expect("`partial_cmp` for FullInt can never return `None`")
 623     }
 624 }
 625
 626 fn numeric_cast_precast_bounds<'a>(cx: &LateContext<'_>, expr: &'a Expr<'_>) -> Option<(FullInt, FullInt)> {
 627     if let ExprKind::Cast(ref cast_exp, _) = expr.kind {
 628         let pre_cast_ty = cx.typeck_results().expr_ty(cast_exp);
 629         let cast_ty = cx.typeck_results().expr_ty(expr);
 630         // if it's a cast from i32 to u32 wrapping will invalidate all these checks
 631         if cx.layout_of(pre_cast_ty).ok().map(|l| l.size) == cx.layout_of(cast_ty).ok().map(|l| l.size) {
 632             return None;
 633         }
 634         match pre_cast_ty.kind() {
 635             ty::Int(int_ty) => Some(match int_ty {
 636                 IntTy::I8 => (FullInt::S(i128::from(i8::MIN)), FullInt::S(i128::from(i8::MAX))),
 637                 IntTy::I16 => (FullInt::S(i128::from(i16::MIN)), FullInt::S(i128::from(i16::MAX))),
 638                 IntTy::I32 => (FullInt::S(i128::from(i32::MIN)), FullInt::S(i128::from(i32::MAX))),
 639                 IntTy::I64 => (FullInt::S(i128::from(i64::MIN)), FullInt::S(i128::from(i64::MAX))),
 640                 IntTy::I128 => (FullInt::S(i128::MIN), FullInt::S(i128::MAX)),
 641                 IntTy::Isize => (FullInt::S(isize::MIN as i128), FullInt::S(isize::MAX as i128)),
 642             }),
 643             ty::Uint(uint_ty) => Some(match uint_ty {
 644                 UintTy::U8 => (FullInt::U(u128::from(u8::MIN)), FullInt::U(u128::from(u8::MAX))),
 645                 UintTy::U16 => (FullInt::U(u128::from(u16::MIN)), FullInt::U(u128::from(u16::MAX))),
 646                 UintTy::U32 => (FullInt::U(u128::from(u32::MIN)), FullInt::U(u128::from(u32::MAX))),
 647                 UintTy::U64 => (FullInt::U(u128::from(u64::MIN)), FullInt::U(u128::from(u64::MAX))),
 648                 UintTy::U128 => (FullInt::U(u128::MIN), FullInt::U(u128::MAX)),
 649                 UintTy::Usize => (FullInt::U(usize::MIN as u128), FullInt::U(usize::MAX as u128)),
 650             }),
 651             _ => None,
 652         }
 653     } else {
 654         None
 655     }
 656 }
 657
 658 fn node_as_const_fullint<'tcx>(cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) -> Option<FullInt> {
 659     let val = constant(cx, cx.typeck_results(), expr)?.0;
 660     if let Constant::Int(const_int) = val {
 661         match *cx.typeck_results().expr_ty(expr).kind() {
 662             ty::Int(ity) => Some(FullInt::S(sext(cx.tcx, const_int, ity))),
 663             ty::Uint(_) => Some(FullInt::U(const_int)),
 664             _ => None,
 665         }
 666     } else {
 667         None
 668     }
 669 }
 670
 671 fn err_upcast_comparison(cx: &LateContext<'_>, span: Span, expr: &Expr<'_>, always: bool) {
 672     if let ExprKind::Cast(ref cast_val, _) = expr.kind {
 673         span_lint(
 674             cx,
 675             INVALID_UPCAST_COMPARISONS,
 676             span,
 677             &format!(
 678                 "because of the numeric bounds on `{}` prior to casting, this expression is always {}",
 679                 snippet(cx, cast_val.span, "the expression"),
 680                 if always { "true" } else { "false" },
 681             ),
 682         );
 683     }
 684 }
 685
 686 fn upcast_comparison_bounds_err<'tcx>(
 687     cx: &LateContext<'tcx>,
 688     span: Span,
 689     rel: comparisons::Rel,
 690     lhs_bounds: Option<(FullInt, FullInt)>,
 691     lhs: &'tcx Expr<'_>,
 692     rhs: &'tcx Expr<'_>,
 693     invert: bool,
 694 ) {
 695     use clippy_utils::comparisons::Rel;
 696
 697     if let Some((lb, ub)) = lhs_bounds {
 698         if let Some(norm_rhs_val) = node_as_const_fullint(cx, rhs) {
 699             if rel == Rel::Eq || rel == Rel::Ne {
 700                 if norm_rhs_val < lb || norm_rhs_val > ub {
 701                     err_upcast_comparison(cx, span, lhs, rel == Rel::Ne);
 702                 }
 703             } else if match rel {
 704                 Rel::Lt => {
 705                     if invert {
 706                         norm_rhs_val < lb
 707                     } else {
 708                         ub < norm_rhs_val
 709                     }
 710                 },
 711                 Rel::Le => {
 712                     if invert {
 713                         norm_rhs_val <= lb
 714                     } else {
 715                         ub <= norm_rhs_val
 716                     }
 717                 },
 718                 Rel::Eq | Rel::Ne => unreachable!(),
 719             } {
 720                 err_upcast_comparison(cx, span, lhs, true)
 721             } else if match rel {
 722                 Rel::Lt => {
 723                     if invert {
 724                         norm_rhs_val >= ub
 725                     } else {
 726                         lb >= norm_rhs_val
 727                     }
 728                 },
 729                 Rel::Le => {
 730                     if invert {
 731                         norm_rhs_val > ub
 732                     } else {
 733                         lb > norm_rhs_val
 734                     }
 735                 },
 736                 Rel::Eq | Rel::Ne => unreachable!(),
 737             } {
 738                 err_upcast_comparison(cx, span, lhs, false)
 739             }
 740         }
 741     }
 742 }
 743
 744 impl<'tcx> LateLintPass<'tcx> for InvalidUpcastComparisons {
 745     fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
 746         if let ExprKind::Binary(ref cmp, ref lhs, ref rhs) = expr.kind {
 747             let normalized = comparisons::normalize_comparison(cmp.node, lhs, rhs);
 748             let (rel, normalized_lhs, normalized_rhs) = if let Some(val) = normalized {
 749                 val
 750             } else {
 751                 return;
 752             };
 753
 754             let lhs_bounds = numeric_cast_precast_bounds(cx, normalized_lhs);
 755             let rhs_bounds = numeric_cast_precast_bounds(cx, normalized_rhs);
 756
 757             upcast_comparison_bounds_err(cx, expr.span, rel, lhs_bounds, normalized_lhs, normalized_rhs, false);
 758             upcast_comparison_bounds_err(cx, expr.span, rel, rhs_bounds, normalized_rhs, normalized_lhs, true);
 759         }
 760     }
 761 }
 762
 763 declare_clippy_lint! {
 764     /// **What it does:** Checks for public `impl` or `fn` missing generalization
 765     /// over different hashers and implicitly defaulting to the default hashing
 766     /// algorithm (`SipHash`).
 767     ///
 768     /// **Why is this bad?** `HashMap` or `HashSet` with custom hashers cannot be
 769     /// used with them.
 770     ///
 771     /// **Known problems:** Suggestions for replacing constructors can contain
 772     /// false-positives. Also applying suggestions can require modification of other
 773     /// pieces of code, possibly including external crates.
 774     ///
 775     /// **Example:**
 776     /// ```rust
 777     /// # use std::collections::HashMap;
 778     /// # use std::hash::{Hash, BuildHasher};
 779     /// # trait Serialize {};
 780     /// impl<K: Hash + Eq, V> Serialize for HashMap<K, V> { }
 781     ///
 782     /// pub fn foo(map: &mut HashMap<i32, i32>) { }
 783     /// ```
 784     /// could be rewritten as
 785     /// ```rust
 786     /// # use std::collections::HashMap;
 787     /// # use std::hash::{Hash, BuildHasher};
 788     /// # trait Serialize {};
 789     /// impl<K: Hash + Eq, V, S: BuildHasher> Serialize for HashMap<K, V, S> { }
 790     ///
 791     /// pub fn foo<S: BuildHasher>(map: &mut HashMap<i32, i32, S>) { }
 792     /// ```
 793     pub IMPLICIT_HASHER,
 794     pedantic,
 795     "missing generalization over different hashers"
 796 }
 797
 798 declare_lint_pass!(ImplicitHasher => [IMPLICIT_HASHER]);
 799
 800 impl<'tcx> LateLintPass<'tcx> for ImplicitHasher {
 801     #[allow(clippy::cast_possible_truncation, clippy::too_many_lines)]
 802     fn check_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx Item<'_>) {
 803         use rustc_span::BytePos;
 804
 805         fn suggestion<'tcx>(
 806             cx: &LateContext<'tcx>,
 807             diag: &mut DiagnosticBuilder<'_>,
 808             generics_span: Span,
 809             generics_suggestion_span: Span,
 810             target: &ImplicitHasherType<'_>,
 811             vis: ImplicitHasherConstructorVisitor<'_, '_, '_>,
 812         ) {
 813             let generics_snip = snippet(cx, generics_span, "");
 814             // trim `<` `>`
 815             let generics_snip = if generics_snip.is_empty() {
 816                 ""
 817             } else {
 818                 &generics_snip[1..generics_snip.len() - 1]
 819             };
 820
 821             multispan_sugg(
 822                 diag,
 823                 "consider adding a type parameter",
 824                 vec![
 825                     (
 826                         generics_suggestion_span,
 827                         format!(
 828                             "<{}{}S: ::std::hash::BuildHasher{}>",
 829                             generics_snip,
 830                             if generics_snip.is_empty() { "" } else { ", " },
 831                             if vis.suggestions.is_empty() {
 832                                 ""
 833                             } else {
 834                                 // request users to add `Default` bound so that generic constructors can be used
 835                                 " + Default"
 836                             },
 837                         ),
 838                     ),
 839                     (
 840                         target.span(),
 841                         format!("{}<{}, S>", target.type_name(), target.type_arguments(),),
 842                     ),
 843                 ],
 844             );
 845
 846             if !vis.suggestions.is_empty() {
 847                 multispan_sugg(diag, "...and use generic constructor", vis.suggestions);
 848             }
 849         }
 850
 851         if !cx.access_levels.is_exported(item.hir_id()) {
 852             return;
 853         }
 854
 855         match item.kind {
 856             ItemKind::Impl(ref impl_) => {
 857                 let mut vis = ImplicitHasherTypeVisitor::new(cx);
 858                 vis.visit_ty(impl_.self_ty);
 859
 860                 for target in &vis.found {
 861                     if differing_macro_contexts(item.span, target.span()) {
 862                         return;
 863                     }
 864
 865                     let generics_suggestion_span = impl_.generics.span.substitute_dummy({
 866                         let pos = snippet_opt(cx, item.span.until(target.span()))
 867                             .and_then(|snip| Some(item.span.lo() + BytePos(snip.find("impl")? as u32 + 4)));
 868                         if let Some(pos) = pos {
 869                             Span::new(pos, pos, item.span.data().ctxt)
 870                         } else {
 871                             return;
 872                         }
 873                     });
 874
 875                     let mut ctr_vis = ImplicitHasherConstructorVisitor::new(cx, target);
 876                     for item in impl_.items.iter().map(|item| cx.tcx.hir().impl_item(item.id)) {
 877                         ctr_vis.visit_impl_item(item);
 878                     }
 879
 880                     span_lint_and_then(
 881                         cx,
 882                         IMPLICIT_HASHER,
 883                         target.span(),
 884                         &format!(
 885                             "impl for `{}` should be generalized over different hashers",
 886                             target.type_name()
 887                         ),
 888                         move |diag| {
 889                             suggestion(cx, diag, impl_.generics.span, generics_suggestion_span, target, ctr_vis);
 890                         },
 891                     );
 892                 }
 893             },
 894             ItemKind::Fn(ref sig, ref generics, body_id) => {
 895                 let body = cx.tcx.hir().body(body_id);
 896
 897                 for ty in sig.decl.inputs {
 898                     let mut vis = ImplicitHasherTypeVisitor::new(cx);
 899                     vis.visit_ty(ty);
 900
 901                     for target in &vis.found {
 902                         if in_external_macro(cx.sess(), generics.span) {
 903                             continue;
 904                         }
 905                         let generics_suggestion_span = generics.span.substitute_dummy({
 906                             let pos = snippet_opt(cx, item.span.until(body.params[0].pat.span))
 907                                 .and_then(|snip| {
 908                                     let i = snip.find("fn")?;
 909                                     Some(item.span.lo() + BytePos((i + (&snip[i..]).find('(')?) as u32))
 910                                 })
 911                                 .expect("failed to create span for type parameters");
 912                             Span::new(pos, pos, item.span.data().ctxt)
 913                         });
 914
 915                         let mut ctr_vis = ImplicitHasherConstructorVisitor::new(cx, target);
 916                         ctr_vis.visit_body(body);
 917
 918                         span_lint_and_then(
 919                             cx,
 920                             IMPLICIT_HASHER,
 921                             target.span(),
 922                             &format!(
 923                                 "parameter of type `{}` should be generalized over different hashers",
 924                                 target.type_name()
 925                             ),
 926                             move |diag| {
 927                                 suggestion(cx, diag, generics.span, generics_suggestion_span, target, ctr_vis);
 928                             },
 929                         );
 930                     }
 931                 }
 932             },
 933             _ => {},
 934         }
 935     }
 936 }
 937
 938 enum ImplicitHasherType<'tcx> {
 939     HashMap(Span, Ty<'tcx>, Cow<'static, str>, Cow<'static, str>),
 940     HashSet(Span, Ty<'tcx>, Cow<'static, str>),
 941 }
 942
 943 impl<'tcx> ImplicitHasherType<'tcx> {
 944     /// Checks that `ty` is a target type without a `BuildHasher`.
 945     fn new(cx: &LateContext<'tcx>, hir_ty: &hir::Ty<'_>) -> Option<Self> {
 946         if let TyKind::Path(QPath::Resolved(None, ref path)) = hir_ty.kind {
 947             let params: Vec<_> = path
 948                 .segments
 949                 .last()
 950                 .as_ref()?
 951                 .args
 952                 .as_ref()?
 953                 .args
 954                 .iter()
 955                 .filter_map(|arg| match arg {
 956                     GenericArg::Type(ty) => Some(ty),
 957                     _ => None,
 958                 })
 959                 .collect();
 960             let params_len = params.len();
 961
 962             let ty = hir_ty_to_ty(cx.tcx, hir_ty);
 963
 964             if is_type_diagnostic_item(cx, ty, sym::hashmap_type) && params_len == 2 {
 965                 Some(ImplicitHasherType::HashMap(
 966                     hir_ty.span,
 967                     ty,
 968                     snippet(cx, params[0].span, "K"),
 969                     snippet(cx, params[1].span, "V"),
 970                 ))
 971             } else if is_type_diagnostic_item(cx, ty, sym::hashset_type) && params_len == 1 {
 972                 Some(ImplicitHasherType::HashSet(
 973                     hir_ty.span,
 974                     ty,
 975                     snippet(cx, params[0].span, "T"),
 976                 ))
 977             } else {
 978                 None
 979             }
 980         } else {
 981             None
 982         }
 983     }
 984
 985     fn type_name(&self) -> &'static str {
 986         match *self {
 987             ImplicitHasherType::HashMap(..) => "HashMap",
 988             ImplicitHasherType::HashSet(..) => "HashSet",
 989         }
 990     }
 991
 992     fn type_arguments(&self) -> String {
 993         match *self {
 994             ImplicitHasherType::HashMap(.., ref k, ref v) => format!("{}, {}", k, v),
 995             ImplicitHasherType::HashSet(.., ref t) => format!("{}", t),
 996         }
 997     }
 998
 999     fn ty(&self) -> Ty<'tcx> {
1000         match *self {
1001             ImplicitHasherType::HashMap(_, ty, ..) | ImplicitHasherType::HashSet(_, ty, ..) => ty,
1002         }
1003     }
1004
1005     fn span(&self) -> Span {
1006         match *self {
1007             ImplicitHasherType::HashMap(span, ..) | ImplicitHasherType::HashSet(span, ..) => span,
1008         }
1009     }
1010 }
1011
1012 struct ImplicitHasherTypeVisitor<'a, 'tcx> {
1013     cx: &'a LateContext<'tcx>,
1014     found: Vec<ImplicitHasherType<'tcx>>,
1015 }
1016
1017 impl<'a, 'tcx> ImplicitHasherTypeVisitor<'a, 'tcx> {
1018     fn new(cx: &'a LateContext<'tcx>) -> Self {
1019         Self { cx, found: vec![] }
1020     }
1021 }
1022
1023 impl<'a, 'tcx> Visitor<'tcx> for ImplicitHasherTypeVisitor<'a, 'tcx> {
1024     type Map = Map<'tcx>;
1025
1026     fn visit_ty(&mut self, t: &'tcx hir::Ty<'_>) {
1027         if let Some(target) = ImplicitHasherType::new(self.cx, t) {
1028             self.found.push(target);
1029         }
1030
1031         walk_ty(self, t);
1032     }
1033
1034     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
1035         NestedVisitorMap::None
1036     }
1037 }
1038
1039 /// Looks for default-hasher-dependent constructors like `HashMap::new`.
1040 struct ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
1041     cx: &'a LateContext<'tcx>,
1042     maybe_typeck_results: Option<&'tcx TypeckResults<'tcx>>,
1043     target: &'b ImplicitHasherType<'tcx>,
1044     suggestions: BTreeMap<Span, String>,
1045 }
1046
1047 impl<'a, 'b, 'tcx> ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
1048     fn new(cx: &'a LateContext<'tcx>, target: &'b ImplicitHasherType<'tcx>) -> Self {
1049         Self {
1050             cx,
1051             maybe_typeck_results: cx.maybe_typeck_results(),
1052             target,
1053             suggestions: BTreeMap::new(),
1054         }
1055     }
1056 }
1057
1058 impl<'a, 'b, 'tcx> Visitor<'tcx> for ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
1059     type Map = Map<'tcx>;
1060
1061     fn visit_body(&mut self, body: &'tcx Body<'_>) {
1062         let old_maybe_typeck_results = self.maybe_typeck_results.replace(self.cx.tcx.typeck_body(body.id()));
1063         walk_body(self, body);
1064         self.maybe_typeck_results = old_maybe_typeck_results;
1065     }
1066
1067     fn visit_expr(&mut self, e: &'tcx Expr<'_>) {
1068         if_chain! {
1069             if let ExprKind::Call(ref fun, ref args) = e.kind;
1070             if let ExprKind::Path(QPath::TypeRelative(ref ty, ref method)) = fun.kind;
1071             if let TyKind::Path(QPath::Resolved(None, ty_path)) = ty.kind;
1072             then {
1073                 if !TyS::same_type(self.target.ty(), self.maybe_typeck_results.unwrap().expr_ty(e)) {
1074                     return;
1075                 }
1076
1077                 if match_path(ty_path, &paths::HASHMAP) {
1078                     if method.ident.name == sym::new {
1079                         self.suggestions
1080                             .insert(e.span, "HashMap::default()".to_string());
1081                     } else if method.ident.name == sym!(with_capacity) {
1082                         self.suggestions.insert(
1083                             e.span,
1084                             format!(
1085                                 "HashMap::with_capacity_and_hasher({}, Default::default())",
1086                                 snippet(self.cx, args[0].span, "capacity"),
1087                             ),
1088                         );
1089                     }
1090                 } else if match_path(ty_path, &paths::HASHSET) {
1091                     if method.ident.name == sym::new {
1092                         self.suggestions
1093                             .insert(e.span, "HashSet::default()".to_string());
1094                     } else if method.ident.name == sym!(with_capacity) {
1095                         self.suggestions.insert(
1096                             e.span,
1097                             format!(
1098                                 "HashSet::with_capacity_and_hasher({}, Default::default())",
1099                                 snippet(self.cx, args[0].span, "capacity"),
1100                             ),
1101                         );
1102                     }
1103                 }
1104             }
1105         }
1106
1107         walk_expr(self, e);
1108     }
1109
1110     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
1111         NestedVisitorMap::OnlyBodies(self.cx.tcx.hir())
1112     }
1113 }