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