src/tools/clippy/clippy_lints/src/methods/unnecessary_sort_by.rs

   1 use clippy_utils::diagnostics::span_lint_and_sugg;
   2 use clippy_utils::is_trait_method;
   3 use clippy_utils::sugg::Sugg;
   4 use clippy_utils::ty::implements_trait;
   5 use if_chain::if_chain;
   6 use rustc_errors::Applicability;
   7 use rustc_hir::{Closure, Expr, ExprKind, Mutability, Param, Pat, PatKind, Path, PathSegment, QPath};
   8 use rustc_lint::LateContext;
   9 use rustc_middle::ty::{self, subst::GenericArgKind};
  10 use rustc_span::sym;
  11 use rustc_span::symbol::Ident;
  12 use std::iter;
  13
  14 use super::UNNECESSARY_SORT_BY;
  15
  16 enum LintTrigger {
  17     Sort(SortDetection),
  18     SortByKey(SortByKeyDetection),
  19 }
  20
  21 struct SortDetection {
  22     vec_name: String,
  23 }
  24
  25 struct SortByKeyDetection {
  26     vec_name: String,
  27     closure_arg: String,
  28     closure_body: String,
  29     reverse: bool,
  30 }
  31
  32 /// Detect if the two expressions are mirrored (identical, except one
  33 /// contains a and the other replaces it with b)
  34 fn mirrored_exprs(a_expr: &Expr<'_>, a_ident: &Ident, b_expr: &Expr<'_>, b_ident: &Ident) -> bool {
  35     match (&a_expr.kind, &b_expr.kind) {
  36         // Two boxes with mirrored contents
  37         (ExprKind::Box(left_expr), ExprKind::Box(right_expr)) => {
  38             mirrored_exprs(left_expr, a_ident, right_expr, b_ident)
  39         },
  40         // Two arrays with mirrored contents
  41         (ExprKind::Array(left_exprs), ExprKind::Array(right_exprs)) => {
  42             iter::zip(*left_exprs, *right_exprs).all(|(left, right)| mirrored_exprs(left, a_ident, right, b_ident))
  43         },
  44         // The two exprs are function calls.
  45         // Check to see that the function itself and its arguments are mirrored
  46         (ExprKind::Call(left_expr, left_args), ExprKind::Call(right_expr, right_args)) => {
  47             mirrored_exprs(left_expr, a_ident, right_expr, b_ident)
  48                 && iter::zip(*left_args, *right_args).all(|(left, right)| mirrored_exprs(left, a_ident, right, b_ident))
  49         },
  50         // The two exprs are method calls.
  51         // Check to see that the function is the same and the arguments are mirrored
  52         // This is enough because the receiver of the method is listed in the arguments
  53         (
  54             ExprKind::MethodCall(left_segment, left_receiver, left_args, _),
  55             ExprKind::MethodCall(right_segment, right_receiver, right_args, _),
  56         ) => {
  57             left_segment.ident == right_segment.ident
  58                 && iter::zip(*left_args, *right_args).all(|(left, right)| mirrored_exprs(left, a_ident, right, b_ident))
  59                 && mirrored_exprs(left_receiver, a_ident, right_receiver, b_ident)
  60         },
  61         // Two tuples with mirrored contents
  62         (ExprKind::Tup(left_exprs), ExprKind::Tup(right_exprs)) => {
  63             iter::zip(*left_exprs, *right_exprs).all(|(left, right)| mirrored_exprs(left, a_ident, right, b_ident))
  64         },
  65         // Two binary ops, which are the same operation and which have mirrored arguments
  66         (ExprKind::Binary(left_op, left_left, left_right), ExprKind::Binary(right_op, right_left, right_right)) => {
  67             left_op.node == right_op.node
  68                 && mirrored_exprs(left_left, a_ident, right_left, b_ident)
  69                 && mirrored_exprs(left_right, a_ident, right_right, b_ident)
  70         },
  71         // Two unary ops, which are the same operation and which have the same argument
  72         (ExprKind::Unary(left_op, left_expr), ExprKind::Unary(right_op, right_expr)) => {
  73             left_op == right_op && mirrored_exprs(left_expr, a_ident, right_expr, b_ident)
  74         },
  75         // The two exprs are literals of some kind
  76         (ExprKind::Lit(left_lit), ExprKind::Lit(right_lit)) => left_lit.node == right_lit.node,
  77         (ExprKind::Cast(left, _), ExprKind::Cast(right, _)) => mirrored_exprs(left, a_ident, right, b_ident),
  78         (ExprKind::DropTemps(left_block), ExprKind::DropTemps(right_block)) => {
  79             mirrored_exprs(left_block, a_ident, right_block, b_ident)
  80         },
  81         (ExprKind::Field(left_expr, left_ident), ExprKind::Field(right_expr, right_ident)) => {
  82             left_ident.name == right_ident.name && mirrored_exprs(left_expr, a_ident, right_expr, right_ident)
  83         },
  84         // Two paths: either one is a and the other is b, or they're identical to each other
  85         (
  86             ExprKind::Path(QPath::Resolved(
  87                 _,
  88                 Path {
  89                     segments: left_segments,
  90                     ..
  91                 },
  92             )),
  93             ExprKind::Path(QPath::Resolved(
  94                 _,
  95                 Path {
  96                     segments: right_segments,
  97                     ..
  98                 },
  99             )),
 100         ) => {
 101             (iter::zip(*left_segments, *right_segments).all(|(left, right)| left.ident == right.ident)
 102                 && left_segments
 103                     .iter()
 104                     .all(|seg| &seg.ident != a_ident && &seg.ident != b_ident))
 105                 || (left_segments.len() == 1
 106                     && &left_segments[0].ident == a_ident
 107                     && right_segments.len() == 1
 108                     && &right_segments[0].ident == b_ident)
 109         },
 110         // Matching expressions, but one or both is borrowed
 111         (
 112             ExprKind::AddrOf(left_kind, Mutability::Not, left_expr),
 113             ExprKind::AddrOf(right_kind, Mutability::Not, right_expr),
 114         ) => left_kind == right_kind && mirrored_exprs(left_expr, a_ident, right_expr, b_ident),
 115         (_, ExprKind::AddrOf(_, Mutability::Not, right_expr)) => mirrored_exprs(a_expr, a_ident, right_expr, b_ident),
 116         (ExprKind::AddrOf(_, Mutability::Not, left_expr), _) => mirrored_exprs(left_expr, a_ident, b_expr, b_ident),
 117         _ => false,
 118     }
 119 }
 120
 121 fn detect_lint(cx: &LateContext<'_>, expr: &Expr<'_>, recv: &Expr<'_>, arg: &Expr<'_>) -> Option<LintTrigger> {
 122     if_chain! {
 123         if let Some(method_id) = cx.typeck_results().type_dependent_def_id(expr.hir_id);
 124         if let Some(impl_id) = cx.tcx.impl_of_method(method_id);
 125         if cx.tcx.type_of(impl_id).is_slice();
 126         if let ExprKind::Closure(&Closure { body, .. }) = arg.kind;
 127         if let closure_body = cx.tcx.hir().body(body);
 128         if let &[
 129             Param { pat: Pat { kind: PatKind::Binding(_, _, left_ident, _), .. }, ..},
 130             Param { pat: Pat { kind: PatKind::Binding(_, _, right_ident, _), .. }, .. }
 131         ] = &closure_body.params;
 132         if let ExprKind::MethodCall(method_path, left_expr, [right_expr], _) = closure_body.value.kind;
 133         if method_path.ident.name == sym::cmp;
 134         if is_trait_method(cx, closure_body.value, sym::Ord);
 135         then {
 136             let (closure_body, closure_arg, reverse) = if mirrored_exprs(
 137                 left_expr,
 138                 left_ident,
 139                 right_expr,
 140                 right_ident
 141             ) {
 142                 (Sugg::hir(cx, left_expr, "..").to_string(), left_ident.name.to_string(), false)
 143             } else if mirrored_exprs(left_expr, right_ident, right_expr, left_ident) {
 144                 (Sugg::hir(cx, left_expr, "..").to_string(), right_ident.name.to_string(), true)
 145             } else {
 146                 return None;
 147             };
 148             let vec_name = Sugg::hir(cx, recv, "..").to_string();
 149
 150             if_chain! {
 151                 if let ExprKind::Path(QPath::Resolved(_, Path {
 152                     segments: [PathSegment { ident: left_name, .. }], ..
 153                 })) = &left_expr.kind;
 154                 if left_name == left_ident;
 155                 if cx.tcx.get_diagnostic_item(sym::Ord).map_or(false, |id| {
 156                     implements_trait(cx, cx.typeck_results().expr_ty(left_expr), id, &[])
 157                 });
 158                 then {
 159                     return Some(LintTrigger::Sort(SortDetection { vec_name }));
 160                 }
 161             }
 162
 163             if !expr_borrows(cx, left_expr) {
 164                 return Some(LintTrigger::SortByKey(SortByKeyDetection {
 165                     vec_name,
 166                     closure_arg,
 167                     closure_body,
 168                     reverse,
 169                 }));
 170             }
 171         }
 172     }
 173
 174     None
 175 }
 176
 177 fn expr_borrows(cx: &LateContext<'_>, expr: &Expr<'_>) -> bool {
 178     let ty = cx.typeck_results().expr_ty(expr);
 179     matches!(ty.kind(), ty::Ref(..)) || ty.walk().any(|arg| matches!(arg.unpack(), GenericArgKind::Lifetime(_)))
 180 }
 181
 182 pub(super) fn check<'tcx>(
 183     cx: &LateContext<'tcx>,
 184     expr: &'tcx Expr<'_>,
 185     recv: &'tcx Expr<'_>,
 186     arg: &'tcx Expr<'_>,
 187     is_unstable: bool,
 188 ) {
 189     match detect_lint(cx, expr, recv, arg) {
 190         Some(LintTrigger::SortByKey(trigger)) => span_lint_and_sugg(
 191             cx,
 192             UNNECESSARY_SORT_BY,
 193             expr.span,
 194             "use Vec::sort_by_key here instead",
 195             "try",
 196             format!(
 197                 "{}.sort{}_by_key(|{}| {})",
 198                 trigger.vec_name,
 199                 if is_unstable { "_unstable" } else { "" },
 200                 trigger.closure_arg,
 201                 if trigger.reverse {
 202                     format!("std::cmp::Reverse({})", trigger.closure_body)
 203                 } else {
 204                     trigger.closure_body.to_string()
 205                 },
 206             ),
 207             if trigger.reverse {
 208                 Applicability::MaybeIncorrect
 209             } else {
 210                 Applicability::MachineApplicable
 211             },
 212         ),
 213         Some(LintTrigger::Sort(trigger)) => span_lint_and_sugg(
 214             cx,
 215             UNNECESSARY_SORT_BY,
 216             expr.span,
 217             "use Vec::sort here instead",
 218             "try",
 219             format!(
 220                 "{}.sort{}()",
 221                 trigger.vec_name,
 222                 if is_unstable { "_unstable" } else { "" },
 223             ),
 224             Applicability::MachineApplicable,
 225         ),
 226         None => {},
 227     }
 228 }