1 use clippy_utils::diagnostics::span_lint_and_then;
2 use clippy_utils::sugg::Sugg;
3 use clippy_utils::ty::is_type_diagnostic_item;
4 use clippy_utils::{get_enclosing_block, is_expr_path_def_path, path_to_local, path_to_local_id, paths, SpanlessEq};
5 use if_chain::if_chain;
6 use rustc_ast::ast::LitKind;
7 use rustc_errors::Applicability;
8 use rustc_hir::intravisit::{walk_block, walk_expr, walk_stmt, Visitor};
9 use rustc_hir::{BindingAnnotation, Block, Expr, ExprKind, HirId, PatKind, QPath, Stmt, StmtKind};
10 use rustc_lint::{LateContext, LateLintPass};
11 use rustc_session::{declare_lint_pass, declare_tool_lint};
12 use rustc_span::symbol::sym;
14 declare_clippy_lint! {
16 /// Checks slow zero-filled vector initialization
18 /// ### Why is this bad?
19 /// These structures are non-idiomatic and less efficient than simply using
24 /// # use core::iter::repeat;
26 /// let mut vec1 = Vec::with_capacity(len);
27 /// vec1.resize(len, 0);
29 /// let mut vec1 = Vec::with_capacity(len);
30 /// vec1.resize(vec1.capacity(), 0);
32 /// let mut vec2 = Vec::with_capacity(len);
33 /// vec2.extend(repeat(0).take(len));
39 /// let mut vec1 = vec![0; len];
40 /// let mut vec2 = vec![0; len];
42 #[clippy::version = "1.32.0"]
43 pub SLOW_VECTOR_INITIALIZATION,
45 "slow vector initialization"
48 declare_lint_pass!(SlowVectorInit => [SLOW_VECTOR_INITIALIZATION]);
50 /// `VecAllocation` contains data regarding a vector allocated with `with_capacity` and then
51 /// assigned to a variable. For example, `let mut vec = Vec::with_capacity(0)` or
52 /// `vec = Vec::with_capacity(0)`
53 struct VecAllocation<'tcx> {
54 /// HirId of the variable
57 /// Reference to the expression which allocates the vector
58 allocation_expr: &'tcx Expr<'tcx>,
60 /// Reference to the expression used as argument on `with_capacity` call. This is used
61 /// to only match slow zero-filling idioms of the same length than vector initialization.
62 len_expr: &'tcx Expr<'tcx>,
65 /// Type of slow initialization
66 enum InitializationType<'tcx> {
67 /// Extend is a slow initialization with the form `vec.extend(repeat(0).take(..))`
68 Extend(&'tcx Expr<'tcx>),
70 /// Resize is a slow initialization with the form `vec.resize(.., 0)`
71 Resize(&'tcx Expr<'tcx>),
74 impl<'tcx> LateLintPass<'tcx> for SlowVectorInit {
75 fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
76 // Matches initialization on reassignements. For example: `vec = Vec::with_capacity(100)`
78 if let ExprKind::Assign(left, right, _) = expr.kind;
81 if let Some(local_id) = path_to_local(left);
83 // Extract len argument
84 if let Some(len_arg) = Self::is_vec_with_capacity(cx, right);
87 let vi = VecAllocation {
89 allocation_expr: right,
93 Self::search_initialization(cx, vi, expr.hir_id);
98 fn check_stmt(&mut self, cx: &LateContext<'tcx>, stmt: &'tcx Stmt<'_>) {
99 // Matches statements which initializes vectors. For example: `let mut vec = Vec::with_capacity(10)`
101 if let StmtKind::Local(local) = stmt.kind;
102 if let PatKind::Binding(BindingAnnotation::MUT, local_id, _, None) = local.pat.kind;
103 if let Some(init) = local.init;
104 if let Some(len_arg) = Self::is_vec_with_capacity(cx, init);
107 let vi = VecAllocation {
109 allocation_expr: init,
113 Self::search_initialization(cx, vi, stmt.hir_id);
119 impl SlowVectorInit {
120 /// Checks if the given expression is `Vec::with_capacity(..)`. It will return the expression
121 /// of the first argument of `with_capacity` call if it matches or `None` if it does not.
122 fn is_vec_with_capacity<'tcx>(cx: &LateContext<'_>, expr: &Expr<'tcx>) -> Option<&'tcx Expr<'tcx>> {
124 if let ExprKind::Call(func, [arg]) = expr.kind;
125 if let ExprKind::Path(QPath::TypeRelative(ty, name)) = func.kind;
126 if name.ident.as_str() == "with_capacity";
127 if is_type_diagnostic_item(cx, cx.typeck_results().node_type(ty.hir_id), sym::Vec);
136 /// Search initialization for the given vector
137 fn search_initialization<'tcx>(cx: &LateContext<'tcx>, vec_alloc: VecAllocation<'tcx>, parent_node: HirId) {
138 let enclosing_body = get_enclosing_block(cx, parent_node);
140 if enclosing_body.is_none() {
144 let mut v = VectorInitializationVisitor {
147 slow_expression: None,
148 initialization_found: false,
151 v.visit_block(enclosing_body.unwrap());
153 if let Some(ref allocation_expr) = v.slow_expression {
154 Self::lint_initialization(cx, allocation_expr, &v.vec_alloc);
158 fn lint_initialization<'tcx>(
159 cx: &LateContext<'tcx>,
160 initialization: &InitializationType<'tcx>,
161 vec_alloc: &VecAllocation<'_>,
163 match initialization {
164 InitializationType::Extend(e) | InitializationType::Resize(e) => {
165 Self::emit_lint(cx, e, vec_alloc, "slow zero-filling initialization");
170 fn emit_lint<'tcx>(cx: &LateContext<'tcx>, slow_fill: &Expr<'_>, vec_alloc: &VecAllocation<'_>, msg: &str) {
171 let len_expr = Sugg::hir(cx, vec_alloc.len_expr, "len");
173 span_lint_and_then(cx, SLOW_VECTOR_INITIALIZATION, slow_fill.span, msg, |diag| {
174 diag.span_suggestion(
175 vec_alloc.allocation_expr.span,
176 "consider replace allocation with",
177 format!("vec![0; {}]", len_expr),
178 Applicability::Unspecified,
184 /// `VectorInitializationVisitor` searches for unsafe or slow vector initializations for the given
186 struct VectorInitializationVisitor<'a, 'tcx> {
187 cx: &'a LateContext<'tcx>,
189 /// Contains the information.
190 vec_alloc: VecAllocation<'tcx>,
192 /// Contains the slow initialization expression, if one was found.
193 slow_expression: Option<InitializationType<'tcx>>,
195 /// `true` if the initialization of the vector has been found on the visited block.
196 initialization_found: bool,
199 impl<'a, 'tcx> VectorInitializationVisitor<'a, 'tcx> {
200 /// Checks if the given expression is extending a vector with `repeat(0).take(..)`
201 fn search_slow_extend_filling(&mut self, expr: &'tcx Expr<'_>) {
203 if self.initialization_found;
204 if let ExprKind::MethodCall(path, self_arg, [extend_arg], _) = expr.kind;
205 if path_to_local_id(self_arg, self.vec_alloc.local_id);
206 if path.ident.name == sym!(extend);
207 if self.is_repeat_take(extend_arg);
210 self.slow_expression = Some(InitializationType::Extend(expr));
215 /// Checks if the given expression is resizing a vector with 0
216 fn search_slow_resize_filling(&mut self, expr: &'tcx Expr<'_>) {
217 if self.initialization_found
218 && let ExprKind::MethodCall(path, self_arg, [len_arg, fill_arg], _) = expr.kind
219 && path_to_local_id(self_arg, self.vec_alloc.local_id)
220 && path.ident.name == sym!(resize)
221 // Check that is filled with 0
222 && let ExprKind::Lit(ref lit) = fill_arg.kind
223 && let LitKind::Int(0, _) = lit.node {
224 // Check that len expression is equals to `with_capacity` expression
225 if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr) {
226 self.slow_expression = Some(InitializationType::Resize(expr));
227 } else if let ExprKind::MethodCall(path, ..) = len_arg.kind && path.ident.as_str() == "capacity" {
228 self.slow_expression = Some(InitializationType::Resize(expr));
233 /// Returns `true` if give expression is `repeat(0).take(...)`
234 fn is_repeat_take(&self, expr: &Expr<'_>) -> bool {
236 if let ExprKind::MethodCall(take_path, recv, [len_arg, ..], _) = expr.kind;
237 if take_path.ident.name == sym!(take);
238 // Check that take is applied to `repeat(0)`
239 if self.is_repeat_zero(recv);
241 // Check that len expression is equals to `with_capacity` expression
242 if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr) {
244 } else if let ExprKind::MethodCall(path, ..) = len_arg.kind && path.ident.as_str() == "capacity" {
253 /// Returns `true` if given expression is `repeat(0)`
254 fn is_repeat_zero(&self, expr: &Expr<'_>) -> bool {
256 if let ExprKind::Call(fn_expr, [repeat_arg]) = expr.kind;
257 if is_expr_path_def_path(self.cx, fn_expr, &paths::ITER_REPEAT);
258 if let ExprKind::Lit(ref lit) = repeat_arg.kind;
259 if let LitKind::Int(0, _) = lit.node;
270 impl<'a, 'tcx> Visitor<'tcx> for VectorInitializationVisitor<'a, 'tcx> {
271 fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
272 if self.initialization_found {
274 StmtKind::Expr(expr) | StmtKind::Semi(expr) => {
275 self.search_slow_extend_filling(expr);
276 self.search_slow_resize_filling(expr);
281 self.initialization_found = false;
283 walk_stmt(self, stmt);
287 fn visit_block(&mut self, block: &'tcx Block<'_>) {
288 if self.initialization_found {
289 if let Some(s) = block.stmts.get(0) {
293 self.initialization_found = false;
295 walk_block(self, block);
299 fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
300 // Skip all the expressions previous to the vector initialization
301 if self.vec_alloc.allocation_expr.hir_id == expr.hir_id {
302 self.initialization_found = true;
305 walk_expr(self, expr);