src/librustc/infer/error_reporting.rs

   1 // Copyright 2012-2013 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 //! Error Reporting Code for the inference engine
  12 //!
  13 //! Because of the way inference, and in particular region inference,
  14 //! works, it often happens that errors are not detected until far after
  15 //! the relevant line of code has been type-checked. Therefore, there is
  16 //! an elaborate system to track why a particular constraint in the
  17 //! inference graph arose so that we can explain to the user what gave
  18 //! rise to a particular error.
  19 //!
  20 //! The basis of the system are the "origin" types. An "origin" is the
  21 //! reason that a constraint or inference variable arose. There are
  22 //! different "origin" enums for different kinds of constraints/variables
  23 //! (e.g., `TypeOrigin`, `RegionVariableOrigin`). An origin always has
  24 //! a span, but also more information so that we can generate a meaningful
  25 //! error message.
  26 //!
  27 //! Having a catalogue of all the different reasons an error can arise is
  28 //! also useful for other reasons, like cross-referencing FAQs etc, though
  29 //! we are not really taking advantage of this yet.
  30 //!
  31 //! # Region Inference
  32 //!
  33 //! Region inference is particularly tricky because it always succeeds "in
  34 //! the moment" and simply registers a constraint. Then, at the end, we
  35 //! can compute the full graph and report errors, so we need to be able to
  36 //! store and later report what gave rise to the conflicting constraints.
  37 //!
  38 //! # Subtype Trace
  39 //!
  40 //! Determining whether `T1 <: T2` often involves a number of subtypes and
  41 //! subconstraints along the way. A "TypeTrace" is an extended version
  42 //! of an origin that traces the types and other values that were being
  43 //! compared. It is not necessarily comprehensive (in fact, at the time of
  44 //! this writing it only tracks the root values being compared) but I'd
  45 //! like to extend it to include significant "waypoints". For example, if
  46 //! you are comparing `(T1, T2) <: (T3, T4)`, and the problem is that `T2
  47 //! <: T4` fails, I'd like the trace to include enough information to say
  48 //! "in the 2nd element of the tuple". Similarly, failures when comparing
  49 //! arguments or return types in fn types should be able to cite the
  50 //! specific position, etc.
  51 //!
  52 //! # Reality vs plan
  53 //!
  54 //! Of course, there is still a LOT of code in typeck that has yet to be
  55 //! ported to this system, and which relies on string concatenation at the
  56 //! time of error detection.
  57
  58 use self::FreshOrKept::*;
  59
  60 use super::InferCtxt;
  61 use super::TypeTrace;
  62 use super::SubregionOrigin;
  63 use super::RegionVariableOrigin;
  64 use super::ValuePairs;
  65 use super::region_inference::RegionResolutionError;
  66 use super::region_inference::ConcreteFailure;
  67 use super::region_inference::SubSupConflict;
  68 use super::region_inference::GenericBoundFailure;
  69 use super::region_inference::GenericKind;
  70 use super::region_inference::ProcessedErrors;
  71 use super::region_inference::ProcessedErrorOrigin;
  72 use super::region_inference::SameRegions;
  73
  74 use std::collections::HashSet;
  75
  76 use hir::map as ast_map;
  77 use hir;
  78 use hir::print as pprust;
  79
  80 use lint;
  81 use hir::def::Def;
  82 use hir::def_id::DefId;
  83 use infer::{self, TypeOrigin};
  84 use middle::region;
  85 use ty::{self, TyCtxt, TypeFoldable};
  86 use ty::{Region, ReFree};
  87 use ty::error::TypeError;
  88
  89 use std::cell::{Cell, RefCell};
  90 use std::char::from_u32;
  91 use std::fmt;
  92 use syntax::ast;
  93 use syntax::parse::token;
  94 use syntax::ptr::P;
  95 use syntax_pos::{self, Pos, Span};
  96 use errors::DiagnosticBuilder;
  97
  98 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
  99     pub fn note_and_explain_region(self,
 100                                    err: &mut DiagnosticBuilder,
 101                                    prefix: &str,
 102                                    region: ty::Region,
 103                                    suffix: &str) {
 104         fn item_scope_tag(item: &hir::Item) -> &'static str {
 105             match item.node {
 106                 hir::ItemImpl(..) => "impl",
 107                 hir::ItemStruct(..) => "struct",
 108                 hir::ItemEnum(..) => "enum",
 109                 hir::ItemTrait(..) => "trait",
 110                 hir::ItemFn(..) => "function body",
 111                 _ => "item"
 112             }
 113         }
 114
 115         fn explain_span<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 116                                         heading: &str, span: Span)
 117                                         -> (String, Option<Span>) {
 118             let lo = tcx.sess.codemap().lookup_char_pos_adj(span.lo);
 119             (format!("the {} at {}:{}", heading, lo.line, lo.col.to_usize()),
 120              Some(span))
 121         }
 122
 123         let (description, span) = match region {
 124             ty::ReScope(scope) => {
 125                 let new_string;
 126                 let unknown_scope = || {
 127                     format!("{}unknown scope: {:?}{}.  Please report a bug.",
 128                             prefix, scope, suffix)
 129                 };
 130                 let span = match scope.span(&self.region_maps, &self.map) {
 131                     Some(s) => s,
 132                     None => {
 133                         err.note(&unknown_scope());
 134                         return;
 135                     }
 136                 };
 137                 let tag = match self.map.find(scope.node_id(&self.region_maps)) {
 138                     Some(ast_map::NodeBlock(_)) => "block",
 139                     Some(ast_map::NodeExpr(expr)) => match expr.node {
 140                         hir::ExprCall(..) => "call",
 141                         hir::ExprMethodCall(..) => "method call",
 142                         hir::ExprMatch(_, _, hir::MatchSource::IfLetDesugar { .. }) => "if let",
 143                         hir::ExprMatch(_, _, hir::MatchSource::WhileLetDesugar) =>  "while let",
 144                         hir::ExprMatch(_, _, hir::MatchSource::ForLoopDesugar) =>  "for",
 145                         hir::ExprMatch(..) => "match",
 146                         _ => "expression",
 147                     },
 148                     Some(ast_map::NodeStmt(_)) => "statement",
 149                     Some(ast_map::NodeItem(it)) => item_scope_tag(&it),
 150                     Some(_) | None => {
 151                         err.span_note(span, &unknown_scope());
 152                         return;
 153                     }
 154                 };
 155                 let scope_decorated_tag = match self.region_maps.code_extent_data(scope) {
 156                     region::CodeExtentData::Misc(_) => tag,
 157                     region::CodeExtentData::CallSiteScope { .. } => {
 158                         "scope of call-site for function"
 159                     }
 160                     region::CodeExtentData::ParameterScope { .. } => {
 161                         "scope of function body"
 162                     }
 163                     region::CodeExtentData::DestructionScope(_) => {
 164                         new_string = format!("destruction scope surrounding {}", tag);
 165                         &new_string[..]
 166                     }
 167                     region::CodeExtentData::Remainder(r) => {
 168                         new_string = format!("block suffix following statement {}",
 169                                              r.first_statement_index);
 170                         &new_string[..]
 171                     }
 172                 };
 173                 explain_span(self, scope_decorated_tag, span)
 174             }
 175
 176             ty::ReFree(ref fr) => {
 177                 let prefix = match fr.bound_region {
 178                     ty::BrAnon(idx) => {
 179                         format!("the anonymous lifetime #{} defined on", idx + 1)
 180                     }
 181                     ty::BrFresh(_) => "an anonymous lifetime defined on".to_owned(),
 182                     _ => {
 183                         format!("the lifetime {} as defined on",
 184                                 fr.bound_region)
 185                     }
 186                 };
 187
 188                 match self.map.find(fr.scope.node_id(&self.region_maps)) {
 189                     Some(ast_map::NodeBlock(ref blk)) => {
 190                         let (msg, opt_span) = explain_span(self, "block", blk.span);
 191                         (format!("{} {}", prefix, msg), opt_span)
 192                     }
 193                     Some(ast_map::NodeItem(it)) => {
 194                         let tag = item_scope_tag(&it);
 195                         let (msg, opt_span) = explain_span(self, tag, it.span);
 196                         (format!("{} {}", prefix, msg), opt_span)
 197                     }
 198                     Some(_) | None => {
 199                         // this really should not happen, but it does:
 200                         // FIXME(#27942)
 201                         (format!("{} unknown free region bounded by scope {:?}",
 202                                  prefix, fr.scope), None)
 203                     }
 204                 }
 205             }
 206
 207             ty::ReStatic => ("the static lifetime".to_owned(), None),
 208
 209             ty::ReEmpty => ("the empty lifetime".to_owned(), None),
 210
 211             ty::ReEarlyBound(ref data) => (data.name.to_string(), None),
 212
 213             // FIXME(#13998) ReSkolemized should probably print like
 214             // ReFree rather than dumping Debug output on the user.
 215             //
 216             // We shouldn't really be having unification failures with ReVar
 217             // and ReLateBound though.
 218             ty::ReSkolemized(..) |
 219             ty::ReVar(_) |
 220             ty::ReLateBound(..) |
 221             ty::ReErased => {
 222                 (format!("lifetime {:?}", region), None)
 223             }
 224         };
 225         let message = format!("{}{}{}", prefix, description, suffix);
 226         if let Some(span) = span {
 227             err.span_note(span, &message);
 228         } else {
 229             err.note(&message);
 230         }
 231     }
 232 }
 233
 234 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 235     pub fn report_region_errors(&self,
 236                                 errors: &Vec<RegionResolutionError<'tcx>>) {
 237         debug!("report_region_errors(): {} errors to start", errors.len());
 238
 239         // try to pre-process the errors, which will group some of them
 240         // together into a `ProcessedErrors` group:
 241         let processed_errors = self.process_errors(errors);
 242         let errors = processed_errors.as_ref().unwrap_or(errors);
 243
 244         debug!("report_region_errors: {} errors after preprocessing", errors.len());
 245
 246         for error in errors {
 247             match error.clone() {
 248                 ConcreteFailure(origin, sub, sup) => {
 249                     self.report_concrete_failure(origin, sub, sup).emit();
 250                 }
 251
 252                 GenericBoundFailure(kind, param_ty, sub) => {
 253                     self.report_generic_bound_failure(kind, param_ty, sub);
 254                 }
 255
 256                 SubSupConflict(var_origin,
 257                                sub_origin, sub_r,
 258                                sup_origin, sup_r) => {
 259                     self.report_sub_sup_conflict(var_origin,
 260                                                  sub_origin, sub_r,
 261                                                  sup_origin, sup_r);
 262                 }
 263
 264                 ProcessedErrors(ref origins,
 265                                 ref same_regions) => {
 266                     if !same_regions.is_empty() {
 267                         self.report_processed_errors(origins, same_regions);
 268                     }
 269                 }
 270             }
 271         }
 272     }
 273
 274     // This method goes through all the errors and try to group certain types
 275     // of error together, for the purpose of suggesting explicit lifetime
 276     // parameters to the user. This is done so that we can have a more
 277     // complete view of what lifetimes should be the same.
 278     // If the return value is an empty vector, it means that processing
 279     // failed (so the return value of this method should not be used).
 280     //
 281     // The method also attempts to weed out messages that seem like
 282     // duplicates that will be unhelpful to the end-user. But
 283     // obviously it never weeds out ALL errors.
 284     fn process_errors(&self, errors: &Vec<RegionResolutionError<'tcx>>)
 285                       -> Option<Vec<RegionResolutionError<'tcx>>> {
 286         debug!("process_errors()");
 287         let mut origins = Vec::new();
 288
 289         // we collect up ConcreteFailures and SubSupConflicts that are
 290         // relating free-regions bound on the fn-header and group them
 291         // together into this vector
 292         let mut same_regions = Vec::new();
 293
 294         // here we put errors that we will not be able to process nicely
 295         let mut other_errors = Vec::new();
 296
 297         // we collect up GenericBoundFailures in here.
 298         let mut bound_failures = Vec::new();
 299
 300         for error in errors {
 301             match *error {
 302                 ConcreteFailure(ref origin, sub, sup) => {
 303                     debug!("processing ConcreteFailure");
 304                     match free_regions_from_same_fn(self.tcx, sub, sup) {
 305                         Some(ref same_frs) => {
 306                             origins.push(
 307                                 ProcessedErrorOrigin::ConcreteFailure(
 308                                     origin.clone(),
 309                                     sub,
 310                                     sup));
 311                             append_to_same_regions(&mut same_regions, same_frs);
 312                         }
 313                         _ => {
 314                             other_errors.push(error.clone());
 315                         }
 316                     }
 317                 }
 318                 SubSupConflict(ref var_origin, _, sub_r, _, sup_r) => {
 319                     debug!("processing SubSupConflict sub: {:?} sup: {:?}", sub_r, sup_r);
 320                     match free_regions_from_same_fn(self.tcx, sub_r, sup_r) {
 321                         Some(ref same_frs) => {
 322                             origins.push(
 323                                 ProcessedErrorOrigin::VariableFailure(
 324                                     var_origin.clone()));
 325                             append_to_same_regions(&mut same_regions, same_frs);
 326                         }
 327                         None => {
 328                             other_errors.push(error.clone());
 329                         }
 330                     }
 331                 }
 332                 GenericBoundFailure(ref origin, ref kind, region) => {
 333                     bound_failures.push((origin.clone(), kind.clone(), region));
 334                 }
 335                 ProcessedErrors(..) => {
 336                     bug!("should not encounter a `ProcessedErrors` yet: {:?}", error)
 337                 }
 338             }
 339         }
 340
 341         // ok, let's pull together the errors, sorted in an order that
 342         // we think will help user the best
 343         let mut processed_errors = vec![];
 344
 345         // first, put the processed errors, if any
 346         if !same_regions.is_empty() {
 347             let common_scope_id = same_regions[0].scope_id;
 348             for sr in &same_regions {
 349                 // Since ProcessedErrors is used to reconstruct the function
 350                 // declaration, we want to make sure that they are, in fact,
 351                 // from the same scope
 352                 if sr.scope_id != common_scope_id {
 353                     debug!("returning empty result from process_errors because
 354                             {} != {}", sr.scope_id, common_scope_id);
 355                     return None;
 356                 }
 357             }
 358             assert!(origins.len() > 0);
 359             let pe = ProcessedErrors(origins, same_regions);
 360             debug!("errors processed: {:?}", pe);
 361             processed_errors.push(pe);
 362         }
 363
 364         // next, put the other misc errors
 365         processed_errors.extend(other_errors);
 366
 367         // finally, put the `T: 'a` errors, but only if there were no
 368         // other errors. otherwise, these have a very high rate of
 369         // being unhelpful in practice. This is because they are
 370         // basically secondary checks that test the state of the
 371         // region graph after the rest of inference is done, and the
 372         // other kinds of errors indicate that the region constraint
 373         // graph is internally inconsistent, so these test results are
 374         // likely to be meaningless.
 375         if processed_errors.is_empty() {
 376             for (origin, kind, region) in bound_failures {
 377                 processed_errors.push(GenericBoundFailure(origin, kind, region));
 378             }
 379         }
 380
 381         // we should always wind up with SOME errors, unless there were no
 382         // errors to start
 383         assert!(if errors.len() > 0 {processed_errors.len() > 0} else {true});
 384
 385         return Some(processed_errors);
 386
 387         #[derive(Debug)]
 388         struct FreeRegionsFromSameFn {
 389             sub_fr: ty::FreeRegion,
 390             sup_fr: ty::FreeRegion,
 391             scope_id: ast::NodeId
 392         }
 393
 394         impl FreeRegionsFromSameFn {
 395             fn new(sub_fr: ty::FreeRegion,
 396                    sup_fr: ty::FreeRegion,
 397                    scope_id: ast::NodeId)
 398                    -> FreeRegionsFromSameFn {
 399                 FreeRegionsFromSameFn {
 400                     sub_fr: sub_fr,
 401                     sup_fr: sup_fr,
 402                     scope_id: scope_id
 403                 }
 404             }
 405         }
 406
 407         fn free_regions_from_same_fn<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 408                                                      sub: Region,
 409                                                      sup: Region)
 410                                                      -> Option<FreeRegionsFromSameFn> {
 411             debug!("free_regions_from_same_fn(sub={:?}, sup={:?})", sub, sup);
 412             let (scope_id, fr1, fr2) = match (sub, sup) {
 413                 (ReFree(fr1), ReFree(fr2)) => {
 414                     if fr1.scope != fr2.scope {
 415                         return None
 416                     }
 417                     assert!(fr1.scope == fr2.scope);
 418                     (fr1.scope.node_id(&tcx.region_maps), fr1, fr2)
 419                 },
 420                 _ => return None
 421             };
 422             let parent = tcx.map.get_parent(scope_id);
 423             let parent_node = tcx.map.find(parent);
 424             match parent_node {
 425                 Some(node) => match node {
 426                     ast_map::NodeItem(item) => match item.node {
 427                         hir::ItemFn(..) => {
 428                             Some(FreeRegionsFromSameFn::new(fr1, fr2, scope_id))
 429                         },
 430                         _ => None
 431                     },
 432                     ast_map::NodeImplItem(..) |
 433                     ast_map::NodeTraitItem(..) => {
 434                         Some(FreeRegionsFromSameFn::new(fr1, fr2, scope_id))
 435                     },
 436                     _ => None
 437                 },
 438                 None => {
 439                     debug!("no parent node of scope_id {}", scope_id);
 440                     None
 441                 }
 442             }
 443         }
 444
 445         fn append_to_same_regions(same_regions: &mut Vec<SameRegions>,
 446                                   same_frs: &FreeRegionsFromSameFn) {
 447             debug!("append_to_same_regions(same_regions={:?}, same_frs={:?})",
 448                    same_regions, same_frs);
 449             let scope_id = same_frs.scope_id;
 450             let (sub_fr, sup_fr) = (same_frs.sub_fr, same_frs.sup_fr);
 451             for sr in same_regions.iter_mut() {
 452                 if sr.contains(&sup_fr.bound_region) && scope_id == sr.scope_id {
 453                     sr.push(sub_fr.bound_region);
 454                     return
 455                 }
 456             }
 457             same_regions.push(SameRegions {
 458                 scope_id: scope_id,
 459                 regions: vec!(sub_fr.bound_region, sup_fr.bound_region)
 460             })
 461         }
 462     }
 463
 464     /// Adds a note if the types come from similarly named crates
 465     fn check_and_note_conflicting_crates(&self,
 466                                          err: &mut DiagnosticBuilder,
 467                                          terr: &TypeError<'tcx>,
 468                                          sp: Span) {
 469         let report_path_match = |err: &mut DiagnosticBuilder, did1: DefId, did2: DefId| {
 470             // Only external crates, if either is from a local
 471             // module we could have false positives
 472             if !(did1.is_local() || did2.is_local()) && did1.krate != did2.krate {
 473                 let exp_path = self.tcx.item_path_str(did1);
 474                 let found_path = self.tcx.item_path_str(did2);
 475                 // We compare strings because DefPath can be different
 476                 // for imported and non-imported crates
 477                 if exp_path == found_path {
 478                     let crate_name = self.tcx.sess.cstore.crate_name(did1.krate);
 479                     err.span_note(sp, &format!("Perhaps two different versions \
 480                                                 of crate `{}` are being used?",
 481                                                crate_name));
 482                 }
 483             }
 484         };
 485         match *terr {
 486             TypeError::Sorts(ref exp_found) => {
 487                 // if they are both "path types", there's a chance of ambiguity
 488                 // due to different versions of the same crate
 489                 match (&exp_found.expected.sty, &exp_found.found.sty) {
 490                     (&ty::TyEnum(ref exp_adt, _), &ty::TyEnum(ref found_adt, _)) |
 491                     (&ty::TyStruct(ref exp_adt, _), &ty::TyStruct(ref found_adt, _)) |
 492                     (&ty::TyEnum(ref exp_adt, _), &ty::TyStruct(ref found_adt, _)) |
 493                     (&ty::TyStruct(ref exp_adt, _), &ty::TyEnum(ref found_adt, _)) => {
 494                         report_path_match(err, exp_adt.did, found_adt.did);
 495                     },
 496                     _ => ()
 497                 }
 498             },
 499             TypeError::Traits(ref exp_found) => {
 500                 report_path_match(err, exp_found.expected, exp_found.found);
 501             },
 502             _ => () // FIXME(#22750) handle traits and stuff
 503         }
 504     }
 505
 506     fn note_error_origin(&self,
 507                          err: &mut DiagnosticBuilder<'tcx>,
 508                          origin: &TypeOrigin)
 509     {
 510         match origin {
 511             &TypeOrigin::MatchExpressionArm(_, arm_span, source) => match source {
 512                 hir::MatchSource::IfLetDesugar {..} => {
 513                     err.span_note(arm_span, "`if let` arm with an incompatible type");
 514                 }
 515                 _ => {
 516                     err.span_note(arm_span, "match arm with an incompatible type");
 517                 }
 518             },
 519             _ => ()
 520         }
 521     }
 522
 523     pub fn note_type_err(&self,
 524                          diag: &mut DiagnosticBuilder<'tcx>,
 525                          origin: TypeOrigin,
 526                          values: Option<ValuePairs<'tcx>>,
 527                          terr: &TypeError<'tcx>)
 528     {
 529         let expected_found = match values {
 530             None => None,
 531             Some(values) => match self.values_str(&values) {
 532                 Some((expected, found)) => Some((expected, found)),
 533                 None => {
 534                     // Derived error. Cancel the emitter.
 535                     self.tcx.sess.diagnostic().cancel(diag);
 536                     return
 537                 }
 538             }
 539         };
 540
 541         let span = origin.span();
 542
 543         if let Some((expected, found)) = expected_found {
 544             let is_simple_error = if let &TypeError::Sorts(ref values) = terr {
 545                 values.expected.is_primitive() && values.found.is_primitive()
 546             } else {
 547                 false
 548             };
 549
 550             if !is_simple_error {
 551                 diag.note_expected_found(&"type", &expected, &found);
 552             }
 553         }
 554
 555         diag.span_label(span, &terr);
 556
 557         self.note_error_origin(diag, &origin);
 558         self.check_and_note_conflicting_crates(diag, terr, span);
 559         self.tcx.note_and_explain_type_err(diag, terr, span);
 560     }
 561
 562     pub fn report_and_explain_type_error(&self,
 563                                          trace: TypeTrace<'tcx>,
 564                                          terr: &TypeError<'tcx>)
 565                                          -> DiagnosticBuilder<'tcx>
 566     {
 567         // FIXME: do we want to use a different error code for each origin?
 568         let mut diag = struct_span_err!(
 569             self.tcx.sess, trace.origin.span(), E0308,
 570             "{}", trace.origin.as_failure_str()
 571         );
 572         self.note_type_err(&mut diag, trace.origin, Some(trace.values), terr);
 573         diag
 574     }
 575
 576     /// Returns a string of the form "expected `{}`, found `{}`".
 577     fn values_str(&self, values: &ValuePairs<'tcx>) -> Option<(String, String)> {
 578         match *values {
 579             infer::Types(ref exp_found) => self.expected_found_str(exp_found),
 580             infer::TraitRefs(ref exp_found) => self.expected_found_str(exp_found),
 581             infer::PolyTraitRefs(ref exp_found) => self.expected_found_str(exp_found),
 582         }
 583     }
 584
 585     fn expected_found_str<T: fmt::Display + TypeFoldable<'tcx>>(
 586         &self,
 587         exp_found: &ty::error::ExpectedFound<T>)
 588         -> Option<(String, String)>
 589     {
 590         let exp_found = self.resolve_type_vars_if_possible(exp_found);
 591         if exp_found.references_error() {
 592             return None;
 593         }
 594
 595         Some((format!("{}", exp_found.expected), format!("{}", exp_found.found)))
 596     }
 597
 598     fn report_generic_bound_failure(&self,
 599                                     origin: SubregionOrigin<'tcx>,
 600                                     bound_kind: GenericKind<'tcx>,
 601                                     sub: Region)
 602     {
 603         // FIXME: it would be better to report the first error message
 604         // with the span of the parameter itself, rather than the span
 605         // where the error was detected. But that span is not readily
 606         // accessible.
 607
 608         let labeled_user_string = match bound_kind {
 609             GenericKind::Param(ref p) =>
 610                 format!("the parameter type `{}`", p),
 611             GenericKind::Projection(ref p) =>
 612                 format!("the associated type `{}`", p),
 613         };
 614
 615         let mut err = match sub {
 616             ty::ReFree(ty::FreeRegion {bound_region: ty::BrNamed(..), ..}) => {
 617                 // Does the required lifetime have a nice name we can print?
 618                 let mut err = struct_span_err!(self.tcx.sess,
 619                                                origin.span(),
 620                                                E0309,
 621                                                "{} may not live long enough",
 622                                                labeled_user_string);
 623                 err.help(&format!("consider adding an explicit lifetime bound `{}: {}`...",
 624                          bound_kind,
 625                          sub));
 626                 err
 627             }
 628
 629             ty::ReStatic => {
 630                 // Does the required lifetime have a nice name we can print?
 631                 let mut err = struct_span_err!(self.tcx.sess,
 632                                                origin.span(),
 633                                                E0310,
 634                                                "{} may not live long enough",
 635                                                labeled_user_string);
 636                 err.help(&format!("consider adding an explicit lifetime \
 637                                    bound `{}: 'static`...",
 638                                   bound_kind));
 639                 err
 640             }
 641
 642             _ => {
 643                 // If not, be less specific.
 644                 let mut err = struct_span_err!(self.tcx.sess,
 645                                                origin.span(),
 646                                                E0311,
 647                                                "{} may not live long enough",
 648                                                labeled_user_string);
 649                 err.help(&format!("consider adding an explicit lifetime bound for `{}`",
 650                                   bound_kind));
 651                 self.tcx.note_and_explain_region(
 652                     &mut err,
 653                     &format!("{} must be valid for ", labeled_user_string),
 654                     sub,
 655                     "...");
 656                 err
 657             }
 658         };
 659
 660         self.note_region_origin(&mut err, &origin);
 661         err.emit();
 662     }
 663
 664     fn report_concrete_failure(&self,
 665                                origin: SubregionOrigin<'tcx>,
 666                                sub: Region,
 667                                sup: Region)
 668                                 -> DiagnosticBuilder<'tcx> {
 669         match origin {
 670             infer::Subtype(trace) => {
 671                 let terr = TypeError::RegionsDoesNotOutlive(sup, sub);
 672                 self.report_and_explain_type_error(trace, &terr)
 673             }
 674             infer::Reborrow(span) => {
 675                 let mut err = struct_span_err!(self.tcx.sess, span, E0312,
 676                     "lifetime of reference outlives \
 677                      lifetime of borrowed content...");
 678                 self.tcx.note_and_explain_region(&mut err,
 679                     "...the reference is valid for ",
 680                     sub,
 681                     "...");
 682                 self.tcx.note_and_explain_region(&mut err,
 683                     "...but the borrowed content is only valid for ",
 684                     sup,
 685                     "");
 686                 err
 687             }
 688             infer::ReborrowUpvar(span, ref upvar_id) => {
 689                 let mut err = struct_span_err!(self.tcx.sess, span, E0313,
 690                     "lifetime of borrowed pointer outlives \
 691                             lifetime of captured variable `{}`...",
 692                             self.tcx.local_var_name_str(upvar_id.var_id));
 693                 self.tcx.note_and_explain_region(&mut err,
 694                     "...the borrowed pointer is valid for ",
 695                     sub,
 696                     "...");
 697                 self.tcx.note_and_explain_region(&mut err,
 698                     &format!("...but `{}` is only valid for ",
 699                              self.tcx.local_var_name_str(upvar_id.var_id)),
 700                     sup,
 701                     "");
 702                 err
 703             }
 704             infer::InfStackClosure(span) => {
 705                 let mut err = struct_span_err!(self.tcx.sess, span, E0314,
 706                     "closure outlives stack frame");
 707                 self.tcx.note_and_explain_region(&mut err,
 708                     "...the closure must be valid for ",
 709                     sub,
 710                     "...");
 711                 self.tcx.note_and_explain_region(&mut err,
 712                     "...but the closure's stack frame is only valid for ",
 713                     sup,
 714                     "");
 715                 err
 716             }
 717             infer::InvokeClosure(span) => {
 718                 let mut err = struct_span_err!(self.tcx.sess, span, E0315,
 719                     "cannot invoke closure outside of its lifetime");
 720                 self.tcx.note_and_explain_region(&mut err,
 721                     "the closure is only valid for ",
 722                     sup,
 723                     "");
 724                 err
 725             }
 726             infer::DerefPointer(span) => {
 727                 let mut err = struct_span_err!(self.tcx.sess, span, E0473,
 728                           "dereference of reference outside its lifetime");
 729                 self.tcx.note_and_explain_region(&mut err,
 730                     "the reference is only valid for ",
 731                     sup,
 732                     "");
 733                 err
 734             }
 735             infer::FreeVariable(span, id) => {
 736                 let mut err = struct_span_err!(self.tcx.sess, span, E0474,
 737                           "captured variable `{}` does not outlive the enclosing closure",
 738                           self.tcx.local_var_name_str(id));
 739                 self.tcx.note_and_explain_region(&mut err,
 740                     "captured variable is valid for ",
 741                     sup,
 742                     "");
 743                 self.tcx.note_and_explain_region(&mut err,
 744                     "closure is valid for ",
 745                     sub,
 746                     "");
 747                 err
 748             }
 749             infer::IndexSlice(span) => {
 750                 let mut err = struct_span_err!(self.tcx.sess, span, E0475,
 751                           "index of slice outside its lifetime");
 752                 self.tcx.note_and_explain_region(&mut err,
 753                     "the slice is only valid for ",
 754                     sup,
 755                     "");
 756                 err
 757             }
 758             infer::RelateObjectBound(span) => {
 759                 let mut err = struct_span_err!(self.tcx.sess, span, E0476,
 760                           "lifetime of the source pointer does not outlive \
 761                            lifetime bound of the object type");
 762                 self.tcx.note_and_explain_region(&mut err,
 763                     "object type is valid for ",
 764                     sub,
 765                     "");
 766                 self.tcx.note_and_explain_region(&mut err,
 767                     "source pointer is only valid for ",
 768                     sup,
 769                     "");
 770                 err
 771             }
 772             infer::RelateParamBound(span, ty) => {
 773                 let mut err = struct_span_err!(self.tcx.sess, span, E0477,
 774                           "the type `{}` does not fulfill the required lifetime",
 775                           self.ty_to_string(ty));
 776                 self.tcx.note_and_explain_region(&mut err,
 777                                         "type must outlive ",
 778                                         sub,
 779                                         "");
 780                 err
 781             }
 782             infer::RelateRegionParamBound(span) => {
 783                 let mut err = struct_span_err!(self.tcx.sess, span, E0478,
 784                           "lifetime bound not satisfied");
 785                 self.tcx.note_and_explain_region(&mut err,
 786                     "lifetime parameter instantiated with ",
 787                     sup,
 788                     "");
 789                 self.tcx.note_and_explain_region(&mut err,
 790                     "but lifetime parameter must outlive ",
 791                     sub,
 792                     "");
 793                 err
 794             }
 795             infer::RelateDefaultParamBound(span, ty) => {
 796                 let mut err = struct_span_err!(self.tcx.sess, span, E0479,
 797                           "the type `{}` (provided as the value of \
 798                            a type parameter) is not valid at this point",
 799                           self.ty_to_string(ty));
 800                 self.tcx.note_and_explain_region(&mut err,
 801                                         "type must outlive ",
 802                                         sub,
 803                                         "");
 804                 err
 805             }
 806             infer::CallRcvr(span) => {
 807                 let mut err = struct_span_err!(self.tcx.sess, span, E0480,
 808                           "lifetime of method receiver does not outlive \
 809                            the method call");
 810                 self.tcx.note_and_explain_region(&mut err,
 811                     "the receiver is only valid for ",
 812                     sup,
 813                     "");
 814                 err
 815             }
 816             infer::CallArg(span) => {
 817                 let mut err = struct_span_err!(self.tcx.sess, span, E0481,
 818                           "lifetime of function argument does not outlive \
 819                            the function call");
 820                 self.tcx.note_and_explain_region(&mut err,
 821                     "the function argument is only valid for ",
 822                     sup,
 823                     "");
 824                 err
 825             }
 826             infer::CallReturn(span) => {
 827                 let mut err = struct_span_err!(self.tcx.sess, span, E0482,
 828                           "lifetime of return value does not outlive \
 829                            the function call");
 830                 self.tcx.note_and_explain_region(&mut err,
 831                     "the return value is only valid for ",
 832                     sup,
 833                     "");
 834                 err
 835             }
 836             infer::Operand(span) => {
 837                 let mut err = struct_span_err!(self.tcx.sess, span, E0483,
 838                           "lifetime of operand does not outlive \
 839                            the operation");
 840                 self.tcx.note_and_explain_region(&mut err,
 841                     "the operand is only valid for ",
 842                     sup,
 843                     "");
 844                 err
 845             }
 846             infer::AddrOf(span) => {
 847                 let mut err = struct_span_err!(self.tcx.sess, span, E0484,
 848                           "reference is not valid at the time of borrow");
 849                 self.tcx.note_and_explain_region(&mut err,
 850                     "the borrow is only valid for ",
 851                     sup,
 852                     "");
 853                 err
 854             }
 855             infer::AutoBorrow(span) => {
 856                 let mut err = struct_span_err!(self.tcx.sess, span, E0485,
 857                           "automatically reference is not valid \
 858                            at the time of borrow");
 859                 self.tcx.note_and_explain_region(&mut err,
 860                     "the automatic borrow is only valid for ",
 861                     sup,
 862                     "");
 863                 err
 864             }
 865             infer::ExprTypeIsNotInScope(t, span) => {
 866                 let mut err = struct_span_err!(self.tcx.sess, span, E0486,
 867                           "type of expression contains references \
 868                            that are not valid during the expression: `{}`",
 869                           self.ty_to_string(t));
 870                 self.tcx.note_and_explain_region(&mut err,
 871                     "type is only valid for ",
 872                     sup,
 873                     "");
 874                 err
 875             }
 876             infer::SafeDestructor(span) => {
 877                 let mut err = struct_span_err!(self.tcx.sess, span, E0487,
 878                           "unsafe use of destructor: destructor might be called \
 879                            while references are dead");
 880                 // FIXME (22171): terms "super/subregion" are suboptimal
 881                 self.tcx.note_and_explain_region(&mut err,
 882                     "superregion: ",
 883                     sup,
 884                     "");
 885                 self.tcx.note_and_explain_region(&mut err,
 886                     "subregion: ",
 887                     sub,
 888                     "");
 889                 err
 890             }
 891             infer::BindingTypeIsNotValidAtDecl(span) => {
 892                 let mut err = struct_span_err!(self.tcx.sess, span, E0488,
 893                           "lifetime of variable does not enclose its declaration");
 894                 self.tcx.note_and_explain_region(&mut err,
 895                     "the variable is only valid for ",
 896                     sup,
 897                     "");
 898                 err
 899             }
 900             infer::ParameterInScope(_, span) => {
 901                 let mut err = struct_span_err!(self.tcx.sess, span, E0489,
 902                           "type/lifetime parameter not in scope here");
 903                 self.tcx.note_and_explain_region(&mut err,
 904                     "the parameter is only valid for ",
 905                     sub,
 906                     "");
 907                 err
 908             }
 909             infer::DataBorrowed(ty, span) => {
 910                 let mut err = struct_span_err!(self.tcx.sess, span, E0490,
 911                           "a value of type `{}` is borrowed for too long",
 912                           self.ty_to_string(ty));
 913                 self.tcx.note_and_explain_region(&mut err, "the type is valid for ", sub, "");
 914                 self.tcx.note_and_explain_region(&mut err, "but the borrow lasts for ", sup, "");
 915                 err
 916             }
 917             infer::ReferenceOutlivesReferent(ty, span) => {
 918                 let mut err = struct_span_err!(self.tcx.sess, span, E0491,
 919                           "in type `{}`, reference has a longer lifetime \
 920                            than the data it references",
 921                           self.ty_to_string(ty));
 922                 self.tcx.note_and_explain_region(&mut err,
 923                     "the pointer is valid for ",
 924                     sub,
 925                     "");
 926                 self.tcx.note_and_explain_region(&mut err,
 927                     "but the referenced data is only valid for ",
 928                     sup,
 929                     "");
 930                 err
 931             }
 932         }
 933     }
 934
 935     fn report_sub_sup_conflict(&self,
 936                                var_origin: RegionVariableOrigin,
 937                                sub_origin: SubregionOrigin<'tcx>,
 938                                sub_region: Region,
 939                                sup_origin: SubregionOrigin<'tcx>,
 940                                sup_region: Region) {
 941         let mut err = self.report_inference_failure(var_origin);
 942
 943         self.tcx.note_and_explain_region(&mut err,
 944             "first, the lifetime cannot outlive ",
 945             sup_region,
 946             "...");
 947
 948         self.note_region_origin(&mut err, &sup_origin);
 949
 950         self.tcx.note_and_explain_region(&mut err,
 951             "but, the lifetime must be valid for ",
 952             sub_region,
 953             "...");
 954
 955         self.note_region_origin(&mut err, &sub_origin);
 956         err.emit();
 957     }
 958
 959     fn report_processed_errors(&self,
 960                                origins: &[ProcessedErrorOrigin<'tcx>],
 961                                same_regions: &[SameRegions]) {
 962         for (i, origin) in origins.iter().enumerate() {
 963             let mut err = match *origin {
 964                 ProcessedErrorOrigin::VariableFailure(ref var_origin) =>
 965                     self.report_inference_failure(var_origin.clone()),
 966                 ProcessedErrorOrigin::ConcreteFailure(ref sr_origin, sub, sup) =>
 967                     self.report_concrete_failure(sr_origin.clone(), sub, sup),
 968             };
 969
 970             // attach the suggestion to the last such error
 971             if i == origins.len() - 1 {
 972                 self.give_suggestion(&mut err, same_regions);
 973             }
 974
 975             err.emit();
 976         }
 977     }
 978
 979     fn give_suggestion(&self, err: &mut DiagnosticBuilder, same_regions: &[SameRegions]) {
 980         let scope_id = same_regions[0].scope_id;
 981         let parent = self.tcx.map.get_parent(scope_id);
 982         let parent_node = self.tcx.map.find(parent);
 983         let taken = lifetimes_in_scope(self.tcx, scope_id);
 984         let life_giver = LifeGiver::with_taken(&taken[..]);
 985         let node_inner = match parent_node {
 986             Some(ref node) => match *node {
 987                 ast_map::NodeItem(ref item) => {
 988                     match item.node {
 989                         hir::ItemFn(ref fn_decl, unsafety, constness, _, ref gen, _) => {
 990                             Some((fn_decl, gen, unsafety, constness, item.name, item.span))
 991                         },
 992                         _ => None
 993                     }
 994                 }
 995                 ast_map::NodeImplItem(item) => {
 996                     match item.node {
 997                         hir::ImplItemKind::Method(ref sig, _) => {
 998                             Some((&sig.decl,
 999                                   &sig.generics,
1000                                   sig.unsafety,
1001                                   sig.constness,
1002                                   item.name,
1003                                   item.span))
1004                         }
1005                         _ => None,
1006                     }
1007                 },
1008                 ast_map::NodeTraitItem(item) => {
1009                     match item.node {
1010                         hir::MethodTraitItem(ref sig, Some(_)) => {
1011                             Some((&sig.decl,
1012                                   &sig.generics,
1013                                   sig.unsafety,
1014                                   sig.constness,
1015                                   item.name,
1016                                   item.span))
1017                         }
1018                         _ => None
1019                     }
1020                 }
1021                 _ => None
1022             },
1023             None => None
1024         };
1025         let (fn_decl, generics, unsafety, constness, name, span)
1026                                     = node_inner.expect("expect item fn");
1027         let rebuilder = Rebuilder::new(self.tcx, fn_decl, generics, same_regions, &life_giver);
1028         let (fn_decl, generics) = rebuilder.rebuild();
1029         self.give_expl_lifetime_param(err, &fn_decl, unsafety, constness, name, &generics, span);
1030     }
1031
1032     pub fn issue_32330_warnings(&self, span: Span, issue32330s: &[ty::Issue32330]) {
1033         for issue32330 in issue32330s {
1034             match *issue32330 {
1035                 ty::Issue32330::WontChange => { }
1036                 ty::Issue32330::WillChange { fn_def_id, region_name } => {
1037                     self.tcx.sess.add_lint(
1038                         lint::builtin::HR_LIFETIME_IN_ASSOC_TYPE,
1039                         ast::CRATE_NODE_ID,
1040                         span,
1041                         format!("lifetime parameter `{0}` declared on fn `{1}` \
1042                                  appears only in the return type, \
1043                                  but here is required to be higher-ranked, \
1044                                  which means that `{0}` must appear in both \
1045                                  argument and return types",
1046                                 region_name,
1047                                 self.tcx.item_path_str(fn_def_id)));
1048                 }
1049             }
1050         }
1051     }
1052 }
1053
1054 struct RebuildPathInfo<'a> {
1055     path: &'a hir::Path,
1056     // indexes to insert lifetime on path.lifetimes
1057     indexes: Vec<u32>,
1058     // number of lifetimes we expect to see on the type referred by `path`
1059     // (e.g., expected=1 for struct Foo<'a>)
1060     expected: u32,
1061     anon_nums: &'a HashSet<u32>,
1062     region_names: &'a HashSet<ast::Name>
1063 }
1064
1065 struct Rebuilder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
1066     tcx: TyCtxt<'a, 'gcx, 'tcx>,
1067     fn_decl: &'a hir::FnDecl,
1068     generics: &'a hir::Generics,
1069     same_regions: &'a [SameRegions],
1070     life_giver: &'a LifeGiver,
1071     cur_anon: Cell<u32>,
1072     inserted_anons: RefCell<HashSet<u32>>,
1073 }
1074
1075 enum FreshOrKept {
1076     Fresh,
1077     Kept
1078 }
1079
1080 impl<'a, 'gcx, 'tcx> Rebuilder<'a, 'gcx, 'tcx> {
1081     fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>,
1082            fn_decl: &'a hir::FnDecl,
1083            generics: &'a hir::Generics,
1084            same_regions: &'a [SameRegions],
1085            life_giver: &'a LifeGiver)
1086            -> Rebuilder<'a, 'gcx, 'tcx> {
1087         Rebuilder {
1088             tcx: tcx,
1089             fn_decl: fn_decl,
1090             generics: generics,
1091             same_regions: same_regions,
1092             life_giver: life_giver,
1093             cur_anon: Cell::new(0),
1094             inserted_anons: RefCell::new(HashSet::new()),
1095         }
1096     }
1097
1098     fn rebuild(&self) -> (hir::FnDecl, hir::Generics) {
1099         let mut inputs = self.fn_decl.inputs.clone();
1100         let mut output = self.fn_decl.output.clone();
1101         let mut ty_params = self.generics.ty_params.clone();
1102         let where_clause = self.generics.where_clause.clone();
1103         let mut kept_lifetimes = HashSet::new();
1104         for sr in self.same_regions {
1105             self.cur_anon.set(0);
1106             self.offset_cur_anon();
1107             let (anon_nums, region_names) =
1108                                 self.extract_anon_nums_and_names(sr);
1109             let (lifetime, fresh_or_kept) = self.pick_lifetime(&region_names);
1110             match fresh_or_kept {
1111                 Kept => { kept_lifetimes.insert(lifetime.name); }
1112                 _ => ()
1113             }
1114             inputs = self.rebuild_args_ty(&inputs[..], lifetime,
1115                                           &anon_nums, &region_names);
1116             output = self.rebuild_output(&output, lifetime, &anon_nums, &region_names);
1117             ty_params = self.rebuild_ty_params(ty_params, lifetime,
1118                                                &region_names);
1119         }
1120         let fresh_lifetimes = self.life_giver.get_generated_lifetimes();
1121         let all_region_names = self.extract_all_region_names();
1122         let generics = self.rebuild_generics(self.generics,
1123                                              &fresh_lifetimes,
1124                                              &kept_lifetimes,
1125                                              &all_region_names,
1126                                              ty_params,
1127                                              where_clause);
1128         let new_fn_decl = hir::FnDecl {
1129             inputs: inputs,
1130             output: output,
1131             variadic: self.fn_decl.variadic
1132         };
1133         (new_fn_decl, generics)
1134     }
1135
1136     fn pick_lifetime(&self,
1137                      region_names: &HashSet<ast::Name>)
1138                      -> (hir::Lifetime, FreshOrKept) {
1139         if !region_names.is_empty() {
1140             // It's not necessary to convert the set of region names to a
1141             // vector of string and then sort them. However, it makes the
1142             // choice of lifetime name deterministic and thus easier to test.
1143             let mut names = Vec::new();
1144             for rn in region_names {
1145                 let lt_name = rn.to_string();
1146                 names.push(lt_name);
1147             }
1148             names.sort();
1149             let name = token::intern(&names[0]);
1150             return (name_to_dummy_lifetime(name), Kept);
1151         }
1152         return (self.life_giver.give_lifetime(), Fresh);
1153     }
1154
1155     fn extract_anon_nums_and_names(&self, same_regions: &SameRegions)
1156                                    -> (HashSet<u32>, HashSet<ast::Name>) {
1157         let mut anon_nums = HashSet::new();
1158         let mut region_names = HashSet::new();
1159         for br in &same_regions.regions {
1160             match *br {
1161                 ty::BrAnon(i) => {
1162                     anon_nums.insert(i);
1163                 }
1164                 ty::BrNamed(_, name, _) => {
1165                     region_names.insert(name);
1166                 }
1167                 _ => ()
1168             }
1169         }
1170         (anon_nums, region_names)
1171     }
1172
1173     fn extract_all_region_names(&self) -> HashSet<ast::Name> {
1174         let mut all_region_names = HashSet::new();
1175         for sr in self.same_regions {
1176             for br in &sr.regions {
1177                 match *br {
1178                     ty::BrNamed(_, name, _) => {
1179                         all_region_names.insert(name);
1180                     }
1181                     _ => ()
1182                 }
1183             }
1184         }
1185         all_region_names
1186     }
1187
1188     fn inc_cur_anon(&self, n: u32) {
1189         let anon = self.cur_anon.get();
1190         self.cur_anon.set(anon+n);
1191     }
1192
1193     fn offset_cur_anon(&self) {
1194         let mut anon = self.cur_anon.get();
1195         while self.inserted_anons.borrow().contains(&anon) {
1196             anon += 1;
1197         }
1198         self.cur_anon.set(anon);
1199     }
1200
1201     fn inc_and_offset_cur_anon(&self, n: u32) {
1202         self.inc_cur_anon(n);
1203         self.offset_cur_anon();
1204     }
1205
1206     fn track_anon(&self, anon: u32) {
1207         self.inserted_anons.borrow_mut().insert(anon);
1208     }
1209
1210     fn rebuild_ty_params(&self,
1211                          ty_params: hir::HirVec<hir::TyParam>,
1212                          lifetime: hir::Lifetime,
1213                          region_names: &HashSet<ast::Name>)
1214                          -> hir::HirVec<hir::TyParam> {
1215         ty_params.iter().map(|ty_param| {
1216             let bounds = self.rebuild_ty_param_bounds(ty_param.bounds.clone(),
1217                                                       lifetime,
1218                                                       region_names);
1219             hir::TyParam {
1220                 name: ty_param.name,
1221                 id: ty_param.id,
1222                 bounds: bounds,
1223                 default: ty_param.default.clone(),
1224                 span: ty_param.span,
1225             }
1226         }).collect()
1227     }
1228
1229     fn rebuild_ty_param_bounds(&self,
1230                                ty_param_bounds: hir::TyParamBounds,
1231                                lifetime: hir::Lifetime,
1232                                region_names: &HashSet<ast::Name>)
1233                                -> hir::TyParamBounds {
1234         ty_param_bounds.iter().map(|tpb| {
1235             match tpb {
1236                 &hir::RegionTyParamBound(lt) => {
1237                     // FIXME -- it's unclear whether I'm supposed to
1238                     // substitute lifetime here. I suspect we need to
1239                     // be passing down a map.
1240                     hir::RegionTyParamBound(lt)
1241                 }
1242                 &hir::TraitTyParamBound(ref poly_tr, modifier) => {
1243                     let tr = &poly_tr.trait_ref;
1244                     let last_seg = tr.path.segments.last().unwrap();
1245                     let mut insert = Vec::new();
1246                     let lifetimes = last_seg.parameters.lifetimes();
1247                     for (i, lt) in lifetimes.iter().enumerate() {
1248                         if region_names.contains(&lt.name) {
1249                             insert.push(i as u32);
1250                         }
1251                     }
1252                     let rebuild_info = RebuildPathInfo {
1253                         path: &tr.path,
1254                         indexes: insert,
1255                         expected: lifetimes.len() as u32,
1256                         anon_nums: &HashSet::new(),
1257                         region_names: region_names
1258                     };
1259                     let new_path = self.rebuild_path(rebuild_info, lifetime);
1260                     hir::TraitTyParamBound(hir::PolyTraitRef {
1261                         bound_lifetimes: poly_tr.bound_lifetimes.clone(),
1262                         trait_ref: hir::TraitRef {
1263                             path: new_path,
1264                             ref_id: tr.ref_id,
1265                         },
1266                         span: poly_tr.span,
1267                     }, modifier)
1268                 }
1269             }
1270         }).collect()
1271     }
1272
1273     fn rebuild_generics(&self,
1274                         generics: &hir::Generics,
1275                         add: &Vec<hir::Lifetime>,
1276                         keep: &HashSet<ast::Name>,
1277                         remove: &HashSet<ast::Name>,
1278                         ty_params: hir::HirVec<hir::TyParam>,
1279                         where_clause: hir::WhereClause)
1280                         -> hir::Generics {
1281         let mut lifetimes = Vec::new();
1282         for lt in add {
1283             lifetimes.push(hir::LifetimeDef { lifetime: *lt,
1284                                               bounds: hir::HirVec::new() });
1285         }
1286         for lt in &generics.lifetimes {
1287             if keep.contains(&lt.lifetime.name) ||
1288                 !remove.contains(&lt.lifetime.name) {
1289                 lifetimes.push((*lt).clone());
1290             }
1291         }
1292         hir::Generics {
1293             lifetimes: lifetimes.into(),
1294             ty_params: ty_params,
1295             where_clause: where_clause,
1296         }
1297     }
1298
1299     fn rebuild_args_ty(&self,
1300                        inputs: &[hir::Arg],
1301                        lifetime: hir::Lifetime,
1302                        anon_nums: &HashSet<u32>,
1303                        region_names: &HashSet<ast::Name>)
1304                        -> hir::HirVec<hir::Arg> {
1305         let mut new_inputs = Vec::new();
1306         for arg in inputs {
1307             let new_ty = self.rebuild_arg_ty_or_output(&arg.ty, lifetime,
1308                                                        anon_nums, region_names);
1309             let possibly_new_arg = hir::Arg {
1310                 ty: new_ty,
1311                 pat: arg.pat.clone(),
1312                 id: arg.id
1313             };
1314             new_inputs.push(possibly_new_arg);
1315         }
1316         new_inputs.into()
1317     }
1318
1319     fn rebuild_output(&self, ty: &hir::FunctionRetTy,
1320                       lifetime: hir::Lifetime,
1321                       anon_nums: &HashSet<u32>,
1322                       region_names: &HashSet<ast::Name>) -> hir::FunctionRetTy {
1323         match *ty {
1324             hir::Return(ref ret_ty) => hir::Return(
1325                 self.rebuild_arg_ty_or_output(&ret_ty, lifetime, anon_nums, region_names)
1326             ),
1327             hir::DefaultReturn(span) => hir::DefaultReturn(span),
1328         }
1329     }
1330
1331     fn rebuild_arg_ty_or_output(&self,
1332                                 ty: &hir::Ty,
1333                                 lifetime: hir::Lifetime,
1334                                 anon_nums: &HashSet<u32>,
1335                                 region_names: &HashSet<ast::Name>)
1336                                 -> P<hir::Ty> {
1337         let mut new_ty = P(ty.clone());
1338         let mut ty_queue = vec!(ty);
1339         while !ty_queue.is_empty() {
1340             let cur_ty = ty_queue.remove(0);
1341             match cur_ty.node {
1342                 hir::TyRptr(lt_opt, ref mut_ty) => {
1343                     let rebuild = match lt_opt {
1344                         Some(lt) => region_names.contains(&lt.name),
1345                         None => {
1346                             let anon = self.cur_anon.get();
1347                             let rebuild = anon_nums.contains(&anon);
1348                             if rebuild {
1349                                 self.track_anon(anon);
1350                             }
1351                             self.inc_and_offset_cur_anon(1);
1352                             rebuild
1353                         }
1354                     };
1355                     if rebuild {
1356                         let to = hir::Ty {
1357                             id: cur_ty.id,
1358                             node: hir::TyRptr(Some(lifetime), mut_ty.clone()),
1359                             span: cur_ty.span
1360                         };
1361                         new_ty = self.rebuild_ty(new_ty, P(to));
1362                     }
1363                     ty_queue.push(&mut_ty.ty);
1364                 }
1365                 hir::TyPath(ref maybe_qself, ref path) => {
1366                     match self.tcx.expect_def(cur_ty.id) {
1367                         Def::Enum(did) | Def::TyAlias(did) | Def::Struct(did) => {
1368                             let generics = self.tcx.lookup_generics(did);
1369
1370                             let expected =
1371                                 generics.regions.len() as u32;
1372                             let lifetimes =
1373                                 path.segments.last().unwrap().parameters.lifetimes();
1374                             let mut insert = Vec::new();
1375                             if lifetimes.is_empty() {
1376                                 let anon = self.cur_anon.get();
1377                                 for (i, a) in (anon..anon+expected).enumerate() {
1378                                     if anon_nums.contains(&a) {
1379                                         insert.push(i as u32);
1380                                     }
1381                                     self.track_anon(a);
1382                                 }
1383                                 self.inc_and_offset_cur_anon(expected);
1384                             } else {
1385                                 for (i, lt) in lifetimes.iter().enumerate() {
1386                                     if region_names.contains(&lt.name) {
1387                                         insert.push(i as u32);
1388                                     }
1389                                 }
1390                             }
1391                             let rebuild_info = RebuildPathInfo {
1392                                 path: path,
1393                                 indexes: insert,
1394                                 expected: expected,
1395                                 anon_nums: anon_nums,
1396                                 region_names: region_names
1397                             };
1398                             let new_path = self.rebuild_path(rebuild_info, lifetime);
1399                             let qself = maybe_qself.as_ref().map(|qself| {
1400                                 hir::QSelf {
1401                                     ty: self.rebuild_arg_ty_or_output(&qself.ty, lifetime,
1402                                                                       anon_nums, region_names),
1403                                     position: qself.position
1404                                 }
1405                             });
1406                             let to = hir::Ty {
1407                                 id: cur_ty.id,
1408                                 node: hir::TyPath(qself, new_path),
1409                                 span: cur_ty.span
1410                             };
1411                             new_ty = self.rebuild_ty(new_ty, P(to));
1412                         }
1413                         _ => ()
1414                     }
1415                 }
1416
1417                 hir::TyPtr(ref mut_ty) => {
1418                     ty_queue.push(&mut_ty.ty);
1419                 }
1420                 hir::TyVec(ref ty) |
1421                 hir::TyFixedLengthVec(ref ty, _) => {
1422                     ty_queue.push(&ty);
1423                 }
1424                 hir::TyTup(ref tys) => ty_queue.extend(tys.iter().map(|ty| &**ty)),
1425                 _ => {}
1426             }
1427         }
1428         new_ty
1429     }
1430
1431     fn rebuild_ty(&self,
1432                   from: P<hir::Ty>,
1433                   to: P<hir::Ty>)
1434                   -> P<hir::Ty> {
1435
1436         fn build_to(from: P<hir::Ty>,
1437                     to: &mut Option<P<hir::Ty>>)
1438                     -> P<hir::Ty> {
1439             if Some(from.id) == to.as_ref().map(|ty| ty.id) {
1440                 return to.take().expect("`to` type found more than once during rebuild");
1441             }
1442             from.map(|hir::Ty {id, node, span}| {
1443                 let new_node = match node {
1444                     hir::TyRptr(lifetime, mut_ty) => {
1445                         hir::TyRptr(lifetime, hir::MutTy {
1446                             mutbl: mut_ty.mutbl,
1447                             ty: build_to(mut_ty.ty, to),
1448                         })
1449                     }
1450                     hir::TyPtr(mut_ty) => {
1451                         hir::TyPtr(hir::MutTy {
1452                             mutbl: mut_ty.mutbl,
1453                             ty: build_to(mut_ty.ty, to),
1454                         })
1455                     }
1456                     hir::TyVec(ty) => hir::TyVec(build_to(ty, to)),
1457                     hir::TyFixedLengthVec(ty, e) => {
1458                         hir::TyFixedLengthVec(build_to(ty, to), e)
1459                     }
1460                     hir::TyTup(tys) => {
1461                         hir::TyTup(tys.into_iter().map(|ty| build_to(ty, to)).collect())
1462                     }
1463                     other => other
1464                 };
1465                 hir::Ty { id: id, node: new_node, span: span }
1466             })
1467         }
1468
1469         build_to(from, &mut Some(to))
1470     }
1471
1472     fn rebuild_path(&self,
1473                     rebuild_info: RebuildPathInfo,
1474                     lifetime: hir::Lifetime)
1475                     -> hir::Path
1476     {
1477         let RebuildPathInfo {
1478             path,
1479             indexes,
1480             expected,
1481             anon_nums,
1482             region_names,
1483         } = rebuild_info;
1484
1485         let last_seg = path.segments.last().unwrap();
1486         let new_parameters = match last_seg.parameters {
1487             hir::ParenthesizedParameters(..) => {
1488                 last_seg.parameters.clone()
1489             }
1490
1491             hir::AngleBracketedParameters(ref data) => {
1492                 let mut new_lts = Vec::new();
1493                 if data.lifetimes.is_empty() {
1494                     // traverse once to see if there's a need to insert lifetime
1495                     let need_insert = (0..expected).any(|i| {
1496                         indexes.contains(&i)
1497                     });
1498                     if need_insert {
1499                         for i in 0..expected {
1500                             if indexes.contains(&i) {
1501                                 new_lts.push(lifetime);
1502                             } else {
1503                                 new_lts.push(self.life_giver.give_lifetime());
1504                             }
1505                         }
1506                     }
1507                 } else {
1508                     for (i, lt) in data.lifetimes.iter().enumerate() {
1509                         if indexes.contains(&(i as u32)) {
1510                             new_lts.push(lifetime);
1511                         } else {
1512                             new_lts.push(*lt);
1513                         }
1514                     }
1515                 }
1516                 let new_types = data.types.iter().map(|t| {
1517                     self.rebuild_arg_ty_or_output(&t, lifetime, anon_nums, region_names)
1518                 }).collect();
1519                 let new_bindings = data.bindings.iter().map(|b| {
1520                     hir::TypeBinding {
1521                         id: b.id,
1522                         name: b.name,
1523                         ty: self.rebuild_arg_ty_or_output(&b.ty,
1524                                                           lifetime,
1525                                                           anon_nums,
1526                                                           region_names),
1527                         span: b.span
1528                     }
1529                 }).collect();
1530                 hir::AngleBracketedParameters(hir::AngleBracketedParameterData {
1531                     lifetimes: new_lts.into(),
1532                     types: new_types,
1533                     bindings: new_bindings,
1534                })
1535             }
1536         };
1537         let new_seg = hir::PathSegment {
1538             name: last_seg.name,
1539             parameters: new_parameters
1540         };
1541         let mut new_segs = Vec::new();
1542         new_segs.extend_from_slice(path.segments.split_last().unwrap().1);
1543         new_segs.push(new_seg);
1544         hir::Path {
1545             span: path.span,
1546             global: path.global,
1547             segments: new_segs.into()
1548         }
1549     }
1550 }
1551
1552 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
1553     fn give_expl_lifetime_param(&self,
1554                                 err: &mut DiagnosticBuilder,
1555                                 decl: &hir::FnDecl,
1556                                 unsafety: hir::Unsafety,
1557                                 constness: hir::Constness,
1558                                 name: ast::Name,
1559                                 generics: &hir::Generics,
1560                                 span: Span) {
1561         let suggested_fn = pprust::fun_to_string(decl, unsafety, constness, name, generics);
1562         let msg = format!("consider using an explicit lifetime \
1563                            parameter as shown: {}", suggested_fn);
1564         err.span_help(span, &msg[..]);
1565     }
1566
1567     fn report_inference_failure(&self,
1568                                 var_origin: RegionVariableOrigin)
1569                                 -> DiagnosticBuilder<'tcx> {
1570         let br_string = |br: ty::BoundRegion| {
1571             let mut s = br.to_string();
1572             if !s.is_empty() {
1573                 s.push_str(" ");
1574             }
1575             s
1576         };
1577         let var_description = match var_origin {
1578             infer::MiscVariable(_) => "".to_string(),
1579             infer::PatternRegion(_) => " for pattern".to_string(),
1580             infer::AddrOfRegion(_) => " for borrow expression".to_string(),
1581             infer::Autoref(_) => " for autoref".to_string(),
1582             infer::Coercion(_) => " for automatic coercion".to_string(),
1583             infer::LateBoundRegion(_, br, infer::FnCall) => {
1584                 format!(" for lifetime parameter {}in function call",
1585                         br_string(br))
1586             }
1587             infer::LateBoundRegion(_, br, infer::HigherRankedType) => {
1588                 format!(" for lifetime parameter {}in generic type", br_string(br))
1589             }
1590             infer::LateBoundRegion(_, br, infer::AssocTypeProjection(type_name)) => {
1591                 format!(" for lifetime parameter {}in trait containing associated type `{}`",
1592                         br_string(br), type_name)
1593             }
1594             infer::EarlyBoundRegion(_, name) => {
1595                 format!(" for lifetime parameter `{}`",
1596                         name)
1597             }
1598             infer::BoundRegionInCoherence(name) => {
1599                 format!(" for lifetime parameter `{}` in coherence check",
1600                         name)
1601             }
1602             infer::UpvarRegion(ref upvar_id, _) => {
1603                 format!(" for capture of `{}` by closure",
1604                         self.tcx.local_var_name_str(upvar_id.var_id).to_string())
1605             }
1606         };
1607
1608         struct_span_err!(self.tcx.sess, var_origin.span(), E0495,
1609                   "cannot infer an appropriate lifetime{} \
1610                    due to conflicting requirements",
1611                   var_description)
1612     }
1613
1614     fn note_region_origin(&self, err: &mut DiagnosticBuilder, origin: &SubregionOrigin<'tcx>) {
1615         match *origin {
1616             infer::Subtype(ref trace) => {
1617                 if let Some((expected, found)) = self.values_str(&trace.values) {
1618                     // FIXME: do we want a "the" here?
1619                     err.span_note(
1620                         trace.origin.span(),
1621                         &format!("...so that {} (expected {}, found {})",
1622                                  trace.origin.as_requirement_str(), expected, found));
1623                 } else {
1624                     // FIXME: this really should be handled at some earlier stage. Our
1625                     // handling of region checking when type errors are present is
1626                     // *terrible*.
1627
1628                     err.span_note(
1629                         trace.origin.span(),
1630                         &format!("...so that {}",
1631                                  trace.origin.as_requirement_str()));
1632                 }
1633             }
1634             infer::Reborrow(span) => {
1635                 err.span_note(
1636                     span,
1637                     "...so that reference does not outlive \
1638                     borrowed content");
1639             }
1640             infer::ReborrowUpvar(span, ref upvar_id) => {
1641                 err.span_note(
1642                     span,
1643                     &format!(
1644                         "...so that closure can access `{}`",
1645                         self.tcx.local_var_name_str(upvar_id.var_id)
1646                             .to_string()));
1647             }
1648             infer::InfStackClosure(span) => {
1649                 err.span_note(
1650                     span,
1651                     "...so that closure does not outlive its stack frame");
1652             }
1653             infer::InvokeClosure(span) => {
1654                 err.span_note(
1655                     span,
1656                     "...so that closure is not invoked outside its lifetime");
1657             }
1658             infer::DerefPointer(span) => {
1659                 err.span_note(
1660                     span,
1661                     "...so that pointer is not dereferenced \
1662                     outside its lifetime");
1663             }
1664             infer::FreeVariable(span, id) => {
1665                 err.span_note(
1666                     span,
1667                     &format!("...so that captured variable `{}` \
1668                             does not outlive the enclosing closure",
1669                             self.tcx.local_var_name_str(id)));
1670             }
1671             infer::IndexSlice(span) => {
1672                 err.span_note(
1673                     span,
1674                     "...so that slice is not indexed outside the lifetime");
1675             }
1676             infer::RelateObjectBound(span) => {
1677                 err.span_note(
1678                     span,
1679                     "...so that it can be closed over into an object");
1680             }
1681             infer::CallRcvr(span) => {
1682                 err.span_note(
1683                     span,
1684                     "...so that method receiver is valid for the method call");
1685             }
1686             infer::CallArg(span) => {
1687                 err.span_note(
1688                     span,
1689                     "...so that argument is valid for the call");
1690             }
1691             infer::CallReturn(span) => {
1692                 err.span_note(
1693                     span,
1694                     "...so that return value is valid for the call");
1695             }
1696             infer::Operand(span) => {
1697                 err.span_note(
1698                     span,
1699                     "...so that operand is valid for operation");
1700             }
1701             infer::AddrOf(span) => {
1702                 err.span_note(
1703                     span,
1704                     "...so that reference is valid \
1705                      at the time of borrow");
1706             }
1707             infer::AutoBorrow(span) => {
1708                 err.span_note(
1709                     span,
1710                     "...so that auto-reference is valid \
1711                      at the time of borrow");
1712             }
1713             infer::ExprTypeIsNotInScope(t, span) => {
1714                 err.span_note(
1715                     span,
1716                     &format!("...so type `{}` of expression is valid during the \
1717                              expression",
1718                             self.ty_to_string(t)));
1719             }
1720             infer::BindingTypeIsNotValidAtDecl(span) => {
1721                 err.span_note(
1722                     span,
1723                     "...so that variable is valid at time of its declaration");
1724             }
1725             infer::ParameterInScope(_, span) => {
1726                 err.span_note(
1727                     span,
1728                     "...so that a type/lifetime parameter is in scope here");
1729             }
1730             infer::DataBorrowed(ty, span) => {
1731                 err.span_note(
1732                     span,
1733                     &format!("...so that the type `{}` is not borrowed for too long",
1734                              self.ty_to_string(ty)));
1735             }
1736             infer::ReferenceOutlivesReferent(ty, span) => {
1737                 err.span_note(
1738                     span,
1739                     &format!("...so that the reference type `{}` \
1740                              does not outlive the data it points at",
1741                             self.ty_to_string(ty)));
1742             }
1743             infer::RelateParamBound(span, t) => {
1744                 err.span_note(
1745                     span,
1746                     &format!("...so that the type `{}` \
1747                              will meet its required lifetime bounds",
1748                             self.ty_to_string(t)));
1749             }
1750             infer::RelateDefaultParamBound(span, t) => {
1751                 err.span_note(
1752                     span,
1753                     &format!("...so that type parameter \
1754                              instantiated with `{}`, \
1755                              will meet its declared lifetime bounds",
1756                             self.ty_to_string(t)));
1757             }
1758             infer::RelateRegionParamBound(span) => {
1759                 err.span_note(
1760                     span,
1761                     "...so that the declared lifetime parameter bounds \
1762                                 are satisfied");
1763             }
1764             infer::SafeDestructor(span) => {
1765                 err.span_note(
1766                     span,
1767                     "...so that references are valid when the destructor \
1768                      runs");
1769             }
1770         }
1771     }
1772 }
1773
1774 fn lifetimes_in_scope<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
1775                                       scope_id: ast::NodeId)
1776                                       -> Vec<hir::LifetimeDef> {
1777     let mut taken = Vec::new();
1778     let parent = tcx.map.get_parent(scope_id);
1779     let method_id_opt = match tcx.map.find(parent) {
1780         Some(node) => match node {
1781             ast_map::NodeItem(item) => match item.node {
1782                 hir::ItemFn(_, _, _, _, ref gen, _) => {
1783                     taken.extend_from_slice(&gen.lifetimes);
1784                     None
1785                 },
1786                 _ => None
1787             },
1788             ast_map::NodeImplItem(ii) => {
1789                 match ii.node {
1790                     hir::ImplItemKind::Method(ref sig, _) => {
1791                         taken.extend_from_slice(&sig.generics.lifetimes);
1792                         Some(ii.id)
1793                     }
1794                     _ => None,
1795                 }
1796             }
1797             _ => None
1798         },
1799         None => None
1800     };
1801     if let Some(method_id) = method_id_opt {
1802         let parent = tcx.map.get_parent(method_id);
1803         if let Some(node) = tcx.map.find(parent) {
1804             match node {
1805                 ast_map::NodeItem(item) => match item.node {
1806                     hir::ItemImpl(_, _, ref gen, _, _, _) => {
1807                         taken.extend_from_slice(&gen.lifetimes);
1808                     }
1809                     _ => ()
1810                 },
1811                 _ => ()
1812             }
1813         }
1814     }
1815     return taken;
1816 }
1817
1818 // LifeGiver is responsible for generating fresh lifetime names
1819 struct LifeGiver {
1820     taken: HashSet<String>,
1821     counter: Cell<usize>,
1822     generated: RefCell<Vec<hir::Lifetime>>,
1823 }
1824
1825 impl LifeGiver {
1826     fn with_taken(taken: &[hir::LifetimeDef]) -> LifeGiver {
1827         let mut taken_ = HashSet::new();
1828         for lt in taken {
1829             let lt_name = lt.lifetime.name.to_string();
1830             taken_.insert(lt_name);
1831         }
1832         LifeGiver {
1833             taken: taken_,
1834             counter: Cell::new(0),
1835             generated: RefCell::new(Vec::new()),
1836         }
1837     }
1838
1839     fn inc_counter(&self) {
1840         let c = self.counter.get();
1841         self.counter.set(c+1);
1842     }
1843
1844     fn give_lifetime(&self) -> hir::Lifetime {
1845         let lifetime;
1846         loop {
1847             let mut s = String::from("'");
1848             s.push_str(&num_to_string(self.counter.get()));
1849             if !self.taken.contains(&s) {
1850                 lifetime = name_to_dummy_lifetime(token::intern(&s[..]));
1851                 self.generated.borrow_mut().push(lifetime);
1852                 break;
1853             }
1854             self.inc_counter();
1855         }
1856         self.inc_counter();
1857         return lifetime;
1858
1859         // 0 .. 25 generates a .. z, 26 .. 51 generates aa .. zz, and so on
1860         fn num_to_string(counter: usize) -> String {
1861             let mut s = String::new();
1862             let (n, r) = (counter/26 + 1, counter % 26);
1863             let letter: char = from_u32((r+97) as u32).unwrap();
1864             for _ in 0..n {
1865                 s.push(letter);
1866             }
1867             s
1868         }
1869     }
1870
1871     fn get_generated_lifetimes(&self) -> Vec<hir::Lifetime> {
1872         self.generated.borrow().clone()
1873     }
1874 }
1875
1876 fn name_to_dummy_lifetime(name: ast::Name) -> hir::Lifetime {
1877     hir::Lifetime { id: ast::DUMMY_NODE_ID,
1878                     span: syntax_pos::DUMMY_SP,
1879                     name: name }
1880 }