1 use crate::utils::sugg::Sugg;
2 use crate::utils::{get_enclosing_block, match_qpath, span_lint_and_then, SpanlessEq};
3 use if_chain::if_chain;
4 use rustc_ast::ast::LitKind;
5 use rustc_errors::Applicability;
6 use rustc_hir::intravisit::{walk_block, walk_expr, walk_stmt, NestedVisitorMap, Visitor};
7 use rustc_hir::{BindingAnnotation, Block, Expr, ExprKind, HirId, PatKind, QPath, Stmt, StmtKind};
8 use rustc_lint::{LateContext, LateLintPass, Lint};
9 use rustc_middle::hir::map::Map;
10 use rustc_session::{declare_lint_pass, declare_tool_lint};
11 use rustc_span::symbol::Symbol;
13 declare_clippy_lint! {
14 /// **What it does:** Checks slow zero-filled vector initialization
16 /// **Why is this bad?** These structures are non-idiomatic and less efficient than simply using
19 /// **Known problems:** None.
23 /// # use core::iter::repeat;
25 /// let mut vec1 = Vec::with_capacity(len);
26 /// vec1.resize(len, 0);
28 /// let mut vec2 = Vec::with_capacity(len);
29 /// vec2.extend(repeat(0).take(len))
31 pub SLOW_VECTOR_INITIALIZATION,
33 "slow vector initialization"
36 declare_lint_pass!(SlowVectorInit => [SLOW_VECTOR_INITIALIZATION]);
38 /// `VecAllocation` contains data regarding a vector allocated with `with_capacity` and then
39 /// assigned to a variable. For example, `let mut vec = Vec::with_capacity(0)` or
40 /// `vec = Vec::with_capacity(0)`
41 struct VecAllocation<'tcx> {
42 /// Symbol of the local variable name
43 variable_name: Symbol,
45 /// Reference to the expression which allocates the vector
46 allocation_expr: &'tcx Expr<'tcx>,
48 /// Reference to the expression used as argument on `with_capacity` call. This is used
49 /// to only match slow zero-filling idioms of the same length than vector initialization.
50 len_expr: &'tcx Expr<'tcx>,
53 /// Type of slow initialization
54 enum InitializationType<'tcx> {
55 /// Extend is a slow initialization with the form `vec.extend(repeat(0).take(..))`
56 Extend(&'tcx Expr<'tcx>),
58 /// Resize is a slow initialization with the form `vec.resize(.., 0)`
59 Resize(&'tcx Expr<'tcx>),
62 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for SlowVectorInit {
63 fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr<'_>) {
64 // Matches initialization on reassignements. For example: `vec = Vec::with_capacity(100)`
66 if let ExprKind::Assign(ref left, ref right, _) = expr.kind;
68 // Extract variable name
69 if let ExprKind::Path(QPath::Resolved(_, ref path)) = left.kind;
70 if let Some(variable_name) = path.segments.get(0);
72 // Extract len argument
73 if let Some(ref len_arg) = Self::is_vec_with_capacity(right);
76 let vi = VecAllocation {
77 variable_name: variable_name.ident.name,
78 allocation_expr: right,
82 Self::search_initialization(cx, vi, expr.hir_id);
87 fn check_stmt(&mut self, cx: &LateContext<'a, 'tcx>, stmt: &'tcx Stmt<'_>) {
88 // Matches statements which initializes vectors. For example: `let mut vec = Vec::with_capacity(10)`
90 if let StmtKind::Local(ref local) = stmt.kind;
91 if let PatKind::Binding(BindingAnnotation::Mutable, .., variable_name, None) = local.pat.kind;
92 if let Some(ref init) = local.init;
93 if let Some(ref len_arg) = Self::is_vec_with_capacity(init);
96 let vi = VecAllocation {
97 variable_name: variable_name.name,
98 allocation_expr: init,
102 Self::search_initialization(cx, vi, stmt.hir_id);
108 impl SlowVectorInit {
109 /// Checks if the given expression is `Vec::with_capacity(..)`. It will return the expression
110 /// of the first argument of `with_capacity` call if it matches or `None` if it does not.
111 fn is_vec_with_capacity<'tcx>(expr: &Expr<'tcx>) -> Option<&'tcx Expr<'tcx>> {
113 if let ExprKind::Call(ref func, ref args) = expr.kind;
114 if let ExprKind::Path(ref path) = func.kind;
115 if match_qpath(path, &["Vec", "with_capacity"]);
119 return Some(&args[0]);
126 /// Search initialization for the given vector
127 fn search_initialization<'tcx>(cx: &LateContext<'_, 'tcx>, vec_alloc: VecAllocation<'tcx>, parent_node: HirId) {
128 let enclosing_body = get_enclosing_block(cx, parent_node);
130 if enclosing_body.is_none() {
134 let mut v = VectorInitializationVisitor {
137 slow_expression: None,
138 initialization_found: false,
141 v.visit_block(enclosing_body.unwrap());
143 if let Some(ref allocation_expr) = v.slow_expression {
144 Self::lint_initialization(cx, allocation_expr, &v.vec_alloc);
148 fn lint_initialization<'tcx>(
149 cx: &LateContext<'_, 'tcx>,
150 initialization: &InitializationType<'tcx>,
151 vec_alloc: &VecAllocation<'_>,
153 match initialization {
154 InitializationType::Extend(e) | InitializationType::Resize(e) => Self::emit_lint(
158 "slow zero-filling initialization",
159 SLOW_VECTOR_INITIALIZATION,
165 cx: &LateContext<'_, 'tcx>,
166 slow_fill: &Expr<'_>,
167 vec_alloc: &VecAllocation<'_>,
171 let len_expr = Sugg::hir(cx, vec_alloc.len_expr, "len");
173 span_lint_and_then(cx, lint, slow_fill.span, msg, |db| {
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<'a, '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(ref path, _, ref args) = expr.kind;
205 if let ExprKind::Path(ref qpath_subj) = args[0].kind;
206 if match_qpath(&qpath_subj, &[&*self.vec_alloc.variable_name.as_str()]);
207 if path.ident.name == sym!(extend);
208 if let Some(ref extend_arg) = args.get(1);
209 if self.is_repeat_take(extend_arg);
212 self.slow_expression = Some(InitializationType::Extend(expr));
217 /// Checks if the given expression is resizing a vector with 0
218 fn search_slow_resize_filling(&mut self, expr: &'tcx Expr<'_>) {
220 if self.initialization_found;
221 if let ExprKind::MethodCall(ref path, _, ref args) = expr.kind;
222 if let ExprKind::Path(ref qpath_subj) = args[0].kind;
223 if match_qpath(&qpath_subj, &[&*self.vec_alloc.variable_name.as_str()]);
224 if path.ident.name == sym!(resize);
225 if let (Some(ref len_arg), Some(fill_arg)) = (args.get(1), args.get(2));
227 // Check that is filled with 0
228 if let ExprKind::Lit(ref lit) = fill_arg.kind;
229 if let LitKind::Int(0, _) = lit.node;
231 // Check that len expression is equals to `with_capacity` expression
232 if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
235 self.slow_expression = Some(InitializationType::Resize(expr));
240 /// Returns `true` if give expression is `repeat(0).take(...)`
241 fn is_repeat_take(&self, expr: &Expr<'_>) -> bool {
243 if let ExprKind::MethodCall(ref take_path, _, ref take_args) = expr.kind;
244 if take_path.ident.name == sym!(take);
246 // Check that take is applied to `repeat(0)`
247 if let Some(ref repeat_expr) = take_args.get(0);
248 if Self::is_repeat_zero(repeat_expr);
250 // Check that len expression is equals to `with_capacity` expression
251 if let Some(ref len_arg) = take_args.get(1);
252 if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
262 /// Returns `true` if given expression is `repeat(0)`
263 fn is_repeat_zero(expr: &Expr<'_>) -> bool {
265 if let ExprKind::Call(ref fn_expr, ref repeat_args) = expr.kind;
266 if let ExprKind::Path(ref qpath_repeat) = fn_expr.kind;
267 if match_qpath(&qpath_repeat, &["repeat"]);
268 if let Some(ref repeat_arg) = repeat_args.get(0);
269 if let ExprKind::Lit(ref lit) = repeat_arg.kind;
270 if let LitKind::Int(0, _) = lit.node;
281 impl<'a, 'tcx> Visitor<'tcx> for VectorInitializationVisitor<'a, 'tcx> {
282 type Map = Map<'tcx>;
284 fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
285 if self.initialization_found {
287 StmtKind::Expr(ref expr) | StmtKind::Semi(ref expr) => {
288 self.search_slow_extend_filling(expr);
289 self.search_slow_resize_filling(expr);
294 self.initialization_found = false;
296 walk_stmt(self, stmt);
300 fn visit_block(&mut self, block: &'tcx Block<'_>) {
301 if self.initialization_found {
302 if let Some(ref s) = block.stmts.get(0) {
306 self.initialization_found = false;
308 walk_block(self, block);
312 fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
313 // Skip all the expressions previous to the vector initialization
314 if self.vec_alloc.allocation_expr.hir_id == expr.hir_id {
315 self.initialization_found = true;
318 walk_expr(self, expr);
321 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
322 NestedVisitorMap::None