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