clippy_lints/src/slow_vector_initialization.rs

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