clippy_lints/src/unnecessary_sort_by.rs

   1 use crate::utils;
   2 use crate::utils::paths;
   3 use crate::utils::sugg::Sugg;
   4 use if_chain::if_chain;
   5 use rustc_errors::Applicability;
   6 use rustc_hir::{Expr, ExprKind, Mutability, Param, Pat, PatKind, Path, PathSegment, QPath};
   7 use rustc_lint::{LateContext, LateLintPass};
   8 use rustc_session::{declare_lint_pass, declare_tool_lint};
   9 use rustc_span::symbol::Ident;
  10
  11 declare_clippy_lint! {
  12     /// **What it does:**
  13     /// Detects when people use `Vec::sort_by` and pass in a function
  14     /// which compares the two arguments, either directly or indirectly.
  15     ///
  16     /// **Why is this bad?**
  17     /// It is more clear to use `Vec::sort_by_key` (or `Vec::sort` if
  18     /// possible) than to use `Vec::sort_by` and and a more complicated
  19     /// closure.
  20     ///
  21     /// **Known problems:**
  22     /// If the suggested `Vec::sort_by_key` uses Reverse and it isn't
  23     /// imported by a use statement in the current frame, then a `use`
  24     /// statement that imports it will need to be added (which this lint
  25     /// can't do).
  26     ///
  27     /// **Example:**
  28     ///
  29     /// ```rust
  30     /// # struct A;
  31     /// # impl A { fn foo(&self) {} }
  32     /// # let mut vec: Vec<A> = Vec::new();
  33     /// vec.sort_by(|a, b| a.foo().cmp(&b.foo()));
  34     /// ```
  35     /// Use instead:
  36     /// ```rust
  37     /// # struct A;
  38     /// # impl A { fn foo(&self) {} }
  39     /// # let mut vec: Vec<A> = Vec::new();
  40     /// vec.sort_by_key(|a| a.foo());
  41     /// ```
  42     pub UNNECESSARY_SORT_BY,
  43     complexity,
  44     "Use of `Vec::sort_by` when `Vec::sort_by_key` or `Vec::sort` would be clearer"
  45 }
  46
  47 declare_lint_pass!(UnnecessarySortBy => [UNNECESSARY_SORT_BY]);
  48
  49 enum LintTrigger {
  50     Sort(SortDetection),
  51     SortByKey(SortByKeyDetection),
  52 }
  53
  54 struct SortDetection {
  55     vec_name: String,
  56     unstable: bool,
  57 }
  58
  59 struct SortByKeyDetection {
  60     vec_name: String,
  61     closure_arg: String,
  62     closure_body: String,
  63     reverse: bool,
  64     unstable: bool,
  65 }
  66
  67 /// Detect if the two expressions are mirrored (identical, except one
  68 /// contains a and the other replaces it with b)
  69 fn mirrored_exprs(
  70     cx: &LateContext<'_, '_>,
  71     a_expr: &Expr<'_>,
  72     a_ident: &Ident,
  73     b_expr: &Expr<'_>,
  74     b_ident: &Ident,
  75 ) -> bool {
  76     match (&a_expr.kind, &b_expr.kind) {
  77         // Two boxes with mirrored contents
  78         (ExprKind::Box(left_expr), ExprKind::Box(right_expr)) => {
  79             mirrored_exprs(cx, left_expr, a_ident, right_expr, b_ident)
  80         },
  81         // Two arrays with mirrored contents
  82         (ExprKind::Array(left_exprs), ExprKind::Array(right_exprs)) => left_exprs
  83             .iter()
  84             .zip(right_exprs.iter())
  85             .all(|(left, right)| mirrored_exprs(cx, left, a_ident, right, b_ident)),
  86         // The two exprs are function calls.
  87         // Check to see that the function itself and its arguments are mirrored
  88         (ExprKind::Call(left_expr, left_args), ExprKind::Call(right_expr, right_args)) => {
  89             mirrored_exprs(cx, left_expr, a_ident, right_expr, b_ident)
  90                 && left_args
  91                     .iter()
  92                     .zip(right_args.iter())
  93                     .all(|(left, right)| mirrored_exprs(cx, left, a_ident, right, b_ident))
  94         },
  95         // The two exprs are method calls.
  96         // Check to see that the function is the same and the arguments are mirrored
  97         // This is enough because the receiver of the method is listed in the arguments
  98         (ExprKind::MethodCall(left_segment, _, left_args, _), ExprKind::MethodCall(right_segment, _, right_args, _)) => {
  99             left_segment.ident == right_segment.ident
 100                 && left_args
 101                     .iter()
 102                     .zip(right_args.iter())
 103                     .all(|(left, right)| mirrored_exprs(cx, left, a_ident, right, b_ident))
 104         },
 105         // Two tuples with mirrored contents
 106         (ExprKind::Tup(left_exprs), ExprKind::Tup(right_exprs)) => left_exprs
 107             .iter()
 108             .zip(right_exprs.iter())
 109             .all(|(left, right)| mirrored_exprs(cx, left, a_ident, right, b_ident)),
 110         // Two binary ops, which are the same operation and which have mirrored arguments
 111         (ExprKind::Binary(left_op, left_left, left_right), ExprKind::Binary(right_op, right_left, right_right)) => {
 112             left_op.node == right_op.node
 113                 && mirrored_exprs(cx, left_left, a_ident, right_left, b_ident)
 114                 && mirrored_exprs(cx, left_right, a_ident, right_right, b_ident)
 115         },
 116         // Two unary ops, which are the same operation and which have the same argument
 117         (ExprKind::Unary(left_op, left_expr), ExprKind::Unary(right_op, right_expr)) => {
 118             left_op == right_op && mirrored_exprs(cx, left_expr, a_ident, right_expr, b_ident)
 119         },
 120         // The two exprs are literals of some kind
 121         (ExprKind::Lit(left_lit), ExprKind::Lit(right_lit)) => left_lit.node == right_lit.node,
 122         (ExprKind::Cast(left, _), ExprKind::Cast(right, _)) => mirrored_exprs(cx, left, a_ident, right, b_ident),
 123         (ExprKind::DropTemps(left_block), ExprKind::DropTemps(right_block)) => {
 124             mirrored_exprs(cx, left_block, a_ident, right_block, b_ident)
 125         },
 126         (ExprKind::Field(left_expr, left_ident), ExprKind::Field(right_expr, right_ident)) => {
 127             left_ident.name == right_ident.name && mirrored_exprs(cx, left_expr, a_ident, right_expr, right_ident)
 128         },
 129         // Two paths: either one is a and the other is b, or they're identical to each other
 130         (
 131             ExprKind::Path(QPath::Resolved(
 132                 _,
 133                 Path {
 134                     segments: left_segments,
 135                     ..
 136                 },
 137             )),
 138             ExprKind::Path(QPath::Resolved(
 139                 _,
 140                 Path {
 141                     segments: right_segments,
 142                     ..
 143                 },
 144             )),
 145         ) => {
 146             (left_segments
 147                 .iter()
 148                 .zip(right_segments.iter())
 149                 .all(|(left, right)| left.ident == right.ident)
 150                 && left_segments
 151                     .iter()
 152                     .all(|seg| &seg.ident != a_ident && &seg.ident != b_ident))
 153                 || (left_segments.len() == 1
 154                     && &left_segments[0].ident == a_ident
 155                     && right_segments.len() == 1
 156                     && &right_segments[0].ident == b_ident)
 157         },
 158         // Matching expressions, but one or both is borrowed
 159         (
 160             ExprKind::AddrOf(left_kind, Mutability::Not, left_expr),
 161             ExprKind::AddrOf(right_kind, Mutability::Not, right_expr),
 162         ) => left_kind == right_kind && mirrored_exprs(cx, left_expr, a_ident, right_expr, b_ident),
 163         (_, ExprKind::AddrOf(_, Mutability::Not, right_expr)) => {
 164             mirrored_exprs(cx, a_expr, a_ident, right_expr, b_ident)
 165         },
 166         (ExprKind::AddrOf(_, Mutability::Not, left_expr), _) => mirrored_exprs(cx, left_expr, a_ident, b_expr, b_ident),
 167         _ => false,
 168     }
 169 }
 170
 171 fn detect_lint(cx: &LateContext<'_, '_>, expr: &Expr<'_>) -> Option<LintTrigger> {
 172     if_chain! {
 173         if let ExprKind::MethodCall(name_ident, _, args, _) = &expr.kind;
 174         if let name = name_ident.ident.name.to_ident_string();
 175         if name == "sort_by" || name == "sort_unstable_by";
 176         if let [vec, Expr { kind: ExprKind::Closure(_, _, closure_body_id, _, _), .. }] = args;
 177         if utils::match_type(cx, &cx.tables.expr_ty(vec), &paths::VEC);
 178         if let closure_body = cx.tcx.hir().body(*closure_body_id);
 179         if let &[
 180             Param { pat: Pat { kind: PatKind::Binding(_, _, left_ident, _), .. }, ..},
 181             Param { pat: Pat { kind: PatKind::Binding(_, _, right_ident, _), .. }, .. }
 182         ] = &closure_body.params;
 183         if let ExprKind::MethodCall(method_path, _, [ref left_expr, ref right_expr], _) = &closure_body.value.kind;
 184         if method_path.ident.name.to_ident_string() == "cmp";
 185         then {
 186             let (closure_body, closure_arg, reverse) = if mirrored_exprs(
 187                 &cx,
 188                 &left_expr,
 189                 &left_ident,
 190                 &right_expr,
 191                 &right_ident
 192             ) {
 193                 (Sugg::hir(cx, &left_expr, "..").to_string(), left_ident.name.to_string(), false)
 194             } else if mirrored_exprs(&cx, &left_expr, &right_ident, &right_expr, &left_ident) {
 195                 (Sugg::hir(cx, &left_expr, "..").to_string(), right_ident.name.to_string(), true)
 196             } else {
 197                 return None;
 198             };
 199             let vec_name = Sugg::hir(cx, &args[0], "..").to_string();
 200             let unstable = name == "sort_unstable_by";
 201             if_chain! {
 202                 if let ExprKind::Path(QPath::Resolved(_, Path {
 203                     segments: [PathSegment { ident: left_name, .. }], ..
 204                 })) = &left_expr.kind;
 205                 if left_name == left_ident;
 206                 then {
 207                     Some(LintTrigger::Sort(SortDetection { vec_name, unstable }))
 208                 }
 209                 else {
 210                     Some(LintTrigger::SortByKey(SortByKeyDetection {
 211                         vec_name,
 212                         unstable,
 213                         closure_arg,
 214                         closure_body,
 215                         reverse
 216                     }))
 217                 }
 218             }
 219         } else {
 220             None
 221         }
 222     }
 223 }
 224
 225 impl LateLintPass<'_, '_> for UnnecessarySortBy {
 226     fn check_expr(&mut self, cx: &LateContext<'_, '_>, expr: &Expr<'_>) {
 227         match detect_lint(cx, expr) {
 228             Some(LintTrigger::SortByKey(trigger)) => utils::span_lint_and_sugg(
 229                 cx,
 230                 UNNECESSARY_SORT_BY,
 231                 expr.span,
 232                 "use Vec::sort_by_key here instead",
 233                 "try",
 234                 format!(
 235                     "{}.sort{}_by_key(|&{}| {})",
 236                     trigger.vec_name,
 237                     if trigger.unstable { "_unstable" } else { "" },
 238                     trigger.closure_arg,
 239                     if trigger.reverse {
 240                         format!("Reverse({})", trigger.closure_body)
 241                     } else {
 242                         trigger.closure_body.to_string()
 243                     },
 244                 ),
 245                 if trigger.reverse {
 246                     Applicability::MaybeIncorrect
 247                 } else {
 248                     Applicability::MachineApplicable
 249                 },
 250             ),
 251             Some(LintTrigger::Sort(trigger)) => utils::span_lint_and_sugg(
 252                 cx,
 253                 UNNECESSARY_SORT_BY,
 254                 expr.span,
 255                 "use Vec::sort here instead",
 256                 "try",
 257                 format!(
 258                     "{}.sort{}()",
 259                     trigger.vec_name,
 260                     if trigger.unstable { "_unstable" } else { "" },
 261                 ),
 262                 Applicability::MachineApplicable,
 263             ),
 264             None => {},
 265         }
 266     }
 267 }