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