src/tools/clippy/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, NestedVisitorMap, Visitor};
   9 use rustc_hir::{BindingAnnotation, Block, Expr, ExprKind, HirId, PatKind, QPath, Stmt, StmtKind};
  10 use rustc_lint::{LateContext, LateLintPass};
  11 use rustc_middle::hir::map::Map;
  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     ///
  28     /// // Bad
  29     /// let mut vec1 = Vec::with_capacity(len);
  30     /// vec1.resize(len, 0);
  31     ///
  32     /// let mut vec2 = Vec::with_capacity(len);
  33     /// vec2.extend(repeat(0).take(len));
  34     ///
  35     /// // Good
  36     /// let mut vec1 = vec![0; len];
  37     /// let mut vec2 = vec![0; len];
  38     /// ```
  39     pub SLOW_VECTOR_INITIALIZATION,
  40     perf,
  41     "slow vector initialization"
  42 }
  43
  44 declare_lint_pass!(SlowVectorInit => [SLOW_VECTOR_INITIALIZATION]);
  45
  46 /// `VecAllocation` contains data regarding a vector allocated with `with_capacity` and then
  47 /// assigned to a variable. For example, `let mut vec = Vec::with_capacity(0)` or
  48 /// `vec = Vec::with_capacity(0)`
  49 struct VecAllocation<'tcx> {
  50     /// HirId of the variable
  51     local_id: HirId,
  52
  53     /// Reference to the expression which allocates the vector
  54     allocation_expr: &'tcx Expr<'tcx>,
  55
  56     /// Reference to the expression used as argument on `with_capacity` call. This is used
  57     /// to only match slow zero-filling idioms of the same length than vector initialization.
  58     len_expr: &'tcx Expr<'tcx>,
  59 }
  60
  61 /// Type of slow initialization
  62 enum InitializationType<'tcx> {
  63     /// Extend is a slow initialization with the form `vec.extend(repeat(0).take(..))`
  64     Extend(&'tcx Expr<'tcx>),
  65
  66     /// Resize is a slow initialization with the form `vec.resize(.., 0)`
  67     Resize(&'tcx Expr<'tcx>),
  68 }
  69
  70 impl<'tcx> LateLintPass<'tcx> for SlowVectorInit {
  71     fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
  72         // Matches initialization on reassignements. For example: `vec = Vec::with_capacity(100)`
  73         if_chain! {
  74             if let ExprKind::Assign(left, right, _) = expr.kind;
  75
  76             // Extract variable
  77             if let Some(local_id) = path_to_local(left);
  78
  79             // Extract len argument
  80             if let Some(len_arg) = Self::is_vec_with_capacity(cx, right);
  81
  82             then {
  83                 let vi = VecAllocation {
  84                     local_id,
  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(local) = stmt.kind;
  98             if let PatKind::Binding(BindingAnnotation::Mutable, local_id, _, None) = local.pat.kind;
  99             if let Some(init) = local.init;
 100             if let Some(len_arg) = Self::is_vec_with_capacity(cx, init);
 101
 102             then {
 103                 let vi = VecAllocation {
 104                     local_id,
 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>(cx: &LateContext<'_>, expr: &Expr<'tcx>) -> Option<&'tcx Expr<'tcx>> {
 119         if_chain! {
 120             if let ExprKind::Call(func, [arg]) = expr.kind;
 121             if let ExprKind::Path(QPath::TypeRelative(ty, name)) = func.kind;
 122             if name.ident.as_str() == "with_capacity";
 123             if is_type_diagnostic_item(cx, cx.typeck_results().node_type(ty.hir_id), sym::vec_type);
 124             then {
 125                 Some(arg)
 126             } else {
 127                 None
 128             }
 129         }
 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) => {
 161                 Self::emit_lint(cx, e, vec_alloc, "slow zero-filling initialization");
 162             },
 163         };
 164     }
 165
 166     fn emit_lint<'tcx>(cx: &LateContext<'tcx>, slow_fill: &Expr<'_>, vec_alloc: &VecAllocation<'_>, msg: &str) {
 167         let len_expr = Sugg::hir(cx, vec_alloc.len_expr, "len");
 168
 169         span_lint_and_then(cx, SLOW_VECTOR_INITIALIZATION, slow_fill.span, msg, |diag| {
 170             diag.span_suggestion(
 171                 vec_alloc.allocation_expr.span,
 172                 "consider replace allocation with",
 173                 format!("vec![0; {}]", len_expr),
 174                 Applicability::Unspecified,
 175             );
 176         });
 177     }
 178 }
 179
 180 /// `VectorInitializationVisitor` searches for unsafe or slow vector initializations for the given
 181 /// vector.
 182 struct VectorInitializationVisitor<'a, 'tcx> {
 183     cx: &'a LateContext<'tcx>,
 184
 185     /// Contains the information.
 186     vec_alloc: VecAllocation<'tcx>,
 187
 188     /// Contains the slow initialization expression, if one was found.
 189     slow_expression: Option<InitializationType<'tcx>>,
 190
 191     /// `true` if the initialization of the vector has been found on the visited block.
 192     initialization_found: bool,
 193 }
 194
 195 impl<'a, 'tcx> VectorInitializationVisitor<'a, 'tcx> {
 196     /// Checks if the given expression is extending a vector with `repeat(0).take(..)`
 197     fn search_slow_extend_filling(&mut self, expr: &'tcx Expr<'_>) {
 198         if_chain! {
 199             if self.initialization_found;
 200             if let ExprKind::MethodCall(path, _, [self_arg, extend_arg], _) = expr.kind;
 201             if path_to_local_id(self_arg, self.vec_alloc.local_id);
 202             if path.ident.name == sym!(extend);
 203             if self.is_repeat_take(extend_arg);
 204
 205             then {
 206                 self.slow_expression = Some(InitializationType::Extend(expr));
 207             }
 208         }
 209     }
 210
 211     /// Checks if the given expression is resizing a vector with 0
 212     fn search_slow_resize_filling(&mut self, expr: &'tcx Expr<'_>) {
 213         if_chain! {
 214             if self.initialization_found;
 215             if let ExprKind::MethodCall(path, _, [self_arg, len_arg, fill_arg], _) = expr.kind;
 216             if path_to_local_id(self_arg, self.vec_alloc.local_id);
 217             if path.ident.name == sym!(resize);
 218
 219             // Check that is filled with 0
 220             if let ExprKind::Lit(ref lit) = fill_arg.kind;
 221             if let LitKind::Int(0, _) = lit.node;
 222
 223             // Check that len expression is equals to `with_capacity` expression
 224             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 225
 226             then {
 227                 self.slow_expression = Some(InitializationType::Resize(expr));
 228             }
 229         }
 230     }
 231
 232     /// Returns `true` if give expression is `repeat(0).take(...)`
 233     fn is_repeat_take(&self, expr: &Expr<'_>) -> bool {
 234         if_chain! {
 235             if let ExprKind::MethodCall(take_path, _, take_args, _) = expr.kind;
 236             if take_path.ident.name == sym!(take);
 237
 238             // Check that take is applied to `repeat(0)`
 239             if let Some(repeat_expr) = take_args.get(0);
 240             if self.is_repeat_zero(repeat_expr);
 241
 242             // Check that len expression is equals to `with_capacity` expression
 243             if let Some(len_arg) = take_args.get(1);
 244             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 245
 246             then {
 247                 return true;
 248             }
 249         }
 250
 251         false
 252     }
 253
 254     /// Returns `true` if given expression is `repeat(0)`
 255     fn is_repeat_zero(&self, expr: &Expr<'_>) -> bool {
 256         if_chain! {
 257             if let ExprKind::Call(fn_expr, [repeat_arg]) = expr.kind;
 258             if is_expr_path_def_path(self.cx, fn_expr, &paths::ITER_REPEAT);
 259             if let ExprKind::Lit(ref lit) = repeat_arg.kind;
 260             if let LitKind::Int(0, _) = lit.node;
 261
 262             then {
 263                 true
 264             } else {
 265                 false
 266             }
 267         }
 268     }
 269 }
 270
 271 impl<'a, 'tcx> Visitor<'tcx> for VectorInitializationVisitor<'a, 'tcx> {
 272     type Map = Map<'tcx>;
 273
 274     fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
 275         if self.initialization_found {
 276             match stmt.kind {
 277                 StmtKind::Expr(expr) | StmtKind::Semi(expr) => {
 278                     self.search_slow_extend_filling(expr);
 279                     self.search_slow_resize_filling(expr);
 280                 },
 281                 _ => (),
 282             }
 283
 284             self.initialization_found = false;
 285         } else {
 286             walk_stmt(self, stmt);
 287         }
 288     }
 289
 290     fn visit_block(&mut self, block: &'tcx Block<'_>) {
 291         if self.initialization_found {
 292             if let Some(s) = block.stmts.get(0) {
 293                 self.visit_stmt(s);
 294             }
 295
 296             self.initialization_found = false;
 297         } else {
 298             walk_block(self, block);
 299         }
 300     }
 301
 302     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
 303         // Skip all the expressions previous to the vector initialization
 304         if self.vec_alloc.allocation_expr.hir_id == expr.hir_id {
 305             self.initialization_found = true;
 306         }
 307
 308         walk_expr(self, expr);
 309     }
 310
 311     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 312         NestedVisitorMap::None
 313     }
 314 }