don't emit AlwaysBreaks if it targets a block

Introduced an ignored_ids parameter.
Takes O(n^2) time in the worst case.

Can be changed to collect block ids in first phase,
and then filter with binary search in second.

2 files changed, 79 insertions, 45 deletions

diff --git a/clippy_lints/src/loops/never_loop.rs b/clippy_lints/src/loops/never_loop.rs
index abb18187ef1..123e1e3cce1 100644
--- a/clippy_lints/src/loops/never_loop.rs
+++ b/clippy_lints/src/loops/never_loop.rs
@@ -4,7 +4,7 @@ use clippy_utils::diagnostics::span_lint_and_then;
 use clippy_utils::higher::ForLoop;
 use clippy_utils::source::snippet;
 use rustc_errors::Applicability;
-use rustc_hir::{Block, Expr, ExprKind, HirId, InlineAsmOperand, Pat, Stmt, StmtKind};
+use rustc_hir::{Block, Destination, Expr, ExprKind, HirId, InlineAsmOperand, Pat, Stmt, StmtKind};
 use rustc_lint::LateContext;
 use rustc_span::Span;
 use std::iter::{once, Iterator};
@@ -16,7 +16,7 @@ pub(super) fn check(
     span: Span,
     for_loop: Option<&ForLoop<'_>>,
 ) {
-    match never_loop_block(block, loop_id) {
+    match never_loop_block(block, &mut Vec::new(), loop_id) {
         NeverLoopResult::AlwaysBreak => {
             span_lint_and_then(cx, NEVER_LOOP, span, "this loop never actually loops", |diag| {
                 if let Some(ForLoop {
@@ -92,35 +92,33 @@ fn combine_branches(b1: NeverLoopResult, b2: NeverLoopResult) -> NeverLoopResult
     }
 }
 
-fn never_loop_block(block: &Block<'_>, main_loop_id: HirId) -> NeverLoopResult {
-    let mut iter = block
+fn never_loop_block(block: &Block<'_>, ignore_ids: &mut Vec<HirId>, main_loop_id: HirId) -> NeverLoopResult {
+    let iter = block
         .stmts
         .iter()
         .filter_map(stmt_to_expr)
         .chain(block.expr.map(|expr| (expr, None)));
-    never_loop_expr_seq(&mut iter, main_loop_id)
-}
 
-fn never_loop_expr_seq<'a, T: Iterator<Item = (&'a Expr<'a>, Option<&'a Block<'a>>)>>(
-    es: &mut T,
-    main_loop_id: HirId,
-) -> NeverLoopResult {
-    es.map(|(e, els)| {
-        let e = never_loop_expr(e, main_loop_id);
-        els.map_or(e, |els| combine_branches(e, never_loop_block(els, main_loop_id)))
+    iter.map(|(e, els)| {
+        let e = never_loop_expr(e, ignore_ids, main_loop_id);
+        // els is an else block in a let...else binding
+        els.map_or(e, |els| {
+            combine_branches(e, never_loop_block(els, ignore_ids, main_loop_id))
+        })
     })
     .fold(NeverLoopResult::Otherwise, combine_seq)
 }
 
 fn stmt_to_expr<'tcx>(stmt: &Stmt<'tcx>) -> Option<(&'tcx Expr<'tcx>, Option<&'tcx Block<'tcx>>)> {
     match stmt.kind {
-        StmtKind::Semi(e, ..) | StmtKind::Expr(e, ..) => Some((e, None)),
+        StmtKind::Semi(e) | StmtKind::Expr(e) => Some((e, None)),
+        // add the let...else expression (if present)
         StmtKind::Local(local) => local.init.map(|init| (init, local.els)),
         StmtKind::Item(..) => None,
     }
 }
 
-fn never_loop_expr(expr: &Expr<'_>, main_loop_id: HirId) -> NeverLoopResult {
+fn never_loop_expr(expr: &Expr<'_>, ignore_ids: &mut Vec<HirId>, main_loop_id: HirId) -> NeverLoopResult {
     match expr.kind {
         ExprKind::Box(e)
         | ExprKind::Unary(_, e)
@@ -129,48 +127,56 @@ fn never_loop_expr(expr: &Expr<'_>, main_loop_id: HirId) -> NeverLoopResult {
         | ExprKind::Field(e, _)
         | ExprKind::AddrOf(_, _, e)
         | ExprKind::Repeat(e, _)
-        | ExprKind::DropTemps(e) => never_loop_expr(e, main_loop_id),
-        ExprKind::Let(let_expr) => never_loop_expr(let_expr.init, main_loop_id),
-        ExprKind::Array(es) | ExprKind::Tup(es) => never_loop_expr_all(&mut es.iter(), main_loop_id),
-        ExprKind::MethodCall(_, receiver, es, _) => {
-            never_loop_expr_all(&mut std::iter::once(receiver).chain(es.iter()), main_loop_id)
-        },
+        | ExprKind::DropTemps(e) => never_loop_expr(e, ignore_ids, main_loop_id),
+        ExprKind::Let(let_expr) => never_loop_expr(let_expr.init, ignore_ids, main_loop_id),
+        ExprKind::Array(es) | ExprKind::Tup(es) => never_loop_expr_all(&mut es.iter(), ignore_ids, main_loop_id),
+        ExprKind::MethodCall(_, receiver, es, _) => never_loop_expr_all(
+            &mut std::iter::once(receiver).chain(es.iter()),
+            ignore_ids,
+            main_loop_id,
+        ),
         ExprKind::Struct(_, fields, base) => {
-            let fields = never_loop_expr_all(&mut fields.iter().map(|f| f.expr), main_loop_id);
+            let fields = never_loop_expr_all(&mut fields.iter().map(|f| f.expr), ignore_ids, main_loop_id);
             if let Some(base) = base {
-                combine_both(fields, never_loop_expr(base, main_loop_id))
+                combine_both(fields, never_loop_expr(base, ignore_ids, main_loop_id))
             } else {
                 fields
             }
         },
-        ExprKind::Call(e, es) => never_loop_expr_all(&mut once(e).chain(es.iter()), main_loop_id),
+        ExprKind::Call(e, es) => never_loop_expr_all(&mut once(e).chain(es.iter()), ignore_ids, main_loop_id),
         ExprKind::Binary(_, e1, e2)
         | ExprKind::Assign(e1, e2, _)
         | ExprKind::AssignOp(_, e1, e2)
-        | ExprKind::Index(e1, e2) => never_loop_expr_all(&mut [e1, e2].iter().copied(), main_loop_id),
+        | ExprKind::Index(e1, e2) => never_loop_expr_all(&mut [e1, e2].iter().copied(), ignore_ids, main_loop_id),
         ExprKind::Loop(b, _, _, _) => {
             // Break can come from the inner loop so remove them.
-            absorb_break(never_loop_block(b, main_loop_id))
+            absorb_break(never_loop_block(b, ignore_ids, main_loop_id))
         },
         ExprKind::If(e, e2, 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_or(NeverLoopResult::Otherwise, |e| never_loop_expr(e, main_loop_id));
+            let e1 = never_loop_expr(e, ignore_ids, main_loop_id);
+            let e2 = never_loop_expr(e2, ignore_ids, main_loop_id);
+            let e3 = e3.as_ref().map_or(NeverLoopResult::Otherwise, |e| {
+                never_loop_expr(e, ignore_ids, main_loop_id)
+            });
             combine_seq(e1, combine_branches(e2, e3))
         },
         ExprKind::Match(e, arms, _) => {
-            let e = never_loop_expr(e, main_loop_id);
+            let e = never_loop_expr(e, ignore_ids, 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);
+                let arms = never_loop_expr_branch(&mut arms.iter().map(|a| a.body), ignore_ids, main_loop_id);
                 combine_seq(e, arms)
             }
         },
-        ExprKind::Block(b, None) => never_loop_block(b, main_loop_id),
-        ExprKind::Block(b, Some(_label)) => absorb_break(never_loop_block(b, main_loop_id)),
+        ExprKind::Block(b, l) => {
+            if let Some(_) = l {
+                ignore_ids.push(b.hir_id);
+            }
+            let ret = never_loop_block(b, ignore_ids, main_loop_id);
+            ignore_ids.pop();
+            ret
+        },
         ExprKind::Continue(d) => {
             let id = d
                 .target_id
@@ -181,20 +187,31 @@ fn never_loop_expr(expr: &Expr<'_>, main_loop_id: HirId) -> NeverLoopResult {
                 NeverLoopResult::AlwaysBreak
             }
         },
+        ExprKind::Break(Destination { target_id: Ok(t), .. }, e) if ignore_ids.contains(&t) => e
+            .map_or(NeverLoopResult::Otherwise, |e| {
+                combine_seq(never_loop_expr(e, ignore_ids, main_loop_id), NeverLoopResult::Otherwise)
+            }),
         ExprKind::Break(_, e) | ExprKind::Ret(e) => e.as_ref().map_or(NeverLoopResult::AlwaysBreak, |e| {
-            combine_seq(never_loop_expr(e, main_loop_id), NeverLoopResult::AlwaysBreak)
+            combine_seq(
+                never_loop_expr(e, ignore_ids, main_loop_id),
+                NeverLoopResult::AlwaysBreak,
+            )
         }),
         ExprKind::InlineAsm(asm) => asm
             .operands
             .iter()
             .map(|(o, _)| match o {
                 InlineAsmOperand::In { expr, .. } | InlineAsmOperand::InOut { expr, .. } => {
-                    never_loop_expr(expr, main_loop_id)
+                    never_loop_expr(expr, ignore_ids, main_loop_id)
                 },
-                InlineAsmOperand::Out { expr, .. } => never_loop_expr_all(&mut expr.iter().copied(), main_loop_id),
-                InlineAsmOperand::SplitInOut { in_expr, out_expr, .. } => {
-                    never_loop_expr_all(&mut once(*in_expr).chain(out_expr.iter().copied()), main_loop_id)
+                InlineAsmOperand::Out { expr, .. } => {
+                    never_loop_expr_all(&mut expr.iter().copied(), ignore_ids, main_loop_id)
                 },
+                InlineAsmOperand::SplitInOut { in_expr, out_expr, .. } => never_loop_expr_all(
+                    &mut once(*in_expr).chain(out_expr.iter().copied()),
+                    ignore_ids,
+                    main_loop_id,
+                ),
                 InlineAsmOperand::Const { .. }
                 | InlineAsmOperand::SymFn { .. }
                 | InlineAsmOperand::SymStatic { .. } => NeverLoopResult::Otherwise,
@@ -209,13 +226,21 @@ fn never_loop_expr(expr: &Expr<'_>, main_loop_id: HirId) -> NeverLoopResult {
     }
 }
 
-fn never_loop_expr_all<'a, T: Iterator<Item = &'a Expr<'a>>>(es: &mut T, main_loop_id: HirId) -> NeverLoopResult {
-    es.map(|e| never_loop_expr(e, main_loop_id))
+fn never_loop_expr_all<'a, T: Iterator<Item = &'a Expr<'a>>>(
+    es: &mut T,
+    ignore_ids: &mut Vec<HirId>,
+    main_loop_id: HirId,
+) -> NeverLoopResult {
+    es.map(|e| never_loop_expr(e, ignore_ids, main_loop_id))
         .fold(NeverLoopResult::Otherwise, combine_both)
 }
 
-fn never_loop_expr_branch<'a, T: Iterator<Item = &'a Expr<'a>>>(e: &mut T, main_loop_id: HirId) -> NeverLoopResult {
-    e.map(|e| never_loop_expr(e, main_loop_id))
+fn never_loop_expr_branch<'a, T: Iterator<Item = &'a Expr<'a>>>(
+    e: &mut T,
+    ignore_ids: &mut Vec<HirId>,
+    main_loop_id: HirId,
+) -> NeverLoopResult {
+    e.map(|e| never_loop_expr(e, ignore_ids, main_loop_id))
         .fold(NeverLoopResult::AlwaysBreak, combine_branches)
 }
 
diff --git a/tests/ui/never_loop.rs b/tests/ui/never_loop.rs
index 86a5d03f765..28e8f459d44 100644
--- a/tests/ui/never_loop.rs
+++ b/tests/ui/never_loop.rs
@@ -234,13 +234,22 @@ pub fn test19() {
     fn thing(iter: impl Iterator) {
         for _ in iter {
             'b: {
-                // error goes away if we just have the block's value be ().
                 break 'b;
             }
         }
     }
 }
 
+pub fn test20() {
+    'a: loop {
+        'b: {
+            break 'b 'c: {
+                break 'a;
+            };
+        }
+    }
+}
+
 fn main() {
     test1();
     test2();