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