clippy_lints/src/loops/utils.rs

   1 use clippy_utils::ty::{has_iter_method, implements_trait};
   2 use clippy_utils::{get_parent_expr, is_integer_const, path_to_local, path_to_local_id, sugg};
   3 use if_chain::if_chain;
   4 use rustc_errors::Applicability;
   5 use rustc_hir::intravisit::{walk_expr, walk_pat, walk_stmt, NestedVisitorMap, Visitor};
   6 use rustc_hir::HirIdMap;
   7 use rustc_hir::{BinOpKind, BorrowKind, Expr, ExprKind, HirId, Mutability, Pat, PatKind, Stmt, StmtKind};
   8 use rustc_lint::LateContext;
   9 use rustc_middle::hir::map::Map;
  10 use rustc_span::source_map::Span;
  11 use rustc_span::symbol::{sym, Symbol};
  12 use std::iter::Iterator;
  13
  14 #[derive(Debug, PartialEq)]
  15 enum IncrementVisitorVarState {
  16     Initial,  // Not examined yet
  17     IncrOnce, // Incremented exactly once, may be a loop counter
  18     DontWarn,
  19 }
  20
  21 /// Scan a for loop for variables that are incremented exactly once and not used after that.
  22 pub(super) struct IncrementVisitor<'a, 'tcx> {
  23     cx: &'a LateContext<'tcx>,                  // context reference
  24     states: HirIdMap<IncrementVisitorVarState>, // incremented variables
  25     depth: u32,                                 // depth of conditional expressions
  26     done: bool,
  27 }
  28
  29 impl<'a, 'tcx> IncrementVisitor<'a, 'tcx> {
  30     pub(super) fn new(cx: &'a LateContext<'tcx>) -> Self {
  31         Self {
  32             cx,
  33             states: HirIdMap::default(),
  34             depth: 0,
  35             done: false,
  36         }
  37     }
  38
  39     pub(super) fn into_results(self) -> impl Iterator<Item = HirId> {
  40         self.states.into_iter().filter_map(|(id, state)| {
  41             if state == IncrementVisitorVarState::IncrOnce {
  42                 Some(id)
  43             } else {
  44                 None
  45             }
  46         })
  47     }
  48 }
  49
  50 impl<'a, 'tcx> Visitor<'tcx> for IncrementVisitor<'a, 'tcx> {
  51     type Map = Map<'tcx>;
  52
  53     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
  54         if self.done {
  55             return;
  56         }
  57
  58         // If node is a variable
  59         if let Some(def_id) = path_to_local(expr) {
  60             if let Some(parent) = get_parent_expr(self.cx, expr) {
  61                 let state = self.states.entry(def_id).or_insert(IncrementVisitorVarState::Initial);
  62                 if *state == IncrementVisitorVarState::IncrOnce {
  63                     *state = IncrementVisitorVarState::DontWarn;
  64                     return;
  65                 }
  66
  67                 match parent.kind {
  68                     ExprKind::AssignOp(op, lhs, rhs) => {
  69                         if lhs.hir_id == expr.hir_id {
  70                             *state = if op.node == BinOpKind::Add
  71                                 && is_integer_const(self.cx, rhs, 1)
  72                                 && *state == IncrementVisitorVarState::Initial
  73                                 && self.depth == 0
  74                             {
  75                                 IncrementVisitorVarState::IncrOnce
  76                             } else {
  77                                 // Assigned some other value or assigned multiple times
  78                                 IncrementVisitorVarState::DontWarn
  79                             };
  80                         }
  81                     },
  82                     ExprKind::Assign(lhs, _, _) if lhs.hir_id == expr.hir_id => {
  83                         *state = IncrementVisitorVarState::DontWarn;
  84                     },
  85                     ExprKind::AddrOf(BorrowKind::Ref, mutability, _) if mutability == Mutability::Mut => {
  86                         *state = IncrementVisitorVarState::DontWarn;
  87                     },
  88                     _ => (),
  89                 }
  90             }
  91
  92             walk_expr(self, expr);
  93         } else if is_loop(expr) || is_conditional(expr) {
  94             self.depth += 1;
  95             walk_expr(self, expr);
  96             self.depth -= 1;
  97         } else if let ExprKind::Continue(_) = expr.kind {
  98             self.done = true;
  99         } else {
 100             walk_expr(self, expr);
 101         }
 102     }
 103     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 104         NestedVisitorMap::None
 105     }
 106 }
 107
 108 enum InitializeVisitorState<'hir> {
 109     Initial,          // Not examined yet
 110     Declared(Symbol), // Declared but not (yet) initialized
 111     Initialized {
 112         name: Symbol,
 113         initializer: &'hir Expr<'hir>,
 114     },
 115     DontWarn,
 116 }
 117
 118 /// Checks whether a variable is initialized at the start of a loop and not modified
 119 /// and used after the loop.
 120 pub(super) struct InitializeVisitor<'a, 'tcx> {
 121     cx: &'a LateContext<'tcx>,  // context reference
 122     end_expr: &'tcx Expr<'tcx>, // the for loop. Stop scanning here.
 123     var_id: HirId,
 124     state: InitializeVisitorState<'tcx>,
 125     depth: u32, // depth of conditional expressions
 126     past_loop: bool,
 127 }
 128
 129 impl<'a, 'tcx> InitializeVisitor<'a, 'tcx> {
 130     pub(super) fn new(cx: &'a LateContext<'tcx>, end_expr: &'tcx Expr<'tcx>, var_id: HirId) -> Self {
 131         Self {
 132             cx,
 133             end_expr,
 134             var_id,
 135             state: InitializeVisitorState::Initial,
 136             depth: 0,
 137             past_loop: false,
 138         }
 139     }
 140
 141     pub(super) fn get_result(&self) -> Option<(Symbol, &'tcx Expr<'tcx>)> {
 142         if let InitializeVisitorState::Initialized { name, initializer } = self.state {
 143             Some((name, initializer))
 144         } else {
 145             None
 146         }
 147     }
 148 }
 149
 150 impl<'a, 'tcx> Visitor<'tcx> for InitializeVisitor<'a, 'tcx> {
 151     type Map = Map<'tcx>;
 152
 153     fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
 154         // Look for declarations of the variable
 155         if_chain! {
 156             if let StmtKind::Local(local) = stmt.kind;
 157             if local.pat.hir_id == self.var_id;
 158             if let PatKind::Binding(.., ident, _) = local.pat.kind;
 159             then {
 160                 self.state = local.init.map_or(InitializeVisitorState::Declared(ident.name), |init| {
 161                     InitializeVisitorState::Initialized {
 162                         initializer: init,
 163                         name: ident.name,
 164                     }
 165                 })
 166             }
 167         }
 168         walk_stmt(self, stmt);
 169     }
 170
 171     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
 172         if matches!(self.state, InitializeVisitorState::DontWarn) {
 173             return;
 174         }
 175         if expr.hir_id == self.end_expr.hir_id {
 176             self.past_loop = true;
 177             return;
 178         }
 179         // No need to visit expressions before the variable is
 180         // declared
 181         if matches!(self.state, InitializeVisitorState::Initial) {
 182             return;
 183         }
 184
 185         // If node is the desired variable, see how it's used
 186         if path_to_local_id(expr, self.var_id) {
 187             if self.past_loop {
 188                 self.state = InitializeVisitorState::DontWarn;
 189                 return;
 190             }
 191
 192             if let Some(parent) = get_parent_expr(self.cx, expr) {
 193                 match parent.kind {
 194                     ExprKind::AssignOp(_, lhs, _) if lhs.hir_id == expr.hir_id => {
 195                         self.state = InitializeVisitorState::DontWarn;
 196                     },
 197                     ExprKind::Assign(lhs, rhs, _) if lhs.hir_id == expr.hir_id => {
 198                         self.state = if_chain! {
 199                             if self.depth == 0;
 200                             if let InitializeVisitorState::Declared(name)
 201                                 | InitializeVisitorState::Initialized { name, ..} = self.state;
 202                             then {
 203                                 InitializeVisitorState::Initialized { initializer: rhs, name }
 204                             } else {
 205                                 InitializeVisitorState::DontWarn
 206                             }
 207                         }
 208                     },
 209                     ExprKind::AddrOf(BorrowKind::Ref, mutability, _) if mutability == Mutability::Mut => {
 210                         self.state = InitializeVisitorState::DontWarn;
 211                     },
 212                     _ => (),
 213                 }
 214             }
 215
 216             walk_expr(self, expr);
 217         } else if !self.past_loop && is_loop(expr) {
 218             self.state = InitializeVisitorState::DontWarn;
 219         } else if is_conditional(expr) {
 220             self.depth += 1;
 221             walk_expr(self, expr);
 222             self.depth -= 1;
 223         } else {
 224             walk_expr(self, expr);
 225         }
 226     }
 227
 228     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 229         NestedVisitorMap::OnlyBodies(self.cx.tcx.hir())
 230     }
 231 }
 232
 233 fn is_loop(expr: &Expr<'_>) -> bool {
 234     matches!(expr.kind, ExprKind::Loop(..))
 235 }
 236
 237 fn is_conditional(expr: &Expr<'_>) -> bool {
 238     matches!(expr.kind, ExprKind::If(..) | ExprKind::Match(..))
 239 }
 240
 241 #[derive(PartialEq, Eq)]
 242 pub(super) enum Nesting {
 243     Unknown,     // no nesting detected yet
 244     RuledOut,    // the iterator is initialized or assigned within scope
 245     LookFurther, // no nesting detected, no further walk required
 246 }
 247
 248 use self::Nesting::{LookFurther, RuledOut, Unknown};
 249
 250 pub(super) struct LoopNestVisitor {
 251     pub(super) hir_id: HirId,
 252     pub(super) iterator: HirId,
 253     pub(super) nesting: Nesting,
 254 }
 255
 256 impl<'tcx> Visitor<'tcx> for LoopNestVisitor {
 257     type Map = Map<'tcx>;
 258
 259     fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
 260         if stmt.hir_id == self.hir_id {
 261             self.nesting = LookFurther;
 262         } else if self.nesting == Unknown {
 263             walk_stmt(self, stmt);
 264         }
 265     }
 266
 267     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
 268         if self.nesting != Unknown {
 269             return;
 270         }
 271         if expr.hir_id == self.hir_id {
 272             self.nesting = LookFurther;
 273             return;
 274         }
 275         match expr.kind {
 276             ExprKind::Assign(path, _, _) | ExprKind::AssignOp(_, path, _) => {
 277                 if path_to_local_id(path, self.iterator) {
 278                     self.nesting = RuledOut;
 279                 }
 280             },
 281             _ => walk_expr(self, expr),
 282         }
 283     }
 284
 285     fn visit_pat(&mut self, pat: &'tcx Pat<'_>) {
 286         if self.nesting != Unknown {
 287             return;
 288         }
 289         if let PatKind::Binding(_, id, ..) = pat.kind {
 290             if id == self.iterator {
 291                 self.nesting = RuledOut;
 292                 return;
 293             }
 294         }
 295         walk_pat(self, pat);
 296     }
 297
 298     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 299         NestedVisitorMap::None
 300     }
 301 }
 302
 303 // this function assumes the given expression is a `for` loop.
 304 pub(super) fn get_span_of_entire_for_loop(expr: &Expr<'_>) -> Span {
 305     // for some reason this is the only way to get the `Span`
 306     // of the entire `for` loop
 307     if let ExprKind::Match(_, arms, _) = &expr.kind {
 308         arms[0].body.span
 309     } else {
 310         unreachable!()
 311     }
 312 }
 313
 314 /// If `arg` was the argument to a `for` loop, return the "cleanest" way of writing the
 315 /// actual `Iterator` that the loop uses.
 316 pub(super) fn make_iterator_snippet(cx: &LateContext<'_>, arg: &Expr<'_>, applic_ref: &mut Applicability) -> String {
 317     let impls_iterator = cx.tcx.get_diagnostic_item(sym::Iterator).map_or(false, |id| {
 318         implements_trait(cx, cx.typeck_results().expr_ty(arg), id, &[])
 319     });
 320     if impls_iterator {
 321         format!(
 322             "{}",
 323             sugg::Sugg::hir_with_applicability(cx, arg, "_", applic_ref).maybe_par()
 324         )
 325     } else {
 326         // (&x).into_iter() ==> x.iter()
 327         // (&mut x).into_iter() ==> x.iter_mut()
 328         match &arg.kind {
 329             ExprKind::AddrOf(BorrowKind::Ref, mutability, arg_inner)
 330                 if has_iter_method(cx, cx.typeck_results().expr_ty(arg_inner)).is_some() =>
 331             {
 332                 let meth_name = match mutability {
 333                     Mutability::Mut => "iter_mut",
 334                     Mutability::Not => "iter",
 335                 };
 336                 format!(
 337                     "{}.{}()",
 338                     sugg::Sugg::hir_with_applicability(cx, arg_inner, "_", applic_ref).maybe_par(),
 339                     meth_name,
 340                 )
 341             }
 342             _ => format!(
 343                 "{}.into_iter()",
 344                 sugg::Sugg::hir_with_applicability(cx, arg, "_", applic_ref).maybe_par()
 345             ),
 346         }
 347     }
 348 }