clippy_lints/src/infinite_iter.rs

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