clippy_lints/src/unnecessary_sort_by.rs

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