clippy_lints/src/stable_sort_primitive.rs

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