src/tools/clippy/clippy_lints/src/loops/manual_memcpy.rs

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