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