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