clippy_lints/src/stable_sort_primitive.rs

   1 use crate::utils::{is_slice_of_primitives, sugg::Sugg};
   2 use clippy_utils::diagnostics::span_lint_and_then;
   3
   4 use if_chain::if_chain;
   5
   6 use rustc_errors::Applicability;
   7 use rustc_hir::{Expr, ExprKind};
   8 use rustc_lint::{LateContext, LateLintPass};
   9 use rustc_session::{declare_lint_pass, declare_tool_lint};
  10
  11 declare_clippy_lint! {
  12     /// **What it does:**
  13     /// When sorting primitive values (integers, bools, chars, as well
  14     /// as arrays, slices, and tuples of such items), it is better to
  15     /// use an unstable sort than a stable sort.
  16     ///
  17     /// **Why is this bad?**
  18     /// Using a stable sort consumes more memory and cpu cycles. Because
  19     /// values which compare equal are identical, preserving their
  20     /// relative order (the guarantee that a stable sort provides) means
  21     /// nothing, while the extra costs still apply.
  22     ///
  23     /// **Known problems:**
  24     /// None
  25     ///
  26     /// **Example:**
  27     ///
  28     /// ```rust
  29     /// let mut vec = vec![2, 1, 3];
  30     /// vec.sort();
  31     /// ```
  32     /// Use instead:
  33     /// ```rust
  34     /// let mut vec = vec![2, 1, 3];
  35     /// vec.sort_unstable();
  36     /// ```
  37     pub STABLE_SORT_PRIMITIVE,
  38     perf,
  39     "use of sort() when sort_unstable() is equivalent"
  40 }
  41
  42 declare_lint_pass!(StableSortPrimitive => [STABLE_SORT_PRIMITIVE]);
  43
  44 /// The three "kinds" of sorts
  45 enum SortingKind {
  46     Vanilla,
  47     /* The other kinds of lint are currently commented out because they
  48      * can map distinct values to equal ones. If the key function is
  49      * provably one-to-one, or if the Cmp function conserves equality,
  50      * then they could be linted on, but I don't know if we can check
  51      * for that. */
  52
  53     /* ByKey,
  54      * ByCmp, */
  55 }
  56 impl SortingKind {
  57     /// The name of the stable version of this kind of sort
  58     fn stable_name(&self) -> &str {
  59         match self {
  60             SortingKind::Vanilla => "sort",
  61             /* SortingKind::ByKey => "sort_by_key",
  62              * SortingKind::ByCmp => "sort_by", */
  63         }
  64     }
  65     /// The name of the unstable version of this kind of sort
  66     fn unstable_name(&self) -> &str {
  67         match self {
  68             SortingKind::Vanilla => "sort_unstable",
  69             /* SortingKind::ByKey => "sort_unstable_by_key",
  70              * SortingKind::ByCmp => "sort_unstable_by", */
  71         }
  72     }
  73     /// Takes the name of a function call and returns the kind of sort
  74     /// that corresponds to that function name (or None if it isn't)
  75     fn from_stable_name(name: &str) -> Option<SortingKind> {
  76         match name {
  77             "sort" => Some(SortingKind::Vanilla),
  78             // "sort_by" => Some(SortingKind::ByCmp),
  79             // "sort_by_key" => Some(SortingKind::ByKey),
  80             _ => None,
  81         }
  82     }
  83 }
  84
  85 /// A detected instance of this lint
  86 struct LintDetection {
  87     slice_name: String,
  88     method: SortingKind,
  89     method_args: String,
  90     slice_type: String,
  91 }
  92
  93 fn detect_stable_sort_primitive(cx: &LateContext<'_>, expr: &Expr<'_>) -> Option<LintDetection> {
  94     if_chain! {
  95         if let ExprKind::MethodCall(method_name, _, args, _) = &expr.kind;
  96         if let Some(slice) = &args.get(0);
  97         if let Some(method) = SortingKind::from_stable_name(&method_name.ident.name.as_str());
  98         if let Some(slice_type) = is_slice_of_primitives(cx, slice);
  99         then {
 100             let args_str = args.iter().skip(1).map(|arg| Sugg::hir(cx, arg, "..").to_string()).collect::<Vec<String>>().join(", ");
 101             Some(LintDetection { slice_name: Sugg::hir(cx, slice, "..").to_string(), method, method_args: args_str, slice_type })
 102         } else {
 103             None
 104         }
 105     }
 106 }
 107
 108 impl LateLintPass<'_> for StableSortPrimitive {
 109     fn check_expr(&mut self, cx: &LateContext<'_>, expr: &Expr<'_>) {
 110         if let Some(detection) = detect_stable_sort_primitive(cx, expr) {
 111             span_lint_and_then(
 112                 cx,
 113                 STABLE_SORT_PRIMITIVE,
 114                 expr.span,
 115                 format!(
 116                     "used `{}` on primitive type `{}`",
 117                     detection.method.stable_name(),
 118                     detection.slice_type,
 119                 )
 120                 .as_str(),
 121                 |diag| {
 122                     diag.span_suggestion(
 123                         expr.span,
 124                         "try",
 125                         format!(
 126                             "{}.{}({})",
 127                             detection.slice_name,
 128                             detection.method.unstable_name(),
 129                             detection.method_args,
 130                         ),
 131                         Applicability::MachineApplicable,
 132                     );
 133                     diag.note(
 134                         "an unstable sort would perform faster without any observable difference for this data type",
 135                     );
 136                 },
 137             );
 138         }
 139     }
 140 }