src/tools/clippy/clippy_lints/src/methods/needless_collect.rs

   1 use super::NEEDLESS_COLLECT;
   2 use clippy_utils::diagnostics::{span_lint_and_sugg, span_lint_hir_and_then};
   3 use clippy_utils::higher;
   4 use clippy_utils::source::{snippet, snippet_with_applicability};
   5 use clippy_utils::sugg::Sugg;
   6 use clippy_utils::ty::{is_type_diagnostic_item, make_normalized_projection, make_projection};
   7 use clippy_utils::{
   8     can_move_expr_to_closure, get_enclosing_block, get_parent_node, is_trait_method, path_to_local, path_to_local_id,
   9     CaptureKind,
  10 };
  11 use rustc_data_structures::fx::FxHashMap;
  12 use rustc_errors::{Applicability, MultiSpan};
  13 use rustc_hir::intravisit::{walk_block, walk_expr, Visitor};
  14 use rustc_hir::{
  15     BindingAnnotation, Block, Expr, ExprKind, HirId, HirIdSet, Local, Mutability, Node, PatKind, Stmt, StmtKind,
  16 };
  17 use rustc_lint::LateContext;
  18 use rustc_middle::hir::nested_filter;
  19 use rustc_middle::ty::{self, AssocKind, EarlyBinder, GenericArg, GenericArgKind, Ty};
  20 use rustc_span::symbol::Ident;
  21 use rustc_span::{sym, Span, Symbol};
  22
  23 const NEEDLESS_COLLECT_MSG: &str = "avoid using `collect()` when not needed";
  24
  25 pub(super) fn check<'tcx>(
  26     cx: &LateContext<'tcx>,
  27     name_span: Span,
  28     collect_expr: &'tcx Expr<'_>,
  29     iter_expr: &'tcx Expr<'tcx>,
  30     call_span: Span,
  31 ) {
  32     if let Some(parent) = get_parent_node(cx.tcx, collect_expr.hir_id) {
  33         match parent {
  34             Node::Expr(parent) => {
  35                 if let ExprKind::MethodCall(name, _, args @ ([] | [_]), _) = parent.kind {
  36                     let mut app = Applicability::MachineApplicable;
  37                     let name = name.ident.as_str();
  38                     let collect_ty = cx.typeck_results().expr_ty(collect_expr);
  39
  40                     let sugg: String = match name {
  41                         "len" => {
  42                             if let Some(adt) = collect_ty.ty_adt_def()
  43                                 && matches!(
  44                                     cx.tcx.get_diagnostic_name(adt.did()),
  45                                     Some(sym::Vec | sym::VecDeque | sym::LinkedList | sym::BinaryHeap)
  46                                 )
  47                             {
  48                                 "count()".into()
  49                             } else {
  50                                 return;
  51                             }
  52                         },
  53                         "is_empty"
  54                             if is_is_empty_sig(cx, parent.hir_id)
  55                                 && iterates_same_ty(cx, cx.typeck_results().expr_ty(iter_expr), collect_ty) =>
  56                         {
  57                             "next().is_none()".into()
  58                         },
  59                         "contains" => {
  60                             if is_contains_sig(cx, parent.hir_id, iter_expr)
  61                                 && let Some(arg) = args.first()
  62                             {
  63                                 let (span, prefix) = if let ExprKind::AddrOf(_, _, arg) = arg.kind {
  64                                     (arg.span, "")
  65                                 } else {
  66                                     (arg.span, "*")
  67                                 };
  68                                 let snip = snippet_with_applicability(cx, span, "??", &mut app);
  69                                 format!("any(|x| x == {prefix}{snip})")
  70                             } else {
  71                                 return;
  72                             }
  73                         },
  74                         _ => return,
  75                     };
  76
  77                     span_lint_and_sugg(
  78                         cx,
  79                         NEEDLESS_COLLECT,
  80                         call_span.with_hi(parent.span.hi()),
  81                         NEEDLESS_COLLECT_MSG,
  82                         "replace with",
  83                         sugg,
  84                         app,
  85                     );
  86                 }
  87             },
  88             Node::Local(l) => {
  89                 if let PatKind::Binding(BindingAnnotation::NONE | BindingAnnotation::MUT, id, _, None)
  90                     = l.pat.kind
  91                     && let ty = cx.typeck_results().expr_ty(collect_expr)
  92                     && [sym::Vec, sym::VecDeque, sym::BinaryHeap, sym::LinkedList].into_iter()
  93                         .any(|item| is_type_diagnostic_item(cx, ty, item))
  94                     && let iter_ty = cx.typeck_results().expr_ty(iter_expr)
  95                     && let Some(block) = get_enclosing_block(cx, l.hir_id)
  96                     && let Some(iter_calls) = detect_iter_and_into_iters(block, id, cx, get_captured_ids(cx, iter_ty))
  97                     && let [iter_call] = &*iter_calls
  98                 {
  99                     let mut used_count_visitor = UsedCountVisitor {
 100                         cx,
 101                         id,
 102                         count: 0,
 103                     };
 104                     walk_block(&mut used_count_visitor, block);
 105                     if used_count_visitor.count > 1 {
 106                         return;
 107                     }
 108
 109                     // Suggest replacing iter_call with iter_replacement, and removing stmt
 110                     let mut span = MultiSpan::from_span(name_span);
 111                     span.push_span_label(iter_call.span, "the iterator could be used here instead");
 112                     span_lint_hir_and_then(
 113                         cx,
 114                         super::NEEDLESS_COLLECT,
 115                         collect_expr.hir_id,
 116                         span,
 117                         NEEDLESS_COLLECT_MSG,
 118                         |diag| {
 119                             let iter_replacement = format!("{}{}", Sugg::hir(cx, iter_expr, ".."), iter_call.get_iter_method(cx));
 120                             diag.multipart_suggestion(
 121                                 iter_call.get_suggestion_text(),
 122                                 vec![
 123                                     (l.span, String::new()),
 124                                     (iter_call.span, iter_replacement)
 125                                 ],
 126                                 Applicability::MaybeIncorrect,
 127                             );
 128                         },
 129                     );
 130                 }
 131             },
 132             _ => (),
 133         }
 134     }
 135 }
 136
 137 /// Checks if the given method call matches the expected signature of `([&[mut]] self) -> bool`
 138 fn is_is_empty_sig(cx: &LateContext<'_>, call_id: HirId) -> bool {
 139     cx.typeck_results().type_dependent_def_id(call_id).map_or(false, |id| {
 140         let sig = cx.tcx.fn_sig(id).skip_binder();
 141         sig.inputs().len() == 1 && sig.output().is_bool()
 142     })
 143 }
 144
 145 /// Checks if `<iter_ty as Iterator>::Item` is the same as `<collect_ty as IntoIter>::Item`
 146 fn iterates_same_ty<'tcx>(cx: &LateContext<'tcx>, iter_ty: Ty<'tcx>, collect_ty: Ty<'tcx>) -> bool {
 147     let item = Symbol::intern("Item");
 148     if let Some(iter_trait) = cx.tcx.get_diagnostic_item(sym::Iterator)
 149         && let Some(into_iter_trait) = cx.tcx.get_diagnostic_item(sym::IntoIterator)
 150         && let Some(iter_item_ty) = make_normalized_projection(cx.tcx, cx.param_env, iter_trait, item, [iter_ty])
 151         && let Some(into_iter_item_proj) = make_projection(cx.tcx, into_iter_trait, item, [collect_ty])
 152         && let Ok(into_iter_item_ty) = cx.tcx.try_normalize_erasing_regions(
 153             cx.param_env,
 154             cx.tcx.mk_projection(into_iter_item_proj.def_id, into_iter_item_proj.substs)
 155         )
 156     {
 157         iter_item_ty == into_iter_item_ty
 158     } else {
 159         false
 160     }
 161 }
 162
 163 /// Checks if the given method call matches the expected signature of
 164 /// `([&[mut]] self, &<iter_ty as Iterator>::Item) -> bool`
 165 fn is_contains_sig(cx: &LateContext<'_>, call_id: HirId, iter_expr: &Expr<'_>) -> bool {
 166     let typeck = cx.typeck_results();
 167     if let Some(id) = typeck.type_dependent_def_id(call_id)
 168         && let sig = cx.tcx.fn_sig(id)
 169         && sig.skip_binder().output().is_bool()
 170         && let [_, search_ty] = *sig.skip_binder().inputs()
 171         && let ty::Ref(_, search_ty, Mutability::Not) = *cx.tcx.erase_late_bound_regions(sig.rebind(search_ty)).kind()
 172         && let Some(iter_trait) = cx.tcx.get_diagnostic_item(sym::Iterator)
 173         && let Some(iter_item) = cx.tcx
 174             .associated_items(iter_trait)
 175             .find_by_name_and_kind(cx.tcx, Ident::with_dummy_span(Symbol::intern("Item")), AssocKind::Type, iter_trait)
 176         && let substs = cx.tcx.mk_substs([GenericArg::from(typeck.expr_ty_adjusted(iter_expr))].into_iter())
 177         && let proj_ty = cx.tcx.mk_projection(iter_item.def_id, substs)
 178         && let Ok(item_ty) = cx.tcx.try_normalize_erasing_regions(cx.param_env, proj_ty)
 179     {
 180         item_ty == EarlyBinder(search_ty).subst(cx.tcx, cx.typeck_results().node_substs(call_id))
 181     } else {
 182         false
 183     }
 184 }
 185
 186 struct IterFunction {
 187     func: IterFunctionKind,
 188     span: Span,
 189 }
 190 impl IterFunction {
 191     fn get_iter_method(&self, cx: &LateContext<'_>) -> String {
 192         match &self.func {
 193             IterFunctionKind::IntoIter => String::new(),
 194             IterFunctionKind::Len => String::from(".count()"),
 195             IterFunctionKind::IsEmpty => String::from(".next().is_none()"),
 196             IterFunctionKind::Contains(span) => {
 197                 let s = snippet(cx, *span, "..");
 198                 if let Some(stripped) = s.strip_prefix('&') {
 199                     format!(".any(|x| x == {stripped})")
 200                 } else {
 201                     format!(".any(|x| x == *{s})")
 202                 }
 203             },
 204         }
 205     }
 206     fn get_suggestion_text(&self) -> &'static str {
 207         match &self.func {
 208             IterFunctionKind::IntoIter => {
 209                 "use the original Iterator instead of collecting it and then producing a new one"
 210             },
 211             IterFunctionKind::Len => {
 212                 "take the original Iterator's count instead of collecting it and finding the length"
 213             },
 214             IterFunctionKind::IsEmpty => {
 215                 "check if the original Iterator has anything instead of collecting it and seeing if it's empty"
 216             },
 217             IterFunctionKind::Contains(_) => {
 218                 "check if the original Iterator contains an element instead of collecting then checking"
 219             },
 220         }
 221     }
 222 }
 223 enum IterFunctionKind {
 224     IntoIter,
 225     Len,
 226     IsEmpty,
 227     Contains(Span),
 228 }
 229
 230 struct IterFunctionVisitor<'a, 'tcx> {
 231     illegal_mutable_capture_ids: HirIdSet,
 232     current_mutably_captured_ids: HirIdSet,
 233     cx: &'a LateContext<'tcx>,
 234     uses: Vec<Option<IterFunction>>,
 235     hir_id_uses_map: FxHashMap<HirId, usize>,
 236     current_statement_hir_id: Option<HirId>,
 237     seen_other: bool,
 238     target: HirId,
 239 }
 240 impl<'tcx> Visitor<'tcx> for IterFunctionVisitor<'_, 'tcx> {
 241     fn visit_block(&mut self, block: &'tcx Block<'tcx>) {
 242         for (expr, hir_id) in block.stmts.iter().filter_map(get_expr_and_hir_id_from_stmt) {
 243             if check_loop_kind(expr).is_some() {
 244                 continue;
 245             }
 246             self.visit_block_expr(expr, hir_id);
 247         }
 248         if let Some(expr) = block.expr {
 249             if let Some(loop_kind) = check_loop_kind(expr) {
 250                 if let LoopKind::Conditional(block_expr) = loop_kind {
 251                     self.visit_block_expr(block_expr, None);
 252                 }
 253             } else {
 254                 self.visit_block_expr(expr, None);
 255             }
 256         }
 257     }
 258
 259     fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
 260         // Check function calls on our collection
 261         if let ExprKind::MethodCall(method_name, recv, [args @ ..], _) = &expr.kind {
 262             if method_name.ident.name == sym!(collect) && is_trait_method(self.cx, expr, sym::Iterator) {
 263                 self.current_mutably_captured_ids = get_captured_ids(self.cx, self.cx.typeck_results().expr_ty(recv));
 264                 self.visit_expr(recv);
 265                 return;
 266             }
 267
 268             if path_to_local_id(recv, self.target) {
 269                 if self
 270                     .illegal_mutable_capture_ids
 271                     .intersection(&self.current_mutably_captured_ids)
 272                     .next()
 273                     .is_none()
 274                 {
 275                     if let Some(hir_id) = self.current_statement_hir_id {
 276                         self.hir_id_uses_map.insert(hir_id, self.uses.len());
 277                     }
 278                     match method_name.ident.name.as_str() {
 279                         "into_iter" => self.uses.push(Some(IterFunction {
 280                             func: IterFunctionKind::IntoIter,
 281                             span: expr.span,
 282                         })),
 283                         "len" => self.uses.push(Some(IterFunction {
 284                             func: IterFunctionKind::Len,
 285                             span: expr.span,
 286                         })),
 287                         "is_empty" => self.uses.push(Some(IterFunction {
 288                             func: IterFunctionKind::IsEmpty,
 289                             span: expr.span,
 290                         })),
 291                         "contains" => self.uses.push(Some(IterFunction {
 292                             func: IterFunctionKind::Contains(args[0].span),
 293                             span: expr.span,
 294                         })),
 295                         _ => {
 296                             self.seen_other = true;
 297                             if let Some(hir_id) = self.current_statement_hir_id {
 298                                 self.hir_id_uses_map.remove(&hir_id);
 299                             }
 300                         },
 301                     }
 302                 }
 303                 return;
 304             }
 305
 306             if let Some(hir_id) = path_to_local(recv) {
 307                 if let Some(index) = self.hir_id_uses_map.remove(&hir_id) {
 308                     if self
 309                         .illegal_mutable_capture_ids
 310                         .intersection(&self.current_mutably_captured_ids)
 311                         .next()
 312                         .is_none()
 313                     {
 314                         if let Some(hir_id) = self.current_statement_hir_id {
 315                             self.hir_id_uses_map.insert(hir_id, index);
 316                         }
 317                     } else {
 318                         self.uses[index] = None;
 319                     }
 320                 }
 321             }
 322         }
 323         // Check if the collection is used for anything else
 324         if path_to_local_id(expr, self.target) {
 325             self.seen_other = true;
 326         } else {
 327             walk_expr(self, expr);
 328         }
 329     }
 330 }
 331
 332 enum LoopKind<'tcx> {
 333     Conditional(&'tcx Expr<'tcx>),
 334     Loop,
 335 }
 336
 337 fn check_loop_kind<'tcx>(expr: &Expr<'tcx>) -> Option<LoopKind<'tcx>> {
 338     if let Some(higher::WhileLet { let_expr, .. }) = higher::WhileLet::hir(expr) {
 339         return Some(LoopKind::Conditional(let_expr));
 340     }
 341     if let Some(higher::While { condition, .. }) = higher::While::hir(expr) {
 342         return Some(LoopKind::Conditional(condition));
 343     }
 344     if let Some(higher::ForLoop { arg, .. }) = higher::ForLoop::hir(expr) {
 345         return Some(LoopKind::Conditional(arg));
 346     }
 347     if let ExprKind::Loop { .. } = expr.kind {
 348         return Some(LoopKind::Loop);
 349     }
 350
 351     None
 352 }
 353
 354 impl<'tcx> IterFunctionVisitor<'_, 'tcx> {
 355     fn visit_block_expr(&mut self, expr: &'tcx Expr<'tcx>, hir_id: Option<HirId>) {
 356         self.current_statement_hir_id = hir_id;
 357         self.current_mutably_captured_ids = get_captured_ids(self.cx, self.cx.typeck_results().expr_ty(expr));
 358         self.visit_expr(expr);
 359     }
 360 }
 361
 362 fn get_expr_and_hir_id_from_stmt<'v>(stmt: &'v Stmt<'v>) -> Option<(&'v Expr<'v>, Option<HirId>)> {
 363     match stmt.kind {
 364         StmtKind::Expr(expr) | StmtKind::Semi(expr) => Some((expr, None)),
 365         StmtKind::Item(..) => None,
 366         StmtKind::Local(Local { init, pat, .. }) => {
 367             if let PatKind::Binding(_, hir_id, ..) = pat.kind {
 368                 init.map(|init_expr| (init_expr, Some(hir_id)))
 369             } else {
 370                 init.map(|init_expr| (init_expr, None))
 371             }
 372         },
 373     }
 374 }
 375
 376 struct UsedCountVisitor<'a, 'tcx> {
 377     cx: &'a LateContext<'tcx>,
 378     id: HirId,
 379     count: usize,
 380 }
 381
 382 impl<'a, 'tcx> Visitor<'tcx> for UsedCountVisitor<'a, 'tcx> {
 383     type NestedFilter = nested_filter::OnlyBodies;
 384
 385     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
 386         if path_to_local_id(expr, self.id) {
 387             self.count += 1;
 388         } else {
 389             walk_expr(self, expr);
 390         }
 391     }
 392
 393     fn nested_visit_map(&mut self) -> Self::Map {
 394         self.cx.tcx.hir()
 395     }
 396 }
 397
 398 /// Detect the occurrences of calls to `iter` or `into_iter` for the
 399 /// given identifier
 400 fn detect_iter_and_into_iters<'tcx: 'a, 'a>(
 401     block: &'tcx Block<'tcx>,
 402     id: HirId,
 403     cx: &'a LateContext<'tcx>,
 404     captured_ids: HirIdSet,
 405 ) -> Option<Vec<IterFunction>> {
 406     let mut visitor = IterFunctionVisitor {
 407         uses: Vec::new(),
 408         target: id,
 409         seen_other: false,
 410         cx,
 411         current_mutably_captured_ids: HirIdSet::default(),
 412         illegal_mutable_capture_ids: captured_ids,
 413         hir_id_uses_map: FxHashMap::default(),
 414         current_statement_hir_id: None,
 415     };
 416     visitor.visit_block(block);
 417     if visitor.seen_other {
 418         None
 419     } else {
 420         Some(visitor.uses.into_iter().flatten().collect())
 421     }
 422 }
 423
 424 fn get_captured_ids(cx: &LateContext<'_>, ty: Ty<'_>) -> HirIdSet {
 425     fn get_captured_ids_recursive(cx: &LateContext<'_>, ty: Ty<'_>, set: &mut HirIdSet) {
 426         match ty.kind() {
 427             ty::Adt(_, generics) => {
 428                 for generic in *generics {
 429                     if let GenericArgKind::Type(ty) = generic.unpack() {
 430                         get_captured_ids_recursive(cx, ty, set);
 431                     }
 432                 }
 433             },
 434             ty::Closure(def_id, _) => {
 435                 let closure_hir_node = cx.tcx.hir().get_if_local(*def_id).unwrap();
 436                 if let Node::Expr(closure_expr) = closure_hir_node {
 437                     can_move_expr_to_closure(cx, closure_expr)
 438                         .unwrap()
 439                         .into_iter()
 440                         .for_each(|(hir_id, capture_kind)| {
 441                             if matches!(capture_kind, CaptureKind::Ref(Mutability::Mut)) {
 442                                 set.insert(hir_id);
 443                             }
 444                         });
 445                 }
 446             },
 447             _ => (),
 448         }
 449     }
 450
 451     let mut set = HirIdSet::default();
 452
 453     get_captured_ids_recursive(cx, ty, &mut set);
 454
 455     set
 456 }