clippy_lints/src/unnecessary_sort_by.rs

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