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::Local(ref local) = stmt.node;
  95             if let PatKind::Binding(BindingAnnotation::Mutable, _, variable_name, None) = local.pat.node;
  96             if let Some(ref init) = local.init;
  97             if let Some(ref len_arg) = Self::is_vec_with_capacity(init);
  98
  99             then {
 100                 let vi = VecAllocation {
 101                     variable_name: variable_name.name,
 102                     allocation_expr: init,
 103                     len_expr: len_arg,
 104                 };
 105
 106                 Self::search_initialization(cx, vi, stmt.id);
 107             }
 108         }
 109     }
 110 }
 111
 112 impl Pass {
 113     /// Checks if the given expression is `Vec::with_capacity(..)`. It will return the expression
 114     /// of the first argument of `with_capacity` call if it matches or `None` if it does not.
 115     fn is_vec_with_capacity(expr: &Expr) -> Option<&Expr> {
 116         if_chain! {
 117             if let ExprKind::Call(ref func, ref args) = expr.node;
 118             if let ExprKind::Path(ref path) = func.node;
 119             if match_qpath(path, &["Vec", "with_capacity"]);
 120             if args.len() == 1;
 121
 122             then {
 123                 return Some(&args[0]);
 124             }
 125         }
 126
 127         None
 128     }
 129
 130     /// Search initialization for the given vector
 131     fn search_initialization<'tcx>(cx: &LateContext<'_, 'tcx>, vec_alloc: VecAllocation<'tcx>, parent_node: NodeId) {
 132         let enclosing_body = get_enclosing_block(cx, parent_node);
 133
 134         if enclosing_body.is_none() {
 135             return;
 136         }
 137
 138         let mut v = VectorInitializationVisitor {
 139             cx,
 140             vec_alloc,
 141             slow_expression: None,
 142             initialization_found: false,
 143         };
 144
 145         v.visit_block(enclosing_body.unwrap());
 146
 147         if let Some(ref allocation_expr) = v.slow_expression {
 148             Self::lint_initialization(cx, allocation_expr, &v.vec_alloc);
 149         }
 150     }
 151
 152     fn lint_initialization<'tcx>(
 153         cx: &LateContext<'_, 'tcx>,
 154         initialization: &InitializationType<'tcx>,
 155         vec_alloc: &VecAllocation<'_>,
 156     ) {
 157         match initialization {
 158             InitializationType::Extend(e) | InitializationType::Resize(e) => Self::emit_lint(
 159                 cx,
 160                 e,
 161                 vec_alloc,
 162                 "slow zero-filling initialization",
 163                 SLOW_VECTOR_INITIALIZATION,
 164             ),
 165         };
 166     }
 167
 168     fn emit_lint<'tcx>(
 169         cx: &LateContext<'_, 'tcx>,
 170         slow_fill: &Expr,
 171         vec_alloc: &VecAllocation<'_>,
 172         msg: &str,
 173         lint: &'static Lint,
 174     ) {
 175         let len_expr = Sugg::hir(cx, vec_alloc.len_expr, "len");
 176
 177         span_lint_and_then(cx, lint, slow_fill.span, msg, |db| {
 178             db.span_suggestion_with_applicability(
 179                 vec_alloc.allocation_expr.span,
 180                 "consider replace allocation with",
 181                 format!("vec![0; {}]", len_expr),
 182                 Applicability::Unspecified,
 183             );
 184         });
 185     }
 186 }
 187
 188 /// `VectorInitializationVisitor` searches for unsafe or slow vector initializations for the given
 189 /// vector.
 190 struct VectorInitializationVisitor<'a, 'tcx: 'a> {
 191     cx: &'a LateContext<'a, 'tcx>,
 192
 193     /// Contains the information
 194     vec_alloc: VecAllocation<'tcx>,
 195
 196     /// Contains, if found, the slow initialization expression
 197     slow_expression: Option<InitializationType<'tcx>>,
 198
 199     /// true if the initialization of the vector has been found on the visited block
 200     initialization_found: bool,
 201 }
 202
 203 impl<'a, 'tcx> VectorInitializationVisitor<'a, 'tcx> {
 204     /// Checks if the given expression is extending a vector with `repeat(0).take(..)`
 205     fn search_slow_extend_filling(&mut self, expr: &'tcx Expr) {
 206         if_chain! {
 207             if self.initialization_found;
 208             if let ExprKind::MethodCall(ref path, _, ref args) = expr.node;
 209             if let ExprKind::Path(ref qpath_subj) = args[0].node;
 210             if match_qpath(&qpath_subj, &[&self.vec_alloc.variable_name.to_string()]);
 211             if path.ident.name == "extend";
 212             if let Some(ref extend_arg) = args.get(1);
 213             if self.is_repeat_take(extend_arg);
 214
 215             then {
 216                 self.slow_expression = Some(InitializationType::Extend(expr));
 217             }
 218         }
 219     }
 220
 221     /// Checks if the given expression is resizing a vector with 0
 222     fn search_slow_resize_filling(&mut self, expr: &'tcx Expr) {
 223         if_chain! {
 224             if self.initialization_found;
 225             if let ExprKind::MethodCall(ref path, _, ref args) = expr.node;
 226             if let ExprKind::Path(ref qpath_subj) = args[0].node;
 227             if match_qpath(&qpath_subj, &[&self.vec_alloc.variable_name.to_string()]);
 228             if path.ident.name == "resize";
 229             if let (Some(ref len_arg), Some(fill_arg)) = (args.get(1), args.get(2));
 230
 231             // Check that is filled with 0
 232             if let ExprKind::Lit(ref lit) = fill_arg.node;
 233             if let LitKind::Int(0, _) = lit.node;
 234
 235             // Check that len expression is equals to `with_capacity` expression
 236             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 237
 238             then {
 239                 self.slow_expression = Some(InitializationType::Resize(expr));
 240             }
 241         }
 242     }
 243
 244     /// Returns `true` if give expression is `repeat(0).take(...)`
 245     fn is_repeat_take(&self, expr: &Expr) -> bool {
 246         if_chain! {
 247             if let ExprKind::MethodCall(ref take_path, _, ref take_args) = expr.node;
 248             if take_path.ident.name == "take";
 249
 250             // Check that take is applied to `repeat(0)`
 251             if let Some(ref repeat_expr) = take_args.get(0);
 252             if self.is_repeat_zero(repeat_expr);
 253
 254             // Check that len expression is equals to `with_capacity` expression
 255             if let Some(ref len_arg) = take_args.get(1);
 256             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 257
 258             then {
 259                 return true;
 260             }
 261         }
 262
 263         false
 264     }
 265
 266     /// Returns `true` if given expression is `repeat(0)`
 267     fn is_repeat_zero(&self, expr: &Expr) -> bool {
 268         if_chain! {
 269             if let ExprKind::Call(ref fn_expr, ref repeat_args) = expr.node;
 270             if let ExprKind::Path(ref qpath_repeat) = fn_expr.node;
 271             if match_qpath(&qpath_repeat, &["repeat"]);
 272             if let Some(ref repeat_arg) = repeat_args.get(0);
 273             if let ExprKind::Lit(ref lit) = repeat_arg.node;
 274             if let LitKind::Int(0, _) = lit.node;
 275
 276             then {
 277                 return true
 278             }
 279         }
 280
 281         false
 282     }
 283 }
 284
 285 impl<'a, 'tcx> Visitor<'tcx> for VectorInitializationVisitor<'a, 'tcx> {
 286     fn visit_stmt(&mut self, stmt: &'tcx Stmt) {
 287         if self.initialization_found {
 288             match stmt.node {
 289                 StmtKind::Expr(ref expr) | StmtKind::Semi(ref expr) => {
 290                     self.search_slow_extend_filling(expr);
 291                     self.search_slow_resize_filling(expr);
 292                 },
 293                 _ => (),
 294             }
 295
 296             self.initialization_found = false;
 297         } else {
 298             walk_stmt(self, stmt);
 299         }
 300     }
 301
 302     fn visit_block(&mut self, block: &'tcx Block) {
 303         if self.initialization_found {
 304             if let Some(ref s) = block.stmts.get(0) {
 305                 self.visit_stmt(s)
 306             }
 307
 308             self.initialization_found = false;
 309         } else {
 310             walk_block(self, block);
 311         }
 312     }
 313
 314     fn visit_expr(&mut self, expr: &'tcx Expr) {
 315         // Skip all the expressions previous to the vector initialization
 316         if self.vec_alloc.allocation_expr.id == expr.id {
 317             self.initialization_found = true;
 318         }
 319
 320         walk_expr(self, expr);
 321     }
 322
 323     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 324         NestedVisitorMap::None
 325     }
 326 }