compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs

   1 pub mod on_unimplemented;
   2 pub mod suggestions;
   3
   4 use super::{
   5     EvaluationResult, FulfillmentError, FulfillmentErrorCode, MismatchedProjectionTypes,
   6     Obligation, ObligationCause, ObligationCauseCode, OnUnimplementedDirective,
   7     OnUnimplementedNote, OutputTypeParameterMismatch, Overflow, PredicateObligation,
   8     SelectionContext, SelectionError, TraitNotObjectSafe,
   9 };
  10
  11 use crate::infer::error_reporting::{TyCategory, TypeAnnotationNeeded as ErrorCode};
  12 use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
  13 use crate::infer::{self, InferCtxt, TyCtxtInferExt};
  14 use rustc_data_structures::fx::FxHashMap;
  15 use rustc_errors::{pluralize, struct_span_err, Applicability, DiagnosticBuilder, ErrorReported};
  16 use rustc_hir as hir;
  17 use rustc_hir::def_id::DefId;
  18 use rustc_hir::intravisit::Visitor;
  19 use rustc_hir::GenericParam;
  20 use rustc_hir::Item;
  21 use rustc_hir::Node;
  22 use rustc_middle::thir::abstract_const::NotConstEvaluatable;
  23 use rustc_middle::ty::error::ExpectedFound;
  24 use rustc_middle::ty::fast_reject::{self, SimplifyParams, StripReferences};
  25 use rustc_middle::ty::fold::TypeFolder;
  26 use rustc_middle::ty::{
  27     self, AdtKind, SubtypePredicate, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable,
  28 };
  29 use rustc_session::DiagnosticMessageId;
  30 use rustc_span::symbol::{kw, sym};
  31 use rustc_span::{ExpnKind, MultiSpan, Span, DUMMY_SP};
  32 use std::fmt;
  33 use std::iter;
  34
  35 use crate::traits::query::evaluate_obligation::InferCtxtExt as _;
  36 use crate::traits::query::normalize::AtExt as _;
  37 use crate::traits::specialize::to_pretty_impl_header;
  38 use on_unimplemented::InferCtxtExt as _;
  39 use suggestions::InferCtxtExt as _;
  40
  41 pub use rustc_infer::traits::error_reporting::*;
  42
  43 pub trait InferCtxtExt<'tcx> {
  44     fn report_fulfillment_errors(
  45         &self,
  46         errors: &[FulfillmentError<'tcx>],
  47         body_id: Option<hir::BodyId>,
  48         fallback_has_occurred: bool,
  49     );
  50
  51     fn report_overflow_error<T>(
  52         &self,
  53         obligation: &Obligation<'tcx, T>,
  54         suggest_increasing_limit: bool,
  55     ) -> !
  56     where
  57         T: fmt::Display + TypeFoldable<'tcx>;
  58
  59     fn report_overflow_error_cycle(&self, cycle: &[PredicateObligation<'tcx>]) -> !;
  60
  61     /// The `root_obligation` parameter should be the `root_obligation` field
  62     /// from a `FulfillmentError`. If no `FulfillmentError` is available,
  63     /// then it should be the same as `obligation`.
  64     fn report_selection_error(
  65         &self,
  66         obligation: PredicateObligation<'tcx>,
  67         root_obligation: &PredicateObligation<'tcx>,
  68         error: &SelectionError<'tcx>,
  69         fallback_has_occurred: bool,
  70     );
  71
  72     /// Given some node representing a fn-like thing in the HIR map,
  73     /// returns a span and `ArgKind` information that describes the
  74     /// arguments it expects. This can be supplied to
  75     /// `report_arg_count_mismatch`.
  76     fn get_fn_like_arguments(&self, node: Node<'_>) -> Option<(Span, Vec<ArgKind>)>;
  77
  78     /// Reports an error when the number of arguments needed by a
  79     /// trait match doesn't match the number that the expression
  80     /// provides.
  81     fn report_arg_count_mismatch(
  82         &self,
  83         span: Span,
  84         found_span: Option<Span>,
  85         expected_args: Vec<ArgKind>,
  86         found_args: Vec<ArgKind>,
  87         is_closure: bool,
  88     ) -> DiagnosticBuilder<'tcx>;
  89 }
  90
  91 impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
  92     fn report_fulfillment_errors(
  93         &self,
  94         errors: &[FulfillmentError<'tcx>],
  95         body_id: Option<hir::BodyId>,
  96         fallback_has_occurred: bool,
  97     ) {
  98         #[derive(Debug)]
  99         struct ErrorDescriptor<'tcx> {
 100             predicate: ty::Predicate<'tcx>,
 101             index: Option<usize>, // None if this is an old error
 102         }
 103
 104         let mut error_map: FxHashMap<_, Vec<_>> = self
 105             .reported_trait_errors
 106             .borrow()
 107             .iter()
 108             .map(|(&span, predicates)| {
 109                 (
 110                     span,
 111                     predicates
 112                         .iter()
 113                         .map(|&predicate| ErrorDescriptor { predicate, index: None })
 114                         .collect(),
 115                 )
 116             })
 117             .collect();
 118
 119         for (index, error) in errors.iter().enumerate() {
 120             // We want to ignore desugarings here: spans are equivalent even
 121             // if one is the result of a desugaring and the other is not.
 122             let mut span = error.obligation.cause.span;
 123             let expn_data = span.ctxt().outer_expn_data();
 124             if let ExpnKind::Desugaring(_) = expn_data.kind {
 125                 span = expn_data.call_site;
 126             }
 127
 128             error_map.entry(span).or_default().push(ErrorDescriptor {
 129                 predicate: error.obligation.predicate,
 130                 index: Some(index),
 131             });
 132
 133             self.reported_trait_errors
 134                 .borrow_mut()
 135                 .entry(span)
 136                 .or_default()
 137                 .push(error.obligation.predicate);
 138         }
 139
 140         // We do this in 2 passes because we want to display errors in order, though
 141         // maybe it *is* better to sort errors by span or something.
 142         let mut is_suppressed = vec![false; errors.len()];
 143         for (_, error_set) in error_map.iter() {
 144             // We want to suppress "duplicate" errors with the same span.
 145             for error in error_set {
 146                 if let Some(index) = error.index {
 147                     // Suppress errors that are either:
 148                     // 1) strictly implied by another error.
 149                     // 2) implied by an error with a smaller index.
 150                     for error2 in error_set {
 151                         if error2.index.map_or(false, |index2| is_suppressed[index2]) {
 152                             // Avoid errors being suppressed by already-suppressed
 153                             // errors, to prevent all errors from being suppressed
 154                             // at once.
 155                             continue;
 156                         }
 157
 158                         if self.error_implies(error2.predicate, error.predicate)
 159                             && !(error2.index >= error.index
 160                                 && self.error_implies(error.predicate, error2.predicate))
 161                         {
 162                             info!("skipping {:?} (implied by {:?})", error, error2);
 163                             is_suppressed[index] = true;
 164                             break;
 165                         }
 166                     }
 167                 }
 168             }
 169         }
 170
 171         for (error, suppressed) in iter::zip(errors, is_suppressed) {
 172             if !suppressed {
 173                 self.report_fulfillment_error(error, body_id, fallback_has_occurred);
 174             }
 175         }
 176     }
 177
 178     /// Reports that an overflow has occurred and halts compilation. We
 179     /// halt compilation unconditionally because it is important that
 180     /// overflows never be masked -- they basically represent computations
 181     /// whose result could not be truly determined and thus we can't say
 182     /// if the program type checks or not -- and they are unusual
 183     /// occurrences in any case.
 184     fn report_overflow_error<T>(
 185         &self,
 186         obligation: &Obligation<'tcx, T>,
 187         suggest_increasing_limit: bool,
 188     ) -> !
 189     where
 190         T: fmt::Display + TypeFoldable<'tcx>,
 191     {
 192         let predicate = self.resolve_vars_if_possible(obligation.predicate.clone());
 193         let mut err = struct_span_err!(
 194             self.tcx.sess,
 195             obligation.cause.span,
 196             E0275,
 197             "overflow evaluating the requirement `{}`",
 198             predicate
 199         );
 200
 201         if suggest_increasing_limit {
 202             self.suggest_new_overflow_limit(&mut err);
 203         }
 204
 205         self.note_obligation_cause_code(
 206             &mut err,
 207             &obligation.predicate,
 208             obligation.param_env,
 209             obligation.cause.code(),
 210             &mut vec![],
 211             &mut Default::default(),
 212         );
 213
 214         err.emit();
 215         self.tcx.sess.abort_if_errors();
 216         bug!();
 217     }
 218
 219     /// Reports that a cycle was detected which led to overflow and halts
 220     /// compilation. This is equivalent to `report_overflow_error` except
 221     /// that we can give a more helpful error message (and, in particular,
 222     /// we do not suggest increasing the overflow limit, which is not
 223     /// going to help).
 224     fn report_overflow_error_cycle(&self, cycle: &[PredicateObligation<'tcx>]) -> ! {
 225         let cycle = self.resolve_vars_if_possible(cycle.to_owned());
 226         assert!(!cycle.is_empty());
 227
 228         debug!("report_overflow_error_cycle: cycle={:?}", cycle);
 229
 230         // The 'deepest' obligation is most likely to have a useful
 231         // cause 'backtrace'
 232         self.report_overflow_error(cycle.iter().max_by_key(|p| p.recursion_depth).unwrap(), false);
 233     }
 234
 235     fn report_selection_error(
 236         &self,
 237         mut obligation: PredicateObligation<'tcx>,
 238         root_obligation: &PredicateObligation<'tcx>,
 239         error: &SelectionError<'tcx>,
 240         fallback_has_occurred: bool,
 241     ) {
 242         let tcx = self.tcx;
 243         let mut span = obligation.cause.span;
 244
 245         let mut err = match *error {
 246             SelectionError::Ambiguous(ref impls) => {
 247                 let mut err = self.tcx.sess.struct_span_err(
 248                     obligation.cause.span,
 249                     &format!("multiple applicable `impl`s for `{}`", obligation.predicate),
 250                 );
 251                 self.annotate_source_of_ambiguity(&mut err, impls, obligation.predicate);
 252                 err.emit();
 253                 return;
 254             }
 255             SelectionError::Unimplemented => {
 256                 // If this obligation was generated as a result of well-formedness checking, see if we
 257                 // can get a better error message by performing HIR-based well-formedness checking.
 258                 if let ObligationCauseCode::WellFormed(Some(wf_loc)) =
 259                     root_obligation.cause.code().peel_derives()
 260                 {
 261                     if let Some(cause) = self
 262                         .tcx
 263                         .diagnostic_hir_wf_check((tcx.erase_regions(obligation.predicate), *wf_loc))
 264                     {
 265                         obligation.cause = cause;
 266                         span = obligation.cause.span;
 267                     }
 268                 }
 269                 if let ObligationCauseCode::CompareImplMethodObligation {
 270                     impl_item_def_id,
 271                     trait_item_def_id,
 272                 }
 273                 | ObligationCauseCode::CompareImplTypeObligation {
 274                     impl_item_def_id,
 275                     trait_item_def_id,
 276                 } = *obligation.cause.code()
 277                 {
 278                     self.report_extra_impl_obligation(
 279                         span,
 280                         impl_item_def_id,
 281                         trait_item_def_id,
 282                         &format!("`{}`", obligation.predicate),
 283                     )
 284                     .emit();
 285                     return;
 286                 }
 287
 288                 let bound_predicate = obligation.predicate.kind();
 289                 match bound_predicate.skip_binder() {
 290                     ty::PredicateKind::Trait(trait_predicate) => {
 291                         let trait_predicate = bound_predicate.rebind(trait_predicate);
 292                         let mut trait_predicate = self.resolve_vars_if_possible(trait_predicate);
 293
 294                         trait_predicate.remap_constness_diag(obligation.param_env);
 295                         let predicate_is_const = ty::BoundConstness::ConstIfConst
 296                             == trait_predicate.skip_binder().constness;
 297
 298                         if self.tcx.sess.has_errors() && trait_predicate.references_error() {
 299                             return;
 300                         }
 301                         let trait_ref = trait_predicate.to_poly_trait_ref();
 302                         let (post_message, pre_message, type_def) = self
 303                             .get_parent_trait_ref(obligation.cause.code())
 304                             .map(|(t, s)| {
 305                                 (
 306                                     format!(" in `{}`", t),
 307                                     format!("within `{}`, ", t),
 308                                     s.map(|s| (format!("within this `{}`", t), s)),
 309                                 )
 310                             })
 311                             .unwrap_or_default();
 312
 313                         let OnUnimplementedNote { message, label, note, enclosing_scope } =
 314                             self.on_unimplemented_note(trait_ref, &obligation);
 315                         let have_alt_message = message.is_some() || label.is_some();
 316                         let is_try_conversion = self.is_try_conversion(span, trait_ref.def_id());
 317                         let is_unsize =
 318                             { Some(trait_ref.def_id()) == self.tcx.lang_items().unsize_trait() };
 319                         let (message, note) = if is_try_conversion {
 320                             (
 321                                 Some(format!(
 322                                     "`?` couldn't convert the error to `{}`",
 323                                     trait_ref.skip_binder().self_ty(),
 324                                 )),
 325                                 Some(
 326                                     "the question mark operation (`?`) implicitly performs a \
 327                                         conversion on the error value using the `From` trait"
 328                                         .to_owned(),
 329                                 ),
 330                             )
 331                         } else {
 332                             (message, note)
 333                         };
 334
 335                         let mut err = struct_span_err!(
 336                             self.tcx.sess,
 337                             span,
 338                             E0277,
 339                             "{}",
 340                             (!predicate_is_const).then(|| message).flatten().unwrap_or_else(
 341                                 || format!(
 342                                     "the trait bound `{}` is not satisfied{}",
 343                                     trait_predicate, post_message,
 344                                 )
 345                             )
 346                         );
 347
 348                         if is_try_conversion {
 349                             let none_error = self
 350                                 .tcx
 351                                 .get_diagnostic_item(sym::none_error)
 352                                 .map(|def_id| tcx.type_of(def_id));
 353                             let should_convert_option_to_result =
 354                                 Some(trait_ref.skip_binder().substs.type_at(1)) == none_error;
 355                             let should_convert_result_to_option =
 356                                 Some(trait_ref.self_ty().skip_binder()) == none_error;
 357                             if should_convert_option_to_result {
 358                                 err.span_suggestion_verbose(
 359                                     span.shrink_to_lo(),
 360                                     "consider converting the `Option<T>` into a `Result<T, _>` \
 361                                      using `Option::ok_or` or `Option::ok_or_else`",
 362                                     ".ok_or_else(|| /* error value */)".to_string(),
 363                                     Applicability::HasPlaceholders,
 364                                 );
 365                             } else if should_convert_result_to_option {
 366                                 err.span_suggestion_verbose(
 367                                     span.shrink_to_lo(),
 368                                     "consider converting the `Result<T, _>` into an `Option<T>` \
 369                                      using `Result::ok`",
 370                                     ".ok()".to_string(),
 371                                     Applicability::MachineApplicable,
 372                                 );
 373                             }
 374                             if let Some(ret_span) = self.return_type_span(&obligation) {
 375                                 err.span_label(
 376                                     ret_span,
 377                                     &format!(
 378                                         "expected `{}` because of this",
 379                                         trait_ref.skip_binder().self_ty()
 380                                     ),
 381                                 );
 382                             }
 383                         }
 384
 385                         let explanation = if let ObligationCauseCode::MainFunctionType =
 386                             obligation.cause.code()
 387                         {
 388                             "consider using `()`, or a `Result`".to_owned()
 389                         } else {
 390                             format!(
 391                                 "{}the trait `{}` is not implemented for `{}`",
 392                                 pre_message,
 393                                 trait_predicate.print_modifiers_and_trait_path(),
 394                                 trait_ref.skip_binder().self_ty(),
 395                             )
 396                         };
 397
 398                         if self.suggest_add_reference_to_arg(
 399                             &obligation,
 400                             &mut err,
 401                             trait_predicate,
 402                             have_alt_message,
 403                         ) {
 404                             self.note_obligation_cause(&mut err, &obligation);
 405                             err.emit();
 406                             return;
 407                         }
 408                         if let Some(ref s) = label {
 409                             // If it has a custom `#[rustc_on_unimplemented]`
 410                             // error message, let's display it as the label!
 411                             err.span_label(span, s.as_str());
 412                             if !matches!(trait_ref.skip_binder().self_ty().kind(), ty::Param(_)) {
 413                                 // When the self type is a type param We don't need to "the trait
 414                                 // `std::marker::Sized` is not implemented for `T`" as we will point
 415                                 // at the type param with a label to suggest constraining it.
 416                                 err.help(&explanation);
 417                             }
 418                         } else {
 419                             err.span_label(span, explanation);
 420                         }
 421                         if let Some((msg, span)) = type_def {
 422                             err.span_label(span, &msg);
 423                         }
 424                         if let Some(ref s) = note {
 425                             // If it has a custom `#[rustc_on_unimplemented]` note, let's display it
 426                             err.note(s.as_str());
 427                         }
 428                         if let Some(ref s) = enclosing_scope {
 429                             let body = tcx
 430                                 .hir()
 431                                 .opt_local_def_id(obligation.cause.body_id)
 432                                 .unwrap_or_else(|| {
 433                                     tcx.hir().body_owner_def_id(hir::BodyId {
 434                                         hir_id: obligation.cause.body_id,
 435                                     })
 436                                 });
 437
 438                             let enclosing_scope_span =
 439                                 tcx.hir().span_with_body(tcx.hir().local_def_id_to_hir_id(body));
 440
 441                             err.span_label(enclosing_scope_span, s.as_str());
 442                         }
 443
 444                         self.suggest_dereferences(&obligation, &mut err, trait_predicate);
 445                         self.suggest_fn_call(&obligation, &mut err, trait_predicate);
 446                         self.suggest_remove_reference(&obligation, &mut err, trait_predicate);
 447                         self.suggest_semicolon_removal(
 448                             &obligation,
 449                             &mut err,
 450                             span,
 451                             trait_predicate,
 452                         );
 453                         self.note_version_mismatch(&mut err, &trait_ref);
 454                         self.suggest_remove_await(&obligation, &mut err);
 455
 456                         if Some(trait_ref.def_id()) == tcx.lang_items().try_trait() {
 457                             self.suggest_await_before_try(
 458                                 &mut err,
 459                                 &obligation,
 460                                 trait_predicate,
 461                                 span,
 462                             );
 463                         }
 464
 465                         if self.suggest_impl_trait(&mut err, span, &obligation, trait_predicate) {
 466                             err.emit();
 467                             return;
 468                         }
 469
 470                         if is_unsize {
 471                             // If the obligation failed due to a missing implementation of the
 472                             // `Unsize` trait, give a pointer to why that might be the case
 473                             err.note(
 474                                 "all implementations of `Unsize` are provided \
 475                                 automatically by the compiler, see \
 476                                 <https://doc.rust-lang.org/stable/std/marker/trait.Unsize.html> \
 477                                 for more information",
 478                             );
 479                         }
 480
 481                         let is_fn_trait = [
 482                             self.tcx.lang_items().fn_trait(),
 483                             self.tcx.lang_items().fn_mut_trait(),
 484                             self.tcx.lang_items().fn_once_trait(),
 485                         ]
 486                         .contains(&Some(trait_ref.def_id()));
 487                         let is_target_feature_fn = if let ty::FnDef(def_id, _) =
 488                             *trait_ref.skip_binder().self_ty().kind()
 489                         {
 490                             !self.tcx.codegen_fn_attrs(def_id).target_features.is_empty()
 491                         } else {
 492                             false
 493                         };
 494                         if is_fn_trait && is_target_feature_fn {
 495                             err.note(
 496                                 "`#[target_feature]` functions do not implement the `Fn` traits",
 497                             );
 498                         }
 499
 500                         // Try to report a help message
 501                         if !trait_ref.has_infer_types_or_consts()
 502                             && self.predicate_can_apply(obligation.param_env, trait_ref)
 503                         {
 504                             // If a where-clause may be useful, remind the
 505                             // user that they can add it.
 506                             //
 507                             // don't display an on-unimplemented note, as
 508                             // these notes will often be of the form
 509                             //     "the type `T` can't be frobnicated"
 510                             // which is somewhat confusing.
 511                             self.suggest_restricting_param_bound(
 512                                 &mut err,
 513                                 trait_predicate,
 514                                 obligation.cause.body_id,
 515                             );
 516                         } else if !have_alt_message {
 517                             // Can't show anything else useful, try to find similar impls.
 518                             let impl_candidates = self.find_similar_impl_candidates(trait_ref);
 519                             self.report_similar_impl_candidates(impl_candidates, &mut err);
 520                         }
 521
 522                         // Changing mutability doesn't make a difference to whether we have
 523                         // an `Unsize` impl (Fixes ICE in #71036)
 524                         if !is_unsize {
 525                             self.suggest_change_mut(&obligation, &mut err, trait_predicate);
 526                         }
 527
 528                         // If this error is due to `!: Trait` not implemented but `(): Trait` is
 529                         // implemented, and fallback has occurred, then it could be due to a
 530                         // variable that used to fallback to `()` now falling back to `!`. Issue a
 531                         // note informing about the change in behaviour.
 532                         if trait_predicate.skip_binder().self_ty().is_never()
 533                             && fallback_has_occurred
 534                         {
 535                             let predicate = trait_predicate.map_bound(|mut trait_pred| {
 536                                 trait_pred.trait_ref.substs = self.tcx.mk_substs_trait(
 537                                     self.tcx.mk_unit(),
 538                                     &trait_pred.trait_ref.substs[1..],
 539                                 );
 540                                 trait_pred
 541                             });
 542                             let unit_obligation = obligation.with(predicate.to_predicate(tcx));
 543                             if self.predicate_may_hold(&unit_obligation) {
 544                                 err.note("this trait is implemented for `()`");
 545                                 err.note(
 546                                     "this error might have been caused by changes to \
 547                                     Rust's type-inference algorithm (see issue #48950 \
 548                                     <https://github.com/rust-lang/rust/issues/48950> \
 549                                     for more information)",
 550                                 );
 551                                 err.help("did you intend to use the type `()` here instead?");
 552                             }
 553                         }
 554
 555                         // Return early if the trait is Debug or Display and the invocation
 556                         // originates within a standard library macro, because the output
 557                         // is otherwise overwhelming and unhelpful (see #85844 for an
 558                         // example).
 559
 560                         let in_std_macro =
 561                             match obligation.cause.span.ctxt().outer_expn_data().macro_def_id {
 562                                 Some(macro_def_id) => {
 563                                     let crate_name = tcx.crate_name(macro_def_id.krate);
 564                                     crate_name == sym::std || crate_name == sym::core
 565                                 }
 566                                 None => false,
 567                             };
 568
 569                         if in_std_macro
 570                             && matches!(
 571                                 self.tcx.get_diagnostic_name(trait_ref.def_id()),
 572                                 Some(sym::Debug | sym::Display)
 573                             )
 574                         {
 575                             err.emit();
 576                             return;
 577                         }
 578
 579                         err
 580                     }
 581
 582                     ty::PredicateKind::Subtype(predicate) => {
 583                         // Errors for Subtype predicates show up as
 584                         // `FulfillmentErrorCode::CodeSubtypeError`,
 585                         // not selection error.
 586                         span_bug!(span, "subtype requirement gave wrong error: `{:?}`", predicate)
 587                     }
 588
 589                     ty::PredicateKind::Coerce(predicate) => {
 590                         // Errors for Coerce predicates show up as
 591                         // `FulfillmentErrorCode::CodeSubtypeError`,
 592                         // not selection error.
 593                         span_bug!(span, "coerce requirement gave wrong error: `{:?}`", predicate)
 594                     }
 595
 596                     ty::PredicateKind::RegionOutlives(predicate) => {
 597                         let predicate = bound_predicate.rebind(predicate);
 598                         let predicate = self.resolve_vars_if_possible(predicate);
 599                         let err = self
 600                             .region_outlives_predicate(&obligation.cause, predicate)
 601                             .err()
 602                             .unwrap();
 603                         struct_span_err!(
 604                             self.tcx.sess,
 605                             span,
 606                             E0279,
 607                             "the requirement `{}` is not satisfied (`{}`)",
 608                             predicate,
 609                             err,
 610                         )
 611                     }
 612
 613                     ty::PredicateKind::Projection(..) | ty::PredicateKind::TypeOutlives(..) => {
 614                         let predicate = self.resolve_vars_if_possible(obligation.predicate);
 615                         struct_span_err!(
 616                             self.tcx.sess,
 617                             span,
 618                             E0280,
 619                             "the requirement `{}` is not satisfied",
 620                             predicate
 621                         )
 622                     }
 623
 624                     ty::PredicateKind::ObjectSafe(trait_def_id) => {
 625                         let violations = self.tcx.object_safety_violations(trait_def_id);
 626                         report_object_safety_error(self.tcx, span, trait_def_id, violations)
 627                     }
 628
 629                     ty::PredicateKind::ClosureKind(closure_def_id, closure_substs, kind) => {
 630                         let found_kind = self.closure_kind(closure_substs).unwrap();
 631                         let closure_span =
 632                             self.tcx.sess.source_map().guess_head_span(
 633                                 self.tcx.hir().span_if_local(closure_def_id).unwrap(),
 634                             );
 635                         let mut err = struct_span_err!(
 636                             self.tcx.sess,
 637                             closure_span,
 638                             E0525,
 639                             "expected a closure that implements the `{}` trait, \
 640                              but this closure only implements `{}`",
 641                             kind,
 642                             found_kind
 643                         );
 644
 645                         err.span_label(
 646                             closure_span,
 647                             format!("this closure implements `{}`, not `{}`", found_kind, kind),
 648                         );
 649                         err.span_label(
 650                             obligation.cause.span,
 651                             format!("the requirement to implement `{}` derives from here", kind),
 652                         );
 653
 654                         // Additional context information explaining why the closure only implements
 655                         // a particular trait.
 656                         if let Some(typeck_results) = self.in_progress_typeck_results {
 657                             let hir_id = self
 658                                 .tcx
 659                                 .hir()
 660                                 .local_def_id_to_hir_id(closure_def_id.expect_local());
 661                             let typeck_results = typeck_results.borrow();
 662                             match (found_kind, typeck_results.closure_kind_origins().get(hir_id)) {
 663                                 (ty::ClosureKind::FnOnce, Some((span, place))) => {
 664                                     err.span_label(
 665                                         *span,
 666                                         format!(
 667                                             "closure is `FnOnce` because it moves the \
 668                                          variable `{}` out of its environment",
 669                                             ty::place_to_string_for_capture(tcx, place)
 670                                         ),
 671                                     );
 672                                 }
 673                                 (ty::ClosureKind::FnMut, Some((span, place))) => {
 674                                     err.span_label(
 675                                         *span,
 676                                         format!(
 677                                             "closure is `FnMut` because it mutates the \
 678                                          variable `{}` here",
 679                                             ty::place_to_string_for_capture(tcx, place)
 680                                         ),
 681                                     );
 682                                 }
 683                                 _ => {}
 684                             }
 685                         }
 686
 687                         err.emit();
 688                         return;
 689                     }
 690
 691                     ty::PredicateKind::WellFormed(ty) => {
 692                         if !self.tcx.sess.opts.debugging_opts.chalk {
 693                             // WF predicates cannot themselves make
 694                             // errors. They can only block due to
 695                             // ambiguity; otherwise, they always
 696                             // degenerate into other obligations
 697                             // (which may fail).
 698                             span_bug!(span, "WF predicate not satisfied for {:?}", ty);
 699                         } else {
 700                             // FIXME: we'll need a better message which takes into account
 701                             // which bounds actually failed to hold.
 702                             self.tcx.sess.struct_span_err(
 703                                 span,
 704                                 &format!("the type `{}` is not well-formed (chalk)", ty),
 705                             )
 706                         }
 707                     }
 708
 709                     ty::PredicateKind::ConstEvaluatable(..) => {
 710                         // Errors for `ConstEvaluatable` predicates show up as
 711                         // `SelectionError::ConstEvalFailure`,
 712                         // not `Unimplemented`.
 713                         span_bug!(
 714                             span,
 715                             "const-evaluatable requirement gave wrong error: `{:?}`",
 716                             obligation
 717                         )
 718                     }
 719
 720                     ty::PredicateKind::ConstEquate(..) => {
 721                         // Errors for `ConstEquate` predicates show up as
 722                         // `SelectionError::ConstEvalFailure`,
 723                         // not `Unimplemented`.
 724                         span_bug!(
 725                             span,
 726                             "const-equate requirement gave wrong error: `{:?}`",
 727                             obligation
 728                         )
 729                     }
 730
 731                     ty::PredicateKind::TypeWellFormedFromEnv(..) => span_bug!(
 732                         span,
 733                         "TypeWellFormedFromEnv predicate should only exist in the environment"
 734                     ),
 735                 }
 736             }
 737
 738             OutputTypeParameterMismatch(found_trait_ref, expected_trait_ref, _) => {
 739                 let found_trait_ref = self.resolve_vars_if_possible(found_trait_ref);
 740                 let expected_trait_ref = self.resolve_vars_if_possible(expected_trait_ref);
 741
 742                 if expected_trait_ref.self_ty().references_error() {
 743                     return;
 744                 }
 745
 746                 let found_trait_ty = match found_trait_ref.self_ty().no_bound_vars() {
 747                     Some(ty) => ty,
 748                     None => return,
 749                 };
 750
 751                 let found_did = match *found_trait_ty.kind() {
 752                     ty::Closure(did, _)
 753                     | ty::Foreign(did)
 754                     | ty::FnDef(did, _)
 755                     | ty::Generator(did, ..) => Some(did),
 756                     ty::Adt(def, _) => Some(def.did),
 757                     _ => None,
 758                 };
 759
 760                 let found_span = found_did
 761                     .and_then(|did| self.tcx.hir().span_if_local(did))
 762                     .map(|sp| self.tcx.sess.source_map().guess_head_span(sp)); // the sp could be an fn def
 763
 764                 if self.reported_closure_mismatch.borrow().contains(&(span, found_span)) {
 765                     // We check closures twice, with obligations flowing in different directions,
 766                     // but we want to complain about them only once.
 767                     return;
 768                 }
 769
 770                 self.reported_closure_mismatch.borrow_mut().insert((span, found_span));
 771
 772                 let found = match found_trait_ref.skip_binder().substs.type_at(1).kind() {
 773                     ty::Tuple(ref tys) => vec![ArgKind::empty(); tys.len()],
 774                     _ => vec![ArgKind::empty()],
 775                 };
 776
 777                 let expected_ty = expected_trait_ref.skip_binder().substs.type_at(1);
 778                 let expected = match expected_ty.kind() {
 779                     ty::Tuple(ref tys) => tys
 780                         .iter()
 781                         .map(|t| ArgKind::from_expected_ty(t.expect_ty(), Some(span)))
 782                         .collect(),
 783                     _ => vec![ArgKind::Arg("_".to_owned(), expected_ty.to_string())],
 784                 };
 785
 786                 if found.len() == expected.len() {
 787                     self.report_closure_arg_mismatch(
 788                         span,
 789                         found_span,
 790                         found_trait_ref,
 791                         expected_trait_ref,
 792                     )
 793                 } else {
 794                     let (closure_span, found) = found_did
 795                         .and_then(|did| {
 796                             let node = self.tcx.hir().get_if_local(did)?;
 797                             let (found_span, found) = self.get_fn_like_arguments(node)?;
 798                             Some((Some(found_span), found))
 799                         })
 800                         .unwrap_or((found_span, found));
 801
 802                     self.report_arg_count_mismatch(
 803                         span,
 804                         closure_span,
 805                         expected,
 806                         found,
 807                         found_trait_ty.is_closure(),
 808                     )
 809                 }
 810             }
 811
 812             TraitNotObjectSafe(did) => {
 813                 let violations = self.tcx.object_safety_violations(did);
 814                 report_object_safety_error(self.tcx, span, did, violations)
 815             }
 816
 817             SelectionError::NotConstEvaluatable(NotConstEvaluatable::MentionsInfer) => {
 818                 bug!(
 819                     "MentionsInfer should have been handled in `traits/fulfill.rs` or `traits/select/mod.rs`"
 820                 )
 821             }
 822             SelectionError::NotConstEvaluatable(NotConstEvaluatable::MentionsParam) => {
 823                 if !self.tcx.features().generic_const_exprs {
 824                     let mut err = self.tcx.sess.struct_span_err(
 825                         span,
 826                         "constant expression depends on a generic parameter",
 827                     );
 828                     // FIXME(const_generics): we should suggest to the user how they can resolve this
 829                     // issue. However, this is currently not actually possible
 830                     // (see https://github.com/rust-lang/rust/issues/66962#issuecomment-575907083).
 831                     //
 832                     // Note that with `feature(generic_const_exprs)` this case should not
 833                     // be reachable.
 834                     err.note("this may fail depending on what value the parameter takes");
 835                     err.emit();
 836                     return;
 837                 }
 838
 839                 match obligation.predicate.kind().skip_binder() {
 840                     ty::PredicateKind::ConstEvaluatable(uv) => {
 841                         let mut err =
 842                             self.tcx.sess.struct_span_err(span, "unconstrained generic constant");
 843                         let const_span = self.tcx.def_span(uv.def.did);
 844                         match self.tcx.sess.source_map().span_to_snippet(const_span) {
 845                             Ok(snippet) => err.help(&format!(
 846                                 "try adding a `where` bound using this expression: `where [(); {}]:`",
 847                                 snippet
 848                             )),
 849                             _ => err.help("consider adding a `where` bound using this expression"),
 850                         };
 851                         err
 852                     }
 853                     _ => {
 854                         span_bug!(
 855                             span,
 856                             "unexpected non-ConstEvaluatable predicate, this should not be reachable"
 857                         )
 858                     }
 859                 }
 860             }
 861
 862             // Already reported in the query.
 863             SelectionError::NotConstEvaluatable(NotConstEvaluatable::Error(ErrorReported)) => {
 864                 // FIXME(eddyb) remove this once `ErrorReported` becomes a proof token.
 865                 self.tcx.sess.delay_span_bug(span, "`ErrorReported` without an error");
 866                 return;
 867             }
 868
 869             Overflow => {
 870                 bug!("overflow should be handled before the `report_selection_error` path");
 871             }
 872             SelectionError::ErrorReporting => {
 873                 bug!("ErrorReporting Overflow should not reach `report_selection_err` call")
 874             }
 875         };
 876
 877         self.note_obligation_cause(&mut err, &obligation);
 878         self.point_at_returns_when_relevant(&mut err, &obligation);
 879
 880         err.emit();
 881     }
 882
 883     /// Given some node representing a fn-like thing in the HIR map,
 884     /// returns a span and `ArgKind` information that describes the
 885     /// arguments it expects. This can be supplied to
 886     /// `report_arg_count_mismatch`.
 887     fn get_fn_like_arguments(&self, node: Node<'_>) -> Option<(Span, Vec<ArgKind>)> {
 888         let sm = self.tcx.sess.source_map();
 889         let hir = self.tcx.hir();
 890         Some(match node {
 891             Node::Expr(&hir::Expr {
 892                 kind: hir::ExprKind::Closure(_, ref _decl, id, span, _),
 893                 ..
 894             }) => (
 895                 sm.guess_head_span(span),
 896                 hir.body(id)
 897                     .params
 898                     .iter()
 899                     .map(|arg| {
 900                         if let hir::Pat { kind: hir::PatKind::Tuple(ref args, _), span, .. } =
 901                             *arg.pat
 902                         {
 903                             Some(ArgKind::Tuple(
 904                                 Some(span),
 905                                 args.iter()
 906                                     .map(|pat| {
 907                                         sm.span_to_snippet(pat.span)
 908                                             .ok()
 909                                             .map(|snippet| (snippet, "_".to_owned()))
 910                                     })
 911                                     .collect::<Option<Vec<_>>>()?,
 912                             ))
 913                         } else {
 914                             let name = sm.span_to_snippet(arg.pat.span).ok()?;
 915                             Some(ArgKind::Arg(name, "_".to_owned()))
 916                         }
 917                     })
 918                     .collect::<Option<Vec<ArgKind>>>()?,
 919             ),
 920             Node::Item(&hir::Item { span, kind: hir::ItemKind::Fn(ref sig, ..), .. })
 921             | Node::ImplItem(&hir::ImplItem {
 922                 span,
 923                 kind: hir::ImplItemKind::Fn(ref sig, _),
 924                 ..
 925             })
 926             | Node::TraitItem(&hir::TraitItem {
 927                 span,
 928                 kind: hir::TraitItemKind::Fn(ref sig, _),
 929                 ..
 930             }) => (
 931                 sm.guess_head_span(span),
 932                 sig.decl
 933                     .inputs
 934                     .iter()
 935                     .map(|arg| match arg.kind {
 936                         hir::TyKind::Tup(ref tys) => ArgKind::Tuple(
 937                             Some(arg.span),
 938                             vec![("_".to_owned(), "_".to_owned()); tys.len()],
 939                         ),
 940                         _ => ArgKind::empty(),
 941                     })
 942                     .collect::<Vec<ArgKind>>(),
 943             ),
 944             Node::Ctor(ref variant_data) => {
 945                 let span = variant_data.ctor_hir_id().map_or(DUMMY_SP, |id| hir.span(id));
 946                 let span = sm.guess_head_span(span);
 947                 (span, vec![ArgKind::empty(); variant_data.fields().len()])
 948             }
 949             _ => panic!("non-FnLike node found: {:?}", node),
 950         })
 951     }
 952
 953     /// Reports an error when the number of arguments needed by a
 954     /// trait match doesn't match the number that the expression
 955     /// provides.
 956     fn report_arg_count_mismatch(
 957         &self,
 958         span: Span,
 959         found_span: Option<Span>,
 960         expected_args: Vec<ArgKind>,
 961         found_args: Vec<ArgKind>,
 962         is_closure: bool,
 963     ) -> DiagnosticBuilder<'tcx> {
 964         let kind = if is_closure { "closure" } else { "function" };
 965
 966         let args_str = |arguments: &[ArgKind], other: &[ArgKind]| {
 967             let arg_length = arguments.len();
 968             let distinct = matches!(other, &[ArgKind::Tuple(..)]);
 969             match (arg_length, arguments.get(0)) {
 970                 (1, Some(&ArgKind::Tuple(_, ref fields))) => {
 971                     format!("a single {}-tuple as argument", fields.len())
 972                 }
 973                 _ => format!(
 974                     "{} {}argument{}",
 975                     arg_length,
 976                     if distinct && arg_length > 1 { "distinct " } else { "" },
 977                     pluralize!(arg_length)
 978                 ),
 979             }
 980         };
 981
 982         let expected_str = args_str(&expected_args, &found_args);
 983         let found_str = args_str(&found_args, &expected_args);
 984
 985         let mut err = struct_span_err!(
 986             self.tcx.sess,
 987             span,
 988             E0593,
 989             "{} is expected to take {}, but it takes {}",
 990             kind,
 991             expected_str,
 992             found_str,
 993         );
 994
 995         err.span_label(span, format!("expected {} that takes {}", kind, expected_str));
 996
 997         if let Some(found_span) = found_span {
 998             err.span_label(found_span, format!("takes {}", found_str));
 999
1000             // move |_| { ... }
1001             // ^^^^^^^^-- def_span
1002             //
1003             // move |_| { ... }
1004             // ^^^^^-- prefix
1005             let prefix_span = self.tcx.sess.source_map().span_until_non_whitespace(found_span);
1006             // move |_| { ... }
1007             //      ^^^-- pipe_span
1008             let pipe_span =
1009                 if let Some(span) = found_span.trim_start(prefix_span) { span } else { found_span };
1010
1011             // Suggest to take and ignore the arguments with expected_args_length `_`s if
1012             // found arguments is empty (assume the user just wants to ignore args in this case).
1013             // For example, if `expected_args_length` is 2, suggest `|_, _|`.
1014             if found_args.is_empty() && is_closure {
1015                 let underscores = vec!["_"; expected_args.len()].join(", ");
1016                 err.span_suggestion_verbose(
1017                     pipe_span,
1018                     &format!(
1019                         "consider changing the closure to take and ignore the expected argument{}",
1020                         pluralize!(expected_args.len())
1021                     ),
1022                     format!("|{}|", underscores),
1023                     Applicability::MachineApplicable,
1024                 );
1025             }
1026
1027             if let &[ArgKind::Tuple(_, ref fields)] = &found_args[..] {
1028                 if fields.len() == expected_args.len() {
1029                     let sugg = fields
1030                         .iter()
1031                         .map(|(name, _)| name.to_owned())
1032                         .collect::<Vec<String>>()
1033                         .join(", ");
1034                     err.span_suggestion_verbose(
1035                         found_span,
1036                         "change the closure to take multiple arguments instead of a single tuple",
1037                         format!("|{}|", sugg),
1038                         Applicability::MachineApplicable,
1039                     );
1040                 }
1041             }
1042             if let &[ArgKind::Tuple(_, ref fields)] = &expected_args[..] {
1043                 if fields.len() == found_args.len() && is_closure {
1044                     let sugg = format!(
1045                         "|({}){}|",
1046                         found_args
1047                             .iter()
1048                             .map(|arg| match arg {
1049                                 ArgKind::Arg(name, _) => name.to_owned(),
1050                                 _ => "_".to_owned(),
1051                             })
1052                             .collect::<Vec<String>>()
1053                             .join(", "),
1054                         // add type annotations if available
1055                         if found_args.iter().any(|arg| match arg {
1056                             ArgKind::Arg(_, ty) => ty != "_",
1057                             _ => false,
1058                         }) {
1059                             format!(
1060                                 ": ({})",
1061                                 fields
1062                                     .iter()
1063                                     .map(|(_, ty)| ty.to_owned())
1064                                     .collect::<Vec<String>>()
1065                                     .join(", ")
1066                             )
1067                         } else {
1068                             String::new()
1069                         },
1070                     );
1071                     err.span_suggestion_verbose(
1072                         found_span,
1073                         "change the closure to accept a tuple instead of individual arguments",
1074                         sugg,
1075                         Applicability::MachineApplicable,
1076                     );
1077                 }
1078             }
1079         }
1080
1081         err
1082     }
1083 }
1084
1085 trait InferCtxtPrivExt<'hir, 'tcx> {
1086     // returns if `cond` not occurring implies that `error` does not occur - i.e., that
1087     // `error` occurring implies that `cond` occurs.
1088     fn error_implies(&self, cond: ty::Predicate<'tcx>, error: ty::Predicate<'tcx>) -> bool;
1089
1090     fn report_fulfillment_error(
1091         &self,
1092         error: &FulfillmentError<'tcx>,
1093         body_id: Option<hir::BodyId>,
1094         fallback_has_occurred: bool,
1095     );
1096
1097     fn report_projection_error(
1098         &self,
1099         obligation: &PredicateObligation<'tcx>,
1100         error: &MismatchedProjectionTypes<'tcx>,
1101     );
1102
1103     fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool;
1104
1105     fn describe_generator(&self, body_id: hir::BodyId) -> Option<&'static str>;
1106
1107     fn find_similar_impl_candidates(
1108         &self,
1109         trait_ref: ty::PolyTraitRef<'tcx>,
1110     ) -> Vec<ty::TraitRef<'tcx>>;
1111
1112     fn report_similar_impl_candidates(
1113         &self,
1114         impl_candidates: Vec<ty::TraitRef<'tcx>>,
1115         err: &mut DiagnosticBuilder<'_>,
1116     );
1117
1118     /// Gets the parent trait chain start
1119     fn get_parent_trait_ref(
1120         &self,
1121         code: &ObligationCauseCode<'tcx>,
1122     ) -> Option<(String, Option<Span>)>;
1123
1124     /// If the `Self` type of the unsatisfied trait `trait_ref` implements a trait
1125     /// with the same path as `trait_ref`, a help message about
1126     /// a probable version mismatch is added to `err`
1127     fn note_version_mismatch(
1128         &self,
1129         err: &mut DiagnosticBuilder<'_>,
1130         trait_ref: &ty::PolyTraitRef<'tcx>,
1131     );
1132
1133     /// Creates a `PredicateObligation` with `new_self_ty` replacing the existing type in the
1134     /// `trait_ref`.
1135     ///
1136     /// For this to work, `new_self_ty` must have no escaping bound variables.
1137     fn mk_trait_obligation_with_new_self_ty(
1138         &self,
1139         param_env: ty::ParamEnv<'tcx>,
1140         trait_ref: ty::PolyTraitPredicate<'tcx>,
1141         new_self_ty: Ty<'tcx>,
1142     ) -> PredicateObligation<'tcx>;
1143
1144     fn maybe_report_ambiguity(
1145         &self,
1146         obligation: &PredicateObligation<'tcx>,
1147         body_id: Option<hir::BodyId>,
1148     );
1149
1150     fn predicate_can_apply(
1151         &self,
1152         param_env: ty::ParamEnv<'tcx>,
1153         pred: ty::PolyTraitRef<'tcx>,
1154     ) -> bool;
1155
1156     fn note_obligation_cause(
1157         &self,
1158         err: &mut DiagnosticBuilder<'tcx>,
1159         obligation: &PredicateObligation<'tcx>,
1160     );
1161
1162     fn suggest_unsized_bound_if_applicable(
1163         &self,
1164         err: &mut DiagnosticBuilder<'tcx>,
1165         obligation: &PredicateObligation<'tcx>,
1166     );
1167
1168     fn annotate_source_of_ambiguity(
1169         &self,
1170         err: &mut DiagnosticBuilder<'tcx>,
1171         impls: &[DefId],
1172         predicate: ty::Predicate<'tcx>,
1173     );
1174
1175     fn maybe_suggest_unsized_generics(
1176         &self,
1177         err: &mut DiagnosticBuilder<'tcx>,
1178         span: Span,
1179         node: Node<'hir>,
1180     );
1181
1182     fn maybe_indirection_for_unsized(
1183         &self,
1184         err: &mut DiagnosticBuilder<'tcx>,
1185         item: &'hir Item<'hir>,
1186         param: &'hir GenericParam<'hir>,
1187     ) -> bool;
1188
1189     fn is_recursive_obligation(
1190         &self,
1191         obligated_types: &mut Vec<&ty::TyS<'tcx>>,
1192         cause_code: &ObligationCauseCode<'tcx>,
1193     ) -> bool;
1194 }
1195
1196 impl<'a, 'tcx> InferCtxtPrivExt<'a, 'tcx> for InferCtxt<'a, 'tcx> {
1197     // returns if `cond` not occurring implies that `error` does not occur - i.e., that
1198     // `error` occurring implies that `cond` occurs.
1199     fn error_implies(&self, cond: ty::Predicate<'tcx>, error: ty::Predicate<'tcx>) -> bool {
1200         if cond == error {
1201             return true;
1202         }
1203
1204         // FIXME: It should be possible to deal with `ForAll` in a cleaner way.
1205         let bound_error = error.kind();
1206         let (cond, error) = match (cond.kind().skip_binder(), bound_error.skip_binder()) {
1207             (ty::PredicateKind::Trait(..), ty::PredicateKind::Trait(error)) => {
1208                 (cond, bound_error.rebind(error))
1209             }
1210             _ => {
1211                 // FIXME: make this work in other cases too.
1212                 return false;
1213             }
1214         };
1215
1216         for obligation in super::elaborate_predicates(self.tcx, std::iter::once(cond)) {
1217             let bound_predicate = obligation.predicate.kind();
1218             if let ty::PredicateKind::Trait(implication) = bound_predicate.skip_binder() {
1219                 let error = error.to_poly_trait_ref();
1220                 let implication = bound_predicate.rebind(implication.trait_ref);
1221                 // FIXME: I'm just not taking associated types at all here.
1222                 // Eventually I'll need to implement param-env-aware
1223                 // `Γ₁ ⊦ φ₁ => Γ₂ ⊦ φ₂` logic.
1224                 let param_env = ty::ParamEnv::empty();
1225                 if self.can_sub(param_env, error, implication).is_ok() {
1226                     debug!("error_implies: {:?} -> {:?} -> {:?}", cond, error, implication);
1227                     return true;
1228                 }
1229             }
1230         }
1231
1232         false
1233     }
1234
1235     #[instrument(skip(self), level = "debug")]
1236     fn report_fulfillment_error(
1237         &self,
1238         error: &FulfillmentError<'tcx>,
1239         body_id: Option<hir::BodyId>,
1240         fallback_has_occurred: bool,
1241     ) {
1242         match error.code {
1243             FulfillmentErrorCode::CodeSelectionError(ref selection_error) => {
1244                 self.report_selection_error(
1245                     error.obligation.clone(),
1246                     &error.root_obligation,
1247                     selection_error,
1248                     fallback_has_occurred,
1249                 );
1250             }
1251             FulfillmentErrorCode::CodeProjectionError(ref e) => {
1252                 self.report_projection_error(&error.obligation, e);
1253             }
1254             FulfillmentErrorCode::CodeAmbiguity => {
1255                 self.maybe_report_ambiguity(&error.obligation, body_id);
1256             }
1257             FulfillmentErrorCode::CodeSubtypeError(ref expected_found, ref err) => {
1258                 self.report_mismatched_types(
1259                     &error.obligation.cause,
1260                     expected_found.expected,
1261                     expected_found.found,
1262                     err.clone(),
1263                 )
1264                 .emit();
1265             }
1266             FulfillmentErrorCode::CodeConstEquateError(ref expected_found, ref err) => {
1267                 self.report_mismatched_consts(
1268                     &error.obligation.cause,
1269                     expected_found.expected,
1270                     expected_found.found,
1271                     err.clone(),
1272                 )
1273                 .emit();
1274             }
1275         }
1276     }
1277
1278     fn report_projection_error(
1279         &self,
1280         obligation: &PredicateObligation<'tcx>,
1281         error: &MismatchedProjectionTypes<'tcx>,
1282     ) {
1283         let predicate = self.resolve_vars_if_possible(obligation.predicate);
1284
1285         if predicate.references_error() {
1286             return;
1287         }
1288
1289         self.probe(|_| {
1290             let err_buf;
1291             let mut err = &error.err;
1292             let mut values = None;
1293
1294             // try to find the mismatched types to report the error with.
1295             //
1296             // this can fail if the problem was higher-ranked, in which
1297             // cause I have no idea for a good error message.
1298             let bound_predicate = predicate.kind();
1299             if let ty::PredicateKind::Projection(data) = bound_predicate.skip_binder() {
1300                 let mut selcx = SelectionContext::new(self);
1301                 let (data, _) = self.replace_bound_vars_with_fresh_vars(
1302                     obligation.cause.span,
1303                     infer::LateBoundRegionConversionTime::HigherRankedType,
1304                     bound_predicate.rebind(data),
1305                 );
1306                 let mut obligations = vec![];
1307                 let normalized_ty = super::normalize_projection_type(
1308                     &mut selcx,
1309                     obligation.param_env,
1310                     data.projection_ty,
1311                     obligation.cause.clone(),
1312                     0,
1313                     &mut obligations,
1314                 );
1315
1316                 debug!(
1317                     "report_projection_error obligation.cause={:?} obligation.param_env={:?}",
1318                     obligation.cause, obligation.param_env
1319                 );
1320
1321                 debug!(
1322                     "report_projection_error normalized_ty={:?} data.ty={:?}",
1323                     normalized_ty, data.term,
1324                 );
1325
1326                 let is_normalized_ty_expected = !matches!(
1327                     obligation.cause.code().peel_derives(),
1328                     ObligationCauseCode::ItemObligation(_)
1329                         | ObligationCauseCode::BindingObligation(_, _)
1330                         | ObligationCauseCode::ObjectCastObligation(_)
1331                         | ObligationCauseCode::OpaqueType
1332                 );
1333                 // FIXME(associated_const_equality): Handle Consts here
1334                 let data_ty = data.term.ty().unwrap();
1335                 if let Err(error) = self.at(&obligation.cause, obligation.param_env).eq_exp(
1336                     is_normalized_ty_expected,
1337                     normalized_ty,
1338                     data_ty,
1339                 ) {
1340                     values = Some(infer::ValuePairs::Types(ExpectedFound::new(
1341                         is_normalized_ty_expected,
1342                         normalized_ty,
1343                         data_ty,
1344                     )));
1345
1346                     err_buf = error;
1347                     err = &err_buf;
1348                 }
1349             }
1350
1351             let msg = format!("type mismatch resolving `{}`", predicate);
1352             let error_id = (DiagnosticMessageId::ErrorId(271), Some(obligation.cause.span), msg);
1353             let fresh = self.tcx.sess.one_time_diagnostics.borrow_mut().insert(error_id);
1354             if fresh {
1355                 let mut diag = struct_span_err!(
1356                     self.tcx.sess,
1357                     obligation.cause.span,
1358                     E0271,
1359                     "type mismatch resolving `{}`",
1360                     predicate
1361                 );
1362                 let secondary_span = match predicate.kind().skip_binder() {
1363                     ty::PredicateKind::Projection(proj) => self
1364                         .tcx
1365                         .opt_associated_item(proj.projection_ty.item_def_id)
1366                         .and_then(|trait_assoc_item| {
1367                             self.tcx
1368                                 .trait_of_item(proj.projection_ty.item_def_id)
1369                                 .map(|id| (trait_assoc_item, id))
1370                         })
1371                         .and_then(|(trait_assoc_item, id)| {
1372                             self.tcx.find_map_relevant_impl(
1373                                 id,
1374                                 proj.projection_ty.self_ty(),
1375                                 |did| {
1376                                     self.tcx
1377                                         .associated_items(did)
1378                                         .in_definition_order()
1379                                         .filter(|assoc| assoc.ident == trait_assoc_item.ident)
1380                                         .next()
1381                                 },
1382                             )
1383                         })
1384                         .and_then(|item| match self.tcx.hir().get_if_local(item.def_id) {
1385                             Some(
1386                                 hir::Node::TraitItem(hir::TraitItem {
1387                                     kind: hir::TraitItemKind::Type(_, Some(ty)),
1388                                     ..
1389                                 })
1390                                 | hir::Node::ImplItem(hir::ImplItem {
1391                                     kind: hir::ImplItemKind::TyAlias(ty),
1392                                     ..
1393                                 }),
1394                             ) => {
1395                                 Some((ty.span, format!("type mismatch resolving `{}`", predicate)))
1396                             }
1397                             _ => None,
1398                         }),
1399                     _ => None,
1400                 };
1401                 self.note_type_err(&mut diag, &obligation.cause, secondary_span, values, err, true);
1402                 self.note_obligation_cause(&mut diag, obligation);
1403                 diag.emit();
1404             }
1405         });
1406     }
1407
1408     fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
1409         /// returns the fuzzy category of a given type, or None
1410         /// if the type can be equated to any type.
1411         fn type_category(t: Ty<'_>) -> Option<u32> {
1412             match t.kind() {
1413                 ty::Bool => Some(0),
1414                 ty::Char => Some(1),
1415                 ty::Str => Some(2),
1416                 ty::Int(..) | ty::Uint(..) | ty::Infer(ty::IntVar(..)) => Some(3),
1417                 ty::Float(..) | ty::Infer(ty::FloatVar(..)) => Some(4),
1418                 ty::Ref(..) | ty::RawPtr(..) => Some(5),
1419                 ty::Array(..) | ty::Slice(..) => Some(6),
1420                 ty::FnDef(..) | ty::FnPtr(..) => Some(7),
1421                 ty::Dynamic(..) => Some(8),
1422                 ty::Closure(..) => Some(9),
1423                 ty::Tuple(..) => Some(10),
1424                 ty::Projection(..) => Some(11),
1425                 ty::Param(..) => Some(12),
1426                 ty::Opaque(..) => Some(13),
1427                 ty::Never => Some(14),
1428                 ty::Adt(adt, ..) => match adt.adt_kind() {
1429                     AdtKind::Struct => Some(15),
1430                     AdtKind::Union => Some(16),
1431                     AdtKind::Enum => Some(17),
1432                 },
1433                 ty::Generator(..) => Some(18),
1434                 ty::Foreign(..) => Some(19),
1435                 ty::GeneratorWitness(..) => Some(20),
1436                 ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error(_) => None,
1437             }
1438         }
1439
1440         match (type_category(a), type_category(b)) {
1441             (Some(cat_a), Some(cat_b)) => match (a.kind(), b.kind()) {
1442                 (&ty::Adt(def_a, _), &ty::Adt(def_b, _)) => def_a == def_b,
1443                 _ => cat_a == cat_b,
1444             },
1445             // infer and error can be equated to all types
1446             _ => true,
1447         }
1448     }
1449
1450     fn describe_generator(&self, body_id: hir::BodyId) -> Option<&'static str> {
1451         self.tcx.hir().body(body_id).generator_kind.map(|gen_kind| match gen_kind {
1452             hir::GeneratorKind::Gen => "a generator",
1453             hir::GeneratorKind::Async(hir::AsyncGeneratorKind::Block) => "an async block",
1454             hir::GeneratorKind::Async(hir::AsyncGeneratorKind::Fn) => "an async function",
1455             hir::GeneratorKind::Async(hir::AsyncGeneratorKind::Closure) => "an async closure",
1456         })
1457     }
1458
1459     fn find_similar_impl_candidates(
1460         &self,
1461         trait_ref: ty::PolyTraitRef<'tcx>,
1462     ) -> Vec<ty::TraitRef<'tcx>> {
1463         // We simplify params and strip references here.
1464         //
1465         // This both removes a lot of unhelpful suggestions, e.g.
1466         // when searching for `&Foo: Trait` it doesn't suggestion `impl Trait for &Bar`,
1467         // while also suggesting impls for `&Foo` when we're looking for `Foo: Trait`.
1468         //
1469         // The second thing isn't necessarily always a good thing, but
1470         // any other simple setup results in a far worse output, so 🤷
1471         let simp = fast_reject::simplify_type(
1472             self.tcx,
1473             trait_ref.skip_binder().self_ty(),
1474             SimplifyParams::Yes,
1475             StripReferences::Yes,
1476         );
1477         let all_impls = self.tcx.all_impls(trait_ref.def_id());
1478
1479         match simp {
1480             Some(simp) => all_impls
1481                 .filter_map(|def_id| {
1482                     let imp = self.tcx.impl_trait_ref(def_id).unwrap();
1483                     let imp_simp = fast_reject::simplify_type(
1484                         self.tcx,
1485                         imp.self_ty(),
1486                         SimplifyParams::Yes,
1487                         StripReferences::Yes,
1488                     );
1489                     if let Some(imp_simp) = imp_simp {
1490                         if simp != imp_simp {
1491                             return None;
1492                         }
1493                     }
1494                     if self.tcx.impl_polarity(def_id) == ty::ImplPolarity::Negative {
1495                         return None;
1496                     }
1497                     Some(imp)
1498                 })
1499                 .collect(),
1500             None => all_impls
1501                 .filter_map(|def_id| {
1502                     if self.tcx.impl_polarity(def_id) == ty::ImplPolarity::Negative {
1503                         return None;
1504                     }
1505                     self.tcx.impl_trait_ref(def_id)
1506                 })
1507                 .collect(),
1508         }
1509     }
1510
1511     fn report_similar_impl_candidates(
1512         &self,
1513         impl_candidates: Vec<ty::TraitRef<'tcx>>,
1514         err: &mut DiagnosticBuilder<'_>,
1515     ) {
1516         if impl_candidates.is_empty() {
1517             return;
1518         }
1519
1520         let len = impl_candidates.len();
1521         let end = if impl_candidates.len() <= 5 { impl_candidates.len() } else { 4 };
1522
1523         let normalize = |candidate| {
1524             self.tcx.infer_ctxt().enter(|ref infcx| {
1525                 let normalized = infcx
1526                     .at(&ObligationCause::dummy(), ty::ParamEnv::empty())
1527                     .normalize(candidate)
1528                     .ok();
1529                 match normalized {
1530                     Some(normalized) => format!("\n  {}", normalized.value),
1531                     None => format!("\n  {}", candidate),
1532                 }
1533             })
1534         };
1535
1536         // Sort impl candidates so that ordering is consistent for UI tests.
1537         let mut normalized_impl_candidates =
1538             impl_candidates.iter().copied().map(normalize).collect::<Vec<String>>();
1539
1540         // Sort before taking the `..end` range,
1541         // because the ordering of `impl_candidates` may not be deterministic:
1542         // https://github.com/rust-lang/rust/pull/57475#issuecomment-455519507
1543         normalized_impl_candidates.sort();
1544
1545         err.help(&format!(
1546             "the following implementations were found:{}{}",
1547             normalized_impl_candidates[..end].join(""),
1548             if len > 5 { format!("\nand {} others", len - 4) } else { String::new() }
1549         ));
1550     }
1551
1552     /// Gets the parent trait chain start
1553     fn get_parent_trait_ref(
1554         &self,
1555         code: &ObligationCauseCode<'tcx>,
1556     ) -> Option<(String, Option<Span>)> {
1557         match code {
1558             ObligationCauseCode::BuiltinDerivedObligation(data) => {
1559                 let parent_trait_ref = self.resolve_vars_if_possible(data.parent_trait_pred);
1560                 match self.get_parent_trait_ref(&data.parent_code) {
1561                     Some(t) => Some(t),
1562                     None => {
1563                         let ty = parent_trait_ref.skip_binder().self_ty();
1564                         let span = TyCategory::from_ty(self.tcx, ty)
1565                             .map(|(_, def_id)| self.tcx.def_span(def_id));
1566                         Some((ty.to_string(), span))
1567                     }
1568                 }
1569             }
1570             ObligationCauseCode::FunctionArgumentObligation { parent_code, .. } => {
1571                 self.get_parent_trait_ref(&parent_code)
1572             }
1573             _ => None,
1574         }
1575     }
1576
1577     /// If the `Self` type of the unsatisfied trait `trait_ref` implements a trait
1578     /// with the same path as `trait_ref`, a help message about
1579     /// a probable version mismatch is added to `err`
1580     fn note_version_mismatch(
1581         &self,
1582         err: &mut DiagnosticBuilder<'_>,
1583         trait_ref: &ty::PolyTraitRef<'tcx>,
1584     ) {
1585         let get_trait_impl = |trait_def_id| {
1586             self.tcx.find_map_relevant_impl(trait_def_id, trait_ref.skip_binder().self_ty(), Some)
1587         };
1588         let required_trait_path = self.tcx.def_path_str(trait_ref.def_id());
1589         let traits_with_same_path: std::collections::BTreeSet<_> = self
1590             .tcx
1591             .all_traits()
1592             .filter(|trait_def_id| *trait_def_id != trait_ref.def_id())
1593             .filter(|trait_def_id| self.tcx.def_path_str(*trait_def_id) == required_trait_path)
1594             .collect();
1595         for trait_with_same_path in traits_with_same_path {
1596             if let Some(impl_def_id) = get_trait_impl(trait_with_same_path) {
1597                 let impl_span = self.tcx.def_span(impl_def_id);
1598                 err.span_help(impl_span, "trait impl with same name found");
1599                 let trait_crate = self.tcx.crate_name(trait_with_same_path.krate);
1600                 let crate_msg = format!(
1601                     "perhaps two different versions of crate `{}` are being used?",
1602                     trait_crate
1603                 );
1604                 err.note(&crate_msg);
1605             }
1606         }
1607     }
1608
1609     fn mk_trait_obligation_with_new_self_ty(
1610         &self,
1611         param_env: ty::ParamEnv<'tcx>,
1612         trait_ref: ty::PolyTraitPredicate<'tcx>,
1613         new_self_ty: Ty<'tcx>,
1614     ) -> PredicateObligation<'tcx> {
1615         assert!(!new_self_ty.has_escaping_bound_vars());
1616
1617         let trait_pred = trait_ref.map_bound_ref(|tr| ty::TraitPredicate {
1618             trait_ref: ty::TraitRef {
1619                 substs: self.tcx.mk_substs_trait(new_self_ty, &tr.trait_ref.substs[1..]),
1620                 ..tr.trait_ref
1621             },
1622             ..*tr
1623         });
1624
1625         Obligation::new(ObligationCause::dummy(), param_env, trait_pred.to_predicate(self.tcx))
1626     }
1627
1628     #[instrument(skip(self), level = "debug")]
1629     fn maybe_report_ambiguity(
1630         &self,
1631         obligation: &PredicateObligation<'tcx>,
1632         body_id: Option<hir::BodyId>,
1633     ) {
1634         // Unable to successfully determine, probably means
1635         // insufficient type information, but could mean
1636         // ambiguous impls. The latter *ought* to be a
1637         // coherence violation, so we don't report it here.
1638
1639         let predicate = self.resolve_vars_if_possible(obligation.predicate);
1640         let span = obligation.cause.span;
1641
1642         debug!(?predicate, obligation.cause.code = tracing::field::debug(&obligation.cause.code()));
1643
1644         // Ambiguity errors are often caused as fallout from earlier errors.
1645         // We ignore them if this `infcx` is tainted in some cases below.
1646
1647         let bound_predicate = predicate.kind();
1648         let mut err = match bound_predicate.skip_binder() {
1649             ty::PredicateKind::Trait(data) => {
1650                 let trait_ref = bound_predicate.rebind(data.trait_ref);
1651                 debug!(?trait_ref);
1652
1653                 if predicate.references_error() {
1654                     return;
1655                 }
1656                 // Typically, this ambiguity should only happen if
1657                 // there are unresolved type inference variables
1658                 // (otherwise it would suggest a coherence
1659                 // failure). But given #21974 that is not necessarily
1660                 // the case -- we can have multiple where clauses that
1661                 // are only distinguished by a region, which results
1662                 // in an ambiguity even when all types are fully
1663                 // known, since we don't dispatch based on region
1664                 // relationships.
1665
1666                 // Pick the first substitution that still contains inference variables as the one
1667                 // we're going to emit an error for. If there are none (see above), fall back to
1668                 // the substitution for `Self`.
1669                 let subst = {
1670                     let substs = data.trait_ref.substs;
1671                     substs
1672                         .iter()
1673                         .find(|s| s.has_infer_types_or_consts())
1674                         .unwrap_or_else(|| substs[0])
1675                 };
1676
1677                 // This is kind of a hack: it frequently happens that some earlier
1678                 // error prevents types from being fully inferred, and then we get
1679                 // a bunch of uninteresting errors saying something like "<generic
1680                 // #0> doesn't implement Sized".  It may even be true that we
1681                 // could just skip over all checks where the self-ty is an
1682                 // inference variable, but I was afraid that there might be an
1683                 // inference variable created, registered as an obligation, and
1684                 // then never forced by writeback, and hence by skipping here we'd
1685                 // be ignoring the fact that we don't KNOW the type works
1686                 // out. Though even that would probably be harmless, given that
1687                 // we're only talking about builtin traits, which are known to be
1688                 // inhabited. We used to check for `self.tcx.sess.has_errors()` to
1689                 // avoid inundating the user with unnecessary errors, but we now
1690                 // check upstream for type errors and don't add the obligations to
1691                 // begin with in those cases.
1692                 if self.tcx.lang_items().sized_trait() == Some(trait_ref.def_id()) {
1693                     if !self.is_tainted_by_errors() {
1694                         self.emit_inference_failure_err(
1695                             body_id,
1696                             span,
1697                             subst,
1698                             vec![],
1699                             ErrorCode::E0282,
1700                         )
1701                         .emit();
1702                     }
1703                     return;
1704                 }
1705
1706                 let impl_candidates = self.find_similar_impl_candidates(trait_ref);
1707                 let mut err = self.emit_inference_failure_err(
1708                     body_id,
1709                     span,
1710                     subst,
1711                     impl_candidates,
1712                     ErrorCode::E0283,
1713                 );
1714
1715                 let obligation = Obligation::new(
1716                     obligation.cause.clone(),
1717                     obligation.param_env,
1718                     trait_ref.to_poly_trait_predicate(),
1719                 );
1720                 let mut selcx = SelectionContext::with_query_mode(
1721                     &self,
1722                     crate::traits::TraitQueryMode::Standard,
1723                 );
1724                 match selcx.select_from_obligation(&obligation) {
1725                     Err(SelectionError::Ambiguous(impls)) if impls.len() > 1 => {
1726                         self.annotate_source_of_ambiguity(&mut err, &impls, predicate);
1727                     }
1728                     _ => {
1729                         if self.is_tainted_by_errors() {
1730                             err.cancel();
1731                             return;
1732                         }
1733                         err.note(&format!("cannot satisfy `{}`", predicate));
1734                     }
1735                 }
1736
1737                 if let ObligationCauseCode::ItemObligation(def_id) = *obligation.cause.code() {
1738                     self.suggest_fully_qualified_path(&mut err, def_id, span, trait_ref.def_id());
1739                 } else if let (
1740                     Ok(ref snippet),
1741                     ObligationCauseCode::BindingObligation(ref def_id, _),
1742                 ) =
1743                     (self.tcx.sess.source_map().span_to_snippet(span), obligation.cause.code())
1744                 {
1745                     let generics = self.tcx.generics_of(*def_id);
1746                     if generics.params.iter().any(|p| p.name != kw::SelfUpper)
1747                         && !snippet.ends_with('>')
1748                         && !generics.has_impl_trait()
1749                         && !self.tcx.fn_trait_kind_from_lang_item(*def_id).is_some()
1750                     {
1751                         // FIXME: To avoid spurious suggestions in functions where type arguments
1752                         // where already supplied, we check the snippet to make sure it doesn't
1753                         // end with a turbofish. Ideally we would have access to a `PathSegment`
1754                         // instead. Otherwise we would produce the following output:
1755                         //
1756                         // error[E0283]: type annotations needed
1757                         //   --> $DIR/issue-54954.rs:3:24
1758                         //    |
1759                         // LL | const ARR_LEN: usize = Tt::const_val::<[i8; 123]>();
1760                         //    |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^
1761                         //    |                        |
1762                         //    |                        cannot infer type
1763                         //    |                        help: consider specifying the type argument
1764                         //    |                        in the function call:
1765                         //    |                        `Tt::const_val::<[i8; 123]>::<T>`
1766                         // ...
1767                         // LL |     const fn const_val<T: Sized>() -> usize {
1768                         //    |                        - required by this bound in `Tt::const_val`
1769                         //    |
1770                         //    = note: cannot satisfy `_: Tt`
1771
1772                         err.span_suggestion_verbose(
1773                             span.shrink_to_hi(),
1774                             &format!(
1775                                 "consider specifying the type argument{} in the function call",
1776                                 pluralize!(generics.params.len()),
1777                             ),
1778                             format!(
1779                                 "::<{}>",
1780                                 generics
1781                                     .params
1782                                     .iter()
1783                                     .map(|p| p.name.to_string())
1784                                     .collect::<Vec<String>>()
1785                                     .join(", ")
1786                             ),
1787                             Applicability::HasPlaceholders,
1788                         );
1789                     }
1790                 }
1791                 err
1792             }
1793
1794             ty::PredicateKind::WellFormed(arg) => {
1795                 // Same hacky approach as above to avoid deluging user
1796                 // with error messages.
1797                 if arg.references_error()
1798                     || self.tcx.sess.has_errors()
1799                     || self.is_tainted_by_errors()
1800                 {
1801                     return;
1802                 }
1803
1804                 self.emit_inference_failure_err(body_id, span, arg, vec![], ErrorCode::E0282)
1805             }
1806
1807             ty::PredicateKind::Subtype(data) => {
1808                 if data.references_error()
1809                     || self.tcx.sess.has_errors()
1810                     || self.is_tainted_by_errors()
1811                 {
1812                     // no need to overload user in such cases
1813                     return;
1814                 }
1815                 let SubtypePredicate { a_is_expected: _, a, b } = data;
1816                 // both must be type variables, or the other would've been instantiated
1817                 assert!(a.is_ty_var() && b.is_ty_var());
1818                 self.emit_inference_failure_err(body_id, span, a.into(), vec![], ErrorCode::E0282)
1819             }
1820             ty::PredicateKind::Projection(data) => {
1821                 let self_ty = data.projection_ty.self_ty();
1822                 let term = data.term;
1823                 if predicate.references_error() || self.is_tainted_by_errors() {
1824                     return;
1825                 }
1826                 if self_ty.needs_infer() && term.needs_infer() {
1827                     // We do this for the `foo.collect()?` case to produce a suggestion.
1828                     let mut err = self.emit_inference_failure_err(
1829                         body_id,
1830                         span,
1831                         self_ty.into(),
1832                         vec![],
1833                         ErrorCode::E0284,
1834                     );
1835                     err.note(&format!("cannot satisfy `{}`", predicate));
1836                     err
1837                 } else {
1838                     let mut err = struct_span_err!(
1839                         self.tcx.sess,
1840                         span,
1841                         E0284,
1842                         "type annotations needed: cannot satisfy `{}`",
1843                         predicate,
1844                     );
1845                     err.span_label(span, &format!("cannot satisfy `{}`", predicate));
1846                     err
1847                 }
1848             }
1849
1850             _ => {
1851                 if self.tcx.sess.has_errors() || self.is_tainted_by_errors() {
1852                     return;
1853                 }
1854                 let mut err = struct_span_err!(
1855                     self.tcx.sess,
1856                     span,
1857                     E0284,
1858                     "type annotations needed: cannot satisfy `{}`",
1859                     predicate,
1860                 );
1861                 err.span_label(span, &format!("cannot satisfy `{}`", predicate));
1862                 err
1863             }
1864         };
1865         self.note_obligation_cause(&mut err, obligation);
1866         err.emit();
1867     }
1868
1869     fn annotate_source_of_ambiguity(
1870         &self,
1871         err: &mut DiagnosticBuilder<'tcx>,
1872         impls: &[DefId],
1873         predicate: ty::Predicate<'tcx>,
1874     ) {
1875         let mut spans = vec![];
1876         let mut crates = vec![];
1877         let mut post = vec![];
1878         for def_id in impls {
1879             match self.tcx.span_of_impl(*def_id) {
1880                 Ok(span) => spans.push(self.tcx.sess.source_map().guess_head_span(span)),
1881                 Err(name) => {
1882                     crates.push(name);
1883                     if let Some(header) = to_pretty_impl_header(self.tcx, *def_id) {
1884                         post.push(header);
1885                     }
1886                 }
1887             }
1888         }
1889         let msg = format!("multiple `impl`s satisfying `{}` found", predicate);
1890         let mut crate_names: Vec<_> = crates.iter().map(|n| format!("`{}`", n)).collect();
1891         crate_names.sort();
1892         crate_names.dedup();
1893         post.sort();
1894         post.dedup();
1895
1896         if self.is_tainted_by_errors()
1897             && crate_names.len() == 1
1898             && crate_names[0] == "`core`"
1899             && spans.len() == 0
1900         {
1901             // Avoid complaining about other inference issues for expressions like
1902             // `42 >> 1`, where the types are still `{integer}`, but we want to
1903             // Do we need `trait_ref.skip_binder().self_ty().is_numeric() &&` too?
1904             err.cancel();
1905             return;
1906         }
1907         let post = if post.len() > 4 {
1908             format!(
1909                 ":\n{}\nand {} more",
1910                 post.iter().map(|p| format!("- {}", p)).take(4).collect::<Vec<_>>().join("\n"),
1911                 post.len() - 4,
1912             )
1913         } else if post.len() > 1 || (post.len() == 1 && post[0].contains('\n')) {
1914             format!(":\n{}", post.iter().map(|p| format!("- {}", p)).collect::<Vec<_>>().join("\n"),)
1915         } else if post.len() == 1 {
1916             format!(": `{}`", post[0])
1917         } else {
1918             String::new()
1919         };
1920
1921         match (spans.len(), crates.len(), crate_names.len()) {
1922             (0, 0, 0) => {
1923                 err.note(&format!("cannot satisfy `{}`", predicate));
1924             }
1925             (0, _, 1) => {
1926                 err.note(&format!("{} in the `{}` crate{}", msg, crates[0], post,));
1927             }
1928             (0, _, _) => {
1929                 err.note(&format!(
1930                     "{} in the following crates: {}{}",
1931                     msg,
1932                     crate_names.join(", "),
1933                     post,
1934                 ));
1935             }
1936             (_, 0, 0) => {
1937                 let span: MultiSpan = spans.into();
1938                 err.span_note(span, &msg);
1939             }
1940             (_, 1, 1) => {
1941                 let span: MultiSpan = spans.into();
1942                 err.span_note(span, &msg);
1943                 err.note(
1944                     &format!("and another `impl` found in the `{}` crate{}", crates[0], post,),
1945                 );
1946             }
1947             _ => {
1948                 let span: MultiSpan = spans.into();
1949                 err.span_note(span, &msg);
1950                 err.note(&format!(
1951                     "and more `impl`s found in the following crates: {}{}",
1952                     crate_names.join(", "),
1953                     post,
1954                 ));
1955             }
1956         }
1957     }
1958
1959     /// Returns `true` if the trait predicate may apply for *some* assignment
1960     /// to the type parameters.
1961     fn predicate_can_apply(
1962         &self,
1963         param_env: ty::ParamEnv<'tcx>,
1964         pred: ty::PolyTraitRef<'tcx>,
1965     ) -> bool {
1966         struct ParamToVarFolder<'a, 'tcx> {
1967             infcx: &'a InferCtxt<'a, 'tcx>,
1968             var_map: FxHashMap<Ty<'tcx>, Ty<'tcx>>,
1969         }
1970
1971         impl<'a, 'tcx> TypeFolder<'tcx> for ParamToVarFolder<'a, 'tcx> {
1972             fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
1973                 self.infcx.tcx
1974             }
1975
1976             fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
1977                 if let ty::Param(ty::ParamTy { name, .. }) = *ty.kind() {
1978                     let infcx = self.infcx;
1979                     self.var_map.entry(ty).or_insert_with(|| {
1980                         infcx.next_ty_var(TypeVariableOrigin {
1981                             kind: TypeVariableOriginKind::TypeParameterDefinition(name, None),
1982                             span: DUMMY_SP,
1983                         })
1984                     })
1985                 } else {
1986                     ty.super_fold_with(self)
1987                 }
1988             }
1989         }
1990
1991         self.probe(|_| {
1992             let mut selcx = SelectionContext::new(self);
1993
1994             let cleaned_pred =
1995                 pred.fold_with(&mut ParamToVarFolder { infcx: self, var_map: Default::default() });
1996
1997             let cleaned_pred = super::project::normalize(
1998                 &mut selcx,
1999                 param_env,
2000                 ObligationCause::dummy(),
2001                 cleaned_pred,
2002             )
2003             .value;
2004
2005             let obligation = Obligation::new(
2006                 ObligationCause::dummy(),
2007                 param_env,
2008                 cleaned_pred.without_const().to_predicate(selcx.tcx()),
2009             );
2010
2011             self.predicate_may_hold(&obligation)
2012         })
2013     }
2014
2015     fn note_obligation_cause(
2016         &self,
2017         err: &mut DiagnosticBuilder<'tcx>,
2018         obligation: &PredicateObligation<'tcx>,
2019     ) {
2020         // First, attempt to add note to this error with an async-await-specific
2021         // message, and fall back to regular note otherwise.
2022         if !self.maybe_note_obligation_cause_for_async_await(err, obligation) {
2023             self.note_obligation_cause_code(
2024                 err,
2025                 &obligation.predicate,
2026                 obligation.param_env,
2027                 obligation.cause.code(),
2028                 &mut vec![],
2029                 &mut Default::default(),
2030             );
2031             self.suggest_unsized_bound_if_applicable(err, obligation);
2032         }
2033     }
2034
2035     fn suggest_unsized_bound_if_applicable(
2036         &self,
2037         err: &mut DiagnosticBuilder<'tcx>,
2038         obligation: &PredicateObligation<'tcx>,
2039     ) {
2040         let (pred, item_def_id, span) = match (
2041             obligation.predicate.kind().skip_binder(),
2042             obligation.cause.code().peel_derives(),
2043         ) {
2044             (
2045                 ty::PredicateKind::Trait(pred),
2046                 &ObligationCauseCode::BindingObligation(item_def_id, span),
2047             ) => (pred, item_def_id, span),
2048             _ => return,
2049         };
2050         debug!(
2051             "suggest_unsized_bound_if_applicable: pred={:?} item_def_id={:?} span={:?}",
2052             pred, item_def_id, span
2053         );
2054         let node = match (
2055             self.tcx.hir().get_if_local(item_def_id),
2056             Some(pred.def_id()) == self.tcx.lang_items().sized_trait(),
2057         ) {
2058             (Some(node), true) => node,
2059             _ => return,
2060         };
2061         self.maybe_suggest_unsized_generics(err, span, node);
2062     }
2063
2064     fn maybe_suggest_unsized_generics<'hir>(
2065         &self,
2066         err: &mut DiagnosticBuilder<'tcx>,
2067         span: Span,
2068         node: Node<'hir>,
2069     ) {
2070         let generics = match node.generics() {
2071             Some(generics) => generics,
2072             None => return,
2073         };
2074         let sized_trait = self.tcx.lang_items().sized_trait();
2075         debug!("maybe_suggest_unsized_generics: generics.params={:?}", generics.params);
2076         debug!("maybe_suggest_unsized_generics: generics.where_clause={:?}", generics.where_clause);
2077         let param = generics.params.iter().filter(|param| param.span == span).find(|param| {
2078             // Check that none of the explicit trait bounds is `Sized`. Assume that an explicit
2079             // `Sized` bound is there intentionally and we don't need to suggest relaxing it.
2080             param
2081                 .bounds
2082                 .iter()
2083                 .all(|bound| bound.trait_ref().and_then(|tr| tr.trait_def_id()) != sized_trait)
2084         });
2085         let param = match param {
2086             Some(param) => param,
2087             _ => return,
2088         };
2089         let param_def_id = self.tcx.hir().local_def_id(param.hir_id).to_def_id();
2090         let preds = generics.where_clause.predicates.iter();
2091         let explicitly_sized = preds
2092             .filter_map(|pred| match pred {
2093                 hir::WherePredicate::BoundPredicate(bp) => Some(bp),
2094                 _ => None,
2095             })
2096             .filter(|bp| bp.is_param_bound(param_def_id))
2097             .flat_map(|bp| bp.bounds)
2098             .any(|bound| bound.trait_ref().and_then(|tr| tr.trait_def_id()) == sized_trait);
2099         if explicitly_sized {
2100             return;
2101         }
2102         debug!("maybe_suggest_unsized_generics: param={:?}", param);
2103         match node {
2104             hir::Node::Item(
2105                 item @ hir::Item {
2106                     // Only suggest indirection for uses of type parameters in ADTs.
2107                     kind:
2108                         hir::ItemKind::Enum(..) | hir::ItemKind::Struct(..) | hir::ItemKind::Union(..),
2109                     ..
2110                 },
2111             ) => {
2112                 if self.maybe_indirection_for_unsized(err, item, param) {
2113                     return;
2114                 }
2115             }
2116             _ => {}
2117         };
2118         // Didn't add an indirection suggestion, so add a general suggestion to relax `Sized`.
2119         let (span, separator) = match param.bounds {
2120             [] => (span.shrink_to_hi(), ":"),
2121             [.., bound] => (bound.span().shrink_to_hi(), " +"),
2122         };
2123         err.span_suggestion_verbose(
2124             span,
2125             "consider relaxing the implicit `Sized` restriction",
2126             format!("{} ?Sized", separator),
2127             Applicability::MachineApplicable,
2128         );
2129     }
2130
2131     fn maybe_indirection_for_unsized<'hir>(
2132         &self,
2133         err: &mut DiagnosticBuilder<'tcx>,
2134         item: &'hir Item<'hir>,
2135         param: &'hir GenericParam<'hir>,
2136     ) -> bool {
2137         // Suggesting `T: ?Sized` is only valid in an ADT if `T` is only used in a
2138         // borrow. `struct S<'a, T: ?Sized>(&'a T);` is valid, `struct S<T: ?Sized>(T);`
2139         // is not. Look for invalid "bare" parameter uses, and suggest using indirection.
2140         let mut visitor =
2141             FindTypeParam { param: param.name.ident().name, invalid_spans: vec![], nested: false };
2142         visitor.visit_item(item);
2143         if visitor.invalid_spans.is_empty() {
2144             return false;
2145         }
2146         let mut multispan: MultiSpan = param.span.into();
2147         multispan.push_span_label(
2148             param.span,
2149             format!("this could be changed to `{}: ?Sized`...", param.name.ident()),
2150         );
2151         for sp in visitor.invalid_spans {
2152             multispan.push_span_label(
2153                 sp,
2154                 format!("...if indirection were used here: `Box<{}>`", param.name.ident()),
2155             );
2156         }
2157         err.span_help(
2158             multispan,
2159             &format!(
2160                 "you could relax the implicit `Sized` bound on `{T}` if it were \
2161                 used through indirection like `&{T}` or `Box<{T}>`",
2162                 T = param.name.ident(),
2163             ),
2164         );
2165         true
2166     }
2167
2168     fn is_recursive_obligation(
2169         &self,
2170         obligated_types: &mut Vec<&ty::TyS<'tcx>>,
2171         cause_code: &ObligationCauseCode<'tcx>,
2172     ) -> bool {
2173         if let ObligationCauseCode::BuiltinDerivedObligation(ref data) = cause_code {
2174             let parent_trait_ref = self.resolve_vars_if_possible(data.parent_trait_pred);
2175             let self_ty = parent_trait_ref.skip_binder().self_ty();
2176             if obligated_types.iter().any(|ot| ot == &self_ty) {
2177                 return true;
2178             }
2179             if let ty::Adt(def, substs) = self_ty.kind() {
2180                 if let [arg] = &substs[..] {
2181                     if let ty::subst::GenericArgKind::Type(ty) = arg.unpack() {
2182                         if let ty::Adt(inner_def, _) = ty.kind() {
2183                             if inner_def == def {
2184                                 return true;
2185                             }
2186                         }
2187                     }
2188                 }
2189             }
2190         }
2191         false
2192     }
2193 }
2194
2195 /// Look for type `param` in an ADT being used only through a reference to confirm that suggesting
2196 /// `param: ?Sized` would be a valid constraint.
2197 struct FindTypeParam {
2198     param: rustc_span::Symbol,
2199     invalid_spans: Vec<Span>,
2200     nested: bool,
2201 }
2202
2203 impl<'v> Visitor<'v> for FindTypeParam {
2204     fn visit_where_predicate(&mut self, _: &'v hir::WherePredicate<'v>) {
2205         // Skip where-clauses, to avoid suggesting indirection for type parameters found there.
2206     }
2207
2208     fn visit_ty(&mut self, ty: &hir::Ty<'_>) {
2209         // We collect the spans of all uses of the "bare" type param, like in `field: T` or
2210         // `field: (T, T)` where we could make `T: ?Sized` while skipping cases that are known to be
2211         // valid like `field: &'a T` or `field: *mut T` and cases that *might* have further `Sized`
2212         // obligations like `Box<T>` and `Vec<T>`, but we perform no extra analysis for those cases
2213         // and suggest `T: ?Sized` regardless of their obligations. This is fine because the errors
2214         // in that case should make what happened clear enough.
2215         match ty.kind {
2216             hir::TyKind::Ptr(_) | hir::TyKind::Rptr(..) | hir::TyKind::TraitObject(..) => {}
2217             hir::TyKind::Path(hir::QPath::Resolved(None, path))
2218                 if path.segments.len() == 1 && path.segments[0].ident.name == self.param =>
2219             {
2220                 if !self.nested {
2221                     debug!("FindTypeParam::visit_ty: ty={:?}", ty);
2222                     self.invalid_spans.push(ty.span);
2223                 }
2224             }
2225             hir::TyKind::Path(_) => {
2226                 let prev = self.nested;
2227                 self.nested = true;
2228                 hir::intravisit::walk_ty(self, ty);
2229                 self.nested = prev;
2230             }
2231             _ => {
2232                 hir::intravisit::walk_ty(self, ty);
2233             }
2234         }
2235     }
2236 }
2237
2238 pub fn recursive_type_with_infinite_size_error(
2239     tcx: TyCtxt<'_>,
2240     type_def_id: DefId,
2241     spans: Vec<Span>,
2242 ) {
2243     assert!(type_def_id.is_local());
2244     let span = tcx.hir().span_if_local(type_def_id).unwrap();
2245     let span = tcx.sess.source_map().guess_head_span(span);
2246     let path = tcx.def_path_str(type_def_id);
2247     let mut err =
2248         struct_span_err!(tcx.sess, span, E0072, "recursive type `{}` has infinite size", path);
2249     err.span_label(span, "recursive type has infinite size");
2250     for &span in &spans {
2251         err.span_label(span, "recursive without indirection");
2252     }
2253     let msg = format!(
2254         "insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `{}` representable",
2255         path,
2256     );
2257     if spans.len() <= 4 {
2258         err.multipart_suggestion(
2259             &msg,
2260             spans
2261                 .iter()
2262                 .flat_map(|&span| {
2263                     [
2264                         (span.shrink_to_lo(), "Box<".to_string()),
2265                         (span.shrink_to_hi(), ">".to_string()),
2266                     ]
2267                     .into_iter()
2268                 })
2269                 .collect(),
2270             Applicability::HasPlaceholders,
2271         );
2272     } else {
2273         err.help(&msg);
2274     }
2275     err.emit();
2276 }
2277
2278 /// Summarizes information
2279 #[derive(Clone)]
2280 pub enum ArgKind {
2281     /// An argument of non-tuple type. Parameters are (name, ty)
2282     Arg(String, String),
2283
2284     /// An argument of tuple type. For a "found" argument, the span is
2285     /// the location in the source of the pattern. For an "expected"
2286     /// argument, it will be None. The vector is a list of (name, ty)
2287     /// strings for the components of the tuple.
2288     Tuple(Option<Span>, Vec<(String, String)>),
2289 }
2290
2291 impl ArgKind {
2292     fn empty() -> ArgKind {
2293         ArgKind::Arg("_".to_owned(), "_".to_owned())
2294     }
2295
2296     /// Creates an `ArgKind` from the expected type of an
2297     /// argument. It has no name (`_`) and an optional source span.
2298     pub fn from_expected_ty(t: Ty<'_>, span: Option<Span>) -> ArgKind {
2299         match t.kind() {
2300             ty::Tuple(tys) => ArgKind::Tuple(
2301                 span,
2302                 tys.iter().map(|ty| ("_".to_owned(), ty.to_string())).collect::<Vec<_>>(),
2303             ),
2304             _ => ArgKind::Arg("_".to_owned(), t.to_string()),
2305         }
2306     }
2307 }