clippy_lints/src/infinite_iter.rs

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