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