clippy_lints/src/stable_sort_primitive.rs

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