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