clippy_lints/src/infinite_iter.rs

   1 use rustc::hir::*;
   2 use rustc::lint::*;
   3 use crate::utils::{get_trait_def_id, higher, implements_trait, match_qpath, paths, span_lint};
   4
   5 /// **What it does:** Checks for iteration that is guaranteed to be infinite.
   6 ///
   7 /// **Why is this bad?** While there may be places where this is acceptable
   8 /// (e.g. in event streams), in most cases this is simply an error.
   9 ///
  10 /// **Known problems:** None.
  11 ///
  12 /// **Example:**
  13 /// ```rust
  14 /// repeat(1_u8).iter().collect::<Vec<_>>()
  15 /// ```
  16 declare_clippy_lint! {
  17     pub INFINITE_ITER,
  18     correctness,
  19     "infinite iteration"
  20 }
  21
  22 /// **What it does:** Checks for iteration that may be infinite.
  23 ///
  24 /// **Why is this bad?** While there may be places where this is acceptable
  25 /// (e.g. in event streams), in most cases this is simply an error.
  26 ///
  27 /// **Known problems:** The code may have a condition to stop iteration, but
  28 /// this lint is not clever enough to analyze it.
  29 ///
  30 /// **Example:**
  31 /// ```rust
  32 /// [0..].iter().zip(infinite_iter.take_while(|x| x > 5))
  33 /// ```
  34 declare_clippy_lint! {
  35     pub MAYBE_INFINITE_ITER,
  36     pedantic,
  37     "possible infinite iteration"
  38 }
  39
  40 #[derive(Copy, Clone)]
  41 pub struct Pass;
  42
  43 impl LintPass for Pass {
  44     fn get_lints(&self) -> LintArray {
  45         lint_array!(INFINITE_ITER, MAYBE_INFINITE_ITER)
  46     }
  47 }
  48
  49 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
  50     fn check_expr(&mut self, cx: &LateContext<'a, '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     fn and(self, b: Self) -> Self {
  73         match (self, b) {
  74             (Finite, _) | (_, Finite) => Finite,
  75             (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
  76             _ => Infinite,
  77         }
  78     }
  79
  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     fn from(b: bool) -> Self {
  91         if b {
  92             Infinite
  93         } else {
  94             Finite
  95         }
  96     }
  97 }
  98
  99 /// This tells us what to look for to know if the iterator returned by
 100 /// this method is infinite
 101 #[derive(Copy, Clone)]
 102 enum Heuristic {
 103     /// infinite no matter what
 104     Always,
 105     /// infinite if the first argument is
 106     First,
 107     /// infinite if any of the supplied arguments is
 108     Any,
 109     /// infinite if all of the supplied arguments are
 110     All,
 111 }
 112
 113 use self::Heuristic::{All, Always, Any, First};
 114
 115 /// a slice of (method name, number of args, heuristic, bounds) tuples
 116 /// that will be used to determine whether the method in question
 117 /// returns an infinite or possibly infinite iterator. The finiteness
 118 /// is an upper bound, e.g. some methods can return a possibly
 119 /// infinite iterator at worst, e.g. `take_while`.
 120 static HEURISTICS: &[(&str, usize, Heuristic, Finiteness)] = &[
 121     ("zip", 2, All, Infinite),
 122     ("chain", 2, Any, Infinite),
 123     ("cycle", 1, Always, Infinite),
 124     ("map", 2, First, Infinite),
 125     ("by_ref", 1, First, Infinite),
 126     ("cloned", 1, First, Infinite),
 127     ("rev", 1, First, Infinite),
 128     ("inspect", 1, First, Infinite),
 129     ("enumerate", 1, First, Infinite),
 130     ("peekable", 2, First, Infinite),
 131     ("fuse", 1, First, Infinite),
 132     ("skip", 2, First, Infinite),
 133     ("skip_while", 1, First, Infinite),
 134     ("filter", 2, First, Infinite),
 135     ("filter_map", 2, First, Infinite),
 136     ("flat_map", 2, First, Infinite),
 137     ("unzip", 1, First, Infinite),
 138     ("take_while", 2, First, MaybeInfinite),
 139     ("scan", 3, First, MaybeInfinite),
 140 ];
 141
 142 fn is_infinite(cx: &LateContext, expr: &Expr) -> Finiteness {
 143     match expr.node {
 144         ExprMethodCall(ref method, _, ref args) => {
 145             for &(name, len, heuristic, cap) in HEURISTICS.iter() {
 146                 if method.name == name && args.len() == len {
 147                     return (match heuristic {
 148                         Always => Infinite,
 149                         First => is_infinite(cx, &args[0]),
 150                         Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
 151                         All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
 152                     }).and(cap);
 153                 }
 154             }
 155             if method.name == "flat_map" && args.len() == 2 {
 156                 if let ExprClosure(_, _, body_id, _, _) = args[1].node {
 157                     let body = cx.tcx.hir.body(body_id);
 158                     return is_infinite(cx, &body.value);
 159                 }
 160             }
 161             Finite
 162         },
 163         ExprBlock(ref block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
 164         ExprBox(ref e) | ExprAddrOf(_, ref e) => is_infinite(cx, e),
 165         ExprCall(ref path, _) => if let ExprPath(ref qpath) = path.node {
 166             match_qpath(qpath, &paths::REPEAT).into()
 167         } else {
 168             Finite
 169         },
 170         ExprStruct(..) => higher::range(cx, expr)
 171             .map_or(false, |r| r.end.is_none())
 172             .into(),
 173         _ => Finite,
 174     }
 175 }
 176
 177 /// the names and argument lengths of methods that *may* exhaust their
 178 /// iterators
 179 static POSSIBLY_COMPLETING_METHODS: &[(&str, usize)] = &[
 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 static COMPLETING_METHODS: &[(&str, usize)] = &[
 191     ("count", 1),
 192     ("collect", 1),
 193     ("fold", 3),
 194     ("for_each", 2),
 195     ("partition", 2),
 196     ("max", 1),
 197     ("max_by", 2),
 198     ("max_by_key", 2),
 199     ("min", 1),
 200     ("min_by", 2),
 201     ("min_by_key", 2),
 202     ("sum", 1),
 203     ("product", 1),
 204 ];
 205
 206 fn complete_infinite_iter(cx: &LateContext, expr: &Expr) -> Finiteness {
 207     match expr.node {
 208         ExprMethodCall(ref method, _, ref args) => {
 209             for &(name, len) in COMPLETING_METHODS.iter() {
 210                 if method.name == name && args.len() == len {
 211                     return is_infinite(cx, &args[0]);
 212                 }
 213             }
 214             for &(name, len) in POSSIBLY_COMPLETING_METHODS.iter() {
 215                 if method.name == name && args.len() == len {
 216                     return MaybeInfinite.and(is_infinite(cx, &args[0]));
 217                 }
 218             }
 219             if method.name == "last" && args.len() == 1 {
 220                 let not_double_ended = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR)
 221                     .map_or(false, |id| !implements_trait(cx, cx.tables.expr_ty(&args[0]), id, &[]));
 222                 if not_double_ended {
 223                     return is_infinite(cx, &args[0]);
 224                 }
 225             }
 226         },
 227         ExprBinary(op, ref l, ref r) => if op.node.is_comparison() {
 228             return is_infinite(cx, l)
 229                 .and(is_infinite(cx, r))
 230                 .and(MaybeInfinite);
 231         }, // TODO: ExprLoop + Match
 232         _ => (),
 233     }
 234     Finite
 235 }