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