compiler/rustc_typeck/src/check/method/suggest.rs

   1 //! Give useful errors and suggestions to users when an item can't be
   2 //! found or is otherwise invalid.
   3
   4 use crate::check::FnCtxt;
   5 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   6 use rustc_errors::{pluralize, struct_span_err, Applicability, DiagnosticBuilder};
   7 use rustc_hir as hir;
   8 use rustc_hir::def_id::{DefId, LocalDefId};
   9 use rustc_hir::lang_items::LangItem;
  10 use rustc_hir::{ExprKind, Node, QPath};
  11 use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
  12 use rustc_middle::ty::fast_reject::{simplify_type, SimplifyParams};
  13 use rustc_middle::ty::print::with_crate_prefix;
  14 use rustc_middle::ty::{self, DefIdTree, ToPredicate, Ty, TyCtxt, TypeFoldable};
  15 use rustc_span::lev_distance;
  16 use rustc_span::symbol::{kw, sym, Ident};
  17 use rustc_span::{source_map, FileName, MultiSpan, Span};
  18 use rustc_trait_selection::traits::query::evaluate_obligation::InferCtxtExt;
  19 use rustc_trait_selection::traits::{
  20     FulfillmentError, Obligation, ObligationCause, ObligationCauseCode,
  21 };
  22
  23 use std::cmp::Ordering;
  24 use std::iter;
  25
  26 use super::probe::Mode;
  27 use super::{CandidateSource, MethodError, NoMatchData};
  28
  29 impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
  30     fn is_fn_ty(&self, ty: Ty<'tcx>, span: Span) -> bool {
  31         let tcx = self.tcx;
  32         match ty.kind() {
  33             // Not all of these (e.g., unsafe fns) implement `FnOnce`,
  34             // so we look for these beforehand.
  35             ty::Closure(..) | ty::FnDef(..) | ty::FnPtr(_) => true,
  36             // If it's not a simple function, look for things which implement `FnOnce`.
  37             _ => {
  38                 let fn_once = match tcx.lang_items().require(LangItem::FnOnce) {
  39                     Ok(fn_once) => fn_once,
  40                     Err(..) => return false,
  41                 };
  42
  43                 self.autoderef(span, ty).any(|(ty, _)| {
  44                     self.probe(|_| {
  45                         let fn_once_substs = tcx.mk_substs_trait(
  46                             ty,
  47                             &[self
  48                                 .next_ty_var(TypeVariableOrigin {
  49                                     kind: TypeVariableOriginKind::MiscVariable,
  50                                     span,
  51                                 })
  52                                 .into()],
  53                         );
  54                         let trait_ref = ty::TraitRef::new(fn_once, fn_once_substs);
  55                         let poly_trait_ref = ty::Binder::dummy(trait_ref);
  56                         let obligation = Obligation::misc(
  57                             span,
  58                             self.body_id,
  59                             self.param_env,
  60                             poly_trait_ref.without_const().to_predicate(tcx),
  61                         );
  62                         self.predicate_may_hold(&obligation)
  63                     })
  64                 })
  65             }
  66         }
  67     }
  68
  69     fn is_slice_ty(&self, ty: Ty<'tcx>, span: Span) -> bool {
  70         self.autoderef(span, ty).any(|(ty, _)| matches!(ty.kind(), ty::Slice(..) | ty::Array(..)))
  71     }
  72
  73     pub fn report_method_error(
  74         &self,
  75         mut span: Span,
  76         rcvr_ty: Ty<'tcx>,
  77         item_name: Ident,
  78         source: SelfSource<'tcx>,
  79         error: MethodError<'tcx>,
  80         args: Option<&'tcx [hir::Expr<'tcx>]>,
  81     ) -> Option<DiagnosticBuilder<'_>> {
  82         // Avoid suggestions when we don't know what's going on.
  83         if rcvr_ty.references_error() {
  84             return None;
  85         }
  86
  87         let report_candidates = |span: Span,
  88                                  err: &mut DiagnosticBuilder<'_>,
  89                                  mut sources: Vec<CandidateSource>,
  90                                  sugg_span: Span| {
  91             sources.sort();
  92             sources.dedup();
  93             // Dynamic limit to avoid hiding just one candidate, which is silly.
  94             let limit = if sources.len() == 5 { 5 } else { 4 };
  95
  96             for (idx, source) in sources.iter().take(limit).enumerate() {
  97                 match *source {
  98                     CandidateSource::ImplSource(impl_did) => {
  99                         // Provide the best span we can. Use the item, if local to crate, else
 100                         // the impl, if local to crate (item may be defaulted), else nothing.
 101                         let item = match self.associated_value(impl_did, item_name).or_else(|| {
 102                             let impl_trait_ref = self.tcx.impl_trait_ref(impl_did)?;
 103                             self.associated_value(impl_trait_ref.def_id, item_name)
 104                         }) {
 105                             Some(item) => item,
 106                             None => continue,
 107                         };
 108                         let note_span = self
 109                             .tcx
 110                             .hir()
 111                             .span_if_local(item.def_id)
 112                             .or_else(|| self.tcx.hir().span_if_local(impl_did));
 113
 114                         let impl_ty = self.tcx.at(span).type_of(impl_did);
 115
 116                         let insertion = match self.tcx.impl_trait_ref(impl_did) {
 117                             None => String::new(),
 118                             Some(trait_ref) => format!(
 119                                 " of the trait `{}`",
 120                                 self.tcx.def_path_str(trait_ref.def_id)
 121                             ),
 122                         };
 123
 124                         let (note_str, idx) = if sources.len() > 1 {
 125                             (
 126                                 format!(
 127                                     "candidate #{} is defined in an impl{} for the type `{}`",
 128                                     idx + 1,
 129                                     insertion,
 130                                     impl_ty,
 131                                 ),
 132                                 Some(idx + 1),
 133                             )
 134                         } else {
 135                             (
 136                                 format!(
 137                                     "the candidate is defined in an impl{} for the type `{}`",
 138                                     insertion, impl_ty,
 139                                 ),
 140                                 None,
 141                             )
 142                         };
 143                         if let Some(note_span) = note_span {
 144                             // We have a span pointing to the method. Show note with snippet.
 145                             err.span_note(
 146                                 self.tcx.sess.source_map().guess_head_span(note_span),
 147                                 &note_str,
 148                             );
 149                         } else {
 150                             err.note(&note_str);
 151                         }
 152                         if let Some(trait_ref) = self.tcx.impl_trait_ref(impl_did) {
 153                             let path = self.tcx.def_path_str(trait_ref.def_id);
 154
 155                             let ty = match item.kind {
 156                                 ty::AssocKind::Const | ty::AssocKind::Type => rcvr_ty,
 157                                 ty::AssocKind::Fn => self
 158                                     .tcx
 159                                     .fn_sig(item.def_id)
 160                                     .inputs()
 161                                     .skip_binder()
 162                                     .get(0)
 163                                     .filter(|ty| ty.is_region_ptr() && !rcvr_ty.is_region_ptr())
 164                                     .copied()
 165                                     .unwrap_or(rcvr_ty),
 166                             };
 167                             print_disambiguation_help(
 168                                 item_name,
 169                                 args,
 170                                 err,
 171                                 path,
 172                                 ty,
 173                                 item.kind,
 174                                 item.def_id,
 175                                 sugg_span,
 176                                 idx,
 177                                 self.tcx.sess.source_map(),
 178                                 item.fn_has_self_parameter,
 179                             );
 180                         }
 181                     }
 182                     CandidateSource::TraitSource(trait_did) => {
 183                         let item = match self.associated_value(trait_did, item_name) {
 184                             Some(item) => item,
 185                             None => continue,
 186                         };
 187                         let item_span = self
 188                             .tcx
 189                             .sess
 190                             .source_map()
 191                             .guess_head_span(self.tcx.def_span(item.def_id));
 192                         let idx = if sources.len() > 1 {
 193                             let msg = &format!(
 194                                 "candidate #{} is defined in the trait `{}`",
 195                                 idx + 1,
 196                                 self.tcx.def_path_str(trait_did)
 197                             );
 198                             err.span_note(item_span, msg);
 199                             Some(idx + 1)
 200                         } else {
 201                             let msg = &format!(
 202                                 "the candidate is defined in the trait `{}`",
 203                                 self.tcx.def_path_str(trait_did)
 204                             );
 205                             err.span_note(item_span, msg);
 206                             None
 207                         };
 208                         let path = self.tcx.def_path_str(trait_did);
 209                         print_disambiguation_help(
 210                             item_name,
 211                             args,
 212                             err,
 213                             path,
 214                             rcvr_ty,
 215                             item.kind,
 216                             item.def_id,
 217                             sugg_span,
 218                             idx,
 219                             self.tcx.sess.source_map(),
 220                             item.fn_has_self_parameter,
 221                         );
 222                     }
 223                 }
 224             }
 225             if sources.len() > limit {
 226                 err.note(&format!("and {} others", sources.len() - limit));
 227             }
 228         };
 229
 230         let sugg_span = if let SelfSource::MethodCall(expr) = source {
 231             // Given `foo.bar(baz)`, `expr` is `bar`, but we want to point to the whole thing.
 232             self.tcx.hir().expect_expr(self.tcx.hir().get_parent_node(expr.hir_id)).span
 233         } else {
 234             span
 235         };
 236
 237         match error {
 238             MethodError::NoMatch(NoMatchData {
 239                 static_candidates: static_sources,
 240                 unsatisfied_predicates,
 241                 out_of_scope_traits,
 242                 lev_candidate,
 243                 mode,
 244             }) => {
 245                 let tcx = self.tcx;
 246
 247                 let actual = self.resolve_vars_if_possible(rcvr_ty);
 248                 let ty_str = self.ty_to_string(actual);
 249                 let is_method = mode == Mode::MethodCall;
 250                 let item_kind = if is_method {
 251                     "method"
 252                 } else if actual.is_enum() {
 253                     "variant or associated item"
 254                 } else {
 255                     match (item_name.as_str().chars().next(), actual.is_fresh_ty()) {
 256                         (Some(name), false) if name.is_lowercase() => "function or associated item",
 257                         (Some(_), false) => "associated item",
 258                         (Some(_), true) | (None, false) => "variant or associated item",
 259                         (None, true) => "variant",
 260                     }
 261                 };
 262                 let mut err = if !actual.references_error() {
 263                     // Suggest clamping down the type if the method that is being attempted to
 264                     // be used exists at all, and the type is an ambiguous numeric type
 265                     // ({integer}/{float}).
 266                     let mut candidates = all_traits(self.tcx)
 267                         .into_iter()
 268                         .filter_map(|info| self.associated_value(info.def_id, item_name));
 269                     // There are methods that are defined on the primitive types and won't be
 270                     // found when exploring `all_traits`, but we also need them to be acurate on
 271                     // our suggestions (#47759).
 272                     let fund_assoc = |opt_def_id: Option<DefId>| {
 273                         opt_def_id.and_then(|id| self.associated_value(id, item_name)).is_some()
 274                     };
 275                     let lang_items = tcx.lang_items();
 276                     let found_candidate = candidates.next().is_some()
 277                         || fund_assoc(lang_items.i8_impl())
 278                         || fund_assoc(lang_items.i16_impl())
 279                         || fund_assoc(lang_items.i32_impl())
 280                         || fund_assoc(lang_items.i64_impl())
 281                         || fund_assoc(lang_items.i128_impl())
 282                         || fund_assoc(lang_items.u8_impl())
 283                         || fund_assoc(lang_items.u16_impl())
 284                         || fund_assoc(lang_items.u32_impl())
 285                         || fund_assoc(lang_items.u64_impl())
 286                         || fund_assoc(lang_items.u128_impl())
 287                         || fund_assoc(lang_items.f32_impl())
 288                         || fund_assoc(lang_items.f32_runtime_impl())
 289                         || fund_assoc(lang_items.f64_impl())
 290                         || fund_assoc(lang_items.f64_runtime_impl());
 291                     if let (true, false, SelfSource::MethodCall(expr), true) = (
 292                         actual.is_numeric(),
 293                         actual.has_concrete_skeleton(),
 294                         source,
 295                         found_candidate,
 296                     ) {
 297                         let mut err = struct_span_err!(
 298                             tcx.sess,
 299                             span,
 300                             E0689,
 301                             "can't call {} `{}` on ambiguous numeric type `{}`",
 302                             item_kind,
 303                             item_name,
 304                             ty_str
 305                         );
 306                         let concrete_type = if actual.is_integral() { "i32" } else { "f32" };
 307                         match expr.kind {
 308                             ExprKind::Lit(ref lit) => {
 309                                 // numeric literal
 310                                 let snippet = tcx
 311                                     .sess
 312                                     .source_map()
 313                                     .span_to_snippet(lit.span)
 314                                     .unwrap_or_else(|_| "<numeric literal>".to_owned());
 315
 316                                 // If this is a floating point literal that ends with '.',
 317                                 // get rid of it to stop this from becoming a member access.
 318                                 let snippet = snippet.strip_suffix('.').unwrap_or(&snippet);
 319
 320                                 err.span_suggestion(
 321                                     lit.span,
 322                                     &format!(
 323                                         "you must specify a concrete type for this numeric value, \
 324                                          like `{}`",
 325                                         concrete_type
 326                                     ),
 327                                     format!("{snippet}_{concrete_type}"),
 328                                     Applicability::MaybeIncorrect,
 329                                 );
 330                             }
 331                             ExprKind::Path(QPath::Resolved(_, path)) => {
 332                                 // local binding
 333                                 if let hir::def::Res::Local(hir_id) = path.res {
 334                                     let span = tcx.hir().span(hir_id);
 335                                     let snippet = tcx.sess.source_map().span_to_snippet(span);
 336                                     let filename = tcx.sess.source_map().span_to_filename(span);
 337
 338                                     let parent_node =
 339                                         self.tcx.hir().get(self.tcx.hir().get_parent_node(hir_id));
 340                                     let msg = format!(
 341                                         "you must specify a type for this binding, like `{}`",
 342                                         concrete_type,
 343                                     );
 344
 345                                     match (filename, parent_node, snippet) {
 346                                         (
 347                                             FileName::Real(_),
 348                                             Node::Local(hir::Local {
 349                                                 source: hir::LocalSource::Normal,
 350                                                 ty,
 351                                                 ..
 352                                             }),
 353                                             Ok(ref snippet),
 354                                         ) => {
 355                                             err.span_suggestion(
 356                                                 // account for `let x: _ = 42;`
 357                                                 //                  ^^^^
 358                                                 span.to(ty
 359                                                     .as_ref()
 360                                                     .map(|ty| ty.span)
 361                                                     .unwrap_or(span)),
 362                                                 &msg,
 363                                                 format!("{}: {}", snippet, concrete_type),
 364                                                 Applicability::MaybeIncorrect,
 365                                             );
 366                                         }
 367                                         _ => {
 368                                             err.span_label(span, msg);
 369                                         }
 370                                     }
 371                                 }
 372                             }
 373                             _ => {}
 374                         }
 375                         err.emit();
 376                         return None;
 377                     } else {
 378                         span = item_name.span;
 379
 380                         // Don't show generic arguments when the method can't be found in any implementation (#81576).
 381                         let mut ty_str_reported = ty_str.clone();
 382                         if let ty::Adt(_, generics) = actual.kind() {
 383                             if generics.len() > 0 {
 384                                 let mut autoderef = self.autoderef(span, actual);
 385                                 let candidate_found = autoderef.any(|(ty, _)| {
 386                                     if let ty::Adt(adt_deref, _) = ty.kind() {
 387                                         self.tcx
 388                                             .inherent_impls(adt_deref.did)
 389                                             .iter()
 390                                             .filter_map(|def_id| {
 391                                                 self.associated_value(*def_id, item_name)
 392                                             })
 393                                             .count()
 394                                             >= 1
 395                                     } else {
 396                                         false
 397                                     }
 398                                 });
 399                                 let has_deref = autoderef.step_count() > 0;
 400                                 if !candidate_found
 401                                     && !has_deref
 402                                     && unsatisfied_predicates.is_empty()
 403                                 {
 404                                     if let Some((path_string, _)) = ty_str.split_once('<') {
 405                                         ty_str_reported = path_string.to_string();
 406                                     }
 407                                 }
 408                             }
 409                         }
 410
 411                         let mut err = struct_span_err!(
 412                             tcx.sess,
 413                             span,
 414                             E0599,
 415                             "no {} named `{}` found for {} `{}` in the current scope",
 416                             item_kind,
 417                             item_name,
 418                             actual.prefix_string(self.tcx),
 419                             ty_str_reported,
 420                         );
 421                         if let Mode::MethodCall = mode {
 422                             if let SelfSource::MethodCall(call) = source {
 423                                 self.suggest_await_before_method(
 424                                     &mut err, item_name, actual, call, span,
 425                                 );
 426                             }
 427                         }
 428                         if let Some(span) =
 429                             tcx.resolutions(()).confused_type_with_std_module.get(&span)
 430                         {
 431                             if let Ok(snippet) = tcx.sess.source_map().span_to_snippet(*span) {
 432                                 err.span_suggestion(
 433                                     *span,
 434                                     "you are looking for the module in `std`, \
 435                                      not the primitive type",
 436                                     format!("std::{}", snippet),
 437                                     Applicability::MachineApplicable,
 438                                 );
 439                             }
 440                         }
 441                         if let ty::RawPtr(_) = &actual.kind() {
 442                             err.note(
 443                                 "try using `<*const T>::as_ref()` to get a reference to the \
 444                                       type behind the pointer: https://doc.rust-lang.org/std/\
 445                                       primitive.pointer.html#method.as_ref",
 446                             );
 447                             err.note(
 448                                 "using `<*const T>::as_ref()` on a pointer \
 449                                       which is unaligned or points to invalid \
 450                                       or uninitialized memory is undefined behavior",
 451                             );
 452                         }
 453                         err
 454                     }
 455                 } else {
 456                     tcx.sess.diagnostic().struct_dummy()
 457                 };
 458
 459                 if let Some(def) = actual.ty_adt_def() {
 460                     if let Some(full_sp) = tcx.hir().span_if_local(def.did) {
 461                         let def_sp = tcx.sess.source_map().guess_head_span(full_sp);
 462                         err.span_label(
 463                             def_sp,
 464                             format!(
 465                                 "{} `{}` not found {}",
 466                                 item_kind,
 467                                 item_name,
 468                                 if def.is_enum() && !is_method { "here" } else { "for this" }
 469                             ),
 470                         );
 471                     }
 472                 }
 473
 474                 let mut label_span_not_found = || {
 475                     if unsatisfied_predicates.is_empty() {
 476                         err.span_label(span, format!("{item_kind} not found in `{ty_str}`"));
 477                         let is_string_or_ref_str = match actual.kind() {
 478                             ty::Ref(_, ty, _) => {
 479                                 ty.is_str()
 480                                     || matches!(
 481                                         ty.kind(),
 482                                         ty::Adt(adt, _) if self.tcx.is_diagnostic_item(sym::String, adt.did)
 483                                     )
 484                             }
 485                             ty::Adt(adt, _) => self.tcx.is_diagnostic_item(sym::String, adt.did),
 486                             _ => false,
 487                         };
 488                         if is_string_or_ref_str && item_name.name == sym::iter {
 489                             err.span_suggestion_verbose(
 490                                 item_name.span,
 491                                 "because of the in-memory representation of `&str`, to obtain \
 492                                  an `Iterator` over each of its codepoint use method `chars`",
 493                                 String::from("chars"),
 494                                 Applicability::MachineApplicable,
 495                             );
 496                         }
 497                         if let ty::Adt(adt, _) = rcvr_ty.kind() {
 498                             let mut inherent_impls_candidate = self
 499                                 .tcx
 500                                 .inherent_impls(adt.did)
 501                                 .iter()
 502                                 .copied()
 503                                 .filter(|def_id| {
 504                                     if let Some(assoc) = self.associated_value(*def_id, item_name) {
 505                                         // Check for both mode is the same so we avoid suggesting
 506                                         // incorrect associated item.
 507                                         match (mode, assoc.fn_has_self_parameter, source) {
 508                                             (Mode::MethodCall, true, SelfSource::MethodCall(_)) => {
 509                                                 // We check that the suggest type is actually
 510                                                 // different from the received one
 511                                                 // So we avoid suggestion method with Box<Self>
 512                                                 // for instance
 513                                                 self.tcx.at(span).type_of(*def_id) != actual
 514                                                     && self.tcx.at(span).type_of(*def_id) != rcvr_ty
 515                                             }
 516                                             (Mode::Path, false, _) => true,
 517                                             _ => false,
 518                                         }
 519                                     } else {
 520                                         false
 521                                     }
 522                                 })
 523                                 .collect::<Vec<_>>();
 524                             if !inherent_impls_candidate.is_empty() {
 525                                 inherent_impls_candidate.sort();
 526                                 inherent_impls_candidate.dedup();
 527
 528                                 // number of type to shows at most.
 529                                 let limit = if inherent_impls_candidate.len() == 5 { 5 } else { 4 };
 530                                 let type_candidates = inherent_impls_candidate
 531                                     .iter()
 532                                     .take(limit)
 533                                     .map(|impl_item| {
 534                                         format!("- `{}`", self.tcx.at(span).type_of(*impl_item))
 535                                     })
 536                                     .collect::<Vec<_>>()
 537                                     .join("\n");
 538                                 let additional_types = if inherent_impls_candidate.len() > limit {
 539                                     format!(
 540                                         "\nand {} more types",
 541                                         inherent_impls_candidate.len() - limit
 542                                     )
 543                                 } else {
 544                                     "".to_string()
 545                                 };
 546                                 err.note(&format!(
 547                                     "the {item_kind} was found for\n{}{}",
 548                                     type_candidates, additional_types
 549                                 ));
 550                             }
 551                         }
 552                     } else {
 553                         err.span_label(span, format!("{item_kind} cannot be called on `{ty_str}` due to unsatisfied trait bounds"));
 554                     }
 555                 };
 556
 557                 // If the method name is the name of a field with a function or closure type,
 558                 // give a helping note that it has to be called as `(x.f)(...)`.
 559                 if let SelfSource::MethodCall(expr) = source {
 560                     let field_receiver =
 561                         self.autoderef(span, rcvr_ty).find_map(|(ty, _)| match ty.kind() {
 562                             ty::Adt(def, substs) if !def.is_enum() => {
 563                                 let variant = &def.non_enum_variant();
 564                                 self.tcx.find_field_index(item_name, variant).map(|index| {
 565                                     let field = &variant.fields[index];
 566                                     let field_ty = field.ty(tcx, substs);
 567                                     (field, field_ty)
 568                                 })
 569                             }
 570                             _ => None,
 571                         });
 572
 573                     if let Some((field, field_ty)) = field_receiver {
 574                         let scope = self.tcx.parent_module(self.body_id).to_def_id();
 575                         let is_accessible = field.vis.is_accessible_from(scope, self.tcx);
 576
 577                         if is_accessible {
 578                             if self.is_fn_ty(field_ty, span) {
 579                                 let expr_span = expr.span.to(item_name.span);
 580                                 err.multipart_suggestion(
 581                                     &format!(
 582                                         "to call the function stored in `{}`, \
 583                                          surround the field access with parentheses",
 584                                         item_name,
 585                                     ),
 586                                     vec![
 587                                         (expr_span.shrink_to_lo(), '('.to_string()),
 588                                         (expr_span.shrink_to_hi(), ')'.to_string()),
 589                                     ],
 590                                     Applicability::MachineApplicable,
 591                                 );
 592                             } else {
 593                                 let call_expr = self
 594                                     .tcx
 595                                     .hir()
 596                                     .expect_expr(self.tcx.hir().get_parent_node(expr.hir_id));
 597
 598                                 if let Some(span) = call_expr.span.trim_start(item_name.span) {
 599                                     err.span_suggestion(
 600                                         span,
 601                                         "remove the arguments",
 602                                         String::new(),
 603                                         Applicability::MaybeIncorrect,
 604                                     );
 605                                 }
 606                             }
 607                         }
 608
 609                         let field_kind = if is_accessible { "field" } else { "private field" };
 610                         err.span_label(item_name.span, format!("{}, not a method", field_kind));
 611                     } else if lev_candidate.is_none() && static_sources.is_empty() {
 612                         label_span_not_found();
 613                     }
 614                 } else {
 615                     label_span_not_found();
 616                 }
 617
 618                 if self.is_fn_ty(rcvr_ty, span) {
 619                     fn report_function<T: std::fmt::Display>(
 620                         err: &mut DiagnosticBuilder<'_>,
 621                         name: T,
 622                     ) {
 623                         err.note(
 624                             &format!("`{}` is a function, perhaps you wish to call it", name,),
 625                         );
 626                     }
 627
 628                     if let SelfSource::MethodCall(expr) = source {
 629                         if let Ok(expr_string) = tcx.sess.source_map().span_to_snippet(expr.span) {
 630                             report_function(&mut err, expr_string);
 631                         } else if let ExprKind::Path(QPath::Resolved(_, path)) = expr.kind {
 632                             if let Some(segment) = path.segments.last() {
 633                                 report_function(&mut err, segment.ident);
 634                             }
 635                         }
 636                     }
 637                 }
 638
 639                 if !static_sources.is_empty() {
 640                     err.note(
 641                         "found the following associated functions; to be used as methods, \
 642                          functions must have a `self` parameter",
 643                     );
 644                     err.span_label(span, "this is an associated function, not a method");
 645                 }
 646                 if static_sources.len() == 1 {
 647                     let ty_str = if let Some(CandidateSource::ImplSource(impl_did)) =
 648                         static_sources.get(0)
 649                     {
 650                         // When the "method" is resolved through dereferencing, we really want the
 651                         // original type that has the associated function for accurate suggestions.
 652                         // (#61411)
 653                         let ty = tcx.at(span).type_of(*impl_did);
 654                         match (&ty.peel_refs().kind(), &actual.peel_refs().kind()) {
 655                             (ty::Adt(def, _), ty::Adt(def_actual, _)) if def == def_actual => {
 656                                 // Use `actual` as it will have more `substs` filled in.
 657                                 self.ty_to_value_string(actual.peel_refs())
 658                             }
 659                             _ => self.ty_to_value_string(ty.peel_refs()),
 660                         }
 661                     } else {
 662                         self.ty_to_value_string(actual.peel_refs())
 663                     };
 664                     if let SelfSource::MethodCall(expr) = source {
 665                         err.span_suggestion(
 666                             expr.span.to(span),
 667                             "use associated function syntax instead",
 668                             format!("{}::{}", ty_str, item_name),
 669                             Applicability::MachineApplicable,
 670                         );
 671                     } else {
 672                         err.help(&format!("try with `{}::{}`", ty_str, item_name,));
 673                     }
 674
 675                     report_candidates(span, &mut err, static_sources, sugg_span);
 676                 } else if static_sources.len() > 1 {
 677                     report_candidates(span, &mut err, static_sources, sugg_span);
 678                 }
 679
 680                 let mut restrict_type_params = false;
 681                 let mut unsatisfied_bounds = false;
 682                 if item_name.name == sym::count && self.is_slice_ty(actual, span) {
 683                     let msg = "consider using `len` instead";
 684                     if let SelfSource::MethodCall(_expr) = source {
 685                         err.span_suggestion_short(
 686                             span,
 687                             msg,
 688                             String::from("len"),
 689                             Applicability::MachineApplicable,
 690                         );
 691                     } else {
 692                         err.span_label(span, msg);
 693                     }
 694                     if let Some(iterator_trait) = self.tcx.get_diagnostic_item(sym::Iterator) {
 695                         let iterator_trait = self.tcx.def_path_str(iterator_trait);
 696                         err.note(&format!("`count` is defined on `{iterator_trait}`, which `{actual}` does not implement"));
 697                     }
 698                 } else if !unsatisfied_predicates.is_empty() {
 699                     let def_span = |def_id| {
 700                         self.tcx.sess.source_map().guess_head_span(self.tcx.def_span(def_id))
 701                     };
 702                     let mut type_params = FxHashMap::default();
 703                     let mut bound_spans = vec![];
 704
 705                     let mut collect_type_param_suggestions =
 706                         |self_ty: Ty<'tcx>, parent_pred: ty::Predicate<'tcx>, obligation: &str| {
 707                             // We don't care about regions here, so it's fine to skip the binder here.
 708                             if let (ty::Param(_), ty::PredicateKind::Trait(p)) =
 709                                 (self_ty.kind(), parent_pred.kind().skip_binder())
 710                             {
 711                                 let node = match p.trait_ref.self_ty().kind() {
 712                                     ty::Param(_) => {
 713                                         // Account for `fn` items like in `issue-35677.rs` to
 714                                         // suggest restricting its type params.
 715                                         let did = self.tcx.hir().body_owner_def_id(hir::BodyId {
 716                                             hir_id: self.body_id,
 717                                         });
 718                                         Some(
 719                                             self.tcx
 720                                                 .hir()
 721                                                 .get(self.tcx.hir().local_def_id_to_hir_id(did)),
 722                                         )
 723                                     }
 724                                     ty::Adt(def, _) => def.did.as_local().map(|def_id| {
 725                                         self.tcx
 726                                             .hir()
 727                                             .get(self.tcx.hir().local_def_id_to_hir_id(def_id))
 728                                     }),
 729                                     _ => None,
 730                                 };
 731                                 if let Some(hir::Node::Item(hir::Item { kind, .. })) = node {
 732                                     if let Some(g) = kind.generics() {
 733                                         let key = match g.where_clause.predicates {
 734                                             [.., pred] => (pred.span().shrink_to_hi(), false),
 735                                             [] => (
 736                                                 g.where_clause.span_for_predicates_or_empty_place(),
 737                                                 true,
 738                                             ),
 739                                         };
 740                                         type_params
 741                                             .entry(key)
 742                                             .or_insert_with(FxHashSet::default)
 743                                             .insert(obligation.to_owned());
 744                                     }
 745                                 }
 746                             }
 747                         };
 748                     let mut bound_span_label = |self_ty: Ty<'_>, obligation: &str, quiet: &str| {
 749                         let msg = format!(
 750                             "doesn't satisfy `{}`",
 751                             if obligation.len() > 50 { quiet } else { obligation }
 752                         );
 753                         match &self_ty.kind() {
 754                             // Point at the type that couldn't satisfy the bound.
 755                             ty::Adt(def, _) => bound_spans.push((def_span(def.did), msg)),
 756                             // Point at the trait object that couldn't satisfy the bound.
 757                             ty::Dynamic(preds, _) => {
 758                                 for pred in preds.iter() {
 759                                     match pred.skip_binder() {
 760                                         ty::ExistentialPredicate::Trait(tr) => {
 761                                             bound_spans.push((def_span(tr.def_id), msg.clone()))
 762                                         }
 763                                         ty::ExistentialPredicate::Projection(_)
 764                                         | ty::ExistentialPredicate::AutoTrait(_) => {}
 765                                     }
 766                                 }
 767                             }
 768                             // Point at the closure that couldn't satisfy the bound.
 769                             ty::Closure(def_id, _) => bound_spans
 770                                 .push((def_span(*def_id), format!("doesn't satisfy `{}`", quiet))),
 771                             _ => {}
 772                         }
 773                     };
 774                     let mut format_pred = |pred: ty::Predicate<'tcx>| {
 775                         let bound_predicate = pred.kind();
 776                         match bound_predicate.skip_binder() {
 777                             ty::PredicateKind::Projection(pred) => {
 778                                 let pred = bound_predicate.rebind(pred);
 779                                 // `<Foo as Iterator>::Item = String`.
 780                                 let projection_ty = pred.skip_binder().projection_ty;
 781
 782                                 let substs_with_infer_self = tcx.mk_substs(
 783                                     iter::once(tcx.mk_ty_var(ty::TyVid::from_u32(0)).into())
 784                                         .chain(projection_ty.substs.iter().skip(1)),
 785                                 );
 786
 787                                 let quiet_projection_ty = ty::ProjectionTy {
 788                                     substs: substs_with_infer_self,
 789                                     item_def_id: projection_ty.item_def_id,
 790                                 };
 791
 792                                 let term = pred.skip_binder().term;
 793
 794                                 let obligation = format!("{} = {}", projection_ty, term);
 795                                 let quiet = format!("{} = {}", quiet_projection_ty, term);
 796
 797                                 bound_span_label(projection_ty.self_ty(), &obligation, &quiet);
 798                                 Some((obligation, projection_ty.self_ty()))
 799                             }
 800                             ty::PredicateKind::Trait(poly_trait_ref) => {
 801                                 let p = poly_trait_ref.trait_ref;
 802                                 let self_ty = p.self_ty();
 803                                 let path = p.print_only_trait_path();
 804                                 let obligation = format!("{}: {}", self_ty, path);
 805                                 let quiet = format!("_: {}", path);
 806                                 bound_span_label(self_ty, &obligation, &quiet);
 807                                 Some((obligation, self_ty))
 808                             }
 809                             _ => None,
 810                         }
 811                     };
 812
 813                     // Find all the requirements that come from a local `impl` block.
 814                     let mut skip_list: FxHashSet<_> = Default::default();
 815                     let mut spanned_predicates: FxHashMap<MultiSpan, _> = Default::default();
 816                     for (data, p, parent_p) in unsatisfied_predicates
 817                         .iter()
 818                         .filter_map(|(p, parent, c)| c.as_ref().map(|c| (p, parent, c)))
 819                         .filter_map(|(p, parent, c)| match c.code() {
 820                             ObligationCauseCode::ImplDerivedObligation(ref data) => {
 821                                 Some((data, p, parent))
 822                             }
 823                             _ => None,
 824                         })
 825                     {
 826                         let parent_trait_ref = data.parent_trait_pred;
 827                         let parent_def_id = parent_trait_ref.def_id();
 828                         let path = parent_trait_ref.print_modifiers_and_trait_path();
 829                         let tr_self_ty = parent_trait_ref.skip_binder().self_ty();
 830                         let mut candidates = vec![];
 831                         self.tcx.for_each_relevant_impl(
 832                             parent_def_id,
 833                             parent_trait_ref.self_ty().skip_binder(),
 834                             |impl_def_id| match self.tcx.hir().get_if_local(impl_def_id) {
 835                                 Some(Node::Item(hir::Item {
 836                                     kind: hir::ItemKind::Impl(hir::Impl { .. }),
 837                                     ..
 838                                 })) => {
 839                                     candidates.push(impl_def_id);
 840                                 }
 841                                 _ => {}
 842                             },
 843                         );
 844                         if let [def_id] = &candidates[..] {
 845                             match self.tcx.hir().get_if_local(*def_id) {
 846                                 Some(Node::Item(hir::Item {
 847                                     kind: hir::ItemKind::Impl(hir::Impl { of_trait, self_ty, .. }),
 848                                     ..
 849                                 })) => {
 850                                     if let Some(pred) = parent_p {
 851                                         // Done to add the "doesn't satisfy" `span_label`.
 852                                         let _ = format_pred(*pred);
 853                                     }
 854                                     skip_list.insert(p);
 855                                     let mut spans = Vec::with_capacity(2);
 856                                     if let Some(trait_ref) = of_trait {
 857                                         spans.push(trait_ref.path.span);
 858                                     }
 859                                     spans.push(self_ty.span);
 860                                     let entry = spanned_predicates.entry(spans.into());
 861                                     entry
 862                                         .or_insert_with(|| (path, tr_self_ty, Vec::new()))
 863                                         .2
 864                                         .push(p);
 865                                 }
 866                                 _ => {}
 867                             }
 868                         }
 869                     }
 870                     for (span, (path, self_ty, preds)) in spanned_predicates {
 871                         err.span_note(
 872                             span,
 873                             &format!(
 874                                 "the following trait bounds were not satisfied because of the \
 875                                  requirements of the implementation of `{}` for `{}`:\n{}",
 876                                 path,
 877                                 self_ty,
 878                                 preds
 879                                     .into_iter()
 880                                     // .map(|pred| format!("{:?}", pred))
 881                                     .filter_map(|pred| format_pred(*pred))
 882                                     .map(|(p, _)| format!("`{}`", p))
 883                                     .collect::<Vec<_>>()
 884                                     .join("\n"),
 885                             ),
 886                         );
 887                     }
 888
 889                     // The requirements that didn't have an `impl` span to show.
 890                     let mut bound_list = unsatisfied_predicates
 891                         .iter()
 892                         .filter(|(pred, _, _parent_pred)| !skip_list.contains(&pred))
 893                         .filter_map(|(pred, parent_pred, _cause)| {
 894                             format_pred(*pred).map(|(p, self_ty)| {
 895                                 collect_type_param_suggestions(self_ty, *pred, &p);
 896                                 match parent_pred {
 897                                     None => format!("`{}`", &p),
 898                                     Some(parent_pred) => match format_pred(*parent_pred) {
 899                                         None => format!("`{}`", &p),
 900                                         Some((parent_p, _)) => {
 901                                             collect_type_param_suggestions(
 902                                                 self_ty,
 903                                                 *parent_pred,
 904                                                 &p,
 905                                             );
 906                                             format!("`{}`\nwhich is required by `{}`", p, parent_p)
 907                                         }
 908                                     },
 909                                 }
 910                             })
 911                         })
 912                         .enumerate()
 913                         .collect::<Vec<(usize, String)>>();
 914
 915                     for ((span, empty_where), obligations) in type_params.into_iter() {
 916                         restrict_type_params = true;
 917                         // #74886: Sort here so that the output is always the same.
 918                         let mut obligations = obligations.into_iter().collect::<Vec<_>>();
 919                         obligations.sort();
 920                         err.span_suggestion_verbose(
 921                             span,
 922                             &format!(
 923                                 "consider restricting the type parameter{s} to satisfy the \
 924                                  trait bound{s}",
 925                                 s = pluralize!(obligations.len())
 926                             ),
 927                             format!(
 928                                 "{} {}",
 929                                 if empty_where { " where" } else { "," },
 930                                 obligations.join(", ")
 931                             ),
 932                             Applicability::MaybeIncorrect,
 933                         );
 934                     }
 935
 936                     bound_list.sort_by(|(_, a), (_, b)| a.cmp(b)); // Sort alphabetically.
 937                     bound_list.dedup_by(|(_, a), (_, b)| a == b); // #35677
 938                     bound_list.sort_by_key(|(pos, _)| *pos); // Keep the original predicate order.
 939                     bound_spans.sort();
 940                     bound_spans.dedup();
 941                     for (span, msg) in bound_spans.into_iter() {
 942                         err.span_label(span, &msg);
 943                     }
 944                     if !bound_list.is_empty() || !skip_list.is_empty() {
 945                         let bound_list = bound_list
 946                             .into_iter()
 947                             .map(|(_, path)| path)
 948                             .collect::<Vec<_>>()
 949                             .join("\n");
 950                         let actual_prefix = actual.prefix_string(self.tcx);
 951                         err.set_primary_message(&format!(
 952                             "the {item_kind} `{item_name}` exists for {actual_prefix} `{ty_str}`, but its trait bounds were not satisfied"
 953                         ));
 954                         if !bound_list.is_empty() {
 955                             err.note(&format!(
 956                                 "the following trait bounds were not satisfied:\n{bound_list}"
 957                             ));
 958                         }
 959                         self.suggest_derive(&mut err, &unsatisfied_predicates);
 960
 961                         unsatisfied_bounds = true;
 962                     }
 963                 }
 964
 965                 if actual.is_numeric() && actual.is_fresh() || restrict_type_params {
 966                 } else {
 967                     self.suggest_traits_to_import(
 968                         &mut err,
 969                         span,
 970                         rcvr_ty,
 971                         item_name,
 972                         source,
 973                         out_of_scope_traits,
 974                         &unsatisfied_predicates,
 975                         unsatisfied_bounds,
 976                     );
 977                 }
 978
 979                 // Don't emit a suggestion if we found an actual method
 980                 // that had unsatisfied trait bounds
 981                 if unsatisfied_predicates.is_empty() && actual.is_enum() {
 982                     let adt_def = actual.ty_adt_def().expect("enum is not an ADT");
 983                     if let Some(suggestion) = lev_distance::find_best_match_for_name(
 984                         &adt_def.variants.iter().map(|s| s.name).collect::<Vec<_>>(),
 985                         item_name.name,
 986                         None,
 987                     ) {
 988                         err.span_suggestion(
 989                             span,
 990                             "there is a variant with a similar name",
 991                             suggestion.to_string(),
 992                             Applicability::MaybeIncorrect,
 993                         );
 994                     }
 995                 }
 996
 997                 if item_name.name == sym::as_str && actual.peel_refs().is_str() {
 998                     let msg = "remove this method call";
 999                     let mut fallback_span = true;
1000                     if let SelfSource::MethodCall(expr) = source {
1001                         let call_expr =
1002                             self.tcx.hir().expect_expr(self.tcx.hir().get_parent_node(expr.hir_id));
1003                         if let Some(span) = call_expr.span.trim_start(expr.span) {
1004                             err.span_suggestion(
1005                                 span,
1006                                 msg,
1007                                 String::new(),
1008                                 Applicability::MachineApplicable,
1009                             );
1010                             fallback_span = false;
1011                         }
1012                     }
1013                     if fallback_span {
1014                         err.span_label(span, msg);
1015                     }
1016                 } else if let Some(lev_candidate) = lev_candidate {
1017                     // Don't emit a suggestion if we found an actual method
1018                     // that had unsatisfied trait bounds
1019                     if unsatisfied_predicates.is_empty() {
1020                         let def_kind = lev_candidate.kind.as_def_kind();
1021                         err.span_suggestion(
1022                             span,
1023                             &format!(
1024                                 "there is {} {} with a similar name",
1025                                 def_kind.article(),
1026                                 def_kind.descr(lev_candidate.def_id),
1027                             ),
1028                             lev_candidate.name.to_string(),
1029                             Applicability::MaybeIncorrect,
1030                         );
1031                     }
1032                 }
1033
1034                 return Some(err);
1035             }
1036
1037             MethodError::Ambiguity(sources) => {
1038                 let mut err = struct_span_err!(
1039                     self.sess(),
1040                     item_name.span,
1041                     E0034,
1042                     "multiple applicable items in scope"
1043                 );
1044                 err.span_label(item_name.span, format!("multiple `{}` found", item_name));
1045
1046                 report_candidates(span, &mut err, sources, sugg_span);
1047                 err.emit();
1048             }
1049
1050             MethodError::PrivateMatch(kind, def_id, out_of_scope_traits) => {
1051                 let kind = kind.descr(def_id);
1052                 let mut err = struct_span_err!(
1053                     self.tcx.sess,
1054                     item_name.span,
1055                     E0624,
1056                     "{} `{}` is private",
1057                     kind,
1058                     item_name
1059                 );
1060                 err.span_label(item_name.span, &format!("private {}", kind));
1061                 let sp = self
1062                     .tcx
1063                     .hir()
1064                     .span_if_local(def_id)
1065                     .unwrap_or_else(|| self.tcx.def_span(def_id));
1066                 err.span_label(sp, &format!("private {} defined here", kind));
1067                 self.suggest_valid_traits(&mut err, out_of_scope_traits);
1068                 err.emit();
1069             }
1070
1071             MethodError::IllegalSizedBound(candidates, needs_mut, bound_span) => {
1072                 let msg = format!("the `{}` method cannot be invoked on a trait object", item_name);
1073                 let mut err = self.sess().struct_span_err(span, &msg);
1074                 err.span_label(bound_span, "this has a `Sized` requirement");
1075                 if !candidates.is_empty() {
1076                     let help = format!(
1077                         "{an}other candidate{s} {were} found in the following trait{s}, perhaps \
1078                          add a `use` for {one_of_them}:",
1079                         an = if candidates.len() == 1 { "an" } else { "" },
1080                         s = pluralize!(candidates.len()),
1081                         were = if candidates.len() == 1 { "was" } else { "were" },
1082                         one_of_them = if candidates.len() == 1 { "it" } else { "one_of_them" },
1083                     );
1084                     self.suggest_use_candidates(&mut err, help, candidates);
1085                 }
1086                 if let ty::Ref(region, t_type, mutability) = rcvr_ty.kind() {
1087                     if needs_mut {
1088                         let trait_type = self.tcx.mk_ref(
1089                             *region,
1090                             ty::TypeAndMut { ty: *t_type, mutbl: mutability.invert() },
1091                         );
1092                         err.note(&format!("you need `{}` instead of `{}`", trait_type, rcvr_ty));
1093                     }
1094                 }
1095                 err.emit();
1096             }
1097
1098             MethodError::BadReturnType => bug!("no return type expectations but got BadReturnType"),
1099         }
1100         None
1101     }
1102
1103     crate fn note_unmet_impls_on_type(
1104         &self,
1105         err: &mut rustc_errors::DiagnosticBuilder<'_>,
1106         errors: Vec<FulfillmentError<'tcx>>,
1107     ) {
1108         let all_local_types_needing_impls =
1109             errors.iter().all(|e| match e.obligation.predicate.kind().skip_binder() {
1110                 ty::PredicateKind::Trait(pred) => match pred.self_ty().kind() {
1111                     ty::Adt(def, _) => def.did.is_local(),
1112                     _ => false,
1113                 },
1114                 _ => false,
1115             });
1116         let mut preds: Vec<_> = errors
1117             .iter()
1118             .filter_map(|e| match e.obligation.predicate.kind().skip_binder() {
1119                 ty::PredicateKind::Trait(pred) => Some(pred),
1120                 _ => None,
1121             })
1122             .collect();
1123         preds.sort_by_key(|pred| (pred.def_id(), pred.self_ty()));
1124         let def_ids = preds
1125             .iter()
1126             .filter_map(|pred| match pred.self_ty().kind() {
1127                 ty::Adt(def, _) => Some(def.did),
1128                 _ => None,
1129             })
1130             .collect::<FxHashSet<_>>();
1131         let sm = self.tcx.sess.source_map();
1132         let mut spans: MultiSpan = def_ids
1133             .iter()
1134             .filter_map(|def_id| {
1135                 let span = self.tcx.def_span(*def_id);
1136                 if span.is_dummy() { None } else { Some(sm.guess_head_span(span)) }
1137             })
1138             .collect::<Vec<_>>()
1139             .into();
1140
1141         for pred in &preds {
1142             match pred.self_ty().kind() {
1143                 ty::Adt(def, _) => {
1144                     spans.push_span_label(
1145                         sm.guess_head_span(self.tcx.def_span(def.did)),
1146                         format!("must implement `{}`", pred.trait_ref.print_only_trait_path()),
1147                     );
1148                 }
1149                 _ => {}
1150             }
1151         }
1152
1153         if all_local_types_needing_impls && spans.primary_span().is_some() {
1154             let msg = if preds.len() == 1 {
1155                 format!(
1156                     "an implementation of `{}` might be missing for `{}`",
1157                     preds[0].trait_ref.print_only_trait_path(),
1158                     preds[0].self_ty()
1159                 )
1160             } else {
1161                 format!(
1162                     "the following type{} would have to `impl` {} required trait{} for this \
1163                      operation to be valid",
1164                     pluralize!(def_ids.len()),
1165                     if def_ids.len() == 1 { "its" } else { "their" },
1166                     pluralize!(preds.len()),
1167                 )
1168             };
1169             err.span_note(spans, &msg);
1170         }
1171
1172         let preds: Vec<_> = errors
1173             .iter()
1174             .map(|e| (e.obligation.predicate, None, Some(e.obligation.cause.clone())))
1175             .collect();
1176         self.suggest_derive(err, &preds);
1177     }
1178
1179     fn suggest_derive(
1180         &self,
1181         err: &mut DiagnosticBuilder<'_>,
1182         unsatisfied_predicates: &[(
1183             ty::Predicate<'tcx>,
1184             Option<ty::Predicate<'tcx>>,
1185             Option<ObligationCause<'tcx>>,
1186         )],
1187     ) {
1188         let mut derives = Vec::<(String, Span, String)>::new();
1189         let mut traits = Vec::<Span>::new();
1190         for (pred, _, _) in unsatisfied_predicates {
1191             let trait_pred = match pred.kind().skip_binder() {
1192                 ty::PredicateKind::Trait(trait_pred) => trait_pred,
1193                 _ => continue,
1194             };
1195             let adt = match trait_pred.self_ty().ty_adt_def() {
1196                 Some(adt) if adt.did.is_local() => adt,
1197                 _ => continue,
1198             };
1199             let can_derive = match self.tcx.get_diagnostic_name(trait_pred.def_id()) {
1200                 Some(sym::Default) => !adt.is_enum(),
1201                 Some(
1202                     sym::Eq
1203                     | sym::PartialEq
1204                     | sym::Ord
1205                     | sym::PartialOrd
1206                     | sym::Clone
1207                     | sym::Copy
1208                     | sym::Hash
1209                     | sym::Debug,
1210                 ) => true,
1211                 _ => false,
1212             };
1213             if can_derive {
1214                 derives.push((
1215                     format!("{}", trait_pred.self_ty()),
1216                     self.tcx.def_span(adt.did),
1217                     format!("{}", trait_pred.trait_ref.print_only_trait_name()),
1218                 ));
1219             } else {
1220                 traits.push(self.tcx.def_span(trait_pred.def_id()));
1221             }
1222         }
1223         traits.sort();
1224         traits.dedup();
1225
1226         derives.sort();
1227         derives.dedup();
1228
1229         let mut derives_grouped = Vec::<(String, Span, String)>::new();
1230         for (self_name, self_span, trait_name) in derives.into_iter() {
1231             if let Some((last_self_name, _, ref mut last_trait_names)) = derives_grouped.last_mut()
1232             {
1233                 if last_self_name == &self_name {
1234                     last_trait_names.push_str(format!(", {}", trait_name).as_str());
1235                     continue;
1236                 }
1237             }
1238             derives_grouped.push((self_name, self_span, trait_name));
1239         }
1240
1241         let len = traits.len();
1242         if len > 0 {
1243             let span: MultiSpan = traits.into();
1244             err.span_note(
1245                 span,
1246                 &format!("the following trait{} must be implemented", pluralize!(len),),
1247             );
1248         }
1249
1250         for (self_name, self_span, traits) in &derives_grouped {
1251             err.span_suggestion_verbose(
1252                 self_span.shrink_to_lo(),
1253                 &format!("consider annotating `{}` with `#[derive({})]`", self_name, traits),
1254                 format!("#[derive({})]\n", traits),
1255                 Applicability::MaybeIncorrect,
1256             );
1257         }
1258     }
1259
1260     /// Print out the type for use in value namespace.
1261     fn ty_to_value_string(&self, ty: Ty<'tcx>) -> String {
1262         match ty.kind() {
1263             ty::Adt(def, substs) => format!("{}", ty::Instance::new(def.did, substs)),
1264             _ => self.ty_to_string(ty),
1265         }
1266     }
1267
1268     fn suggest_await_before_method(
1269         &self,
1270         err: &mut DiagnosticBuilder<'_>,
1271         item_name: Ident,
1272         ty: Ty<'tcx>,
1273         call: &hir::Expr<'_>,
1274         span: Span,
1275     ) {
1276         let output_ty = match self.infcx.get_impl_future_output_ty(ty) {
1277             Some(output_ty) => self.resolve_vars_if_possible(output_ty).skip_binder(),
1278             _ => return,
1279         };
1280         let method_exists = self.method_exists(item_name, output_ty, call.hir_id, true);
1281         debug!("suggest_await_before_method: is_method_exist={}", method_exists);
1282         if method_exists {
1283             err.span_suggestion_verbose(
1284                 span.shrink_to_lo(),
1285                 "consider `await`ing on the `Future` and calling the method on its `Output`",
1286                 "await.".to_string(),
1287                 Applicability::MaybeIncorrect,
1288             );
1289         }
1290     }
1291
1292     fn suggest_use_candidates(
1293         &self,
1294         err: &mut DiagnosticBuilder<'_>,
1295         mut msg: String,
1296         candidates: Vec<DefId>,
1297     ) {
1298         let parent_map = self.tcx.visible_parent_map(());
1299
1300         // Separate out candidates that must be imported with a glob, because they are named `_`
1301         // and cannot be referred with their identifier.
1302         let (candidates, globs): (Vec<_>, Vec<_>) = candidates.into_iter().partition(|trait_did| {
1303             if let Some(parent_did) = parent_map.get(trait_did) {
1304                 // If the item is re-exported as `_`, we should suggest a glob-import instead.
1305                 if Some(*parent_did) != self.tcx.parent(*trait_did)
1306                     && self
1307                         .tcx
1308                         .module_children(*parent_did)
1309                         .iter()
1310                         .filter(|child| child.res.opt_def_id() == Some(*trait_did))
1311                         .all(|child| child.ident.name == kw::Underscore)
1312                 {
1313                     return false;
1314                 }
1315             }
1316
1317             true
1318         });
1319
1320         let module_did = self.tcx.parent_module(self.body_id);
1321         let (span, found_use) = find_use_placement(self.tcx, module_did);
1322         if let Some(span) = span {
1323             let path_strings = candidates.iter().map(|trait_did| {
1324                 // Produce an additional newline to separate the new use statement
1325                 // from the directly following item.
1326                 let additional_newline = if found_use { "" } else { "\n" };
1327                 format!(
1328                     "use {};\n{}",
1329                     with_crate_prefix(|| self.tcx.def_path_str(*trait_did)),
1330                     additional_newline
1331                 )
1332             });
1333
1334             let glob_path_strings = globs.iter().map(|trait_did| {
1335                 let parent_did = parent_map.get(trait_did).unwrap();
1336
1337                 // Produce an additional newline to separate the new use statement
1338                 // from the directly following item.
1339                 let additional_newline = if found_use { "" } else { "\n" };
1340                 format!(
1341                     "use {}::*; // trait {}\n{}",
1342                     with_crate_prefix(|| self.tcx.def_path_str(*parent_did)),
1343                     self.tcx.item_name(*trait_did),
1344                     additional_newline
1345                 )
1346             });
1347
1348             err.span_suggestions(
1349                 span,
1350                 &msg,
1351                 path_strings.chain(glob_path_strings),
1352                 Applicability::MaybeIncorrect,
1353             );
1354         } else {
1355             let limit = if candidates.len() + globs.len() == 5 { 5 } else { 4 };
1356             for (i, trait_did) in candidates.iter().take(limit).enumerate() {
1357                 if candidates.len() + globs.len() > 1 {
1358                     msg.push_str(&format!(
1359                         "\ncandidate #{}: `use {};`",
1360                         i + 1,
1361                         with_crate_prefix(|| self.tcx.def_path_str(*trait_did))
1362                     ));
1363                 } else {
1364                     msg.push_str(&format!(
1365                         "\n`use {};`",
1366                         with_crate_prefix(|| self.tcx.def_path_str(*trait_did))
1367                     ));
1368                 }
1369             }
1370             for (i, trait_did) in
1371                 globs.iter().take(limit.saturating_sub(candidates.len())).enumerate()
1372             {
1373                 let parent_did = parent_map.get(trait_did).unwrap();
1374
1375                 if candidates.len() + globs.len() > 1 {
1376                     msg.push_str(&format!(
1377                         "\ncandidate #{}: `use {}::*; // trait {}`",
1378                         candidates.len() + i + 1,
1379                         with_crate_prefix(|| self.tcx.def_path_str(*parent_did)),
1380                         self.tcx.item_name(*trait_did),
1381                     ));
1382                 } else {
1383                     msg.push_str(&format!(
1384                         "\n`use {}::*; // trait {}`",
1385                         with_crate_prefix(|| self.tcx.def_path_str(*parent_did)),
1386                         self.tcx.item_name(*trait_did),
1387                     ));
1388                 }
1389             }
1390             if candidates.len() > limit {
1391                 msg.push_str(&format!("\nand {} others", candidates.len() + globs.len() - limit));
1392             }
1393             err.note(&msg);
1394         }
1395     }
1396
1397     fn suggest_valid_traits(
1398         &self,
1399         err: &mut DiagnosticBuilder<'_>,
1400         valid_out_of_scope_traits: Vec<DefId>,
1401     ) -> bool {
1402         if !valid_out_of_scope_traits.is_empty() {
1403             let mut candidates = valid_out_of_scope_traits;
1404             candidates.sort();
1405             candidates.dedup();
1406
1407             // `TryFrom` and `FromIterator` have no methods
1408             let edition_fix = candidates
1409                 .iter()
1410                 .find(|did| self.tcx.is_diagnostic_item(sym::TryInto, **did))
1411                 .copied();
1412
1413             err.help("items from traits can only be used if the trait is in scope");
1414             let msg = format!(
1415                 "the following {traits_are} implemented but not in scope; \
1416                  perhaps add a `use` for {one_of_them}:",
1417                 traits_are = if candidates.len() == 1 { "trait is" } else { "traits are" },
1418                 one_of_them = if candidates.len() == 1 { "it" } else { "one of them" },
1419             );
1420
1421             self.suggest_use_candidates(err, msg, candidates);
1422             if let Some(did) = edition_fix {
1423                 err.note(&format!(
1424                     "'{}' is included in the prelude starting in Edition 2021",
1425                     with_crate_prefix(|| self.tcx.def_path_str(did))
1426                 ));
1427             }
1428
1429             true
1430         } else {
1431             false
1432         }
1433     }
1434
1435     fn suggest_traits_to_import(
1436         &self,
1437         err: &mut DiagnosticBuilder<'_>,
1438         span: Span,
1439         rcvr_ty: Ty<'tcx>,
1440         item_name: Ident,
1441         source: SelfSource<'tcx>,
1442         valid_out_of_scope_traits: Vec<DefId>,
1443         unsatisfied_predicates: &[(
1444             ty::Predicate<'tcx>,
1445             Option<ty::Predicate<'tcx>>,
1446             Option<ObligationCause<'tcx>>,
1447         )],
1448         unsatisfied_bounds: bool,
1449     ) {
1450         let mut alt_rcvr_sugg = false;
1451         if let (SelfSource::MethodCall(rcvr), false) = (source, unsatisfied_bounds) {
1452             debug!(?span, ?item_name, ?rcvr_ty, ?rcvr);
1453             let skippable = [
1454                 self.tcx.lang_items().clone_trait(),
1455                 self.tcx.lang_items().deref_trait(),
1456                 self.tcx.lang_items().deref_mut_trait(),
1457                 self.tcx.lang_items().drop_trait(),
1458                 self.tcx.get_diagnostic_item(sym::AsRef),
1459             ];
1460             // Try alternative arbitrary self types that could fulfill this call.
1461             // FIXME: probe for all types that *could* be arbitrary self-types, not
1462             // just this list.
1463             for (rcvr_ty, post) in &[
1464                 (rcvr_ty, ""),
1465                 (self.tcx.mk_mut_ref(self.tcx.lifetimes.re_erased, rcvr_ty), "&mut "),
1466                 (self.tcx.mk_imm_ref(self.tcx.lifetimes.re_erased, rcvr_ty), "&"),
1467             ] {
1468                 if let Ok(pick) = self.lookup_probe(
1469                     span,
1470                     item_name,
1471                     *rcvr_ty,
1472                     rcvr,
1473                     crate::check::method::probe::ProbeScope::AllTraits,
1474                 ) {
1475                     // If the method is defined for the receiver we have, it likely wasn't `use`d.
1476                     // We point at the method, but we just skip the rest of the check for arbitrary
1477                     // self types and rely on the suggestion to `use` the trait from
1478                     // `suggest_valid_traits`.
1479                     let did = Some(pick.item.container.id());
1480                     let skip = skippable.contains(&did);
1481                     if pick.autoderefs == 0 && !skip {
1482                         err.span_label(
1483                             pick.item.ident(self.tcx).span,
1484                             &format!("the method is available for `{}` here", rcvr_ty),
1485                         );
1486                     }
1487                     break;
1488                 }
1489                 for (rcvr_ty, pre) in &[
1490                     (self.tcx.mk_lang_item(*rcvr_ty, LangItem::OwnedBox), "Box::new"),
1491                     (self.tcx.mk_lang_item(*rcvr_ty, LangItem::Pin), "Pin::new"),
1492                     (self.tcx.mk_diagnostic_item(*rcvr_ty, sym::Arc), "Arc::new"),
1493                     (self.tcx.mk_diagnostic_item(*rcvr_ty, sym::Rc), "Rc::new"),
1494                 ] {
1495                     if let Some(new_rcvr_t) = *rcvr_ty {
1496                         if let Ok(pick) = self.lookup_probe(
1497                             span,
1498                             item_name,
1499                             new_rcvr_t,
1500                             rcvr,
1501                             crate::check::method::probe::ProbeScope::AllTraits,
1502                         ) {
1503                             debug!("try_alt_rcvr: pick candidate {:?}", pick);
1504                             let did = Some(pick.item.container.id());
1505                             // We don't want to suggest a container type when the missing
1506                             // method is `.clone()` or `.deref()` otherwise we'd suggest
1507                             // `Arc::new(foo).clone()`, which is far from what the user wants.
1508                             // Explicitly ignore the `Pin::as_ref()` method as `Pin` does not
1509                             // implement the `AsRef` trait.
1510                             let skip = skippable.contains(&did)
1511                                 || (("Pin::new" == *pre) && (sym::as_ref == item_name.name));
1512                             // Make sure the method is defined for the *actual* receiver: we don't
1513                             // want to treat `Box<Self>` as a receiver if it only works because of
1514                             // an autoderef to `&self`
1515                             if pick.autoderefs == 0 && !skip {
1516                                 err.span_label(
1517                                     pick.item.ident(self.tcx).span,
1518                                     &format!("the method is available for `{}` here", new_rcvr_t),
1519                                 );
1520                                 err.multipart_suggestion(
1521                                     "consider wrapping the receiver expression with the \
1522                                         appropriate type",
1523                                     vec![
1524                                         (rcvr.span.shrink_to_lo(), format!("{}({}", pre, post)),
1525                                         (rcvr.span.shrink_to_hi(), ")".to_string()),
1526                                     ],
1527                                     Applicability::MaybeIncorrect,
1528                                 );
1529                                 // We don't care about the other suggestions.
1530                                 alt_rcvr_sugg = true;
1531                             }
1532                         }
1533                     }
1534                 }
1535             }
1536         }
1537         if self.suggest_valid_traits(err, valid_out_of_scope_traits) {
1538             return;
1539         }
1540
1541         let type_is_local = self.type_derefs_to_local(span, rcvr_ty, source);
1542
1543         let mut arbitrary_rcvr = vec![];
1544         // There are no traits implemented, so lets suggest some traits to
1545         // implement, by finding ones that have the item name, and are
1546         // legal to implement.
1547         let mut candidates = all_traits(self.tcx)
1548             .into_iter()
1549             // Don't issue suggestions for unstable traits since they're
1550             // unlikely to be implementable anyway
1551             .filter(|info| match self.tcx.lookup_stability(info.def_id) {
1552                 Some(attr) => attr.level.is_stable(),
1553                 None => true,
1554             })
1555             .filter(|info| {
1556                 // We approximate the coherence rules to only suggest
1557                 // traits that are legal to implement by requiring that
1558                 // either the type or trait is local. Multi-dispatch means
1559                 // this isn't perfect (that is, there are cases when
1560                 // implementing a trait would be legal but is rejected
1561                 // here).
1562                 unsatisfied_predicates.iter().all(|(p, _, _)| {
1563                     match p.kind().skip_binder() {
1564                         // Hide traits if they are present in predicates as they can be fixed without
1565                         // having to implement them.
1566                         ty::PredicateKind::Trait(t) => t.def_id() == info.def_id,
1567                         ty::PredicateKind::Projection(p) => {
1568                             p.projection_ty.item_def_id == info.def_id
1569                         }
1570                         _ => false,
1571                     }
1572                 }) && (type_is_local || info.def_id.is_local())
1573                     && self
1574                         .associated_value(info.def_id, item_name)
1575                         .filter(|item| {
1576                             if let ty::AssocKind::Fn = item.kind {
1577                                 let id = item
1578                                     .def_id
1579                                     .as_local()
1580                                     .map(|def_id| self.tcx.hir().local_def_id_to_hir_id(def_id));
1581                                 if let Some(hir::Node::TraitItem(hir::TraitItem {
1582                                     kind: hir::TraitItemKind::Fn(fn_sig, method),
1583                                     ..
1584                                 })) = id.map(|id| self.tcx.hir().get(id))
1585                                 {
1586                                     let self_first_arg = match method {
1587                                         hir::TraitFn::Required([ident, ..]) => {
1588                                             ident.name == kw::SelfLower
1589                                         }
1590                                         hir::TraitFn::Provided(body_id) => {
1591                                             self.tcx.hir().body(*body_id).params.first().map_or(
1592                                                 false,
1593                                                 |param| {
1594                                                     matches!(
1595                                                         param.pat.kind,
1596                                                         hir::PatKind::Binding(_, _, ident, _)
1597                                                             if ident.name == kw::SelfLower
1598                                                     )
1599                                                 },
1600                                             )
1601                                         }
1602                                         _ => false,
1603                                     };
1604
1605                                     if !fn_sig.decl.implicit_self.has_implicit_self()
1606                                         && self_first_arg
1607                                     {
1608                                         if let Some(ty) = fn_sig.decl.inputs.get(0) {
1609                                             arbitrary_rcvr.push(ty.span);
1610                                         }
1611                                         return false;
1612                                     }
1613                                 }
1614                             }
1615                             // We only want to suggest public or local traits (#45781).
1616                             item.vis.is_public() || info.def_id.is_local()
1617                         })
1618                         .is_some()
1619             })
1620             .collect::<Vec<_>>();
1621         for span in &arbitrary_rcvr {
1622             err.span_label(
1623                 *span,
1624                 "the method might not be found because of this arbitrary self type",
1625             );
1626         }
1627         if alt_rcvr_sugg {
1628             return;
1629         }
1630
1631         if !candidates.is_empty() {
1632             // Sort from most relevant to least relevant.
1633             candidates.sort_by(|a, b| a.cmp(b).reverse());
1634             candidates.dedup();
1635
1636             let param_type = match rcvr_ty.kind() {
1637                 ty::Param(param) => Some(param),
1638                 ty::Ref(_, ty, _) => match ty.kind() {
1639                     ty::Param(param) => Some(param),
1640                     _ => None,
1641                 },
1642                 _ => None,
1643             };
1644             err.help(if param_type.is_some() {
1645                 "items from traits can only be used if the type parameter is bounded by the trait"
1646             } else {
1647                 "items from traits can only be used if the trait is implemented and in scope"
1648             });
1649             let candidates_len = candidates.len();
1650             let message = |action| {
1651                 format!(
1652                     "the following {traits_define} an item `{name}`, perhaps you need to {action} \
1653                      {one_of_them}:",
1654                     traits_define =
1655                         if candidates_len == 1 { "trait defines" } else { "traits define" },
1656                     action = action,
1657                     one_of_them = if candidates_len == 1 { "it" } else { "one of them" },
1658                     name = item_name,
1659                 )
1660             };
1661             // Obtain the span for `param` and use it for a structured suggestion.
1662             if let (Some(param), Some(table)) = (param_type, self.in_progress_typeck_results) {
1663                 let table_owner = table.borrow().hir_owner;
1664                 let generics = self.tcx.generics_of(table_owner.to_def_id());
1665                 let type_param = generics.type_param(param, self.tcx);
1666                 let hir = self.tcx.hir();
1667                 if let Some(def_id) = type_param.def_id.as_local() {
1668                     let id = hir.local_def_id_to_hir_id(def_id);
1669                     // Get the `hir::Param` to verify whether it already has any bounds.
1670                     // We do this to avoid suggesting code that ends up as `T: FooBar`,
1671                     // instead we suggest `T: Foo + Bar` in that case.
1672                     match hir.get(id) {
1673                         Node::GenericParam(param) => {
1674                             let mut impl_trait = false;
1675                             let has_bounds =
1676                                 if let hir::GenericParamKind::Type { synthetic: true, .. } =
1677                                     &param.kind
1678                                 {
1679                                     // We've found `fn foo(x: impl Trait)` instead of
1680                                     // `fn foo<T>(x: T)`. We want to suggest the correct
1681                                     // `fn foo(x: impl Trait + TraitBound)` instead of
1682                                     // `fn foo<T: TraitBound>(x: T)`. (#63706)
1683                                     impl_trait = true;
1684                                     param.bounds.get(1)
1685                                 } else {
1686                                     param.bounds.get(0)
1687                                 };
1688                             let sp = hir.span(id);
1689                             let sp = if let Some(first_bound) = has_bounds {
1690                                 // `sp` only covers `T`, change it so that it covers
1691                                 // `T:` when appropriate
1692                                 sp.until(first_bound.span())
1693                             } else {
1694                                 sp
1695                             };
1696                             let trait_def_ids: FxHashSet<DefId> = param
1697                                 .bounds
1698                                 .iter()
1699                                 .filter_map(|bound| bound.trait_ref()?.trait_def_id())
1700                                 .collect();
1701                             if !candidates.iter().any(|t| trait_def_ids.contains(&t.def_id)) {
1702                                 err.span_suggestions(
1703                                     sp,
1704                                     &message(format!(
1705                                         "restrict type parameter `{}` with",
1706                                         param.name.ident(),
1707                                     )),
1708                                     candidates.iter().map(|t| {
1709                                         format!(
1710                                             "{}{} {}{}",
1711                                             param.name.ident(),
1712                                             if impl_trait { " +" } else { ":" },
1713                                             self.tcx.def_path_str(t.def_id),
1714                                             if has_bounds.is_some() { " + " } else { "" },
1715                                         )
1716                                     }),
1717                                     Applicability::MaybeIncorrect,
1718                                 );
1719                             }
1720                             return;
1721                         }
1722                         Node::Item(hir::Item {
1723                             kind: hir::ItemKind::Trait(.., bounds, _),
1724                             ident,
1725                             ..
1726                         }) => {
1727                             let (sp, sep, article) = if bounds.is_empty() {
1728                                 (ident.span.shrink_to_hi(), ":", "a")
1729                             } else {
1730                                 (bounds.last().unwrap().span().shrink_to_hi(), " +", "another")
1731                             };
1732                             err.span_suggestions(
1733                                 sp,
1734                                 &message(format!("add {} supertrait for", article)),
1735                                 candidates.iter().map(|t| {
1736                                     format!("{} {}", sep, self.tcx.def_path_str(t.def_id),)
1737                                 }),
1738                                 Applicability::MaybeIncorrect,
1739                             );
1740                             return;
1741                         }
1742                         _ => {}
1743                     }
1744                 }
1745             }
1746
1747             let (potential_candidates, explicitly_negative) = if param_type.is_some() {
1748                 // FIXME: Even though negative bounds are not implemented, we could maybe handle
1749                 // cases where a positive bound implies a negative impl.
1750                 (candidates, Vec::new())
1751             } else if let Some(simp_rcvr_ty) = simplify_type(self.tcx, rcvr_ty, SimplifyParams::Yes)
1752             {
1753                 let mut potential_candidates = Vec::new();
1754                 let mut explicitly_negative = Vec::new();
1755                 for candidate in candidates {
1756                     // Check if there's a negative impl of `candidate` for `rcvr_ty`
1757                     if self
1758                         .tcx
1759                         .all_impls(candidate.def_id)
1760                         .filter(|imp_did| {
1761                             self.tcx.impl_polarity(*imp_did) == ty::ImplPolarity::Negative
1762                         })
1763                         .any(|imp_did| {
1764                             let imp = self.tcx.impl_trait_ref(imp_did).unwrap();
1765                             let imp_simp =
1766                                 simplify_type(self.tcx, imp.self_ty(), SimplifyParams::Yes);
1767                             imp_simp.map_or(false, |s| s == simp_rcvr_ty)
1768                         })
1769                     {
1770                         explicitly_negative.push(candidate);
1771                     } else {
1772                         potential_candidates.push(candidate);
1773                     }
1774                 }
1775                 (potential_candidates, explicitly_negative)
1776             } else {
1777                 // We don't know enough about `recv_ty` to make proper suggestions.
1778                 (candidates, Vec::new())
1779             };
1780
1781             let action = if let Some(param) = param_type {
1782                 format!("restrict type parameter `{}` with", param)
1783             } else {
1784                 // FIXME: it might only need to be imported into scope, not implemented.
1785                 "implement".to_string()
1786             };
1787             match &potential_candidates[..] {
1788                 [] => {}
1789                 [trait_info] if trait_info.def_id.is_local() => {
1790                     let span = self.tcx.hir().span_if_local(trait_info.def_id).unwrap();
1791                     err.span_note(
1792                         self.tcx.sess.source_map().guess_head_span(span),
1793                         &format!(
1794                             "`{}` defines an item `{}`, perhaps you need to {} it",
1795                             self.tcx.def_path_str(trait_info.def_id),
1796                             item_name,
1797                             action
1798                         ),
1799                     );
1800                 }
1801                 trait_infos => {
1802                     let mut msg = message(action);
1803                     for (i, trait_info) in trait_infos.iter().enumerate() {
1804                         msg.push_str(&format!(
1805                             "\ncandidate #{}: `{}`",
1806                             i + 1,
1807                             self.tcx.def_path_str(trait_info.def_id),
1808                         ));
1809                     }
1810                     err.note(&msg);
1811                 }
1812             }
1813             match &explicitly_negative[..] {
1814                 [] => {}
1815                 [trait_info] => {
1816                     let msg = format!(
1817                         "the trait `{}` defines an item `{}`, but is explicitly unimplemented",
1818                         self.tcx.def_path_str(trait_info.def_id),
1819                         item_name
1820                     );
1821                     err.note(&msg);
1822                 }
1823                 trait_infos => {
1824                     let mut msg = format!(
1825                         "the following traits define an item `{}`, but are explicitly unimplemented:",
1826                         item_name
1827                     );
1828                     for trait_info in trait_infos {
1829                         msg.push_str(&format!("\n{}", self.tcx.def_path_str(trait_info.def_id)));
1830                     }
1831                     err.note(&msg);
1832                 }
1833             }
1834         }
1835     }
1836
1837     /// Checks whether there is a local type somewhere in the chain of
1838     /// autoderefs of `rcvr_ty`.
1839     fn type_derefs_to_local(
1840         &self,
1841         span: Span,
1842         rcvr_ty: Ty<'tcx>,
1843         source: SelfSource<'tcx>,
1844     ) -> bool {
1845         fn is_local(ty: Ty<'_>) -> bool {
1846             match ty.kind() {
1847                 ty::Adt(def, _) => def.did.is_local(),
1848                 ty::Foreign(did) => did.is_local(),
1849                 ty::Dynamic(tr, ..) => tr.principal().map_or(false, |d| d.def_id().is_local()),
1850                 ty::Param(_) => true,
1851
1852                 // Everything else (primitive types, etc.) is effectively
1853                 // non-local (there are "edge" cases, e.g., `(LocalType,)`, but
1854                 // the noise from these sort of types is usually just really
1855                 // annoying, rather than any sort of help).
1856                 _ => false,
1857             }
1858         }
1859
1860         // This occurs for UFCS desugaring of `T::method`, where there is no
1861         // receiver expression for the method call, and thus no autoderef.
1862         if let SelfSource::QPath(_) = source {
1863             return is_local(self.resolve_vars_with_obligations(rcvr_ty));
1864         }
1865
1866         self.autoderef(span, rcvr_ty).any(|(ty, _)| is_local(ty))
1867     }
1868 }
1869
1870 #[derive(Copy, Clone, Debug)]
1871 pub enum SelfSource<'a> {
1872     QPath(&'a hir::Ty<'a>),
1873     MethodCall(&'a hir::Expr<'a> /* rcvr */),
1874 }
1875
1876 #[derive(Copy, Clone)]
1877 pub struct TraitInfo {
1878     pub def_id: DefId,
1879 }
1880
1881 impl PartialEq for TraitInfo {
1882     fn eq(&self, other: &TraitInfo) -> bool {
1883         self.cmp(other) == Ordering::Equal
1884     }
1885 }
1886 impl Eq for TraitInfo {}
1887 impl PartialOrd for TraitInfo {
1888     fn partial_cmp(&self, other: &TraitInfo) -> Option<Ordering> {
1889         Some(self.cmp(other))
1890     }
1891 }
1892 impl Ord for TraitInfo {
1893     fn cmp(&self, other: &TraitInfo) -> Ordering {
1894         // Local crates are more important than remote ones (local:
1895         // `cnum == 0`), and otherwise we throw in the defid for totality.
1896
1897         let lhs = (other.def_id.krate, other.def_id);
1898         let rhs = (self.def_id.krate, self.def_id);
1899         lhs.cmp(&rhs)
1900     }
1901 }
1902
1903 /// Retrieves all traits in this crate and any dependent crates,
1904 /// and wraps them into `TraitInfo` for custom sorting.
1905 pub fn all_traits(tcx: TyCtxt<'_>) -> Vec<TraitInfo> {
1906     tcx.all_traits().map(|def_id| TraitInfo { def_id }).collect()
1907 }
1908
1909 fn find_use_placement<'tcx>(tcx: TyCtxt<'tcx>, target_module: LocalDefId) -> (Option<Span>, bool) {
1910     let mut span = None;
1911     let mut found_use = false;
1912     let (module, _, _) = tcx.hir().get_module(target_module);
1913
1914     // Find a `use` statement.
1915     for &item_id in module.item_ids {
1916         let item = tcx.hir().item(item_id);
1917         match item.kind {
1918             hir::ItemKind::Use(..) => {
1919                 // Don't suggest placing a `use` before the prelude
1920                 // import or other generated ones.
1921                 if !item.span.from_expansion() {
1922                     span = Some(item.span.shrink_to_lo());
1923                     found_use = true;
1924                     break;
1925                 }
1926             }
1927             // Don't place `use` before `extern crate`...
1928             hir::ItemKind::ExternCrate(_) => {}
1929             // ...but do place them before the first other item.
1930             _ => {
1931                 if span.map_or(true, |span| item.span < span) {
1932                     if !item.span.from_expansion() {
1933                         span = Some(item.span.shrink_to_lo());
1934                         // Don't insert between attributes and an item.
1935                         let attrs = tcx.hir().attrs(item.hir_id());
1936                         // Find the first attribute on the item.
1937                         // FIXME: This is broken for active attributes.
1938                         for attr in attrs {
1939                             if !attr.span.is_dummy() && span.map_or(true, |span| attr.span < span) {
1940                                 span = Some(attr.span.shrink_to_lo());
1941                             }
1942                         }
1943                     }
1944                 }
1945             }
1946         }
1947     }
1948
1949     (span, found_use)
1950 }
1951
1952 fn print_disambiguation_help<'tcx>(
1953     item_name: Ident,
1954     args: Option<&'tcx [hir::Expr<'tcx>]>,
1955     err: &mut DiagnosticBuilder<'_>,
1956     trait_name: String,
1957     rcvr_ty: Ty<'_>,
1958     kind: ty::AssocKind,
1959     def_id: DefId,
1960     span: Span,
1961     candidate: Option<usize>,
1962     source_map: &source_map::SourceMap,
1963     fn_has_self_parameter: bool,
1964 ) {
1965     let mut applicability = Applicability::MachineApplicable;
1966     let (span, sugg) = if let (ty::AssocKind::Fn, Some(args)) = (kind, args) {
1967         let args = format!(
1968             "({}{})",
1969             if rcvr_ty.is_region_ptr() {
1970                 if rcvr_ty.is_mutable_ptr() { "&mut " } else { "&" }
1971             } else {
1972                 ""
1973             },
1974             args.iter()
1975                 .map(|arg| source_map.span_to_snippet(arg.span).unwrap_or_else(|_| {
1976                     applicability = Applicability::HasPlaceholders;
1977                     "_".to_owned()
1978                 }))
1979                 .collect::<Vec<_>>()
1980                 .join(", "),
1981         );
1982         let trait_name = if !fn_has_self_parameter {
1983             format!("<{} as {}>", rcvr_ty, trait_name)
1984         } else {
1985             trait_name
1986         };
1987         (span, format!("{}::{}{}", trait_name, item_name, args))
1988     } else {
1989         (span.with_hi(item_name.span.lo()), format!("<{} as {}>::", rcvr_ty, trait_name))
1990     };
1991     err.span_suggestion_verbose(
1992         span,
1993         &format!(
1994             "disambiguate the {} for {}",
1995             kind.as_def_kind().descr(def_id),
1996             if let Some(candidate) = candidate {
1997                 format!("candidate #{}", candidate)
1998             } else {
1999                 "the candidate".to_string()
2000             },
2001         ),
2002         sugg,
2003         applicability,
2004     );
2005 }