clippy_lints/src/loops/manual_memcpy.rs

   1 use super::{IncrementVisitor, InitializeVisitor, MANUAL_MEMCPY};
   2 use clippy_utils::diagnostics::span_lint_and_sugg;
   3 use clippy_utils::source::snippet;
   4 use clippy_utils::sugg::Sugg;
   5 use clippy_utils::ty::is_copy;
   6 use clippy_utils::{get_enclosing_block, higher, path_to_local, sugg};
   7 use if_chain::if_chain;
   8 use rustc_ast::ast;
   9 use rustc_errors::Applicability;
  10 use rustc_hir::intravisit::walk_block;
  11 use rustc_hir::{BinOpKind, Block, Expr, ExprKind, HirId, Pat, PatKind, StmtKind};
  12 use rustc_lint::LateContext;
  13 use rustc_middle::ty::{self, Ty};
  14 use rustc_span::symbol::sym;
  15 use std::fmt::Display;
  16 use std::iter::Iterator;
  17
  18 /// Checks for for loops that sequentially copy items from one slice-like
  19 /// object to another.
  20 pub(super) fn check<'tcx>(
  21     cx: &LateContext<'tcx>,
  22     pat: &'tcx Pat<'_>,
  23     arg: &'tcx Expr<'_>,
  24     body: &'tcx Expr<'_>,
  25     expr: &'tcx Expr<'_>,
  26 ) -> bool {
  27     if let Some(higher::Range {
  28         start: Some(start),
  29         end: Some(end),
  30         limits,
  31     }) = higher::Range::hir(arg)
  32     {
  33         // the var must be a single name
  34         if let PatKind::Binding(_, canonical_id, _, _) = pat.kind {
  35             let mut starts = vec![Start {
  36                 id: canonical_id,
  37                 kind: StartKind::Range,
  38             }];
  39
  40             // This is one of few ways to return different iterators
  41             // derived from: https://stackoverflow.com/questions/29760668/conditionally-iterate-over-one-of-several-possible-iterators/52064434#52064434
  42             let mut iter_a = None;
  43             let mut iter_b = None;
  44
  45             if let ExprKind::Block(block, _) = body.kind {
  46                 if let Some(loop_counters) = get_loop_counters(cx, block, expr) {
  47                     starts.extend(loop_counters);
  48                 }
  49                 iter_a = Some(get_assignments(block, &starts));
  50             } else {
  51                 iter_b = Some(get_assignment(body));
  52             }
  53
  54             let assignments = iter_a.into_iter().flatten().chain(iter_b.into_iter());
  55
  56             let big_sugg = assignments
  57                 // The only statements in the for loops can be indexed assignments from
  58                 // indexed retrievals (except increments of loop counters).
  59                 .map(|o| {
  60                     o.and_then(|(lhs, rhs)| {
  61                         let rhs = fetch_cloned_expr(rhs);
  62                         if_chain! {
  63                             if let ExprKind::Index(base_left, idx_left) = lhs.kind;
  64                             if let ExprKind::Index(base_right, idx_right) = rhs.kind;
  65                             if let Some(ty) = get_slice_like_element_ty(cx, cx.typeck_results().expr_ty(base_left));
  66                             if get_slice_like_element_ty(cx, cx.typeck_results().expr_ty(base_right)).is_some();
  67                             if let Some((start_left, offset_left)) = get_details_from_idx(cx, idx_left, &starts);
  68                             if let Some((start_right, offset_right)) = get_details_from_idx(cx, idx_right, &starts);
  69
  70                             // Source and destination must be different
  71                             if path_to_local(base_left) != path_to_local(base_right);
  72                             then {
  73                                 Some((ty, IndexExpr { base: base_left, idx: start_left, idx_offset: offset_left },
  74                                     IndexExpr { base: base_right, idx: start_right, idx_offset: offset_right }))
  75                             } else {
  76                                 None
  77                             }
  78                         }
  79                     })
  80                 })
  81                 .map(|o| o.map(|(ty, dst, src)| build_manual_memcpy_suggestion(cx, start, end, limits, ty, &dst, &src)))
  82                 .collect::<Option<Vec<_>>>()
  83                 .filter(|v| !v.is_empty())
  84                 .map(|v| v.join("\n    "));
  85
  86             if let Some(big_sugg) = big_sugg {
  87                 span_lint_and_sugg(
  88                     cx,
  89                     MANUAL_MEMCPY,
  90                     expr.span,
  91                     "it looks like you're manually copying between slices",
  92                     "try replacing the loop by",
  93                     big_sugg,
  94                     Applicability::Unspecified,
  95                 );
  96                 return true;
  97             }
  98         }
  99     }
 100     false
 101 }
 102
 103 fn build_manual_memcpy_suggestion<'tcx>(
 104     cx: &LateContext<'tcx>,
 105     start: &Expr<'_>,
 106     end: &Expr<'_>,
 107     limits: ast::RangeLimits,
 108     elem_ty: Ty<'tcx>,
 109     dst: &IndexExpr<'_>,
 110     src: &IndexExpr<'_>,
 111 ) -> String {
 112     fn print_offset(offset: MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 113         if offset.to_string() == "0" {
 114             sugg::EMPTY.into()
 115         } else {
 116             offset
 117         }
 118     }
 119
 120     let print_limit = |end: &Expr<'_>, end_str: &str, base: &Expr<'_>, sugg: MinifyingSugg<'static>| {
 121         if_chain! {
 122             if let ExprKind::MethodCall(method, [recv], _) = end.kind;
 123             if method.ident.name == sym::len;
 124             if path_to_local(recv) == path_to_local(base);
 125             then {
 126                 if sugg.to_string() == end_str {
 127                     sugg::EMPTY.into()
 128                 } else {
 129                     sugg
 130                 }
 131             } else {
 132                 match limits {
 133                     ast::RangeLimits::Closed => {
 134                         sugg + &sugg::ONE.into()
 135                     },
 136                     ast::RangeLimits::HalfOpen => sugg,
 137                 }
 138             }
 139         }
 140     };
 141
 142     let start_str = Sugg::hir(cx, start, "").into();
 143     let end_str: MinifyingSugg<'_> = Sugg::hir(cx, end, "").into();
 144
 145     let print_offset_and_limit = |idx_expr: &IndexExpr<'_>| match idx_expr.idx {
 146         StartKind::Range => (
 147             print_offset(apply_offset(&start_str, &idx_expr.idx_offset)).into_sugg(),
 148             print_limit(
 149                 end,
 150                 end_str.to_string().as_str(),
 151                 idx_expr.base,
 152                 apply_offset(&end_str, &idx_expr.idx_offset),
 153             )
 154             .into_sugg(),
 155         ),
 156         StartKind::Counter { initializer } => {
 157             let counter_start = Sugg::hir(cx, initializer, "").into();
 158             (
 159                 print_offset(apply_offset(&counter_start, &idx_expr.idx_offset)).into_sugg(),
 160                 print_limit(
 161                     end,
 162                     end_str.to_string().as_str(),
 163                     idx_expr.base,
 164                     apply_offset(&end_str, &idx_expr.idx_offset) + &counter_start - &start_str,
 165                 )
 166                 .into_sugg(),
 167             )
 168         },
 169     };
 170
 171     let (dst_offset, dst_limit) = print_offset_and_limit(dst);
 172     let (src_offset, src_limit) = print_offset_and_limit(src);
 173
 174     let dst_base_str = snippet(cx, dst.base.span, "???");
 175     let src_base_str = snippet(cx, src.base.span, "???");
 176
 177     let dst = if dst_offset == sugg::EMPTY && dst_limit == sugg::EMPTY {
 178         dst_base_str
 179     } else {
 180         format!(
 181             "{}[{}..{}]",
 182             dst_base_str,
 183             dst_offset.maybe_par(),
 184             dst_limit.maybe_par()
 185         )
 186         .into()
 187     };
 188
 189     let method_str = if is_copy(cx, elem_ty) {
 190         "copy_from_slice"
 191     } else {
 192         "clone_from_slice"
 193     };
 194
 195     format!(
 196         "{}.{}(&{}[{}..{}]);",
 197         dst,
 198         method_str,
 199         src_base_str,
 200         src_offset.maybe_par(),
 201         src_limit.maybe_par()
 202     )
 203 }
 204
 205 /// a wrapper of `Sugg`. Besides what `Sugg` do, this removes unnecessary `0`;
 206 /// and also, it avoids subtracting a variable from the same one by replacing it with `0`.
 207 /// it exists for the convenience of the overloaded operators while normal functions can do the
 208 /// same.
 209 #[derive(Clone)]
 210 struct MinifyingSugg<'a>(Sugg<'a>);
 211
 212 impl<'a> Display for MinifyingSugg<'a> {
 213     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 214         self.0.fmt(f)
 215     }
 216 }
 217
 218 impl<'a> MinifyingSugg<'a> {
 219     fn into_sugg(self) -> Sugg<'a> {
 220         self.0
 221     }
 222 }
 223
 224 impl<'a> From<Sugg<'a>> for MinifyingSugg<'a> {
 225     fn from(sugg: Sugg<'a>) -> Self {
 226         Self(sugg)
 227     }
 228 }
 229
 230 impl std::ops::Add for &MinifyingSugg<'static> {
 231     type Output = MinifyingSugg<'static>;
 232     fn add(self, rhs: &MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 233         match (self.to_string().as_str(), rhs.to_string().as_str()) {
 234             ("0", _) => rhs.clone(),
 235             (_, "0") => self.clone(),
 236             (_, _) => (&self.0 + &rhs.0).into(),
 237         }
 238     }
 239 }
 240
 241 impl std::ops::Sub for &MinifyingSugg<'static> {
 242     type Output = MinifyingSugg<'static>;
 243     fn sub(self, rhs: &MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 244         match (self.to_string().as_str(), rhs.to_string().as_str()) {
 245             (_, "0") => self.clone(),
 246             ("0", _) => (-rhs.0.clone()).into(),
 247             (x, y) if x == y => sugg::ZERO.into(),
 248             (_, _) => (&self.0 - &rhs.0).into(),
 249         }
 250     }
 251 }
 252
 253 impl std::ops::Add<&MinifyingSugg<'static>> for MinifyingSugg<'static> {
 254     type Output = MinifyingSugg<'static>;
 255     fn add(self, rhs: &MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 256         match (self.to_string().as_str(), rhs.to_string().as_str()) {
 257             ("0", _) => rhs.clone(),
 258             (_, "0") => self,
 259             (_, _) => (self.0 + &rhs.0).into(),
 260         }
 261     }
 262 }
 263
 264 impl std::ops::Sub<&MinifyingSugg<'static>> for MinifyingSugg<'static> {
 265     type Output = MinifyingSugg<'static>;
 266     fn sub(self, rhs: &MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 267         match (self.to_string().as_str(), rhs.to_string().as_str()) {
 268             (_, "0") => self,
 269             ("0", _) => (-rhs.0.clone()).into(),
 270             (x, y) if x == y => sugg::ZERO.into(),
 271             (_, _) => (self.0 - &rhs.0).into(),
 272         }
 273     }
 274 }
 275
 276 /// a wrapper around `MinifyingSugg`, which carries an operator like currying
 277 /// so that the suggested code become more efficient (e.g. `foo + -bar` `foo - bar`).
 278 struct Offset {
 279     value: MinifyingSugg<'static>,
 280     sign: OffsetSign,
 281 }
 282
 283 #[derive(Clone, Copy)]
 284 enum OffsetSign {
 285     Positive,
 286     Negative,
 287 }
 288
 289 impl Offset {
 290     fn negative(value: Sugg<'static>) -> Self {
 291         Self {
 292             value: value.into(),
 293             sign: OffsetSign::Negative,
 294         }
 295     }
 296
 297     fn positive(value: Sugg<'static>) -> Self {
 298         Self {
 299             value: value.into(),
 300             sign: OffsetSign::Positive,
 301         }
 302     }
 303
 304     fn empty() -> Self {
 305         Self::positive(sugg::ZERO)
 306     }
 307 }
 308
 309 fn apply_offset(lhs: &MinifyingSugg<'static>, rhs: &Offset) -> MinifyingSugg<'static> {
 310     match rhs.sign {
 311         OffsetSign::Positive => lhs + &rhs.value,
 312         OffsetSign::Negative => lhs - &rhs.value,
 313     }
 314 }
 315
 316 #[derive(Debug, Clone, Copy)]
 317 enum StartKind<'hir> {
 318     Range,
 319     Counter { initializer: &'hir Expr<'hir> },
 320 }
 321
 322 struct IndexExpr<'hir> {
 323     base: &'hir Expr<'hir>,
 324     idx: StartKind<'hir>,
 325     idx_offset: Offset,
 326 }
 327
 328 struct Start<'hir> {
 329     id: HirId,
 330     kind: StartKind<'hir>,
 331 }
 332
 333 fn get_slice_like_element_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
 334     match ty.kind() {
 335         ty::Adt(adt, subs) if cx.tcx.is_diagnostic_item(sym::Vec, adt.did()) => Some(subs.type_at(0)),
 336         ty::Ref(_, subty, _) => get_slice_like_element_ty(cx, *subty),
 337         ty::Slice(ty) | ty::Array(ty, _) => Some(*ty),
 338         _ => None,
 339     }
 340 }
 341
 342 fn fetch_cloned_expr<'tcx>(expr: &'tcx Expr<'tcx>) -> &'tcx Expr<'tcx> {
 343     if_chain! {
 344         if let ExprKind::MethodCall(method, [arg], _) = expr.kind;
 345         if method.ident.name == sym::clone;
 346         then { arg } else { expr }
 347     }
 348 }
 349
 350 fn get_details_from_idx<'tcx>(
 351     cx: &LateContext<'tcx>,
 352     idx: &Expr<'_>,
 353     starts: &[Start<'tcx>],
 354 ) -> Option<(StartKind<'tcx>, Offset)> {
 355     fn get_start<'tcx>(e: &Expr<'_>, starts: &[Start<'tcx>]) -> Option<StartKind<'tcx>> {
 356         let id = path_to_local(e)?;
 357         starts.iter().find(|start| start.id == id).map(|start| start.kind)
 358     }
 359
 360     fn get_offset<'tcx>(cx: &LateContext<'tcx>, e: &Expr<'_>, starts: &[Start<'tcx>]) -> Option<Sugg<'static>> {
 361         match &e.kind {
 362             ExprKind::Lit(l) => match l.node {
 363                 ast::LitKind::Int(x, _ty) => Some(Sugg::NonParen(x.to_string().into())),
 364                 _ => None,
 365             },
 366             ExprKind::Path(..) if get_start(e, starts).is_none() => Some(Sugg::hir(cx, e, "???")),
 367             _ => None,
 368         }
 369     }
 370
 371     match idx.kind {
 372         ExprKind::Binary(op, lhs, rhs) => match op.node {
 373             BinOpKind::Add => {
 374                 let offset_opt = get_start(lhs, starts)
 375                     .and_then(|s| get_offset(cx, rhs, starts).map(|o| (s, o)))
 376                     .or_else(|| get_start(rhs, starts).and_then(|s| get_offset(cx, lhs, starts).map(|o| (s, o))));
 377
 378                 offset_opt.map(|(s, o)| (s, Offset::positive(o)))
 379             },
 380             BinOpKind::Sub => {
 381                 get_start(lhs, starts).and_then(|s| get_offset(cx, rhs, starts).map(|o| (s, Offset::negative(o))))
 382             },
 383             _ => None,
 384         },
 385         ExprKind::Path(..) => get_start(idx, starts).map(|s| (s, Offset::empty())),
 386         _ => None,
 387     }
 388 }
 389
 390 fn get_assignment<'tcx>(e: &'tcx Expr<'tcx>) -> Option<(&'tcx Expr<'tcx>, &'tcx Expr<'tcx>)> {
 391     if let ExprKind::Assign(lhs, rhs, _) = e.kind {
 392         Some((lhs, rhs))
 393     } else {
 394         None
 395     }
 396 }
 397
 398 /// Get assignments from the given block.
 399 /// The returned iterator yields `None` if no assignment expressions are there,
 400 /// filtering out the increments of the given whitelisted loop counters;
 401 /// because its job is to make sure there's nothing other than assignments and the increments.
 402 fn get_assignments<'a, 'tcx>(
 403     Block { stmts, expr, .. }: &'tcx Block<'tcx>,
 404     loop_counters: &'a [Start<'tcx>],
 405 ) -> impl Iterator<Item = Option<(&'tcx Expr<'tcx>, &'tcx Expr<'tcx>)>> + 'a {
 406     // As the `filter` and `map` below do different things, I think putting together
 407     // just increases complexity. (cc #3188 and #4193)
 408     stmts
 409         .iter()
 410         .filter_map(move |stmt| match stmt.kind {
 411             StmtKind::Local(..) | StmtKind::Item(..) => None,
 412             StmtKind::Expr(e) | StmtKind::Semi(e) => Some(e),
 413         })
 414         .chain((*expr).into_iter())
 415         .filter(move |e| {
 416             if let ExprKind::AssignOp(_, place, _) = e.kind {
 417                 path_to_local(place).map_or(false, |id| {
 418                     !loop_counters
 419                         .iter()
 420                         // skip the first item which should be `StartKind::Range`
 421                         // this makes it possible to use the slice with `StartKind::Range` in the same iterator loop.
 422                         .skip(1)
 423                         .any(|counter| counter.id == id)
 424                 })
 425             } else {
 426                 true
 427             }
 428         })
 429         .map(get_assignment)
 430 }
 431
 432 fn get_loop_counters<'a, 'tcx>(
 433     cx: &'a LateContext<'tcx>,
 434     body: &'tcx Block<'tcx>,
 435     expr: &'tcx Expr<'_>,
 436 ) -> Option<impl Iterator<Item = Start<'tcx>> + 'a> {
 437     // Look for variables that are incremented once per loop iteration.
 438     let mut increment_visitor = IncrementVisitor::new(cx);
 439     walk_block(&mut increment_visitor, body);
 440
 441     // For each candidate, check the parent block to see if
 442     // it's initialized to zero at the start of the loop.
 443     get_enclosing_block(cx, expr.hir_id).and_then(|block| {
 444         increment_visitor
 445             .into_results()
 446             .filter_map(move |var_id| {
 447                 let mut initialize_visitor = InitializeVisitor::new(cx, expr, var_id);
 448                 walk_block(&mut initialize_visitor, block);
 449
 450                 initialize_visitor.get_result().map(|(_, _, initializer)| Start {
 451                     id: var_id,
 452                     kind: StartKind::Counter { initializer },
 453                 })
 454             })
 455             .into()
 456     })
 457 }