clippy_lints/src/slow_vector_initialization.rs

   1 // Copyright 2014-2018 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution.
   3 //
   4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   5 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   7 // option. This file may not be copied, modified, or distributed
   8 // except according to those terms.
   9
  10 use crate::rustc::hir::intravisit::{walk_block, walk_expr, walk_stmt, NestedVisitorMap, Visitor};
  11 use crate::rustc::hir::*;
  12 use crate::rustc::lint::{LateContext, LateLintPass, Lint, LintArray, LintPass};
  13 use crate::rustc::{declare_tool_lint, lint_array};
  14 use crate::rustc_errors::Applicability;
  15 use crate::syntax::ast::{LitKind, NodeId};
  16 use crate::syntax_pos::symbol::Symbol;
  17 use crate::utils::sugg::Sugg;
  18 use crate::utils::{get_enclosing_block, match_qpath, span_lint_and_then, SpanlessEq};
  19 use if_chain::if_chain;
  20
  21 /// **What it does:** Checks slow zero-filled vector initialization
  22 ///
  23 /// **Why is this bad?** This structures are non-idiomatic and less efficient than simply using
  24 /// `vec![len; 0]`.
  25 ///
  26 /// **Known problems:** None.
  27 ///
  28 /// **Example:**
  29 /// ```rust
  30 /// let mut vec1 = Vec::with_capacity(len);
  31 /// vec1.resize(len, 0);
  32 ///
  33 /// let mut vec2 = Vec::with_capacity(len);
  34 /// vec2.extend(repeat(0).take(len))
  35 /// ```
  36 declare_clippy_lint! {
  37     pub SLOW_VECTOR_INITIALIZATION,
  38     perf,
  39     "slow vector initialization"
  40 }
  41
  42 /// **What it does:** Checks unsafe vector initialization
  43 ///
  44 /// **Why is this bad?** Changing the length of a vector may expose uninitialized memory, which
  45 /// can lead to memory safety issues
  46 ///
  47 /// **Known problems:** None.
  48 ///
  49 /// **Example:**
  50 /// ```rust
  51 /// let mut vec1 = Vec::with_capacity(len);
  52 /// unsafe {
  53 ///     vec1.set_len(len);
  54 /// }
  55 /// ```
  56 declare_clippy_lint! {
  57     pub UNSAFE_VECTOR_INITIALIZATION,
  58     correctness,
  59     "unsafe vector initialization"
  60 }
  61
  62 #[derive(Copy, Clone, Default)]
  63 pub struct Pass;
  64
  65 impl LintPass for Pass {
  66     fn get_lints(&self) -> LintArray {
  67         lint_array!(SLOW_VECTOR_INITIALIZATION, UNSAFE_VECTOR_INITIALIZATION,)
  68     }
  69 }
  70
  71 /// `VecAllocation` contains data regarding a vector allocated with `with_capacity` and then
  72 /// assigned to a variable. For example, `let mut vec = Vec::with_capacity(0)` or
  73 /// `vec = Vec::with_capacity(0)`
  74 struct VecAllocation<'tcx> {
  75     /// Symbol of the local variable name
  76     variable_name: Symbol,
  77
  78     /// Reference to the expression which allocates the vector
  79     allocation_expr: &'tcx Expr,
  80
  81     /// Reference to the expression used as argument on `with_capacity` call. This is used
  82     /// to only match slow zero-filling idioms of the same length than vector initialization.
  83     len_expr: &'tcx Expr,
  84 }
  85
  86 /// Type of slow initialization
  87 enum InitializationType<'tcx> {
  88     /// Extend is a slow initialization with the form `vec.extend(repeat(0).take(..))`
  89     Extend(&'tcx Expr),
  90
  91     /// Resize is a slow initialization with the form `vec.resize(.., 0)`
  92     Resize(&'tcx Expr),
  93
  94     /// UnsafeSetLen is a slow initialization with the form `vec.set_len(..)`
  95     UnsafeSetLen(&'tcx Expr),
  96 }
  97
  98 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
  99     fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
 100         // Matches initialization on reassignements. For example: `vec = Vec::with_capacity(100)`
 101         if_chain! {
 102             if let ExprKind::Assign(ref left, ref right) = expr.node;
 103
 104             // Extract variable name
 105             if let ExprKind::Path(QPath::Resolved(_, ref path)) = left.node;
 106             if let Some(variable_name) = path.segments.get(0);
 107
 108             // Extract len argument
 109             if let Some(ref len_arg) = Self::is_vec_with_capacity(right);
 110
 111             then {
 112                 let vi = VecAllocation {
 113                     variable_name: variable_name.ident.name,
 114                     allocation_expr: right,
 115                     len_expr: len_arg,
 116                 };
 117
 118                 Self::search_initialization(cx, vi, expr.id);
 119             }
 120         }
 121     }
 122
 123     fn check_stmt(&mut self, cx: &LateContext<'a, 'tcx>, stmt: &'tcx Stmt) {
 124         // Matches statements which initializes vectors. For example: `let mut vec = Vec::with_capacity(10)`
 125         if_chain! {
 126             if let StmtKind::Decl(ref decl, _) = stmt.node;
 127             if let DeclKind::Local(ref local) = decl.node;
 128             if let PatKind::Binding(BindingAnnotation::Mutable, _, variable_name, None) = local.pat.node;
 129             if let Some(ref init) = local.init;
 130             if let Some(ref len_arg) = Self::is_vec_with_capacity(init);
 131
 132             then {
 133                 let vi = VecAllocation {
 134                     variable_name: variable_name.name,
 135                     allocation_expr: init,
 136                     len_expr: len_arg,
 137                 };
 138
 139                 Self::search_initialization(cx, vi, stmt.node.id());
 140             }
 141         }
 142     }
 143 }
 144
 145 impl Pass {
 146     /// Checks if the given expression is `Vec::with_capacity(..)`. It will return the expression
 147     /// of the first argument of `with_capacity` call if it matches or `None` if it does not.
 148     fn is_vec_with_capacity(expr: &Expr) -> Option<&Expr> {
 149         if_chain! {
 150             if let ExprKind::Call(ref func, ref args) = expr.node;
 151             if let ExprKind::Path(ref path) = func.node;
 152             if match_qpath(path, &["Vec", "with_capacity"]);
 153             if args.len() == 1;
 154
 155             then {
 156                 return Some(&args[0]);
 157             }
 158         }
 159
 160         None
 161     }
 162
 163     /// Search initialization for the given vector
 164     fn search_initialization<'tcx>(cx: &LateContext<'_, 'tcx>, vec_alloc: VecAllocation<'tcx>, parent_node: NodeId) {
 165         let enclosing_body = get_enclosing_block(cx, parent_node);
 166
 167         if enclosing_body.is_none() {
 168             return;
 169         }
 170
 171         let mut v = VectorInitializationVisitor {
 172             cx,
 173             vec_alloc,
 174             slow_expression: None,
 175             initialization_found: false,
 176         };
 177
 178         v.visit_block(enclosing_body.unwrap());
 179
 180         if let Some(ref allocation_expr) = v.slow_expression {
 181             Self::lint_initialization(cx, allocation_expr, &v.vec_alloc);
 182         }
 183     }
 184
 185     fn lint_initialization<'tcx>(
 186         cx: &LateContext<'_, 'tcx>,
 187         initialization: &InitializationType<'tcx>,
 188         vec_alloc: &VecAllocation<'_>,
 189     ) {
 190         match initialization {
 191             InitializationType::UnsafeSetLen(e) => Self::emit_lint(
 192                 cx,
 193                 e,
 194                 vec_alloc,
 195                 "unsafe vector initialization",
 196                 UNSAFE_VECTOR_INITIALIZATION,
 197             ),
 198
 199             InitializationType::Extend(e) | InitializationType::Resize(e) => Self::emit_lint(
 200                 cx,
 201                 e,
 202                 vec_alloc,
 203                 "slow zero-filling initialization",
 204                 SLOW_VECTOR_INITIALIZATION,
 205             ),
 206         };
 207     }
 208
 209     fn emit_lint<'tcx>(
 210         cx: &LateContext<'_, 'tcx>,
 211         slow_fill: &Expr,
 212         vec_alloc: &VecAllocation<'_>,
 213         msg: &str,
 214         lint: &'static Lint,
 215     ) {
 216         let len_expr = Sugg::hir(cx, vec_alloc.len_expr, "len");
 217
 218         span_lint_and_then(cx, lint, slow_fill.span, msg, |db| {
 219             db.span_suggestion_with_applicability(
 220                 vec_alloc.allocation_expr.span,
 221                 "consider replace allocation with",
 222                 format!("vec![0; {}]", len_expr),
 223                 Applicability::Unspecified,
 224             );
 225         });
 226     }
 227 }
 228
 229 /// `VectorInitializationVisitor` searches for unsafe or slow vector initializations for the given
 230 /// vector.
 231 struct VectorInitializationVisitor<'a, 'tcx: 'a> {
 232     cx: &'a LateContext<'a, 'tcx>,
 233
 234     /// Contains the information
 235     vec_alloc: VecAllocation<'tcx>,
 236
 237     /// Contains, if found, the slow initialization expression
 238     slow_expression: Option<InitializationType<'tcx>>,
 239
 240     /// true if the initialization of the vector has been found on the visited block
 241     initialization_found: bool,
 242 }
 243
 244 impl<'a, 'tcx> VectorInitializationVisitor<'a, 'tcx> {
 245     /// Checks if the given expression is extending a vector with `repeat(0).take(..)`
 246     fn search_slow_extend_filling(&mut self, expr: &'tcx Expr) {
 247         if_chain! {
 248             if self.initialization_found;
 249             if let ExprKind::MethodCall(ref path, _, ref args) = expr.node;
 250             if let ExprKind::Path(ref qpath_subj) = args[0].node;
 251             if match_qpath(&qpath_subj, &[&self.vec_alloc.variable_name.to_string()]);
 252             if path.ident.name == "extend";
 253             if let Some(ref extend_arg) = args.get(1);
 254             if self.is_repeat_take(extend_arg);
 255
 256             then {
 257                 self.slow_expression = Some(InitializationType::Extend(expr));
 258             }
 259         }
 260     }
 261
 262     /// Checks if the given expression is resizing a vector with 0
 263     fn search_slow_resize_filling(&mut self, expr: &'tcx Expr) {
 264         if_chain! {
 265             if self.initialization_found;
 266             if let ExprKind::MethodCall(ref path, _, ref args) = expr.node;
 267             if let ExprKind::Path(ref qpath_subj) = args[0].node;
 268             if match_qpath(&qpath_subj, &[&self.vec_alloc.variable_name.to_string()]);
 269             if path.ident.name == "resize";
 270             if let (Some(ref len_arg), Some(fill_arg)) = (args.get(1), args.get(2));
 271
 272             // Check that is filled with 0
 273             if let ExprKind::Lit(ref lit) = fill_arg.node;
 274             if let LitKind::Int(0, _) = lit.node;
 275
 276             // Check that len expression is equals to `with_capacity` expression
 277             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 278
 279             then {
 280                 self.slow_expression = Some(InitializationType::Resize(expr));
 281             }
 282         }
 283     }
 284
 285     /// Checks if the given expression is using `set_len` to initialize the vector
 286     fn search_unsafe_set_len(&mut self, expr: &'tcx Expr) {
 287         if_chain! {
 288             if self.initialization_found;
 289             if let ExprKind::MethodCall(ref path, _, ref args) = expr.node;
 290             if let ExprKind::Path(ref qpath_subj) = args[0].node;
 291             if match_qpath(&qpath_subj, &[&self.vec_alloc.variable_name.to_string()]);
 292             if path.ident.name == "set_len";
 293             if let Some(ref len_arg) = args.get(1);
 294
 295             // Check that len expression is equals to `with_capacity` expression
 296             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 297
 298             then {
 299                 self.slow_expression = Some(InitializationType::UnsafeSetLen(expr));
 300             }
 301         }
 302     }
 303
 304     /// Returns `true` if give expression is `repeat(0).take(...)`
 305     fn is_repeat_take(&self, expr: &Expr) -> bool {
 306         if_chain! {
 307             if let ExprKind::MethodCall(ref take_path, _, ref take_args) = expr.node;
 308             if take_path.ident.name == "take";
 309
 310             // Check that take is applied to `repeat(0)`
 311             if let Some(ref repeat_expr) = take_args.get(0);
 312             if self.is_repeat_zero(repeat_expr);
 313
 314             // Check that len expression is equals to `with_capacity` expression
 315             if let Some(ref len_arg) = take_args.get(1);
 316             if SpanlessEq::new(self.cx).eq_expr(len_arg, self.vec_alloc.len_expr);
 317
 318             then {
 319                 return true;
 320             }
 321         }
 322
 323         false
 324     }
 325
 326     /// Returns `true` if given expression is `repeat(0)`
 327     fn is_repeat_zero(&self, expr: &Expr) -> bool {
 328         if_chain! {
 329             if let ExprKind::Call(ref fn_expr, ref repeat_args) = expr.node;
 330             if let ExprKind::Path(ref qpath_repeat) = fn_expr.node;
 331             if match_qpath(&qpath_repeat, &["repeat"]);
 332             if let Some(ref repeat_arg) = repeat_args.get(0);
 333             if let ExprKind::Lit(ref lit) = repeat_arg.node;
 334             if let LitKind::Int(0, _) = lit.node;
 335
 336             then {
 337                 return true
 338             }
 339         }
 340
 341         false
 342     }
 343 }
 344
 345 impl<'a, 'tcx> Visitor<'tcx> for VectorInitializationVisitor<'a, 'tcx> {
 346     fn visit_stmt(&mut self, stmt: &'tcx Stmt) {
 347         if self.initialization_found {
 348             match stmt.node {
 349                 StmtKind::Expr(ref expr, _) | StmtKind::Semi(ref expr, _) => {
 350                     self.search_slow_extend_filling(expr);
 351                     self.search_slow_resize_filling(expr);
 352                     self.search_unsafe_set_len(expr);
 353                 },
 354                 _ => (),
 355             }
 356
 357             self.initialization_found = false;
 358         } else {
 359             walk_stmt(self, stmt);
 360         }
 361     }
 362
 363     fn visit_block(&mut self, block: &'tcx Block) {
 364         if self.initialization_found {
 365             if let Some(ref s) = block.stmts.get(0) {
 366                 self.visit_stmt(s)
 367             }
 368
 369             self.initialization_found = false;
 370         } else {
 371             walk_block(self, block);
 372         }
 373     }
 374
 375     fn visit_expr(&mut self, expr: &'tcx Expr) {
 376         // Skip all the expressions previous to the vector initialization
 377         if self.vec_alloc.allocation_expr.id == expr.id {
 378             self.initialization_found = true;
 379         }
 380
 381         walk_expr(self, expr);
 382     }
 383
 384     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 385         NestedVisitorMap::None
 386     }
 387 }