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