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