src/librustc_typeck/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 crate::middle::lang_items::FnOnceTraitLangItem;
   6 use crate::namespace::Namespace;
   7 use crate::util::nodemap::FxHashSet;
   8 use errors::{Applicability, DiagnosticBuilder};
   9 use rustc::hir::{self, ExprKind, Node, QPath};
  10 use rustc::hir::def::{Res, DefKind};
  11 use rustc::hir::def_id::{CRATE_DEF_INDEX, LOCAL_CRATE, DefId};
  12 use rustc::hir::map as hir_map;
  13 use rustc::hir::print;
  14 use rustc::infer::type_variable::TypeVariableOrigin;
  15 use rustc::traits::Obligation;
  16 use rustc::ty::{self, Ty, TyCtxt, ToPolyTraitRef, ToPredicate, TypeFoldable};
  17 use rustc::ty::print::with_crate_prefix;
  18 use syntax_pos::{Span, FileName};
  19 use syntax::ast;
  20 use syntax::util::lev_distance;
  21
  22 use std::cmp::Ordering;
  23
  24 use super::{MethodError, NoMatchData, CandidateSource};
  25 use super::probe::Mode;
  26
  27 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
  28     fn is_fn_ty(&self, ty: Ty<'tcx>, span: Span) -> bool {
  29         let tcx = self.tcx;
  30         match ty.sty {
  31             // Not all of these (e.g., unsafe fns) implement `FnOnce`,
  32             // so we look for these beforehand.
  33             ty::Closure(..) |
  34             ty::FnDef(..) |
  35             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(FnOnceTraitLangItem) {
  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(ty, &[
  46                             self.next_ty_var(TypeVariableOrigin::MiscVariable(span)).into()
  47                         ]);
  48                         let trait_ref = ty::TraitRef::new(fn_once, fn_once_substs);
  49                         let poly_trait_ref = trait_ref.to_poly_trait_ref();
  50                         let obligation =
  51                             Obligation::misc(span,
  52                                              self.body_id,
  53                                              self.param_env,
  54                                              poly_trait_ref.to_predicate());
  55                         self.predicate_may_hold(&obligation)
  56                     })
  57                 })
  58             }
  59         }
  60     }
  61
  62     pub fn report_method_error<'b>(
  63         &self,
  64         span: Span,
  65         rcvr_ty: Ty<'tcx>,
  66         item_name: ast::Ident,
  67         source: SelfSource<'b>,
  68         error: MethodError<'tcx>,
  69         args: Option<&'gcx [hir::Expr]>,
  70     ) {
  71         let orig_span = span;
  72         let mut span = span;
  73         // Avoid suggestions when we don't know what's going on.
  74         if rcvr_ty.references_error() {
  75             return;
  76         }
  77
  78         let report_candidates = |
  79             span: Span,
  80             err: &mut DiagnosticBuilder<'_>,
  81             mut sources: Vec<CandidateSource>,
  82         | {
  83             sources.sort();
  84             sources.dedup();
  85             // Dynamic limit to avoid hiding just one candidate, which is silly.
  86             let limit = if sources.len() == 5 { 5 } else { 4 };
  87
  88             for (idx, source) in sources.iter().take(limit).enumerate() {
  89                 match *source {
  90                     CandidateSource::ImplSource(impl_did) => {
  91                         // Provide the best span we can. Use the item, if local to crate, else
  92                         // the impl, if local to crate (item may be defaulted), else nothing.
  93                         let item = match self.associated_item(
  94                             impl_did,
  95                             item_name,
  96                             Namespace::Value,
  97                         ).or_else(|| {
  98                             let impl_trait_ref = self.tcx.impl_trait_ref(impl_did)?;
  99                             self.associated_item(
 100                                 impl_trait_ref.def_id,
 101                                 item_name,
 102                                 Namespace::Value,
 103                             )
 104                         }) {
 105                             Some(item) => item,
 106                             None => continue,
 107                         };
 108                         let note_span = self.tcx.hir().span_if_local(item.def_id).or_else(|| {
 109                             self.tcx.hir().span_if_local(impl_did)
 110                         });
 111
 112                         let impl_ty = self.impl_self_ty(span, impl_did).ty;
 113
 114                         let insertion = match self.tcx.impl_trait_ref(impl_did) {
 115                             None => String::new(),
 116                             Some(trait_ref) => {
 117                                 format!(" of the trait `{}`",
 118                                         self.tcx.def_path_str(trait_ref.def_id))
 119                             }
 120                         };
 121
 122                         let note_str = if sources.len() > 1 {
 123                             format!("candidate #{} is defined in an impl{} for the type `{}`",
 124                                     idx + 1,
 125                                     insertion,
 126                                     impl_ty)
 127                         } else {
 128                             format!("the candidate is defined in an impl{} for the type `{}`",
 129                                     insertion,
 130                                     impl_ty)
 131                         };
 132                         if let Some(note_span) = note_span {
 133                             // We have a span pointing to the method. Show note with snippet.
 134                             err.span_note(self.tcx.sess.source_map().def_span(note_span),
 135                                           &note_str);
 136                         } else {
 137                             err.note(&note_str);
 138                         }
 139                     }
 140                     CandidateSource::TraitSource(trait_did) => {
 141                         let item = match self.associated_item(
 142                             trait_did,
 143                             item_name,
 144                             Namespace::Value)
 145                         {
 146                             Some(item) => item,
 147                             None => continue,
 148                         };
 149                         let item_span = self.tcx.sess.source_map()
 150                             .def_span(self.tcx.def_span(item.def_id));
 151                         if sources.len() > 1 {
 152                             span_note!(err,
 153                                        item_span,
 154                                        "candidate #{} is defined in the trait `{}`",
 155                                        idx + 1,
 156                                        self.tcx.def_path_str(trait_did));
 157                         } else {
 158                             span_note!(err,
 159                                        item_span,
 160                                        "the candidate is defined in the trait `{}`",
 161                                        self.tcx.def_path_str(trait_did));
 162                         }
 163                         err.help(&format!("to disambiguate the method call, write `{}::{}({}{})` \
 164                                           instead",
 165                                           self.tcx.def_path_str(trait_did),
 166                                           item_name,
 167                                           if rcvr_ty.is_region_ptr() && args.is_some() {
 168                                               if rcvr_ty.is_mutable_pointer() {
 169                                                   "&mut "
 170                                               } else {
 171                                                   "&"
 172                                               }
 173                                           } else {
 174                                               ""
 175                                           },
 176                                           args.map(|arg| arg.iter()
 177                                               .map(|arg| print::to_string(print::NO_ANN,
 178                                                                           |s| s.print_expr(arg)))
 179                                               .collect::<Vec<_>>()
 180                                               .join(", ")).unwrap_or_else(|| "...".to_owned())));
 181                     }
 182                 }
 183             }
 184             if sources.len() > limit {
 185                 err.note(&format!("and {} others", sources.len() - limit));
 186             }
 187         };
 188
 189         match error {
 190             MethodError::NoMatch(NoMatchData {
 191                 static_candidates: static_sources,
 192                 unsatisfied_predicates,
 193                 out_of_scope_traits,
 194                 lev_candidate,
 195                 mode,
 196             }) => {
 197                 let tcx = self.tcx;
 198
 199                 let actual = self.resolve_type_vars_if_possible(&rcvr_ty);
 200                 let ty_str = self.ty_to_string(actual);
 201                 let is_method = mode == Mode::MethodCall;
 202                 let item_kind = if is_method {
 203                     "method"
 204                 } else if actual.is_enum() {
 205                     "variant or associated item"
 206                 } else {
 207                     match (item_name.as_str().chars().next(), actual.is_fresh_ty()) {
 208                         (Some(name), false) if name.is_lowercase() => {
 209                             "function or associated item"
 210                         }
 211                         (Some(_), false) => "associated item",
 212                         (Some(_), true) | (None, false) => {
 213                             "variant or associated item"
 214                         }
 215                         (None, true) => "variant",
 216                     }
 217                 };
 218                 let mut err = if !actual.references_error() {
 219                     // Suggest clamping down the type if the method that is being attempted to
 220                     // be used exists at all, and the type is an ambiuous numeric type
 221                     // ({integer}/{float}).
 222                     let mut candidates = all_traits(self.tcx)
 223                         .into_iter()
 224                         .filter_map(|info|
 225                             self.associated_item(info.def_id, item_name, Namespace::Value)
 226                         );
 227                     if let (true, false, SelfSource::MethodCall(expr), Some(_)) =
 228                            (actual.is_numeric(),
 229                             actual.has_concrete_skeleton(),
 230                             source,
 231                             candidates.next()) {
 232                         let mut err = struct_span_err!(
 233                             tcx.sess,
 234                             span,
 235                             E0689,
 236                             "can't call {} `{}` on ambiguous numeric type `{}`",
 237                             item_kind,
 238                             item_name,
 239                             ty_str
 240                         );
 241                         let concrete_type = if actual.is_integral() {
 242                             "i32"
 243                         } else {
 244                             "f32"
 245                         };
 246                         match expr.node {
 247                             ExprKind::Lit(ref lit) => {
 248                                 // numeric literal
 249                                 let snippet = tcx.sess.source_map().span_to_snippet(lit.span)
 250                                     .unwrap_or_else(|_| "<numeric literal>".to_owned());
 251
 252                                 err.span_suggestion(
 253                                     lit.span,
 254                                     &format!("you must specify a concrete type for \
 255                                               this numeric value, like `{}`", concrete_type),
 256                                     format!("{}_{}", snippet, concrete_type),
 257                                     Applicability::MaybeIncorrect,
 258                                 );
 259                             }
 260                             ExprKind::Path(ref qpath) => {
 261                                 // local binding
 262                                 if let &QPath::Resolved(_, ref path) = &qpath {
 263                                     if let hir::def::Res::Local(hir_id) = path.res {
 264                                         let span = tcx.hir().span_by_hir_id(hir_id);
 265                                         let snippet = tcx.sess.source_map().span_to_snippet(span);
 266                                         let filename = tcx.sess.source_map().span_to_filename(span);
 267
 268                                         let parent_node = self.tcx.hir().get_by_hir_id(
 269                                             self.tcx.hir().get_parent_node_by_hir_id(hir_id),
 270                                         );
 271                                         let msg = format!(
 272                                             "you must specify a type for this binding, like `{}`",
 273                                             concrete_type,
 274                                         );
 275
 276                                         match (filename, parent_node, snippet) {
 277                                             (FileName::Real(_), Node::Local(hir::Local {
 278                                                 source: hir::LocalSource::Normal,
 279                                                 ty,
 280                                                 ..
 281                                             }), Ok(ref snippet)) => {
 282                                                 err.span_suggestion(
 283                                                     // account for `let x: _ = 42;`
 284                                                     //                  ^^^^
 285                                                     span.to(ty.as_ref().map(|ty| ty.span)
 286                                                         .unwrap_or(span)),
 287                                                     &msg,
 288                                                     format!("{}: {}", snippet, concrete_type),
 289                                                     Applicability::MaybeIncorrect,
 290                                                 );
 291                                             }
 292                                             _ => {
 293                                                 err.span_label(span, msg);
 294                                             }
 295                                         }
 296                                     }
 297                                 }
 298                             }
 299                             _ => {}
 300                         }
 301                         err.emit();
 302                         return;
 303                     } else {
 304                         span = item_name.span;
 305                         let mut err = struct_span_err!(
 306                             tcx.sess,
 307                             span,
 308                             E0599,
 309                             "no {} named `{}` found for type `{}` in the current scope",
 310                             item_kind,
 311                             item_name,
 312                             ty_str
 313                         );
 314                         if let Some(span) = tcx.sess.confused_type_with_std_module.borrow()
 315                             .get(&span)
 316                         {
 317                             if let Ok(snippet) = tcx.sess.source_map().span_to_snippet(*span) {
 318                                 err.span_suggestion(
 319                                     *span,
 320                                     "you are looking for the module in `std`, \
 321                                      not the primitive type",
 322                                     format!("std::{}", snippet),
 323                                     Applicability::MachineApplicable,
 324                                 );
 325                             }
 326                         }
 327                         err
 328                     }
 329                 } else {
 330                     tcx.sess.diagnostic().struct_dummy()
 331                 };
 332
 333                 if let Some(def) = actual.ty_adt_def() {
 334                     if let Some(full_sp) = tcx.hir().span_if_local(def.did) {
 335                         let def_sp = tcx.sess.source_map().def_span(full_sp);
 336                         err.span_label(def_sp, format!("{} `{}` not found {}",
 337                                                        item_kind,
 338                                                        item_name,
 339                                                        if def.is_enum() && !is_method {
 340                                                            "here"
 341                                                        } else {
 342                                                            "for this"
 343                                                        }));
 344                     }
 345                 }
 346
 347                 // If the method name is the name of a field with a function or closure type,
 348                 // give a helping note that it has to be called as `(x.f)(...)`.
 349                 if let SelfSource::MethodCall(expr) = source {
 350                     let field_receiver = self
 351                         .autoderef(span, rcvr_ty)
 352                         .find_map(|(ty, _)| match ty.sty {
 353                             ty::Adt(def, substs) if !def.is_enum() => {
 354                                 let variant = &def.non_enum_variant();
 355                                 self.tcx.find_field_index(item_name, variant).map(|index| {
 356                                     let field = &variant.fields[index];
 357                                     let field_ty = field.ty(tcx, substs);
 358                                     (field, field_ty)
 359                                 })
 360                             }
 361                             _ => None,
 362                         });
 363
 364                     if let Some((field, field_ty)) = field_receiver {
 365                         let scope = self.tcx.hir().get_module_parent_by_hir_id(self.body_id);
 366                         let is_accessible = field.vis.is_accessible_from(scope, self.tcx);
 367
 368                         if is_accessible {
 369                             if self.is_fn_ty(&field_ty, span) {
 370                                 let expr_span = expr.span.to(item_name.span);
 371                                 err.multipart_suggestion(
 372                                     &format!(
 373                                         "to call the function stored in `{}`, \
 374                                          surround the field access with parentheses",
 375                                         item_name,
 376                                     ),
 377                                     vec![
 378                                         (expr_span.shrink_to_lo(), '('.to_string()),
 379                                         (expr_span.shrink_to_hi(), ')'.to_string()),
 380                                     ],
 381                                     Applicability::MachineApplicable,
 382                                 );
 383                             } else {
 384                                 let call_expr = self.tcx.hir().expect_expr_by_hir_id(
 385                                     self.tcx.hir().get_parent_node_by_hir_id(expr.hir_id),
 386                                 );
 387
 388                                 if let Some(span) = call_expr.span.trim_start(item_name.span) {
 389                                     err.span_suggestion(
 390                                         span,
 391                                         "remove the arguments",
 392                                         String::new(),
 393                                         Applicability::MaybeIncorrect,
 394                                     );
 395                                 }
 396                             }
 397                         }
 398
 399                         let field_kind = if is_accessible {
 400                             "field"
 401                         } else {
 402                             "private field"
 403                         };
 404                         err.span_label(item_name.span, format!("{}, not a method", field_kind));
 405                     }
 406                 } else {
 407                     err.span_label(span, format!("{} not found in `{}`", item_kind, ty_str));
 408                     self.tcx.sess.trait_methods_not_found.borrow_mut().insert(orig_span);
 409                 }
 410
 411                 if self.is_fn_ty(&rcvr_ty, span) {
 412                     macro_rules! report_function {
 413                         ($span:expr, $name:expr) => {
 414                             err.note(&format!("{} is a function, perhaps you wish to call it",
 415                                               $name));
 416                         }
 417                     }
 418
 419                     if let SelfSource::MethodCall(expr) = source {
 420                         if let Ok(expr_string) = tcx.sess.source_map().span_to_snippet(expr.span) {
 421                             report_function!(expr.span, expr_string);
 422                         } else if let ExprKind::Path(QPath::Resolved(_, ref path)) =
 423                             expr.node
 424                         {
 425                             if let Some(segment) = path.segments.last() {
 426                                 report_function!(expr.span, segment.ident);
 427                             }
 428                         }
 429                     }
 430                 }
 431
 432                 if !static_sources.is_empty() {
 433                     err.note("found the following associated functions; to be used as methods, \
 434                               functions must have a `self` parameter");
 435                     err.span_label(span, "this is an associated function, not a method");
 436                 }
 437                 if static_sources.len() == 1 {
 438                     if let SelfSource::MethodCall(expr) = source {
 439                         err.span_suggestion(expr.span.to(span),
 440                                             "use associated function syntax instead",
 441                                             format!("{}::{}",
 442                                                     self.ty_to_string(actual),
 443                                                     item_name),
 444                                             Applicability::MachineApplicable);
 445                     } else {
 446                         err.help(&format!("try with `{}::{}`",
 447                                           self.ty_to_string(actual), item_name));
 448                     }
 449
 450                     report_candidates(span, &mut err, static_sources);
 451                 } else if static_sources.len() > 1 {
 452                     report_candidates(span, &mut err, static_sources);
 453                 }
 454
 455                 if !unsatisfied_predicates.is_empty() {
 456                     let mut bound_list = unsatisfied_predicates.iter()
 457                         .map(|p| format!("`{} : {}`", p.self_ty(), p))
 458                         .collect::<Vec<_>>();
 459                     bound_list.sort();
 460                     bound_list.dedup();  // #35677
 461                     let bound_list = bound_list.join("\n");
 462                     err.note(&format!("the method `{}` exists but the following trait bounds \
 463                                        were not satisfied:\n{}",
 464                                       item_name,
 465                                       bound_list));
 466                 }
 467
 468                 if actual.is_numeric() && actual.is_fresh() {
 469
 470                 } else {
 471                     self.suggest_traits_to_import(&mut err,
 472                                                   span,
 473                                                   rcvr_ty,
 474                                                   item_name,
 475                                                   source,
 476                                                   out_of_scope_traits);
 477                 }
 478
 479                 if actual.is_enum() {
 480                     let adt_def = actual.ty_adt_def().expect("enum is not an ADT");
 481                     if let Some(suggestion) = lev_distance::find_best_match_for_name(
 482                         adt_def.variants.iter().map(|s| &s.ident.name),
 483                         &item_name.as_str(),
 484                         None,
 485                     ) {
 486                         err.span_suggestion(
 487                             span,
 488                             "there is a variant with a similar name",
 489                             suggestion.to_string(),
 490                             Applicability::MaybeIncorrect,
 491                         );
 492                     }
 493                 }
 494
 495                 if let Some(lev_candidate) = lev_candidate {
 496                     let def_kind = lev_candidate.def_kind();
 497                     err.span_suggestion(
 498                         span,
 499                         &format!(
 500                             "there is {} {} with a similar name",
 501                             def_kind.article(),
 502                             def_kind.descr(),
 503                         ),
 504                         lev_candidate.ident.to_string(),
 505                         Applicability::MaybeIncorrect,
 506                     );
 507                 }
 508
 509                 err.emit();
 510             }
 511
 512             MethodError::Ambiguity(sources) => {
 513                 let mut err = struct_span_err!(self.sess(),
 514                                                span,
 515                                                E0034,
 516                                                "multiple applicable items in scope");
 517                 err.span_label(span, format!("multiple `{}` found", item_name));
 518
 519                 report_candidates(span, &mut err, sources);
 520                 err.emit();
 521             }
 522
 523             MethodError::PrivateMatch(kind, _, out_of_scope_traits) => {
 524                 let mut err = struct_span_err!(self.tcx.sess, span, E0624,
 525                                                "{} `{}` is private", kind.descr(), item_name);
 526                 self.suggest_valid_traits(&mut err, out_of_scope_traits);
 527                 err.emit();
 528             }
 529
 530             MethodError::IllegalSizedBound(candidates) => {
 531                 let msg = format!("the `{}` method cannot be invoked on a trait object", item_name);
 532                 let mut err = self.sess().struct_span_err(span, &msg);
 533                 if !candidates.is_empty() {
 534                     let help = format!("{an}other candidate{s} {were} found in the following \
 535                                         trait{s}, perhaps add a `use` for {one_of_them}:",
 536                                     an = if candidates.len() == 1 {"an" } else { "" },
 537                                     s = if candidates.len() == 1 { "" } else { "s" },
 538                                     were = if candidates.len() == 1 { "was" } else { "were" },
 539                                     one_of_them = if candidates.len() == 1 {
 540                                         "it"
 541                                     } else {
 542                                         "one_of_them"
 543                                     });
 544                     self.suggest_use_candidates(&mut err, help, candidates);
 545                 }
 546                 err.emit();
 547             }
 548
 549             MethodError::BadReturnType => {
 550                 bug!("no return type expectations but got BadReturnType")
 551             }
 552         }
 553     }
 554
 555     fn suggest_use_candidates(&self,
 556                               err: &mut DiagnosticBuilder<'_>,
 557                               mut msg: String,
 558                               candidates: Vec<DefId>) {
 559         let module_did = self.tcx.hir().get_module_parent_by_hir_id(self.body_id);
 560         let module_id = self.tcx.hir().as_local_hir_id(module_did).unwrap();
 561         let krate = self.tcx.hir().krate();
 562         let (span, found_use) = UsePlacementFinder::check(self.tcx, krate, module_id);
 563         if let Some(span) = span {
 564             let path_strings = candidates.iter().map(|did| {
 565                 // Produce an additional newline to separate the new use statement
 566                 // from the directly following item.
 567                 let additional_newline = if found_use {
 568                     ""
 569                 } else {
 570                     "\n"
 571                 };
 572                 format!(
 573                     "use {};\n{}",
 574                     with_crate_prefix(|| self.tcx.def_path_str(*did)),
 575                     additional_newline
 576                 )
 577             });
 578
 579             err.span_suggestions(span, &msg, path_strings, Applicability::MaybeIncorrect);
 580         } else {
 581             let limit = if candidates.len() == 5 { 5 } else { 4 };
 582             for (i, trait_did) in candidates.iter().take(limit).enumerate() {
 583                 if candidates.len() > 1 {
 584                     msg.push_str(
 585                         &format!(
 586                             "\ncandidate #{}: `use {};`",
 587                             i + 1,
 588                             with_crate_prefix(|| self.tcx.def_path_str(*trait_did))
 589                         )
 590                     );
 591                 } else {
 592                     msg.push_str(
 593                         &format!(
 594                             "\n`use {};`",
 595                             with_crate_prefix(|| self.tcx.def_path_str(*trait_did))
 596                         )
 597                     );
 598                 }
 599             }
 600             if candidates.len() > limit {
 601                 msg.push_str(&format!("\nand {} others", candidates.len() - limit));
 602             }
 603             err.note(&msg[..]);
 604         }
 605     }
 606
 607     fn suggest_valid_traits(&self,
 608                             err: &mut DiagnosticBuilder<'_>,
 609                             valid_out_of_scope_traits: Vec<DefId>) -> bool {
 610         if !valid_out_of_scope_traits.is_empty() {
 611             let mut candidates = valid_out_of_scope_traits;
 612             candidates.sort();
 613             candidates.dedup();
 614             err.help("items from traits can only be used if the trait is in scope");
 615             let msg = format!("the following {traits_are} implemented but not in scope, \
 616                                perhaps add a `use` for {one_of_them}:",
 617                             traits_are = if candidates.len() == 1 {
 618                                 "trait is"
 619                             } else {
 620                                 "traits are"
 621                             },
 622                             one_of_them = if candidates.len() == 1 {
 623                                 "it"
 624                             } else {
 625                                 "one of them"
 626                             });
 627
 628             self.suggest_use_candidates(err, msg, candidates);
 629             true
 630         } else {
 631             false
 632         }
 633     }
 634
 635     fn suggest_traits_to_import<'b>(&self,
 636                                     err: &mut DiagnosticBuilder<'_>,
 637                                     span: Span,
 638                                     rcvr_ty: Ty<'tcx>,
 639                                     item_name: ast::Ident,
 640                                     source: SelfSource<'b>,
 641                                     valid_out_of_scope_traits: Vec<DefId>) {
 642         if self.suggest_valid_traits(err, valid_out_of_scope_traits) {
 643             return;
 644         }
 645
 646         let type_is_local = self.type_derefs_to_local(span, rcvr_ty, source);
 647
 648         // There are no traits implemented, so lets suggest some traits to
 649         // implement, by finding ones that have the item name, and are
 650         // legal to implement.
 651         let mut candidates = all_traits(self.tcx)
 652             .into_iter()
 653             .filter(|info| {
 654                 // We approximate the coherence rules to only suggest
 655                 // traits that are legal to implement by requiring that
 656                 // either the type or trait is local. Multi-dispatch means
 657                 // this isn't perfect (that is, there are cases when
 658                 // implementing a trait would be legal but is rejected
 659                 // here).
 660                 (type_is_local || info.def_id.is_local()) &&
 661                     self.associated_item(info.def_id, item_name, Namespace::Value)
 662                         .filter(|item| {
 663                             // We only want to suggest public or local traits (#45781).
 664                             item.vis == ty::Visibility::Public || info.def_id.is_local()
 665                         })
 666                         .is_some()
 667             })
 668             .collect::<Vec<_>>();
 669
 670         if !candidates.is_empty() {
 671             // Sort from most relevant to least relevant.
 672             candidates.sort_by(|a, b| a.cmp(b).reverse());
 673             candidates.dedup();
 674
 675             // FIXME #21673: this help message could be tuned to the case
 676             // of a type parameter: suggest adding a trait bound rather
 677             // than implementing.
 678             err.help("items from traits can only be used if the trait is implemented and in scope");
 679             let mut msg = format!("the following {traits_define} an item `{name}`, \
 680                                    perhaps you need to implement {one_of_them}:",
 681                                   traits_define = if candidates.len() == 1 {
 682                                       "trait defines"
 683                                   } else {
 684                                       "traits define"
 685                                   },
 686                                   one_of_them = if candidates.len() == 1 {
 687                                       "it"
 688                                   } else {
 689                                       "one of them"
 690                                   },
 691                                   name = item_name);
 692
 693             for (i, trait_info) in candidates.iter().enumerate() {
 694                 msg.push_str(&format!("\ncandidate #{}: `{}`",
 695                                       i + 1,
 696                                       self.tcx.def_path_str(trait_info.def_id)));
 697             }
 698             err.note(&msg[..]);
 699         }
 700     }
 701
 702     /// Checks whether there is a local type somewhere in the chain of
 703     /// autoderefs of `rcvr_ty`.
 704     fn type_derefs_to_local(&self,
 705                             span: Span,
 706                             rcvr_ty: Ty<'tcx>,
 707                             source: SelfSource<'_>) -> bool {
 708         fn is_local(ty: Ty<'_>) -> bool {
 709             match ty.sty {
 710                 ty::Adt(def, _) => def.did.is_local(),
 711                 ty::Foreign(did) => did.is_local(),
 712
 713                 ty::Dynamic(ref tr, ..) =>
 714                     tr.principal().map(|d| d.def_id().is_local()).unwrap_or(false),
 715
 716                 ty::Param(_) => true,
 717
 718                 // Everything else (primitive types, etc.) is effectively
 719                 // non-local (there are "edge" cases, e.g., `(LocalType,)`, but
 720                 // the noise from these sort of types is usually just really
 721                 // annoying, rather than any sort of help).
 722                 _ => false,
 723             }
 724         }
 725
 726         // This occurs for UFCS desugaring of `T::method`, where there is no
 727         // receiver expression for the method call, and thus no autoderef.
 728         if let SelfSource::QPath(_) = source {
 729             return is_local(self.resolve_type_vars_with_obligations(rcvr_ty));
 730         }
 731
 732         self.autoderef(span, rcvr_ty).any(|(ty, _)| is_local(ty))
 733     }
 734 }
 735
 736 #[derive(Copy, Clone)]
 737 pub enum SelfSource<'a> {
 738     QPath(&'a hir::Ty),
 739     MethodCall(&'a hir::Expr /* rcvr */),
 740 }
 741
 742 #[derive(Copy, Clone)]
 743 pub struct TraitInfo {
 744     pub def_id: DefId,
 745 }
 746
 747 impl PartialEq for TraitInfo {
 748     fn eq(&self, other: &TraitInfo) -> bool {
 749         self.cmp(other) == Ordering::Equal
 750     }
 751 }
 752 impl Eq for TraitInfo {}
 753 impl PartialOrd for TraitInfo {
 754     fn partial_cmp(&self, other: &TraitInfo) -> Option<Ordering> {
 755         Some(self.cmp(other))
 756     }
 757 }
 758 impl Ord for TraitInfo {
 759     fn cmp(&self, other: &TraitInfo) -> Ordering {
 760         // Local crates are more important than remote ones (local:
 761         // `cnum == 0`), and otherwise we throw in the defid for totality.
 762
 763         let lhs = (other.def_id.krate, other.def_id);
 764         let rhs = (self.def_id.krate, self.def_id);
 765         lhs.cmp(&rhs)
 766     }
 767 }
 768
 769 /// Retrieves all traits in this crate and any dependent crates.
 770 pub fn all_traits<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Vec<TraitInfo> {
 771     tcx.all_traits(LOCAL_CRATE).iter().map(|&def_id| TraitInfo { def_id }).collect()
 772 }
 773
 774 /// Computes all traits in this crate and any dependent crates.
 775 fn compute_all_traits<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Vec<DefId> {
 776     use hir::itemlikevisit;
 777
 778     let mut traits = vec![];
 779
 780     // Crate-local:
 781
 782     struct Visitor<'a, 'tcx: 'a> {
 783         map: &'a hir_map::Map<'tcx>,
 784         traits: &'a mut Vec<DefId>,
 785     }
 786
 787     impl<'v, 'a, 'tcx> itemlikevisit::ItemLikeVisitor<'v> for Visitor<'a, 'tcx> {
 788         fn visit_item(&mut self, i: &'v hir::Item) {
 789             match i.node {
 790                 hir::ItemKind::Trait(..) |
 791                 hir::ItemKind::TraitAlias(..) => {
 792                     let def_id = self.map.local_def_id_from_hir_id(i.hir_id);
 793                     self.traits.push(def_id);
 794                 }
 795                 _ => ()
 796             }
 797         }
 798
 799         fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) {}
 800
 801         fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) {}
 802     }
 803
 804     tcx.hir().krate().visit_all_item_likes(&mut Visitor {
 805         map: &tcx.hir(),
 806         traits: &mut traits,
 807     });
 808
 809     // Cross-crate:
 810
 811     let mut external_mods = FxHashSet::default();
 812     fn handle_external_res(tcx: TyCtxt<'_, '_, '_>,
 813                            traits: &mut Vec<DefId>,
 814                            external_mods: &mut FxHashSet<DefId>,
 815                            res: Res) {
 816         match res {
 817             Res::Def(DefKind::Trait, def_id) |
 818             Res::Def(DefKind::TraitAlias, def_id) => {
 819                 traits.push(def_id);
 820             }
 821             Res::Def(DefKind::Mod, def_id) => {
 822                 if !external_mods.insert(def_id) {
 823                     return;
 824                 }
 825                 for child in tcx.item_children(def_id).iter() {
 826                     handle_external_res(tcx, traits, external_mods, child.res)
 827                 }
 828             }
 829             _ => {}
 830         }
 831     }
 832     for &cnum in tcx.crates().iter() {
 833         let def_id = DefId {
 834             krate: cnum,
 835             index: CRATE_DEF_INDEX,
 836         };
 837         handle_external_res(tcx, &mut traits, &mut external_mods, Res::Def(DefKind::Mod, def_id));
 838     }
 839
 840     traits
 841 }
 842
 843 pub fn provide(providers: &mut ty::query::Providers<'_>) {
 844     providers.all_traits = |tcx, cnum| {
 845         assert_eq!(cnum, LOCAL_CRATE);
 846         &tcx.arena.alloc(compute_all_traits(tcx))[..]
 847     }
 848 }
 849
 850 struct UsePlacementFinder<'a, 'tcx: 'a, 'gcx: 'tcx> {
 851     target_module: hir::HirId,
 852     span: Option<Span>,
 853     found_use: bool,
 854     tcx: TyCtxt<'a, 'gcx, 'tcx>
 855 }
 856
 857 impl<'a, 'tcx, 'gcx> UsePlacementFinder<'a, 'tcx, 'gcx> {
 858     fn check(
 859         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 860         krate: &'tcx hir::Crate,
 861         target_module: hir::HirId,
 862     ) -> (Option<Span>, bool) {
 863         let mut finder = UsePlacementFinder {
 864             target_module,
 865             span: None,
 866             found_use: false,
 867             tcx,
 868         };
 869         hir::intravisit::walk_crate(&mut finder, krate);
 870         (finder.span, finder.found_use)
 871     }
 872 }
 873
 874 impl<'a, 'tcx, 'gcx> hir::intravisit::Visitor<'tcx> for UsePlacementFinder<'a, 'tcx, 'gcx> {
 875     fn visit_mod(
 876         &mut self,
 877         module: &'tcx hir::Mod,
 878         _: Span,
 879         hir_id: hir::HirId,
 880     ) {
 881         if self.span.is_some() {
 882             return;
 883         }
 884         if hir_id != self.target_module {
 885             hir::intravisit::walk_mod(self, module, hir_id);
 886             return;
 887         }
 888         // Find a `use` statement.
 889         for item_id in &module.item_ids {
 890             let item = self.tcx.hir().expect_item_by_hir_id(item_id.id);
 891             match item.node {
 892                 hir::ItemKind::Use(..) => {
 893                     // Don't suggest placing a `use` before the prelude
 894                     // import or other generated ones.
 895                     if item.span.ctxt().outer().expn_info().is_none() {
 896                         self.span = Some(item.span.shrink_to_lo());
 897                         self.found_use = true;
 898                         return;
 899                     }
 900                 },
 901                 // Don't place `use` before `extern crate`...
 902                 hir::ItemKind::ExternCrate(_) => {}
 903                 // ...but do place them before the first other item.
 904                 _ => if self.span.map_or(true, |span| item.span < span ) {
 905                     if item.span.ctxt().outer().expn_info().is_none() {
 906                         // Don't insert between attributes and an item.
 907                         if item.attrs.is_empty() {
 908                             self.span = Some(item.span.shrink_to_lo());
 909                         } else {
 910                             // Find the first attribute on the item.
 911                             for attr in &item.attrs {
 912                                 if self.span.map_or(true, |span| attr.span < span) {
 913                                     self.span = Some(attr.span.shrink_to_lo());
 914                                 }
 915                             }
 916                         }
 917                     }
 918                 },
 919             }
 920         }
 921     }
 922
 923     fn nested_visit_map<'this>(
 924         &'this mut self
 925     ) -> hir::intravisit::NestedVisitorMap<'this, 'tcx> {
 926         hir::intravisit::NestedVisitorMap::None
 927     }
 928 }