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