1 use clippy_utils::diagnostics::span_lint_and_then;
2 use clippy_utils::sugg::Sugg;
3 use clippy_utils::{get_enclosing_block, match_qpath, SpanlessEq};
4 use if_chain::if_chain;
5 use rustc_ast::ast::LitKind;
6 use rustc_errors::Applicability;
7 use rustc_hir::intravisit::{walk_block, walk_expr, walk_stmt, NestedVisitorMap, Visitor};
8 use rustc_hir::{BindingAnnotation, Block, Expr, ExprKind, HirId, PatKind, QPath, Stmt, StmtKind};
9 use rustc_lint::{LateContext, LateLintPass, Lint};
10 use rustc_middle::hir::map::Map;
11 use rustc_session::{declare_lint_pass, declare_tool_lint};
12 use rustc_span::symbol::Symbol;
14 declare_clippy_lint! {
15 /// **What it does:** Checks slow zero-filled vector initialization
17 /// **Why is this bad?** These structures are non-idiomatic and less efficient than simply using
20 /// **Known problems:** None.
24 /// # use core::iter::repeat;
28 /// let mut vec1 = Vec::with_capacity(len);
29 /// vec1.resize(len, 0);
31 /// let mut vec2 = Vec::with_capacity(len);
32 /// vec2.extend(repeat(0).take(len));
35 /// let mut vec1 = vec![0; len];
36 /// let mut vec2 = vec![0; len];
38 pub SLOW_VECTOR_INITIALIZATION,
40 "slow vector initialization"
43 declare_lint_pass!(SlowVectorInit => [SLOW_VECTOR_INITIALIZATION]);
45 /// `VecAllocation` contains data regarding a vector allocated with `with_capacity` and then
46 /// assigned to a variable. For example, `let mut vec = Vec::with_capacity(0)` or
47 /// `vec = Vec::with_capacity(0)`
48 struct VecAllocation<'tcx> {
49 /// Symbol of the local variable name
50 variable_name: Symbol,
52 /// Reference to the expression which allocates the vector
53 allocation_expr: &'tcx Expr<'tcx>,
55 /// Reference to the expression used as argument on `with_capacity` call. This is used
56 /// to only match slow zero-filling idioms of the same length than vector initialization.
57 len_expr: &'tcx Expr<'tcx>,
60 /// Type of slow initialization
61 enum InitializationType<'tcx> {
62 /// Extend is a slow initialization with the form `vec.extend(repeat(0).take(..))`
63 Extend(&'tcx Expr<'tcx>),
65 /// Resize is a slow initialization with the form `vec.resize(.., 0)`
66 Resize(&'tcx Expr<'tcx>),
69 impl<'tcx> LateLintPass<'tcx> for SlowVectorInit {
70 fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
71 // Matches initialization on reassignements. For example: `vec = Vec::with_capacity(100)`
73 if let ExprKind::Assign(left, right, _) = expr.kind;
75 // Extract variable name
76 if let ExprKind::Path(QPath::Resolved(_, path)) = left.kind;
77 if let Some(variable_name) = path.segments.get(0);
79 // Extract len argument
80 if let Some(len_arg) = Self::is_vec_with_capacity(right);
83 let vi = VecAllocation {
84 variable_name: variable_name.ident.name,
85 allocation_expr: right,
89 Self::search_initialization(cx, vi, expr.hir_id);
94 fn check_stmt(&mut self, cx: &LateContext<'tcx>, stmt: &'tcx Stmt<'_>) {
95 // Matches statements which initializes vectors. For example: `let mut vec = Vec::with_capacity(10)`
97 if let StmtKind::Local(local) = stmt.kind;
98 if let PatKind::Binding(BindingAnnotation::Mutable, .., variable_name, None) = local.pat.kind;
99 if let Some(init) = local.init;
100 if let Some(len_arg) = Self::is_vec_with_capacity(init);
103 let vi = VecAllocation {
104 variable_name: variable_name.name,
105 allocation_expr: init,
109 Self::search_initialization(cx, vi, stmt.hir_id);
115 impl SlowVectorInit {
116 /// Checks if the given expression is `Vec::with_capacity(..)`. It will return the expression
117 /// of the first argument of `with_capacity` call if it matches or `None` if it does not.
118 fn is_vec_with_capacity<'tcx>(expr: &Expr<'tcx>) -> Option<&'tcx Expr<'tcx>> {
120 if let ExprKind::Call(func, args) = expr.kind;
121 if let ExprKind::Path(ref path) = func.kind;
122 if match_qpath(path, &["Vec", "with_capacity"]);
126 return Some(&args[0]);
133 /// Search initialization for the given vector
134 fn search_initialization<'tcx>(cx: &LateContext<'tcx>, vec_alloc: VecAllocation<'tcx>, parent_node: HirId) {
135 let enclosing_body = get_enclosing_block(cx, parent_node);
137 if enclosing_body.is_none() {
141 let mut v = VectorInitializationVisitor {
144 slow_expression: None,
145 initialization_found: false,
148 v.visit_block(enclosing_body.unwrap());
150 if let Some(ref allocation_expr) = v.slow_expression {
151 Self::lint_initialization(cx, allocation_expr, &v.vec_alloc);
155 fn lint_initialization<'tcx>(
156 cx: &LateContext<'tcx>,
157 initialization: &InitializationType<'tcx>,
158 vec_alloc: &VecAllocation<'_>,
160 match initialization {
161 InitializationType::Extend(e) | InitializationType::Resize(e) => Self::emit_lint(
165 "slow zero-filling initialization",
166 SLOW_VECTOR_INITIALIZATION,
172 cx: &LateContext<'tcx>,
173 slow_fill: &Expr<'_>,
174 vec_alloc: &VecAllocation<'_>,
178 let len_expr = Sugg::hir(cx, vec_alloc.len_expr, "len");
180 span_lint_and_then(cx, lint, slow_fill.span, msg, |diag| {
181 diag.span_suggestion(
182 vec_alloc.allocation_expr.span,
183 "consider replace allocation with",
184 format!("vec![0; {}]", len_expr),
185 Applicability::Unspecified,
191 /// `VectorInitializationVisitor` searches for unsafe or slow vector initializations for the given
193 struct VectorInitializationVisitor<'a, 'tcx> {
194 cx: &'a LateContext<'tcx>,
196 /// Contains the information.
197 vec_alloc: VecAllocation<'tcx>,
199 /// Contains the slow initialization expression, if one was found.
200 slow_expression: Option<InitializationType<'tcx>>,
202 /// `true` if the initialization of the vector has been found on the visited block.
203 initialization_found: bool,
206 impl<'a, 'tcx> VectorInitializationVisitor<'a, 'tcx> {
207 /// Checks if the given expression is extending a vector with `repeat(0).take(..)`
208 fn search_slow_extend_filling(&mut self, expr: &'tcx Expr<'_>) {
210 if self.initialization_found;
211 if let ExprKind::MethodCall(path, _, args, _) = expr.kind;
212 if let ExprKind::Path(ref qpath_subj) = args[0].kind;
213 if match_qpath(qpath_subj, &[&*self.vec_alloc.variable_name.as_str()]);
214 if path.ident.name == sym!(extend);
215 if let Some(extend_arg) = args.get(1);
216 if self.is_repeat_take(extend_arg);
219 self.slow_expression = Some(InitializationType::Extend(expr));
224 /// Checks if the given expression is resizing a vector with 0
225 fn search_slow_resize_filling(&mut self, expr: &'tcx Expr<'_>) {
227 if self.initialization_found;
228 if let ExprKind::MethodCall(path, _, args, _) = expr.kind;
229 if let ExprKind::Path(ref qpath_subj) = args[0].kind;
230 if match_qpath(qpath_subj, &[&*self.vec_alloc.variable_name.as_str()]);
231 if path.ident.name == sym!(resize);
232 if let (Some(len_arg), Some(fill_arg)) = (args.get(1), args.get(2));
234 // Check that is filled with 0
235 if let ExprKind::Lit(ref lit) = fill_arg.kind;
236 if let LitKind::Int(0, _) = lit.node;
238 // Check that len expression is equals to `with_capacity` expression
239 if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
242 self.slow_expression = Some(InitializationType::Resize(expr));
247 /// Returns `true` if give expression is `repeat(0).take(...)`
248 fn is_repeat_take(&self, expr: &Expr<'_>) -> bool {
250 if let ExprKind::MethodCall(take_path, _, take_args, _) = expr.kind;
251 if take_path.ident.name == sym!(take);
253 // Check that take is applied to `repeat(0)`
254 if let Some(repeat_expr) = take_args.get(0);
255 if Self::is_repeat_zero(repeat_expr);
257 // Check that len expression is equals to `with_capacity` expression
258 if let Some(len_arg) = take_args.get(1);
259 if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
269 /// Returns `true` if given expression is `repeat(0)`
270 fn is_repeat_zero(expr: &Expr<'_>) -> bool {
272 if let ExprKind::Call(fn_expr, repeat_args) = expr.kind;
273 if let ExprKind::Path(ref qpath_repeat) = fn_expr.kind;
274 if match_qpath(qpath_repeat, &["repeat"]);
275 if let Some(repeat_arg) = repeat_args.get(0);
276 if let ExprKind::Lit(ref lit) = repeat_arg.kind;
277 if let LitKind::Int(0, _) = lit.node;
288 impl<'a, 'tcx> Visitor<'tcx> for VectorInitializationVisitor<'a, 'tcx> {
289 type Map = Map<'tcx>;
291 fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
292 if self.initialization_found {
294 StmtKind::Expr(expr) | StmtKind::Semi(expr) => {
295 self.search_slow_extend_filling(expr);
296 self.search_slow_resize_filling(expr);
301 self.initialization_found = false;
303 walk_stmt(self, stmt);
307 fn visit_block(&mut self, block: &'tcx Block<'_>) {
308 if self.initialization_found {
309 if let Some(s) = block.stmts.get(0) {
313 self.initialization_found = false;
315 walk_block(self, block);
319 fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
320 // Skip all the expressions previous to the vector initialization
321 if self.vec_alloc.allocation_expr.hir_id == expr.hir_id {
322 self.initialization_found = true;
325 walk_expr(self, expr);
328 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
329 NestedVisitorMap::None