clippy_lints/src/slow_vector_initialization.rs

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