src/loops.rs

   1 use rustc::lint::*;
   2 use rustc_front::hir::*;
   3 use reexport::*;
   4 use rustc_front::visit::{Visitor, walk_expr, walk_block, walk_decl};
   5 use rustc::middle::ty;
   6 use rustc::middle::def::DefLocal;
   7 use consts::{constant_simple, Constant};
   8 use rustc::front::map::Node::{NodeBlock};
   9 use std::collections::{HashSet,HashMap};
  10 use syntax::ast::Lit_::*;
  11
  12 use utils::{snippet, span_lint, get_parent_expr, match_trait_method, match_type,
  13             in_external_macro, expr_block, span_help_and_lint, is_integer_literal};
  14 use utils::{VEC_PATH, LL_PATH};
  15
  16 declare_lint!{ pub NEEDLESS_RANGE_LOOP, Warn,
  17                "for-looping over a range of indices where an iterator over items would do" }
  18
  19 declare_lint!{ pub EXPLICIT_ITER_LOOP, Warn,
  20                "for-looping over `_.iter()` or `_.iter_mut()` when `&_` or `&mut _` would do" }
  21
  22 declare_lint!{ pub ITER_NEXT_LOOP, Warn,
  23                "for-looping over `_.next()` which is probably not intended" }
  24
  25 declare_lint!{ pub WHILE_LET_LOOP, Warn,
  26                "`loop { if let { ... } else break }` can be written as a `while let` loop" }
  27
  28 declare_lint!{ pub UNUSED_COLLECT, Warn,
  29                "`collect()`ing an iterator without using the result; this is usually better \
  30                 written as a for loop" }
  31
  32 declare_lint!{ pub REVERSE_RANGE_LOOP, Warn,
  33                "Iterating over an empty range, such as `10..0` or `5..5`" }
  34
  35 declare_lint!{ pub EXPLICIT_COUNTER_LOOP, Warn,
  36                "for-looping with an explicit counter when `_.enumerate()` would do" }
  37
  38 #[derive(Copy, Clone)]
  39 pub struct LoopsPass;
  40
  41 impl LintPass for LoopsPass {
  42     fn get_lints(&self) -> LintArray {
  43         lint_array!(NEEDLESS_RANGE_LOOP, EXPLICIT_ITER_LOOP, ITER_NEXT_LOOP,
  44                     WHILE_LET_LOOP, UNUSED_COLLECT, REVERSE_RANGE_LOOP, EXPLICIT_COUNTER_LOOP)
  45     }
  46 }
  47
  48 impl LateLintPass for LoopsPass {
  49     fn check_expr(&mut self, cx: &LateContext, expr: &Expr) {
  50         if let Some((pat, arg, body)) = recover_for_loop(expr) {
  51             // check for looping over a range and then indexing a sequence with it
  52             // -> the iteratee must be a range literal
  53             if let ExprRange(Some(ref l), _) = arg.node {
  54                 // Range should start with `0`
  55                 if let ExprLit(ref lit) = l.node {
  56                     if let LitInt(0, _) = lit.node {
  57
  58                         // the var must be a single name
  59                         if let PatIdent(_, ref ident, _) = pat.node {
  60                             let mut visitor = VarVisitor { cx: cx, var: ident.node.name,
  61                                                            indexed: HashSet::new(), nonindex: false };
  62                             walk_expr(&mut visitor, body);
  63                             // linting condition: we only indexed one variable
  64                             if visitor.indexed.len() == 1 {
  65                                 let indexed = visitor.indexed.into_iter().next().expect(
  66                                     "Len was nonzero, but no contents found");
  67                                 if visitor.nonindex {
  68                                     span_lint(cx, NEEDLESS_RANGE_LOOP, expr.span, &format!(
  69                                         "the loop variable `{}` is used to index `{}`. Consider using \
  70                                          `for ({}, item) in {}.iter().enumerate()` or similar iterators",
  71                                         ident.node.name, indexed, ident.node.name, indexed));
  72                                 } else {
  73                                     span_lint(cx, NEEDLESS_RANGE_LOOP, expr.span, &format!(
  74                                         "the loop variable `{}` is only used to index `{}`. \
  75                                          Consider using `for item in &{}` or similar iterators",
  76                                         ident.node.name, indexed, indexed));
  77                                 }
  78                             }
  79                         }
  80                     }
  81                 }
  82             }
  83
  84             // if this for loop is iterating over a two-sided range...
  85             if let ExprRange(Some(ref start_expr), Some(ref stop_expr)) = arg.node {
  86                 // ...and both sides are compile-time constant integers...
  87                 if let Some(Constant::ConstantInt(start_idx, _)) = constant_simple(start_expr) {
  88                     if let Some(Constant::ConstantInt(stop_idx, _)) = constant_simple(stop_expr) {
  89                         // ...and the start index is greater than the stop index,
  90                         // this loop will never run. This is often confusing for developers
  91                         // who think that this will iterate from the larger value to the
  92                         // smaller value.
  93                         if start_idx > stop_idx {
  94                             span_help_and_lint(cx, REVERSE_RANGE_LOOP, expr.span,
  95                                 "this range is empty so this for loop will never run",
  96                                 &format!("Consider using `({}..{}).rev()` if you are attempting to \
  97                                 iterate over this range in reverse", stop_idx, start_idx));
  98                         } else if start_idx == stop_idx {
  99                             // if they are equal, it's also problematic - this loop
 100                             // will never run.
 101                             span_lint(cx, REVERSE_RANGE_LOOP, expr.span,
 102                                 "this range is empty so this for loop will never run");
 103                         }
 104                     }
 105                 }
 106             }
 107
 108             if let ExprMethodCall(ref method, _, ref args) = arg.node {
 109                 // just the receiver, no arguments
 110                 if args.len() == 1 {
 111                     let method_name = method.node;
 112                     // check for looping over x.iter() or x.iter_mut(), could use &x or &mut x
 113                     if method_name.as_str() == "iter" || method_name.as_str() == "iter_mut" {
 114                         if is_ref_iterable_type(cx, &args[0]) {
 115                             let object = snippet(cx, args[0].span, "_");
 116                             span_lint(cx, EXPLICIT_ITER_LOOP, expr.span, &format!(
 117                                 "it is more idiomatic to loop over `&{}{}` instead of `{}.{}()`",
 118                                 if method_name.as_str() == "iter_mut" { "mut " } else { "" },
 119                                 object, object, method_name));
 120                         }
 121                     }
 122                     // check for looping over Iterator::next() which is not what you want
 123                     else if method_name.as_str() == "next" &&
 124                             match_trait_method(cx, arg, &["core", "iter", "Iterator"]) {
 125                         span_lint(cx, ITER_NEXT_LOOP, expr.span,
 126                                   "you are iterating over `Iterator::next()` which is an Option; \
 127                                    this will compile but is probably not what you want");
 128                     }
 129                 }
 130             }
 131
 132             // Look for variables that are incremented once per loop iteration.
 133             let mut visitor = IncrementVisitor { cx: cx, states: HashMap::new(), depth: 0, done: false };
 134             walk_expr(&mut visitor, body);
 135
 136             // For each candidate, check the parent block to see if
 137             // it's initialized to zero at the start of the loop.
 138             let map = &cx.tcx.map;
 139             let parent_scope = map.get_enclosing_scope(expr.id).and_then(|id| map.get_enclosing_scope(id) );
 140             if let Some(parent_id) = parent_scope {
 141                 if let NodeBlock(block) = map.get(parent_id) {
 142                     for (id, _) in visitor.states.iter().filter( |&(_,v)| *v == VarState::IncrOnce) {
 143                         let mut visitor2 = InitializeVisitor { cx: cx, end_expr: expr, var_id: id.clone(),
 144                                                                state: VarState::IncrOnce, name: None,
 145                                                                depth: 0, done: false };
 146                         walk_block(&mut visitor2, block);
 147
 148                         if visitor2.state == VarState::Warn {
 149                             if let Some(name) = visitor2.name {
 150                                 span_lint(cx, EXPLICIT_COUNTER_LOOP, expr.span,
 151                                           &format!("the variable `{0}` is used as a loop counter. Consider \
 152                                                     using `for ({0}, item) in {1}.enumerate()` \
 153                                                     or similar iterators",
 154                                                    name, snippet(cx, arg.span, "_")));
 155                             }
 156                         }
 157                     }
 158                 }
 159             }
 160         }
 161         // check for `loop { if let {} else break }` that could be `while let`
 162         // (also matches explicit "match" instead of "if let")
 163         if let ExprLoop(ref block, _) = expr.node {
 164             // extract a single expression
 165             if let Some(inner) = extract_single_expr(block) {
 166                 if let ExprMatch(ref matchexpr, ref arms, ref source) = inner.node {
 167                     // ensure "if let" compatible match structure
 168                     match *source {
 169                         MatchSource::Normal | MatchSource::IfLetDesugar{..} => if
 170                             arms.len() == 2 &&
 171                             arms[0].pats.len() == 1 && arms[0].guard.is_none() &&
 172                             arms[1].pats.len() == 1 && arms[1].guard.is_none() &&
 173                             // finally, check for "break" in the second clause
 174                             is_break_expr(&arms[1].body)
 175                         {
 176                             if in_external_macro(cx, expr.span) { return; }
 177                             span_help_and_lint(cx, WHILE_LET_LOOP, expr.span,
 178                                                "this loop could be written as a `while let` loop",
 179                                                &format!("try\nwhile let {} = {} {}",
 180                                                         snippet(cx, arms[0].pats[0].span, ".."),
 181                                                         snippet(cx, matchexpr.span, ".."),
 182                                                         expr_block(cx, &arms[0].body, "..")));
 183                         },
 184                         _ => ()
 185                     }
 186                 }
 187             }
 188         }
 189     }
 190
 191     fn check_stmt(&mut self, cx: &LateContext, stmt: &Stmt) {
 192         if let StmtSemi(ref expr, _) = stmt.node {
 193             if let ExprMethodCall(ref method, _, ref args) = expr.node {
 194                 if args.len() == 1 && method.node.as_str() == "collect" &&
 195                         match_trait_method(cx, expr, &["core", "iter", "Iterator"]) {
 196                     span_lint(cx, UNUSED_COLLECT, expr.span, &format!(
 197                         "you are collect()ing an iterator and throwing away the result. \
 198                          Consider using an explicit for loop to exhaust the iterator"));
 199                 }
 200             }
 201         }
 202     }
 203 }
 204
 205 /// Recover the essential nodes of a desugared for loop:
 206 /// `for pat in arg { body }` becomes `(pat, arg, body)`.
 207 fn recover_for_loop(expr: &Expr) -> Option<(&Pat, &Expr, &Expr)> {
 208     if_let_chain! {
 209         [
 210             let ExprMatch(ref iterexpr, ref arms, _) = expr.node,
 211             let ExprCall(_, ref iterargs) = iterexpr.node,
 212             iterargs.len() == 1 && arms.len() == 1 && arms[0].guard.is_none(),
 213             let ExprLoop(ref block, _) = arms[0].body.node,
 214             block.stmts.is_empty(),
 215             let Some(ref loopexpr) = block.expr,
 216             let ExprMatch(_, ref innerarms, MatchSource::ForLoopDesugar) = loopexpr.node,
 217             innerarms.len() == 2 && innerarms[0].pats.len() == 1,
 218             let PatEnum(_, Some(ref somepats)) = innerarms[0].pats[0].node,
 219             somepats.len() == 1
 220         ], {
 221             return Some((&somepats[0],
 222                          &iterargs[0],
 223                          &innerarms[0].body));
 224         }
 225     }
 226     None
 227 }
 228
 229 struct VarVisitor<'v, 't: 'v> {
 230     cx: &'v LateContext<'v, 't>, // context reference
 231     var: Name,               // var name to look for as index
 232     indexed: HashSet<Name>,  // indexed variables
 233     nonindex: bool,          // has the var been used otherwise?
 234 }
 235
 236 impl<'v, 't> Visitor<'v> for VarVisitor<'v, 't> {
 237     fn visit_expr(&mut self, expr: &'v Expr) {
 238         if let ExprPath(None, ref path) = expr.node {
 239             if path.segments.len() == 1 && path.segments[0].identifier.name == self.var {
 240                 // we are referencing our variable! now check if it's as an index
 241                 if_let_chain! {
 242                     [
 243                         let Some(parexpr) = get_parent_expr(self.cx, expr),
 244                         let ExprIndex(ref seqexpr, _) = parexpr.node,
 245                         let ExprPath(None, ref seqvar) = seqexpr.node,
 246                         seqvar.segments.len() == 1
 247                     ], {
 248                         self.indexed.insert(seqvar.segments[0].identifier.name);
 249                         return;  // no need to walk further
 250                     }
 251                 }
 252                 // we are not indexing anything, record that
 253                 self.nonindex = true;
 254                 return;
 255             }
 256         }
 257         walk_expr(self, expr);
 258     }
 259 }
 260
 261 /// Return true if the type of expr is one that provides IntoIterator impls
 262 /// for &T and &mut T, such as Vec.
 263 fn is_ref_iterable_type(cx: &LateContext, e: &Expr) -> bool {
 264     // no walk_ptrs_ty: calling iter() on a reference can make sense because it
 265     // will allow further borrows afterwards
 266     let ty = cx.tcx.expr_ty(e);
 267     is_iterable_array(ty) ||
 268         match_type(cx, ty, &VEC_PATH) ||
 269         match_type(cx, ty, &LL_PATH) ||
 270         match_type(cx, ty, &["std", "collections", "hash", "map", "HashMap"]) ||
 271         match_type(cx, ty, &["std", "collections", "hash", "set", "HashSet"]) ||
 272         match_type(cx, ty, &["collections", "vec_deque", "VecDeque"]) ||
 273         match_type(cx, ty, &["collections", "binary_heap", "BinaryHeap"]) ||
 274         match_type(cx, ty, &["collections", "btree", "map", "BTreeMap"]) ||
 275         match_type(cx, ty, &["collections", "btree", "set", "BTreeSet"])
 276 }
 277
 278 fn is_iterable_array(ty: ty::Ty) -> bool {
 279     //IntoIterator is currently only implemented for array sizes <= 32 in rustc
 280     match ty.sty {
 281         ty::TyArray(_, 0...32) => true,
 282         _ => false
 283     }
 284 }
 285
 286 /// If block consists of a single expression (with or without semicolon), return it.
 287 fn extract_single_expr(block: &Block) -> Option<&Expr> {
 288     match (&block.stmts.len(), &block.expr) {
 289         (&1, &None) => match block.stmts[0].node {
 290             StmtExpr(ref expr, _) |
 291             StmtSemi(ref expr, _) => Some(expr),
 292             _ => None,
 293         },
 294         (&0, &Some(ref expr)) => Some(expr),
 295         _ => None
 296     }
 297 }
 298
 299 /// Return true if expr contains a single break expr (maybe within a block).
 300 fn is_break_expr(expr: &Expr) -> bool {
 301     match expr.node {
 302         ExprBreak(None) => true,
 303         ExprBlock(ref b) => match extract_single_expr(b) {
 304             Some(ref subexpr) => is_break_expr(subexpr),
 305             None => false,
 306         },
 307         _ => false,
 308     }
 309 }
 310
 311 // To trigger the EXPLICIT_COUNTER_LOOP lint, a variable must be
 312 // incremented exactly once in the loop body, and initialized to zero
 313 // at the start of the loop.
 314 #[derive(PartialEq)]
 315 enum VarState {
 316     Initial,      // Not examined yet
 317     IncrOnce,     // Incremented exactly once, may be a loop counter
 318     Declared,     // Declared but not (yet) initialized to zero
 319     Warn,
 320     DontWarn
 321 }
 322
 323 // Scan a for loop for variables that are incremented exactly once.
 324 struct IncrementVisitor<'v, 't: 'v> {
 325     cx: &'v LateContext<'v, 't>,      // context reference
 326     states: HashMap<NodeId, VarState>,  // incremented variables
 327     depth: u32,                         // depth of conditional expressions
 328     done: bool
 329 }
 330
 331 impl<'v, 't> Visitor<'v> for IncrementVisitor<'v, 't> {
 332     fn visit_expr(&mut self, expr: &'v Expr) {
 333         if self.done {
 334             return;
 335         }
 336
 337         // If node is a variable
 338         if let Some(def_id) = var_def_id(self.cx, expr) {
 339             if let Some(parent) = get_parent_expr(self.cx, expr) {
 340                 let state = self.states.entry(def_id).or_insert(VarState::Initial);
 341
 342                 match parent.node {
 343                     ExprAssignOp(op, ref lhs, ref rhs) =>
 344                         if lhs.id == expr.id {
 345                             if op.node == BiAdd && is_integer_literal(rhs, 1) {
 346                                 *state = match *state {
 347                                     VarState::Initial if self.depth == 0 => VarState::IncrOnce,
 348                                     _ => VarState::DontWarn
 349                                 };
 350                             }
 351                             else {
 352                                 // Assigned some other value
 353                                 *state = VarState::DontWarn;
 354                             }
 355                         },
 356                     ExprAssign(ref lhs, _) if lhs.id == expr.id => *state = VarState::DontWarn,
 357                     ExprAddrOf(mutability,_) if mutability == MutMutable => *state = VarState::DontWarn,
 358                     _ => ()
 359                 }
 360             }
 361         }
 362         // Give up if there are nested loops
 363         else if is_loop(expr) {
 364             self.states.clear();
 365             self.done = true;
 366             return;
 367         }
 368         // Keep track of whether we're inside a conditional expression
 369         else if is_conditional(expr) {
 370             self.depth += 1;
 371             walk_expr(self, expr);
 372             self.depth -= 1;
 373             return;
 374         }
 375         walk_expr(self, expr);
 376     }
 377 }
 378
 379 // Check whether a variable is initialized to zero at the start of a loop.
 380 struct InitializeVisitor<'v, 't: 'v> {
 381     cx: &'v LateContext<'v, 't>, // context reference
 382     end_expr: &'v Expr,      // the for loop. Stop scanning here.
 383     var_id: NodeId,
 384     state: VarState,
 385     name: Option<Name>,
 386     depth: u32,              // depth of conditional expressions
 387     done: bool
 388 }
 389
 390 impl<'v, 't> Visitor<'v> for InitializeVisitor<'v, 't> {
 391     fn visit_decl(&mut self, decl: &'v Decl) {
 392         // Look for declarations of the variable
 393         if let DeclLocal(ref local) = decl.node {
 394             if local.pat.id == self.var_id {
 395                 if let PatIdent(_, ref ident, _) = local.pat.node {
 396                     self.name = Some(ident.node.name);
 397
 398                     self.state = if let Some(ref init) = local.init {
 399                         if is_integer_literal(init, 0) {
 400                             VarState::Warn
 401                         } else {
 402                             VarState::Declared
 403                         }
 404                     }
 405                     else {
 406                         VarState::Declared
 407                     }
 408                 }
 409             }
 410         }
 411         walk_decl(self, decl);
 412     }
 413
 414     fn visit_expr(&mut self, expr: &'v Expr) {
 415         if self.state == VarState::DontWarn || expr == self.end_expr {
 416             self.done = true;
 417         }
 418         // No need to visit expressions before the variable is
 419         // declared or after we've rejected it.
 420         if self.state == VarState::IncrOnce || self.done {
 421             return;
 422         }
 423
 424         // If node is the desired variable, see how it's used
 425         if var_def_id(self.cx, expr) == Some(self.var_id) {
 426             if let Some(parent) = get_parent_expr(self.cx, expr) {
 427                 match parent.node {
 428                     ExprAssignOp(_, ref lhs, _) if lhs.id == expr.id => {
 429                         self.state = VarState::DontWarn;
 430                     },
 431                     ExprAssign(ref lhs, ref rhs) if lhs.id == expr.id => {
 432                         self.state = if is_integer_literal(rhs, 0) && self.depth == 0 {
 433                             VarState::Warn
 434                         } else {
 435                             VarState::DontWarn
 436                         }},
 437                     ExprAddrOf(mutability,_) if mutability == MutMutable => self.state = VarState::DontWarn,
 438                     _ => ()
 439                 }
 440             }
 441         }
 442         // If there are other loops between the declaration and the target loop, give up
 443         else if is_loop(expr) {
 444             self.state = VarState::DontWarn;
 445             self.done = true;
 446             return;
 447         }
 448         // Keep track of whether we're inside a conditional expression
 449         else if is_conditional(expr) {
 450             self.depth += 1;
 451             walk_expr(self, expr);
 452             self.depth -= 1;
 453             return;
 454         }
 455         walk_expr(self, expr);
 456     }
 457 }
 458
 459 fn var_def_id(cx: &LateContext, expr: &Expr) -> Option<NodeId> {
 460     if let Some(path_res) = cx.tcx.def_map.borrow().get(&expr.id) {
 461         if let DefLocal(node_id) = path_res.base_def {
 462             return Some(node_id)
 463         }
 464     }
 465     None
 466 }
 467
 468 fn is_loop(expr: &Expr) -> bool {
 469     match expr.node {
 470         ExprLoop(..) | ExprWhile(..)  => true,
 471         _ => false
 472     }
 473 }
 474
 475 fn is_conditional(expr: &Expr) -> bool {
 476     match expr.node {
 477         ExprIf(..) | ExprMatch(..) => true,
 478         _ => false
 479     }
 480 }