src/librustc/traits/error_reporting.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use super::{
  12     FulfillmentError,
  13     FulfillmentErrorCode,
  14     MismatchedProjectionTypes,
  15     Obligation,
  16     ObligationCause,
  17     ObligationCauseCode,
  18     OutputTypeParameterMismatch,
  19     TraitNotObjectSafe,
  20     PredicateObligation,
  21     SelectionContext,
  22     SelectionError,
  23     ObjectSafetyViolation,
  24 };
  25
  26 use errors::DiagnosticBuilder;
  27 use fmt_macros::{Parser, Piece, Position};
  28 use hir::{self, intravisit, Local, Pat, Body};
  29 use hir::intravisit::{Visitor, NestedVisitorMap};
  30 use hir::map::NodeExpr;
  31 use hir::def_id::DefId;
  32 use infer::{self, InferCtxt};
  33 use infer::type_variable::TypeVariableOrigin;
  34 use rustc::lint::builtin::EXTRA_REQUIREMENT_IN_IMPL;
  35 use std::fmt;
  36 use syntax::ast::{self, NodeId};
  37 use ty::{self, AdtKind, ToPredicate, ToPolyTraitRef, Ty, TyCtxt, TypeFoldable, TyInfer, TyVar};
  38 use ty::error::{ExpectedFound, TypeError};
  39 use ty::fast_reject;
  40 use ty::fold::TypeFolder;
  41 use ty::subst::Subst;
  42 use ty::SubtypePredicate;
  43 use util::nodemap::{FxHashMap, FxHashSet};
  44
  45 use syntax_pos::{DUMMY_SP, Span};
  46
  47
  48 #[derive(Debug, PartialEq, Eq, Hash)]
  49 pub struct TraitErrorKey<'tcx> {
  50     span: Span,
  51     predicate: ty::Predicate<'tcx>
  52 }
  53
  54 impl<'a, 'gcx, 'tcx> TraitErrorKey<'tcx> {
  55     fn from_error(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
  56                   e: &FulfillmentError<'tcx>) -> Self {
  57         let predicate =
  58             infcx.resolve_type_vars_if_possible(&e.obligation.predicate);
  59         TraitErrorKey {
  60             span: e.obligation.cause.span,
  61             predicate: infcx.tcx.erase_regions(&predicate)
  62         }
  63     }
  64 }
  65
  66 struct FindLocalByTypeVisitor<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
  67     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
  68     target_ty: &'a Ty<'tcx>,
  69     hir_map: &'a hir::map::Map<'gcx>,
  70     found_local_pattern: Option<&'gcx Pat>,
  71     found_arg_pattern: Option<&'gcx Pat>,
  72 }
  73
  74 impl<'a, 'gcx, 'tcx> FindLocalByTypeVisitor<'a, 'gcx, 'tcx> {
  75     fn node_matches_type(&mut self, node_id: &'gcx NodeId) -> bool {
  76         match self.infcx.tables.borrow().node_types.get(node_id) {
  77             Some(&ty) => {
  78                 let ty = self.infcx.resolve_type_vars_if_possible(&ty);
  79                 ty.walk().any(|inner_ty| {
  80                     inner_ty == *self.target_ty || match (&inner_ty.sty, &self.target_ty.sty) {
  81                         (&TyInfer(TyVar(a_vid)), &TyInfer(TyVar(b_vid))) => {
  82                             self.infcx
  83                                 .type_variables
  84                                 .borrow_mut()
  85                                 .sub_unified(a_vid, b_vid)
  86                         }
  87                         _ => false,
  88                     }
  89                 })
  90             }
  91             _ => false,
  92         }
  93     }
  94 }
  95
  96 impl<'a, 'gcx, 'tcx> Visitor<'gcx> for FindLocalByTypeVisitor<'a, 'gcx, 'tcx> {
  97     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'gcx> {
  98         NestedVisitorMap::OnlyBodies(&self.hir_map)
  99     }
 100
 101     fn visit_local(&mut self, local: &'gcx Local) {
 102         if self.found_local_pattern.is_none() && self.node_matches_type(&local.id) {
 103             self.found_local_pattern = Some(&*local.pat);
 104         }
 105         intravisit::walk_local(self, local);
 106     }
 107
 108     fn visit_body(&mut self, body: &'gcx Body) {
 109         for argument in &body.arguments {
 110             if self.found_arg_pattern.is_none() && self.node_matches_type(&argument.id) {
 111                 self.found_arg_pattern = Some(&*argument.pat);
 112             }
 113         }
 114         intravisit::walk_body(self, body);
 115     }
 116 }
 117
 118 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 119     pub fn report_fulfillment_errors(&self, errors: &Vec<FulfillmentError<'tcx>>) {
 120         for error in errors {
 121             self.report_fulfillment_error(error);
 122         }
 123     }
 124
 125     fn report_fulfillment_error(&self,
 126                                 error: &FulfillmentError<'tcx>) {
 127         let error_key = TraitErrorKey::from_error(self, error);
 128         debug!("report_fulfillment_errors({:?}) - key={:?}",
 129                error, error_key);
 130         if !self.reported_trait_errors.borrow_mut().insert(error_key) {
 131             debug!("report_fulfillment_errors: skipping duplicate");
 132             return;
 133         }
 134         match error.code {
 135             FulfillmentErrorCode::CodeSelectionError(ref e) => {
 136                 self.report_selection_error(&error.obligation, e);
 137             }
 138             FulfillmentErrorCode::CodeProjectionError(ref e) => {
 139                 self.report_projection_error(&error.obligation, e);
 140             }
 141             FulfillmentErrorCode::CodeAmbiguity => {
 142                 self.maybe_report_ambiguity(&error.obligation);
 143             }
 144             FulfillmentErrorCode::CodeSubtypeError(ref expected_found, ref err) => {
 145                 self.report_mismatched_types(&error.obligation.cause,
 146                                              expected_found.expected,
 147                                              expected_found.found,
 148                                              err.clone())
 149                     .emit();
 150             }
 151         }
 152     }
 153
 154     fn report_projection_error(&self,
 155                                obligation: &PredicateObligation<'tcx>,
 156                                error: &MismatchedProjectionTypes<'tcx>)
 157     {
 158         let predicate =
 159             self.resolve_type_vars_if_possible(&obligation.predicate);
 160
 161         if predicate.references_error() {
 162             return
 163         }
 164
 165         self.probe(|_| {
 166             let err_buf;
 167             let mut err = &error.err;
 168             let mut values = None;
 169
 170             // try to find the mismatched types to report the error with.
 171             //
 172             // this can fail if the problem was higher-ranked, in which
 173             // cause I have no idea for a good error message.
 174             if let ty::Predicate::Projection(ref data) = predicate {
 175                 let mut selcx = SelectionContext::new(self);
 176                 let (data, _) = self.replace_late_bound_regions_with_fresh_var(
 177                     obligation.cause.span,
 178                     infer::LateBoundRegionConversionTime::HigherRankedType,
 179                     data);
 180                 let normalized = super::normalize_projection_type(
 181                     &mut selcx,
 182                     data.projection_ty,
 183                     obligation.cause.clone(),
 184                     0
 185                 );
 186                 if let Err(error) = self.eq_types(
 187                     false, &obligation.cause,
 188                     data.ty, normalized.value
 189                 ) {
 190                     values = Some(infer::ValuePairs::Types(ExpectedFound {
 191                         expected: normalized.value,
 192                         found: data.ty,
 193                     }));
 194                     err_buf = error;
 195                     err = &err_buf;
 196                 }
 197             }
 198
 199             let mut diag = struct_span_err!(
 200                 self.tcx.sess, obligation.cause.span, E0271,
 201                 "type mismatch resolving `{}`", predicate
 202             );
 203             self.note_type_err(&mut diag, &obligation.cause, None, values, err);
 204             self.note_obligation_cause(&mut diag, obligation);
 205             diag.emit();
 206         });
 207     }
 208
 209     fn fuzzy_match_tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
 210         /// returns the fuzzy category of a given type, or None
 211         /// if the type can be equated to any type.
 212         fn type_category<'tcx>(t: Ty<'tcx>) -> Option<u32> {
 213             match t.sty {
 214                 ty::TyBool => Some(0),
 215                 ty::TyChar => Some(1),
 216                 ty::TyStr => Some(2),
 217                 ty::TyInt(..) | ty::TyUint(..) | ty::TyInfer(ty::IntVar(..)) => Some(3),
 218                 ty::TyFloat(..) | ty::TyInfer(ty::FloatVar(..)) => Some(4),
 219                 ty::TyRef(..) | ty::TyRawPtr(..) => Some(5),
 220                 ty::TyArray(..) | ty::TySlice(..) => Some(6),
 221                 ty::TyFnDef(..) | ty::TyFnPtr(..) => Some(7),
 222                 ty::TyDynamic(..) => Some(8),
 223                 ty::TyClosure(..) => Some(9),
 224                 ty::TyTuple(..) => Some(10),
 225                 ty::TyProjection(..) => Some(11),
 226                 ty::TyParam(..) => Some(12),
 227                 ty::TyAnon(..) => Some(13),
 228                 ty::TyNever => Some(14),
 229                 ty::TyAdt(adt, ..) => match adt.adt_kind() {
 230                     AdtKind::Struct => Some(15),
 231                     AdtKind::Union => Some(16),
 232                     AdtKind::Enum => Some(17),
 233                 },
 234                 ty::TyInfer(..) | ty::TyError => None
 235             }
 236         }
 237
 238         match (type_category(a), type_category(b)) {
 239             (Some(cat_a), Some(cat_b)) => match (&a.sty, &b.sty) {
 240                 (&ty::TyAdt(def_a, _), &ty::TyAdt(def_b, _)) => def_a == def_b,
 241                 _ => cat_a == cat_b
 242             },
 243             // infer and error can be equated to all types
 244             _ => true
 245         }
 246     }
 247
 248     fn impl_similar_to(&self,
 249                        trait_ref: ty::PolyTraitRef<'tcx>,
 250                        obligation: &PredicateObligation<'tcx>)
 251                        -> Option<DefId>
 252     {
 253         let tcx = self.tcx;
 254
 255         let trait_ref = tcx.erase_late_bound_regions(&trait_ref);
 256         let trait_self_ty = trait_ref.self_ty();
 257
 258         let mut self_match_impls = vec![];
 259         let mut fuzzy_match_impls = vec![];
 260
 261         self.tcx.trait_def(trait_ref.def_id)
 262             .for_each_relevant_impl(self.tcx, trait_self_ty, |def_id| {
 263                 let impl_substs = self.fresh_substs_for_item(obligation.cause.span, def_id);
 264                 let impl_trait_ref = tcx
 265                     .impl_trait_ref(def_id)
 266                     .unwrap()
 267                     .subst(tcx, impl_substs);
 268
 269                 let impl_self_ty = impl_trait_ref.self_ty();
 270
 271                 if let Ok(..) = self.can_equate(&trait_self_ty, &impl_self_ty) {
 272                     self_match_impls.push(def_id);
 273
 274                     if trait_ref.substs.types().skip(1)
 275                         .zip(impl_trait_ref.substs.types().skip(1))
 276                         .all(|(u,v)| self.fuzzy_match_tys(u, v))
 277                     {
 278                         fuzzy_match_impls.push(def_id);
 279                     }
 280                 }
 281             });
 282
 283         let impl_def_id = if self_match_impls.len() == 1 {
 284             self_match_impls[0]
 285         } else if fuzzy_match_impls.len() == 1 {
 286             fuzzy_match_impls[0]
 287         } else {
 288             return None
 289         };
 290
 291         if tcx.has_attr(impl_def_id, "rustc_on_unimplemented") {
 292             Some(impl_def_id)
 293         } else {
 294             None
 295         }
 296     }
 297
 298     fn on_unimplemented_note(&self,
 299                              trait_ref: ty::PolyTraitRef<'tcx>,
 300                              obligation: &PredicateObligation<'tcx>) -> Option<String> {
 301         let def_id = self.impl_similar_to(trait_ref, obligation)
 302             .unwrap_or(trait_ref.def_id());
 303         let trait_ref = trait_ref.skip_binder();
 304
 305         let span = obligation.cause.span;
 306         let mut report = None;
 307         if let Some(item) = self.tcx
 308             .get_attrs(def_id)
 309             .into_iter()
 310             .filter(|a| a.check_name("rustc_on_unimplemented"))
 311             .next()
 312         {
 313             let err_sp = item.span.substitute_dummy(span);
 314             let trait_str = self.tcx.item_path_str(trait_ref.def_id);
 315             if let Some(istring) = item.value_str() {
 316                 let istring = &*istring.as_str();
 317                 let generics = self.tcx.generics_of(trait_ref.def_id);
 318                 let generic_map = generics.types.iter().map(|param| {
 319                     (param.name.as_str().to_string(),
 320                         trait_ref.substs.type_for_def(param).to_string())
 321                 }).collect::<FxHashMap<String, String>>();
 322                 let parser = Parser::new(istring);
 323                 let mut errored = false;
 324                 let err: String = parser.filter_map(|p| {
 325                     match p {
 326                         Piece::String(s) => Some(s),
 327                         Piece::NextArgument(a) => match a.position {
 328                             Position::ArgumentNamed(s) => match generic_map.get(s) {
 329                                 Some(val) => Some(val),
 330                                 None => {
 331                                     span_err!(self.tcx.sess, err_sp, E0272,
 332                                               "the #[rustc_on_unimplemented] attribute on trait \
 333                                                definition for {} refers to non-existent type \
 334                                                parameter {}",
 335                                               trait_str, s);
 336                                     errored = true;
 337                                     None
 338                                 }
 339                             },
 340                             _ => {
 341                                 span_err!(self.tcx.sess, err_sp, E0273,
 342                                           "the #[rustc_on_unimplemented] attribute on trait \
 343                                            definition for {} must have named format arguments, eg \
 344                                            `#[rustc_on_unimplemented = \"foo {{T}}\"]`",
 345                                           trait_str);
 346                                 errored = true;
 347                                 None
 348                             }
 349                         }
 350                     }
 351                 }).collect();
 352                 // Report only if the format string checks out
 353                 if !errored {
 354                     report = Some(err);
 355                 }
 356             } else {
 357                 span_err!(self.tcx.sess, err_sp, E0274,
 358                                         "the #[rustc_on_unimplemented] attribute on \
 359                                                     trait definition for {} must have a value, \
 360                                                     eg `#[rustc_on_unimplemented = \"foo\"]`",
 361                                                     trait_str);
 362             }
 363         }
 364         report
 365     }
 366
 367     fn find_similar_impl_candidates(&self,
 368                                     trait_ref: ty::PolyTraitRef<'tcx>)
 369                                     -> Vec<ty::TraitRef<'tcx>>
 370     {
 371         let simp = fast_reject::simplify_type(self.tcx,
 372                                               trait_ref.skip_binder().self_ty(),
 373                                               true);
 374         let mut impl_candidates = Vec::new();
 375         let trait_def = self.tcx.trait_def(trait_ref.def_id());
 376
 377         match simp {
 378             Some(simp) => trait_def.for_each_impl(self.tcx, |def_id| {
 379                 let imp = self.tcx.impl_trait_ref(def_id).unwrap();
 380                 let imp_simp = fast_reject::simplify_type(self.tcx,
 381                                                           imp.self_ty(),
 382                                                           true);
 383                 if let Some(imp_simp) = imp_simp {
 384                     if simp != imp_simp {
 385                         return;
 386                     }
 387                 }
 388                 impl_candidates.push(imp);
 389             }),
 390             None => trait_def.for_each_impl(self.tcx, |def_id| {
 391                 impl_candidates.push(
 392                     self.tcx.impl_trait_ref(def_id).unwrap());
 393             })
 394         };
 395         impl_candidates
 396     }
 397
 398     fn report_similar_impl_candidates(&self,
 399                                       impl_candidates: Vec<ty::TraitRef<'tcx>>,
 400                                       err: &mut DiagnosticBuilder)
 401     {
 402         if impl_candidates.is_empty() {
 403             return;
 404         }
 405
 406         let end = if impl_candidates.len() <= 5 {
 407             impl_candidates.len()
 408         } else {
 409             4
 410         };
 411         err.help(&format!("the following implementations were found:{}{}",
 412                           &impl_candidates[0..end].iter().map(|candidate| {
 413                               format!("\n  {:?}", candidate)
 414                           }).collect::<String>(),
 415                           if impl_candidates.len() > 5 {
 416                               format!("\nand {} others", impl_candidates.len() - 4)
 417                           } else {
 418                               "".to_owned()
 419                           }
 420                           ));
 421     }
 422
 423     /// Reports that an overflow has occurred and halts compilation. We
 424     /// halt compilation unconditionally because it is important that
 425     /// overflows never be masked -- they basically represent computations
 426     /// whose result could not be truly determined and thus we can't say
 427     /// if the program type checks or not -- and they are unusual
 428     /// occurrences in any case.
 429     pub fn report_overflow_error<T>(&self,
 430                                     obligation: &Obligation<'tcx, T>,
 431                                     suggest_increasing_limit: bool) -> !
 432         where T: fmt::Display + TypeFoldable<'tcx>
 433     {
 434         let predicate =
 435             self.resolve_type_vars_if_possible(&obligation.predicate);
 436         let mut err = struct_span_err!(self.tcx.sess, obligation.cause.span, E0275,
 437                                        "overflow evaluating the requirement `{}`",
 438                                        predicate);
 439
 440         if suggest_increasing_limit {
 441             self.suggest_new_overflow_limit(&mut err);
 442         }
 443
 444         self.note_obligation_cause(&mut err, obligation);
 445
 446         err.emit();
 447         self.tcx.sess.abort_if_errors();
 448         bug!();
 449     }
 450
 451     /// Reports that a cycle was detected which led to overflow and halts
 452     /// compilation. This is equivalent to `report_overflow_error` except
 453     /// that we can give a more helpful error message (and, in particular,
 454     /// we do not suggest increasing the overflow limit, which is not
 455     /// going to help).
 456     pub fn report_overflow_error_cycle(&self, cycle: &[PredicateObligation<'tcx>]) -> ! {
 457         let cycle = self.resolve_type_vars_if_possible(&cycle.to_owned());
 458         assert!(cycle.len() > 0);
 459
 460         debug!("report_overflow_error_cycle: cycle={:?}", cycle);
 461
 462         self.report_overflow_error(&cycle[0], false);
 463     }
 464
 465     pub fn report_extra_impl_obligation(&self,
 466                                         error_span: Span,
 467                                         item_name: ast::Name,
 468                                         _impl_item_def_id: DefId,
 469                                         trait_item_def_id: DefId,
 470                                         requirement: &fmt::Display,
 471                                         lint_id: Option<ast::NodeId>) // (*)
 472                                         -> DiagnosticBuilder<'tcx>
 473     {
 474         // (*) This parameter is temporary and used only for phasing
 475         // in the bug fix to #18937. If it is `Some`, it has a kind of
 476         // weird effect -- the diagnostic is reported as a lint, and
 477         // the builder which is returned is marked as canceled.
 478
 479         let mut err =
 480             struct_span_err!(self.tcx.sess,
 481                              error_span,
 482                              E0276,
 483                              "impl has stricter requirements than trait");
 484
 485         if let Some(trait_item_span) = self.tcx.hir.span_if_local(trait_item_def_id) {
 486             let span = self.tcx.sess.codemap().def_span(trait_item_span);
 487             err.span_label(span, &format!("definition of `{}` from trait", item_name));
 488         }
 489
 490         err.span_label(
 491             error_span,
 492             &format!("impl has extra requirement {}", requirement));
 493
 494         if let Some(node_id) = lint_id {
 495             self.tcx.sess.add_lint_diagnostic(EXTRA_REQUIREMENT_IN_IMPL,
 496                                               node_id,
 497                                               (*err).clone());
 498             err.cancel();
 499         }
 500
 501         err
 502     }
 503
 504
 505     /// Get the parent trait chain start
 506     fn get_parent_trait_ref(&self, code: &ObligationCauseCode<'tcx>) -> Option<String> {
 507         match code {
 508             &ObligationCauseCode::BuiltinDerivedObligation(ref data) => {
 509                 let parent_trait_ref = self.resolve_type_vars_if_possible(
 510                     &data.parent_trait_ref);
 511                 match self.get_parent_trait_ref(&data.parent_code) {
 512                     Some(t) => Some(t),
 513                     None => Some(format!("{}", parent_trait_ref.0.self_ty())),
 514                 }
 515             }
 516             _ => None,
 517         }
 518     }
 519
 520     pub fn report_selection_error(&self,
 521                                   obligation: &PredicateObligation<'tcx>,
 522                                   error: &SelectionError<'tcx>)
 523     {
 524         let span = obligation.cause.span;
 525
 526         let mut err = match *error {
 527             SelectionError::Unimplemented => {
 528                 if let ObligationCauseCode::CompareImplMethodObligation {
 529                     item_name, impl_item_def_id, trait_item_def_id, lint_id
 530                 } = obligation.cause.code {
 531                     self.report_extra_impl_obligation(
 532                         span,
 533                         item_name,
 534                         impl_item_def_id,
 535                         trait_item_def_id,
 536                         &format!("`{}`", obligation.predicate),
 537                         lint_id)
 538                         .emit();
 539                     return;
 540                 }
 541                 match obligation.predicate {
 542                     ty::Predicate::Trait(ref trait_predicate) => {
 543                         let trait_predicate =
 544                             self.resolve_type_vars_if_possible(trait_predicate);
 545
 546                         if self.tcx.sess.has_errors() && trait_predicate.references_error() {
 547                             return;
 548                         }
 549                         let trait_ref = trait_predicate.to_poly_trait_ref();
 550                         let (post_message, pre_message) =
 551                             self.get_parent_trait_ref(&obligation.cause.code)
 552                                 .map(|t| (format!(" in `{}`", t), format!("within `{}`, ", t)))
 553                                 .unwrap_or((String::new(), String::new()));
 554                         let mut err = struct_span_err!(
 555                             self.tcx.sess,
 556                             span,
 557                             E0277,
 558                             "the trait bound `{}` is not satisfied{}",
 559                             trait_ref.to_predicate(),
 560                             post_message);
 561
 562                         // Try to report a help message
 563                         if !trait_ref.has_infer_types() &&
 564                             self.predicate_can_apply(trait_ref) {
 565                             // If a where-clause may be useful, remind the
 566                             // user that they can add it.
 567                             //
 568                             // don't display an on-unimplemented note, as
 569                             // these notes will often be of the form
 570                             //     "the type `T` can't be frobnicated"
 571                             // which is somewhat confusing.
 572                             err.help(&format!("consider adding a `where {}` bound",
 573                                                 trait_ref.to_predicate()));
 574                         } else if let Some(s) = self.on_unimplemented_note(trait_ref, obligation) {
 575                             // If it has a custom "#[rustc_on_unimplemented]"
 576                             // error message, let's display it!
 577                             err.note(&s);
 578                         } else {
 579                             // Can't show anything else useful, try to find similar impls.
 580                             let impl_candidates = self.find_similar_impl_candidates(trait_ref);
 581                             self.report_similar_impl_candidates(impl_candidates, &mut err);
 582                         }
 583
 584                         err.span_label(span,
 585                                        &format!("{}the trait `{}` is not implemented for `{}`",
 586                                                 pre_message,
 587                                                 trait_ref,
 588                                                 trait_ref.self_ty()));
 589                         err
 590                     }
 591
 592                     ty::Predicate::Subtype(ref predicate) => {
 593                         // Errors for Subtype predicates show up as
 594                         // `FulfillmentErrorCode::CodeSubtypeError`,
 595                         // not selection error.
 596                         span_bug!(span, "subtype requirement gave wrong error: `{:?}`", predicate)
 597                     }
 598
 599                     ty::Predicate::Equate(ref predicate) => {
 600                         let predicate = self.resolve_type_vars_if_possible(predicate);
 601                         let err = self.equality_predicate(&obligation.cause,
 602                                                             &predicate).err().unwrap();
 603                         struct_span_err!(self.tcx.sess, span, E0278,
 604                             "the requirement `{}` is not satisfied (`{}`)",
 605                             predicate, err)
 606                     }
 607
 608                     ty::Predicate::RegionOutlives(ref predicate) => {
 609                         let predicate = self.resolve_type_vars_if_possible(predicate);
 610                         let err = self.region_outlives_predicate(&obligation.cause,
 611                                                                     &predicate).err().unwrap();
 612                         struct_span_err!(self.tcx.sess, span, E0279,
 613                             "the requirement `{}` is not satisfied (`{}`)",
 614                             predicate, err)
 615                     }
 616
 617                     ty::Predicate::Projection(..) | ty::Predicate::TypeOutlives(..) => {
 618                         let predicate =
 619                             self.resolve_type_vars_if_possible(&obligation.predicate);
 620                         struct_span_err!(self.tcx.sess, span, E0280,
 621                             "the requirement `{}` is not satisfied",
 622                             predicate)
 623                     }
 624
 625                     ty::Predicate::ObjectSafe(trait_def_id) => {
 626                         let violations = self.tcx.object_safety_violations(trait_def_id);
 627                         self.tcx.report_object_safety_error(span,
 628                                                             trait_def_id,
 629                                                             violations)
 630                     }
 631
 632                     ty::Predicate::ClosureKind(closure_def_id, kind) => {
 633                         let found_kind = self.closure_kind(closure_def_id).unwrap();
 634                         let closure_span = self.tcx.hir.span_if_local(closure_def_id).unwrap();
 635                         let mut err = struct_span_err!(
 636                             self.tcx.sess, closure_span, E0525,
 637                             "expected a closure that implements the `{}` trait, \
 638                                 but this closure only implements `{}`",
 639                             kind,
 640                             found_kind);
 641                         err.span_note(
 642                             obligation.cause.span,
 643                             &format!("the requirement to implement \
 644                                         `{}` derives from here", kind));
 645                         err.emit();
 646                         return;
 647                     }
 648
 649                     ty::Predicate::WellFormed(ty) => {
 650                         // WF predicates cannot themselves make
 651                         // errors. They can only block due to
 652                         // ambiguity; otherwise, they always
 653                         // degenerate into other obligations
 654                         // (which may fail).
 655                         span_bug!(span, "WF predicate not satisfied for {:?}", ty);
 656                     }
 657                 }
 658             }
 659
 660             OutputTypeParameterMismatch(ref expected_trait_ref, ref actual_trait_ref, ref e) => {
 661                 let expected_trait_ref = self.resolve_type_vars_if_possible(&*expected_trait_ref);
 662                 let actual_trait_ref = self.resolve_type_vars_if_possible(&*actual_trait_ref);
 663                 if actual_trait_ref.self_ty().references_error() {
 664                     return;
 665                 }
 666                 let expected_trait_ty = expected_trait_ref.self_ty();
 667                 let found_span = expected_trait_ty.ty_to_def_id().and_then(|did| {
 668                     self.tcx.hir.span_if_local(did)
 669                 });
 670
 671                 if let &TypeError::TupleSize(ref expected_found) = e {
 672                     // Expected `|x| { }`, found `|x, y| { }`
 673                     self.report_arg_count_mismatch(span,
 674                                                    found_span,
 675                                                    expected_found.expected,
 676                                                    expected_found.found,
 677                                                    expected_trait_ty.is_closure())
 678                 } else if let &TypeError::Sorts(ref expected_found) = e {
 679                     let expected = if let ty::TyTuple(tys, _) = expected_found.expected.sty {
 680                         tys.len()
 681                     } else {
 682                         1
 683                     };
 684                     let found = if let ty::TyTuple(tys, _) = expected_found.found.sty {
 685                         tys.len()
 686                     } else {
 687                         1
 688                     };
 689
 690                     if expected != found {
 691                         // Expected `|| { }`, found `|x, y| { }`
 692                         // Expected `fn(x) -> ()`, found `|| { }`
 693                         self.report_arg_count_mismatch(span,
 694                                                        found_span,
 695                                                        expected,
 696                                                        found,
 697                                                        expected_trait_ty.is_closure())
 698                     } else {
 699                         self.report_type_argument_mismatch(span,
 700                                                             found_span,
 701                                                             expected_trait_ty,
 702                                                             expected_trait_ref,
 703                                                             actual_trait_ref,
 704                                                             e)
 705                     }
 706                 } else {
 707                     self.report_type_argument_mismatch(span,
 708                                                         found_span,
 709                                                         expected_trait_ty,
 710                                                         expected_trait_ref,
 711                                                         actual_trait_ref,
 712                                                         e)
 713                 }
 714             }
 715
 716             TraitNotObjectSafe(did) => {
 717                 let violations = self.tcx.object_safety_violations(did);
 718                 self.tcx.report_object_safety_error(span, did,
 719                                                     violations)
 720             }
 721         };
 722         self.note_obligation_cause(&mut err, obligation);
 723         err.emit();
 724     }
 725
 726     fn report_type_argument_mismatch(&self,
 727                                       span: Span,
 728                                       found_span: Option<Span>,
 729                                       expected_ty: Ty<'tcx>,
 730                                       expected_ref: ty::PolyTraitRef<'tcx>,
 731                                       found_ref: ty::PolyTraitRef<'tcx>,
 732                                       type_error: &TypeError<'tcx>)
 733         -> DiagnosticBuilder<'tcx>
 734     {
 735         let mut err = struct_span_err!(self.tcx.sess, span, E0281,
 736             "type mismatch: `{}` implements the trait `{}`, but the trait `{}` is required",
 737             expected_ty,
 738             expected_ref,
 739             found_ref);
 740
 741         err.span_label(span, &format!("{}", type_error));
 742
 743         if let Some(sp) = found_span {
 744             err.span_label(span, &format!("requires `{}`", found_ref));
 745             err.span_label(sp, &format!("implements `{}`", expected_ref));
 746         }
 747
 748         err
 749     }
 750
 751     fn report_arg_count_mismatch(&self,
 752                                  span: Span,
 753                                  found_span: Option<Span>,
 754                                  expected: usize,
 755                                  found: usize,
 756                                  is_closure: bool)
 757         -> DiagnosticBuilder<'tcx>
 758     {
 759         let mut err = struct_span_err!(self.tcx.sess, span, E0593,
 760             "{} takes {} argument{} but {} argument{} {} required",
 761             if is_closure { "closure" } else { "function" },
 762             found,
 763             if found == 1 { "" } else { "s" },
 764             expected,
 765             if expected == 1 { "" } else { "s" },
 766             if expected == 1 { "is" } else { "are" });
 767
 768         err.span_label(span, &format!("expected {} that takes {} argument{}",
 769                                       if is_closure { "closure" } else { "function" },
 770                                       expected,
 771                                       if expected == 1 { "" } else { "s" }));
 772         if let Some(span) = found_span {
 773             err.span_label(span, &format!("takes {} argument{}",
 774                                           found,
 775                                           if found == 1 { "" } else { "s" }));
 776         }
 777         err
 778     }
 779 }
 780
 781 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 782     pub fn recursive_type_with_infinite_size_error(self,
 783                                                    type_def_id: DefId)
 784                                                    -> DiagnosticBuilder<'tcx>
 785     {
 786         assert!(type_def_id.is_local());
 787         let span = self.hir.span_if_local(type_def_id).unwrap();
 788         let span = self.sess.codemap().def_span(span);
 789         let mut err = struct_span_err!(self.sess, span, E0072,
 790                                        "recursive type `{}` has infinite size",
 791                                        self.item_path_str(type_def_id));
 792         err.span_label(span, &format!("recursive type has infinite size"));
 793         err.help(&format!("insert indirection (e.g., a `Box`, `Rc`, or `&`) \
 794                            at some point to make `{}` representable",
 795                           self.item_path_str(type_def_id)));
 796         err
 797     }
 798
 799     pub fn report_object_safety_error(self,
 800                                       span: Span,
 801                                       trait_def_id: DefId,
 802                                       violations: Vec<ObjectSafetyViolation>)
 803                                       -> DiagnosticBuilder<'tcx>
 804     {
 805         let trait_str = self.item_path_str(trait_def_id);
 806         let span = self.sess.codemap().def_span(span);
 807         let mut err = struct_span_err!(
 808             self.sess, span, E0038,
 809             "the trait `{}` cannot be made into an object",
 810             trait_str);
 811         err.span_label(span, &format!("the trait `{}` cannot be made into an object", trait_str));
 812
 813         let mut reported_violations = FxHashSet();
 814         for violation in violations {
 815             if !reported_violations.insert(violation.clone()) {
 816                 continue;
 817             }
 818             err.note(&violation.error_msg());
 819         }
 820         err
 821     }
 822 }
 823
 824 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 825     fn maybe_report_ambiguity(&self, obligation: &PredicateObligation<'tcx>) {
 826         // Unable to successfully determine, probably means
 827         // insufficient type information, but could mean
 828         // ambiguous impls. The latter *ought* to be a
 829         // coherence violation, so we don't report it here.
 830
 831         let predicate = self.resolve_type_vars_if_possible(&obligation.predicate);
 832         let body_id = hir::BodyId { node_id: obligation.cause.body_id };
 833         let span = obligation.cause.span;
 834
 835         debug!("maybe_report_ambiguity(predicate={:?}, obligation={:?})",
 836                predicate,
 837                obligation);
 838
 839         // Ambiguity errors are often caused as fallout from earlier
 840         // errors. So just ignore them if this infcx is tainted.
 841         if self.is_tainted_by_errors() {
 842             return;
 843         }
 844
 845         match predicate {
 846             ty::Predicate::Trait(ref data) => {
 847                 let trait_ref = data.to_poly_trait_ref();
 848                 let self_ty = trait_ref.self_ty();
 849                 if predicate.references_error() {
 850                     return;
 851                 }
 852                 // Typically, this ambiguity should only happen if
 853                 // there are unresolved type inference variables
 854                 // (otherwise it would suggest a coherence
 855                 // failure). But given #21974 that is not necessarily
 856                 // the case -- we can have multiple where clauses that
 857                 // are only distinguished by a region, which results
 858                 // in an ambiguity even when all types are fully
 859                 // known, since we don't dispatch based on region
 860                 // relationships.
 861
 862                 // This is kind of a hack: it frequently happens that some earlier
 863                 // error prevents types from being fully inferred, and then we get
 864                 // a bunch of uninteresting errors saying something like "<generic
 865                 // #0> doesn't implement Sized".  It may even be true that we
 866                 // could just skip over all checks where the self-ty is an
 867                 // inference variable, but I was afraid that there might be an
 868                 // inference variable created, registered as an obligation, and
 869                 // then never forced by writeback, and hence by skipping here we'd
 870                 // be ignoring the fact that we don't KNOW the type works
 871                 // out. Though even that would probably be harmless, given that
 872                 // we're only talking about builtin traits, which are known to be
 873                 // inhabited. But in any case I just threw in this check for
 874                 // has_errors() to be sure that compilation isn't happening
 875                 // anyway. In that case, why inundate the user.
 876                 if !self.tcx.sess.has_errors() {
 877                     if
 878                         self.tcx.lang_items.sized_trait()
 879                         .map_or(false, |sized_id| sized_id == trait_ref.def_id())
 880                     {
 881                         self.need_type_info(body_id, span, self_ty);
 882                     } else {
 883                         let mut err = struct_span_err!(self.tcx.sess,
 884                                                         span, E0283,
 885                                                         "type annotations required: \
 886                                                         cannot resolve `{}`",
 887                                                         predicate);
 888                         self.note_obligation_cause(&mut err, obligation);
 889                         err.emit();
 890                     }
 891                 }
 892             }
 893
 894             ty::Predicate::WellFormed(ty) => {
 895                 // Same hacky approach as above to avoid deluging user
 896                 // with error messages.
 897                 if !ty.references_error() && !self.tcx.sess.has_errors() {
 898                     self.need_type_info(body_id, span, ty);
 899                 }
 900             }
 901
 902             ty::Predicate::Subtype(ref data) => {
 903                 if data.references_error() || self.tcx.sess.has_errors() {
 904                     // no need to overload user in such cases
 905                 } else {
 906                     let &SubtypePredicate { a_is_expected: _, a, b } = data.skip_binder();
 907                     // both must be type variables, or the other would've been instantiated
 908                     assert!(a.is_ty_var() && b.is_ty_var());
 909                     self.need_type_info(hir::BodyId { node_id: obligation.cause.body_id },
 910                                         obligation.cause.span,
 911                                         a);
 912                 }
 913             }
 914
 915             _ => {
 916                 if !self.tcx.sess.has_errors() {
 917                     let mut err = struct_span_err!(self.tcx.sess,
 918                                                    obligation.cause.span, E0284,
 919                                                    "type annotations required: \
 920                                                     cannot resolve `{}`",
 921                                                    predicate);
 922                     self.note_obligation_cause(&mut err, obligation);
 923                     err.emit();
 924                 }
 925             }
 926         }
 927     }
 928
 929     /// Returns whether the trait predicate may apply for *some* assignment
 930     /// to the type parameters.
 931     fn predicate_can_apply(&self, pred: ty::PolyTraitRef<'tcx>) -> bool {
 932         struct ParamToVarFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 933             infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
 934             var_map: FxHashMap<Ty<'tcx>, Ty<'tcx>>
 935         }
 936
 937         impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for ParamToVarFolder<'a, 'gcx, 'tcx> {
 938             fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.infcx.tcx }
 939
 940             fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 941                 if let ty::TyParam(ty::ParamTy {name, ..}) = ty.sty {
 942                     let infcx = self.infcx;
 943                     self.var_map.entry(ty).or_insert_with(||
 944                         infcx.next_ty_var(
 945                             TypeVariableOrigin::TypeParameterDefinition(DUMMY_SP, name)))
 946                 } else {
 947                     ty.super_fold_with(self)
 948                 }
 949             }
 950         }
 951
 952         self.probe(|_| {
 953             let mut selcx = SelectionContext::new(self);
 954
 955             let cleaned_pred = pred.fold_with(&mut ParamToVarFolder {
 956                 infcx: self,
 957                 var_map: FxHashMap()
 958             });
 959
 960             let cleaned_pred = super::project::normalize(
 961                 &mut selcx,
 962                 ObligationCause::dummy(),
 963                 &cleaned_pred
 964             ).value;
 965
 966             let obligation = Obligation::new(
 967                 ObligationCause::dummy(),
 968                 cleaned_pred.to_predicate()
 969             );
 970
 971             selcx.evaluate_obligation(&obligation)
 972         })
 973     }
 974
 975     fn extract_type_name(&self, ty: &'a Ty<'tcx>) -> String {
 976         if let ty::TyInfer(ty::TyVar(ty_vid)) = (*ty).sty {
 977             let ty_vars = self.type_variables.borrow();
 978             if let TypeVariableOrigin::TypeParameterDefinition(_, name) =
 979                 *ty_vars.var_origin(ty_vid) {
 980                 name.to_string()
 981             } else {
 982                 ty.to_string()
 983             }
 984         } else {
 985             ty.to_string()
 986         }
 987     }
 988
 989     pub fn need_type_info(&self, body_id: hir::BodyId, span: Span, ty: Ty<'tcx>) {
 990         let ty = self.resolve_type_vars_if_possible(&ty);
 991         let name = self.extract_type_name(&ty);
 992
 993         let mut err_span = span;
 994         let mut labels = vec![(span, format!("cannot infer type for `{}`", name))];
 995
 996         let mut local_visitor = FindLocalByTypeVisitor {
 997             infcx: &self,
 998             target_ty: &ty,
 999             hir_map: &self.tcx.hir,
1000             found_local_pattern: None,
1001             found_arg_pattern: None,
1002         };
1003
1004         // #40294: cause.body_id can also be a fn declaration.
1005         // Currently, if it's anything other than NodeExpr, we just ignore it
1006         match self.tcx.hir.find(body_id.node_id) {
1007             Some(NodeExpr(expr)) => local_visitor.visit_expr(expr),
1008             _ => ()
1009         }
1010
1011         if let Some(pattern) = local_visitor.found_arg_pattern {
1012             err_span = pattern.span;
1013             // We don't want to show the default label for closures.
1014             //
1015             // So, before clearing, the output would look something like this:
1016             // ```
1017             // let x = |_| {  };
1018             //          -  ^^^^ cannot infer type for `[_; 0]`
1019             //          |
1020             //          consider giving this closure parameter a type
1021             // ```
1022             //
1023             // After clearing, it looks something like this:
1024             // ```
1025             // let x = |_| {  };
1026             //          ^ consider giving this closure parameter a type
1027             // ```
1028             labels.clear();
1029             labels.push((pattern.span, format!("consider giving this closure parameter a type")));
1030         }
1031
1032         if let Some(pattern) = local_visitor.found_local_pattern {
1033             if let Some(simple_name) = pattern.simple_name() {
1034                 labels.push((pattern.span, format!("consider giving `{}` a type", simple_name)));
1035             } else {
1036                 labels.push((pattern.span, format!("consider giving the pattern a type")));
1037             }
1038         }
1039
1040         let mut err = struct_span_err!(self.tcx.sess,
1041                                        err_span,
1042                                        E0282,
1043                                        "type annotations needed");
1044
1045         for (target_span, label_message) in labels {
1046             err.span_label(target_span, &label_message);
1047         }
1048
1049         err.emit();
1050     }
1051
1052     fn note_obligation_cause<T>(&self,
1053                                 err: &mut DiagnosticBuilder,
1054                                 obligation: &Obligation<'tcx, T>)
1055         where T: fmt::Display
1056     {
1057         self.note_obligation_cause_code(err,
1058                                         &obligation.predicate,
1059                                         &obligation.cause.code);
1060     }
1061
1062     fn note_obligation_cause_code<T>(&self,
1063                                      err: &mut DiagnosticBuilder,
1064                                      predicate: &T,
1065                                      cause_code: &ObligationCauseCode<'tcx>)
1066         where T: fmt::Display
1067     {
1068         let tcx = self.tcx;
1069         match *cause_code {
1070             ObligationCauseCode::ExprAssignable |
1071             ObligationCauseCode::MatchExpressionArm { .. } |
1072             ObligationCauseCode::IfExpression |
1073             ObligationCauseCode::IfExpressionWithNoElse |
1074             ObligationCauseCode::EquatePredicate |
1075             ObligationCauseCode::MainFunctionType |
1076             ObligationCauseCode::StartFunctionType |
1077             ObligationCauseCode::IntrinsicType |
1078             ObligationCauseCode::MethodReceiver |
1079             ObligationCauseCode::ReturnNoExpression |
1080             ObligationCauseCode::MiscObligation => {
1081             }
1082             ObligationCauseCode::SliceOrArrayElem => {
1083                 err.note("slice and array elements must have `Sized` type");
1084             }
1085             ObligationCauseCode::TupleElem => {
1086                 err.note("tuple elements must have `Sized` type");
1087             }
1088             ObligationCauseCode::ProjectionWf(data) => {
1089                 err.note(&format!("required so that the projection `{}` is well-formed",
1090                                   data));
1091             }
1092             ObligationCauseCode::ReferenceOutlivesReferent(ref_ty) => {
1093                 err.note(&format!("required so that reference `{}` does not outlive its referent",
1094                                   ref_ty));
1095             }
1096             ObligationCauseCode::ObjectTypeBound(object_ty, region) => {
1097                 err.note(&format!("required so that the lifetime bound of `{}` for `{}` \
1098                                    is satisfied",
1099                                   region, object_ty));
1100             }
1101             ObligationCauseCode::ItemObligation(item_def_id) => {
1102                 let item_name = tcx.item_path_str(item_def_id);
1103                 err.note(&format!("required by `{}`", item_name));
1104             }
1105             ObligationCauseCode::ObjectCastObligation(object_ty) => {
1106                 err.note(&format!("required for the cast to the object type `{}`",
1107                                   self.ty_to_string(object_ty)));
1108             }
1109             ObligationCauseCode::RepeatVec => {
1110                 err.note("the `Copy` trait is required because the \
1111                           repeated element will be copied");
1112             }
1113             ObligationCauseCode::VariableType(_) => {
1114                 err.note("all local variables must have a statically known size");
1115             }
1116             ObligationCauseCode::ReturnType => {
1117                 err.note("the return type of a function must have a \
1118                           statically known size");
1119             }
1120             ObligationCauseCode::AssignmentLhsSized => {
1121                 err.note("the left-hand-side of an assignment must have a statically known size");
1122             }
1123             ObligationCauseCode::StructInitializerSized => {
1124                 err.note("structs must have a statically known size to be initialized");
1125             }
1126             ObligationCauseCode::FieldSized => {
1127                 err.note("only the last field of a struct may have a dynamically sized type");
1128             }
1129             ObligationCauseCode::ConstSized => {
1130                 err.note("constant expressions must have a statically known size");
1131             }
1132             ObligationCauseCode::SharedStatic => {
1133                 err.note("shared static variables must have a type that implements `Sync`");
1134             }
1135             ObligationCauseCode::BuiltinDerivedObligation(ref data) => {
1136                 let parent_trait_ref = self.resolve_type_vars_if_possible(&data.parent_trait_ref);
1137                 err.note(&format!("required because it appears within the type `{}`",
1138                                   parent_trait_ref.0.self_ty()));
1139                 let parent_predicate = parent_trait_ref.to_predicate();
1140                 self.note_obligation_cause_code(err,
1141                                                 &parent_predicate,
1142                                                 &data.parent_code);
1143             }
1144             ObligationCauseCode::ImplDerivedObligation(ref data) => {
1145                 let parent_trait_ref = self.resolve_type_vars_if_possible(&data.parent_trait_ref);
1146                 err.note(
1147                     &format!("required because of the requirements on the impl of `{}` for `{}`",
1148                              parent_trait_ref,
1149                              parent_trait_ref.0.self_ty()));
1150                 let parent_predicate = parent_trait_ref.to_predicate();
1151                 self.note_obligation_cause_code(err,
1152                                                 &parent_predicate,
1153                                                 &data.parent_code);
1154             }
1155             ObligationCauseCode::CompareImplMethodObligation { .. } => {
1156                 err.note(
1157                     &format!("the requirement `{}` appears on the impl method \
1158                               but not on the corresponding trait method",
1159                              predicate));
1160             }
1161         }
1162     }
1163
1164     fn suggest_new_overflow_limit(&self, err: &mut DiagnosticBuilder) {
1165         let current_limit = self.tcx.sess.recursion_limit.get();
1166         let suggested_limit = current_limit * 2;
1167         err.help(&format!(
1168                           "consider adding a `#![recursion_limit=\"{}\"]` attribute to your crate",
1169                           suggested_limit));
1170     }
1171 }
1172