clippy_lints/src/loops/needless_range_loop.rs

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