[rustc.git] / src / tools / clippy / clippy_lints / src / infinite_iter.rs

use clippy_utils::diagnostics::span_lint;
use clippy_utils::ty::{implements_trait, is_type_diagnostic_item};
use clippy_utils::{get_trait_def_id, higher, is_qpath_def_path, paths};
use rustc_hir::{BorrowKind, Expr, ExprKind};
use rustc_lint::{LateContext, LateLintPass};
use rustc_session::{declare_lint_pass, declare_tool_lint};
use rustc_span::symbol::{sym, Symbol};

declare_clippy_lint! {
    /// ### What it does
    /// Checks for iteration that is guaranteed to be infinite.
    ///
    /// ### Why is this bad?
    /// While there may be places where this is acceptable
    /// (e.g., in event streams), in most cases this is simply an error.
    ///
    /// ### Example
    /// ```no_run
    /// use std::iter;
    ///
    /// iter::repeat(1_u8).collect::<Vec<_>>();
    /// ```
    #[clippy::version = "pre 1.29.0"]
    pub INFINITE_ITER,
    correctness,
    "infinite iteration"
}

declare_clippy_lint! {
    /// ### What it does
    /// Checks for iteration that may be infinite.
    ///
    /// ### Why is this bad?
    /// While there may be places where this is acceptable
    /// (e.g., in event streams), in most cases this is simply an error.
    ///
    /// ### Known problems
    /// The code may have a condition to stop iteration, but
    /// this lint is not clever enough to analyze it.
    ///
    /// ### Example
    /// ```rust
    /// let infinite_iter = 0..;
    /// [0..].iter().zip(infinite_iter.take_while(|x| *x > 5));
    /// ```
    #[clippy::version = "pre 1.29.0"]
    pub MAYBE_INFINITE_ITER,
    pedantic,
    "possible infinite iteration"
}

declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]);

impl<'tcx> LateLintPass<'tcx> for InfiniteIter {
    fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
        let (lint, msg) = match complete_infinite_iter(cx, expr) {
            Infinite => (INFINITE_ITER, "infinite iteration detected"),
            MaybeInfinite => (MAYBE_INFINITE_ITER, "possible infinite iteration detected"),
            Finite => {
                return;
            },
        };
        span_lint(cx, lint, expr.span, msg);
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
enum Finiteness {
    Infinite,
    MaybeInfinite,
    Finite,
}

use self::Finiteness::{Finite, Infinite, MaybeInfinite};

impl Finiteness {
    #[must_use]
    fn and(self, b: Self) -> Self {
        match (self, b) {
            (Finite, _) | (_, Finite) => Finite,
            (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
            _ => Infinite,
        }
    }

    #[must_use]
    fn or(self, b: Self) -> Self {
        match (self, b) {
            (Infinite, _) | (_, Infinite) => Infinite,
            (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
            _ => Finite,
        }
    }
}

impl From<bool> for Finiteness {
    #[must_use]
    fn from(b: bool) -> Self {
        if b { Infinite } else { Finite }
    }
}

/// This tells us what to look for to know if the iterator returned by
/// this method is infinite
#[derive(Copy, Clone)]
enum Heuristic {
    /// infinite no matter what
    Always,
    /// infinite if the first argument is
    First,
    /// infinite if any of the supplied arguments is
    Any,
    /// infinite if all of the supplied arguments are
    All,
}

use self::Heuristic::{All, Always, Any, First};

/// a slice of (method name, number of args, heuristic, bounds) tuples
/// that will be used to determine whether the method in question
/// returns an infinite or possibly infinite iterator. The finiteness
/// is an upper bound, e.g., some methods can return a possibly
/// infinite iterator at worst, e.g., `take_while`.
const HEURISTICS: [(&str, usize, Heuristic, Finiteness); 19] = [
    ("zip", 2, All, Infinite),
    ("chain", 2, Any, Infinite),
    ("cycle", 1, Always, Infinite),
    ("map", 2, First, Infinite),
    ("by_ref", 1, First, Infinite),
    ("cloned", 1, First, Infinite),
    ("rev", 1, First, Infinite),
    ("inspect", 1, First, Infinite),
    ("enumerate", 1, First, Infinite),
    ("peekable", 2, First, Infinite),
    ("fuse", 1, First, Infinite),
    ("skip", 2, First, Infinite),
    ("skip_while", 1, First, Infinite),
    ("filter", 2, First, Infinite),
    ("filter_map", 2, First, Infinite),
    ("flat_map", 2, First, Infinite),
    ("unzip", 1, First, Infinite),
    ("take_while", 2, First, MaybeInfinite),
    ("scan", 3, First, MaybeInfinite),
];

fn is_infinite(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
    match expr.kind {
        ExprKind::MethodCall(method, _, args, _) => {
            for &(name, len, heuristic, cap) in &HEURISTICS {
                if method.ident.name.as_str() == name && args.len() == len {
                    return (match heuristic {
                        Always => Infinite,
                        First => is_infinite(cx, &args[0]),
                        Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
                        All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
                    })
                    .and(cap);
                }
            }
            if method.ident.name == sym!(flat_map) && args.len() == 2 {
                if let ExprKind::Closure(_, _, body_id, _, _) = args[1].kind {
                    let body = cx.tcx.hir().body(body_id);
                    return is_infinite(cx, &body.value);
                }
            }
            Finite
        },
        ExprKind::Block(block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
        ExprKind::Box(e) | ExprKind::AddrOf(BorrowKind::Ref, _, e) => is_infinite(cx, e),
        ExprKind::Call(path, _) => {
            if let ExprKind::Path(ref qpath) = path.kind {
                is_qpath_def_path(cx, qpath, path.hir_id, &paths::ITER_REPEAT).into()
            } else {
                Finite
            }
        },
        ExprKind::Struct(..) => higher::Range::hir(expr).map_or(false, |r| r.end.is_none()).into(),
        _ => Finite,
    }
}

/// the names and argument lengths of methods that *may* exhaust their
/// iterators
const POSSIBLY_COMPLETING_METHODS: [(&str, usize); 6] = [
    ("find", 2),
    ("rfind", 2),
    ("position", 2),
    ("rposition", 2),
    ("any", 2),
    ("all", 2),
];

/// the names and argument lengths of methods that *always* exhaust
/// their iterators
const COMPLETING_METHODS: [(&str, usize); 12] = [
    ("count", 1),
    ("fold", 3),
    ("for_each", 2),
    ("partition", 2),
    ("max", 1),
    ("max_by", 2),
    ("max_by_key", 2),
    ("min", 1),
    ("min_by", 2),
    ("min_by_key", 2),
    ("sum", 1),
    ("product", 1),
];

/// the paths of types that are known to be infinitely allocating
const INFINITE_COLLECTORS: &[Symbol] = &[
    sym::BinaryHeap,
    sym::BTreeMap,
    sym::BTreeSet,
    sym::HashMap,
    sym::HashSet,
    sym::LinkedList,
    sym::Vec,
    sym::VecDeque,
];

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