src/tools/clippy/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!("{dst_base_str}[{}..{}]", dst_offset.maybe_par(), dst_limit.maybe_par()).into()
 181     };
 182
 183     let method_str = if is_copy(cx, elem_ty) {
 184         "copy_from_slice"
 185     } else {
 186         "clone_from_slice"
 187     };
 188
 189     format!(
 190         "{dst}.{method_str}(&{src_base_str}[{}..{}]);",
 191         src_offset.maybe_par(),
 192         src_limit.maybe_par()
 193     )
 194 }
 195
 196 /// a wrapper of `Sugg`. Besides what `Sugg` do, this removes unnecessary `0`;
 197 /// and also, it avoids subtracting a variable from the same one by replacing it with `0`.
 198 /// it exists for the convenience of the overloaded operators while normal functions can do the
 199 /// same.
 200 #[derive(Clone)]
 201 struct MinifyingSugg<'a>(Sugg<'a>);
 202
 203 impl<'a> Display for MinifyingSugg<'a> {
 204     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 205         self.0.fmt(f)
 206     }
 207 }
 208
 209 impl<'a> MinifyingSugg<'a> {
 210     fn into_sugg(self) -> Sugg<'a> {
 211         self.0
 212     }
 213 }
 214
 215 impl<'a> From<Sugg<'a>> for MinifyingSugg<'a> {
 216     fn from(sugg: Sugg<'a>) -> Self {
 217         Self(sugg)
 218     }
 219 }
 220
 221 impl std::ops::Add for &MinifyingSugg<'static> {
 222     type Output = MinifyingSugg<'static>;
 223     fn add(self, rhs: &MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 224         match (self.to_string().as_str(), rhs.to_string().as_str()) {
 225             ("0", _) => rhs.clone(),
 226             (_, "0") => self.clone(),
 227             (_, _) => (&self.0 + &rhs.0).into(),
 228         }
 229     }
 230 }
 231
 232 impl std::ops::Sub for &MinifyingSugg<'static> {
 233     type Output = MinifyingSugg<'static>;
 234     fn sub(self, rhs: &MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 235         match (self.to_string().as_str(), rhs.to_string().as_str()) {
 236             (_, "0") => self.clone(),
 237             ("0", _) => (-rhs.0.clone()).into(),
 238             (x, y) if x == y => sugg::ZERO.into(),
 239             (_, _) => (&self.0 - &rhs.0).into(),
 240         }
 241     }
 242 }
 243
 244 impl std::ops::Add<&MinifyingSugg<'static>> for MinifyingSugg<'static> {
 245     type Output = MinifyingSugg<'static>;
 246     fn add(self, rhs: &MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 247         match (self.to_string().as_str(), rhs.to_string().as_str()) {
 248             ("0", _) => rhs.clone(),
 249             (_, "0") => self,
 250             (_, _) => (self.0 + &rhs.0).into(),
 251         }
 252     }
 253 }
 254
 255 impl std::ops::Sub<&MinifyingSugg<'static>> for MinifyingSugg<'static> {
 256     type Output = MinifyingSugg<'static>;
 257     fn sub(self, rhs: &MinifyingSugg<'static>) -> MinifyingSugg<'static> {
 258         match (self.to_string().as_str(), rhs.to_string().as_str()) {
 259             (_, "0") => self,
 260             ("0", _) => (-rhs.0.clone()).into(),
 261             (x, y) if x == y => sugg::ZERO.into(),
 262             (_, _) => (self.0 - &rhs.0).into(),
 263         }
 264     }
 265 }
 266
 267 /// a wrapper around `MinifyingSugg`, which carries an operator like currying
 268 /// so that the suggested code become more efficient (e.g. `foo + -bar` `foo - bar`).
 269 struct Offset {
 270     value: MinifyingSugg<'static>,
 271     sign: OffsetSign,
 272 }
 273
 274 #[derive(Clone, Copy)]
 275 enum OffsetSign {
 276     Positive,
 277     Negative,
 278 }
 279
 280 impl Offset {
 281     fn negative(value: Sugg<'static>) -> Self {
 282         Self {
 283             value: value.into(),
 284             sign: OffsetSign::Negative,
 285         }
 286     }
 287
 288     fn positive(value: Sugg<'static>) -> Self {
 289         Self {
 290             value: value.into(),
 291             sign: OffsetSign::Positive,
 292         }
 293     }
 294
 295     fn empty() -> Self {
 296         Self::positive(sugg::ZERO)
 297     }
 298 }
 299
 300 fn apply_offset(lhs: &MinifyingSugg<'static>, rhs: &Offset) -> MinifyingSugg<'static> {
 301     match rhs.sign {
 302         OffsetSign::Positive => lhs + &rhs.value,
 303         OffsetSign::Negative => lhs - &rhs.value,
 304     }
 305 }
 306
 307 #[derive(Debug, Clone, Copy)]
 308 enum StartKind<'hir> {
 309     Range,
 310     Counter { initializer: &'hir Expr<'hir> },
 311 }
 312
 313 struct IndexExpr<'hir> {
 314     base: &'hir Expr<'hir>,
 315     idx: StartKind<'hir>,
 316     idx_offset: Offset,
 317 }
 318
 319 struct Start<'hir> {
 320     id: HirId,
 321     kind: StartKind<'hir>,
 322 }
 323
 324 fn get_slice_like_element_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
 325     match ty.kind() {
 326         ty::Adt(adt, subs) if cx.tcx.is_diagnostic_item(sym::Vec, adt.did()) => Some(subs.type_at(0)),
 327         ty::Ref(_, subty, _) => get_slice_like_element_ty(cx, *subty),
 328         ty::Slice(ty) | ty::Array(ty, _) => Some(*ty),
 329         _ => None,
 330     }
 331 }
 332
 333 fn fetch_cloned_expr<'tcx>(expr: &'tcx Expr<'tcx>) -> &'tcx Expr<'tcx> {
 334     if_chain! {
 335         if let ExprKind::MethodCall(method, arg, [], _) = expr.kind;
 336         if method.ident.name == sym::clone;
 337         then { arg } else { expr }
 338     }
 339 }
 340
 341 fn get_details_from_idx<'tcx>(
 342     cx: &LateContext<'tcx>,
 343     idx: &Expr<'_>,
 344     starts: &[Start<'tcx>],
 345 ) -> Option<(StartKind<'tcx>, Offset)> {
 346     fn get_start<'tcx>(e: &Expr<'_>, starts: &[Start<'tcx>]) -> Option<StartKind<'tcx>> {
 347         let id = path_to_local(e)?;
 348         starts.iter().find(|start| start.id == id).map(|start| start.kind)
 349     }
 350
 351     fn get_offset<'tcx>(cx: &LateContext<'tcx>, e: &Expr<'_>, starts: &[Start<'tcx>]) -> Option<Sugg<'static>> {
 352         match &e.kind {
 353             ExprKind::Lit(l) => match l.node {
 354                 ast::LitKind::Int(x, _ty) => Some(Sugg::NonParen(x.to_string().into())),
 355                 _ => None,
 356             },
 357             ExprKind::Path(..) if get_start(e, starts).is_none() => Some(Sugg::hir(cx, e, "???")),
 358             _ => None,
 359         }
 360     }
 361
 362     match idx.kind {
 363         ExprKind::Binary(op, lhs, rhs) => match op.node {
 364             BinOpKind::Add => {
 365                 let offset_opt = get_start(lhs, starts)
 366                     .and_then(|s| get_offset(cx, rhs, starts).map(|o| (s, o)))
 367                     .or_else(|| get_start(rhs, starts).and_then(|s| get_offset(cx, lhs, starts).map(|o| (s, o))));
 368
 369                 offset_opt.map(|(s, o)| (s, Offset::positive(o)))
 370             },
 371             BinOpKind::Sub => {
 372                 get_start(lhs, starts).and_then(|s| get_offset(cx, rhs, starts).map(|o| (s, Offset::negative(o))))
 373             },
 374             _ => None,
 375         },
 376         ExprKind::Path(..) => get_start(idx, starts).map(|s| (s, Offset::empty())),
 377         _ => None,
 378     }
 379 }
 380
 381 fn get_assignment<'tcx>(e: &'tcx Expr<'tcx>) -> Option<(&'tcx Expr<'tcx>, &'tcx Expr<'tcx>)> {
 382     if let ExprKind::Assign(lhs, rhs, _) = e.kind {
 383         Some((lhs, rhs))
 384     } else {
 385         None
 386     }
 387 }
 388
 389 /// Get assignments from the given block.
 390 /// The returned iterator yields `None` if no assignment expressions are there,
 391 /// filtering out the increments of the given whitelisted loop counters;
 392 /// because its job is to make sure there's nothing other than assignments and the increments.
 393 fn get_assignments<'a, 'tcx>(
 394     Block { stmts, expr, .. }: &'tcx Block<'tcx>,
 395     loop_counters: &'a [Start<'tcx>],
 396 ) -> impl Iterator<Item = Option<(&'tcx Expr<'tcx>, &'tcx Expr<'tcx>)>> + 'a {
 397     // As the `filter` and `map` below do different things, I think putting together
 398     // just increases complexity. (cc #3188 and #4193)
 399     stmts
 400         .iter()
 401         .filter_map(move |stmt| match stmt.kind {
 402             StmtKind::Local(..) | StmtKind::Item(..) => None,
 403             StmtKind::Expr(e) | StmtKind::Semi(e) => Some(e),
 404         })
 405         .chain((*expr).into_iter())
 406         .filter(move |e| {
 407             if let ExprKind::AssignOp(_, place, _) = e.kind {
 408                 path_to_local(place).map_or(false, |id| {
 409                     !loop_counters
 410                         .iter()
 411                         // skip the first item which should be `StartKind::Range`
 412                         // this makes it possible to use the slice with `StartKind::Range` in the same iterator loop.
 413                         .skip(1)
 414                         .any(|counter| counter.id == id)
 415                 })
 416             } else {
 417                 true
 418             }
 419         })
 420         .map(get_assignment)
 421 }
 422
 423 fn get_loop_counters<'a, 'tcx>(
 424     cx: &'a LateContext<'tcx>,
 425     body: &'tcx Block<'tcx>,
 426     expr: &'tcx Expr<'_>,
 427 ) -> Option<impl Iterator<Item = Start<'tcx>> + 'a> {
 428     // Look for variables that are incremented once per loop iteration.
 429     let mut increment_visitor = IncrementVisitor::new(cx);
 430     walk_block(&mut increment_visitor, body);
 431
 432     // For each candidate, check the parent block to see if
 433     // it's initialized to zero at the start of the loop.
 434     get_enclosing_block(cx, expr.hir_id).and_then(|block| {
 435         increment_visitor
 436             .into_results()
 437             .filter_map(move |var_id| {
 438                 let mut initialize_visitor = InitializeVisitor::new(cx, expr, var_id);
 439                 walk_block(&mut initialize_visitor, block);
 440
 441                 initialize_visitor.get_result().map(|(_, _, initializer)| Start {
 442                     id: var_id,
 443                     kind: StartKind::Counter { initializer },
 444                 })
 445             })
 446             .into()
 447     })
 448 }