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;
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;
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>,
27 if let Some(higher::Range {
31 }) = higher::Range::hir(arg)
33 // the var must be a single name
34 if let PatKind::Binding(_, canonical_id, _, _) = pat.kind {
35 let mut starts = vec![Start {
37 kind: StartKind::Range,
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;
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);
49 iter_a = Some(get_assignments(block, &starts));
51 iter_b = Some(get_assignment(body));
54 let assignments = iter_a.into_iter().flatten().chain(iter_b.into_iter());
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).
60 o.and_then(|(lhs, rhs)| {
61 let rhs = fetch_cloned_expr(rhs);
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);
70 // Source and destination must be different
71 if path_to_local(base_left) != path_to_local(base_right);
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 }))
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 "));
86 if let Some(big_sugg) = big_sugg {
91 "it looks like you're manually copying between slices",
92 "try replacing the loop by",
94 Applicability::Unspecified,
103 fn build_manual_memcpy_suggestion<'tcx>(
104 cx: &LateContext<'tcx>,
107 limits: ast::RangeLimits,
112 fn print_offset(offset: MinifyingSugg<'static>) -> MinifyingSugg<'static> {
113 if offset.to_string() == "0" {
120 let print_limit = |end: &Expr<'_>, end_str: &str, base: &Expr<'_>, sugg: MinifyingSugg<'static>| {
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);
128 if sugg.to_string() == end_str {
135 ast::RangeLimits::Closed => {
136 sugg + &sugg::ONE.into()
138 ast::RangeLimits::HalfOpen => sugg,
144 let start_str = Sugg::hir(cx, start, "").into();
145 let end_str: MinifyingSugg<'_> = Sugg::hir(cx, end, "").into();
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(),
152 end_str.to_string().as_str(),
154 apply_offset(&end_str, &idx_expr.idx_offset),
158 StartKind::Counter { initializer } => {
159 let counter_start = Sugg::hir(cx, initializer, "").into();
161 print_offset(apply_offset(&counter_start, &idx_expr.idx_offset)).into_sugg(),
164 end_str.to_string().as_str(),
166 apply_offset(&end_str, &idx_expr.idx_offset) + &counter_start - &start_str,
173 let (dst_offset, dst_limit) = print_offset_and_limit(dst);
174 let (src_offset, src_limit) = print_offset_and_limit(src);
176 let dst_base_str = snippet(cx, dst.base.span, "???");
177 let src_base_str = snippet(cx, src.base.span, "???");
179 let dst = if dst_offset == sugg::EMPTY && dst_limit == sugg::EMPTY {
185 dst_offset.maybe_par(),
186 dst_limit.maybe_par()
191 let method_str = if is_copy(cx, elem_ty) {
198 "{}.{}(&{}[{}..{}]);",
202 src_offset.maybe_par(),
203 src_limit.maybe_par()
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
212 struct MinifyingSugg<'a>(Sugg<'a>);
214 impl<'a> Display for MinifyingSugg<'a> {
215 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
220 impl<'a> MinifyingSugg<'a> {
221 fn into_sugg(self) -> Sugg<'a> {
226 impl<'a> From<Sugg<'a>> for MinifyingSugg<'a> {
227 fn from(sugg: Sugg<'a>) -> Self {
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(),
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(),
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(),
261 (_, _) => (self.0 + &rhs.0).into(),
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()) {
271 ("0", _) => (-rhs.0.clone()).into(),
272 (x, y) if x == y => sugg::ZERO.into(),
273 (_, _) => (self.0 - &rhs.0).into(),
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`).
281 value: MinifyingSugg<'static>,
285 #[derive(Clone, Copy)]
292 fn negative(value: Sugg<'static>) -> Self {
295 sign: OffsetSign::Negative,
299 fn positive(value: Sugg<'static>) -> Self {
302 sign: OffsetSign::Positive,
307 Self::positive(sugg::ZERO)
311 fn apply_offset(lhs: &MinifyingSugg<'static>, rhs: &Offset) -> MinifyingSugg<'static> {
313 OffsetSign::Positive => lhs + &rhs.value,
314 OffsetSign::Negative => lhs - &rhs.value,
318 #[derive(Debug, Clone, Copy)]
319 enum StartKind<'hir> {
321 Counter { initializer: &'hir Expr<'hir> },
324 struct IndexExpr<'hir> {
325 base: &'hir Expr<'hir>,
326 idx: StartKind<'hir>,
332 kind: StartKind<'hir>,
335 fn get_slice_like_element_ty<'tcx>(cx: &LateContext<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
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),
344 fn fetch_cloned_expr<'tcx>(expr: &'tcx Expr<'tcx>) -> &'tcx Expr<'tcx> {
346 if let ExprKind::MethodCall(method, _, args, _) = expr.kind;
347 if method.ident.name == sym::clone;
349 if let Some(arg) = args.get(0);
350 then { arg } else { expr }
354 fn get_details_from_idx<'tcx>(
355 cx: &LateContext<'tcx>,
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)
364 fn get_offset<'tcx>(cx: &LateContext<'tcx>, e: &Expr<'_>, starts: &[Start<'tcx>]) -> Option<Sugg<'static>> {
366 ExprKind::Lit(l) => match l.node {
367 ast::LitKind::Int(x, _ty) => Some(Sugg::NonParen(x.to_string().into())),
370 ExprKind::Path(..) if get_start(e, starts).is_none() => Some(Sugg::hir(cx, e, "???")),
376 ExprKind::Binary(op, lhs, rhs) => match op.node {
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))));
382 offset_opt.map(|(s, o)| (s, Offset::positive(o)))
385 get_start(lhs, starts).and_then(|s| get_offset(cx, rhs, starts).map(|o| (s, Offset::negative(o))))
389 ExprKind::Path(..) => get_start(idx, starts).map(|s| (s, Offset::empty())),
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 {
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)
414 .filter_map(move |stmt| match stmt.kind {
415 StmtKind::Local(..) | StmtKind::Item(..) => None,
416 StmtKind::Expr(e) | StmtKind::Semi(e) => Some(e),
418 .chain((*expr).into_iter())
420 if let ExprKind::AssignOp(_, place, _) = e.kind {
421 path_to_local(place).map_or(false, |id| {
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.
427 .any(|counter| counter.id == id)
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);
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| {
450 .filter_map(move |var_id| {
451 let mut initialize_visitor = InitializeVisitor::new(cx, expr, var_id);
452 walk_block(&mut initialize_visitor, block);
454 initialize_visitor.get_result().map(|(_, _, initializer)| Start {
456 kind: StartKind::Counter { initializer },