src/librustc_infer/infer/error_reporting/mod.rs

   1 //! Error Reporting Code for the inference engine
   2 //!
   3 //! Because of the way inference, and in particular region inference,
   4 //! works, it often happens that errors are not detected until far after
   5 //! the relevant line of code has been type-checked. Therefore, there is
   6 //! an elaborate system to track why a particular constraint in the
   7 //! inference graph arose so that we can explain to the user what gave
   8 //! rise to a particular error.
   9 //!
  10 //! The basis of the system are the "origin" types. An "origin" is the
  11 //! reason that a constraint or inference variable arose. There are
  12 //! different "origin" enums for different kinds of constraints/variables
  13 //! (e.g., `TypeOrigin`, `RegionVariableOrigin`). An origin always has
  14 //! a span, but also more information so that we can generate a meaningful
  15 //! error message.
  16 //!
  17 //! Having a catalog of all the different reasons an error can arise is
  18 //! also useful for other reasons, like cross-referencing FAQs etc, though
  19 //! we are not really taking advantage of this yet.
  20 //!
  21 //! # Region Inference
  22 //!
  23 //! Region inference is particularly tricky because it always succeeds "in
  24 //! the moment" and simply registers a constraint. Then, at the end, we
  25 //! can compute the full graph and report errors, so we need to be able to
  26 //! store and later report what gave rise to the conflicting constraints.
  27 //!
  28 //! # Subtype Trace
  29 //!
  30 //! Determining whether `T1 <: T2` often involves a number of subtypes and
  31 //! subconstraints along the way. A "TypeTrace" is an extended version
  32 //! of an origin that traces the types and other values that were being
  33 //! compared. It is not necessarily comprehensive (in fact, at the time of
  34 //! this writing it only tracks the root values being compared) but I'd
  35 //! like to extend it to include significant "waypoints". For example, if
  36 //! you are comparing `(T1, T2) <: (T3, T4)`, and the problem is that `T2
  37 //! <: T4` fails, I'd like the trace to include enough information to say
  38 //! "in the 2nd element of the tuple". Similarly, failures when comparing
  39 //! arguments or return types in fn types should be able to cite the
  40 //! specific position, etc.
  41 //!
  42 //! # Reality vs plan
  43 //!
  44 //! Of course, there is still a LOT of code in typeck that has yet to be
  45 //! ported to this system, and which relies on string concatenation at the
  46 //! time of error detection.
  47
  48 use super::lexical_region_resolve::RegionResolutionError;
  49 use super::region_constraints::GenericKind;
  50 use super::{InferCtxt, RegionVariableOrigin, SubregionOrigin, TypeTrace, ValuePairs};
  51
  52 use crate::infer;
  53 use crate::traits::error_reporting::report_object_safety_error;
  54 use crate::traits::{
  55     IfExpressionCause, MatchExpressionArmCause, ObligationCause, ObligationCauseCode,
  56 };
  57
  58 use rustc::hir::map;
  59 use rustc::middle::region;
  60 use rustc::ty::error::TypeError;
  61 use rustc::ty::{
  62     self,
  63     subst::{Subst, SubstsRef},
  64     Region, Ty, TyCtxt, TypeFoldable,
  65 };
  66 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
  67 use rustc_errors::{pluralize, struct_span_err};
  68 use rustc_errors::{Applicability, DiagnosticBuilder, DiagnosticStyledString};
  69 use rustc_hir as hir;
  70 use rustc_hir::def_id::DefId;
  71 use rustc_hir::Node;
  72 use rustc_span::{DesugaringKind, Pos, Span};
  73 use rustc_target::spec::abi;
  74 use std::{cmp, fmt};
  75
  76 mod note;
  77
  78 mod need_type_info;
  79 pub use need_type_info::TypeAnnotationNeeded;
  80
  81 pub mod nice_region_error;
  82
  83 pub(super) fn note_and_explain_region(
  84     tcx: TyCtxt<'tcx>,
  85     region_scope_tree: &region::ScopeTree,
  86     err: &mut DiagnosticBuilder<'_>,
  87     prefix: &str,
  88     region: ty::Region<'tcx>,
  89     suffix: &str,
  90 ) {
  91     let (description, span) = match *region {
  92         ty::ReScope(scope) => {
  93             let new_string;
  94             let unknown_scope =
  95                 || format!("{}unknown scope: {:?}{}.  Please report a bug.", prefix, scope, suffix);
  96             let span = scope.span(tcx, region_scope_tree);
  97             let tag = match tcx.hir().find(scope.hir_id(region_scope_tree)) {
  98                 Some(Node::Block(_)) => "block",
  99                 Some(Node::Expr(expr)) => match expr.kind {
 100                     hir::ExprKind::Call(..) => "call",
 101                     hir::ExprKind::MethodCall(..) => "method call",
 102                     hir::ExprKind::Match(.., hir::MatchSource::IfLetDesugar { .. }) => "if let",
 103                     hir::ExprKind::Match(.., hir::MatchSource::WhileLetDesugar) => "while let",
 104                     hir::ExprKind::Match(.., hir::MatchSource::ForLoopDesugar) => "for",
 105                     hir::ExprKind::Match(..) => "match",
 106                     _ => "expression",
 107                 },
 108                 Some(Node::Stmt(_)) => "statement",
 109                 Some(Node::Item(it)) => item_scope_tag(&it),
 110                 Some(Node::TraitItem(it)) => trait_item_scope_tag(&it),
 111                 Some(Node::ImplItem(it)) => impl_item_scope_tag(&it),
 112                 Some(_) | None => {
 113                     err.span_note(span, &unknown_scope());
 114                     return;
 115                 }
 116             };
 117             let scope_decorated_tag = match scope.data {
 118                 region::ScopeData::Node => tag,
 119                 region::ScopeData::CallSite => "scope of call-site for function",
 120                 region::ScopeData::Arguments => "scope of function body",
 121                 region::ScopeData::Destruction => {
 122                     new_string = format!("destruction scope surrounding {}", tag);
 123                     &new_string[..]
 124                 }
 125                 region::ScopeData::Remainder(first_statement_index) => {
 126                     new_string = format!(
 127                         "block suffix following statement {}",
 128                         first_statement_index.index()
 129                     );
 130                     &new_string[..]
 131                 }
 132             };
 133             explain_span(tcx, scope_decorated_tag, span)
 134         }
 135
 136         ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReStatic => {
 137             msg_span_from_free_region(tcx, region)
 138         }
 139
 140         ty::ReEmpty(ty::UniverseIndex::ROOT) => ("the empty lifetime".to_owned(), None),
 141
 142         // uh oh, hope no user ever sees THIS
 143         ty::ReEmpty(ui) => (format!("the empty lifetime in universe {:?}", ui), None),
 144
 145         ty::RePlaceholder(_) => ("any other region".to_string(), None),
 146
 147         // FIXME(#13998) RePlaceholder should probably print like
 148         // ReFree rather than dumping Debug output on the user.
 149         //
 150         // We shouldn't really be having unification failures with ReVar
 151         // and ReLateBound though.
 152         ty::ReVar(_) | ty::ReLateBound(..) | ty::ReErased => {
 153             (format!("lifetime {:?}", region), None)
 154         }
 155
 156         // We shouldn't encounter an error message with ReClosureBound.
 157         ty::ReClosureBound(..) => {
 158             bug!("encountered unexpected ReClosureBound: {:?}", region,);
 159         }
 160     };
 161
 162     emit_msg_span(err, prefix, description, span, suffix);
 163 }
 164
 165 pub(super) fn note_and_explain_free_region(
 166     tcx: TyCtxt<'tcx>,
 167     err: &mut DiagnosticBuilder<'_>,
 168     prefix: &str,
 169     region: ty::Region<'tcx>,
 170     suffix: &str,
 171 ) {
 172     let (description, span) = msg_span_from_free_region(tcx, region);
 173
 174     emit_msg_span(err, prefix, description, span, suffix);
 175 }
 176
 177 fn msg_span_from_free_region(
 178     tcx: TyCtxt<'tcx>,
 179     region: ty::Region<'tcx>,
 180 ) -> (String, Option<Span>) {
 181     match *region {
 182         ty::ReEarlyBound(_) | ty::ReFree(_) => {
 183             msg_span_from_early_bound_and_free_regions(tcx, region)
 184         }
 185         ty::ReStatic => ("the static lifetime".to_owned(), None),
 186         ty::ReEmpty(ty::UniverseIndex::ROOT) => ("an empty lifetime".to_owned(), None),
 187         ty::ReEmpty(ui) => (format!("an empty lifetime in universe {:?}", ui), None),
 188         _ => bug!("{:?}", region),
 189     }
 190 }
 191
 192 fn msg_span_from_early_bound_and_free_regions(
 193     tcx: TyCtxt<'tcx>,
 194     region: ty::Region<'tcx>,
 195 ) -> (String, Option<Span>) {
 196     let sm = tcx.sess.source_map();
 197
 198     let scope = region.free_region_binding_scope(tcx);
 199     let node = tcx.hir().as_local_hir_id(scope).unwrap_or(hir::DUMMY_HIR_ID);
 200     let tag = match tcx.hir().find(node) {
 201         Some(Node::Block(_)) | Some(Node::Expr(_)) => "body",
 202         Some(Node::Item(it)) => item_scope_tag(&it),
 203         Some(Node::TraitItem(it)) => trait_item_scope_tag(&it),
 204         Some(Node::ImplItem(it)) => impl_item_scope_tag(&it),
 205         _ => unreachable!(),
 206     };
 207     let (prefix, span) = match *region {
 208         ty::ReEarlyBound(ref br) => {
 209             let mut sp = sm.def_span(tcx.hir().span(node));
 210             if let Some(param) =
 211                 tcx.hir().get_generics(scope).and_then(|generics| generics.get_named(br.name))
 212             {
 213                 sp = param.span;
 214             }
 215             (format!("the lifetime `{}` as defined on", br.name), sp)
 216         }
 217         ty::ReFree(ty::FreeRegion { bound_region: ty::BoundRegion::BrNamed(_, name), .. }) => {
 218             let mut sp = sm.def_span(tcx.hir().span(node));
 219             if let Some(param) =
 220                 tcx.hir().get_generics(scope).and_then(|generics| generics.get_named(name))
 221             {
 222                 sp = param.span;
 223             }
 224             (format!("the lifetime `{}` as defined on", name), sp)
 225         }
 226         ty::ReFree(ref fr) => match fr.bound_region {
 227             ty::BrAnon(idx) => {
 228                 (format!("the anonymous lifetime #{} defined on", idx + 1), tcx.hir().span(node))
 229             }
 230             _ => (
 231                 format!("the lifetime `{}` as defined on", region),
 232                 sm.def_span(tcx.hir().span(node)),
 233             ),
 234         },
 235         _ => bug!(),
 236     };
 237     let (msg, opt_span) = explain_span(tcx, tag, span);
 238     (format!("{} {}", prefix, msg), opt_span)
 239 }
 240
 241 fn emit_msg_span(
 242     err: &mut DiagnosticBuilder<'_>,
 243     prefix: &str,
 244     description: String,
 245     span: Option<Span>,
 246     suffix: &str,
 247 ) {
 248     let message = format!("{}{}{}", prefix, description, suffix);
 249
 250     if let Some(span) = span {
 251         err.span_note(span, &message);
 252     } else {
 253         err.note(&message);
 254     }
 255 }
 256
 257 fn item_scope_tag(item: &hir::Item<'_>) -> &'static str {
 258     match item.kind {
 259         hir::ItemKind::Impl { .. } => "impl",
 260         hir::ItemKind::Struct(..) => "struct",
 261         hir::ItemKind::Union(..) => "union",
 262         hir::ItemKind::Enum(..) => "enum",
 263         hir::ItemKind::Trait(..) => "trait",
 264         hir::ItemKind::Fn(..) => "function body",
 265         _ => "item",
 266     }
 267 }
 268
 269 fn trait_item_scope_tag(item: &hir::TraitItem<'_>) -> &'static str {
 270     match item.kind {
 271         hir::TraitItemKind::Fn(..) => "method body",
 272         hir::TraitItemKind::Const(..) | hir::TraitItemKind::Type(..) => "associated item",
 273     }
 274 }
 275
 276 fn impl_item_scope_tag(item: &hir::ImplItem<'_>) -> &'static str {
 277     match item.kind {
 278         hir::ImplItemKind::Fn(..) => "method body",
 279         hir::ImplItemKind::Const(..)
 280         | hir::ImplItemKind::OpaqueTy(..)
 281         | hir::ImplItemKind::TyAlias(..) => "associated item",
 282     }
 283 }
 284
 285 fn explain_span(tcx: TyCtxt<'tcx>, heading: &str, span: Span) -> (String, Option<Span>) {
 286     let lo = tcx.sess.source_map().lookup_char_pos(span.lo());
 287     (format!("the {} at {}:{}", heading, lo.line, lo.col.to_usize() + 1), Some(span))
 288 }
 289
 290 pub fn unexpected_hidden_region_diagnostic(
 291     tcx: TyCtxt<'tcx>,
 292     region_scope_tree: Option<&region::ScopeTree>,
 293     span: Span,
 294     hidden_ty: Ty<'tcx>,
 295     hidden_region: ty::Region<'tcx>,
 296 ) -> DiagnosticBuilder<'tcx> {
 297     let mut err = struct_span_err!(
 298         tcx.sess,
 299         span,
 300         E0700,
 301         "hidden type for `impl Trait` captures lifetime that does not appear in bounds",
 302     );
 303
 304     // Explain the region we are capturing.
 305     if let ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReStatic | ty::ReEmpty(_) = hidden_region {
 306         // Assuming regionck succeeded (*), we ought to always be
 307         // capturing *some* region from the fn header, and hence it
 308         // ought to be free. So under normal circumstances, we will go
 309         // down this path which gives a decent human readable
 310         // explanation.
 311         //
 312         // (*) if not, the `tainted_by_errors` flag would be set to
 313         // true in any case, so we wouldn't be here at all.
 314         note_and_explain_free_region(
 315             tcx,
 316             &mut err,
 317             &format!("hidden type `{}` captures ", hidden_ty),
 318             hidden_region,
 319             "",
 320         );
 321     } else {
 322         // Ugh. This is a painful case: the hidden region is not one
 323         // that we can easily summarize or explain. This can happen
 324         // in a case like
 325         // `src/test/ui/multiple-lifetimes/ordinary-bounds-unsuited.rs`:
 326         //
 327         // ```
 328         // fn upper_bounds<'a, 'b>(a: Ordinary<'a>, b: Ordinary<'b>) -> impl Trait<'a, 'b> {
 329         //   if condition() { a } else { b }
 330         // }
 331         // ```
 332         //
 333         // Here the captured lifetime is the intersection of `'a` and
 334         // `'b`, which we can't quite express.
 335
 336         if let Some(region_scope_tree) = region_scope_tree {
 337             // If the `region_scope_tree` is available, this is being
 338             // invoked from the "region inferencer error". We can at
 339             // least report a really cryptic error for now.
 340             note_and_explain_region(
 341                 tcx,
 342                 region_scope_tree,
 343                 &mut err,
 344                 &format!("hidden type `{}` captures ", hidden_ty),
 345                 hidden_region,
 346                 "",
 347             );
 348         } else {
 349             // If the `region_scope_tree` is *unavailable*, this is
 350             // being invoked by the code that comes *after* region
 351             // inferencing. This is a bug, as the region inferencer
 352             // ought to have noticed the failed constraint and invoked
 353             // error reporting, which in turn should have prevented us
 354             // from getting trying to infer the hidden type
 355             // completely.
 356             tcx.sess.delay_span_bug(
 357                 span,
 358                 &format!(
 359                     "hidden type captures unexpected lifetime `{:?}` \
 360                      but no region inference failure",
 361                     hidden_region,
 362                 ),
 363             );
 364         }
 365     }
 366
 367     err
 368 }
 369
 370 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
 371     pub fn report_region_errors(
 372         &self,
 373         region_scope_tree: &region::ScopeTree,
 374         errors: &Vec<RegionResolutionError<'tcx>>,
 375     ) {
 376         debug!("report_region_errors(): {} errors to start", errors.len());
 377
 378         // try to pre-process the errors, which will group some of them
 379         // together into a `ProcessedErrors` group:
 380         let errors = self.process_errors(errors);
 381
 382         debug!("report_region_errors: {} errors after preprocessing", errors.len());
 383
 384         for error in errors {
 385             debug!("report_region_errors: error = {:?}", error);
 386
 387             if !self.try_report_nice_region_error(&error) {
 388                 match error.clone() {
 389                     // These errors could indicate all manner of different
 390                     // problems with many different solutions. Rather
 391                     // than generate a "one size fits all" error, what we
 392                     // attempt to do is go through a number of specific
 393                     // scenarios and try to find the best way to present
 394                     // the error. If all of these fails, we fall back to a rather
 395                     // general bit of code that displays the error information
 396                     RegionResolutionError::ConcreteFailure(origin, sub, sup) => {
 397                         if sub.is_placeholder() || sup.is_placeholder() {
 398                             self.report_placeholder_failure(region_scope_tree, origin, sub, sup)
 399                                 .emit();
 400                         } else {
 401                             self.report_concrete_failure(region_scope_tree, origin, sub, sup)
 402                                 .emit();
 403                         }
 404                     }
 405
 406                     RegionResolutionError::GenericBoundFailure(origin, param_ty, sub) => {
 407                         self.report_generic_bound_failure(
 408                             region_scope_tree,
 409                             origin.span(),
 410                             Some(origin),
 411                             param_ty,
 412                             sub,
 413                         );
 414                     }
 415
 416                     RegionResolutionError::SubSupConflict(
 417                         _,
 418                         var_origin,
 419                         sub_origin,
 420                         sub_r,
 421                         sup_origin,
 422                         sup_r,
 423                     ) => {
 424                         if sub_r.is_placeholder() {
 425                             self.report_placeholder_failure(
 426                                 region_scope_tree,
 427                                 sub_origin,
 428                                 sub_r,
 429                                 sup_r,
 430                             )
 431                             .emit();
 432                         } else if sup_r.is_placeholder() {
 433                             self.report_placeholder_failure(
 434                                 region_scope_tree,
 435                                 sup_origin,
 436                                 sub_r,
 437                                 sup_r,
 438                             )
 439                             .emit();
 440                         } else {
 441                             self.report_sub_sup_conflict(
 442                                 region_scope_tree,
 443                                 var_origin,
 444                                 sub_origin,
 445                                 sub_r,
 446                                 sup_origin,
 447                                 sup_r,
 448                             );
 449                         }
 450                     }
 451
 452                     RegionResolutionError::UpperBoundUniverseConflict(
 453                         _,
 454                         _,
 455                         var_universe,
 456                         sup_origin,
 457                         sup_r,
 458                     ) => {
 459                         assert!(sup_r.is_placeholder());
 460
 461                         // Make a dummy value for the "sub region" --
 462                         // this is the initial value of the
 463                         // placeholder. In practice, we expect more
 464                         // tailored errors that don't really use this
 465                         // value.
 466                         let sub_r = self.tcx.mk_region(ty::ReEmpty(var_universe));
 467
 468                         self.report_placeholder_failure(
 469                             region_scope_tree,
 470                             sup_origin,
 471                             sub_r,
 472                             sup_r,
 473                         )
 474                         .emit();
 475                     }
 476
 477                     RegionResolutionError::MemberConstraintFailure {
 478                         hidden_ty,
 479                         member_region,
 480                         span,
 481                     } => {
 482                         let hidden_ty = self.resolve_vars_if_possible(&hidden_ty);
 483                         unexpected_hidden_region_diagnostic(
 484                             self.tcx,
 485                             Some(region_scope_tree),
 486                             span,
 487                             hidden_ty,
 488                             member_region,
 489                         )
 490                         .emit();
 491                     }
 492                 }
 493             }
 494         }
 495     }
 496
 497     // This method goes through all the errors and try to group certain types
 498     // of error together, for the purpose of suggesting explicit lifetime
 499     // parameters to the user. This is done so that we can have a more
 500     // complete view of what lifetimes should be the same.
 501     // If the return value is an empty vector, it means that processing
 502     // failed (so the return value of this method should not be used).
 503     //
 504     // The method also attempts to weed out messages that seem like
 505     // duplicates that will be unhelpful to the end-user. But
 506     // obviously it never weeds out ALL errors.
 507     fn process_errors(
 508         &self,
 509         errors: &Vec<RegionResolutionError<'tcx>>,
 510     ) -> Vec<RegionResolutionError<'tcx>> {
 511         debug!("process_errors()");
 512
 513         // We want to avoid reporting generic-bound failures if we can
 514         // avoid it: these have a very high rate of being unhelpful in
 515         // practice. This is because they are basically secondary
 516         // checks that test the state of the region graph after the
 517         // rest of inference is done, and the other kinds of errors
 518         // indicate that the region constraint graph is internally
 519         // inconsistent, so these test results are likely to be
 520         // meaningless.
 521         //
 522         // Therefore, we filter them out of the list unless they are
 523         // the only thing in the list.
 524
 525         let is_bound_failure = |e: &RegionResolutionError<'tcx>| match *e {
 526             RegionResolutionError::GenericBoundFailure(..) => true,
 527             RegionResolutionError::ConcreteFailure(..)
 528             | RegionResolutionError::SubSupConflict(..)
 529             | RegionResolutionError::UpperBoundUniverseConflict(..)
 530             | RegionResolutionError::MemberConstraintFailure { .. } => false,
 531         };
 532
 533         let mut errors = if errors.iter().all(|e| is_bound_failure(e)) {
 534             errors.clone()
 535         } else {
 536             errors.iter().filter(|&e| !is_bound_failure(e)).cloned().collect()
 537         };
 538
 539         // sort the errors by span, for better error message stability.
 540         errors.sort_by_key(|u| match *u {
 541             RegionResolutionError::ConcreteFailure(ref sro, _, _) => sro.span(),
 542             RegionResolutionError::GenericBoundFailure(ref sro, _, _) => sro.span(),
 543             RegionResolutionError::SubSupConflict(_, ref rvo, _, _, _, _) => rvo.span(),
 544             RegionResolutionError::UpperBoundUniverseConflict(_, ref rvo, _, _, _) => rvo.span(),
 545             RegionResolutionError::MemberConstraintFailure { span, .. } => span,
 546         });
 547         errors
 548     }
 549
 550     /// Adds a note if the types come from similarly named crates
 551     fn check_and_note_conflicting_crates(
 552         &self,
 553         err: &mut DiagnosticBuilder<'_>,
 554         terr: &TypeError<'tcx>,
 555     ) {
 556         use hir::def_id::CrateNum;
 557         use map::DisambiguatedDefPathData;
 558         use ty::print::Printer;
 559         use ty::subst::GenericArg;
 560
 561         struct AbsolutePathPrinter<'tcx> {
 562             tcx: TyCtxt<'tcx>,
 563         }
 564
 565         struct NonTrivialPath;
 566
 567         impl<'tcx> Printer<'tcx> for AbsolutePathPrinter<'tcx> {
 568             type Error = NonTrivialPath;
 569
 570             type Path = Vec<String>;
 571             type Region = !;
 572             type Type = !;
 573             type DynExistential = !;
 574             type Const = !;
 575
 576             fn tcx<'a>(&'a self) -> TyCtxt<'tcx> {
 577                 self.tcx
 578             }
 579
 580             fn print_region(self, _region: ty::Region<'_>) -> Result<Self::Region, Self::Error> {
 581                 Err(NonTrivialPath)
 582             }
 583
 584             fn print_type(self, _ty: Ty<'tcx>) -> Result<Self::Type, Self::Error> {
 585                 Err(NonTrivialPath)
 586             }
 587
 588             fn print_dyn_existential(
 589                 self,
 590                 _predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
 591             ) -> Result<Self::DynExistential, Self::Error> {
 592                 Err(NonTrivialPath)
 593             }
 594
 595             fn print_const(self, _ct: &'tcx ty::Const<'tcx>) -> Result<Self::Const, Self::Error> {
 596                 Err(NonTrivialPath)
 597             }
 598
 599             fn path_crate(self, cnum: CrateNum) -> Result<Self::Path, Self::Error> {
 600                 Ok(vec![self.tcx.original_crate_name(cnum).to_string()])
 601             }
 602             fn path_qualified(
 603                 self,
 604                 _self_ty: Ty<'tcx>,
 605                 _trait_ref: Option<ty::TraitRef<'tcx>>,
 606             ) -> Result<Self::Path, Self::Error> {
 607                 Err(NonTrivialPath)
 608             }
 609
 610             fn path_append_impl(
 611                 self,
 612                 _print_prefix: impl FnOnce(Self) -> Result<Self::Path, Self::Error>,
 613                 _disambiguated_data: &DisambiguatedDefPathData,
 614                 _self_ty: Ty<'tcx>,
 615                 _trait_ref: Option<ty::TraitRef<'tcx>>,
 616             ) -> Result<Self::Path, Self::Error> {
 617                 Err(NonTrivialPath)
 618             }
 619             fn path_append(
 620                 self,
 621                 print_prefix: impl FnOnce(Self) -> Result<Self::Path, Self::Error>,
 622                 disambiguated_data: &DisambiguatedDefPathData,
 623             ) -> Result<Self::Path, Self::Error> {
 624                 let mut path = print_prefix(self)?;
 625                 path.push(disambiguated_data.data.as_symbol().to_string());
 626                 Ok(path)
 627             }
 628             fn path_generic_args(
 629                 self,
 630                 print_prefix: impl FnOnce(Self) -> Result<Self::Path, Self::Error>,
 631                 _args: &[GenericArg<'tcx>],
 632             ) -> Result<Self::Path, Self::Error> {
 633                 print_prefix(self)
 634             }
 635         }
 636
 637         let report_path_match = |err: &mut DiagnosticBuilder<'_>, did1: DefId, did2: DefId| {
 638             // Only external crates, if either is from a local
 639             // module we could have false positives
 640             if !(did1.is_local() || did2.is_local()) && did1.krate != did2.krate {
 641                 let abs_path =
 642                     |def_id| AbsolutePathPrinter { tcx: self.tcx }.print_def_path(def_id, &[]);
 643
 644                 // We compare strings because DefPath can be different
 645                 // for imported and non-imported crates
 646                 let same_path = || -> Result<_, NonTrivialPath> {
 647                     Ok(self.tcx.def_path_str(did1) == self.tcx.def_path_str(did2)
 648                         || abs_path(did1)? == abs_path(did2)?)
 649                 };
 650                 if same_path().unwrap_or(false) {
 651                     let crate_name = self.tcx.crate_name(did1.krate);
 652                     err.note(&format!(
 653                         "perhaps two different versions of crate `{}` are being used?",
 654                         crate_name
 655                     ));
 656                 }
 657             }
 658         };
 659         match *terr {
 660             TypeError::Sorts(ref exp_found) => {
 661                 // if they are both "path types", there's a chance of ambiguity
 662                 // due to different versions of the same crate
 663                 if let (&ty::Adt(exp_adt, _), &ty::Adt(found_adt, _)) =
 664                     (&exp_found.expected.kind, &exp_found.found.kind)
 665                 {
 666                     report_path_match(err, exp_adt.did, found_adt.did);
 667                 }
 668             }
 669             TypeError::Traits(ref exp_found) => {
 670                 report_path_match(err, exp_found.expected, exp_found.found);
 671             }
 672             _ => (), // FIXME(#22750) handle traits and stuff
 673         }
 674     }
 675
 676     fn note_error_origin(
 677         &self,
 678         err: &mut DiagnosticBuilder<'tcx>,
 679         cause: &ObligationCause<'tcx>,
 680         exp_found: Option<ty::error::ExpectedFound<Ty<'tcx>>>,
 681     ) {
 682         match cause.code {
 683             ObligationCauseCode::Pattern { origin_expr: true, span: Some(span), root_ty } => {
 684                 let ty = self.resolve_vars_if_possible(&root_ty);
 685                 if ty.is_suggestable() {
 686                     // don't show type `_`
 687                     err.span_label(span, format!("this expression has type `{}`", ty));
 688                 }
 689                 if let Some(ty::error::ExpectedFound { found, .. }) = exp_found {
 690                     if ty.is_box() && ty.boxed_ty() == found {
 691                         if let Ok(snippet) = self.tcx.sess.source_map().span_to_snippet(span) {
 692                             err.span_suggestion(
 693                                 span,
 694                                 "consider dereferencing the boxed value",
 695                                 format!("*{}", snippet),
 696                                 Applicability::MachineApplicable,
 697                             );
 698                         }
 699                     }
 700                 }
 701             }
 702             ObligationCauseCode::Pattern { origin_expr: false, span: Some(span), .. } => {
 703                 err.span_label(span, "expected due to this");
 704             }
 705             ObligationCauseCode::MatchExpressionArm(box MatchExpressionArmCause {
 706                 source,
 707                 ref prior_arms,
 708                 last_ty,
 709                 scrut_hir_id,
 710                 ..
 711             }) => match source {
 712                 hir::MatchSource::IfLetDesugar { .. } => {
 713                     let msg = "`if let` arms have incompatible types";
 714                     err.span_label(cause.span, msg);
 715                 }
 716                 hir::MatchSource::TryDesugar => {
 717                     if let Some(ty::error::ExpectedFound { expected, .. }) = exp_found {
 718                         let scrut_expr = self.tcx.hir().expect_expr(scrut_hir_id);
 719                         let scrut_ty = if let hir::ExprKind::Call(_, args) = &scrut_expr.kind {
 720                             let arg_expr = args.first().expect("try desugaring call w/out arg");
 721                             self.in_progress_tables
 722                                 .and_then(|tables| tables.borrow().expr_ty_opt(arg_expr))
 723                         } else {
 724                             bug!("try desugaring w/out call expr as scrutinee");
 725                         };
 726
 727                         match scrut_ty {
 728                             Some(ty) if expected == ty => {
 729                                 let source_map = self.tcx.sess.source_map();
 730                                 err.span_suggestion(
 731                                     source_map.end_point(cause.span),
 732                                     "try removing this `?`",
 733                                     "".to_string(),
 734                                     Applicability::MachineApplicable,
 735                                 );
 736                             }
 737                             _ => {}
 738                         }
 739                     }
 740                 }
 741                 _ => {
 742                     // `last_ty` can be `!`, `expected` will have better info when present.
 743                     let t = self.resolve_vars_if_possible(&match exp_found {
 744                         Some(ty::error::ExpectedFound { expected, .. }) => expected,
 745                         _ => last_ty,
 746                     });
 747                     let msg = "`match` arms have incompatible types";
 748                     err.span_label(cause.span, msg);
 749                     if prior_arms.len() <= 4 {
 750                         for sp in prior_arms {
 751                             err.span_label(*sp, format!("this is found to be of type `{}`", t));
 752                         }
 753                     } else if let Some(sp) = prior_arms.last() {
 754                         err.span_label(
 755                             *sp,
 756                             format!("this and all prior arms are found to be of type `{}`", t),
 757                         );
 758                     }
 759                 }
 760             },
 761             ObligationCauseCode::IfExpression(box IfExpressionCause { then, outer, semicolon }) => {
 762                 err.span_label(then, "expected because of this");
 763                 outer.map(|sp| err.span_label(sp, "`if` and `else` have incompatible types"));
 764                 if let Some(sp) = semicolon {
 765                     err.span_suggestion_short(
 766                         sp,
 767                         "consider removing this semicolon",
 768                         String::new(),
 769                         Applicability::MachineApplicable,
 770                     );
 771                 }
 772             }
 773             _ => (),
 774         }
 775     }
 776
 777     /// Given that `other_ty` is the same as a type argument for `name` in `sub`, populate `value`
 778     /// highlighting `name` and every type argument that isn't at `pos` (which is `other_ty`), and
 779     /// populate `other_value` with `other_ty`.
 780     ///
 781     /// ```text
 782     /// Foo<Bar<Qux>>
 783     /// ^^^^--------^ this is highlighted
 784     /// |   |
 785     /// |   this type argument is exactly the same as the other type, not highlighted
 786     /// this is highlighted
 787     /// Bar<Qux>
 788     /// -------- this type is the same as a type argument in the other type, not highlighted
 789     /// ```
 790     fn highlight_outer(
 791         &self,
 792         value: &mut DiagnosticStyledString,
 793         other_value: &mut DiagnosticStyledString,
 794         name: String,
 795         sub: ty::subst::SubstsRef<'tcx>,
 796         pos: usize,
 797         other_ty: Ty<'tcx>,
 798     ) {
 799         // `value` and `other_value` hold two incomplete type representation for display.
 800         // `name` is the path of both types being compared. `sub`
 801         value.push_highlighted(name);
 802         let len = sub.len();
 803         if len > 0 {
 804             value.push_highlighted("<");
 805         }
 806
 807         // Output the lifetimes for the first type
 808         let lifetimes = sub
 809             .regions()
 810             .map(|lifetime| {
 811                 let s = lifetime.to_string();
 812                 if s.is_empty() { "'_".to_string() } else { s }
 813             })
 814             .collect::<Vec<_>>()
 815             .join(", ");
 816         if !lifetimes.is_empty() {
 817             if sub.regions().count() < len {
 818                 value.push_normal(lifetimes + ", ");
 819             } else {
 820                 value.push_normal(lifetimes);
 821             }
 822         }
 823
 824         // Highlight all the type arguments that aren't at `pos` and compare the type argument at
 825         // `pos` and `other_ty`.
 826         for (i, type_arg) in sub.types().enumerate() {
 827             if i == pos {
 828                 let values = self.cmp(type_arg, other_ty);
 829                 value.0.extend((values.0).0);
 830                 other_value.0.extend((values.1).0);
 831             } else {
 832                 value.push_highlighted(type_arg.to_string());
 833             }
 834
 835             if len > 0 && i != len - 1 {
 836                 value.push_normal(", ");
 837             }
 838         }
 839         if len > 0 {
 840             value.push_highlighted(">");
 841         }
 842     }
 843
 844     /// If `other_ty` is the same as a type argument present in `sub`, highlight `path` in `t1_out`,
 845     /// as that is the difference to the other type.
 846     ///
 847     /// For the following code:
 848     ///
 849     /// ```norun
 850     /// let x: Foo<Bar<Qux>> = foo::<Bar<Qux>>();
 851     /// ```
 852     ///
 853     /// The type error output will behave in the following way:
 854     ///
 855     /// ```text
 856     /// Foo<Bar<Qux>>
 857     /// ^^^^--------^ this is highlighted
 858     /// |   |
 859     /// |   this type argument is exactly the same as the other type, not highlighted
 860     /// this is highlighted
 861     /// Bar<Qux>
 862     /// -------- this type is the same as a type argument in the other type, not highlighted
 863     /// ```
 864     fn cmp_type_arg(
 865         &self,
 866         mut t1_out: &mut DiagnosticStyledString,
 867         mut t2_out: &mut DiagnosticStyledString,
 868         path: String,
 869         sub: ty::subst::SubstsRef<'tcx>,
 870         other_path: String,
 871         other_ty: Ty<'tcx>,
 872     ) -> Option<()> {
 873         for (i, ta) in sub.types().enumerate() {
 874             if ta == other_ty {
 875                 self.highlight_outer(&mut t1_out, &mut t2_out, path, sub, i, &other_ty);
 876                 return Some(());
 877             }
 878             if let &ty::Adt(def, _) = &ta.kind {
 879                 let path_ = self.tcx.def_path_str(def.did.clone());
 880                 if path_ == other_path {
 881                     self.highlight_outer(&mut t1_out, &mut t2_out, path, sub, i, &other_ty);
 882                     return Some(());
 883                 }
 884             }
 885         }
 886         None
 887     }
 888
 889     /// Adds a `,` to the type representation only if it is appropriate.
 890     fn push_comma(
 891         &self,
 892         value: &mut DiagnosticStyledString,
 893         other_value: &mut DiagnosticStyledString,
 894         len: usize,
 895         pos: usize,
 896     ) {
 897         if len > 0 && pos != len - 1 {
 898             value.push_normal(", ");
 899             other_value.push_normal(", ");
 900         }
 901     }
 902
 903     /// For generic types with parameters with defaults, remove the parameters corresponding to
 904     /// the defaults. This repeats a lot of the logic found in `ty::print::pretty`.
 905     fn strip_generic_default_params(
 906         &self,
 907         def_id: DefId,
 908         substs: ty::subst::SubstsRef<'tcx>,
 909     ) -> SubstsRef<'tcx> {
 910         let generics = self.tcx.generics_of(def_id);
 911         let mut num_supplied_defaults = 0;
 912         let mut type_params = generics
 913             .params
 914             .iter()
 915             .rev()
 916             .filter_map(|param| match param.kind {
 917                 ty::GenericParamDefKind::Lifetime => None,
 918                 ty::GenericParamDefKind::Type { has_default, .. } => {
 919                     Some((param.def_id, has_default))
 920                 }
 921                 ty::GenericParamDefKind::Const => None, // FIXME(const_generics:defaults)
 922             })
 923             .peekable();
 924         let has_default = {
 925             let has_default = type_params.peek().map(|(_, has_default)| has_default);
 926             *has_default.unwrap_or(&false)
 927         };
 928         if has_default {
 929             let types = substs.types().rev();
 930             for ((def_id, has_default), actual) in type_params.zip(types) {
 931                 if !has_default {
 932                     break;
 933                 }
 934                 if self.tcx.type_of(def_id).subst(self.tcx, substs) != actual {
 935                     break;
 936                 }
 937                 num_supplied_defaults += 1;
 938             }
 939         }
 940         let len = generics.params.len();
 941         let mut generics = generics.clone();
 942         generics.params.truncate(len - num_supplied_defaults);
 943         substs.truncate_to(self.tcx, &generics)
 944     }
 945
 946     /// Given two `fn` signatures highlight only sub-parts that are different.
 947     fn cmp_fn_sig(
 948         &self,
 949         sig1: &ty::PolyFnSig<'tcx>,
 950         sig2: &ty::PolyFnSig<'tcx>,
 951     ) -> (DiagnosticStyledString, DiagnosticStyledString) {
 952         let get_lifetimes = |sig| {
 953             use rustc_hir::def::Namespace;
 954             let mut s = String::new();
 955             let (_, (sig, reg)) = ty::print::FmtPrinter::new(self.tcx, &mut s, Namespace::TypeNS)
 956                 .name_all_regions(sig)
 957                 .unwrap();
 958             let lts: Vec<String> = reg.into_iter().map(|(_, kind)| kind.to_string()).collect();
 959             (if lts.is_empty() { String::new() } else { format!("for<{}> ", lts.join(", ")) }, sig)
 960         };
 961
 962         let (lt1, sig1) = get_lifetimes(sig1);
 963         let (lt2, sig2) = get_lifetimes(sig2);
 964
 965         // unsafe extern "C" for<'a> fn(&'a T) -> &'a T
 966         let mut values = (
 967             DiagnosticStyledString::normal("".to_string()),
 968             DiagnosticStyledString::normal("".to_string()),
 969         );
 970
 971         // unsafe extern "C" for<'a> fn(&'a T) -> &'a T
 972         // ^^^^^^
 973         values.0.push(sig1.unsafety.prefix_str(), sig1.unsafety != sig2.unsafety);
 974         values.1.push(sig2.unsafety.prefix_str(), sig1.unsafety != sig2.unsafety);
 975
 976         // unsafe extern "C" for<'a> fn(&'a T) -> &'a T
 977         //        ^^^^^^^^^^
 978         if sig1.abi != abi::Abi::Rust {
 979             values.0.push(format!("extern {} ", sig1.abi), sig1.abi != sig2.abi);
 980         }
 981         if sig2.abi != abi::Abi::Rust {
 982             values.1.push(format!("extern {} ", sig2.abi), sig1.abi != sig2.abi);
 983         }
 984
 985         // unsafe extern "C" for<'a> fn(&'a T) -> &'a T
 986         //                   ^^^^^^^^
 987         let lifetime_diff = lt1 != lt2;
 988         values.0.push(lt1, lifetime_diff);
 989         values.1.push(lt2, lifetime_diff);
 990
 991         // unsafe extern "C" for<'a> fn(&'a T) -> &'a T
 992         //                           ^^^
 993         values.0.push_normal("fn(");
 994         values.1.push_normal("fn(");
 995
 996         // unsafe extern "C" for<'a> fn(&'a T) -> &'a T
 997         //                              ^^^^^
 998         let len1 = sig1.inputs().len();
 999         let len2 = sig2.inputs().len();
1000         if len1 == len2 {
1001             for (i, (l, r)) in sig1.inputs().iter().zip(sig2.inputs().iter()).enumerate() {
1002                 let (x1, x2) = self.cmp(l, r);
1003                 (values.0).0.extend(x1.0);
1004                 (values.1).0.extend(x2.0);
1005                 self.push_comma(&mut values.0, &mut values.1, len1, i);
1006             }
1007         } else {
1008             for (i, l) in sig1.inputs().iter().enumerate() {
1009                 values.0.push_highlighted(l.to_string());
1010                 if i != len1 - 1 {
1011                     values.0.push_highlighted(", ");
1012                 }
1013             }
1014             for (i, r) in sig2.inputs().iter().enumerate() {
1015                 values.1.push_highlighted(r.to_string());
1016                 if i != len2 - 1 {
1017                     values.1.push_highlighted(", ");
1018                 }
1019             }
1020         }
1021
1022         if sig1.c_variadic {
1023             if len1 > 0 {
1024                 values.0.push_normal(", ");
1025             }
1026             values.0.push("...", !sig2.c_variadic);
1027         }
1028         if sig2.c_variadic {
1029             if len2 > 0 {
1030                 values.1.push_normal(", ");
1031             }
1032             values.1.push("...", !sig1.c_variadic);
1033         }
1034
1035         // unsafe extern "C" for<'a> fn(&'a T) -> &'a T
1036         //                                   ^
1037         values.0.push_normal(")");
1038         values.1.push_normal(")");
1039
1040         // unsafe extern "C" for<'a> fn(&'a T) -> &'a T
1041         //                                     ^^^^^^^^
1042         let output1 = sig1.output();
1043         let output2 = sig2.output();
1044         let (x1, x2) = self.cmp(output1, output2);
1045         if !output1.is_unit() {
1046             values.0.push_normal(" -> ");
1047             (values.0).0.extend(x1.0);
1048         }
1049         if !output2.is_unit() {
1050             values.1.push_normal(" -> ");
1051             (values.1).0.extend(x2.0);
1052         }
1053         values
1054     }
1055
1056     /// Compares two given types, eliding parts that are the same between them and highlighting
1057     /// relevant differences, and return two representation of those types for highlighted printing.
1058     fn cmp(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) -> (DiagnosticStyledString, DiagnosticStyledString) {
1059         debug!("cmp(t1={}, t1.kind={:?}, t2={}, t2.kind={:?})", t1, t1.kind, t2, t2.kind);
1060
1061         // helper functions
1062         fn equals<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
1063             match (&a.kind, &b.kind) {
1064                 (a, b) if *a == *b => true,
1065                 (&ty::Int(_), &ty::Infer(ty::InferTy::IntVar(_)))
1066                 | (&ty::Infer(ty::InferTy::IntVar(_)), &ty::Int(_))
1067                 | (&ty::Infer(ty::InferTy::IntVar(_)), &ty::Infer(ty::InferTy::IntVar(_)))
1068                 | (&ty::Float(_), &ty::Infer(ty::InferTy::FloatVar(_)))
1069                 | (&ty::Infer(ty::InferTy::FloatVar(_)), &ty::Float(_))
1070                 | (&ty::Infer(ty::InferTy::FloatVar(_)), &ty::Infer(ty::InferTy::FloatVar(_))) => {
1071                     true
1072                 }
1073                 _ => false,
1074             }
1075         }
1076
1077         fn push_ty_ref<'tcx>(
1078             r: &ty::Region<'tcx>,
1079             ty: Ty<'tcx>,
1080             mutbl: hir::Mutability,
1081             s: &mut DiagnosticStyledString,
1082         ) {
1083             let mut r = r.to_string();
1084             if r == "'_" {
1085                 r.clear();
1086             } else {
1087                 r.push(' ');
1088             }
1089             s.push_highlighted(format!("&{}{}", r, mutbl.prefix_str()));
1090             s.push_normal(ty.to_string());
1091         }
1092
1093         // process starts here
1094         match (&t1.kind, &t2.kind) {
1095             (&ty::Adt(def1, sub1), &ty::Adt(def2, sub2)) => {
1096                 let sub_no_defaults_1 = self.strip_generic_default_params(def1.did, sub1);
1097                 let sub_no_defaults_2 = self.strip_generic_default_params(def2.did, sub2);
1098                 let mut values = (DiagnosticStyledString::new(), DiagnosticStyledString::new());
1099                 let path1 = self.tcx.def_path_str(def1.did.clone());
1100                 let path2 = self.tcx.def_path_str(def2.did.clone());
1101                 if def1.did == def2.did {
1102                     // Easy case. Replace same types with `_` to shorten the output and highlight
1103                     // the differing ones.
1104                     //     let x: Foo<Bar, Qux> = y::<Foo<Quz, Qux>>();
1105                     //     Foo<Bar, _>
1106                     //     Foo<Quz, _>
1107                     //         ---  ^ type argument elided
1108                     //         |
1109                     //         highlighted in output
1110                     values.0.push_normal(path1);
1111                     values.1.push_normal(path2);
1112
1113                     // Avoid printing out default generic parameters that are common to both
1114                     // types.
1115                     let len1 = sub_no_defaults_1.len();
1116                     let len2 = sub_no_defaults_2.len();
1117                     let common_len = cmp::min(len1, len2);
1118                     let remainder1: Vec<_> = sub1.types().skip(common_len).collect();
1119                     let remainder2: Vec<_> = sub2.types().skip(common_len).collect();
1120                     let common_default_params = remainder1
1121                         .iter()
1122                         .rev()
1123                         .zip(remainder2.iter().rev())
1124                         .filter(|(a, b)| a == b)
1125                         .count();
1126                     let len = sub1.len() - common_default_params;
1127                     let consts_offset = len - sub1.consts().count();
1128
1129                     // Only draw `<...>` if there're lifetime/type arguments.
1130                     if len > 0 {
1131                         values.0.push_normal("<");
1132                         values.1.push_normal("<");
1133                     }
1134
1135                     fn lifetime_display(lifetime: Region<'_>) -> String {
1136                         let s = lifetime.to_string();
1137                         if s.is_empty() { "'_".to_string() } else { s }
1138                     }
1139                     // At one point we'd like to elide all lifetimes here, they are irrelevant for
1140                     // all diagnostics that use this output
1141                     //
1142                     //     Foo<'x, '_, Bar>
1143                     //     Foo<'y, '_, Qux>
1144                     //         ^^  ^^  --- type arguments are not elided
1145                     //         |   |
1146                     //         |   elided as they were the same
1147                     //         not elided, they were different, but irrelevant
1148                     let lifetimes = sub1.regions().zip(sub2.regions());
1149                     for (i, lifetimes) in lifetimes.enumerate() {
1150                         let l1 = lifetime_display(lifetimes.0);
1151                         let l2 = lifetime_display(lifetimes.1);
1152                         if lifetimes.0 == lifetimes.1 {
1153                             values.0.push_normal("'_");
1154                             values.1.push_normal("'_");
1155                         } else {
1156                             values.0.push_highlighted(l1);
1157                             values.1.push_highlighted(l2);
1158                         }
1159                         self.push_comma(&mut values.0, &mut values.1, len, i);
1160                     }
1161
1162                     // We're comparing two types with the same path, so we compare the type
1163                     // arguments for both. If they are the same, do not highlight and elide from the
1164                     // output.
1165                     //     Foo<_, Bar>
1166                     //     Foo<_, Qux>
1167                     //         ^ elided type as this type argument was the same in both sides
1168                     let type_arguments = sub1.types().zip(sub2.types());
1169                     let regions_len = sub1.regions().count();
1170                     let num_display_types = consts_offset - regions_len;
1171                     for (i, (ta1, ta2)) in type_arguments.take(num_display_types).enumerate() {
1172                         let i = i + regions_len;
1173                         if ta1 == ta2 {
1174                             values.0.push_normal("_");
1175                             values.1.push_normal("_");
1176                         } else {
1177                             let (x1, x2) = self.cmp(ta1, ta2);
1178                             (values.0).0.extend(x1.0);
1179                             (values.1).0.extend(x2.0);
1180                         }
1181                         self.push_comma(&mut values.0, &mut values.1, len, i);
1182                     }
1183
1184                     // Do the same for const arguments, if they are equal, do not highlight and
1185                     // elide them from the output.
1186                     let const_arguments = sub1.consts().zip(sub2.consts());
1187                     for (i, (ca1, ca2)) in const_arguments.enumerate() {
1188                         let i = i + consts_offset;
1189                         if ca1 == ca2 {
1190                             values.0.push_normal("_");
1191                             values.1.push_normal("_");
1192                         } else {
1193                             values.0.push_highlighted(ca1.to_string());
1194                             values.1.push_highlighted(ca2.to_string());
1195                         }
1196                         self.push_comma(&mut values.0, &mut values.1, len, i);
1197                     }
1198
1199                     // Close the type argument bracket.
1200                     // Only draw `<...>` if there're lifetime/type arguments.
1201                     if len > 0 {
1202                         values.0.push_normal(">");
1203                         values.1.push_normal(">");
1204                     }
1205                     values
1206                 } else {
1207                     // Check for case:
1208                     //     let x: Foo<Bar<Qux> = foo::<Bar<Qux>>();
1209                     //     Foo<Bar<Qux>
1210                     //         ------- this type argument is exactly the same as the other type
1211                     //     Bar<Qux>
1212                     if self
1213                         .cmp_type_arg(
1214                             &mut values.0,
1215                             &mut values.1,
1216                             path1.clone(),
1217                             sub_no_defaults_1,
1218                             path2.clone(),
1219                             &t2,
1220                         )
1221                         .is_some()
1222                     {
1223                         return values;
1224                     }
1225                     // Check for case:
1226                     //     let x: Bar<Qux> = y:<Foo<Bar<Qux>>>();
1227                     //     Bar<Qux>
1228                     //     Foo<Bar<Qux>>
1229                     //         ------- this type argument is exactly the same as the other type
1230                     if self
1231                         .cmp_type_arg(
1232                             &mut values.1,
1233                             &mut values.0,
1234                             path2,
1235                             sub_no_defaults_2,
1236                             path1,
1237                             &t1,
1238                         )
1239                         .is_some()
1240                     {
1241                         return values;
1242                     }
1243
1244                     // We can't find anything in common, highlight relevant part of type path.
1245                     //     let x: foo::bar::Baz<Qux> = y:<foo::bar::Bar<Zar>>();
1246                     //     foo::bar::Baz<Qux>
1247                     //     foo::bar::Bar<Zar>
1248                     //               -------- this part of the path is different
1249
1250                     let t1_str = t1.to_string();
1251                     let t2_str = t2.to_string();
1252                     let min_len = t1_str.len().min(t2_str.len());
1253
1254                     const SEPARATOR: &str = "::";
1255                     let separator_len = SEPARATOR.len();
1256                     let split_idx: usize = t1_str
1257                         .split(SEPARATOR)
1258                         .zip(t2_str.split(SEPARATOR))
1259                         .take_while(|(mod1_str, mod2_str)| mod1_str == mod2_str)
1260                         .map(|(mod_str, _)| mod_str.len() + separator_len)
1261                         .sum();
1262
1263                     debug!(
1264                         "cmp: separator_len={}, split_idx={}, min_len={}",
1265                         separator_len, split_idx, min_len
1266                     );
1267
1268                     if split_idx >= min_len {
1269                         // paths are identical, highlight everything
1270                         (
1271                             DiagnosticStyledString::highlighted(t1_str),
1272                             DiagnosticStyledString::highlighted(t2_str),
1273                         )
1274                     } else {
1275                         let (common, uniq1) = t1_str.split_at(split_idx);
1276                         let (_, uniq2) = t2_str.split_at(split_idx);
1277                         debug!("cmp: common={}, uniq1={}, uniq2={}", common, uniq1, uniq2);
1278
1279                         values.0.push_normal(common);
1280                         values.0.push_highlighted(uniq1);
1281                         values.1.push_normal(common);
1282                         values.1.push_highlighted(uniq2);
1283
1284                         values
1285                     }
1286                 }
1287             }
1288
1289             // When finding T != &T, highlight only the borrow
1290             (&ty::Ref(r1, ref_ty1, mutbl1), _) if equals(&ref_ty1, &t2) => {
1291                 let mut values = (DiagnosticStyledString::new(), DiagnosticStyledString::new());
1292                 push_ty_ref(&r1, ref_ty1, mutbl1, &mut values.0);
1293                 values.1.push_normal(t2.to_string());
1294                 values
1295             }
1296             (_, &ty::Ref(r2, ref_ty2, mutbl2)) if equals(&t1, &ref_ty2) => {
1297                 let mut values = (DiagnosticStyledString::new(), DiagnosticStyledString::new());
1298                 values.0.push_normal(t1.to_string());
1299                 push_ty_ref(&r2, ref_ty2, mutbl2, &mut values.1);
1300                 values
1301             }
1302
1303             // When encountering &T != &mut T, highlight only the borrow
1304             (&ty::Ref(r1, ref_ty1, mutbl1), &ty::Ref(r2, ref_ty2, mutbl2))
1305                 if equals(&ref_ty1, &ref_ty2) =>
1306             {
1307                 let mut values = (DiagnosticStyledString::new(), DiagnosticStyledString::new());
1308                 push_ty_ref(&r1, ref_ty1, mutbl1, &mut values.0);
1309                 push_ty_ref(&r2, ref_ty2, mutbl2, &mut values.1);
1310                 values
1311             }
1312
1313             // When encountering tuples of the same size, highlight only the differing types
1314             (&ty::Tuple(substs1), &ty::Tuple(substs2)) if substs1.len() == substs2.len() => {
1315                 let mut values =
1316                     (DiagnosticStyledString::normal("("), DiagnosticStyledString::normal("("));
1317                 let len = substs1.len();
1318                 for (i, (left, right)) in substs1.types().zip(substs2.types()).enumerate() {
1319                     let (x1, x2) = self.cmp(left, right);
1320                     (values.0).0.extend(x1.0);
1321                     (values.1).0.extend(x2.0);
1322                     self.push_comma(&mut values.0, &mut values.1, len, i);
1323                 }
1324                 if len == 1 {
1325                     // Keep the output for single element tuples as `(ty,)`.
1326                     values.0.push_normal(",");
1327                     values.1.push_normal(",");
1328                 }
1329                 values.0.push_normal(")");
1330                 values.1.push_normal(")");
1331                 values
1332             }
1333
1334             (ty::FnDef(did1, substs1), ty::FnDef(did2, substs2)) => {
1335                 let sig1 = self.tcx.fn_sig(*did1).subst(self.tcx, substs1);
1336                 let sig2 = self.tcx.fn_sig(*did2).subst(self.tcx, substs2);
1337                 let mut values = self.cmp_fn_sig(&sig1, &sig2);
1338                 let path1 = format!(" {{{}}}", self.tcx.def_path_str_with_substs(*did1, substs1));
1339                 let path2 = format!(" {{{}}}", self.tcx.def_path_str_with_substs(*did2, substs2));
1340                 let same_path = path1 == path2;
1341                 values.0.push(path1, !same_path);
1342                 values.1.push(path2, !same_path);
1343                 values
1344             }
1345
1346             (ty::FnDef(did1, substs1), ty::FnPtr(sig2)) => {
1347                 let sig1 = self.tcx.fn_sig(*did1).subst(self.tcx, substs1);
1348                 let mut values = self.cmp_fn_sig(&sig1, sig2);
1349                 values.0.push_normal(format!(
1350                     " {{{}}}",
1351                     self.tcx.def_path_str_with_substs(*did1, substs1)
1352                 ));
1353                 values
1354             }
1355
1356             (ty::FnPtr(sig1), ty::FnDef(did2, substs2)) => {
1357                 let sig2 = self.tcx.fn_sig(*did2).subst(self.tcx, substs2);
1358                 let mut values = self.cmp_fn_sig(sig1, &sig2);
1359                 values.1.push_normal(format!(
1360                     " {{{}}}",
1361                     self.tcx.def_path_str_with_substs(*did2, substs2)
1362                 ));
1363                 values
1364             }
1365
1366             (ty::FnPtr(sig1), ty::FnPtr(sig2)) => self.cmp_fn_sig(sig1, sig2),
1367
1368             _ => {
1369                 if t1 == t2 {
1370                     // The two types are the same, elide and don't highlight.
1371                     (DiagnosticStyledString::normal("_"), DiagnosticStyledString::normal("_"))
1372                 } else {
1373                     // We couldn't find anything in common, highlight everything.
1374                     (
1375                         DiagnosticStyledString::highlighted(t1.to_string()),
1376                         DiagnosticStyledString::highlighted(t2.to_string()),
1377                     )
1378                 }
1379             }
1380         }
1381     }
1382
1383     pub fn note_type_err(
1384         &self,
1385         diag: &mut DiagnosticBuilder<'tcx>,
1386         cause: &ObligationCause<'tcx>,
1387         secondary_span: Option<(Span, String)>,
1388         mut values: Option<ValuePairs<'tcx>>,
1389         terr: &TypeError<'tcx>,
1390     ) {
1391         let span = cause.span(self.tcx);
1392
1393         // For some types of errors, expected-found does not make
1394         // sense, so just ignore the values we were given.
1395         match terr {
1396             TypeError::CyclicTy(_) => {
1397                 values = None;
1398             }
1399             _ => {}
1400         }
1401
1402         struct OpaqueTypesVisitor<'tcx> {
1403             types: FxHashMap<TyCategory, FxHashSet<Span>>,
1404             expected: FxHashMap<TyCategory, FxHashSet<Span>>,
1405             found: FxHashMap<TyCategory, FxHashSet<Span>>,
1406             ignore_span: Span,
1407             tcx: TyCtxt<'tcx>,
1408         }
1409
1410         impl<'tcx> OpaqueTypesVisitor<'tcx> {
1411             fn visit_expected_found(
1412                 tcx: TyCtxt<'tcx>,
1413                 expected: Ty<'tcx>,
1414                 found: Ty<'tcx>,
1415                 ignore_span: Span,
1416             ) -> Self {
1417                 let mut types_visitor = OpaqueTypesVisitor {
1418                     types: Default::default(),
1419                     expected: Default::default(),
1420                     found: Default::default(),
1421                     ignore_span,
1422                     tcx,
1423                 };
1424                 // The visitor puts all the relevant encountered types in `self.types`, but in
1425                 // here we want to visit two separate types with no relation to each other, so we
1426                 // move the results from `types` to `expected` or `found` as appropriate.
1427                 expected.visit_with(&mut types_visitor);
1428                 std::mem::swap(&mut types_visitor.expected, &mut types_visitor.types);
1429                 found.visit_with(&mut types_visitor);
1430                 std::mem::swap(&mut types_visitor.found, &mut types_visitor.types);
1431                 types_visitor
1432             }
1433
1434             fn report(&self, err: &mut DiagnosticBuilder<'_>) {
1435                 self.add_labels_for_types(err, "expected", &self.expected);
1436                 self.add_labels_for_types(err, "found", &self.found);
1437             }
1438
1439             fn add_labels_for_types(
1440                 &self,
1441                 err: &mut DiagnosticBuilder<'_>,
1442                 target: &str,
1443                 types: &FxHashMap<TyCategory, FxHashSet<Span>>,
1444             ) {
1445                 for (key, values) in types.iter() {
1446                     let count = values.len();
1447                     let kind = key.descr();
1448                     for sp in values {
1449                         err.span_label(
1450                             *sp,
1451                             format!(
1452                                 "{}{}{} {}{}",
1453                                 if sp.is_desugaring(DesugaringKind::Async) {
1454                                     "the `Output` of this `async fn`'s "
1455                                 } else if count == 1 {
1456                                     "the "
1457                                 } else {
1458                                     ""
1459                                 },
1460                                 if count > 1 { "one of the " } else { "" },
1461                                 target,
1462                                 kind,
1463                                 pluralize!(count),
1464                             ),
1465                         );
1466                     }
1467                 }
1468             }
1469         }
1470
1471         impl<'tcx> ty::fold::TypeVisitor<'tcx> for OpaqueTypesVisitor<'tcx> {
1472             fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
1473                 if let Some((kind, def_id)) = TyCategory::from_ty(t) {
1474                     let span = self.tcx.def_span(def_id);
1475                     // Avoid cluttering the output when the "found" and error span overlap:
1476                     //
1477                     // error[E0308]: mismatched types
1478                     //   --> $DIR/issue-20862.rs:2:5
1479                     //    |
1480                     // LL |     |y| x + y
1481                     //    |     ^^^^^^^^^
1482                     //    |     |
1483                     //    |     the found closure
1484                     //    |     expected `()`, found closure
1485                     //    |
1486                     //    = note: expected unit type `()`
1487                     //                 found closure `[closure@$DIR/issue-20862.rs:2:5: 2:14 x:_]`
1488                     if !self.ignore_span.overlaps(span) {
1489                         self.types.entry(kind).or_default().insert(span);
1490                     }
1491                 }
1492                 t.super_visit_with(self)
1493             }
1494         }
1495
1496         debug!("note_type_err(diag={:?})", diag);
1497         let (expected_found, exp_found, is_simple_error) = match values {
1498             None => (None, None, false),
1499             Some(values) => {
1500                 let (is_simple_error, exp_found) = match values {
1501                     ValuePairs::Types(exp_found) => {
1502                         let is_simple_err =
1503                             exp_found.expected.is_simple_text() && exp_found.found.is_simple_text();
1504                         OpaqueTypesVisitor::visit_expected_found(
1505                             self.tcx,
1506                             exp_found.expected,
1507                             exp_found.found,
1508                             span,
1509                         )
1510                         .report(diag);
1511
1512                         (is_simple_err, Some(exp_found))
1513                     }
1514                     _ => (false, None),
1515                 };
1516                 let vals = match self.values_str(&values) {
1517                     Some((expected, found)) => Some((expected, found)),
1518                     None => {
1519                         // Derived error. Cancel the emitter.
1520                         diag.cancel();
1521                         return;
1522                     }
1523                 };
1524                 (vals, exp_found, is_simple_error)
1525             }
1526         };
1527
1528         // Ignore msg for object safe coercion
1529         // since E0038 message will be printed
1530         match terr {
1531             TypeError::ObjectUnsafeCoercion(_) => {}
1532             _ => {
1533                 diag.span_label(span, terr.to_string());
1534                 if let Some((sp, msg)) = secondary_span {
1535                     diag.span_label(sp, msg);
1536                 }
1537             }
1538         };
1539         if let Some((expected, found)) = expected_found {
1540             let expected_label = exp_found.map_or("type".into(), |ef| ef.expected.prefix_string());
1541             let found_label = exp_found.map_or("type".into(), |ef| ef.found.prefix_string());
1542             match (&terr, expected == found) {
1543                 (TypeError::Sorts(values), extra) => {
1544                     let sort_string = |ty: Ty<'tcx>| match (extra, &ty.kind) {
1545                         (true, ty::Opaque(def_id, _)) => format!(
1546                             " (opaque type at {})",
1547                             self.tcx
1548                                 .sess
1549                                 .source_map()
1550                                 .mk_substr_filename(self.tcx.def_span(*def_id)),
1551                         ),
1552                         (true, _) => format!(" ({})", ty.sort_string(self.tcx)),
1553                         (false, _) => "".to_string(),
1554                     };
1555                     if !(values.expected.is_simple_text() && values.found.is_simple_text())
1556                         || (exp_found.map_or(false, |ef| {
1557                             // This happens when the type error is a subset of the expectation,
1558                             // like when you have two references but one is `usize` and the other
1559                             // is `f32`. In those cases we still want to show the `note`. If the
1560                             // value from `ef` is `Infer(_)`, then we ignore it.
1561                             if !ef.expected.is_ty_infer() {
1562                                 ef.expected != values.expected
1563                             } else if !ef.found.is_ty_infer() {
1564                                 ef.found != values.found
1565                             } else {
1566                                 false
1567                             }
1568                         }))
1569                     {
1570                         diag.note_expected_found_extra(
1571                             &expected_label,
1572                             expected,
1573                             &found_label,
1574                             found,
1575                             &sort_string(values.expected),
1576                             &sort_string(values.found),
1577                         );
1578                     }
1579                 }
1580                 (TypeError::ObjectUnsafeCoercion(_), _) => {
1581                     diag.note_unsuccessfull_coercion(found, expected);
1582                 }
1583                 (_, _) => {
1584                     debug!(
1585                         "note_type_err: exp_found={:?}, expected={:?} found={:?}",
1586                         exp_found, expected, found
1587                     );
1588                     if !is_simple_error || terr.must_include_note() {
1589                         diag.note_expected_found(&expected_label, expected, &found_label, found);
1590                     }
1591                 }
1592             }
1593         }
1594         if let Some(exp_found) = exp_found {
1595             self.suggest_as_ref_where_appropriate(span, &exp_found, diag);
1596         }
1597
1598         // In some (most?) cases cause.body_id points to actual body, but in some cases
1599         // it's a actual definition. According to the comments (e.g. in
1600         // librustc_typeck/check/compare_method.rs:compare_predicate_entailment) the latter
1601         // is relied upon by some other code. This might (or might not) need cleanup.
1602         let body_owner_def_id =
1603             self.tcx.hir().opt_local_def_id(cause.body_id).unwrap_or_else(|| {
1604                 self.tcx.hir().body_owner_def_id(hir::BodyId { hir_id: cause.body_id })
1605             });
1606         self.check_and_note_conflicting_crates(diag, terr);
1607         self.tcx.note_and_explain_type_err(diag, terr, span, body_owner_def_id);
1608
1609         // It reads better to have the error origin as the final
1610         // thing.
1611         self.note_error_origin(diag, &cause, exp_found);
1612     }
1613
1614     /// When encountering a case where `.as_ref()` on a `Result` or `Option` would be appropriate,
1615     /// suggests it.
1616     fn suggest_as_ref_where_appropriate(
1617         &self,
1618         span: Span,
1619         exp_found: &ty::error::ExpectedFound<Ty<'tcx>>,
1620         diag: &mut DiagnosticBuilder<'tcx>,
1621     ) {
1622         match (&exp_found.expected.kind, &exp_found.found.kind) {
1623             (ty::Adt(exp_def, exp_substs), ty::Ref(_, found_ty, _)) => {
1624                 if let ty::Adt(found_def, found_substs) = found_ty.kind {
1625                     let path_str = format!("{:?}", exp_def);
1626                     if exp_def == &found_def {
1627                         let opt_msg = "you can convert from `&Option<T>` to `Option<&T>` using \
1628                                        `.as_ref()`";
1629                         let result_msg = "you can convert from `&Result<T, E>` to \
1630                                           `Result<&T, &E>` using `.as_ref()`";
1631                         let have_as_ref = &[
1632                             ("std::option::Option", opt_msg),
1633                             ("core::option::Option", opt_msg),
1634                             ("std::result::Result", result_msg),
1635                             ("core::result::Result", result_msg),
1636                         ];
1637                         if let Some(msg) = have_as_ref
1638                             .iter()
1639                             .filter_map(
1640                                 |(path, msg)| if &path_str == path { Some(msg) } else { None },
1641                             )
1642                             .next()
1643                         {
1644                             let mut show_suggestion = true;
1645                             for (exp_ty, found_ty) in exp_substs.types().zip(found_substs.types()) {
1646                                 match exp_ty.kind {
1647                                     ty::Ref(_, exp_ty, _) => {
1648                                         match (&exp_ty.kind, &found_ty.kind) {
1649                                             (_, ty::Param(_))
1650                                             | (_, ty::Infer(_))
1651                                             | (ty::Param(_), _)
1652                                             | (ty::Infer(_), _) => {}
1653                                             _ if ty::TyS::same_type(exp_ty, found_ty) => {}
1654                                             _ => show_suggestion = false,
1655                                         };
1656                                     }
1657                                     ty::Param(_) | ty::Infer(_) => {}
1658                                     _ => show_suggestion = false,
1659                                 }
1660                             }
1661                             if let (Ok(snippet), true) =
1662                                 (self.tcx.sess.source_map().span_to_snippet(span), show_suggestion)
1663                             {
1664                                 diag.span_suggestion(
1665                                     span,
1666                                     msg,
1667                                     format!("{}.as_ref()", snippet),
1668                                     Applicability::MachineApplicable,
1669                                 );
1670                             }
1671                         }
1672                     }
1673                 }
1674             }
1675             _ => {}
1676         }
1677     }
1678
1679     pub fn report_and_explain_type_error(
1680         &self,
1681         trace: TypeTrace<'tcx>,
1682         terr: &TypeError<'tcx>,
1683     ) -> DiagnosticBuilder<'tcx> {
1684         debug!("report_and_explain_type_error(trace={:?}, terr={:?})", trace, terr);
1685
1686         let span = trace.cause.span(self.tcx);
1687         let failure_code = trace.cause.as_failure_code(terr);
1688         let mut diag = match failure_code {
1689             FailureCode::Error0038(did) => {
1690                 let violations = self.tcx.object_safety_violations(did);
1691                 report_object_safety_error(self.tcx, span, did, violations)
1692             }
1693             FailureCode::Error0317(failure_str) => {
1694                 struct_span_err!(self.tcx.sess, span, E0317, "{}", failure_str)
1695             }
1696             FailureCode::Error0580(failure_str) => {
1697                 struct_span_err!(self.tcx.sess, span, E0580, "{}", failure_str)
1698             }
1699             FailureCode::Error0308(failure_str) => {
1700                 struct_span_err!(self.tcx.sess, span, E0308, "{}", failure_str)
1701             }
1702             FailureCode::Error0644(failure_str) => {
1703                 struct_span_err!(self.tcx.sess, span, E0644, "{}", failure_str)
1704             }
1705         };
1706         self.note_type_err(&mut diag, &trace.cause, None, Some(trace.values), terr);
1707         diag
1708     }
1709
1710     fn values_str(
1711         &self,
1712         values: &ValuePairs<'tcx>,
1713     ) -> Option<(DiagnosticStyledString, DiagnosticStyledString)> {
1714         match *values {
1715             infer::Types(ref exp_found) => self.expected_found_str_ty(exp_found),
1716             infer::Regions(ref exp_found) => self.expected_found_str(exp_found),
1717             infer::Consts(ref exp_found) => self.expected_found_str(exp_found),
1718             infer::TraitRefs(ref exp_found) => {
1719                 let pretty_exp_found = ty::error::ExpectedFound {
1720                     expected: exp_found.expected.print_only_trait_path(),
1721                     found: exp_found.found.print_only_trait_path(),
1722                 };
1723                 self.expected_found_str(&pretty_exp_found)
1724             }
1725             infer::PolyTraitRefs(ref exp_found) => {
1726                 let pretty_exp_found = ty::error::ExpectedFound {
1727                     expected: exp_found.expected.print_only_trait_path(),
1728                     found: exp_found.found.print_only_trait_path(),
1729                 };
1730                 self.expected_found_str(&pretty_exp_found)
1731             }
1732         }
1733     }
1734
1735     fn expected_found_str_ty(
1736         &self,
1737         exp_found: &ty::error::ExpectedFound<Ty<'tcx>>,
1738     ) -> Option<(DiagnosticStyledString, DiagnosticStyledString)> {
1739         let exp_found = self.resolve_vars_if_possible(exp_found);
1740         if exp_found.references_error() {
1741             return None;
1742         }
1743
1744         Some(self.cmp(exp_found.expected, exp_found.found))
1745     }
1746
1747     /// Returns a string of the form "expected `{}`, found `{}`".
1748     fn expected_found_str<T: fmt::Display + TypeFoldable<'tcx>>(
1749         &self,
1750         exp_found: &ty::error::ExpectedFound<T>,
1751     ) -> Option<(DiagnosticStyledString, DiagnosticStyledString)> {
1752         let exp_found = self.resolve_vars_if_possible(exp_found);
1753         if exp_found.references_error() {
1754             return None;
1755         }
1756
1757         Some((
1758             DiagnosticStyledString::highlighted(exp_found.expected.to_string()),
1759             DiagnosticStyledString::highlighted(exp_found.found.to_string()),
1760         ))
1761     }
1762
1763     pub fn report_generic_bound_failure(
1764         &self,
1765         region_scope_tree: &region::ScopeTree,
1766         span: Span,
1767         origin: Option<SubregionOrigin<'tcx>>,
1768         bound_kind: GenericKind<'tcx>,
1769         sub: Region<'tcx>,
1770     ) {
1771         self.construct_generic_bound_failure(region_scope_tree, span, origin, bound_kind, sub)
1772             .emit();
1773     }
1774
1775     pub fn construct_generic_bound_failure(
1776         &self,
1777         region_scope_tree: &region::ScopeTree,
1778         span: Span,
1779         origin: Option<SubregionOrigin<'tcx>>,
1780         bound_kind: GenericKind<'tcx>,
1781         sub: Region<'tcx>,
1782     ) -> DiagnosticBuilder<'a> {
1783         // Attempt to obtain the span of the parameter so we can
1784         // suggest adding an explicit lifetime bound to it.
1785         let type_param_span = match (self.in_progress_tables, bound_kind) {
1786             (Some(ref table), GenericKind::Param(ref param)) => {
1787                 let table = table.borrow();
1788                 table.local_id_root.and_then(|did| {
1789                     let generics = self.tcx.generics_of(did);
1790                     // Account for the case where `did` corresponds to `Self`, which doesn't have
1791                     // the expected type argument.
1792                     if !(generics.has_self && param.index == 0) {
1793                         let type_param = generics.type_param(param, self.tcx);
1794                         let hir = &self.tcx.hir();
1795                         hir.as_local_hir_id(type_param.def_id).map(|id| {
1796                             // Get the `hir::Param` to verify whether it already has any bounds.
1797                             // We do this to avoid suggesting code that ends up as `T: 'a'b`,
1798                             // instead we suggest `T: 'a + 'b` in that case.
1799                             let mut has_bounds = false;
1800                             if let Node::GenericParam(param) = hir.get(id) {
1801                                 has_bounds = !param.bounds.is_empty();
1802                             }
1803                             let sp = hir.span(id);
1804                             // `sp` only covers `T`, change it so that it covers
1805                             // `T:` when appropriate
1806                             let is_impl_trait = bound_kind.to_string().starts_with("impl ");
1807                             let sp = if has_bounds && !is_impl_trait {
1808                                 sp.to(self
1809                                     .tcx
1810                                     .sess
1811                                     .source_map()
1812                                     .next_point(self.tcx.sess.source_map().next_point(sp)))
1813                             } else {
1814                                 sp
1815                             };
1816                             (sp, has_bounds, is_impl_trait)
1817                         })
1818                     } else {
1819                         None
1820                     }
1821                 })
1822             }
1823             _ => None,
1824         };
1825
1826         let labeled_user_string = match bound_kind {
1827             GenericKind::Param(ref p) => format!("the parameter type `{}`", p),
1828             GenericKind::Projection(ref p) => format!("the associated type `{}`", p),
1829         };
1830
1831         if let Some(SubregionOrigin::CompareImplMethodObligation {
1832             span,
1833             item_name,
1834             impl_item_def_id,
1835             trait_item_def_id,
1836         }) = origin
1837         {
1838             return self.report_extra_impl_obligation(
1839                 span,
1840                 item_name,
1841                 impl_item_def_id,
1842                 trait_item_def_id,
1843                 &format!("`{}: {}`", bound_kind, sub),
1844             );
1845         }
1846
1847         fn binding_suggestion<'tcx, S: fmt::Display>(
1848             err: &mut DiagnosticBuilder<'tcx>,
1849             type_param_span: Option<(Span, bool, bool)>,
1850             bound_kind: GenericKind<'tcx>,
1851             sub: S,
1852         ) {
1853             let msg = "consider adding an explicit lifetime bound";
1854             if let Some((sp, has_lifetimes, is_impl_trait)) = type_param_span {
1855                 let suggestion = if is_impl_trait {
1856                     format!("{} + {}", bound_kind, sub)
1857                 } else {
1858                     let tail = if has_lifetimes { " + " } else { "" };
1859                     format!("{}: {}{}", bound_kind, sub, tail)
1860                 };
1861                 err.span_suggestion(
1862                     sp,
1863                     &format!("{}...", msg),
1864                     suggestion,
1865                     Applicability::MaybeIncorrect, // Issue #41966
1866                 );
1867             } else {
1868                 let consider = format!(
1869                     "{} {}...",
1870                     msg,
1871                     if type_param_span.map(|(_, _, is_impl_trait)| is_impl_trait).unwrap_or(false) {
1872                         format!(" `{}` to `{}`", sub, bound_kind)
1873                     } else {
1874                         format!("`{}: {}`", bound_kind, sub)
1875                     },
1876                 );
1877                 err.help(&consider);
1878             }
1879         }
1880
1881         let mut err = match *sub {
1882             ty::ReEarlyBound(ty::EarlyBoundRegion { name, .. })
1883             | ty::ReFree(ty::FreeRegion { bound_region: ty::BrNamed(_, name), .. }) => {
1884                 // Does the required lifetime have a nice name we can print?
1885                 let mut err = struct_span_err!(
1886                     self.tcx.sess,
1887                     span,
1888                     E0309,
1889                     "{} may not live long enough",
1890                     labeled_user_string
1891                 );
1892                 // Explicitly use the name instead of `sub`'s `Display` impl. The `Display` impl
1893                 // for the bound is not suitable for suggestions when `-Zverbose` is set because it
1894                 // uses `Debug` output, so we handle it specially here so that suggestions are
1895                 // always correct.
1896                 binding_suggestion(&mut err, type_param_span, bound_kind, name);
1897                 err
1898             }
1899
1900             ty::ReStatic => {
1901                 // Does the required lifetime have a nice name we can print?
1902                 let mut err = struct_span_err!(
1903                     self.tcx.sess,
1904                     span,
1905                     E0310,
1906                     "{} may not live long enough",
1907                     labeled_user_string
1908                 );
1909                 binding_suggestion(&mut err, type_param_span, bound_kind, "'static");
1910                 err
1911             }
1912
1913             _ => {
1914                 // If not, be less specific.
1915                 let mut err = struct_span_err!(
1916                     self.tcx.sess,
1917                     span,
1918                     E0311,
1919                     "{} may not live long enough",
1920                     labeled_user_string
1921                 );
1922                 err.help(&format!(
1923                     "consider adding an explicit lifetime bound for `{}`",
1924                     bound_kind
1925                 ));
1926                 note_and_explain_region(
1927                     self.tcx,
1928                     region_scope_tree,
1929                     &mut err,
1930                     &format!("{} must be valid for ", labeled_user_string),
1931                     sub,
1932                     "...",
1933                 );
1934                 err
1935             }
1936         };
1937
1938         if let Some(origin) = origin {
1939             self.note_region_origin(&mut err, &origin);
1940         }
1941         err
1942     }
1943
1944     fn report_sub_sup_conflict(
1945         &self,
1946         region_scope_tree: &region::ScopeTree,
1947         var_origin: RegionVariableOrigin,
1948         sub_origin: SubregionOrigin<'tcx>,
1949         sub_region: Region<'tcx>,
1950         sup_origin: SubregionOrigin<'tcx>,
1951         sup_region: Region<'tcx>,
1952     ) {
1953         let mut err = self.report_inference_failure(var_origin);
1954
1955         note_and_explain_region(
1956             self.tcx,
1957             region_scope_tree,
1958             &mut err,
1959             "first, the lifetime cannot outlive ",
1960             sup_region,
1961             "...",
1962         );
1963
1964         match (&sup_origin, &sub_origin) {
1965             (&infer::Subtype(ref sup_trace), &infer::Subtype(ref sub_trace)) => {
1966                 debug!("report_sub_sup_conflict: var_origin={:?}", var_origin);
1967                 debug!("report_sub_sup_conflict: sub_region={:?}", sub_region);
1968                 debug!("report_sub_sup_conflict: sub_origin={:?}", sub_origin);
1969                 debug!("report_sub_sup_conflict: sup_region={:?}", sup_region);
1970                 debug!("report_sub_sup_conflict: sup_origin={:?}", sup_origin);
1971                 debug!("report_sub_sup_conflict: sup_trace={:?}", sup_trace);
1972                 debug!("report_sub_sup_conflict: sub_trace={:?}", sub_trace);
1973                 debug!("report_sub_sup_conflict: sup_trace.values={:?}", sup_trace.values);
1974                 debug!("report_sub_sup_conflict: sub_trace.values={:?}", sub_trace.values);
1975
1976                 if let (Some((sup_expected, sup_found)), Some((sub_expected, sub_found))) =
1977                     (self.values_str(&sup_trace.values), self.values_str(&sub_trace.values))
1978                 {
1979                     if sub_expected == sup_expected && sub_found == sup_found {
1980                         note_and_explain_region(
1981                             self.tcx,
1982                             region_scope_tree,
1983                             &mut err,
1984                             "...but the lifetime must also be valid for ",
1985                             sub_region,
1986                             "...",
1987                         );
1988                         err.span_note(
1989                             sup_trace.cause.span,
1990                             &format!("...so that the {}", sup_trace.cause.as_requirement_str()),
1991                         );
1992
1993                         err.note_expected_found(&"", sup_expected, &"", sup_found);
1994                         err.emit();
1995                         return;
1996                     }
1997                 }
1998             }
1999             _ => {}
2000         }
2001
2002         self.note_region_origin(&mut err, &sup_origin);
2003
2004         note_and_explain_region(
2005             self.tcx,
2006             region_scope_tree,
2007             &mut err,
2008             "but, the lifetime must be valid for ",
2009             sub_region,
2010             "...",
2011         );
2012
2013         self.note_region_origin(&mut err, &sub_origin);
2014         err.emit();
2015     }
2016 }
2017
2018 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
2019     fn report_inference_failure(
2020         &self,
2021         var_origin: RegionVariableOrigin,
2022     ) -> DiagnosticBuilder<'tcx> {
2023         let br_string = |br: ty::BoundRegion| {
2024             let mut s = match br {
2025                 ty::BrNamed(_, name) => name.to_string(),
2026                 _ => String::new(),
2027             };
2028             if !s.is_empty() {
2029                 s.push_str(" ");
2030             }
2031             s
2032         };
2033         let var_description = match var_origin {
2034             infer::MiscVariable(_) => String::new(),
2035             infer::PatternRegion(_) => " for pattern".to_string(),
2036             infer::AddrOfRegion(_) => " for borrow expression".to_string(),
2037             infer::Autoref(_) => " for autoref".to_string(),
2038             infer::Coercion(_) => " for automatic coercion".to_string(),
2039             infer::LateBoundRegion(_, br, infer::FnCall) => {
2040                 format!(" for lifetime parameter {}in function call", br_string(br))
2041             }
2042             infer::LateBoundRegion(_, br, infer::HigherRankedType) => {
2043                 format!(" for lifetime parameter {}in generic type", br_string(br))
2044             }
2045             infer::LateBoundRegion(_, br, infer::AssocTypeProjection(def_id)) => format!(
2046                 " for lifetime parameter {}in trait containing associated type `{}`",
2047                 br_string(br),
2048                 self.tcx.associated_item(def_id).ident
2049             ),
2050             infer::EarlyBoundRegion(_, name) => format!(" for lifetime parameter `{}`", name),
2051             infer::BoundRegionInCoherence(name) => {
2052                 format!(" for lifetime parameter `{}` in coherence check", name)
2053             }
2054             infer::UpvarRegion(ref upvar_id, _) => {
2055                 let var_name = self.tcx.hir().name(upvar_id.var_path.hir_id);
2056                 format!(" for capture of `{}` by closure", var_name)
2057             }
2058             infer::NLL(..) => bug!("NLL variable found in lexical phase"),
2059         };
2060
2061         struct_span_err!(
2062             self.tcx.sess,
2063             var_origin.span(),
2064             E0495,
2065             "cannot infer an appropriate lifetime{} \
2066              due to conflicting requirements",
2067             var_description
2068         )
2069     }
2070 }
2071
2072 enum FailureCode {
2073     Error0038(DefId),
2074     Error0317(&'static str),
2075     Error0580(&'static str),
2076     Error0308(&'static str),
2077     Error0644(&'static str),
2078 }
2079
2080 trait ObligationCauseExt<'tcx> {
2081     fn as_failure_code(&self, terr: &TypeError<'tcx>) -> FailureCode;
2082     fn as_requirement_str(&self) -> &'static str;
2083 }
2084
2085 impl<'tcx> ObligationCauseExt<'tcx> for ObligationCause<'tcx> {
2086     fn as_failure_code(&self, terr: &TypeError<'tcx>) -> FailureCode {
2087         use self::FailureCode::*;
2088         use crate::traits::ObligationCauseCode::*;
2089         match self.code {
2090             CompareImplMethodObligation { .. } => Error0308("method not compatible with trait"),
2091             CompareImplTypeObligation { .. } => Error0308("type not compatible with trait"),
2092             MatchExpressionArm(box MatchExpressionArmCause { source, .. }) => {
2093                 Error0308(match source {
2094                     hir::MatchSource::IfLetDesugar { .. } => {
2095                         "`if let` arms have incompatible types"
2096                     }
2097                     hir::MatchSource::TryDesugar => {
2098                         "try expression alternatives have incompatible types"
2099                     }
2100                     _ => "`match` arms have incompatible types",
2101                 })
2102             }
2103             IfExpression { .. } => Error0308("`if` and `else` have incompatible types"),
2104             IfExpressionWithNoElse => Error0317("`if` may be missing an `else` clause"),
2105             MainFunctionType => Error0580("`main` function has wrong type"),
2106             StartFunctionType => Error0308("`#[start]` function has wrong type"),
2107             IntrinsicType => Error0308("intrinsic has wrong type"),
2108             MethodReceiver => Error0308("mismatched `self` parameter type"),
2109
2110             // In the case where we have no more specific thing to
2111             // say, also take a look at the error code, maybe we can
2112             // tailor to that.
2113             _ => match terr {
2114                 TypeError::CyclicTy(ty) if ty.is_closure() || ty.is_generator() => {
2115                     Error0644("closure/generator type that references itself")
2116                 }
2117                 TypeError::IntrinsicCast => {
2118                     Error0308("cannot coerce intrinsics to function pointers")
2119                 }
2120                 TypeError::ObjectUnsafeCoercion(did) => Error0038(*did),
2121                 _ => Error0308("mismatched types"),
2122             },
2123         }
2124     }
2125
2126     fn as_requirement_str(&self) -> &'static str {
2127         use crate::traits::ObligationCauseCode::*;
2128         match self.code {
2129             CompareImplMethodObligation { .. } => "method type is compatible with trait",
2130             CompareImplTypeObligation { .. } => "associated type is compatible with trait",
2131             ExprAssignable => "expression is assignable",
2132             MatchExpressionArm(box MatchExpressionArmCause { source, .. }) => match source {
2133                 hir::MatchSource::IfLetDesugar { .. } => "`if let` arms have compatible types",
2134                 _ => "`match` arms have compatible types",
2135             },
2136             IfExpression { .. } => "`if` and `else` have incompatible types",
2137             IfExpressionWithNoElse => "`if` missing an `else` returns `()`",
2138             MainFunctionType => "`main` function has the correct type",
2139             StartFunctionType => "`#[start]` function has the correct type",
2140             IntrinsicType => "intrinsic has the correct type",
2141             MethodReceiver => "method receiver has the correct type",
2142             _ => "types are compatible",
2143         }
2144     }
2145 }
2146
2147 /// This is a bare signal of what kind of type we're dealing with. `ty::TyKind` tracks
2148 /// extra information about each type, but we only care about the category.
2149 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
2150 pub enum TyCategory {
2151     Closure,
2152     Opaque,
2153     Generator,
2154     Foreign,
2155 }
2156
2157 impl TyCategory {
2158     fn descr(&self) -> &'static str {
2159         match self {
2160             Self::Closure => "closure",
2161             Self::Opaque => "opaque type",
2162             Self::Generator => "generator",
2163             Self::Foreign => "foreign type",
2164         }
2165     }
2166
2167     pub fn from_ty(ty: Ty<'_>) -> Option<(Self, DefId)> {
2168         match ty.kind {
2169             ty::Closure(def_id, _) => Some((Self::Closure, def_id)),
2170             ty::Opaque(def_id, _) => Some((Self::Opaque, def_id)),
2171             ty::Generator(def_id, ..) => Some((Self::Generator, def_id)),
2172             ty::Foreign(def_id) => Some((Self::Foreign, def_id)),
2173             _ => None,
2174         }
2175     }
2176 }