<commit_before>use itertools::Itertools;
use reexport::*;
use rustc::hir::*;
use rustc::hir::def::Def;
use rustc::hir::def_id;
use rustc::hir::intravisit::{walk_block, walk_decl, walk_expr, walk_pat, walk_stmt, NestedVisitorMap, Visitor};
use rustc::hir::map::Node::{NodeBlock, NodeExpr, NodeStmt};
use rustc::lint::*;
use rustc::middle::const_val::ConstVal;
use rustc::middle::region;
// use rustc::middle::region::CodeExtent;
use rustc::middle::expr_use_visitor::*;
use rustc::middle::mem_categorization::Categorization;
use rustc::middle::mem_categorization::cmt;
use rustc::ty::{self, Ty};
use rustc::ty::subst::{Subst, Substs};
use rustc_const_eval::ConstContext;
use std::collections::{HashMap, HashSet};
use std::iter::{Iterator, once};
use syntax::ast;
use syntax::codemap::Span;
use utils::sugg;
use utils::const_to_u64;

use utils::{get_enclosing_block, get_parent_expr, higher, in_external_macro, is_integer_literal, is_refutable,
            last_path_segment, match_trait_method, match_type, match_var, multispan_sugg, snippet, snippet_opt,
            span_help_and_lint, span_lint, span_lint_and_sugg, span_lint_and_then};
use utils::paths;

/// **What it does:** Checks for for-loops that manually copy items between
/// slices that could be optimized by having a memcpy.
///
/// **Why is this bad?** It is not as fast as a memcpy.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for i in 0..src.len() {
///     dst[i + 64] = src[i];
/// }
/// ```
declare_lint! {
    pub MANUAL_MEMCPY,
    Warn,
    "manually copying items between slices"
}

/// **What it does:** Checks for looping over the range of `0..len` of some
/// collection just to get the values by index.
///
/// **Why is this bad?** Just iterating the collection itself makes the intent
/// more clear and is probably faster.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for i in 0..vec.len() {
///     println!("{}", vec[i]);
/// }
/// ```
declare_lint! {
    pub NEEDLESS_RANGE_LOOP,
    Warn,
    "for-looping over a range of indices where an iterator over items would do"
}

/// **What it does:** Checks for loops on `x.iter()` where `&x` will do, and
/// suggests the latter.
///
/// **Why is this bad?** Readability.
///
/// **Known problems:** False negatives. We currently only warn on some known
/// types.
///
/// **Example:**
/// ```rust
/// // with `y` a `Vec` or slice:
/// for x in y.iter() { .. }
/// ```
declare_lint! {
    pub EXPLICIT_ITER_LOOP,
    Warn,
    "for-looping over `_.iter()` or `_.iter_mut()` when `&_` or `&mut _` would do"
}

/// **What it does:** Checks for loops on `y.into_iter()` where `y` will do, and
/// suggests the latter.
///
/// **Why is this bad?** Readability.
///
/// **Known problems:** None
///
/// **Example:**
/// ```rust
/// // with `y` a `Vec` or slice:
/// for x in y.into_iter() { .. }
/// ```
declare_lint! {
    pub EXPLICIT_INTO_ITER_LOOP,
    Warn,
    "for-looping over `_.into_iter()` when `_` would do"
}

/// **What it does:** Checks for loops on `x.next()`.
///
/// **Why is this bad?** `next()` returns either `Some(value)` if there was a
/// value, or `None` otherwise. The insidious thing is that `Option<_>`
/// implements `IntoIterator`, so that possibly one value will be iterated,
/// leading to some hard to find bugs. No one will want to write such code
/// [except to win an Underhanded Rust
/// Contest](https://www.reddit.
/// com/r/rust/comments/3hb0wm/underhanded_rust_contest/cu5yuhr).
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for x in y.next() { .. }
/// ```
declare_lint! {
    pub ITER_NEXT_LOOP,
    Warn,
    "for-looping over `_.next()` which is probably not intended"
}

/// **What it does:** Checks for `for` loops over `Option` values.
///
/// **Why is this bad?** Readability. This is more clearly expressed as an `if
/// let`.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for x in option { .. }
/// ```
///
/// This should be
/// ```rust
/// if let Some(x) = option { .. }
/// ```
declare_lint! {
    pub FOR_LOOP_OVER_OPTION,
    Warn,
    "for-looping over an `Option`, which is more clearly expressed as an `if let`"
}

/// **What it does:** Checks for `for` loops over `Result` values.
///
/// **Why is this bad?** Readability. This is more clearly expressed as an `if
/// let`.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for x in result { .. }
/// ```
///
/// This should be
/// ```rust
/// if let Ok(x) = result { .. }
/// ```
declare_lint! {
    pub FOR_LOOP_OVER_RESULT,
    Warn,
    "for-looping over a `Result`, which is more clearly expressed as an `if let`"
}

/// **What it does:** Detects `loop + match` combinations that are easier
/// written as a `while let` loop.
///
/// **Why is this bad?** The `while let` loop is usually shorter and more
/// readable.
///
/// **Known problems:** Sometimes the wrong binding is displayed (#383).
///
/// **Example:**
/// ```rust
/// loop {
///     let x = match y {
///         Some(x) => x,
///         None => break,
///     }
///     // .. do something with x
/// }
/// // is easier written as
/// while let Some(x) = y {
///     // .. do something with x
/// }
/// ```
declare_lint! {
    pub WHILE_LET_LOOP,
    Warn,
    "`loop { if let { ... } else break }`, which can be written as a `while let` loop"
}

/// **What it does:** Checks for using `collect()` on an iterator without using
/// the result.
///
/// **Why is this bad?** It is more idiomatic to use a `for` loop over the
/// iterator instead.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// vec.iter().map(|x| /* some operation returning () */).collect::<Vec<_>>();
/// ```
declare_lint! {
    pub UNUSED_COLLECT,
    Warn,
    "`collect()`ing an iterator without using the result; this is usually better \
     written as a for loop"
}

/// **What it does:** Checks for loops over ranges `x..y` where both `x` and `y`
/// are constant and `x` is greater or equal to `y`, unless the range is
/// reversed or has a negative `.step_by(_)`.
///
/// **Why is it bad?** Such loops will either be skipped or loop until
/// wrap-around (in debug code, this may `panic!()`). Both options are probably
/// not intended.
///
/// **Known problems:** The lint cannot catch loops over dynamically defined
/// ranges. Doing this would require simulating all possible inputs and code
/// paths through the program, which would be complex and error-prone.
///
/// **Example:**
/// ```rust
/// for x in 5..10-5 { .. } // oops, stray `-`
/// ```
declare_lint! {
    pub REVERSE_RANGE_LOOP,
    Warn,
    "iteration over an empty range, such as `10..0` or `5..5`"
}

/// **What it does:** Checks `for` loops over slices with an explicit counter
/// and suggests the use of `.enumerate()`.
///
/// **Why is it bad?** Not only is the version using `.enumerate()` more
/// readable, the compiler is able to remove bounds checks which can lead to
/// faster code in some instances.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for i in 0..v.len() { foo(v[i]);
/// for i in 0..v.len() { bar(i, v[i]); }
/// ```
declare_lint! {
    pub EXPLICIT_COUNTER_LOOP,
    Warn,
    "for-looping with an explicit counter when `_.enumerate()` would do"
}

/// **What it does:** Checks for empty `loop` expressions.
///
/// **Why is this bad?** Those busy loops burn CPU cycles without doing
/// anything. Think of the environment and either block on something or at least
/// make the thread sleep for some microseconds.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// loop {}
/// ```
declare_lint! {
    pub EMPTY_LOOP,
    Warn,
    "empty `loop {}`, which should block or sleep"
}

/// **What it does:** Checks for `while let` expressions on iterators.
///
/// **Why is this bad?** Readability. A simple `for` loop is shorter and conveys
/// the intent better.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// while let Some(val) = iter() { .. }
/// ```
declare_lint! {
    pub WHILE_LET_ON_ITERATOR,
    Warn,
    "using a while-let loop instead of a for loop on an iterator"
}

/// **What it does:** Checks for iterating a map (`HashMap` or `BTreeMap`) and
/// ignoring either the keys or values.
///
/// **Why is this bad?** Readability. There are `keys` and `values` methods that
/// can be used to express that don't need the values or keys.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for (k, _) in &map { .. }
/// ```
///
/// could be replaced by
///
/// ```rust
/// for k in map.keys() { .. }
/// ```
declare_lint! {
    pub FOR_KV_MAP,
    Warn,
    "looping on a map using `iter` when `keys` or `values` would do"
}

/// **What it does:** Checks for loops that will always `break`, `return` or
/// `continue` an outer loop.
///
/// **Why is this bad?** This loop never loops, all it does is obfuscating the
/// code.
///
/// **Known problems:** None
///
/// **Example:**
/// ```rust
/// loop { ..; break; }
/// ```
declare_lint! {
    pub NEVER_LOOP,
    Warn,
    "any loop that will always `break` or `return`"
}

/// TODO: add documentation

declare_lint! {
    pub MUT_RANGE_BOUND,
    Warn,
    "for loop over a range where one of the bounds is a mutable variable"
}

#[derive(Copy, Clone)]
pub struct Pass;

impl LintPass for Pass {
    fn get_lints(&self) -> LintArray {
        lint_array!(
            MANUAL_MEMCPY,
            NEEDLESS_RANGE_LOOP,
            EXPLICIT_ITER_LOOP,
            EXPLICIT_INTO_ITER_LOOP,
            ITER_NEXT_LOOP,
            FOR_LOOP_OVER_RESULT,
            FOR_LOOP_OVER_OPTION,
            WHILE_LET_LOOP,
            UNUSED_COLLECT,
            REVERSE_RANGE_LOOP,
            EXPLICIT_COUNTER_LOOP,
            EMPTY_LOOP,
            WHILE_LET_ON_ITERATOR,
            FOR_KV_MAP,
            NEVER_LOOP,
            MUT_RANGE_BOUND
        )
    }
}

impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
    fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
        if let Some((pat, arg, body)) = higher::for_loop(expr) {
            check_for_loop(cx, pat, arg, body, expr);
        }

        // check for never_loop
        match expr.node {
            ExprWhile(_, ref block, _) |
            ExprLoop(ref block, _, _) => {
                match never_loop_block(block, &expr.id) {
                    NeverLoopResult::AlwaysBreak =>
                        span_lint(cx, NEVER_LOOP, expr.span, "this loop never actually loops"),
                    NeverLoopResult::MayContinueMainLoop | NeverLoopResult::Otherwise => (),
                }
            },
            _ => (),
        }

        // check for `loop { if let {} else break }` that could be `while let`
        // (also matches an explicit "match" instead of "if let")
        // (even if the "match" or "if let" is used for declaration)
        if let ExprLoop(ref block, _, LoopSource::Loop) = expr.node {
            // also check for empty `loop {}` statements
            if block.stmts.is_empty() && block.expr.is_none() {
                span_lint(
                    cx,
                    EMPTY_LOOP,
                    expr.span,
                    "empty `loop {}` detected. You may want to either use `panic!()` or add \
                     `std::thread::sleep(..);` to the loop body.",
                );
            }

            // extract the expression from the first statement (if any) in a block
            let inner_stmt_expr = extract_expr_from_first_stmt(block);
            // or extract the first expression (if any) from the block
            if let Some(inner) = inner_stmt_expr.or_else(|| extract_first_expr(block)) {
                if let ExprMatch(ref matchexpr, ref arms, ref source) = inner.node {
                    // ensure "if let" compatible match structure
                    match *source {
                        MatchSource::Normal |
                        MatchSource::IfLetDesugar { .. } => {
                            if arms.len() == 2 && arms[0].pats.len() == 1 && arms[0].guard.is_none() &&
                                arms[1].pats.len() == 1 && arms[1].guard.is_none() &&
                                is_simple_break_expr(&arms[1].body)
                            {
                                if in_external_macro(cx, expr.span) {
                                    return;
                                }

                                // NOTE: we used to make build a body here instead of using
                                // ellipsis, this was removed because:
                                // 1) it was ugly with big bodies;
                                // 2) it was not indented properly;
                                // 3) it wasn’t very smart (see #675).
                                span_lint_and_sugg(
                                    cx,
                                    WHILE_LET_LOOP,
                                    expr.span,
                                    "this loop could be written as a `while let` loop",
                                    "try",
                                    format!(
                                        "while let {} = {} {{ .. }}",
                                        snippet(cx, arms[0].pats[0].span, ".."),
                                        snippet(cx, matchexpr.span, "..")
                                    ),
                                );
                            }
                        },
                        _ => (),
                    }
                }
            }
        }
        if let ExprMatch(ref match_expr, ref arms, MatchSource::WhileLetDesugar) = expr.node {
            let pat = &arms[0].pats[0].node;
            if let (&PatKind::TupleStruct(ref qpath, ref pat_args, _),
                    &ExprMethodCall(ref method_path, _, ref method_args)) = (pat, &match_expr.node)
            {
                let iter_expr = &method_args[0];
                let lhs_constructor = last_path_segment(qpath);
                if method_path.name == "next" && match_trait_method(cx, match_expr, &paths::ITERATOR) &&
                    lhs_constructor.name == "Some" && !is_refutable(cx, &pat_args[0]) &&
                    !is_iterator_used_after_while_let(cx, iter_expr) &&
                    !is_nested(cx, expr, &method_args[0])
                {
                    let iterator = snippet(cx, method_args[0].span, "_");
                    let loop_var = snippet(cx, pat_args[0].span, "_");
                    span_lint_and_sugg(
                        cx,
                        WHILE_LET_ON_ITERATOR,
                        expr.span,
                        "this loop could be written as a `for` loop",
                        "try",
                        format!("for {} in {} {{ .. }}", loop_var, iterator),
                    );
                }
            }
        }
    }

    fn check_stmt(&mut self, cx: &LateContext<'a, 'tcx>, stmt: &'tcx Stmt) {
        if let StmtSemi(ref expr, _) = stmt.node {
            if let ExprMethodCall(ref method, _, ref args) = expr.node {
                if args.len() == 1 && method.name == "collect" && match_trait_method(cx, expr, &paths::ITERATOR) {
                    span_lint(
                        cx,
                        UNUSED_COLLECT,
                        expr.span,
                        "you are collect()ing an iterator and throwing away the result. \
                         Consider using an explicit for loop to exhaust the iterator",
                    );
                }
            }
        }
    }
}

enum NeverLoopResult {
    // A break/return always get triggered but not necessarily for the main loop.
    AlwaysBreak,
    // A continue may occur for the main loop.
    MayContinueMainLoop,
    Otherwise,
}

fn absorb_break(arg: NeverLoopResult) -> NeverLoopResult {
    match arg {
        NeverLoopResult::AlwaysBreak |
        NeverLoopResult::Otherwise => NeverLoopResult::Otherwise,
        NeverLoopResult::MayContinueMainLoop => NeverLoopResult::MayContinueMainLoop,
    }
}

// Combine two results for parts that are called in order.
fn combine_seq(first: NeverLoopResult, second: NeverLoopResult) -> NeverLoopResult {
    match first {
        NeverLoopResult::AlwaysBreak | NeverLoopResult::MayContinueMainLoop => first,
        NeverLoopResult::Otherwise => second,
    }
}

// Combine two results where both parts are called but not necessarily in order.
fn combine_both(left: NeverLoopResult, right: NeverLoopResult) -> NeverLoopResult {
    match (left, right) {
        (NeverLoopResult::MayContinueMainLoop, _) | (_, NeverLoopResult::MayContinueMainLoop) =>
            NeverLoopResult::MayContinueMainLoop,
        (NeverLoopResult::AlwaysBreak, _) | (_, NeverLoopResult::AlwaysBreak) =>
            NeverLoopResult::AlwaysBreak,
        (NeverLoopResult::Otherwise, NeverLoopResult::Otherwise) =>
            NeverLoopResult::Otherwise,
    }
}

// Combine two results where only one of the part may have been executed.
fn combine_branches(b1: NeverLoopResult, b2: NeverLoopResult) -> NeverLoopResult {
    match (b1, b2) {
        (NeverLoopResult::AlwaysBreak, NeverLoopResult::AlwaysBreak) =>
            NeverLoopResult::AlwaysBreak,
        (NeverLoopResult::MayContinueMainLoop, _) | (_, NeverLoopResult::MayContinueMainLoop) =>
            NeverLoopResult::MayContinueMainLoop,
        (NeverLoopResult::Otherwise, _) | (_, NeverLoopResult::Otherwise) =>
            NeverLoopResult::Otherwise,
    }
}

fn never_loop_block(block: &Block, main_loop_id: &NodeId) -> NeverLoopResult {
    let stmts = block.stmts.iter().map(stmt_to_expr);
    let expr = once(block.expr.as_ref().map(|p| &**p));
    let mut iter = stmts.chain(expr).filter_map(|e| e);
    never_loop_expr_seq(&mut iter, main_loop_id)
}

fn stmt_to_expr(stmt: &Stmt) -> Option<&Expr> {
    match stmt.node {
        StmtSemi(ref e, ..) |
        StmtExpr(ref e, ..) => Some(e),
        StmtDecl(ref d, ..) => decl_to_expr(d),
    }
}

fn decl_to_expr(decl: &Decl) -> Option<&Expr> {
    match decl.node {
        DeclLocal(ref local) => local.init.as_ref().map(|p| &**p),
        _ => None,
    }
}

fn never_loop_expr(expr: &Expr, main_loop_id: &NodeId) -> NeverLoopResult {
    match expr.node {
        ExprBox(ref e) |
        ExprUnary(_, ref e) |
        ExprCast(ref e, _) |
        ExprType(ref e, _) |
        ExprField(ref e, _) |
        ExprTupField(ref e, _) |
        ExprAddrOf(_, ref e) |
        ExprStruct(_, _, Some(ref e)) |
        ExprRepeat(ref e, _) => never_loop_expr(e, main_loop_id),
        ExprArray(ref es) |
        ExprMethodCall(_, _, ref es) |
        ExprTup(ref es) => never_loop_expr_all(&mut es.iter(), main_loop_id),
        ExprCall(ref e, ref es) => never_loop_expr_all(&mut once(&**e).chain(es.iter()), main_loop_id),
        ExprBinary(_, ref e1, ref e2) |
        ExprAssign(ref e1, ref e2) |
        ExprAssignOp(_, ref e1, ref e2) |
        ExprIndex(ref e1, ref e2) => never_loop_expr_all(&mut [&**e1, &**e2].iter().cloned(), main_loop_id),
        ExprIf(ref e, ref e2, ref e3) => {
            let e1 = never_loop_expr(e, main_loop_id);
            let e2 = never_loop_expr(e2, main_loop_id);
            let e3 = e3.as_ref().map(|ref e| never_loop_expr(e, main_loop_id)).unwrap_or(NeverLoopResult::Otherwise);
            combine_seq(e1, combine_branches(e2, e3))
        },
        ExprLoop(ref b, _, _) => {
            // Break can come from the inner loop so remove them.
            absorb_break(never_loop_block(b, main_loop_id))
        },
        ExprWhile(ref e, ref b, _) => {
            let e = never_loop_expr(e, main_loop_id);
            let result = never_loop_block(b, main_loop_id);
            // Break can come from the inner loop so remove them.
            combine_seq(e, absorb_break(result))
        },
        ExprMatch(ref e, ref arms, _) => {
            let e = never_loop_expr(e, main_loop_id);
            if arms.is_empty() {
                e
            } else {
                let arms = never_loop_expr_branch(&mut arms.iter().map(|a| &*a.body), main_loop_id);
                combine_seq(e, arms)
            }
        },
        ExprBlock(ref b) => never_loop_block(b, main_loop_id),
        ExprAgain(d) => {
            let id = d.target_id.opt_id().expect("target id can only be missing in the presence of compilation errors");
            if id == *main_loop_id {
                NeverLoopResult::MayContinueMainLoop
            } else {
                NeverLoopResult::AlwaysBreak
            }
        },
        ExprBreak(_, _) => {
            NeverLoopResult::AlwaysBreak
        },
        ExprRet(ref e) => {
            if let Some(ref e) = *e {
                combine_seq(never_loop_expr(e, main_loop_id), NeverLoopResult::AlwaysBreak)
            } else {
                NeverLoopResult::AlwaysBreak
            }
        },
        ExprStruct(_, _, None) |<commit_msg>Make the dogfood test happy.<commit_after>use itertools::Itertools;
use reexport::*;
use rustc::hir::*;
use rustc::hir::def::Def;
use rustc::hir::def_id;
use rustc::hir::intravisit::{walk_block, walk_decl, walk_expr, walk_pat, walk_stmt, NestedVisitorMap, Visitor};
use rustc::hir::map::Node::{NodeBlock, NodeExpr, NodeStmt};
use rustc::lint::*;
use rustc::middle::const_val::ConstVal;
use rustc::middle::region;
// use rustc::middle::region::CodeExtent;
use rustc::middle::expr_use_visitor::*;
use rustc::middle::mem_categorization::Categorization;
use rustc::middle::mem_categorization::cmt;
use rustc::ty::{self, Ty};
use rustc::ty::subst::{Subst, Substs};
use rustc_const_eval::ConstContext;
use std::collections::{HashMap, HashSet};
use std::iter::{Iterator, once};
use syntax::ast;
use syntax::codemap::Span;
use utils::sugg;
use utils::const_to_u64;

use utils::{get_enclosing_block, get_parent_expr, higher, in_external_macro, is_integer_literal, is_refutable,
            last_path_segment, match_trait_method, match_type, match_var, multispan_sugg, snippet, snippet_opt,
            span_help_and_lint, span_lint, span_lint_and_sugg, span_lint_and_then};
use utils::paths;

/// **What it does:** Checks for for-loops that manually copy items between
/// slices that could be optimized by having a memcpy.
///
/// **Why is this bad?** It is not as fast as a memcpy.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for i in 0..src.len() {
///     dst[i + 64] = src[i];
/// }
/// ```
declare_lint! {
    pub MANUAL_MEMCPY,
    Warn,
    "manually copying items between slices"
}

/// **What it does:** Checks for looping over the range of `0..len` of some
/// collection just to get the values by index.
///
/// **Why is this bad?** Just iterating the collection itself makes the intent
/// more clear and is probably faster.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for i in 0..vec.len() {
///     println!("{}", vec[i]);
/// }
/// ```
declare_lint! {
    pub NEEDLESS_RANGE_LOOP,
    Warn,
    "for-looping over a range of indices where an iterator over items would do"
}

/// **What it does:** Checks for loops on `x.iter()` where `&x` will do, and
/// suggests the latter.
///
/// **Why is this bad?** Readability.
///
/// **Known problems:** False negatives. We currently only warn on some known
/// types.
///
/// **Example:**
/// ```rust
/// // with `y` a `Vec` or slice:
/// for x in y.iter() { .. }
/// ```
declare_lint! {
    pub EXPLICIT_ITER_LOOP,
    Warn,
    "for-looping over `_.iter()` or `_.iter_mut()` when `&_` or `&mut _` would do"
}

/// **What it does:** Checks for loops on `y.into_iter()` where `y` will do, and
/// suggests the latter.
///
/// **Why is this bad?** Readability.
///
/// **Known problems:** None
///
/// **Example:**
/// ```rust
/// // with `y` a `Vec` or slice:
/// for x in y.into_iter() { .. }
/// ```
declare_lint! {
    pub EXPLICIT_INTO_ITER_LOOP,
    Warn,
    "for-looping over `_.into_iter()` when `_` would do"
}

/// **What it does:** Checks for loops on `x.next()`.
///
/// **Why is this bad?** `next()` returns either `Some(value)` if there was a
/// value, or `None` otherwise. The insidious thing is that `Option<_>`
/// implements `IntoIterator`, so that possibly one value will be iterated,
/// leading to some hard to find bugs. No one will want to write such code
/// [except to win an Underhanded Rust
/// Contest](https://www.reddit.
/// com/r/rust/comments/3hb0wm/underhanded_rust_contest/cu5yuhr).
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for x in y.next() { .. }
/// ```
declare_lint! {
    pub ITER_NEXT_LOOP,
    Warn,
    "for-looping over `_.next()` which is probably not intended"
}

/// **What it does:** Checks for `for` loops over `Option` values.
///
/// **Why is this bad?** Readability. This is more clearly expressed as an `if
/// let`.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for x in option { .. }
/// ```
///
/// This should be
/// ```rust
/// if let Some(x) = option { .. }
/// ```
declare_lint! {
    pub FOR_LOOP_OVER_OPTION,
    Warn,
    "for-looping over an `Option`, which is more clearly expressed as an `if let`"
}

/// **What it does:** Checks for `for` loops over `Result` values.
///
/// **Why is this bad?** Readability. This is more clearly expressed as an `if
/// let`.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for x in result { .. }
/// ```
///
/// This should be
/// ```rust
/// if let Ok(x) = result { .. }
/// ```
declare_lint! {
    pub FOR_LOOP_OVER_RESULT,
    Warn,
    "for-looping over a `Result`, which is more clearly expressed as an `if let`"
}

/// **What it does:** Detects `loop + match` combinations that are easier
/// written as a `while let` loop.
///
/// **Why is this bad?** The `while let` loop is usually shorter and more
/// readable.
///
/// **Known problems:** Sometimes the wrong binding is displayed (#383).
///
/// **Example:**
/// ```rust
/// loop {
///     let x = match y {
///         Some(x) => x,
///         None => break,
///     }
///     // .. do something with x
/// }
/// // is easier written as
/// while let Some(x) = y {
///     // .. do something with x
/// }
/// ```
declare_lint! {
    pub WHILE_LET_LOOP,
    Warn,
    "`loop { if let { ... } else break }`, which can be written as a `while let` loop"
}

/// **What it does:** Checks for using `collect()` on an iterator without using
/// the result.
///
/// **Why is this bad?** It is more idiomatic to use a `for` loop over the
/// iterator instead.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// vec.iter().map(|x| /* some operation returning () */).collect::<Vec<_>>();
/// ```
declare_lint! {
    pub UNUSED_COLLECT,
    Warn,
    "`collect()`ing an iterator without using the result; this is usually better \
     written as a for loop"
}

/// **What it does:** Checks for loops over ranges `x..y` where both `x` and `y`
/// are constant and `x` is greater or equal to `y`, unless the range is
/// reversed or has a negative `.step_by(_)`.
///
/// **Why is it bad?** Such loops will either be skipped or loop until
/// wrap-around (in debug code, this may `panic!()`). Both options are probably
/// not intended.
///
/// **Known problems:** The lint cannot catch loops over dynamically defined
/// ranges. Doing this would require simulating all possible inputs and code
/// paths through the program, which would be complex and error-prone.
///
/// **Example:**
/// ```rust
/// for x in 5..10-5 { .. } // oops, stray `-`
/// ```
declare_lint! {
    pub REVERSE_RANGE_LOOP,
    Warn,
    "iteration over an empty range, such as `10..0` or `5..5`"
}

/// **What it does:** Checks `for` loops over slices with an explicit counter
/// and suggests the use of `.enumerate()`.
///
/// **Why is it bad?** Not only is the version using `.enumerate()` more
/// readable, the compiler is able to remove bounds checks which can lead to
/// faster code in some instances.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for i in 0..v.len() { foo(v[i]);
/// for i in 0..v.len() { bar(i, v[i]); }
/// ```
declare_lint! {
    pub EXPLICIT_COUNTER_LOOP,
    Warn,
    "for-looping with an explicit counter when `_.enumerate()` would do"
}

/// **What it does:** Checks for empty `loop` expressions.
///
/// **Why is this bad?** Those busy loops burn CPU cycles without doing
/// anything. Think of the environment and either block on something or at least
/// make the thread sleep for some microseconds.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// loop {}
/// ```
declare_lint! {
    pub EMPTY_LOOP,
    Warn,
    "empty `loop {}`, which should block or sleep"
}

/// **What it does:** Checks for `while let` expressions on iterators.
///
/// **Why is this bad?** Readability. A simple `for` loop is shorter and conveys
/// the intent better.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// while let Some(val) = iter() { .. }
/// ```
declare_lint! {
    pub WHILE_LET_ON_ITERATOR,
    Warn,
    "using a while-let loop instead of a for loop on an iterator"
}

/// **What it does:** Checks for iterating a map (`HashMap` or `BTreeMap`) and
/// ignoring either the keys or values.
///
/// **Why is this bad?** Readability. There are `keys` and `values` methods that
/// can be used to express that don't need the values or keys.
///
/// **Known problems:** None.
///
/// **Example:**
/// ```rust
/// for (k, _) in &map { .. }
/// ```
///
/// could be replaced by
///
/// ```rust
/// for k in map.keys() { .. }
/// ```
declare_lint! {
    pub FOR_KV_MAP,
    Warn,
    "looping on a map using `iter` when `keys` or `values` would do"
}

/// **What it does:** Checks for loops that will always `break`, `return` or
/// `continue` an outer loop.
///
/// **Why is this bad?** This loop never loops, all it does is obfuscating the
/// code.
///
/// **Known problems:** None
///
/// **Example:**
/// ```rust
/// loop { ..; break; }
/// ```
declare_lint! {
    pub NEVER_LOOP,
    Warn,
    "any loop that will always `break` or `return`"
}

/// TODO: add documentation

declare_lint! {
    pub MUT_RANGE_BOUND,
    Warn,
    "for loop over a range where one of the bounds is a mutable variable"
}

#[derive(Copy, Clone)]
pub struct Pass;

impl LintPass for Pass {
    fn get_lints(&self) -> LintArray {
        lint_array!(
            MANUAL_MEMCPY,
            NEEDLESS_RANGE_LOOP,
            EXPLICIT_ITER_LOOP,
            EXPLICIT_INTO_ITER_LOOP,
            ITER_NEXT_LOOP,
            FOR_LOOP_OVER_RESULT,
            FOR_LOOP_OVER_OPTION,
            WHILE_LET_LOOP,
            UNUSED_COLLECT,
            REVERSE_RANGE_LOOP,
            EXPLICIT_COUNTER_LOOP,
            EMPTY_LOOP,
            WHILE_LET_ON_ITERATOR,
            FOR_KV_MAP,
            NEVER_LOOP,
            MUT_RANGE_BOUND
        )
    }
}

impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
    fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
        if let Some((pat, arg, body)) = higher::for_loop(expr) {
            check_for_loop(cx, pat, arg, body, expr);
        }

        // check for never_loop
        match expr.node {
            ExprWhile(_, ref block, _) |
            ExprLoop(ref block, _, _) => {
                match never_loop_block(block, &expr.id) {
                    NeverLoopResult::AlwaysBreak =>
                        span_lint(cx, NEVER_LOOP, expr.span, "this loop never actually loops"),
                    NeverLoopResult::MayContinueMainLoop | NeverLoopResult::Otherwise => (),
                }
            },
            _ => (),
        }

        // check for `loop { if let {} else break }` that could be `while let`
        // (also matches an explicit "match" instead of "if let")
        // (even if the "match" or "if let" is used for declaration)
        if let ExprLoop(ref block, _, LoopSource::Loop) = expr.node {
            // also check for empty `loop {}` statements
            if block.stmts.is_empty() && block.expr.is_none() {
                span_lint(
                    cx,
                    EMPTY_LOOP,
                    expr.span,
                    "empty `loop {}` detected. You may want to either use `panic!()` or add \
                     `std::thread::sleep(..);` to the loop body.",
                );
            }

            // extract the expression from the first statement (if any) in a block
            let inner_stmt_expr = extract_expr_from_first_stmt(block);
            // or extract the first expression (if any) from the block
            if let Some(inner) = inner_stmt_expr.or_else(|| extract_first_expr(block)) {
                if let ExprMatch(ref matchexpr, ref arms, ref source) = inner.node {
                    // ensure "if let" compatible match structure
                    match *source {
                        MatchSource::Normal |
                        MatchSource::IfLetDesugar { .. } => {
                            if arms.len() == 2 && arms[0].pats.len() == 1 && arms[0].guard.is_none() &&
                                arms[1].pats.len() == 1 && arms[1].guard.is_none() &&
                                is_simple_break_expr(&arms[1].body)
                            {
                                if in_external_macro(cx, expr.span) {
                                    return;
                                }

                                // NOTE: we used to make build a body here instead of using
                                // ellipsis, this was removed because:
                                // 1) it was ugly with big bodies;
                                // 2) it was not indented properly;
                                // 3) it wasn’t very smart (see #675).
                                span_lint_and_sugg(
                                    cx,
                                    WHILE_LET_LOOP,
                                    expr.span,
                                    "this loop could be written as a `while let` loop",
                                    "try",
                                    format!(
                                        "while let {} = {} {{ .. }}",
                                        snippet(cx, arms[0].pats[0].span, ".."),
                                        snippet(cx, matchexpr.span, "..")
                                    ),
                                );
                            }
                        },
                        _ => (),
                    }
                }
            }
        }
        if let ExprMatch(ref match_expr, ref arms, MatchSource::WhileLetDesugar) = expr.node {
            let pat = &arms[0].pats[0].node;
            if let (&PatKind::TupleStruct(ref qpath, ref pat_args, _),
                    &ExprMethodCall(ref method_path, _, ref method_args)) = (pat, &match_expr.node)
            {
                let iter_expr = &method_args[0];
                let lhs_constructor = last_path_segment(qpath);
                if method_path.name == "next" && match_trait_method(cx, match_expr, &paths::ITERATOR) &&
                    lhs_constructor.name == "Some" && !is_refutable(cx, &pat_args[0]) &&
                    !is_iterator_used_after_while_let(cx, iter_expr) &&
                    !is_nested(cx, expr, &method_args[0])
                {
                    let iterator = snippet(cx, method_args[0].span, "_");
                    let loop_var = snippet(cx, pat_args[0].span, "_");
                    span_lint_and_sugg(
                        cx,
                        WHILE_LET_ON_ITERATOR,
                        expr.span,
                        "this loop could be written as a `for` loop",
                        "try",
                        format!("for {} in {} {{ .. }}", loop_var, iterator),
                    );
                }
            }
        }
    }

    fn check_stmt(&mut self, cx: &LateContext<'a, 'tcx>, stmt: &'tcx Stmt) {
        if let StmtSemi(ref expr, _) = stmt.node {
            if let ExprMethodCall(ref method, _, ref args) = expr.node {
                if args.len() == 1 && method.name == "collect" && match_trait_method(cx, expr, &paths::ITERATOR) {
                    span_lint(
                        cx,
                        UNUSED_COLLECT,
                        expr.span,
                        "you are collect()ing an iterator and throwing away the result. \
                         Consider using an explicit for loop to exhaust the iterator",
                    );
                }
            }
        }
    }
}

enum NeverLoopResult {
    // A break/return always get triggered but not necessarily for the main loop.
    AlwaysBreak,
    // A continue may occur for the main loop.
    MayContinueMainLoop,
    Otherwise,
}

fn absorb_break(arg: &NeverLoopResult) -> NeverLoopResult {
    match *arg {
        NeverLoopResult::AlwaysBreak |
        NeverLoopResult::Otherwise => NeverLoopResult::Otherwise,
        NeverLoopResult::MayContinueMainLoop => NeverLoopResult::MayContinueMainLoop,
    }
}

// Combine two results for parts that are called in order.
fn combine_seq(first: NeverLoopResult, second: NeverLoopResult) -> NeverLoopResult {
    match first {
        NeverLoopResult::AlwaysBreak | NeverLoopResult::MayContinueMainLoop => first,
        NeverLoopResult::Otherwise => second,
    }
}

// Combine two results where both parts are called but not necessarily in order.
fn combine_both(left: NeverLoopResult, right: NeverLoopResult) -> NeverLoopResult {
    match (left, right) {
        (NeverLoopResult::MayContinueMainLoop, _) | (_, NeverLoopResult::MayContinueMainLoop) =>
            NeverLoopResult::MayContinueMainLoop,
        (NeverLoopResult::AlwaysBreak, _) | (_, NeverLoopResult::AlwaysBreak) =>
            NeverLoopResult::AlwaysBreak,
        (NeverLoopResult::Otherwise, NeverLoopResult::Otherwise) =>
            NeverLoopResult::Otherwise,
    }
}

// Combine two results where only one of the part may have been executed.
fn combine_branches(b1: NeverLoopResult, b2: NeverLoopResult) -> NeverLoopResult {
    match (b1, b2) {
        (NeverLoopResult::AlwaysBreak, NeverLoopResult::AlwaysBreak) =>
            NeverLoopResult::AlwaysBreak,
        (NeverLoopResult::MayContinueMainLoop, _) | (_, NeverLoopResult::MayContinueMainLoop) =>
            NeverLoopResult::MayContinueMainLoop,
        (NeverLoopResult::Otherwise, _) | (_, NeverLoopResult::Otherwise) =>
            NeverLoopResult::Otherwise,
    }
}

fn never_loop_block(block: &Block, main_loop_id: &NodeId) -> NeverLoopResult {
    let stmts = block.stmts.iter().map(stmt_to_expr);
    let expr = once(block.expr.as_ref().map(|p| &**p));
    let mut iter = stmts.chain(expr).filter_map(|e| e);
    never_loop_expr_seq(&mut iter, main_loop_id)
}

fn stmt_to_expr(stmt: &Stmt) -> Option<&Expr> {
    match stmt.node {
        StmtSemi(ref e, ..) |
        StmtExpr(ref e, ..) => Some(e),
        StmtDecl(ref d, ..) => decl_to_expr(d),
    }
}

fn decl_to_expr(decl: &Decl) -> Option<&Expr> {
    match decl.node {
        DeclLocal(ref local) => local.init.as_ref().map(|p| &**p),
        _ => None,
    }
}

fn never_loop_expr(expr: &Expr, main_loop_id: &NodeId) -> NeverLoopResult {
    match expr.node {
        ExprBox(ref e) |
        ExprUnary(_, ref e) |
        ExprCast(ref e, _) |
        ExprType(ref e, _) |
        ExprField(ref e, _) |
        ExprTupField(ref e, _) |
        ExprAddrOf(_, ref e) |
        ExprStruct(_, _, Some(ref e)) |
        ExprRepeat(ref e, _) => never_loop_expr(e, main_loop_id),
        ExprArray(ref es) |
        ExprMethodCall(_, _, ref es) |
        ExprTup(ref es) => never_loop_expr_all(&mut es.iter(), main_loop_id),
        ExprCall(ref e, ref es) => never_loop_expr_all(&mut once(&**e).chain(es.iter()), main_loop_id),
        ExprBinary(_, ref e1, ref e2) |
        ExprAssign(ref e1, ref e2) |
        ExprAssignOp(_, ref e1, ref e2) |
        ExprIndex(ref e1, ref e2) => never_loop_expr_all(&mut [&**e1, &**e2].iter().cloned(), main_loop_id),
        ExprIf(ref e, ref e2, ref e3) => {
            let e1 = never_loop_expr(e, main_loop_id);
            let e2 = never_loop_expr(e2, main_loop_id);
            let e3 =
                match *e3 {
                    Some(ref e3) => never_loop_expr(e3, main_loop_id),
                    None => NeverLoopResult::Otherwise,
                };
            combine_seq(e1, combine_branches(e2, e3))
        },
        ExprLoop(ref b, _, _) => {
            // Break can come from the inner loop so remove them.
            absorb_break(&never_loop_block(b, main_loop_id))
        },
        ExprWhile(ref e, ref b, _) => {
            let e = never_loop_expr(e, main_loop_id);
            let result = never_loop_block(b, main_loop_id);
            // Break can come from the inner loop so remove them.
            combine_seq(e, absorb_break(&result))
        },
        ExprMatch(ref e, ref arms, _) => {
            let e = never_loop_expr(e, main_loop_id);
            if arms.is_empty() {
                e
            } else {
                let arms = never_loop_expr_branch(&mut arms.iter().map(|a| &*a.body), main_loop_id);
                combine_seq(e, arms)
            }
        },
        ExprBlock(ref b) => never_loop_block(b, main_loop_id),
        ExprAgain(d) => {
            let id = d.target_id.opt_id().expect("target id can only be missing in the presence of compilation errors");
            if id == *main_loop_id {
                NeverLoopResult::MayContinueMainLoop
            } else {
                NeverLoopResult::AlwaysBreak
            }
        },
        ExprBreak(_, _) => {
            NeverLoopResult::AlwaysBreak
        },
        ExprRet(ref e) => {
            if let Some(ref e) = *e {
                combine_seq(never_loop_expr(e, main_loop_id), NeverLoopResult::AlwaysBreak)
            } else {
                NeverLoopResult::AlwaysBreak
            }
        },
        ExprStruct(_, _, None) |
{'fraction_non_alphanumeric': 0.1500853970964987, 'fraction_numerical': 0.003463326691336939, 'mean_word_length': 1.9519641481688956, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 109, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 35, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3187391', 'n_tokens_mistral': 13116, 'n_tokens_neox': 12722, 'n_words': 3698}