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