clippy_lints/src/loops/needless_range_loop.rs

   1 use super::NEEDLESS_RANGE_LOOP;
   2 use clippy_utils::diagnostics::{multispan_sugg, span_lint_and_then};
   3 use clippy_utils::source::snippet;
   4 use clippy_utils::ty::has_iter_method;
   5 use clippy_utils::visitors::is_local_used;
   6 use clippy_utils::{contains_name, higher, is_integer_const, match_trait_method, paths, sugg, SpanlessEq};
   7 use if_chain::if_chain;
   8 use rustc_ast::ast;
   9 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  10 use rustc_hir::def::{DefKind, Res};
  11 use rustc_hir::intravisit::{walk_expr, Visitor};
  12 use rustc_hir::{BinOpKind, BorrowKind, Expr, ExprKind, HirId, Mutability, Pat, PatKind, QPath};
  13 use rustc_lint::LateContext;
  14 use rustc_middle::middle::region;
  15 use rustc_middle::ty::{self, Ty};
  16 use rustc_span::symbol::{sym, Symbol};
  17 use std::iter::{self, Iterator};
  18 use std::mem;
  19
  20 /// Checks for looping over a range and then indexing a sequence with it.
  21 /// The iteratee must be a range literal.
  22 #[allow(clippy::too_many_lines)]
  23 pub(super) fn check<'tcx>(
  24     cx: &LateContext<'tcx>,
  25     pat: &'tcx Pat<'_>,
  26     arg: &'tcx Expr<'_>,
  27     body: &'tcx Expr<'_>,
  28     expr: &'tcx Expr<'_>,
  29 ) {
  30     if let Some(higher::Range {
  31         start: Some(start),
  32         ref end,
  33         limits,
  34     }) = higher::Range::hir(arg)
  35     {
  36         // the var must be a single name
  37         if let PatKind::Binding(_, canonical_id, ident, _) = pat.kind {
  38             let mut visitor = VarVisitor {
  39                 cx,
  40                 var: canonical_id,
  41                 indexed_mut: FxHashSet::default(),
  42                 indexed_indirectly: FxHashMap::default(),
  43                 indexed_directly: FxHashMap::default(),
  44                 referenced: FxHashSet::default(),
  45                 nonindex: false,
  46                 prefer_mutable: false,
  47             };
  48             walk_expr(&mut visitor, body);
  49
  50             // linting condition: we only indexed one variable, and indexed it directly
  51             if visitor.indexed_indirectly.is_empty() && visitor.indexed_directly.len() == 1 {
  52                 let (indexed, (indexed_extent, indexed_ty)) = visitor
  53                     .indexed_directly
  54                     .into_iter()
  55                     .next()
  56                     .expect("already checked that we have exactly 1 element");
  57
  58                 // ensure that the indexed variable was declared before the loop, see #601
  59                 if let Some(indexed_extent) = indexed_extent {
  60                     let parent_def_id = cx.tcx.hir().get_parent_item(expr.hir_id);
  61                     let region_scope_tree = cx.tcx.region_scope_tree(parent_def_id);
  62                     let pat_extent = region_scope_tree.var_scope(pat.hir_id.local_id);
  63                     if region_scope_tree.is_subscope_of(indexed_extent, pat_extent) {
  64                         return;
  65                     }
  66                 }
  67
  68                 // don't lint if the container that is indexed does not have .iter() method
  69                 let has_iter = has_iter_method(cx, indexed_ty);
  70                 if has_iter.is_none() {
  71                     return;
  72                 }
  73
  74                 // don't lint if the container that is indexed into is also used without
  75                 // indexing
  76                 if visitor.referenced.contains(&indexed) {
  77                     return;
  78                 }
  79
  80                 let starts_at_zero = is_integer_const(cx, start, 0);
  81
  82                 let skip = if starts_at_zero {
  83                     String::new()
  84                 } else if visitor.indexed_mut.contains(&indexed) && contains_name(indexed, start) {
  85                     return;
  86                 } else {
  87                     format!(".skip({})", snippet(cx, start.span, ".."))
  88                 };
  89
  90                 let mut end_is_start_plus_val = false;
  91
  92                 let take = if let Some(end) = *end {
  93                     let mut take_expr = end;
  94
  95                     if let ExprKind::Binary(ref op, left, right) = end.kind {
  96                         if op.node == BinOpKind::Add {
  97                             let start_equal_left = SpanlessEq::new(cx).eq_expr(start, left);
  98                             let start_equal_right = SpanlessEq::new(cx).eq_expr(start, right);
  99
 100                             if start_equal_left {
 101                                 take_expr = right;
 102                             } else if start_equal_right {
 103                                 take_expr = left;
 104                             }
 105
 106                             end_is_start_plus_val = start_equal_left | start_equal_right;
 107                         }
 108                     }
 109
 110                     if is_len_call(end, indexed) || is_end_eq_array_len(cx, end, limits, indexed_ty) {
 111                         String::new()
 112                     } else if visitor.indexed_mut.contains(&indexed) && contains_name(indexed, take_expr) {
 113                         return;
 114                     } else {
 115                         match limits {
 116                             ast::RangeLimits::Closed => {
 117                                 let take_expr = sugg::Sugg::hir(cx, take_expr, "<count>");
 118                                 format!(".take({})", take_expr + sugg::ONE)
 119                             },
 120                             ast::RangeLimits::HalfOpen => format!(".take({})", snippet(cx, take_expr.span, "..")),
 121                         }
 122                     }
 123                 } else {
 124                     String::new()
 125                 };
 126
 127                 let (ref_mut, method) = if visitor.indexed_mut.contains(&indexed) {
 128                     ("mut ", "iter_mut")
 129                 } else {
 130                     ("", "iter")
 131                 };
 132
 133                 let take_is_empty = take.is_empty();
 134                 let mut method_1 = take;
 135                 let mut method_2 = skip;
 136
 137                 if end_is_start_plus_val {
 138                     mem::swap(&mut method_1, &mut method_2);
 139                 }
 140
 141                 if visitor.nonindex {
 142                     span_lint_and_then(
 143                         cx,
 144                         NEEDLESS_RANGE_LOOP,
 145                         arg.span,
 146                         &format!("the loop variable `{}` is used to index `{}`", ident.name, indexed),
 147                         |diag| {
 148                             multispan_sugg(
 149                                 diag,
 150                                 "consider using an iterator",
 151                                 vec![
 152                                     (pat.span, format!("({}, <item>)", ident.name)),
 153                                     (
 154                                         arg.span,
 155                                         format!("{}.{}().enumerate(){}{}", indexed, method, method_1, method_2),
 156                                     ),
 157                                 ],
 158                             );
 159                         },
 160                     );
 161                 } else {
 162                     let repl = if starts_at_zero && take_is_empty {
 163                         format!("&{}{}", ref_mut, indexed)
 164                     } else {
 165                         format!("{}.{}(){}{}", indexed, method, method_1, method_2)
 166                     };
 167
 168                     span_lint_and_then(
 169                         cx,
 170                         NEEDLESS_RANGE_LOOP,
 171                         arg.span,
 172                         &format!("the loop variable `{}` is only used to index `{}`", ident.name, indexed),
 173                         |diag| {
 174                             multispan_sugg(
 175                                 diag,
 176                                 "consider using an iterator",
 177                                 vec![(pat.span, "<item>".to_string()), (arg.span, repl)],
 178                             );
 179                         },
 180                     );
 181                 }
 182             }
 183         }
 184     }
 185 }
 186
 187 fn is_len_call(expr: &Expr<'_>, var: Symbol) -> bool {
 188     if_chain! {
 189         if let ExprKind::MethodCall(method, len_args, _) = expr.kind;
 190         if len_args.len() == 1;
 191         if method.ident.name == sym::len;
 192         if let ExprKind::Path(QPath::Resolved(_, path)) = len_args[0].kind;
 193         if path.segments.len() == 1;
 194         if path.segments[0].ident.name == var;
 195         then {
 196             return true;
 197         }
 198     }
 199
 200     false
 201 }
 202
 203 fn is_end_eq_array_len<'tcx>(
 204     cx: &LateContext<'tcx>,
 205     end: &Expr<'_>,
 206     limits: ast::RangeLimits,
 207     indexed_ty: Ty<'tcx>,
 208 ) -> bool {
 209     if_chain! {
 210         if let ExprKind::Lit(ref lit) = end.kind;
 211         if let ast::LitKind::Int(end_int, _) = lit.node;
 212         if let ty::Array(_, arr_len_const) = indexed_ty.kind();
 213         if let Some(arr_len) = arr_len_const.try_eval_usize(cx.tcx, cx.param_env);
 214         then {
 215             return match limits {
 216                 ast::RangeLimits::Closed => end_int + 1 >= arr_len.into(),
 217                 ast::RangeLimits::HalfOpen => end_int >= arr_len.into(),
 218             };
 219         }
 220     }
 221
 222     false
 223 }
 224
 225 struct VarVisitor<'a, 'tcx> {
 226     /// context reference
 227     cx: &'a LateContext<'tcx>,
 228     /// var name to look for as index
 229     var: HirId,
 230     /// indexed variables that are used mutably
 231     indexed_mut: FxHashSet<Symbol>,
 232     /// indirectly indexed variables (`v[(i + 4) % N]`), the extend is `None` for global
 233     indexed_indirectly: FxHashMap<Symbol, Option<region::Scope>>,
 234     /// subset of `indexed` of vars that are indexed directly: `v[i]`
 235     /// this will not contain cases like `v[calc_index(i)]` or `v[(i + 4) % N]`
 236     indexed_directly: FxHashMap<Symbol, (Option<region::Scope>, Ty<'tcx>)>,
 237     /// Any names that are used outside an index operation.
 238     /// Used to detect things like `&mut vec` used together with `vec[i]`
 239     referenced: FxHashSet<Symbol>,
 240     /// has the loop variable been used in expressions other than the index of
 241     /// an index op?
 242     nonindex: bool,
 243     /// Whether we are inside the `$` in `&mut $` or `$ = foo` or `$.bar`, where bar
 244     /// takes `&mut self`
 245     prefer_mutable: bool,
 246 }
 247
 248 impl<'a, 'tcx> VarVisitor<'a, 'tcx> {
 249     fn check(&mut self, idx: &'tcx Expr<'_>, seqexpr: &'tcx Expr<'_>, expr: &'tcx Expr<'_>) -> bool {
 250         if_chain! {
 251             // the indexed container is referenced by a name
 252             if let ExprKind::Path(ref seqpath) = seqexpr.kind;
 253             if let QPath::Resolved(None, seqvar) = *seqpath;
 254             if seqvar.segments.len() == 1;
 255             if is_local_used(self.cx, idx, self.var);
 256             then {
 257                 if self.prefer_mutable {
 258                     self.indexed_mut.insert(seqvar.segments[0].ident.name);
 259                 }
 260                 let index_used_directly = matches!(idx.kind, ExprKind::Path(_));
 261                 let res = self.cx.qpath_res(seqpath, seqexpr.hir_id);
 262                 match res {
 263                     Res::Local(hir_id) => {
 264                         let parent_def_id = self.cx.tcx.hir().get_parent_item(expr.hir_id);
 265                         let extent = self.cx.tcx.region_scope_tree(parent_def_id).var_scope(hir_id.local_id);
 266                         if index_used_directly {
 267                             self.indexed_directly.insert(
 268                                 seqvar.segments[0].ident.name,
 269                                 (Some(extent), self.cx.typeck_results().node_type(seqexpr.hir_id)),
 270                             );
 271                         } else {
 272                             self.indexed_indirectly.insert(seqvar.segments[0].ident.name, Some(extent));
 273                         }
 274                         return false;  // no need to walk further *on the variable*
 275                     }
 276                     Res::Def(DefKind::Static | DefKind::Const, ..) => {
 277                         if index_used_directly {
 278                             self.indexed_directly.insert(
 279                                 seqvar.segments[0].ident.name,
 280                                 (None, self.cx.typeck_results().node_type(seqexpr.hir_id)),
 281                             );
 282                         } else {
 283                             self.indexed_indirectly.insert(seqvar.segments[0].ident.name, None);
 284                         }
 285                         return false;  // no need to walk further *on the variable*
 286                     }
 287                     _ => (),
 288                 }
 289             }
 290         }
 291         true
 292     }
 293 }
 294
 295 impl<'a, 'tcx> Visitor<'tcx> for VarVisitor<'a, 'tcx> {
 296     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
 297         if_chain! {
 298             // a range index op
 299             if let ExprKind::MethodCall(meth, [args_0, args_1, ..], _) = &expr.kind;
 300             if (meth.ident.name == sym::index && match_trait_method(self.cx, expr, &paths::INDEX))
 301                 || (meth.ident.name == sym::index_mut && match_trait_method(self.cx, expr, &paths::INDEX_MUT));
 302             if !self.check(args_1, args_0, expr);
 303             then { return }
 304         }
 305
 306         if_chain! {
 307             // an index op
 308             if let ExprKind::Index(seqexpr, idx) = expr.kind;
 309             if !self.check(idx, seqexpr, expr);
 310             then { return }
 311         }
 312
 313         if_chain! {
 314             // directly using a variable
 315             if let ExprKind::Path(QPath::Resolved(None, path)) = expr.kind;
 316             if let Res::Local(local_id) = path.res;
 317             then {
 318                 if local_id == self.var {
 319                     self.nonindex = true;
 320                 } else {
 321                     // not the correct variable, but still a variable
 322                     self.referenced.insert(path.segments[0].ident.name);
 323                 }
 324             }
 325         }
 326
 327         let old = self.prefer_mutable;
 328         match expr.kind {
 329             ExprKind::AssignOp(_, lhs, rhs) | ExprKind::Assign(lhs, rhs, _) => {
 330                 self.prefer_mutable = true;
 331                 self.visit_expr(lhs);
 332                 self.prefer_mutable = false;
 333                 self.visit_expr(rhs);
 334             },
 335             ExprKind::AddrOf(BorrowKind::Ref, mutbl, expr) => {
 336                 if mutbl == Mutability::Mut {
 337                     self.prefer_mutable = true;
 338                 }
 339                 self.visit_expr(expr);
 340             },
 341             ExprKind::Call(f, args) => {
 342                 self.visit_expr(f);
 343                 for expr in args {
 344                     let ty = self.cx.typeck_results().expr_ty_adjusted(expr);
 345                     self.prefer_mutable = false;
 346                     if let ty::Ref(_, _, mutbl) = *ty.kind() {
 347                         if mutbl == Mutability::Mut {
 348                             self.prefer_mutable = true;
 349                         }
 350                     }
 351                     self.visit_expr(expr);
 352                 }
 353             },
 354             ExprKind::MethodCall(_, args, _) => {
 355                 let def_id = self.cx.typeck_results().type_dependent_def_id(expr.hir_id).unwrap();
 356                 for (ty, expr) in iter::zip(self.cx.tcx.fn_sig(def_id).inputs().skip_binder(), args) {
 357                     self.prefer_mutable = false;
 358                     if let ty::Ref(_, _, mutbl) = *ty.kind() {
 359                         if mutbl == Mutability::Mut {
 360                             self.prefer_mutable = true;
 361                         }
 362                     }
 363                     self.visit_expr(expr);
 364                 }
 365             },
 366             ExprKind::Closure(_, _, body_id, ..) => {
 367                 let body = self.cx.tcx.hir().body(body_id);
 368                 self.visit_expr(&body.value);
 369             },
 370             _ => walk_expr(self, expr),
 371         }
 372         self.prefer_mutable = old;
 373     }
 374 }