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