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_lint::LateContext;
   9 use rustc_middle::hir::nested_filter;
  10 use rustc_middle::ty::{self, Ty};
  11 use rustc_span::source_map::Spanned;
  12 use rustc_span::symbol::{sym, Symbol};
  13 use rustc_typeck::hir_ty_to_ty;
  14 use std::iter::Iterator;
  15
  16 #[derive(Debug, PartialEq)]
  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     done: bool,
  29 }
  30
  31 impl<'a, 'tcx> IncrementVisitor<'a, 'tcx> {
  32     pub(super) fn new(cx: &'a LateContext<'tcx>) -> Self {
  33         Self {
  34             cx,
  35             states: HirIdMap::default(),
  36             depth: 0,
  37             done: false,
  38         }
  39     }
  40
  41     pub(super) fn into_results(self) -> impl Iterator<Item = HirId> {
  42         self.states.into_iter().filter_map(|(id, state)| {
  43             if state == IncrementVisitorVarState::IncrOnce {
  44                 Some(id)
  45             } else {
  46                 None
  47             }
  48         })
  49     }
  50 }
  51
  52 impl<'a, 'tcx> Visitor<'tcx> for IncrementVisitor<'a, 'tcx> {
  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 }
 104
 105 enum InitializeVisitorState<'hir> {
 106     Initial,                            // Not examined yet
 107     Declared(Symbol, Option<Ty<'hir>>), // Declared but not (yet) initialized
 108     Initialized {
 109         name: Symbol,
 110         ty: Option<Ty<'hir>>,
 111         initializer: &'hir Expr<'hir>,
 112     },
 113     DontWarn,
 114 }
 115
 116 /// Checks whether a variable is initialized at the start of a loop and not modified
 117 /// and used after the loop.
 118 pub(super) struct InitializeVisitor<'a, 'tcx> {
 119     cx: &'a LateContext<'tcx>,  // context reference
 120     end_expr: &'tcx Expr<'tcx>, // the for loop. Stop scanning here.
 121     var_id: HirId,
 122     state: InitializeVisitorState<'tcx>,
 123     depth: u32, // depth of conditional expressions
 124     past_loop: bool,
 125 }
 126
 127 impl<'a, 'tcx> InitializeVisitor<'a, 'tcx> {
 128     pub(super) fn new(cx: &'a LateContext<'tcx>, end_expr: &'tcx Expr<'tcx>, var_id: HirId) -> Self {
 129         Self {
 130             cx,
 131             end_expr,
 132             var_id,
 133             state: InitializeVisitorState::Initial,
 134             depth: 0,
 135             past_loop: false,
 136         }
 137     }
 138
 139     pub(super) fn get_result(&self) -> Option<(Symbol, Option<Ty<'tcx>>, &'tcx Expr<'tcx>)> {
 140         if let InitializeVisitorState::Initialized { name, ty, initializer } = self.state {
 141             Some((name, ty, initializer))
 142         } else {
 143             None
 144         }
 145     }
 146 }
 147
 148 impl<'a, 'tcx> Visitor<'tcx> for InitializeVisitor<'a, 'tcx> {
 149     type NestedFilter = nested_filter::OnlyBodies;
 150
 151     fn visit_local(&mut self, l: &'tcx Local<'_>) {
 152         // Look for declarations of the variable
 153         if_chain! {
 154             if l.pat.hir_id == self.var_id;
 155             if let PatKind::Binding(.., ident, _) = l.pat.kind;
 156             then {
 157                 let ty = l.ty.map(|ty| hir_ty_to_ty(self.cx.tcx, ty));
 158
 159                 self.state = l.init.map_or(InitializeVisitorState::Declared(ident.name, ty), |init| {
 160                     InitializeVisitorState::Initialized {
 161                         initializer: init,
 162                         ty,
 163                         name: ident.name,
 164                     }
 165                 })
 166             }
 167         }
 168
 169         walk_local(self, l);
 170     }
 171
 172     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
 173         if matches!(self.state, InitializeVisitorState::DontWarn) {
 174             return;
 175         }
 176         if expr.hir_id == self.end_expr.hir_id {
 177             self.past_loop = true;
 178             return;
 179         }
 180         // No need to visit expressions before the variable is
 181         // declared
 182         if matches!(self.state, InitializeVisitorState::Initial) {
 183             return;
 184         }
 185
 186         // If node is the desired variable, see how it's used
 187         if path_to_local_id(expr, self.var_id) {
 188             if self.past_loop {
 189                 self.state = InitializeVisitorState::DontWarn;
 190                 return;
 191             }
 192
 193             if let Some(parent) = get_parent_expr(self.cx, expr) {
 194                 match parent.kind {
 195                     ExprKind::AssignOp(_, lhs, _) if lhs.hir_id == expr.hir_id => {
 196                         self.state = InitializeVisitorState::DontWarn;
 197                     },
 198                     ExprKind::Assign(lhs, rhs, _) if lhs.hir_id == expr.hir_id => {
 199                         self.state = if self.depth == 0 {
 200                             match self.state {
 201                                 InitializeVisitorState::Declared(name, mut ty) => {
 202                                     if ty.is_none() {
 203                                         if let ExprKind::Lit(Spanned {
 204                                             node: LitKind::Int(_, LitIntType::Unsuffixed),
 205                                             ..
 206                                         }) = rhs.kind
 207                                         {
 208                                             ty = None;
 209                                         } else {
 210                                             ty = self.cx.typeck_results().expr_ty_opt(rhs);
 211                                         }
 212                                     }
 213
 214                                     InitializeVisitorState::Initialized {
 215                                         initializer: rhs,
 216                                         ty,
 217                                         name,
 218                                     }
 219                                 },
 220                                 InitializeVisitorState::Initialized { ty, name, .. } => {
 221                                     InitializeVisitorState::Initialized {
 222                                         initializer: rhs,
 223                                         ty,
 224                                         name,
 225                                     }
 226                                 },
 227                                 _ => InitializeVisitorState::DontWarn,
 228                             }
 229                         } else {
 230                             InitializeVisitorState::DontWarn
 231                         }
 232                     },
 233                     ExprKind::AddrOf(BorrowKind::Ref, mutability, _) if mutability == Mutability::Mut => {
 234                         self.state = InitializeVisitorState::DontWarn;
 235                     },
 236                     _ => (),
 237                 }
 238             }
 239
 240             walk_expr(self, expr);
 241         } else if !self.past_loop && is_loop(expr) {
 242             self.state = InitializeVisitorState::DontWarn;
 243         } else if is_conditional(expr) {
 244             self.depth += 1;
 245             walk_expr(self, expr);
 246             self.depth -= 1;
 247         } else {
 248             walk_expr(self, expr);
 249         }
 250     }
 251
 252     fn nested_visit_map(&mut self) -> Self::Map {
 253         self.cx.tcx.hir()
 254     }
 255 }
 256
 257 fn is_loop(expr: &Expr<'_>) -> bool {
 258     matches!(expr.kind, ExprKind::Loop(..))
 259 }
 260
 261 fn is_conditional(expr: &Expr<'_>) -> bool {
 262     matches!(expr.kind, ExprKind::If(..) | ExprKind::Match(..))
 263 }
 264
 265 #[derive(PartialEq, Eq)]
 266 pub(super) enum Nesting {
 267     Unknown,     // no nesting detected yet
 268     RuledOut,    // the iterator is initialized or assigned within scope
 269     LookFurther, // no nesting detected, no further walk required
 270 }
 271
 272 use self::Nesting::{LookFurther, RuledOut, Unknown};
 273
 274 pub(super) struct LoopNestVisitor {
 275     pub(super) hir_id: HirId,
 276     pub(super) iterator: HirId,
 277     pub(super) nesting: Nesting,
 278 }
 279
 280 impl<'tcx> Visitor<'tcx> for LoopNestVisitor {
 281     fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
 282         if stmt.hir_id == self.hir_id {
 283             self.nesting = LookFurther;
 284         } else if self.nesting == Unknown {
 285             walk_stmt(self, stmt);
 286         }
 287     }
 288
 289     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
 290         if self.nesting != Unknown {
 291             return;
 292         }
 293         if expr.hir_id == self.hir_id {
 294             self.nesting = LookFurther;
 295             return;
 296         }
 297         match expr.kind {
 298             ExprKind::Assign(path, _, _) | ExprKind::AssignOp(_, path, _) => {
 299                 if path_to_local_id(path, self.iterator) {
 300                     self.nesting = RuledOut;
 301                 }
 302             },
 303             _ => walk_expr(self, expr),
 304         }
 305     }
 306
 307     fn visit_pat(&mut self, pat: &'tcx Pat<'_>) {
 308         if self.nesting != Unknown {
 309             return;
 310         }
 311         if let PatKind::Binding(_, id, ..) = pat.kind {
 312             if id == self.iterator {
 313                 self.nesting = RuledOut;
 314                 return;
 315             }
 316         }
 317         walk_pat(self, pat);
 318     }
 319 }
 320
 321 /// If `arg` was the argument to a `for` loop, return the "cleanest" way of writing the
 322 /// actual `Iterator` that the loop uses.
 323 pub(super) fn make_iterator_snippet(cx: &LateContext<'_>, arg: &Expr<'_>, applic_ref: &mut Applicability) -> String {
 324     let impls_iterator = cx.tcx.get_diagnostic_item(sym::Iterator).map_or(false, |id| {
 325         implements_trait(cx, cx.typeck_results().expr_ty(arg), id, &[])
 326     });
 327     if impls_iterator {
 328         format!(
 329             "{}",
 330             sugg::Sugg::hir_with_applicability(cx, arg, "_", applic_ref).maybe_par()
 331         )
 332     } else {
 333         // (&x).into_iter() ==> x.iter()
 334         // (&mut x).into_iter() ==> x.iter_mut()
 335         let arg_ty = cx.typeck_results().expr_ty_adjusted(arg);
 336         match &arg_ty.kind() {
 337             ty::Ref(_, inner_ty, mutbl) if has_iter_method(cx, *inner_ty).is_some() => {
 338                 let method_name = match mutbl {
 339                     Mutability::Mut => "iter_mut",
 340                     Mutability::Not => "iter",
 341                 };
 342                 let caller = match &arg.kind {
 343                     ExprKind::AddrOf(BorrowKind::Ref, _, arg_inner) => arg_inner,
 344                     _ => arg,
 345                 };
 346                 format!(
 347                     "{}.{}()",
 348                     sugg::Sugg::hir_with_applicability(cx, caller, "_", applic_ref).maybe_par(),
 349                     method_name,
 350                 )
 351             },
 352             _ => format!(
 353                 "{}.into_iter()",
 354                 sugg::Sugg::hir_with_applicability(cx, arg, "_", applic_ref).maybe_par()
 355             ),
 356         }
 357     }
 358 }