clippy_lints/src/slow_vector_initialization.rs

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