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