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