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