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