clippy_lints/src/slow_vector_initialization.rs

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