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

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