clippy_lints/src/loops.rs

   1 use crate::reexport::*;
   2 use if_chain::if_chain;
   3 use itertools::Itertools;
   4 use rustc::hir::def::{DefKind, Res};
   5 use rustc::hir::def_id;
   6 use rustc::hir::intravisit::{walk_block, walk_expr, walk_pat, walk_stmt, NestedVisitorMap, Visitor};
   7 use rustc::hir::*;
   8 use rustc::lint::{in_external_macro, LateContext, LateLintPass, LintArray, LintContext, LintPass};
   9 use rustc::middle::region;
  10 use rustc::{declare_lint_pass, declare_tool_lint};
  11 // use rustc::middle::region::CodeExtent;
  12 use crate::consts::{constant, Constant};
  13 use crate::utils::usage::mutated_variables;
  14 use crate::utils::{is_type_diagnostic_item, qpath_res, sext, sugg};
  15 use rustc::middle::expr_use_visitor::*;
  16 use rustc::middle::mem_categorization::cmt_;
  17 use rustc::middle::mem_categorization::Categorization;
  18 use rustc::ty::subst::Subst;
  19 use rustc::ty::{self, Ty};
  20 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  21 use rustc_errors::Applicability;
  22 use std::iter::{once, Iterator};
  23 use std::mem;
  24 use syntax::ast;
  25 use syntax::source_map::Span;
  26 use syntax_pos::{BytePos, Symbol};
  27
  28 use crate::utils::paths;
  29 use crate::utils::{
  30     get_enclosing_block, get_parent_expr, has_iter_method, higher, is_integer_const, is_refutable, last_path_segment,
  31     match_trait_method, match_type, match_var, multispan_sugg, snippet, snippet_opt, snippet_with_applicability,
  32     span_help_and_lint, span_lint, span_lint_and_sugg, span_lint_and_then, SpanlessEq,
  33 };
  34
  35 declare_clippy_lint! {
  36     /// **What it does:** Checks for for-loops that manually copy items between
  37     /// slices that could be optimized by having a memcpy.
  38     ///
  39     /// **Why is this bad?** It is not as fast as a memcpy.
  40     ///
  41     /// **Known problems:** None.
  42     ///
  43     /// **Example:**
  44     /// ```rust
  45     /// # let src = vec![1];
  46     /// # let mut dst = vec![0; 65];
  47     /// for i in 0..src.len() {
  48     ///     dst[i + 64] = src[i];
  49     /// }
  50     /// ```
  51     /// Could be written as:
  52     /// ```rust
  53     /// # let src = vec![1];
  54     /// # let mut dst = vec![0; 65];
  55     /// dst[64..(src.len() + 64)].clone_from_slice(&src[..]);
  56     /// ```
  57     pub MANUAL_MEMCPY,
  58     perf,
  59     "manually copying items between slices"
  60 }
  61
  62 declare_clippy_lint! {
  63     /// **What it does:** Checks for looping over the range of `0..len` of some
  64     /// collection just to get the values by index.
  65     ///
  66     /// **Why is this bad?** Just iterating the collection itself makes the intent
  67     /// more clear and is probably faster.
  68     ///
  69     /// **Known problems:** None.
  70     ///
  71     /// **Example:**
  72     /// ```rust
  73     /// let vec = vec!['a', 'b', 'c'];
  74     /// for i in 0..vec.len() {
  75     ///     println!("{}", vec[i]);
  76     /// }
  77     /// ```
  78     /// Could be written as:
  79     /// ```rust
  80     /// let vec = vec!['a', 'b', 'c'];
  81     /// for i in vec {
  82     ///     println!("{}", i);
  83     /// }
  84     /// ```
  85     pub NEEDLESS_RANGE_LOOP,
  86     style,
  87     "for-looping over a range of indices where an iterator over items would do"
  88 }
  89
  90 declare_clippy_lint! {
  91     /// **What it does:** Checks for loops on `x.iter()` where `&x` will do, and
  92     /// suggests the latter.
  93     ///
  94     /// **Why is this bad?** Readability.
  95     ///
  96     /// **Known problems:** False negatives. We currently only warn on some known
  97     /// types.
  98     ///
  99     /// **Example:**
 100     /// ```rust
 101     /// // with `y` a `Vec` or slice:
 102     /// # let y = vec![1];
 103     /// for x in y.iter() {
 104     ///     // ..
 105     /// }
 106     /// ```
 107     /// can be rewritten to
 108     /// ```rust
 109     /// # let y = vec![1];
 110     /// for x in &y {
 111     ///     // ..
 112     /// }
 113     /// ```
 114     pub EXPLICIT_ITER_LOOP,
 115     pedantic,
 116     "for-looping over `_.iter()` or `_.iter_mut()` when `&_` or `&mut _` would do"
 117 }
 118
 119 declare_clippy_lint! {
 120     /// **What it does:** Checks for loops on `y.into_iter()` where `y` will do, and
 121     /// suggests the latter.
 122     ///
 123     /// **Why is this bad?** Readability.
 124     ///
 125     /// **Known problems:** None
 126     ///
 127     /// **Example:**
 128     /// ```rust
 129     /// # let y = vec![1];
 130     /// // with `y` a `Vec` or slice:
 131     /// for x in y.into_iter() {
 132     ///     // ..
 133     /// }
 134     /// ```
 135     /// can be rewritten to
 136     /// ```rust
 137     /// # let y = vec![1];
 138     /// for x in y {
 139     ///     // ..
 140     /// }
 141     /// ```
 142     pub EXPLICIT_INTO_ITER_LOOP,
 143     pedantic,
 144     "for-looping over `_.into_iter()` when `_` would do"
 145 }
 146
 147 declare_clippy_lint! {
 148     /// **What it does:** Checks for loops on `x.next()`.
 149     ///
 150     /// **Why is this bad?** `next()` returns either `Some(value)` if there was a
 151     /// value, or `None` otherwise. The insidious thing is that `Option<_>`
 152     /// implements `IntoIterator`, so that possibly one value will be iterated,
 153     /// leading to some hard to find bugs. No one will want to write such code
 154     /// [except to win an Underhanded Rust
 155     /// Contest](https://www.reddit.com/r/rust/comments/3hb0wm/underhanded_rust_contest/cu5yuhr).
 156     ///
 157     /// **Known problems:** None.
 158     ///
 159     /// **Example:**
 160     /// ```ignore
 161     /// for x in y.next() {
 162     ///     ..
 163     /// }
 164     /// ```
 165     pub ITER_NEXT_LOOP,
 166     correctness,
 167     "for-looping over `_.next()` which is probably not intended"
 168 }
 169
 170 declare_clippy_lint! {
 171     /// **What it does:** Checks for `for` loops over `Option` values.
 172     ///
 173     /// **Why is this bad?** Readability. This is more clearly expressed as an `if
 174     /// let`.
 175     ///
 176     /// **Known problems:** None.
 177     ///
 178     /// **Example:**
 179     /// ```ignore
 180     /// for x in option {
 181     ///     ..
 182     /// }
 183     /// ```
 184     ///
 185     /// This should be
 186     /// ```ignore
 187     /// if let Some(x) = option {
 188     ///     ..
 189     /// }
 190     /// ```
 191     pub FOR_LOOP_OVER_OPTION,
 192     correctness,
 193     "for-looping over an `Option`, which is more clearly expressed as an `if let`"
 194 }
 195
 196 declare_clippy_lint! {
 197     /// **What it does:** Checks for `for` loops over `Result` values.
 198     ///
 199     /// **Why is this bad?** Readability. This is more clearly expressed as an `if
 200     /// let`.
 201     ///
 202     /// **Known problems:** None.
 203     ///
 204     /// **Example:**
 205     /// ```ignore
 206     /// for x in result {
 207     ///     ..
 208     /// }
 209     /// ```
 210     ///
 211     /// This should be
 212     /// ```ignore
 213     /// if let Ok(x) = result {
 214     ///     ..
 215     /// }
 216     /// ```
 217     pub FOR_LOOP_OVER_RESULT,
 218     correctness,
 219     "for-looping over a `Result`, which is more clearly expressed as an `if let`"
 220 }
 221
 222 declare_clippy_lint! {
 223     /// **What it does:** Detects `loop + match` combinations that are easier
 224     /// written as a `while let` loop.
 225     ///
 226     /// **Why is this bad?** The `while let` loop is usually shorter and more
 227     /// readable.
 228     ///
 229     /// **Known problems:** Sometimes the wrong binding is displayed (#383).
 230     ///
 231     /// **Example:**
 232     /// ```rust,no_run
 233     /// # let y = Some(1);
 234     /// loop {
 235     ///     let x = match y {
 236     ///         Some(x) => x,
 237     ///         None => break,
 238     ///     };
 239     ///     // .. do something with x
 240     /// }
 241     /// // is easier written as
 242     /// while let Some(x) = y {
 243     ///     // .. do something with x
 244     /// };
 245     /// ```
 246     pub WHILE_LET_LOOP,
 247     complexity,
 248     "`loop { if let { ... } else break }`, which can be written as a `while let` loop"
 249 }
 250
 251 declare_clippy_lint! {
 252     /// **What it does:** Checks for functions collecting an iterator when collect
 253     /// is not needed.
 254     ///
 255     /// **Why is this bad?** `collect` causes the allocation of a new data structure,
 256     /// when this allocation may not be needed.
 257     ///
 258     /// **Known problems:**
 259     /// None
 260     ///
 261     /// **Example:**
 262     /// ```rust
 263     /// # let iterator = vec![1].into_iter();
 264     /// let len = iterator.clone().collect::<Vec<_>>().len();
 265     /// // should be
 266     /// let len = iterator.count();
 267     /// ```
 268     pub NEEDLESS_COLLECT,
 269     perf,
 270     "collecting an iterator when collect is not needed"
 271 }
 272
 273 declare_clippy_lint! {
 274     /// **What it does:** Checks for loops over ranges `x..y` where both `x` and `y`
 275     /// are constant and `x` is greater or equal to `y`, unless the range is
 276     /// reversed or has a negative `.step_by(_)`.
 277     ///
 278     /// **Why is it bad?** Such loops will either be skipped or loop until
 279     /// wrap-around (in debug code, this may `panic!()`). Both options are probably
 280     /// not intended.
 281     ///
 282     /// **Known problems:** The lint cannot catch loops over dynamically defined
 283     /// ranges. Doing this would require simulating all possible inputs and code
 284     /// paths through the program, which would be complex and error-prone.
 285     ///
 286     /// **Example:**
 287     /// ```ignore
 288     /// for x in 5..10 - 5 {
 289     ///     ..
 290     /// } // oops, stray `-`
 291     /// ```
 292     pub REVERSE_RANGE_LOOP,
 293     correctness,
 294     "iteration over an empty range, such as `10..0` or `5..5`"
 295 }
 296
 297 declare_clippy_lint! {
 298     /// **What it does:** Checks `for` loops over slices with an explicit counter
 299     /// and suggests the use of `.enumerate()`.
 300     ///
 301     /// **Why is it bad?** Using `.enumerate()` makes the intent more clear,
 302     /// declutters the code and may be faster in some instances.
 303     ///
 304     /// **Known problems:** None.
 305     ///
 306     /// **Example:**
 307     /// ```rust
 308     /// # let v = vec![1];
 309     /// # fn bar(bar: usize, baz: usize) {}
 310     /// let mut i = 0;
 311     /// for item in &v {
 312     ///     bar(i, *item);
 313     ///     i += 1;
 314     /// }
 315     /// ```
 316     /// Could be written as
 317     /// ```rust
 318     /// # let v = vec![1];
 319     /// # fn bar(bar: usize, baz: usize) {}
 320     /// for (i, item) in v.iter().enumerate() { bar(i, *item); }
 321     /// ```
 322     pub EXPLICIT_COUNTER_LOOP,
 323     complexity,
 324     "for-looping with an explicit counter when `_.enumerate()` would do"
 325 }
 326
 327 declare_clippy_lint! {
 328     /// **What it does:** Checks for empty `loop` expressions.
 329     ///
 330     /// **Why is this bad?** Those busy loops burn CPU cycles without doing
 331     /// anything. Think of the environment and either block on something or at least
 332     /// make the thread sleep for some microseconds.
 333     ///
 334     /// **Known problems:** None.
 335     ///
 336     /// **Example:**
 337     /// ```no_run
 338     /// loop {}
 339     /// ```
 340     pub EMPTY_LOOP,
 341     style,
 342     "empty `loop {}`, which should block or sleep"
 343 }
 344
 345 declare_clippy_lint! {
 346     /// **What it does:** Checks for `while let` expressions on iterators.
 347     ///
 348     /// **Why is this bad?** Readability. A simple `for` loop is shorter and conveys
 349     /// the intent better.
 350     ///
 351     /// **Known problems:** None.
 352     ///
 353     /// **Example:**
 354     /// ```ignore
 355     /// while let Some(val) = iter() {
 356     ///     ..
 357     /// }
 358     /// ```
 359     pub WHILE_LET_ON_ITERATOR,
 360     style,
 361     "using a while-let loop instead of a for loop on an iterator"
 362 }
 363
 364 declare_clippy_lint! {
 365     /// **What it does:** Checks for iterating a map (`HashMap` or `BTreeMap`) and
 366     /// ignoring either the keys or values.
 367     ///
 368     /// **Why is this bad?** Readability. There are `keys` and `values` methods that
 369     /// can be used to express that don't need the values or keys.
 370     ///
 371     /// **Known problems:** None.
 372     ///
 373     /// **Example:**
 374     /// ```ignore
 375     /// for (k, _) in &map {
 376     ///     ..
 377     /// }
 378     /// ```
 379     ///
 380     /// could be replaced by
 381     ///
 382     /// ```ignore
 383     /// for k in map.keys() {
 384     ///     ..
 385     /// }
 386     /// ```
 387     pub FOR_KV_MAP,
 388     style,
 389     "looping on a map using `iter` when `keys` or `values` would do"
 390 }
 391
 392 declare_clippy_lint! {
 393     /// **What it does:** Checks for loops that will always `break`, `return` or
 394     /// `continue` an outer loop.
 395     ///
 396     /// **Why is this bad?** This loop never loops, all it does is obfuscating the
 397     /// code.
 398     ///
 399     /// **Known problems:** None
 400     ///
 401     /// **Example:**
 402     /// ```rust
 403     /// loop {
 404     ///     ..;
 405     ///     break;
 406     /// }
 407     /// ```
 408     pub NEVER_LOOP,
 409     correctness,
 410     "any loop that will always `break` or `return`"
 411 }
 412
 413 declare_clippy_lint! {
 414     /// **What it does:** Checks for loops which have a range bound that is a mutable variable
 415     ///
 416     /// **Why is this bad?** One might think that modifying the mutable variable changes the loop bounds
 417     ///
 418     /// **Known problems:** None
 419     ///
 420     /// **Example:**
 421     /// ```rust
 422     /// let mut foo = 42;
 423     /// for i in 0..foo {
 424     ///     foo -= 1;
 425     ///     println!("{}", i); // prints numbers from 0 to 42, not 0 to 21
 426     /// }
 427     /// ```
 428     pub MUT_RANGE_BOUND,
 429     complexity,
 430     "for loop over a range where one of the bounds is a mutable variable"
 431 }
 432
 433 declare_clippy_lint! {
 434     /// **What it does:** Checks whether variables used within while loop condition
 435     /// can be (and are) mutated in the body.
 436     ///
 437     /// **Why is this bad?** If the condition is unchanged, entering the body of the loop
 438     /// will lead to an infinite loop.
 439     ///
 440     /// **Known problems:** If the `while`-loop is in a closure, the check for mutation of the
 441     /// condition variables in the body can cause false negatives. For example when only `Upvar` `a` is
 442     /// in the condition and only `Upvar` `b` gets mutated in the body, the lint will not trigger.
 443     ///
 444     /// **Example:**
 445     /// ```rust
 446     /// let i = 0;
 447     /// while i > 10 {
 448     ///     println!("let me loop forever!");
 449     /// }
 450     /// ```
 451     pub WHILE_IMMUTABLE_CONDITION,
 452     correctness,
 453     "variables used within while expression are not mutated in the body"
 454 }
 455
 456 declare_lint_pass!(Loops => [
 457     MANUAL_MEMCPY,
 458     NEEDLESS_RANGE_LOOP,
 459     EXPLICIT_ITER_LOOP,
 460     EXPLICIT_INTO_ITER_LOOP,
 461     ITER_NEXT_LOOP,
 462     FOR_LOOP_OVER_RESULT,
 463     FOR_LOOP_OVER_OPTION,
 464     WHILE_LET_LOOP,
 465     NEEDLESS_COLLECT,
 466     REVERSE_RANGE_LOOP,
 467     EXPLICIT_COUNTER_LOOP,
 468     EMPTY_LOOP,
 469     WHILE_LET_ON_ITERATOR,
 470     FOR_KV_MAP,
 471     NEVER_LOOP,
 472     MUT_RANGE_BOUND,
 473     WHILE_IMMUTABLE_CONDITION,
 474 ]);
 475
 476 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Loops {
 477     #[allow(clippy::too_many_lines)]
 478     fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
 479         // we don't want to check expanded macros
 480         if expr.span.from_expansion() {
 481             return;
 482         }
 483
 484         if let Some((pat, arg, body)) = higher::for_loop(expr) {
 485             check_for_loop(cx, pat, arg, body, expr);
 486         }
 487
 488         // check for never_loop
 489         if let ExprKind::Loop(ref block, _, _) = expr.node {
 490             match never_loop_block(block, expr.hir_id) {
 491                 NeverLoopResult::AlwaysBreak => span_lint(cx, NEVER_LOOP, expr.span, "this loop never actually loops"),
 492                 NeverLoopResult::MayContinueMainLoop | NeverLoopResult::Otherwise => (),
 493             }
 494         }
 495
 496         // check for `loop { if let {} else break }` that could be `while let`
 497         // (also matches an explicit "match" instead of "if let")
 498         // (even if the "match" or "if let" is used for declaration)
 499         if let ExprKind::Loop(ref block, _, LoopSource::Loop) = expr.node {
 500             // also check for empty `loop {}` statements
 501             if block.stmts.is_empty() && block.expr.is_none() {
 502                 span_lint(
 503                     cx,
 504                     EMPTY_LOOP,
 505                     expr.span,
 506                     "empty `loop {}` detected. You may want to either use `panic!()` or add \
 507                      `std::thread::sleep(..);` to the loop body.",
 508                 );
 509             }
 510
 511             // extract the expression from the first statement (if any) in a block
 512             let inner_stmt_expr = extract_expr_from_first_stmt(block);
 513             // or extract the first expression (if any) from the block
 514             if let Some(inner) = inner_stmt_expr.or_else(|| extract_first_expr(block)) {
 515                 if let ExprKind::Match(ref matchexpr, ref arms, ref source) = inner.node {
 516                     // ensure "if let" compatible match structure
 517                     match *source {
 518                         MatchSource::Normal | MatchSource::IfLetDesugar { .. } => {
 519                             if arms.len() == 2
 520                                 && arms[0].pats.len() == 1
 521                                 && arms[0].guard.is_none()
 522                                 && arms[1].pats.len() == 1
 523                                 && arms[1].guard.is_none()
 524                                 && is_simple_break_expr(&arms[1].body)
 525                             {
 526                                 if in_external_macro(cx.sess(), expr.span) {
 527                                     return;
 528                                 }
 529
 530                                 // NOTE: we used to build a body here instead of using
 531                                 // ellipsis, this was removed because:
 532                                 // 1) it was ugly with big bodies;
 533                                 // 2) it was not indented properly;
 534                                 // 3) it wasn’t very smart (see #675).
 535                                 let mut applicability = Applicability::HasPlaceholders;
 536                                 span_lint_and_sugg(
 537                                     cx,
 538                                     WHILE_LET_LOOP,
 539                                     expr.span,
 540                                     "this loop could be written as a `while let` loop",
 541                                     "try",
 542                                     format!(
 543                                         "while let {} = {} {{ .. }}",
 544                                         snippet_with_applicability(cx, arms[0].pats[0].span, "..", &mut applicability),
 545                                         snippet_with_applicability(cx, matchexpr.span, "..", &mut applicability),
 546                                     ),
 547                                     applicability,
 548                                 );
 549                             }
 550                         },
 551                         _ => (),
 552                     }
 553                 }
 554             }
 555         }
 556         if let ExprKind::Match(ref match_expr, ref arms, MatchSource::WhileLetDesugar) = expr.node {
 557             let pat = &arms[0].pats[0].node;
 558             if let (
 559                 &PatKind::TupleStruct(ref qpath, ref pat_args, _),
 560                 &ExprKind::MethodCall(ref method_path, _, ref method_args),
 561             ) = (pat, &match_expr.node)
 562             {
 563                 let iter_expr = &method_args[0];
 564                 let lhs_constructor = last_path_segment(qpath);
 565                 if method_path.ident.name == sym!(next)
 566                     && match_trait_method(cx, match_expr, &paths::ITERATOR)
 567                     && lhs_constructor.ident.name == sym!(Some)
 568                     && (pat_args.is_empty()
 569                         || !is_refutable(cx, &pat_args[0])
 570                             && !is_used_inside(cx, iter_expr, &arms[0].body)
 571                             && !is_iterator_used_after_while_let(cx, iter_expr)
 572                             && !is_nested(cx, expr, &method_args[0]))
 573                 {
 574                     let iterator = snippet(cx, method_args[0].span, "_");
 575                     let loop_var = if pat_args.is_empty() {
 576                         "_".to_string()
 577                     } else {
 578                         snippet(cx, pat_args[0].span, "_").into_owned()
 579                     };
 580                     span_lint_and_sugg(
 581                         cx,
 582                         WHILE_LET_ON_ITERATOR,
 583                         expr.span,
 584                         "this loop could be written as a `for` loop",
 585                         "try",
 586                         format!("for {} in {} {{ .. }}", loop_var, iterator),
 587                         Applicability::HasPlaceholders,
 588                     );
 589                 }
 590             }
 591         }
 592
 593         if let Some((cond, body)) = higher::while_loop(&expr) {
 594             check_infinite_loop(cx, cond, body);
 595         }
 596
 597         check_needless_collect(expr, cx);
 598     }
 599 }
 600
 601 enum NeverLoopResult {
 602     // A break/return always get triggered but not necessarily for the main loop.
 603     AlwaysBreak,
 604     // A continue may occur for the main loop.
 605     MayContinueMainLoop,
 606     Otherwise,
 607 }
 608
 609 fn absorb_break(arg: &NeverLoopResult) -> NeverLoopResult {
 610     match *arg {
 611         NeverLoopResult::AlwaysBreak | NeverLoopResult::Otherwise => NeverLoopResult::Otherwise,
 612         NeverLoopResult::MayContinueMainLoop => NeverLoopResult::MayContinueMainLoop,
 613     }
 614 }
 615
 616 // Combine two results for parts that are called in order.
 617 fn combine_seq(first: NeverLoopResult, second: NeverLoopResult) -> NeverLoopResult {
 618     match first {
 619         NeverLoopResult::AlwaysBreak | NeverLoopResult::MayContinueMainLoop => first,
 620         NeverLoopResult::Otherwise => second,
 621     }
 622 }
 623
 624 // Combine two results where both parts are called but not necessarily in order.
 625 fn combine_both(left: NeverLoopResult, right: NeverLoopResult) -> NeverLoopResult {
 626     match (left, right) {
 627         (NeverLoopResult::MayContinueMainLoop, _) | (_, NeverLoopResult::MayContinueMainLoop) => {
 628             NeverLoopResult::MayContinueMainLoop
 629         },
 630         (NeverLoopResult::AlwaysBreak, _) | (_, NeverLoopResult::AlwaysBreak) => NeverLoopResult::AlwaysBreak,
 631         (NeverLoopResult::Otherwise, NeverLoopResult::Otherwise) => NeverLoopResult::Otherwise,
 632     }
 633 }
 634
 635 // Combine two results where only one of the part may have been executed.
 636 fn combine_branches(b1: NeverLoopResult, b2: NeverLoopResult) -> NeverLoopResult {
 637     match (b1, b2) {
 638         (NeverLoopResult::AlwaysBreak, NeverLoopResult::AlwaysBreak) => NeverLoopResult::AlwaysBreak,
 639         (NeverLoopResult::MayContinueMainLoop, _) | (_, NeverLoopResult::MayContinueMainLoop) => {
 640             NeverLoopResult::MayContinueMainLoop
 641         },
 642         (NeverLoopResult::Otherwise, _) | (_, NeverLoopResult::Otherwise) => NeverLoopResult::Otherwise,
 643     }
 644 }
 645
 646 fn never_loop_block(block: &Block, main_loop_id: HirId) -> NeverLoopResult {
 647     let stmts = block.stmts.iter().map(stmt_to_expr);
 648     let expr = once(block.expr.as_ref().map(|p| &**p));
 649     let mut iter = stmts.chain(expr).filter_map(|e| e);
 650     never_loop_expr_seq(&mut iter, main_loop_id)
 651 }
 652
 653 fn stmt_to_expr(stmt: &Stmt) -> Option<&Expr> {
 654     match stmt.node {
 655         StmtKind::Semi(ref e, ..) | StmtKind::Expr(ref e, ..) => Some(e),
 656         StmtKind::Local(ref local) => local.init.as_ref().map(|p| &**p),
 657         _ => None,
 658     }
 659 }
 660
 661 fn never_loop_expr(expr: &Expr, main_loop_id: HirId) -> NeverLoopResult {
 662     match expr.node {
 663         ExprKind::Box(ref e)
 664         | ExprKind::Unary(_, ref e)
 665         | ExprKind::Cast(ref e, _)
 666         | ExprKind::Type(ref e, _)
 667         | ExprKind::Field(ref e, _)
 668         | ExprKind::AddrOf(_, ref e)
 669         | ExprKind::Struct(_, _, Some(ref e))
 670         | ExprKind::Repeat(ref e, _)
 671         | ExprKind::DropTemps(ref e) => never_loop_expr(e, main_loop_id),
 672         ExprKind::Array(ref es) | ExprKind::MethodCall(_, _, ref es) | ExprKind::Tup(ref es) => {
 673             never_loop_expr_all(&mut es.iter(), main_loop_id)
 674         },
 675         ExprKind::Call(ref e, ref es) => never_loop_expr_all(&mut once(&**e).chain(es.iter()), main_loop_id),
 676         ExprKind::Binary(_, ref e1, ref e2)
 677         | ExprKind::Assign(ref e1, ref e2)
 678         | ExprKind::AssignOp(_, ref e1, ref e2)
 679         | ExprKind::Index(ref e1, ref e2) => never_loop_expr_all(&mut [&**e1, &**e2].iter().cloned(), main_loop_id),
 680         ExprKind::Loop(ref b, _, _) => {
 681             // Break can come from the inner loop so remove them.
 682             absorb_break(&never_loop_block(b, main_loop_id))
 683         },
 684         ExprKind::Match(ref e, ref arms, _) => {
 685             let e = never_loop_expr(e, main_loop_id);
 686             if arms.is_empty() {
 687                 e
 688             } else {
 689                 let arms = never_loop_expr_branch(&mut arms.iter().map(|a| &*a.body), main_loop_id);
 690                 combine_seq(e, arms)
 691             }
 692         },
 693         ExprKind::Block(ref b, _) => never_loop_block(b, main_loop_id),
 694         ExprKind::Continue(d) => {
 695             let id = d
 696                 .target_id
 697                 .expect("target ID can only be missing in the presence of compilation errors");
 698             if id == main_loop_id {
 699                 NeverLoopResult::MayContinueMainLoop
 700             } else {
 701                 NeverLoopResult::AlwaysBreak
 702             }
 703         },
 704         ExprKind::Break(_, ref e) | ExprKind::Ret(ref e) => {
 705             if let Some(ref e) = *e {
 706                 combine_seq(never_loop_expr(e, main_loop_id), NeverLoopResult::AlwaysBreak)
 707             } else {
 708                 NeverLoopResult::AlwaysBreak
 709             }
 710         },
 711         ExprKind::Struct(_, _, None)
 712         | ExprKind::Yield(_, _)
 713         | ExprKind::Closure(_, _, _, _, _)
 714         | ExprKind::InlineAsm(_, _, _)
 715         | ExprKind::Path(_)
 716         | ExprKind::Lit(_)
 717         | ExprKind::Err => NeverLoopResult::Otherwise,
 718     }
 719 }
 720
 721 fn never_loop_expr_seq<'a, T: Iterator<Item = &'a Expr>>(es: &mut T, main_loop_id: HirId) -> NeverLoopResult {
 722     es.map(|e| never_loop_expr(e, main_loop_id))
 723         .fold(NeverLoopResult::Otherwise, combine_seq)
 724 }
 725
 726 fn never_loop_expr_all<'a, T: Iterator<Item = &'a Expr>>(es: &mut T, main_loop_id: HirId) -> NeverLoopResult {
 727     es.map(|e| never_loop_expr(e, main_loop_id))
 728         .fold(NeverLoopResult::Otherwise, combine_both)
 729 }
 730
 731 fn never_loop_expr_branch<'a, T: Iterator<Item = &'a Expr>>(e: &mut T, main_loop_id: HirId) -> NeverLoopResult {
 732     e.map(|e| never_loop_expr(e, main_loop_id))
 733         .fold(NeverLoopResult::AlwaysBreak, combine_branches)
 734 }
 735
 736 fn check_for_loop<'a, 'tcx>(
 737     cx: &LateContext<'a, 'tcx>,
 738     pat: &'tcx Pat,
 739     arg: &'tcx Expr,
 740     body: &'tcx Expr,
 741     expr: &'tcx Expr,
 742 ) {
 743     check_for_loop_range(cx, pat, arg, body, expr);
 744     check_for_loop_reverse_range(cx, arg, expr);
 745     check_for_loop_arg(cx, pat, arg, expr);
 746     check_for_loop_explicit_counter(cx, pat, arg, body, expr);
 747     check_for_loop_over_map_kv(cx, pat, arg, body, expr);
 748     check_for_mut_range_bound(cx, arg, body);
 749     detect_manual_memcpy(cx, pat, arg, body, expr);
 750 }
 751
 752 fn same_var<'a, 'tcx>(cx: &LateContext<'a, 'tcx>, expr: &Expr, var: HirId) -> bool {
 753     if_chain! {
 754         if let ExprKind::Path(ref qpath) = expr.node;
 755         if let QPath::Resolved(None, ref path) = *qpath;
 756         if path.segments.len() == 1;
 757         if let Res::Local(local_id) = qpath_res(cx, qpath, expr.hir_id);
 758         // our variable!
 759         if local_id == var;
 760         then {
 761             return true;
 762         }
 763     }
 764
 765     false
 766 }
 767
 768 struct Offset {
 769     value: String,
 770     negate: bool,
 771 }
 772
 773 impl Offset {
 774     fn negative(s: String) -> Self {
 775         Self { value: s, negate: true }
 776     }
 777
 778     fn positive(s: String) -> Self {
 779         Self {
 780             value: s,
 781             negate: false,
 782         }
 783     }
 784 }
 785
 786 struct FixedOffsetVar {
 787     var_name: String,
 788     offset: Offset,
 789 }
 790
 791 fn is_slice_like<'a, 'tcx>(cx: &LateContext<'a, 'tcx>, ty: Ty<'_>) -> bool {
 792     let is_slice = match ty.sty {
 793         ty::Ref(_, subty, _) => is_slice_like(cx, subty),
 794         ty::Slice(..) | ty::Array(..) => true,
 795         _ => false,
 796     };
 797
 798     is_slice || is_type_diagnostic_item(cx, ty, Symbol::intern("vec_type")) || match_type(cx, ty, &paths::VEC_DEQUE)
 799 }
 800
 801 fn get_fixed_offset_var<'a, 'tcx>(cx: &LateContext<'a, 'tcx>, expr: &Expr, var: HirId) -> Option<FixedOffsetVar> {
 802     fn extract_offset<'a, 'tcx>(cx: &LateContext<'a, 'tcx>, e: &Expr, var: HirId) -> Option<String> {
 803         match e.node {
 804             ExprKind::Lit(ref l) => match l.node {
 805                 ast::LitKind::Int(x, _ty) => Some(x.to_string()),
 806                 _ => None,
 807             },
 808             ExprKind::Path(..) if !same_var(cx, e, var) => Some(snippet_opt(cx, e.span).unwrap_or_else(|| "??".into())),
 809             _ => None,
 810         }
 811     }
 812
 813     if let ExprKind::Index(ref seqexpr, ref idx) = expr.node {
 814         let ty = cx.tables.expr_ty(seqexpr);
 815         if !is_slice_like(cx, ty) {
 816             return None;
 817         }
 818
 819         let offset = match idx.node {
 820             ExprKind::Binary(op, ref lhs, ref rhs) => match op.node {
 821                 BinOpKind::Add => {
 822                     let offset_opt = if same_var(cx, lhs, var) {
 823                         extract_offset(cx, rhs, var)
 824                     } else if same_var(cx, rhs, var) {
 825                         extract_offset(cx, lhs, var)
 826                     } else {
 827                         None
 828                     };
 829
 830                     offset_opt.map(Offset::positive)
 831                 },
 832                 BinOpKind::Sub if same_var(cx, lhs, var) => extract_offset(cx, rhs, var).map(Offset::negative),
 833                 _ => None,
 834             },
 835             ExprKind::Path(..) => {
 836                 if same_var(cx, idx, var) {
 837                     Some(Offset::positive("0".into()))
 838                 } else {
 839                     None
 840                 }
 841             },
 842             _ => None,
 843         };
 844
 845         offset.map(|o| FixedOffsetVar {
 846             var_name: snippet_opt(cx, seqexpr.span).unwrap_or_else(|| "???".into()),
 847             offset: o,
 848         })
 849     } else {
 850         None
 851     }
 852 }
 853
 854 fn fetch_cloned_fixed_offset_var<'a, 'tcx>(
 855     cx: &LateContext<'a, 'tcx>,
 856     expr: &Expr,
 857     var: HirId,
 858 ) -> Option<FixedOffsetVar> {
 859     if_chain! {
 860         if let ExprKind::MethodCall(ref method, _, ref args) = expr.node;
 861         if method.ident.name == sym!(clone);
 862         if args.len() == 1;
 863         if let Some(arg) = args.get(0);
 864         then {
 865             return get_fixed_offset_var(cx, arg, var);
 866         }
 867     }
 868
 869     get_fixed_offset_var(cx, expr, var)
 870 }
 871
 872 fn get_indexed_assignments<'a, 'tcx>(
 873     cx: &LateContext<'a, 'tcx>,
 874     body: &Expr,
 875     var: HirId,
 876 ) -> Vec<(FixedOffsetVar, FixedOffsetVar)> {
 877     fn get_assignment<'a, 'tcx>(
 878         cx: &LateContext<'a, 'tcx>,
 879         e: &Expr,
 880         var: HirId,
 881     ) -> Option<(FixedOffsetVar, FixedOffsetVar)> {
 882         if let ExprKind::Assign(ref lhs, ref rhs) = e.node {
 883             match (
 884                 get_fixed_offset_var(cx, lhs, var),
 885                 fetch_cloned_fixed_offset_var(cx, rhs, var),
 886             ) {
 887                 (Some(offset_left), Some(offset_right)) => {
 888                     // Source and destination must be different
 889                     if offset_left.var_name == offset_right.var_name {
 890                         None
 891                     } else {
 892                         Some((offset_left, offset_right))
 893                     }
 894                 },
 895                 _ => None,
 896             }
 897         } else {
 898             None
 899         }
 900     }
 901
 902     if let ExprKind::Block(ref b, _) = body.node {
 903         let Block {
 904             ref stmts, ref expr, ..
 905         } = **b;
 906
 907         stmts
 908             .iter()
 909             .map(|stmt| match stmt.node {
 910                 StmtKind::Local(..) | StmtKind::Item(..) => None,
 911                 StmtKind::Expr(ref e) | StmtKind::Semi(ref e) => Some(get_assignment(cx, e, var)),
 912             })
 913             .chain(expr.as_ref().into_iter().map(|e| Some(get_assignment(cx, &*e, var))))
 914             .filter_map(|op| op)
 915             .collect::<Option<Vec<_>>>()
 916             .unwrap_or_else(|| vec![])
 917     } else {
 918         get_assignment(cx, body, var).into_iter().collect()
 919     }
 920 }
 921
 922 /// Checks for for loops that sequentially copy items from one slice-like
 923 /// object to another.
 924 fn detect_manual_memcpy<'a, 'tcx>(
 925     cx: &LateContext<'a, 'tcx>,
 926     pat: &'tcx Pat,
 927     arg: &'tcx Expr,
 928     body: &'tcx Expr,
 929     expr: &'tcx Expr,
 930 ) {
 931     if let Some(higher::Range {
 932         start: Some(start),
 933         ref end,
 934         limits,
 935     }) = higher::range(cx, arg)
 936     {
 937         // the var must be a single name
 938         if let PatKind::Binding(_, canonical_id, _, _) = pat.node {
 939             let print_sum = |arg1: &Offset, arg2: &Offset| -> String {
 940                 match (&arg1.value[..], arg1.negate, &arg2.value[..], arg2.negate) {
 941                     ("0", _, "0", _) => "".into(),
 942                     ("0", _, x, false) | (x, false, "0", false) => x.into(),
 943                     ("0", _, x, true) | (x, false, "0", true) => format!("-{}", x),
 944                     (x, false, y, false) => format!("({} + {})", x, y),
 945                     (x, false, y, true) => {
 946                         if x == y {
 947                             "0".into()
 948                         } else {
 949                             format!("({} - {})", x, y)
 950                         }
 951                     },
 952                     (x, true, y, false) => {
 953                         if x == y {
 954                             "0".into()
 955                         } else {
 956                             format!("({} - {})", y, x)
 957                         }
 958                     },
 959                     (x, true, y, true) => format!("-({} + {})", x, y),
 960                 }
 961             };
 962
 963             let print_limit = |end: &Option<&Expr>, offset: Offset, var_name: &str| {
 964                 if let Some(end) = *end {
 965                     if_chain! {
 966                         if let ExprKind::MethodCall(ref method, _, ref len_args) = end.node;
 967                         if method.ident.name == sym!(len);
 968                         if len_args.len() == 1;
 969                         if let Some(arg) = len_args.get(0);
 970                         if snippet(cx, arg.span, "??") == var_name;
 971                         then {
 972                             return if offset.negate {
 973                                 format!("({} - {})", snippet(cx, end.span, "<src>.len()"), offset.value)
 974                             } else {
 975                                 String::new()
 976                             };
 977                         }
 978                     }
 979
 980                     let end_str = match limits {
 981                         ast::RangeLimits::Closed => {
 982                             let end = sugg::Sugg::hir(cx, end, "<count>");
 983                             format!("{}", end + sugg::ONE)
 984                         },
 985                         ast::RangeLimits::HalfOpen => format!("{}", snippet(cx, end.span, "..")),
 986                     };
 987
 988                     print_sum(&Offset::positive(end_str), &offset)
 989                 } else {
 990                     "..".into()
 991                 }
 992             };
 993
 994             // The only statements in the for loops can be indexed assignments from
 995             // indexed retrievals.
 996             let manual_copies = get_indexed_assignments(cx, body, canonical_id);
 997
 998             let big_sugg = manual_copies
 999                 .into_iter()
1000                 .map(|(dst_var, src_var)| {
1001                     let start_str = Offset::positive(snippet(cx, start.span, "").to_string());
1002                     let dst_offset = print_sum(&start_str, &dst_var.offset);
1003                     let dst_limit = print_limit(end, dst_var.offset, &dst_var.var_name);
1004                     let src_offset = print_sum(&start_str, &src_var.offset);
1005                     let src_limit = print_limit(end, src_var.offset, &src_var.var_name);
1006                     let dst = if dst_offset == "" && dst_limit == "" {
1007                         dst_var.var_name
1008                     } else {
1009                         format!("{}[{}..{}]", dst_var.var_name, dst_offset, dst_limit)
1010                     };
1011
1012                     format!(
1013                         "{}.clone_from_slice(&{}[{}..{}])",
1014                         dst, src_var.var_name, src_offset, src_limit
1015                     )
1016                 })
1017                 .join("\n    ");
1018
1019             if !big_sugg.is_empty() {
1020                 span_lint_and_sugg(
1021                     cx,
1022                     MANUAL_MEMCPY,
1023                     expr.span,
1024                     "it looks like you're manually copying between slices",
1025                     "try replacing the loop by",
1026                     big_sugg,
1027                     Applicability::Unspecified,
1028                 );
1029             }
1030         }
1031     }
1032 }
1033
1034 /// Checks for looping over a range and then indexing a sequence with it.
1035 /// The iteratee must be a range literal.
1036 #[allow(clippy::too_many_lines)]
1037 fn check_for_loop_range<'a, 'tcx>(
1038     cx: &LateContext<'a, 'tcx>,
1039     pat: &'tcx Pat,
1040     arg: &'tcx Expr,
1041     body: &'tcx Expr,
1042     expr: &'tcx Expr,
1043 ) {
1044     if expr.span.from_expansion() {
1045         return;
1046     }
1047
1048     if let Some(higher::Range {
1049         start: Some(start),
1050         ref end,
1051         limits,
1052     }) = higher::range(cx, arg)
1053     {
1054         // the var must be a single name
1055         if let PatKind::Binding(_, canonical_id, ident, _) = pat.node {
1056             let mut visitor = VarVisitor {
1057                 cx,
1058                 var: canonical_id,
1059                 indexed_mut: FxHashSet::default(),
1060                 indexed_indirectly: FxHashMap::default(),
1061                 indexed_directly: FxHashMap::default(),
1062                 referenced: FxHashSet::default(),
1063                 nonindex: false,
1064                 prefer_mutable: false,
1065             };
1066             walk_expr(&mut visitor, body);
1067
1068             // linting condition: we only indexed one variable, and indexed it directly
1069             if visitor.indexed_indirectly.is_empty() && visitor.indexed_directly.len() == 1 {
1070                 let (indexed, (indexed_extent, indexed_ty)) = visitor
1071                     .indexed_directly
1072                     .into_iter()
1073                     .next()
1074                     .expect("already checked that we have exactly 1 element");
1075
1076                 // ensure that the indexed variable was declared before the loop, see #601
1077                 if let Some(indexed_extent) = indexed_extent {
1078                     let parent_id = cx.tcx.hir().get_parent_item(expr.hir_id);
1079                     let parent_def_id = cx.tcx.hir().local_def_id(parent_id);
1080                     let region_scope_tree = cx.tcx.region_scope_tree(parent_def_id);
1081                     let pat_extent = region_scope_tree.var_scope(pat.hir_id.local_id);
1082                     if region_scope_tree.is_subscope_of(indexed_extent, pat_extent) {
1083                         return;
1084                     }
1085                 }
1086
1087                 // don't lint if the container that is indexed does not have .iter() method
1088                 let has_iter = has_iter_method(cx, indexed_ty);
1089                 if has_iter.is_none() {
1090                     return;
1091                 }
1092
1093                 // don't lint if the container that is indexed into is also used without
1094                 // indexing
1095                 if visitor.referenced.contains(&indexed) {
1096                     return;
1097                 }
1098
1099                 let starts_at_zero = is_integer_const(cx, start, 0);
1100
1101                 let skip = if starts_at_zero {
1102                     String::new()
1103                 } else {
1104                     format!(".skip({})", snippet(cx, start.span, ".."))
1105                 };
1106
1107                 let mut end_is_start_plus_val = false;
1108
1109                 let take = if let Some(end) = *end {
1110                     let mut take_expr = end;
1111
1112                     if let ExprKind::Binary(ref op, ref left, ref right) = end.node {
1113                         if let BinOpKind::Add = op.node {
1114                             let start_equal_left = SpanlessEq::new(cx).eq_expr(start, left);
1115                             let start_equal_right = SpanlessEq::new(cx).eq_expr(start, right);
1116
1117                             if start_equal_left {
1118                                 take_expr = right;
1119                             } else if start_equal_right {
1120                                 take_expr = left;
1121                             }
1122
1123                             end_is_start_plus_val = start_equal_left | start_equal_right;
1124                         }
1125                     }
1126
1127                     if is_len_call(end, indexed) || is_end_eq_array_len(cx, end, limits, indexed_ty) {
1128                         String::new()
1129                     } else {
1130                         match limits {
1131                             ast::RangeLimits::Closed => {
1132                                 let take_expr = sugg::Sugg::hir(cx, take_expr, "<count>");
1133                                 format!(".take({})", take_expr + sugg::ONE)
1134                             },
1135                             ast::RangeLimits::HalfOpen => format!(".take({})", snippet(cx, take_expr.span, "..")),
1136                         }
1137                     }
1138                 } else {
1139                     String::new()
1140                 };
1141
1142                 let (ref_mut, method) = if visitor.indexed_mut.contains(&indexed) {
1143                     ("mut ", "iter_mut")
1144                 } else {
1145                     ("", "iter")
1146                 };
1147
1148                 let take_is_empty = take.is_empty();
1149                 let mut method_1 = take;
1150                 let mut method_2 = skip;
1151
1152                 if end_is_start_plus_val {
1153                     mem::swap(&mut method_1, &mut method_2);
1154                 }
1155
1156                 if visitor.nonindex {
1157                     span_lint_and_then(
1158                         cx,
1159                         NEEDLESS_RANGE_LOOP,
1160                         expr.span,
1161                         &format!("the loop variable `{}` is used to index `{}`", ident.name, indexed),
1162                         |db| {
1163                             multispan_sugg(
1164                                 db,
1165                                 "consider using an iterator".to_string(),
1166                                 vec![
1167                                     (pat.span, format!("({}, <item>)", ident.name)),
1168                                     (
1169                                         arg.span,
1170                                         format!("{}.{}().enumerate(){}{}", indexed, method, method_1, method_2),
1171                                     ),
1172                                 ],
1173                             );
1174                         },
1175                     );
1176                 } else {
1177                     let repl = if starts_at_zero && take_is_empty {
1178                         format!("&{}{}", ref_mut, indexed)
1179                     } else {
1180                         format!("{}.{}(){}{}", indexed, method, method_1, method_2)
1181                     };
1182
1183                     span_lint_and_then(
1184                         cx,
1185                         NEEDLESS_RANGE_LOOP,
1186                         expr.span,
1187                         &format!(
1188                             "the loop variable `{}` is only used to index `{}`.",
1189                             ident.name, indexed
1190                         ),
1191                         |db| {
1192                             multispan_sugg(
1193                                 db,
1194                                 "consider using an iterator".to_string(),
1195                                 vec![(pat.span, "<item>".to_string()), (arg.span, repl)],
1196                             );
1197                         },
1198                     );
1199                 }
1200             }
1201         }
1202     }
1203 }
1204
1205 fn is_len_call(expr: &Expr, var: Name) -> bool {
1206     if_chain! {
1207         if let ExprKind::MethodCall(ref method, _, ref len_args) = expr.node;
1208         if len_args.len() == 1;
1209         if method.ident.name == sym!(len);
1210         if let ExprKind::Path(QPath::Resolved(_, ref path)) = len_args[0].node;
1211         if path.segments.len() == 1;
1212         if path.segments[0].ident.name == var;
1213         then {
1214             return true;
1215         }
1216     }
1217
1218     false
1219 }
1220
1221 fn is_end_eq_array_len<'tcx>(
1222     cx: &LateContext<'_, 'tcx>,
1223     end: &Expr,
1224     limits: ast::RangeLimits,
1225     indexed_ty: Ty<'tcx>,
1226 ) -> bool {
1227     if_chain! {
1228         if let ExprKind::Lit(ref lit) = end.node;
1229         if let ast::LitKind::Int(end_int, _) = lit.node;
1230         if let ty::Array(_, arr_len_const) = indexed_ty.sty;
1231         if let Some(arr_len) = arr_len_const.try_eval_usize(cx.tcx, cx.param_env);
1232         then {
1233             return match limits {
1234                 ast::RangeLimits::Closed => end_int + 1 >= arr_len.into(),
1235                 ast::RangeLimits::HalfOpen => end_int >= arr_len.into(),
1236             };
1237         }
1238     }
1239
1240     false
1241 }
1242
1243 fn check_for_loop_reverse_range<'a, 'tcx>(cx: &LateContext<'a, 'tcx>, arg: &'tcx Expr, expr: &'tcx Expr) {
1244     // if this for loop is iterating over a two-sided range...
1245     if let Some(higher::Range {
1246         start: Some(start),
1247         end: Some(end),
1248         limits,
1249     }) = higher::range(cx, arg)
1250     {
1251         // ...and both sides are compile-time constant integers...
1252         if let Some((start_idx, _)) = constant(cx, cx.tables, start) {
1253             if let Some((end_idx, _)) = constant(cx, cx.tables, end) {
1254                 // ...and the start index is greater than the end index,
1255                 // this loop will never run. This is often confusing for developers
1256                 // who think that this will iterate from the larger value to the
1257                 // smaller value.
1258                 let ty = cx.tables.expr_ty(start);
1259                 let (sup, eq) = match (start_idx, end_idx) {
1260                     (Constant::Int(start_idx), Constant::Int(end_idx)) => (
1261                         match ty.sty {
1262                             ty::Int(ity) => sext(cx.tcx, start_idx, ity) > sext(cx.tcx, end_idx, ity),
1263                             ty::Uint(_) => start_idx > end_idx,
1264                             _ => false,
1265                         },
1266                         start_idx == end_idx,
1267                     ),
1268                     _ => (false, false),
1269                 };
1270
1271                 if sup {
1272                     let start_snippet = snippet(cx, start.span, "_");
1273                     let end_snippet = snippet(cx, end.span, "_");
1274                     let dots = if limits == ast::RangeLimits::Closed {
1275                         "..."
1276                     } else {
1277                         ".."
1278                     };
1279
1280                     span_lint_and_then(
1281                         cx,
1282                         REVERSE_RANGE_LOOP,
1283                         expr.span,
1284                         "this range is empty so this for loop will never run",
1285                         |db| {
1286                             db.span_suggestion(
1287                                 arg.span,
1288                                 "consider using the following if you are attempting to iterate over this \
1289                                  range in reverse",
1290                                 format!(
1291                                     "({end}{dots}{start}).rev()",
1292                                     end = end_snippet,
1293                                     dots = dots,
1294                                     start = start_snippet
1295                                 ),
1296                                 Applicability::MaybeIncorrect,
1297                             );
1298                         },
1299                     );
1300                 } else if eq && limits != ast::RangeLimits::Closed {
1301                     // if they are equal, it's also problematic - this loop
1302                     // will never run.
1303                     span_lint(
1304                         cx,
1305                         REVERSE_RANGE_LOOP,
1306                         expr.span,
1307                         "this range is empty so this for loop will never run",
1308                     );
1309                 }
1310             }
1311         }
1312     }
1313 }
1314
1315 fn lint_iter_method(cx: &LateContext<'_, '_>, args: &[Expr], arg: &Expr, method_name: &str) {
1316     let mut applicability = Applicability::MachineApplicable;
1317     let object = snippet_with_applicability(cx, args[0].span, "_", &mut applicability);
1318     let muta = if method_name == "iter_mut" { "mut " } else { "" };
1319     span_lint_and_sugg(
1320         cx,
1321         EXPLICIT_ITER_LOOP,
1322         arg.span,
1323         "it is more concise to loop over references to containers instead of using explicit \
1324          iteration methods",
1325         "to write this more concisely, try",
1326         format!("&{}{}", muta, object),
1327         applicability,
1328     )
1329 }
1330
1331 fn check_for_loop_arg(cx: &LateContext<'_, '_>, pat: &Pat, arg: &Expr, expr: &Expr) {
1332     let mut next_loop_linted = false; // whether or not ITER_NEXT_LOOP lint was used
1333     if let ExprKind::MethodCall(ref method, _, ref args) = arg.node {
1334         // just the receiver, no arguments
1335         if args.len() == 1 {
1336             let method_name = &*method.ident.as_str();
1337             // check for looping over x.iter() or x.iter_mut(), could use &x or &mut x
1338             if method_name == "iter" || method_name == "iter_mut" {
1339                 if is_ref_iterable_type(cx, &args[0]) {
1340                     lint_iter_method(cx, args, arg, method_name);
1341                 }
1342             } else if method_name == "into_iter" && match_trait_method(cx, arg, &paths::INTO_ITERATOR) {
1343                 let def_id = cx.tables.type_dependent_def_id(arg.hir_id).unwrap();
1344                 let substs = cx.tables.node_substs(arg.hir_id);
1345                 let method_type = cx.tcx.type_of(def_id).subst(cx.tcx, substs);
1346
1347                 let fn_arg_tys = method_type.fn_sig(cx.tcx).inputs();
1348                 assert_eq!(fn_arg_tys.skip_binder().len(), 1);
1349                 if fn_arg_tys.skip_binder()[0].is_region_ptr() {
1350                     match cx.tables.expr_ty(&args[0]).sty {
1351                         // If the length is greater than 32 no traits are implemented for array and
1352                         // therefore we cannot use `&`.
1353                         ty::Array(_, size) if size.eval_usize(cx.tcx, cx.param_env) > 32 => {},
1354                         _ => lint_iter_method(cx, args, arg, method_name),
1355                     };
1356                 } else {
1357                     let mut applicability = Applicability::MachineApplicable;
1358                     let object = snippet_with_applicability(cx, args[0].span, "_", &mut applicability);
1359                     span_lint_and_sugg(
1360                         cx,
1361                         EXPLICIT_INTO_ITER_LOOP,
1362                         arg.span,
1363                         "it is more concise to loop over containers instead of using explicit \
1364                          iteration methods`",
1365                         "to write this more concisely, try",
1366                         object.to_string(),
1367                         applicability,
1368                     );
1369                 }
1370             } else if method_name == "next" && match_trait_method(cx, arg, &paths::ITERATOR) {
1371                 span_lint(
1372                     cx,
1373                     ITER_NEXT_LOOP,
1374                     expr.span,
1375                     "you are iterating over `Iterator::next()` which is an Option; this will compile but is \
1376                      probably not what you want",
1377                 );
1378                 next_loop_linted = true;
1379             }
1380         }
1381     }
1382     if !next_loop_linted {
1383         check_arg_type(cx, pat, arg);
1384     }
1385 }
1386
1387 /// Checks for `for` loops over `Option`s and `Result`s.
1388 fn check_arg_type(cx: &LateContext<'_, '_>, pat: &Pat, arg: &Expr) {
1389     let ty = cx.tables.expr_ty(arg);
1390     if match_type(cx, ty, &paths::OPTION) {
1391         span_help_and_lint(
1392             cx,
1393             FOR_LOOP_OVER_OPTION,
1394             arg.span,
1395             &format!(
1396                 "for loop over `{0}`, which is an `Option`. This is more readably written as an \
1397                  `if let` statement.",
1398                 snippet(cx, arg.span, "_")
1399             ),
1400             &format!(
1401                 "consider replacing `for {0} in {1}` with `if let Some({0}) = {1}`",
1402                 snippet(cx, pat.span, "_"),
1403                 snippet(cx, arg.span, "_")
1404             ),
1405         );
1406     } else if match_type(cx, ty, &paths::RESULT) {
1407         span_help_and_lint(
1408             cx,
1409             FOR_LOOP_OVER_RESULT,
1410             arg.span,
1411             &format!(
1412                 "for loop over `{0}`, which is a `Result`. This is more readably written as an \
1413                  `if let` statement.",
1414                 snippet(cx, arg.span, "_")
1415             ),
1416             &format!(
1417                 "consider replacing `for {0} in {1}` with `if let Ok({0}) = {1}`",
1418                 snippet(cx, pat.span, "_"),
1419                 snippet(cx, arg.span, "_")
1420             ),
1421         );
1422     }
1423 }
1424
1425 fn check_for_loop_explicit_counter<'a, 'tcx>(
1426     cx: &LateContext<'a, 'tcx>,
1427     pat: &'tcx Pat,
1428     arg: &'tcx Expr,
1429     body: &'tcx Expr,
1430     expr: &'tcx Expr,
1431 ) {
1432     // Look for variables that are incremented once per loop iteration.
1433     let mut visitor = IncrementVisitor {
1434         cx,
1435         states: FxHashMap::default(),
1436         depth: 0,
1437         done: false,
1438     };
1439     walk_expr(&mut visitor, body);
1440
1441     // For each candidate, check the parent block to see if
1442     // it's initialized to zero at the start of the loop.
1443     if let Some(block) = get_enclosing_block(&cx, expr.hir_id) {
1444         for (id, _) in visitor.states.iter().filter(|&(_, v)| *v == VarState::IncrOnce) {
1445             let mut visitor2 = InitializeVisitor {
1446                 cx,
1447                 end_expr: expr,
1448                 var_id: *id,
1449                 state: VarState::IncrOnce,
1450                 name: None,
1451                 depth: 0,
1452                 past_loop: false,
1453             };
1454             walk_block(&mut visitor2, block);
1455
1456             if visitor2.state == VarState::Warn {
1457                 if let Some(name) = visitor2.name {
1458                     let mut applicability = Applicability::MachineApplicable;
1459                     span_lint_and_sugg(
1460                         cx,
1461                         EXPLICIT_COUNTER_LOOP,
1462                         expr.span,
1463                         &format!("the variable `{}` is used as a loop counter.", name),
1464                         "consider using",
1465                         format!(
1466                             "for ({}, {}) in {}.enumerate()",
1467                             name,
1468                             snippet_with_applicability(cx, pat.span, "item", &mut applicability),
1469                             if higher::range(cx, arg).is_some() {
1470                                 format!(
1471                                     "({})",
1472                                     snippet_with_applicability(cx, arg.span, "_", &mut applicability)
1473                                 )
1474                             } else {
1475                                 format!(
1476                                     "{}",
1477                                     sugg::Sugg::hir_with_applicability(cx, arg, "_", &mut applicability).maybe_par()
1478                                 )
1479                             }
1480                         ),
1481                         applicability,
1482                     );
1483                 }
1484             }
1485         }
1486     }
1487 }
1488
1489 /// Checks for the `FOR_KV_MAP` lint.
1490 fn check_for_loop_over_map_kv<'a, 'tcx>(
1491     cx: &LateContext<'a, 'tcx>,
1492     pat: &'tcx Pat,
1493     arg: &'tcx Expr,
1494     body: &'tcx Expr,
1495     expr: &'tcx Expr,
1496 ) {
1497     let pat_span = pat.span;
1498
1499     if let PatKind::Tuple(ref pat, _) = pat.node {
1500         if pat.len() == 2 {
1501             let arg_span = arg.span;
1502             let (new_pat_span, kind, ty, mutbl) = match cx.tables.expr_ty(arg).sty {
1503                 ty::Ref(_, ty, mutbl) => match (&pat[0].node, &pat[1].node) {
1504                     (key, _) if pat_is_wild(key, body) => (pat[1].span, "value", ty, mutbl),
1505                     (_, value) if pat_is_wild(value, body) => (pat[0].span, "key", ty, MutImmutable),
1506                     _ => return,
1507                 },
1508                 _ => return,
1509             };
1510             let mutbl = match mutbl {
1511                 MutImmutable => "",
1512                 MutMutable => "_mut",
1513             };
1514             let arg = match arg.node {
1515                 ExprKind::AddrOf(_, ref expr) => &**expr,
1516                 _ => arg,
1517             };
1518
1519             if match_type(cx, ty, &paths::HASHMAP) || match_type(cx, ty, &paths::BTREEMAP) {
1520                 span_lint_and_then(
1521                     cx,
1522                     FOR_KV_MAP,
1523                     expr.span,
1524                     &format!("you seem to want to iterate on a map's {}s", kind),
1525                     |db| {
1526                         let map = sugg::Sugg::hir(cx, arg, "map");
1527                         multispan_sugg(
1528                             db,
1529                             "use the corresponding method".into(),
1530                             vec![
1531                                 (pat_span, snippet(cx, new_pat_span, kind).into_owned()),
1532                                 (arg_span, format!("{}.{}s{}()", map.maybe_par(), kind, mutbl)),
1533                             ],
1534                         );
1535                     },
1536                 );
1537             }
1538         }
1539     }
1540 }
1541
1542 struct MutatePairDelegate {
1543     hir_id_low: Option<HirId>,
1544     hir_id_high: Option<HirId>,
1545     span_low: Option<Span>,
1546     span_high: Option<Span>,
1547 }
1548
1549 impl<'tcx> Delegate<'tcx> for MutatePairDelegate {
1550     fn consume(&mut self, _: HirId, _: Span, _: &cmt_<'tcx>, _: ConsumeMode) {}
1551
1552     fn matched_pat(&mut self, _: &Pat, _: &cmt_<'tcx>, _: MatchMode) {}
1553
1554     fn consume_pat(&mut self, _: &Pat, _: &cmt_<'tcx>, _: ConsumeMode) {}
1555
1556     fn borrow(&mut self, _: HirId, sp: Span, cmt: &cmt_<'tcx>, _: ty::Region<'_>, bk: ty::BorrowKind, _: LoanCause) {
1557         if let ty::BorrowKind::MutBorrow = bk {
1558             if let Categorization::Local(id) = cmt.cat {
1559                 if Some(id) == self.hir_id_low {
1560                     self.span_low = Some(sp)
1561                 }
1562                 if Some(id) == self.hir_id_high {
1563                     self.span_high = Some(sp)
1564                 }
1565             }
1566         }
1567     }
1568
1569     fn mutate(&mut self, _: HirId, sp: Span, cmt: &cmt_<'tcx>, _: MutateMode) {
1570         if let Categorization::Local(id) = cmt.cat {
1571             if Some(id) == self.hir_id_low {
1572                 self.span_low = Some(sp)
1573             }
1574             if Some(id) == self.hir_id_high {
1575                 self.span_high = Some(sp)
1576             }
1577         }
1578     }
1579
1580     fn decl_without_init(&mut self, _: HirId, _: Span) {}
1581 }
1582
1583 impl<'tcx> MutatePairDelegate {
1584     fn mutation_span(&self) -> (Option<Span>, Option<Span>) {
1585         (self.span_low, self.span_high)
1586     }
1587 }
1588
1589 fn check_for_mut_range_bound(cx: &LateContext<'_, '_>, arg: &Expr, body: &Expr) {
1590     if let Some(higher::Range {
1591         start: Some(start),
1592         end: Some(end),
1593         ..
1594     }) = higher::range(cx, arg)
1595     {
1596         let mut_ids = vec![check_for_mutability(cx, start), check_for_mutability(cx, end)];
1597         if mut_ids[0].is_some() || mut_ids[1].is_some() {
1598             let (span_low, span_high) = check_for_mutation(cx, body, &mut_ids);
1599             mut_warn_with_span(cx, span_low);
1600             mut_warn_with_span(cx, span_high);
1601         }
1602     }
1603 }
1604
1605 fn mut_warn_with_span(cx: &LateContext<'_, '_>, span: Option<Span>) {
1606     if let Some(sp) = span {
1607         span_lint(
1608             cx,
1609             MUT_RANGE_BOUND,
1610             sp,
1611             "attempt to mutate range bound within loop; note that the range of the loop is unchanged",
1612         );
1613     }
1614 }
1615
1616 fn check_for_mutability(cx: &LateContext<'_, '_>, bound: &Expr) -> Option<HirId> {
1617     if_chain! {
1618         if let ExprKind::Path(ref qpath) = bound.node;
1619         if let QPath::Resolved(None, _) = *qpath;
1620         then {
1621             let res = qpath_res(cx, qpath, bound.hir_id);
1622             if let Res::Local(node_id) = res {
1623                 let node_str = cx.tcx.hir().get(node_id);
1624                 if_chain! {
1625                     if let Node::Binding(pat) = node_str;
1626                     if let PatKind::Binding(bind_ann, ..) = pat.node;
1627                     if let BindingAnnotation::Mutable = bind_ann;
1628                     then {
1629                         return Some(node_id);
1630                     }
1631                 }
1632             }
1633         }
1634     }
1635     None
1636 }
1637
1638 fn check_for_mutation(
1639     cx: &LateContext<'_, '_>,
1640     body: &Expr,
1641     bound_ids: &[Option<HirId>],
1642 ) -> (Option<Span>, Option<Span>) {
1643     let mut delegate = MutatePairDelegate {
1644         hir_id_low: bound_ids[0],
1645         hir_id_high: bound_ids[1],
1646         span_low: None,
1647         span_high: None,
1648     };
1649     let def_id = def_id::DefId::local(body.hir_id.owner);
1650     let region_scope_tree = &cx.tcx.region_scope_tree(def_id);
1651     ExprUseVisitor::new(
1652         &mut delegate,
1653         cx.tcx,
1654         def_id,
1655         cx.param_env,
1656         region_scope_tree,
1657         cx.tables,
1658         None,
1659     )
1660     .walk_expr(body);
1661     delegate.mutation_span()
1662 }
1663
1664 /// Returns `true` if the pattern is a `PatWild` or an ident prefixed with `_`.
1665 fn pat_is_wild<'tcx>(pat: &'tcx PatKind, body: &'tcx Expr) -> bool {
1666     match *pat {
1667         PatKind::Wild => true,
1668         PatKind::Binding(.., ident, None) if ident.as_str().starts_with('_') => {
1669             let mut visitor = UsedVisitor {
1670                 var: ident.name,
1671                 used: false,
1672             };
1673             walk_expr(&mut visitor, body);
1674             !visitor.used
1675         },
1676         _ => false,
1677     }
1678 }
1679
1680 struct UsedVisitor {
1681     var: ast::Name, // var to look for
1682     used: bool,     // has the var been used otherwise?
1683 }
1684
1685 impl<'tcx> Visitor<'tcx> for UsedVisitor {
1686     fn visit_expr(&mut self, expr: &'tcx Expr) {
1687         if match_var(expr, self.var) {
1688             self.used = true;
1689         } else {
1690             walk_expr(self, expr);
1691         }
1692     }
1693
1694     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
1695         NestedVisitorMap::None
1696     }
1697 }
1698
1699 struct LocalUsedVisitor<'a, 'tcx> {
1700     cx: &'a LateContext<'a, 'tcx>,
1701     local: HirId,
1702     used: bool,
1703 }
1704
1705 impl<'a, 'tcx> Visitor<'tcx> for LocalUsedVisitor<'a, 'tcx> {
1706     fn visit_expr(&mut self, expr: &'tcx Expr) {
1707         if same_var(self.cx, expr, self.local) {
1708             self.used = true;
1709         } else {
1710             walk_expr(self, expr);
1711         }
1712     }
1713
1714     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
1715         NestedVisitorMap::None
1716     }
1717 }
1718
1719 struct VarVisitor<'a, 'tcx> {
1720     /// context reference
1721     cx: &'a LateContext<'a, 'tcx>,
1722     /// var name to look for as index
1723     var: HirId,
1724     /// indexed variables that are used mutably
1725     indexed_mut: FxHashSet<Name>,
1726     /// indirectly indexed variables (`v[(i + 4) % N]`), the extend is `None` for global
1727     indexed_indirectly: FxHashMap<Name, Option<region::Scope>>,
1728     /// subset of `indexed` of vars that are indexed directly: `v[i]`
1729     /// this will not contain cases like `v[calc_index(i)]` or `v[(i + 4) % N]`
1730     indexed_directly: FxHashMap<Name, (Option<region::Scope>, Ty<'tcx>)>,
1731     /// Any names that are used outside an index operation.
1732     /// Used to detect things like `&mut vec` used together with `vec[i]`
1733     referenced: FxHashSet<Name>,
1734     /// has the loop variable been used in expressions other than the index of
1735     /// an index op?
1736     nonindex: bool,
1737     /// Whether we are inside the `$` in `&mut $` or `$ = foo` or `$.bar`, where bar
1738     /// takes `&mut self`
1739     prefer_mutable: bool,
1740 }
1741
1742 impl<'a, 'tcx> VarVisitor<'a, 'tcx> {
1743     fn check(&mut self, idx: &'tcx Expr, seqexpr: &'tcx Expr, expr: &'tcx Expr) -> bool {
1744         if_chain! {
1745             // the indexed container is referenced by a name
1746             if let ExprKind::Path(ref seqpath) = seqexpr.node;
1747             if let QPath::Resolved(None, ref seqvar) = *seqpath;
1748             if seqvar.segments.len() == 1;
1749             then {
1750                 let index_used_directly = same_var(self.cx, idx, self.var);
1751                 let indexed_indirectly = {
1752                     let mut used_visitor = LocalUsedVisitor {
1753                         cx: self.cx,
1754                         local: self.var,
1755                         used: false,
1756                     };
1757                     walk_expr(&mut used_visitor, idx);
1758                     used_visitor.used
1759                 };
1760
1761                 if indexed_indirectly || index_used_directly {
1762                     if self.prefer_mutable {
1763                         self.indexed_mut.insert(seqvar.segments[0].ident.name);
1764                     }
1765                     let res = qpath_res(self.cx, seqpath, seqexpr.hir_id);
1766                     match res {
1767                         Res::Local(hir_id) => {
1768                             let parent_id = self.cx.tcx.hir().get_parent_item(expr.hir_id);
1769                             let parent_def_id = self.cx.tcx.hir().local_def_id(parent_id);
1770                             let extent = self.cx.tcx.region_scope_tree(parent_def_id).var_scope(hir_id.local_id);
1771                             if indexed_indirectly {
1772                                 self.indexed_indirectly.insert(seqvar.segments[0].ident.name, Some(extent));
1773                             }
1774                             if index_used_directly {
1775                                 self.indexed_directly.insert(
1776                                     seqvar.segments[0].ident.name,
1777                                     (Some(extent), self.cx.tables.node_type(seqexpr.hir_id)),
1778                                 );
1779                             }
1780                             return false;  // no need to walk further *on the variable*
1781                         }
1782                         Res::Def(DefKind::Static, ..) | Res::Def(DefKind::Const, ..) => {
1783                             if indexed_indirectly {
1784                                 self.indexed_indirectly.insert(seqvar.segments[0].ident.name, None);
1785                             }
1786                             if index_used_directly {
1787                                 self.indexed_directly.insert(
1788                                     seqvar.segments[0].ident.name,
1789                                     (None, self.cx.tables.node_type(seqexpr.hir_id)),
1790                                 );
1791                             }
1792                             return false;  // no need to walk further *on the variable*
1793                         }
1794                         _ => (),
1795                     }
1796                 }
1797             }
1798         }
1799         true
1800     }
1801 }
1802
1803 impl<'a, 'tcx> Visitor<'tcx> for VarVisitor<'a, 'tcx> {
1804     fn visit_expr(&mut self, expr: &'tcx Expr) {
1805         if_chain! {
1806             // a range index op
1807             if let ExprKind::MethodCall(ref meth, _, ref args) = expr.node;
1808             if (meth.ident.name == sym!(index) && match_trait_method(self.cx, expr, &paths::INDEX))
1809                 || (meth.ident.name == sym!(index_mut) && match_trait_method(self.cx, expr, &paths::INDEX_MUT));
1810             if !self.check(&args[1], &args[0], expr);
1811             then { return }
1812         }
1813
1814         if_chain! {
1815             // an index op
1816             if let ExprKind::Index(ref seqexpr, ref idx) = expr.node;
1817             if !self.check(idx, seqexpr, expr);
1818             then { return }
1819         }
1820
1821         if_chain! {
1822             // directly using a variable
1823             if let ExprKind::Path(ref qpath) = expr.node;
1824             if let QPath::Resolved(None, ref path) = *qpath;
1825             if path.segments.len() == 1;
1826             then {
1827                 if let Res::Local(local_id) = qpath_res(self.cx, qpath, expr.hir_id) {
1828                     if local_id == self.var {
1829                         self.nonindex = true;
1830                     } else {
1831                         // not the correct variable, but still a variable
1832                         self.referenced.insert(path.segments[0].ident.name);
1833                     }
1834                 }
1835             }
1836         }
1837
1838         let old = self.prefer_mutable;
1839         match expr.node {
1840             ExprKind::AssignOp(_, ref lhs, ref rhs) | ExprKind::Assign(ref lhs, ref rhs) => {
1841                 self.prefer_mutable = true;
1842                 self.visit_expr(lhs);
1843                 self.prefer_mutable = false;
1844                 self.visit_expr(rhs);
1845             },
1846             ExprKind::AddrOf(mutbl, ref expr) => {
1847                 if mutbl == MutMutable {
1848                     self.prefer_mutable = true;
1849                 }
1850                 self.visit_expr(expr);
1851             },
1852             ExprKind::Call(ref f, ref args) => {
1853                 self.visit_expr(f);
1854                 for expr in args {
1855                     let ty = self.cx.tables.expr_ty_adjusted(expr);
1856                     self.prefer_mutable = false;
1857                     if let ty::Ref(_, _, mutbl) = ty.sty {
1858                         if mutbl == MutMutable {
1859                             self.prefer_mutable = true;
1860                         }
1861                     }
1862                     self.visit_expr(expr);
1863                 }
1864             },
1865             ExprKind::MethodCall(_, _, ref args) => {
1866                 let def_id = self.cx.tables.type_dependent_def_id(expr.hir_id).unwrap();
1867                 for (ty, expr) in self.cx.tcx.fn_sig(def_id).inputs().skip_binder().iter().zip(args) {
1868                     self.prefer_mutable = false;
1869                     if let ty::Ref(_, _, mutbl) = ty.sty {
1870                         if mutbl == MutMutable {
1871                             self.prefer_mutable = true;
1872                         }
1873                     }
1874                     self.visit_expr(expr);
1875                 }
1876             },
1877             ExprKind::Closure(_, _, body_id, ..) => {
1878                 let body = self.cx.tcx.hir().body(body_id);
1879                 self.visit_expr(&body.value);
1880             },
1881             _ => walk_expr(self, expr),
1882         }
1883         self.prefer_mutable = old;
1884     }
1885     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
1886         NestedVisitorMap::None
1887     }
1888 }
1889
1890 fn is_used_inside<'a, 'tcx>(cx: &'a LateContext<'a, 'tcx>, expr: &'tcx Expr, container: &'tcx Expr) -> bool {
1891     let def_id = match var_def_id(cx, expr) {
1892         Some(id) => id,
1893         None => return false,
1894     };
1895     if let Some(used_mutably) = mutated_variables(container, cx) {
1896         if used_mutably.contains(&def_id) {
1897             return true;
1898         }
1899     }
1900     false
1901 }
1902
1903 fn is_iterator_used_after_while_let<'a, 'tcx>(cx: &LateContext<'a, 'tcx>, iter_expr: &'tcx Expr) -> bool {
1904     let def_id = match var_def_id(cx, iter_expr) {
1905         Some(id) => id,
1906         None => return false,
1907     };
1908     let mut visitor = VarUsedAfterLoopVisitor {
1909         cx,
1910         def_id,
1911         iter_expr_id: iter_expr.hir_id,
1912         past_while_let: false,
1913         var_used_after_while_let: false,
1914     };
1915     if let Some(enclosing_block) = get_enclosing_block(cx, def_id) {
1916         walk_block(&mut visitor, enclosing_block);
1917     }
1918     visitor.var_used_after_while_let
1919 }
1920
1921 struct VarUsedAfterLoopVisitor<'a, 'tcx> {
1922     cx: &'a LateContext<'a, 'tcx>,
1923     def_id: HirId,
1924     iter_expr_id: HirId,
1925     past_while_let: bool,
1926     var_used_after_while_let: bool,
1927 }
1928
1929 impl<'a, 'tcx> Visitor<'tcx> for VarUsedAfterLoopVisitor<'a, 'tcx> {
1930     fn visit_expr(&mut self, expr: &'tcx Expr) {
1931         if self.past_while_let {
1932             if Some(self.def_id) == var_def_id(self.cx, expr) {
1933                 self.var_used_after_while_let = true;
1934             }
1935         } else if self.iter_expr_id == expr.hir_id {
1936             self.past_while_let = true;
1937         }
1938         walk_expr(self, expr);
1939     }
1940     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
1941         NestedVisitorMap::None
1942     }
1943 }
1944
1945 /// Returns `true` if the type of expr is one that provides `IntoIterator` impls
1946 /// for `&T` and `&mut T`, such as `Vec`.
1947 #[rustfmt::skip]
1948 fn is_ref_iterable_type(cx: &LateContext<'_, '_>, e: &Expr) -> bool {
1949     // no walk_ptrs_ty: calling iter() on a reference can make sense because it
1950     // will allow further borrows afterwards
1951     let ty = cx.tables.expr_ty(e);
1952     is_iterable_array(ty, cx) ||
1953     is_type_diagnostic_item(cx, ty, Symbol::intern("vec_type")) ||
1954     match_type(cx, ty, &paths::LINKED_LIST) ||
1955     match_type(cx, ty, &paths::HASHMAP) ||
1956     match_type(cx, ty, &paths::HASHSET) ||
1957     match_type(cx, ty, &paths::VEC_DEQUE) ||
1958     match_type(cx, ty, &paths::BINARY_HEAP) ||
1959     match_type(cx, ty, &paths::BTREEMAP) ||
1960     match_type(cx, ty, &paths::BTREESET)
1961 }
1962
1963 fn is_iterable_array<'tcx>(ty: Ty<'tcx>, cx: &LateContext<'_, 'tcx>) -> bool {
1964     // IntoIterator is currently only implemented for array sizes <= 32 in rustc
1965     match ty.sty {
1966         ty::Array(_, n) => (0..=32).contains(&n.eval_usize(cx.tcx, cx.param_env)),
1967         _ => false,
1968     }
1969 }
1970
1971 /// If a block begins with a statement (possibly a `let` binding) and has an
1972 /// expression, return it.
1973 fn extract_expr_from_first_stmt(block: &Block) -> Option<&Expr> {
1974     if block.stmts.is_empty() {
1975         return None;
1976     }
1977     if let StmtKind::Local(ref local) = block.stmts[0].node {
1978         if let Some(ref expr) = local.init {
1979             Some(expr)
1980         } else {
1981             None
1982         }
1983     } else {
1984         None
1985     }
1986 }
1987
1988 /// If a block begins with an expression (with or without semicolon), return it.
1989 fn extract_first_expr(block: &Block) -> Option<&Expr> {
1990     match block.expr {
1991         Some(ref expr) if block.stmts.is_empty() => Some(expr),
1992         None if !block.stmts.is_empty() => match block.stmts[0].node {
1993             StmtKind::Expr(ref expr) | StmtKind::Semi(ref expr) => Some(expr),
1994             StmtKind::Local(..) | StmtKind::Item(..) => None,
1995         },
1996         _ => None,
1997     }
1998 }
1999
2000 /// Returns `true` if expr contains a single break expr without destination label
2001 /// and
2002 /// passed expression. The expression may be within a block.
2003 fn is_simple_break_expr(expr: &Expr) -> bool {
2004     match expr.node {
2005         ExprKind::Break(dest, ref passed_expr) if dest.label.is_none() && passed_expr.is_none() => true,
2006         ExprKind::Block(ref b, _) => extract_first_expr(b).map_or(false, |subexpr| is_simple_break_expr(subexpr)),
2007         _ => false,
2008     }
2009 }
2010
2011 // To trigger the EXPLICIT_COUNTER_LOOP lint, a variable must be
2012 // incremented exactly once in the loop body, and initialized to zero
2013 // at the start of the loop.
2014 #[derive(Debug, PartialEq)]
2015 enum VarState {
2016     Initial,  // Not examined yet
2017     IncrOnce, // Incremented exactly once, may be a loop counter
2018     Declared, // Declared but not (yet) initialized to zero
2019     Warn,
2020     DontWarn,
2021 }
2022
2023 /// Scan a for loop for variables that are incremented exactly once.
2024 struct IncrementVisitor<'a, 'tcx> {
2025     cx: &'a LateContext<'a, 'tcx>,      // context reference
2026     states: FxHashMap<HirId, VarState>, // incremented variables
2027     depth: u32,                         // depth of conditional expressions
2028     done: bool,
2029 }
2030
2031 impl<'a, 'tcx> Visitor<'tcx> for IncrementVisitor<'a, 'tcx> {
2032     fn visit_expr(&mut self, expr: &'tcx Expr) {
2033         if self.done {
2034             return;
2035         }
2036
2037         // If node is a variable
2038         if let Some(def_id) = var_def_id(self.cx, expr) {
2039             if let Some(parent) = get_parent_expr(self.cx, expr) {
2040                 let state = self.states.entry(def_id).or_insert(VarState::Initial);
2041
2042                 match parent.node {
2043                     ExprKind::AssignOp(op, ref lhs, ref rhs) => {
2044                         if lhs.hir_id == expr.hir_id {
2045                             if op.node == BinOpKind::Add && is_integer_const(self.cx, rhs, 1) {
2046                                 *state = match *state {
2047                                     VarState::Initial if self.depth == 0 => VarState::IncrOnce,
2048                                     _ => VarState::DontWarn,
2049                                 };
2050                             } else {
2051                                 // Assigned some other value
2052                                 *state = VarState::DontWarn;
2053                             }
2054                         }
2055                     },
2056                     ExprKind::Assign(ref lhs, _) if lhs.hir_id == expr.hir_id => *state = VarState::DontWarn,
2057                     ExprKind::AddrOf(mutability, _) if mutability == MutMutable => *state = VarState::DontWarn,
2058                     _ => (),
2059                 }
2060             }
2061         } else if is_loop(expr) || is_conditional(expr) {
2062             self.depth += 1;
2063             walk_expr(self, expr);
2064             self.depth -= 1;
2065             return;
2066         } else if let ExprKind::Continue(_) = expr.node {
2067             self.done = true;
2068             return;
2069         }
2070         walk_expr(self, expr);
2071     }
2072     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
2073         NestedVisitorMap::None
2074     }
2075 }
2076
2077 /// Checks whether a variable is initialized to zero at the start of a loop.
2078 struct InitializeVisitor<'a, 'tcx> {
2079     cx: &'a LateContext<'a, 'tcx>, // context reference
2080     end_expr: &'tcx Expr,          // the for loop. Stop scanning here.
2081     var_id: HirId,
2082     state: VarState,
2083     name: Option<Name>,
2084     depth: u32, // depth of conditional expressions
2085     past_loop: bool,
2086 }
2087
2088 impl<'a, 'tcx> Visitor<'tcx> for InitializeVisitor<'a, 'tcx> {
2089     fn visit_stmt(&mut self, stmt: &'tcx Stmt) {
2090         // Look for declarations of the variable
2091         if let StmtKind::Local(ref local) = stmt.node {
2092             if local.pat.hir_id == self.var_id {
2093                 if let PatKind::Binding(.., ident, _) = local.pat.node {
2094                     self.name = Some(ident.name);
2095
2096                     self.state = if let Some(ref init) = local.init {
2097                         if is_integer_const(&self.cx, init, 0) {
2098                             VarState::Warn
2099                         } else {
2100                             VarState::Declared
2101                         }
2102                     } else {
2103                         VarState::Declared
2104                     }
2105                 }
2106             }
2107         }
2108         walk_stmt(self, stmt);
2109     }
2110
2111     fn visit_expr(&mut self, expr: &'tcx Expr) {
2112         if self.state == VarState::DontWarn {
2113             return;
2114         }
2115         if SpanlessEq::new(self.cx).eq_expr(&expr, self.end_expr) {
2116             self.past_loop = true;
2117             return;
2118         }
2119         // No need to visit expressions before the variable is
2120         // declared
2121         if self.state == VarState::IncrOnce {
2122             return;
2123         }
2124
2125         // If node is the desired variable, see how it's used
2126         if var_def_id(self.cx, expr) == Some(self.var_id) {
2127             if let Some(parent) = get_parent_expr(self.cx, expr) {
2128                 match parent.node {
2129                     ExprKind::AssignOp(_, ref lhs, _) if lhs.hir_id == expr.hir_id => {
2130                         self.state = VarState::DontWarn;
2131                     },
2132                     ExprKind::Assign(ref lhs, ref rhs) if lhs.hir_id == expr.hir_id => {
2133                         self.state = if is_integer_const(&self.cx, rhs, 0) && self.depth == 0 {
2134                             VarState::Warn
2135                         } else {
2136                             VarState::DontWarn
2137                         }
2138                     },
2139                     ExprKind::AddrOf(mutability, _) if mutability == MutMutable => self.state = VarState::DontWarn,
2140                     _ => (),
2141                 }
2142             }
2143
2144             if self.past_loop {
2145                 self.state = VarState::DontWarn;
2146                 return;
2147             }
2148         } else if !self.past_loop && is_loop(expr) {
2149             self.state = VarState::DontWarn;
2150             return;
2151         } else if is_conditional(expr) {
2152             self.depth += 1;
2153             walk_expr(self, expr);
2154             self.depth -= 1;
2155             return;
2156         }
2157         walk_expr(self, expr);
2158     }
2159     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
2160         NestedVisitorMap::None
2161     }
2162 }
2163
2164 fn var_def_id(cx: &LateContext<'_, '_>, expr: &Expr) -> Option<HirId> {
2165     if let ExprKind::Path(ref qpath) = expr.node {
2166         let path_res = qpath_res(cx, qpath, expr.hir_id);
2167         if let Res::Local(node_id) = path_res {
2168             return Some(node_id);
2169         }
2170     }
2171     None
2172 }
2173
2174 fn is_loop(expr: &Expr) -> bool {
2175     match expr.node {
2176         ExprKind::Loop(..) => true,
2177         _ => false,
2178     }
2179 }
2180
2181 fn is_conditional(expr: &Expr) -> bool {
2182     match expr.node {
2183         ExprKind::Match(..) => true,
2184         _ => false,
2185     }
2186 }
2187
2188 fn is_nested(cx: &LateContext<'_, '_>, match_expr: &Expr, iter_expr: &Expr) -> bool {
2189     if_chain! {
2190         if let Some(loop_block) = get_enclosing_block(cx, match_expr.hir_id);
2191         let parent_node = cx.tcx.hir().get_parent_node(loop_block.hir_id);
2192         if let Some(Node::Expr(loop_expr)) = cx.tcx.hir().find(parent_node);
2193         then {
2194             return is_loop_nested(cx, loop_expr, iter_expr)
2195         }
2196     }
2197     false
2198 }
2199
2200 fn is_loop_nested(cx: &LateContext<'_, '_>, loop_expr: &Expr, iter_expr: &Expr) -> bool {
2201     let mut id = loop_expr.hir_id;
2202     let iter_name = if let Some(name) = path_name(iter_expr) {
2203         name
2204     } else {
2205         return true;
2206     };
2207     loop {
2208         let parent = cx.tcx.hir().get_parent_node(id);
2209         if parent == id {
2210             return false;
2211         }
2212         match cx.tcx.hir().find(parent) {
2213             Some(Node::Expr(expr)) => {
2214                 if let ExprKind::Loop(..) = expr.node {
2215                     return true;
2216                 };
2217             },
2218             Some(Node::Block(block)) => {
2219                 let mut block_visitor = LoopNestVisitor {
2220                     hir_id: id,
2221                     iterator: iter_name,
2222                     nesting: Unknown,
2223                 };
2224                 walk_block(&mut block_visitor, block);
2225                 if block_visitor.nesting == RuledOut {
2226                     return false;
2227                 }
2228             },
2229             Some(Node::Stmt(_)) => (),
2230             _ => {
2231                 return false;
2232             },
2233         }
2234         id = parent;
2235     }
2236 }
2237
2238 #[derive(PartialEq, Eq)]
2239 enum Nesting {
2240     Unknown,     // no nesting detected yet
2241     RuledOut,    // the iterator is initialized or assigned within scope
2242     LookFurther, // no nesting detected, no further walk required
2243 }
2244
2245 use self::Nesting::{LookFurther, RuledOut, Unknown};
2246
2247 struct LoopNestVisitor {
2248     hir_id: HirId,
2249     iterator: Name,
2250     nesting: Nesting,
2251 }
2252
2253 impl<'tcx> Visitor<'tcx> for LoopNestVisitor {
2254     fn visit_stmt(&mut self, stmt: &'tcx Stmt) {
2255         if stmt.hir_id == self.hir_id {
2256             self.nesting = LookFurther;
2257         } else if self.nesting == Unknown {
2258             walk_stmt(self, stmt);
2259         }
2260     }
2261
2262     fn visit_expr(&mut self, expr: &'tcx Expr) {
2263         if self.nesting != Unknown {
2264             return;
2265         }
2266         if expr.hir_id == self.hir_id {
2267             self.nesting = LookFurther;
2268             return;
2269         }
2270         match expr.node {
2271             ExprKind::Assign(ref path, _) | ExprKind::AssignOp(_, ref path, _) => {
2272                 if match_var(path, self.iterator) {
2273                     self.nesting = RuledOut;
2274                 }
2275             },
2276             _ => walk_expr(self, expr),
2277         }
2278     }
2279
2280     fn visit_pat(&mut self, pat: &'tcx Pat) {
2281         if self.nesting != Unknown {
2282             return;
2283         }
2284         if let PatKind::Binding(.., span_name, _) = pat.node {
2285             if self.iterator == span_name.name {
2286                 self.nesting = RuledOut;
2287                 return;
2288             }
2289         }
2290         walk_pat(self, pat)
2291     }
2292
2293     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
2294         NestedVisitorMap::None
2295     }
2296 }
2297
2298 fn path_name(e: &Expr) -> Option<Name> {
2299     if let ExprKind::Path(QPath::Resolved(_, ref path)) = e.node {
2300         let segments = &path.segments;
2301         if segments.len() == 1 {
2302             return Some(segments[0].ident.name);
2303         }
2304     };
2305     None
2306 }
2307
2308 fn check_infinite_loop<'a, 'tcx>(cx: &LateContext<'a, 'tcx>, cond: &'tcx Expr, expr: &'tcx Expr) {
2309     if constant(cx, cx.tables, cond).is_some() {
2310         // A pure constant condition (e.g., `while false`) is not linted.
2311         return;
2312     }
2313
2314     let mut var_visitor = VarCollectorVisitor {
2315         cx,
2316         ids: FxHashSet::default(),
2317         def_ids: FxHashMap::default(),
2318         skip: false,
2319     };
2320     var_visitor.visit_expr(cond);
2321     if var_visitor.skip {
2322         return;
2323     }
2324     let used_in_condition = &var_visitor.ids;
2325     let no_cond_variable_mutated = if let Some(used_mutably) = mutated_variables(expr, cx) {
2326         used_in_condition.is_disjoint(&used_mutably)
2327     } else {
2328         return;
2329     };
2330     let mutable_static_in_cond = var_visitor.def_ids.iter().any(|(_, v)| *v);
2331     if no_cond_variable_mutated && !mutable_static_in_cond {
2332         span_lint(
2333             cx,
2334             WHILE_IMMUTABLE_CONDITION,
2335             cond.span,
2336             "Variable in the condition are not mutated in the loop body. \
2337              This either leads to an infinite or to a never running loop.",
2338         );
2339     }
2340 }
2341
2342 /// Collects the set of variables in an expression
2343 /// Stops analysis if a function call is found
2344 /// Note: In some cases such as `self`, there are no mutable annotation,
2345 /// All variables definition IDs are collected
2346 struct VarCollectorVisitor<'a, 'tcx> {
2347     cx: &'a LateContext<'a, 'tcx>,
2348     ids: FxHashSet<HirId>,
2349     def_ids: FxHashMap<def_id::DefId, bool>,
2350     skip: bool,
2351 }
2352
2353 impl<'a, 'tcx> VarCollectorVisitor<'a, 'tcx> {
2354     fn insert_def_id(&mut self, ex: &'tcx Expr) {
2355         if_chain! {
2356             if let ExprKind::Path(ref qpath) = ex.node;
2357             if let QPath::Resolved(None, _) = *qpath;
2358             let res = qpath_res(self.cx, qpath, ex.hir_id);
2359             then {
2360                 match res {
2361                     Res::Local(node_id) => {
2362                         self.ids.insert(node_id);
2363                     },
2364                     Res::Def(DefKind::Static, def_id) => {
2365                         let mutable = self.cx.tcx.is_mutable_static(def_id);
2366                         self.def_ids.insert(def_id, mutable);
2367                     },
2368                     _ => {},
2369                 }
2370             }
2371         }
2372     }
2373 }
2374
2375 impl<'a, 'tcx> Visitor<'tcx> for VarCollectorVisitor<'a, 'tcx> {
2376     fn visit_expr(&mut self, ex: &'tcx Expr) {
2377         match ex.node {
2378             ExprKind::Path(_) => self.insert_def_id(ex),
2379             // If there is any function/method call… we just stop analysis
2380             ExprKind::Call(..) | ExprKind::MethodCall(..) => self.skip = true,
2381
2382             _ => walk_expr(self, ex),
2383         }
2384     }
2385
2386     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
2387         NestedVisitorMap::None
2388     }
2389 }
2390
2391 const NEEDLESS_COLLECT_MSG: &str = "avoid using `collect()` when not needed";
2392
2393 fn check_needless_collect<'a, 'tcx>(expr: &'tcx Expr, cx: &LateContext<'a, 'tcx>) {
2394     if_chain! {
2395         if let ExprKind::MethodCall(ref method, _, ref args) = expr.node;
2396         if let ExprKind::MethodCall(ref chain_method, _, _) = args[0].node;
2397         if chain_method.ident.name == sym!(collect) && match_trait_method(cx, &args[0], &paths::ITERATOR);
2398         if let Some(ref generic_args) = chain_method.args;
2399         if let Some(GenericArg::Type(ref ty)) = generic_args.args.get(0);
2400         then {
2401             let ty = cx.tables.node_type(ty.hir_id);
2402             if is_type_diagnostic_item(cx, ty, Symbol::intern("vec_type")) ||
2403                 match_type(cx, ty, &paths::VEC_DEQUE) ||
2404                 match_type(cx, ty, &paths::BTREEMAP) ||
2405                 match_type(cx, ty, &paths::HASHMAP) {
2406                 if method.ident.name == sym!(len) {
2407                     let span = shorten_needless_collect_span(expr);
2408                     span_lint_and_then(cx, NEEDLESS_COLLECT, span, NEEDLESS_COLLECT_MSG, |db| {
2409                         db.span_suggestion(
2410                             span,
2411                             "replace with",
2412                             ".count()".to_string(),
2413                             Applicability::MachineApplicable,
2414                         );
2415                     });
2416                 }
2417                 if method.ident.name == sym!(is_empty) {
2418                     let span = shorten_needless_collect_span(expr);
2419                     span_lint_and_then(cx, NEEDLESS_COLLECT, span, NEEDLESS_COLLECT_MSG, |db| {
2420                         db.span_suggestion(
2421                             span,
2422                             "replace with",
2423                             ".next().is_none()".to_string(),
2424                             Applicability::MachineApplicable,
2425                         );
2426                     });
2427                 }
2428                 if method.ident.name == sym!(contains) {
2429                     let contains_arg = snippet(cx, args[1].span, "??");
2430                     let span = shorten_needless_collect_span(expr);
2431                     span_lint_and_then(cx, NEEDLESS_COLLECT, span, NEEDLESS_COLLECT_MSG, |db| {
2432                         db.span_suggestion(
2433                             span,
2434                             "replace with",
2435                             format!(
2436                                 ".any(|&x| x == {})",
2437                                 if contains_arg.starts_with('&') { &contains_arg[1..] } else { &contains_arg }
2438                             ),
2439                             Applicability::MachineApplicable,
2440                         );
2441                     });
2442                 }
2443             }
2444         }
2445     }
2446 }
2447
2448 fn shorten_needless_collect_span(expr: &Expr) -> Span {
2449     if_chain! {
2450         if let ExprKind::MethodCall(_, _, ref args) = expr.node;
2451         if let ExprKind::MethodCall(_, ref span, _) = args[0].node;
2452         then {
2453             return expr.span.with_lo(span.lo() - BytePos(1));
2454         }
2455     }
2456     unreachable!()
2457 }