clippy_lints/src/infinite_iter.rs

   1 use clippy_utils::diagnostics::span_lint;
   2 use clippy_utils::ty::{implements_trait, is_type_diagnostic_item};
   3 use clippy_utils::{get_trait_def_id, higher, is_qpath_def_path, paths};
   4 use rustc_hir::{BorrowKind, Expr, ExprKind};
   5 use rustc_lint::{LateContext, LateLintPass};
   6 use rustc_session::{declare_lint_pass, declare_tool_lint};
   7 use rustc_span::symbol::{sym, Symbol};
   8
   9 declare_clippy_lint! {
  10     /// **What it does:** Checks for iteration that is guaranteed to be infinite.
  11     ///
  12     /// **Why is this bad?** While there may be places where this is acceptable
  13     /// (e.g., in event streams), in most cases this is simply an error.
  14     ///
  15     /// **Known problems:** None.
  16     ///
  17     /// **Example:**
  18     /// ```no_run
  19     /// use std::iter;
  20     ///
  21     /// iter::repeat(1_u8).collect::<Vec<_>>();
  22     /// ```
  23     pub INFINITE_ITER,
  24     correctness,
  25     "infinite iteration"
  26 }
  27
  28 declare_clippy_lint! {
  29     /// **What it does:** Checks for iteration that may be infinite.
  30     ///
  31     /// **Why is this bad?** While there may be places where this is acceptable
  32     /// (e.g., in event streams), in most cases this is simply an error.
  33     ///
  34     /// **Known problems:** The code may have a condition to stop iteration, but
  35     /// this lint is not clever enough to analyze it.
  36     ///
  37     /// **Example:**
  38     /// ```rust
  39     /// let infinite_iter = 0..;
  40     /// [0..].iter().zip(infinite_iter.take_while(|x| *x > 5));
  41     /// ```
  42     pub MAYBE_INFINITE_ITER,
  43     pedantic,
  44     "possible infinite iteration"
  45 }
  46
  47 declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]);
  48
  49 impl<'tcx> LateLintPass<'tcx> for InfiniteIter {
  50     fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
  51         let (lint, msg) = match complete_infinite_iter(cx, expr) {
  52             Infinite => (INFINITE_ITER, "infinite iteration detected"),
  53             MaybeInfinite => (MAYBE_INFINITE_ITER, "possible infinite iteration detected"),
  54             Finite => {
  55                 return;
  56             },
  57         };
  58         span_lint(cx, lint, expr.span, msg);
  59     }
  60 }
  61
  62 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  63 enum Finiteness {
  64     Infinite,
  65     MaybeInfinite,
  66     Finite,
  67 }
  68
  69 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
  70
  71 impl Finiteness {
  72     #[must_use]
  73     fn and(self, b: Self) -> Self {
  74         match (self, b) {
  75             (Finite, _) | (_, Finite) => Finite,
  76             (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
  77             _ => Infinite,
  78         }
  79     }
  80
  81     #[must_use]
  82     fn or(self, b: Self) -> Self {
  83         match (self, b) {
  84             (Infinite, _) | (_, Infinite) => Infinite,
  85             (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
  86             _ => Finite,
  87         }
  88     }
  89 }
  90
  91 impl From<bool> for Finiteness {
  92     #[must_use]
  93     fn from(b: bool) -> Self {
  94         if b { Infinite } else { Finite }
  95     }
  96 }
  97
  98 /// This tells us what to look for to know if the iterator returned by
  99 /// this method is infinite
 100 #[derive(Copy, Clone)]
 101 enum Heuristic {
 102     /// infinite no matter what
 103     Always,
 104     /// infinite if the first argument is
 105     First,
 106     /// infinite if any of the supplied arguments is
 107     Any,
 108     /// infinite if all of the supplied arguments are
 109     All,
 110 }
 111
 112 use self::Heuristic::{All, Always, Any, First};
 113
 114 /// a slice of (method name, number of args, heuristic, bounds) tuples
 115 /// that will be used to determine whether the method in question
 116 /// returns an infinite or possibly infinite iterator. The finiteness
 117 /// is an upper bound, e.g., some methods can return a possibly
 118 /// infinite iterator at worst, e.g., `take_while`.
 119 const HEURISTICS: [(&str, usize, Heuristic, Finiteness); 19] = [
 120     ("zip", 2, All, Infinite),
 121     ("chain", 2, Any, Infinite),
 122     ("cycle", 1, Always, Infinite),
 123     ("map", 2, First, Infinite),
 124     ("by_ref", 1, First, Infinite),
 125     ("cloned", 1, First, Infinite),
 126     ("rev", 1, First, Infinite),
 127     ("inspect", 1, First, Infinite),
 128     ("enumerate", 1, First, Infinite),
 129     ("peekable", 2, First, Infinite),
 130     ("fuse", 1, First, Infinite),
 131     ("skip", 2, First, Infinite),
 132     ("skip_while", 1, First, Infinite),
 133     ("filter", 2, First, Infinite),
 134     ("filter_map", 2, First, Infinite),
 135     ("flat_map", 2, First, Infinite),
 136     ("unzip", 1, First, Infinite),
 137     ("take_while", 2, First, MaybeInfinite),
 138     ("scan", 3, First, MaybeInfinite),
 139 ];
 140
 141 fn is_infinite(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
 142     match expr.kind {
 143         ExprKind::MethodCall(method, _, args, _) => {
 144             for &(name, len, heuristic, cap) in &HEURISTICS {
 145                 if method.ident.name.as_str() == name && args.len() == len {
 146                     return (match heuristic {
 147                         Always => Infinite,
 148                         First => is_infinite(cx, &args[0]),
 149                         Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
 150                         All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
 151                     })
 152                     .and(cap);
 153                 }
 154             }
 155             if method.ident.name == sym!(flat_map) && args.len() == 2 {
 156                 if let ExprKind::Closure(_, _, body_id, _, _) = args[1].kind {
 157                     let body = cx.tcx.hir().body(body_id);
 158                     return is_infinite(cx, &body.value);
 159                 }
 160             }
 161             Finite
 162         },
 163         ExprKind::Block(block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
 164         ExprKind::Box(e) | ExprKind::AddrOf(BorrowKind::Ref, _, e) => is_infinite(cx, e),
 165         ExprKind::Call(path, _) => {
 166             if let ExprKind::Path(ref qpath) = path.kind {
 167                 is_qpath_def_path(cx, qpath, path.hir_id, &paths::ITER_REPEAT).into()
 168             } else {
 169                 Finite
 170             }
 171         },
 172         ExprKind::Struct(..) => higher::range(expr).map_or(false, |r| r.end.is_none()).into(),
 173         _ => Finite,
 174     }
 175 }
 176
 177 /// the names and argument lengths of methods that *may* exhaust their
 178 /// iterators
 179 const POSSIBLY_COMPLETING_METHODS: [(&str, usize); 6] = [
 180     ("find", 2),
 181     ("rfind", 2),
 182     ("position", 2),
 183     ("rposition", 2),
 184     ("any", 2),
 185     ("all", 2),
 186 ];
 187
 188 /// the names and argument lengths of methods that *always* exhaust
 189 /// their iterators
 190 const COMPLETING_METHODS: [(&str, usize); 12] = [
 191     ("count", 1),
 192     ("fold", 3),
 193     ("for_each", 2),
 194     ("partition", 2),
 195     ("max", 1),
 196     ("max_by", 2),
 197     ("max_by_key", 2),
 198     ("min", 1),
 199     ("min_by", 2),
 200     ("min_by_key", 2),
 201     ("sum", 1),
 202     ("product", 1),
 203 ];
 204
 205 /// the paths of types that are known to be infinitely allocating
 206 const INFINITE_COLLECTORS: &[Symbol] = &[
 207     sym::BinaryHeap,
 208     sym::BTreeMap,
 209     sym::BTreeSet,
 210     sym::hashmap_type,
 211     sym::hashset_type,
 212     sym::LinkedList,
 213     sym::vec_type,
 214     sym::vecdeque_type,
 215 ];
 216
 217 fn complete_infinite_iter(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
 218     match expr.kind {
 219         ExprKind::MethodCall(method, _, args, _) => {
 220             for &(name, len) in &COMPLETING_METHODS {
 221                 if method.ident.name.as_str() == name && args.len() == len {
 222                     return is_infinite(cx, &args[0]);
 223                 }
 224             }
 225             for &(name, len) in &POSSIBLY_COMPLETING_METHODS {
 226                 if method.ident.name.as_str() == name && args.len() == len {
 227                     return MaybeInfinite.and(is_infinite(cx, &args[0]));
 228                 }
 229             }
 230             if method.ident.name == sym!(last) && args.len() == 1 {
 231                 let not_double_ended = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR).map_or(false, |id| {
 232                     !implements_trait(cx, cx.typeck_results().expr_ty(&args[0]), id, &[])
 233                 });
 234                 if not_double_ended {
 235                     return is_infinite(cx, &args[0]);
 236                 }
 237             } else if method.ident.name == sym!(collect) {
 238                 let ty = cx.typeck_results().expr_ty(expr);
 239                 if INFINITE_COLLECTORS
 240                     .iter()
 241                     .any(|diag_item| is_type_diagnostic_item(cx, ty, *diag_item))
 242                 {
 243                     return is_infinite(cx, &args[0]);
 244                 }
 245             }
 246         },
 247         ExprKind::Binary(op, l, r) => {
 248             if op.node.is_comparison() {
 249                 return is_infinite(cx, l).and(is_infinite(cx, r)).and(MaybeInfinite);
 250             }
 251         }, // TODO: ExprKind::Loop + Match
 252         _ => (),
 253     }
 254     Finite
 255 }