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