clippy_lints/src/infinite_iter.rs

   1 use rustc::hir::*;
   2 use rustc::lint::*;
   3 use utils::{get_trait_def_id, implements_trait, higher, 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_lint! {
  17     pub INFINITE_ITER,
  18     Warn,
  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_lint! {
  35     pub MAYBE_INFINITE_ITER,
  36     Allow,
  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::{Infinite, MaybeInfinite, Finite};
  70
  71 impl Finiteness {
  72     fn and(self, b: Self) -> Self {
  73         match (self, b) {
  74             (Finite, _) | (_, Finite) => Finite,
  75             (MaybeInfinite, _) |
  76             (_, MaybeInfinite) => MaybeInfinite,
  77             _ => Infinite,
  78         }
  79     }
  80
  81     fn or(self, b: Self) -> Self {
  82         match (self, b) {
  83             (Infinite, _) | (_, Infinite) => Infinite,
  84             (MaybeInfinite, _) |
  85             (_, MaybeInfinite) => MaybeInfinite,
  86             _ => Finite,
  87         }
  88     }
  89 }
  90
  91 impl From<bool> for Finiteness {
  92     fn from(b: bool) -> Self {
  93         if b { Infinite } else { Finite }
  94     }
  95 }
  96
  97 /// This tells us what to look for to know if the iterator returned by
  98 /// this method is infinite
  99 #[derive(Copy, Clone)]
 100 enum Heuristic {
 101     /// infinite no matter what
 102     Always,
 103     /// infinite if the first argument is
 104     First,
 105     /// infinite if any of the supplied arguments is
 106     Any,
 107     /// infinite if all of the supplied arguments are
 108     All,
 109 }
 110
 111 use self::Heuristic::{Always, First, Any, All};
 112
 113 /// a slice of (method name, number of args, heuristic, bounds) tuples
 114 /// that will be used to determine whether the method in question
 115 /// returns an infinite or possibly infinite iterator. The finiteness
 116 /// is an upper bound, e.g. some methods can return a possibly
 117 /// infinite iterator at worst, e.g. `take_while`.
 118 static HEURISTICS: &[(&str, usize, Heuristic, Finiteness)] = &[
 119     ("zip", 2, All, Infinite),
 120     ("chain", 2, Any, Infinite),
 121     ("cycle", 1, Always, Infinite),
 122     ("map", 2, First, Infinite),
 123     ("by_ref", 1, First, Infinite),
 124     ("cloned", 1, First, Infinite),
 125     ("rev", 1, First, Infinite),
 126     ("inspect", 1, First, Infinite),
 127     ("enumerate", 1, First, Infinite),
 128     ("peekable", 2, First, Infinite),
 129     ("fuse", 1, First, Infinite),
 130     ("skip", 2, First, Infinite),
 131     ("skip_while", 1, First, Infinite),
 132     ("filter", 2, First, Infinite),
 133     ("filter_map", 2, First, Infinite),
 134     ("flat_map", 2, First, Infinite),
 135     ("unzip", 1, First, Infinite),
 136     ("take_while", 2, First, MaybeInfinite),
 137     ("scan", 3, First, MaybeInfinite),
 138 ];
 139
 140 fn is_infinite(cx: &LateContext, expr: &Expr) -> Finiteness {
 141     match expr.node {
 142         ExprMethodCall(ref method, _, ref args) => {
 143             for &(name, len, heuristic, cap) in HEURISTICS.iter() {
 144                 if method.name == name && args.len() == len {
 145                     return (match heuristic {
 146                                 Always => Infinite,
 147                                 First => is_infinite(cx, &args[0]),
 148                                 Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
 149                                 All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
 150                             }).and(cap);
 151                 }
 152             }
 153             if method.name == "flat_map" && args.len() == 2 {
 154                 if let ExprClosure(_, _, body_id, _, _) = args[1].node {
 155                     let body = cx.tcx.hir.body(body_id);
 156                     return is_infinite(cx, &body.value);
 157                 }
 158             }
 159             Finite
 160         },
 161         ExprBlock(ref block) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
 162         ExprBox(ref e) |
 163         ExprAddrOf(_, ref e) => is_infinite(cx, e),
 164         ExprCall(ref path, _) => {
 165             if let ExprPath(ref qpath) = path.node {
 166                 match_qpath(qpath, &paths::REPEAT).into()
 167             } else {
 168                 Finite
 169             }
 170         },
 171         ExprStruct(..) => {
 172             higher::range(expr)
 173                 .map_or(false, |r| r.end.is_none())
 174                 .into()
 175         },
 176         _ => Finite,
 177     }
 178 }
 179
 180 /// the names and argument lengths of methods that *may* exhaust their
 181 /// iterators
 182 static POSSIBLY_COMPLETING_METHODS: &[(&str, usize)] = &[
 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 static COMPLETING_METHODS: &[(&str, usize)] = &[
 194     ("count", 1),
 195     ("collect", 1),
 196     ("fold", 3),
 197     ("for_each", 2),
 198     ("partition", 2),
 199     ("max", 1),
 200     ("max_by", 2),
 201     ("max_by_key", 2),
 202     ("min", 1),
 203     ("min_by", 2),
 204     ("min_by_key", 2),
 205     ("sum", 1),
 206     ("product", 1),
 207 ];
 208
 209 fn complete_infinite_iter(cx: &LateContext, expr: &Expr) -> Finiteness {
 210     match expr.node {
 211         ExprMethodCall(ref method, _, ref args) => {
 212             for &(name, len) in COMPLETING_METHODS.iter() {
 213                 if method.name == name && args.len() == len {
 214                     return is_infinite(cx, &args[0]);
 215                 }
 216             }
 217             for &(name, len) in POSSIBLY_COMPLETING_METHODS.iter() {
 218                 if method.name == name && args.len() == len {
 219                     return MaybeInfinite.and(is_infinite(cx, &args[0]));
 220                 }
 221             }
 222             if method.name == "last" && args.len() == 1 &&
 223                 get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR).map_or(
 224                     false,
 225                     |id| {
 226                         !implements_trait(cx, cx.tables.expr_ty(&args[0]), id, &[])
 227                     },
 228                 )
 229             {
 230                 return is_infinite(cx, &args[0]);
 231             }
 232         },
 233         ExprBinary(op, ref l, ref r) => {
 234             if op.node.is_comparison() {
 235                 return is_infinite(cx, l).and(is_infinite(cx, r)).and(
 236                     MaybeInfinite,
 237                 );
 238             }
 239         }, //TODO: ExprLoop + Match
 240         _ => (),
 241     }
 242     Finite
 243 }