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