clippy_lints/src/infinite_iter.rs

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