clippy_lints/src/slow_vector_initialization.rs

   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::hir::intravisit::{walk_block, walk_expr, walk_stmt, NestedVisitorMap, Visitor};
   5 use rustc::hir::*;
   6 use rustc::lint::{LateContext, LateLintPass, Lint, LintArray, LintPass};
   7 use rustc::{declare_tool_lint, lint_array};
   8 use rustc_errors::Applicability;
   9 use syntax::ast::{LitKind, NodeId};
  10 use syntax_pos::symbol::Symbol;
  11
  12 /// **What it does:** Checks slow zero-filled vector initialization
  13 ///
  14 /// **Why is this bad?** This structures are non-idiomatic and less efficient than simply using
  15 /// `vec![len; 0]`.
  16 ///
  17 /// **Known problems:** None.
  18 ///
  19 /// **Example:**
  20 /// ```rust
  21 /// let mut vec1 = Vec::with_capacity(len);
  22 /// vec1.resize(len, 0);
  23 ///
  24 /// let mut vec2 = Vec::with_capacity(len);
  25 /// vec2.extend(repeat(0).take(len))
  26 /// ```
  27 declare_clippy_lint! {
  28     pub SLOW_VECTOR_INITIALIZATION,
  29     perf,
  30     "slow vector initialization"
  31 }
  32
  33 #[derive(Copy, Clone, Default)]
  34 pub struct Pass;
  35
  36 impl LintPass for Pass {
  37     fn get_lints(&self) -> LintArray {
  38         lint_array!(SLOW_VECTOR_INITIALIZATION,)
  39     }
  40 }
  41
  42 /// `VecAllocation` contains data regarding a vector allocated with `with_capacity` and then
  43 /// assigned to a variable. For example, `let mut vec = Vec::with_capacity(0)` or
  44 /// `vec = Vec::with_capacity(0)`
  45 struct VecAllocation<'tcx> {
  46     /// Symbol of the local variable name
  47     variable_name: Symbol,
  48
  49     /// Reference to the expression which allocates the vector
  50     allocation_expr: &'tcx Expr,
  51
  52     /// Reference to the expression used as argument on `with_capacity` call. This is used
  53     /// to only match slow zero-filling idioms of the same length than vector initialization.
  54     len_expr: &'tcx Expr,
  55 }
  56
  57 /// Type of slow initialization
  58 enum InitializationType<'tcx> {
  59     /// Extend is a slow initialization with the form `vec.extend(repeat(0).take(..))`
  60     Extend(&'tcx Expr),
  61
  62     /// Resize is a slow initialization with the form `vec.resize(.., 0)`
  63     Resize(&'tcx Expr),
  64 }
  65
  66 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
  67     fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
  68         // Matches initialization on reassignements. For example: `vec = Vec::with_capacity(100)`
  69         if_chain! {
  70             if let ExprKind::Assign(ref left, ref right) = expr.node;
  71
  72             // Extract variable name
  73             if let ExprKind::Path(QPath::Resolved(_, ref path)) = left.node;
  74             if let Some(variable_name) = path.segments.get(0);
  75
  76             // Extract len argument
  77             if let Some(ref len_arg) = Self::is_vec_with_capacity(right);
  78
  79             then {
  80                 let vi = VecAllocation {
  81                     variable_name: variable_name.ident.name,
  82                     allocation_expr: right,
  83                     len_expr: len_arg,
  84                 };
  85
  86                 Self::search_initialization(cx, vi, expr.id);
  87             }
  88         }
  89     }
  90
  91     fn check_stmt(&mut self, cx: &LateContext<'a, 'tcx>, stmt: &'tcx Stmt) {
  92         // Matches statements which initializes vectors. For example: `let mut vec = Vec::with_capacity(10)`
  93         if_chain! {
  94             if let StmtKind::Decl(ref decl, _) = stmt.node;
  95             if let DeclKind::Local(ref local) = decl.node;
  96             if let PatKind::Binding(BindingAnnotation::Mutable, _, variable_name, None) = local.pat.node;
  97             if let Some(ref init) = local.init;
  98             if let Some(ref len_arg) = Self::is_vec_with_capacity(init);
  99
 100             then {
 101                 let vi = VecAllocation {
 102                     variable_name: variable_name.name,
 103                     allocation_expr: init,
 104                     len_expr: len_arg,
 105                 };
 106
 107                 Self::search_initialization(cx, vi, stmt.node.id());
 108             }
 109         }
 110     }
 111 }
 112
 113 impl Pass {
 114     /// Checks if the given expression is `Vec::with_capacity(..)`. It will return the expression
 115     /// of the first argument of `with_capacity` call if it matches or `None` if it does not.
 116     fn is_vec_with_capacity(expr: &Expr) -> Option<&Expr> {
 117         if_chain! {
 118             if let ExprKind::Call(ref func, ref args) = expr.node;
 119             if let ExprKind::Path(ref path) = func.node;
 120             if match_qpath(path, &["Vec", "with_capacity"]);
 121             if args.len() == 1;
 122
 123             then {
 124                 return Some(&args[0]);
 125             }
 126         }
 127
 128         None
 129     }
 130
 131     /// Search initialization for the given vector
 132     fn search_initialization<'tcx>(cx: &LateContext<'_, 'tcx>, vec_alloc: VecAllocation<'tcx>, parent_node: NodeId) {
 133         let enclosing_body = get_enclosing_block(cx, parent_node);
 134
 135         if enclosing_body.is_none() {
 136             return;
 137         }
 138
 139         let mut v = VectorInitializationVisitor {
 140             cx,
 141             vec_alloc,
 142             slow_expression: None,
 143             initialization_found: false,
 144         };
 145
 146         v.visit_block(enclosing_body.unwrap());
 147
 148         if let Some(ref allocation_expr) = v.slow_expression {
 149             Self::lint_initialization(cx, allocation_expr, &v.vec_alloc);
 150         }
 151     }
 152
 153     fn lint_initialization<'tcx>(
 154         cx: &LateContext<'_, 'tcx>,
 155         initialization: &InitializationType<'tcx>,
 156         vec_alloc: &VecAllocation<'_>,
 157     ) {
 158         match initialization {
 159             InitializationType::Extend(e) | InitializationType::Resize(e) => Self::emit_lint(
 160                 cx,
 161                 e,
 162                 vec_alloc,
 163                 "slow zero-filling initialization",
 164                 SLOW_VECTOR_INITIALIZATION,
 165             ),
 166         };
 167     }
 168
 169     fn emit_lint<'tcx>(
 170         cx: &LateContext<'_, 'tcx>,
 171         slow_fill: &Expr,
 172         vec_alloc: &VecAllocation<'_>,
 173         msg: &str,
 174         lint: &'static Lint,
 175     ) {
 176         let len_expr = Sugg::hir(cx, vec_alloc.len_expr, "len");
 177
 178         span_lint_and_then(cx, lint, slow_fill.span, msg, |db| {
 179             db.span_suggestion_with_applicability(
 180                 vec_alloc.allocation_expr.span,
 181                 "consider replace allocation with",
 182                 format!("vec![0; {}]", len_expr),
 183                 Applicability::Unspecified,
 184             );
 185         });
 186     }
 187 }
 188
 189 /// `VectorInitializationVisitor` searches for unsafe or slow vector initializations for the given
 190 /// vector.
 191 struct VectorInitializationVisitor<'a, 'tcx: 'a> {
 192     cx: &'a LateContext<'a, 'tcx>,
 193
 194     /// Contains the information
 195     vec_alloc: VecAllocation<'tcx>,
 196
 197     /// Contains, if found, the slow initialization expression
 198     slow_expression: Option<InitializationType<'tcx>>,
 199
 200     /// true if the initialization of the vector has been found on the visited block
 201     initialization_found: bool,
 202 }
 203
 204 impl<'a, 'tcx> VectorInitializationVisitor<'a, 'tcx> {
 205     /// Checks if the given expression is extending a vector with `repeat(0).take(..)`
 206     fn search_slow_extend_filling(&mut self, expr: &'tcx Expr) {
 207         if_chain! {
 208             if self.initialization_found;
 209             if let ExprKind::MethodCall(ref path, _, ref args) = expr.node;
 210             if let ExprKind::Path(ref qpath_subj) = args[0].node;
 211             if match_qpath(&qpath_subj, &[&self.vec_alloc.variable_name.to_string()]);
 212             if path.ident.name == "extend";
 213             if let Some(ref extend_arg) = args.get(1);
 214             if self.is_repeat_take(extend_arg);
 215
 216             then {
 217                 self.slow_expression = Some(InitializationType::Extend(expr));
 218             }
 219         }
 220     }
 221
 222     /// Checks if the given expression is resizing a vector with 0
 223     fn search_slow_resize_filling(&mut self, expr: &'tcx Expr) {
 224         if_chain! {
 225             if self.initialization_found;
 226             if let ExprKind::MethodCall(ref path, _, ref args) = expr.node;
 227             if let ExprKind::Path(ref qpath_subj) = args[0].node;
 228             if match_qpath(&qpath_subj, &[&self.vec_alloc.variable_name.to_string()]);
 229             if path.ident.name == "resize";
 230             if let (Some(ref len_arg), Some(fill_arg)) = (args.get(1), args.get(2));
 231
 232             // Check that is filled with 0
 233             if let ExprKind::Lit(ref lit) = fill_arg.node;
 234             if let LitKind::Int(0, _) = lit.node;
 235
 236             // Check that len expression is equals to `with_capacity` expression
 237             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 238
 239             then {
 240                 self.slow_expression = Some(InitializationType::Resize(expr));
 241             }
 242         }
 243     }
 244
 245     /// Returns `true` if give expression is `repeat(0).take(...)`
 246     fn is_repeat_take(&self, expr: &Expr) -> bool {
 247         if_chain! {
 248             if let ExprKind::MethodCall(ref take_path, _, ref take_args) = expr.node;
 249             if take_path.ident.name == "take";
 250
 251             // Check that take is applied to `repeat(0)`
 252             if let Some(ref repeat_expr) = take_args.get(0);
 253             if self.is_repeat_zero(repeat_expr);
 254
 255             // Check that len expression is equals to `with_capacity` expression
 256             if let Some(ref len_arg) = take_args.get(1);
 257             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 258
 259             then {
 260                 return true;
 261             }
 262         }
 263
 264         false
 265     }
 266
 267     /// Returns `true` if given expression is `repeat(0)`
 268     fn is_repeat_zero(&self, expr: &Expr) -> bool {
 269         if_chain! {
 270             if let ExprKind::Call(ref fn_expr, ref repeat_args) = expr.node;
 271             if let ExprKind::Path(ref qpath_repeat) = fn_expr.node;
 272             if match_qpath(&qpath_repeat, &["repeat"]);
 273             if let Some(ref repeat_arg) = repeat_args.get(0);
 274             if let ExprKind::Lit(ref lit) = repeat_arg.node;
 275             if let LitKind::Int(0, _) = lit.node;
 276
 277             then {
 278                 return true
 279             }
 280         }
 281
 282         false
 283     }
 284 }
 285
 286 impl<'a, 'tcx> Visitor<'tcx> for VectorInitializationVisitor<'a, 'tcx> {
 287     fn visit_stmt(&mut self, stmt: &'tcx Stmt) {
 288         if self.initialization_found {
 289             match stmt.node {
 290                 StmtKind::Expr(ref expr, _) | StmtKind::Semi(ref expr, _) => {
 291                     self.search_slow_extend_filling(expr);
 292                     self.search_slow_resize_filling(expr);
 293                 },
 294                 _ => (),
 295             }
 296
 297             self.initialization_found = false;
 298         } else {
 299             walk_stmt(self, stmt);
 300         }
 301     }
 302
 303     fn visit_block(&mut self, block: &'tcx Block) {
 304         if self.initialization_found {
 305             if let Some(ref s) = block.stmts.get(0) {
 306                 self.visit_stmt(s)
 307             }
 308
 309             self.initialization_found = false;
 310         } else {
 311             walk_block(self, block);
 312         }
 313     }
 314
 315     fn visit_expr(&mut self, expr: &'tcx Expr) {
 316         // Skip all the expressions previous to the vector initialization
 317         if self.vec_alloc.allocation_expr.id == expr.id {
 318             self.initialization_found = true;
 319         }
 320
 321         walk_expr(self, expr);
 322     }
 323
 324     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 325         NestedVisitorMap::None
 326     }
 327 }