src/librustc/middle/typeck/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 /*!
  12
  13 Error Reporting Code for the inference engine
  14
  15 Because of the way inference, and in particular region inference,
  16 works, it often happens that errors are not detected until far after
  17 the relevant line of code has been type-checked. Therefore, there is
  18 an elaborate system to track why a particular constraint in the
  19 inference graph arose so that we can explain to the user what gave
  20 rise to a patricular error.
  21
  22 The basis of the system are the "origin" types. An "origin" is the
  23 reason that a constraint or inference variable arose. There are
  24 different "origin" enums for different kinds of constraints/variables
  25 (e.g., `TypeOrigin`, `RegionVariableOrigin`). An origin always has
  26 a span, but also more information so that we can generate a meaningful
  27 error message.
  28
  29 Having a catalogue of all the different reasons an error can arise is
  30 also useful for other reasons, like cross-referencing FAQs etc, though
  31 we are not really taking advantage of this yet.
  32
  33 # Region Inference
  34
  35 Region inference is particularly tricky because it always succeeds "in
  36 the moment" and simply registers a constraint. Then, at the end, we
  37 can compute the full graph and report errors, so we need to be able to
  38 store and later report what gave rise to the conflicting constraints.
  39
  40 # Subtype Trace
  41
  42 Determing whether `T1 <: T2` often involves a number of subtypes and
  43 subconstraints along the way. A "TypeTrace" is an extended version
  44 of an origin that traces the types and other values that were being
  45 compared. It is not necessarily comprehensive (in fact, at the time of
  46 this writing it only tracks the root values being compared) but I'd
  47 like to extend it to include significant "waypoints". For example, if
  48 you are comparing `(T1, T2) <: (T3, T4)`, and the problem is that `T2
  49 <: T4` fails, I'd like the trace to include enough information to say
  50 "in the 2nd element of the tuple". Similarly, failures when comparing
  51 arguments or return types in fn types should be able to cite the
  52 specific position, etc.
  53
  54 # Reality vs plan
  55
  56 Of course, there is still a LOT of code in typeck that has yet to be
  57 ported to this system, and which relies on string concatenation at the
  58 time of error detection.
  59
  60 */
  61
  62 use collections::HashSet;
  63 use middle::ty;
  64 use middle::ty::{Region, ReFree};
  65 use middle::typeck::infer;
  66 use middle::typeck::infer::InferCtxt;
  67 use middle::typeck::infer::TypeTrace;
  68 use middle::typeck::infer::SubregionOrigin;
  69 use middle::typeck::infer::RegionVariableOrigin;
  70 use middle::typeck::infer::ValuePairs;
  71 use middle::typeck::infer::region_inference::RegionResolutionError;
  72 use middle::typeck::infer::region_inference::ConcreteFailure;
  73 use middle::typeck::infer::region_inference::SubSupConflict;
  74 use middle::typeck::infer::region_inference::SupSupConflict;
  75 use middle::typeck::infer::region_inference::ProcessedErrors;
  76 use middle::typeck::infer::region_inference::SameRegions;
  77 use std::cell::{Cell, RefCell};
  78 use std::char::from_u32;
  79 use std::strbuf::StrBuf;
  80 use syntax::ast;
  81 use syntax::ast_map;
  82 use syntax::ast_util;
  83 use syntax::ast_util::name_to_dummy_lifetime;
  84 use syntax::owned_slice::OwnedSlice;
  85 use syntax::parse::token;
  86 use syntax::print::pprust;
  87 use util::ppaux::UserString;
  88 use util::ppaux::bound_region_to_str;
  89 use util::ppaux::note_and_explain_region;
  90
  91 pub trait ErrorReporting {
  92     fn report_region_errors(&self,
  93                             errors: &Vec<RegionResolutionError>);
  94
  95     fn process_errors(&self, errors: &Vec<RegionResolutionError>)
  96                       -> Vec<RegionResolutionError>;
  97
  98     fn report_type_error(&self, trace: TypeTrace, terr: &ty::type_err);
  99
 100     fn report_and_explain_type_error(&self,
 101                                      trace: TypeTrace,
 102                                      terr: &ty::type_err);
 103
 104     fn values_str(&self, values: &ValuePairs) -> Option<~str>;
 105
 106     fn expected_found_str<T:UserString+Resolvable>(
 107         &self,
 108         exp_found: &ty::expected_found<T>)
 109         -> Option<~str>;
 110
 111     fn report_concrete_failure(&self,
 112                                origin: SubregionOrigin,
 113                                sub: Region,
 114                                sup: Region);
 115
 116     fn report_sub_sup_conflict(&self,
 117                                var_origin: RegionVariableOrigin,
 118                                sub_origin: SubregionOrigin,
 119                                sub_region: Region,
 120                                sup_origin: SubregionOrigin,
 121                                sup_region: Region);
 122
 123     fn report_sup_sup_conflict(&self,
 124                                var_origin: RegionVariableOrigin,
 125                                origin1: SubregionOrigin,
 126                                region1: Region,
 127                                origin2: SubregionOrigin,
 128                                region2: Region);
 129
 130     fn report_processed_errors(&self,
 131                                var_origin: &[RegionVariableOrigin],
 132                                trace_origin: &[(TypeTrace, ty::type_err)],
 133                                same_regions: &[SameRegions]);
 134
 135     fn give_suggestion(&self, same_regions: &[SameRegions]);
 136 }
 137
 138 trait ErrorReportingHelpers {
 139     fn report_inference_failure(&self,
 140                                 var_origin: RegionVariableOrigin);
 141
 142     fn note_region_origin(&self,
 143                           origin: SubregionOrigin);
 144
 145     fn give_expl_lifetime_param(&self,
 146                                 inputs: Vec<ast::Arg>,
 147                                 output: ast::P<ast::Ty>,
 148                                 item: ast::P<ast::Item>,
 149                                 generics: ast::Generics);
 150 }
 151
 152 impl<'a> ErrorReporting for InferCtxt<'a> {
 153     fn report_region_errors(&self,
 154                             errors: &Vec<RegionResolutionError>) {
 155         let p_errors = self.process_errors(errors);
 156         let errors = if p_errors.is_empty() { errors } else { &p_errors };
 157         for error in errors.iter() {
 158             match *error {
 159                 ConcreteFailure(origin, sub, sup) => {
 160                     self.report_concrete_failure(origin, sub, sup);
 161                 }
 162
 163                 SubSupConflict(var_origin,
 164                                sub_origin, sub_r,
 165                                sup_origin, sup_r) => {
 166                     self.report_sub_sup_conflict(var_origin,
 167                                                  sub_origin, sub_r,
 168                                                  sup_origin, sup_r);
 169                 }
 170
 171                 SupSupConflict(var_origin,
 172                                origin1, r1,
 173                                origin2, r2) => {
 174                     self.report_sup_sup_conflict(var_origin,
 175                                                  origin1, r1,
 176                                                  origin2, r2);
 177                 }
 178
 179                 ProcessedErrors(ref var_origins,
 180                                 ref trace_origins,
 181                                 ref same_regions) => {
 182                     if !same_regions.is_empty() {
 183                         self.report_processed_errors(var_origins.as_slice(),
 184                                                      trace_origins.as_slice(),
 185                                                      same_regions.as_slice());
 186                     }
 187                 }
 188             }
 189         }
 190     }
 191
 192     // This method goes through all the errors and try to group certain types
 193     // of error together, for the purpose of suggesting explicit lifetime
 194     // parameters to the user. This is done so that we can have a more
 195     // complete view of what lifetimes should be the same.
 196     // If the return value is an empty vector, it means that processing
 197     // failed (so the return value of this method should not be used)
 198     fn process_errors(&self, errors: &Vec<RegionResolutionError>)
 199                       -> Vec<RegionResolutionError> {
 200         debug!("process_errors()");
 201         let mut var_origins = Vec::new();
 202         let mut trace_origins = Vec::new();
 203         let mut same_regions = Vec::new();
 204         let mut processed_errors = Vec::new();
 205         for error in errors.iter() {
 206             match *error {
 207                 ConcreteFailure(origin, sub, sup) => {
 208                     debug!("processing ConcreteFailure")
 209                     let trace = match origin {
 210                         infer::Subtype(trace) => Some(trace),
 211                         _ => None,
 212                     };
 213                     match free_regions_from_same_fn(self.tcx, sub, sup) {
 214                         Some(ref same_frs) if trace.is_some() => {
 215                             let trace = trace.unwrap();
 216                             let terr = ty::terr_regions_does_not_outlive(sup,
 217                                                                          sub);
 218                             trace_origins.push((trace, terr));
 219                             append_to_same_regions(&mut same_regions, same_frs);
 220                         }
 221                         _ => processed_errors.push((*error).clone()),
 222                     }
 223                 }
 224                 SubSupConflict(var_origin, _, sub_r, _, sup_r) => {
 225                     debug!("processing SubSupConflict")
 226                     match free_regions_from_same_fn(self.tcx, sub_r, sup_r) {
 227                         Some(ref same_frs) => {
 228                             var_origins.push(var_origin);
 229                             append_to_same_regions(&mut same_regions, same_frs);
 230                         }
 231                         None => processed_errors.push((*error).clone()),
 232                     }
 233                 }
 234                 SupSupConflict(..) => processed_errors.push((*error).clone()),
 235                 _ => ()  // This shouldn't happen
 236             }
 237         }
 238         if !same_regions.is_empty() {
 239             let common_scope_id = same_regions.get(0).scope_id;
 240             for sr in same_regions.iter() {
 241                 // Since ProcessedErrors is used to reconstruct the function
 242                 // declaration, we want to make sure that they are, in fact,
 243                 // from the same scope
 244                 if sr.scope_id != common_scope_id {
 245                     debug!("returning empty result from process_errors because
 246                             {} != {}", sr.scope_id, common_scope_id);
 247                     return vec!();
 248                 }
 249             }
 250             let pe = ProcessedErrors(var_origins, trace_origins, same_regions);
 251             debug!("errors processed: {:?}", pe);
 252             processed_errors.push(pe);
 253         }
 254         return processed_errors;
 255
 256
 257         struct FreeRegionsFromSameFn {
 258             sub_fr: ty::FreeRegion,
 259             sup_fr: ty::FreeRegion,
 260             scope_id: ast::NodeId
 261         }
 262
 263         fn free_regions_from_same_fn(tcx: &ty::ctxt,
 264                                      sub: Region,
 265                                      sup: Region)
 266                                      -> Option<FreeRegionsFromSameFn> {
 267             debug!("free_regions_from_same_fn(sub={:?}, sup={:?})", sub, sup);
 268             let (scope_id, fr1, fr2) = match (sub, sup) {
 269                 (ReFree(fr1), ReFree(fr2)) => {
 270                     if fr1.scope_id != fr2.scope_id {
 271                         return None
 272                     }
 273                     assert!(fr1.scope_id == fr2.scope_id);
 274                     (fr1.scope_id, fr1, fr2)
 275                 },
 276                 _ => return None
 277             };
 278             let parent = tcx.map.get_parent(scope_id);
 279             let parent_node = tcx.map.find(parent);
 280             match parent_node {
 281                 Some(node) => match node {
 282                     ast_map::NodeItem(item) => match item.node {
 283                         // FIXME: handle method
 284                         ast::ItemFn(..) => {
 285                             let fr_from_same_fn = FreeRegionsFromSameFn {
 286                                 sub_fr: fr1,
 287                                 sup_fr: fr2,
 288                                 scope_id: scope_id
 289                             };
 290                             Some(fr_from_same_fn)
 291                         },
 292                         _ => None
 293                     },
 294                     _ => None
 295                 },
 296                 None => {
 297                     debug!("no parent node of scope_id {}", scope_id)
 298                     None
 299                 }
 300             }
 301         }
 302
 303         fn append_to_same_regions(same_regions: &mut Vec<SameRegions>,
 304                                   same_frs: &FreeRegionsFromSameFn) {
 305             let scope_id = same_frs.scope_id;
 306             let (sub_fr, sup_fr) = (same_frs.sub_fr, same_frs.sup_fr);
 307             for sr in same_regions.mut_iter() {
 308                 if sr.contains(&sup_fr.bound_region)
 309                    && scope_id == sr.scope_id {
 310                     sr.push(sub_fr.bound_region);
 311                     return
 312                 }
 313             }
 314             same_regions.push(SameRegions {
 315                 scope_id: scope_id,
 316                 regions: vec!(sub_fr.bound_region, sup_fr.bound_region)
 317             })
 318         }
 319     }
 320
 321     fn report_type_error(&self, trace: TypeTrace, terr: &ty::type_err) {
 322         let expected_found_str = match self.values_str(&trace.values) {
 323             Some(v) => v,
 324             None => {
 325                 return; /* derived error */
 326             }
 327         };
 328
 329         let message_root_str = match trace.origin {
 330             infer::Misc(_) => "mismatched types",
 331             infer::MethodCompatCheck(_) => "method not compatible with trait",
 332             infer::ExprAssignable(_) => "mismatched types",
 333             infer::RelateTraitRefs(_) => "mismatched traits",
 334             infer::RelateSelfType(_) => "mismatched types",
 335             infer::MatchExpression(_) => "match arms have incompatible types",
 336             infer::IfExpression(_) => "if and else have incompatible types",
 337         };
 338
 339         self.tcx.sess.span_err(
 340             trace.origin.span(),
 341             format!("{}: {} ({})",
 342                  message_root_str,
 343                  expected_found_str,
 344                  ty::type_err_to_str(self.tcx, terr)));
 345     }
 346
 347     fn report_and_explain_type_error(&self,
 348                                      trace: TypeTrace,
 349                                      terr: &ty::type_err) {
 350         self.report_type_error(trace, terr);
 351         ty::note_and_explain_type_err(self.tcx, terr);
 352     }
 353
 354     fn values_str(&self, values: &ValuePairs) -> Option<~str> {
 355         /*!
 356          * Returns a string of the form "expected `{}` but found `{}`",
 357          * or None if this is a derived error.
 358          */
 359         match *values {
 360             infer::Types(ref exp_found) => {
 361                 self.expected_found_str(exp_found)
 362             }
 363             infer::TraitRefs(ref exp_found) => {
 364                 self.expected_found_str(exp_found)
 365             }
 366         }
 367     }
 368
 369     fn expected_found_str<T:UserString+Resolvable>(
 370         &self,
 371         exp_found: &ty::expected_found<T>)
 372         -> Option<~str>
 373     {
 374         let expected = exp_found.expected.resolve(self);
 375         if expected.contains_error() {
 376             return None;
 377         }
 378
 379         let found = exp_found.found.resolve(self);
 380         if found.contains_error() {
 381             return None;
 382         }
 383
 384         Some(format!("expected `{}` but found `{}`",
 385                   expected.user_string(self.tcx),
 386                   found.user_string(self.tcx)))
 387     }
 388
 389     fn report_concrete_failure(&self,
 390                                origin: SubregionOrigin,
 391                                sub: Region,
 392                                sup: Region) {
 393         match origin {
 394             infer::Subtype(trace) => {
 395                 let terr = ty::terr_regions_does_not_outlive(sup, sub);
 396                 self.report_and_explain_type_error(trace, &terr);
 397             }
 398             infer::Reborrow(span) => {
 399                 self.tcx.sess.span_err(
 400                     span,
 401                     "lifetime of reference outlines \
 402                      lifetime of borrowed content...");
 403                 note_and_explain_region(
 404                     self.tcx,
 405                     "...the reference is valid for ",
 406                     sub,
 407                     "...");
 408                 note_and_explain_region(
 409                     self.tcx,
 410                     "...but the borrowed content is only valid for ",
 411                     sup,
 412                     "");
 413             }
 414             infer::ReborrowUpvar(span, ref upvar_id) => {
 415                 self.tcx.sess.span_err(
 416                     span,
 417                     format!("lifetime of borrowed pointer outlives \
 418                             lifetime of captured variable `{}`...",
 419                             ty::local_var_name_str(self.tcx, upvar_id.var_id).get().to_str()));
 420                 note_and_explain_region(
 421                     self.tcx,
 422                     "...the borrowed pointer is valid for ",
 423                     sub,
 424                     "...");
 425                 note_and_explain_region(
 426                     self.tcx,
 427                     format!("...but `{}` is only valid for ",
 428                             ty::local_var_name_str(self.tcx, upvar_id.var_id).get().to_str()),
 429                     sup,
 430                     "");
 431             }
 432             infer::InfStackClosure(span) => {
 433                 self.tcx.sess.span_err(
 434                     span,
 435                     "closure outlives stack frame");
 436                 note_and_explain_region(
 437                     self.tcx,
 438                     "...the closure must be valid for ",
 439                     sub,
 440                     "...");
 441                 note_and_explain_region(
 442                     self.tcx,
 443                     "...but the closure's stack frame is only valid for ",
 444                     sup,
 445                     "");
 446             }
 447             infer::InvokeClosure(span) => {
 448                 self.tcx.sess.span_err(
 449                     span,
 450                     "cannot invoke closure outside of its lifetime");
 451                 note_and_explain_region(
 452                     self.tcx,
 453                     "the closure is only valid for ",
 454                     sup,
 455                     "");
 456             }
 457             infer::DerefPointer(span) => {
 458                 self.tcx.sess.span_err(
 459                     span,
 460                     "dereference of reference outside its lifetime");
 461                 note_and_explain_region(
 462                     self.tcx,
 463                     "the reference is only valid for ",
 464                     sup,
 465                     "");
 466             }
 467             infer::FreeVariable(span, id) => {
 468                 self.tcx.sess.span_err(
 469                     span,
 470                     format!("captured variable `{}` does not \
 471                             outlive the enclosing closure",
 472                             ty::local_var_name_str(self.tcx, id).get().to_str()));
 473                 note_and_explain_region(
 474                     self.tcx,
 475                     "captured variable is valid for ",
 476                     sup,
 477                     "");
 478                 note_and_explain_region(
 479                     self.tcx,
 480                     "closure is valid for ",
 481                     sub,
 482                     "");
 483             }
 484             infer::IndexSlice(span) => {
 485                 self.tcx.sess.span_err(
 486                     span,
 487                     format!("index of slice outside its lifetime"));
 488                 note_and_explain_region(
 489                     self.tcx,
 490                     "the slice is only valid for ",
 491                     sup,
 492                     "");
 493             }
 494             infer::RelateObjectBound(span) => {
 495                 self.tcx.sess.span_err(
 496                     span,
 497                     "lifetime of the source pointer does not outlive \
 498                      lifetime bound of the object type");
 499                 note_and_explain_region(
 500                     self.tcx,
 501                     "object type is valid for ",
 502                     sub,
 503                     "");
 504                 note_and_explain_region(
 505                     self.tcx,
 506                     "source pointer is only valid for ",
 507                     sup,
 508                     "");
 509             }
 510             infer::CallRcvr(span) => {
 511                 self.tcx.sess.span_err(
 512                     span,
 513                     "lifetime of method receiver does not outlive \
 514                      the method call");
 515                 note_and_explain_region(
 516                     self.tcx,
 517                     "the receiver is only valid for ",
 518                     sup,
 519                     "");
 520             }
 521             infer::CallArg(span) => {
 522                 self.tcx.sess.span_err(
 523                     span,
 524                     "lifetime of function argument does not outlive \
 525                      the function call");
 526                 note_and_explain_region(
 527                     self.tcx,
 528                     "the function argument is only valid for ",
 529                     sup,
 530                     "");
 531             }
 532             infer::CallReturn(span) => {
 533                 self.tcx.sess.span_err(
 534                     span,
 535                     "lifetime of return value does not outlive \
 536                      the function call");
 537                 note_and_explain_region(
 538                     self.tcx,
 539                     "the return value is only valid for ",
 540                     sup,
 541                     "");
 542             }
 543             infer::AddrOf(span) => {
 544                 self.tcx.sess.span_err(
 545                     span,
 546                     "reference is not valid \
 547                      at the time of borrow");
 548                 note_and_explain_region(
 549                     self.tcx,
 550                     "the borrow is only valid for ",
 551                     sup,
 552                     "");
 553             }
 554             infer::AutoBorrow(span) => {
 555                 self.tcx.sess.span_err(
 556                     span,
 557                     "automatically reference is not valid \
 558                      at the time of borrow");
 559                 note_and_explain_region(
 560                     self.tcx,
 561                     "the automatic borrow is only valid for ",
 562                     sup,
 563                     "");
 564             }
 565             infer::BindingTypeIsNotValidAtDecl(span) => {
 566                 self.tcx.sess.span_err(
 567                     span,
 568                     "lifetime of variable does not enclose its declaration");
 569                 note_and_explain_region(
 570                     self.tcx,
 571                     "the variable is only valid for ",
 572                     sup,
 573                     "");
 574             }
 575             infer::ReferenceOutlivesReferent(ty, span) => {
 576                 self.tcx.sess.span_err(
 577                     span,
 578                     format!("in type `{}`, pointer has a longer lifetime than \
 579                           the data it references",
 580                          ty.user_string(self.tcx)));
 581                 note_and_explain_region(
 582                     self.tcx,
 583                     "the pointer is valid for ",
 584                     sub,
 585                     "");
 586                 note_and_explain_region(
 587                     self.tcx,
 588                     "but the referenced data is only valid for ",
 589                     sup,
 590                     "");
 591             }
 592         }
 593     }
 594
 595     fn report_sub_sup_conflict(&self,
 596                                var_origin: RegionVariableOrigin,
 597                                sub_origin: SubregionOrigin,
 598                                sub_region: Region,
 599                                sup_origin: SubregionOrigin,
 600                                sup_region: Region) {
 601         self.report_inference_failure(var_origin);
 602
 603         note_and_explain_region(
 604             self.tcx,
 605             "first, the lifetime cannot outlive ",
 606             sup_region,
 607             "...");
 608
 609         self.note_region_origin(sup_origin);
 610
 611         note_and_explain_region(
 612             self.tcx,
 613             "but, the lifetime must be valid for ",
 614             sub_region,
 615             "...");
 616
 617         self.note_region_origin(sub_origin);
 618     }
 619
 620     fn report_sup_sup_conflict(&self,
 621                                var_origin: RegionVariableOrigin,
 622                                origin1: SubregionOrigin,
 623                                region1: Region,
 624                                origin2: SubregionOrigin,
 625                                region2: Region) {
 626         self.report_inference_failure(var_origin);
 627
 628         note_and_explain_region(
 629             self.tcx,
 630             "first, the lifetime must be contained by ",
 631             region1,
 632             "...");
 633
 634         self.note_region_origin(origin1);
 635
 636         note_and_explain_region(
 637             self.tcx,
 638             "but, the lifetime must also be contained by ",
 639             region2,
 640             "...");
 641
 642         self.note_region_origin(origin2);
 643     }
 644
 645     fn report_processed_errors(&self,
 646                                var_origins: &[RegionVariableOrigin],
 647                                trace_origins: &[(TypeTrace, ty::type_err)],
 648                                same_regions: &[SameRegions]) {
 649         self.give_suggestion(same_regions);
 650         for vo in var_origins.iter() {
 651             self.report_inference_failure(*vo);
 652         }
 653         for &(trace, terr) in trace_origins.iter() {
 654             self.report_type_error(trace, &terr);
 655         }
 656     }
 657
 658     fn give_suggestion(&self, same_regions: &[SameRegions]) {
 659         let scope_id = same_regions[0].scope_id;
 660         let parent = self.tcx.map.get_parent(scope_id);
 661         let parent_node = self.tcx.map.find(parent);
 662         let node_inner = match parent_node {
 663             Some(node) => match node {
 664                 ast_map::NodeItem(item) => match item.node {
 665                     // FIXME: handling method
 666                     ast::ItemFn(ref fn_decl, _, _, ref gen, _) => {
 667                         Some((item, fn_decl, gen))
 668                     },
 669                     _ => None
 670                 },
 671                 _ => None
 672             },
 673             None => None
 674         };
 675         let (item, fn_decl, generics) = node_inner.expect("expect item fn");
 676         let rebuilder = Rebuilder::new(self.tcx, *fn_decl,
 677                                        generics, same_regions);
 678         let (inputs, output, generics) = rebuilder.rebuild();
 679         self.give_expl_lifetime_param(inputs, output, item, generics);
 680     }
 681 }
 682
 683 struct RebuildPathInfo<'a> {
 684     path: &'a ast::Path,
 685     // indexes to insert lifetime on path.lifetimes
 686     indexes: Vec<uint>,
 687     // number of lifetimes we expect to see on the type referred by `path`
 688     // (e.g., expected=1 for struct Foo<'a>)
 689     expected: uint,
 690     anon_nums: &'a HashSet<uint>,
 691     region_names: &'a HashSet<ast::Name>
 692 }
 693
 694 struct Rebuilder<'a> {
 695     tcx: &'a ty::ctxt,
 696     fn_decl: ast::P<ast::FnDecl>,
 697     generics: &'a ast::Generics,
 698     same_regions: &'a [SameRegions],
 699     life_giver: LifeGiver,
 700     cur_anon: Cell<uint>,
 701     inserted_anons: RefCell<HashSet<uint>>,
 702 }
 703
 704 impl<'a> Rebuilder<'a> {
 705     fn new(tcx: &'a ty::ctxt,
 706            fn_decl: ast::P<ast::FnDecl>,
 707            generics: &'a ast::Generics,
 708            same_regions: &'a [SameRegions])
 709            -> Rebuilder<'a> {
 710         Rebuilder {
 711             tcx: tcx,
 712             fn_decl: fn_decl,
 713             generics: generics,
 714             same_regions: same_regions,
 715             life_giver: LifeGiver::with_taken(generics.lifetimes.as_slice()),
 716             cur_anon: Cell::new(0),
 717             inserted_anons: RefCell::new(HashSet::new()),
 718         }
 719     }
 720
 721     fn rebuild(&self) -> (Vec<ast::Arg>, ast::P<ast::Ty>, ast::Generics) {
 722         let mut inputs = self.fn_decl.inputs.clone();
 723         let mut output = self.fn_decl.output;
 724         let mut ty_params = self.generics.ty_params.clone();
 725         for sr in self.same_regions.iter() {
 726             self.cur_anon.set(0);
 727             self.offset_cur_anon();
 728             let (anon_nums, region_names) =
 729                                 self.extract_anon_nums_and_names(sr);
 730             let lifetime = self.life_giver.give_lifetime();
 731             inputs = self.rebuild_args_ty(inputs.as_slice(), lifetime,
 732                                           &anon_nums, &region_names);
 733             output = self.rebuild_arg_ty_or_output(output, lifetime,
 734                                                    &anon_nums, &region_names);
 735             ty_params = self.rebuild_ty_params(ty_params, lifetime,
 736                                                &region_names);
 737         }
 738         let generated_lifetimes = self.life_giver.get_generated_lifetimes();
 739         let all_region_names = self.extract_all_region_names();
 740         let generics = self.rebuild_generics(self.generics,
 741                                              generated_lifetimes,
 742                                              &all_region_names, ty_params);
 743         (inputs, output, generics)
 744     }
 745
 746     fn extract_anon_nums_and_names(&self, same_regions: &SameRegions)
 747                                    -> (HashSet<uint>, HashSet<ast::Name>) {
 748         let mut anon_nums = HashSet::new();
 749         let mut region_names = HashSet::new();
 750         for br in same_regions.regions.iter() {
 751             match *br {
 752                 ty::BrAnon(i) => {
 753                     anon_nums.insert(i);
 754                 }
 755                 ty::BrNamed(_, name) => {
 756                     region_names.insert(name);
 757                 }
 758                 _ => ()
 759             }
 760         }
 761         (anon_nums, region_names)
 762     }
 763
 764     fn extract_all_region_names(&self) -> HashSet<ast::Name> {
 765         let mut all_region_names = HashSet::new();
 766         for sr in self.same_regions.iter() {
 767             for br in sr.regions.iter() {
 768                 match *br {
 769                     ty::BrNamed(_, name) => {
 770                         all_region_names.insert(name);
 771                     }
 772                     _ => ()
 773                 }
 774             }
 775         }
 776         all_region_names
 777     }
 778
 779     fn inc_cur_anon(&self, n: uint) {
 780         let anon = self.cur_anon.get();
 781         self.cur_anon.set(anon+n);
 782     }
 783
 784     fn offset_cur_anon(&self) {
 785         let mut anon = self.cur_anon.get();
 786         while self.inserted_anons.borrow().contains(&anon) {
 787             anon += 1;
 788         }
 789         self.cur_anon.set(anon);
 790     }
 791
 792     fn inc_and_offset_cur_anon(&self, n: uint) {
 793         self.inc_cur_anon(n);
 794         self.offset_cur_anon();
 795     }
 796
 797     fn track_anon(&self, anon: uint) {
 798         self.inserted_anons.borrow_mut().insert(anon);
 799     }
 800
 801     fn rebuild_ty_params(&self,
 802                          ty_params: OwnedSlice<ast::TyParam>,
 803                          lifetime: ast::Lifetime,
 804                          region_names: &HashSet<ast::Name>)
 805                          -> OwnedSlice<ast::TyParam> {
 806         ty_params.map(|ty_param| {
 807             let bounds = self.rebuild_ty_param_bounds(ty_param.bounds.clone(),
 808                                                       lifetime,
 809                                                       region_names);
 810             ast::TyParam {
 811                 ident: ty_param.ident,
 812                 id: ty_param.id,
 813                 bounds: bounds,
 814                 default: ty_param.default,
 815             }
 816         })
 817     }
 818
 819     fn rebuild_ty_param_bounds(&self,
 820                                ty_param_bounds: OwnedSlice<ast::TyParamBound>,
 821                                lifetime: ast::Lifetime,
 822                                region_names: &HashSet<ast::Name>)
 823                                -> OwnedSlice<ast::TyParamBound> {
 824         ty_param_bounds.map(|tpb| {
 825             match tpb {
 826                 &ast::RegionTyParamBound => ast::RegionTyParamBound,
 827                 &ast::TraitTyParamBound(ref tr) => {
 828                     let last_seg = tr.path.segments.last().unwrap();
 829                     let mut insert = Vec::new();
 830                     for (i, lt) in last_seg.lifetimes.iter().enumerate() {
 831                         if region_names.contains(&lt.name) {
 832                             insert.push(i);
 833                         }
 834                     }
 835                     let rebuild_info = RebuildPathInfo {
 836                         path: &tr.path,
 837                         indexes: insert,
 838                         expected: last_seg.lifetimes.len(),
 839                         anon_nums: &HashSet::new(),
 840                         region_names: region_names
 841                     };
 842                     let new_path = self.rebuild_path(rebuild_info, lifetime);
 843                     ast::TraitTyParamBound(ast::TraitRef {
 844                         path: new_path,
 845                         ref_id: tr.ref_id,
 846                     })
 847                 }
 848             }
 849         })
 850     }
 851
 852     fn rebuild_generics(&self,
 853                         generics: &ast::Generics,
 854                         add: Vec<ast::Lifetime>,
 855                         remove: &HashSet<ast::Name>,
 856                         ty_params: OwnedSlice<ast::TyParam>)
 857                         -> ast::Generics {
 858         let mut lifetimes = Vec::new();
 859         for lt in add.iter() {
 860             lifetimes.push(*lt);
 861         }
 862         for lt in generics.lifetimes.iter() {
 863             if !remove.contains(&lt.name) {
 864                 lifetimes.push((*lt).clone());
 865             }
 866         }
 867         ast::Generics {
 868             lifetimes: lifetimes,
 869             ty_params: ty_params
 870         }
 871     }
 872
 873     fn rebuild_args_ty(&self,
 874                        inputs: &[ast::Arg],
 875                        lifetime: ast::Lifetime,
 876                        anon_nums: &HashSet<uint>,
 877                        region_names: &HashSet<ast::Name>)
 878                        -> Vec<ast::Arg> {
 879         let mut new_inputs = Vec::new();
 880         for arg in inputs.iter() {
 881             let new_ty = self.rebuild_arg_ty_or_output(arg.ty, lifetime,
 882                                                        anon_nums, region_names);
 883             let possibly_new_arg = ast::Arg {
 884                 ty: new_ty,
 885                 pat: arg.pat,
 886                 id: arg.id
 887             };
 888             new_inputs.push(possibly_new_arg);
 889         }
 890         new_inputs
 891     }
 892
 893     fn rebuild_arg_ty_or_output(&self,
 894                                 ty: ast::P<ast::Ty>,
 895                                 lifetime: ast::Lifetime,
 896                                 anon_nums: &HashSet<uint>,
 897                                 region_names: &HashSet<ast::Name>)
 898                                 -> ast::P<ast::Ty> {
 899         let mut new_ty = ty;
 900         let mut ty_queue = vec!(ty);
 901         let mut cur_ty;
 902         while !ty_queue.is_empty() {
 903             cur_ty = ty_queue.shift().unwrap();
 904             match cur_ty.node {
 905                 ast::TyRptr(lt_opt, mut_ty) => {
 906                     match lt_opt {
 907                         Some(lt) => if region_names.contains(&lt.name) {
 908                             new_ty = self.rebuild_ty(new_ty, cur_ty,
 909                                                      lifetime, None);
 910                         },
 911                         None => {
 912                             let anon = self.cur_anon.get();
 913                             if anon_nums.contains(&anon) {
 914                                 new_ty = self.rebuild_ty(new_ty, cur_ty,
 915                                                          lifetime, None);
 916                                 self.track_anon(anon);
 917                             }
 918                             self.inc_and_offset_cur_anon(1);
 919                         }
 920                     }
 921                     ty_queue.push(mut_ty.ty);
 922                 }
 923                 ast::TyPath(ref path, _, id) => {
 924                     let a_def = match self.tcx.def_map.borrow().find(&id) {
 925                         None => self.tcx.sess.fatal(format!("unbound path {}",
 926                                                     pprust::path_to_str(path))),
 927                         Some(&d) => d
 928                     };
 929                     match a_def {
 930                         ast::DefTy(did) | ast::DefStruct(did) => {
 931                             let ty::ty_param_bounds_and_ty {
 932                                 generics: generics,
 933                                 ty: _
 934                             } = ty::lookup_item_type(self.tcx, did);
 935
 936                             let expected = generics.region_param_defs().len();
 937                             let lifetimes = &path.segments.last()
 938                                                  .unwrap().lifetimes;
 939                             let mut insert = Vec::new();
 940                             if lifetimes.len() == 0 {
 941                                 let anon = self.cur_anon.get();
 942                                 for (i, a) in range(anon,
 943                                                     anon+expected).enumerate() {
 944                                     if anon_nums.contains(&a) {
 945                                         insert.push(i);
 946                                     }
 947                                     self.track_anon(a);
 948                                 }
 949                                 self.inc_and_offset_cur_anon(expected);
 950                             } else {
 951                                 for (i, lt) in lifetimes.iter().enumerate() {
 952                                     if region_names.contains(&lt.name) {
 953                                         insert.push(i);
 954                                     }
 955                                 }
 956                             }
 957                             let rebuild_info = RebuildPathInfo {
 958                                 path: path,
 959                                 indexes: insert,
 960                                 expected: expected,
 961                                 anon_nums: anon_nums,
 962                                 region_names: region_names
 963                             };
 964                             new_ty = self.rebuild_ty(new_ty, cur_ty,
 965                                                      lifetime,
 966                                                      Some(rebuild_info));
 967                         }
 968                         _ => ()
 969                     }
 970
 971                 }
 972                 _ => ty_queue.push_all_move(ast_util::get_inner_tys(cur_ty))
 973             }
 974         }
 975         new_ty
 976     }
 977
 978     fn rebuild_ty(&self,
 979                   from: ast::P<ast::Ty>,
 980                   to: ast::P<ast::Ty>,
 981                   lifetime: ast::Lifetime,
 982                   rebuild_path_info: Option<RebuildPathInfo>)
 983                   -> ast::P<ast::Ty> {
 984
 985         fn build_to(from: ast::P<ast::Ty>,
 986                     to: ast::P<ast::Ty>)
 987                     -> ast::P<ast::Ty> {
 988             if from.id == to.id {
 989                 return to;
 990             }
 991             let new_node = match from.node {
 992                 ast::TyRptr(ref lifetime, ref mut_ty) => {
 993                     let new_mut_ty = ast::MutTy {
 994                         ty: build_to(mut_ty.ty, to),
 995                         mutbl: mut_ty.mutbl
 996                     };
 997                     ast::TyRptr(*lifetime, new_mut_ty)
 998                 }
 999                 ast::TyPtr(ref mut_ty) => {
1000                     let new_mut_ty = ast::MutTy {
1001                         ty: build_to(mut_ty.ty, to),
1002                         mutbl: mut_ty.mutbl
1003                     };
1004                     ast::TyPtr(new_mut_ty)
1005                 }
1006                 ast::TyBox(ref ty) => ast::TyBox(build_to(*ty, to)),
1007                 ast::TyVec(ref ty) => ast::TyVec(build_to(*ty, to)),
1008                 ast::TyUniq(ref ty) => ast::TyUniq(build_to(*ty, to)),
1009                 ast::TyFixedLengthVec(ref ty, ref e) => {
1010                     ast::TyFixedLengthVec(build_to(*ty, to), *e)
1011                 }
1012                 ast::TyTup(ref tys) => {
1013                     let mut new_tys = Vec::new();
1014                     for ty in tys.iter() {
1015                         new_tys.push(build_to(*ty, to));
1016                     }
1017                     ast::TyTup(new_tys)
1018                 }
1019                 ref other => other.clone()
1020             };
1021             @ast::Ty { id: from.id, node: new_node, span: from.span }
1022         }
1023
1024         let new_ty_node = match to.node {
1025             ast::TyRptr(_, mut_ty) => ast::TyRptr(Some(lifetime), mut_ty),
1026             ast::TyPath(_, ref bounds, id) => {
1027                 let rebuild_info = match rebuild_path_info {
1028                     Some(ri) => ri,
1029                     None => fail!("expect index_opt in rebuild_ty/ast::TyPath")
1030                 };
1031                 let new_path = self.rebuild_path(rebuild_info, lifetime);
1032                 ast::TyPath(new_path, bounds.clone(), id)
1033             }
1034             _ => fail!("expect ast::TyRptr or ast::TyPath")
1035         };
1036         let new_ty = @ast::Ty {
1037             id: to.id,
1038             node: new_ty_node,
1039             span: to.span
1040         };
1041         build_to(from, new_ty)
1042     }
1043
1044     fn rebuild_path(&self,
1045                     rebuild_info: RebuildPathInfo,
1046                     lifetime: ast::Lifetime)
1047                     -> ast::Path {
1048         let RebuildPathInfo {
1049             path: path,
1050             indexes: indexes,
1051             expected: expected,
1052             anon_nums: anon_nums,
1053             region_names: region_names,
1054         } = rebuild_info;
1055
1056         let last_seg = path.segments.last().unwrap();
1057         let mut new_lts = Vec::new();
1058         if last_seg.lifetimes.len() == 0 {
1059             // traverse once to see if there's a need to insert lifetime
1060             let need_insert = range(0, expected).any(|i| {
1061                 indexes.contains(&i)
1062             });
1063             if need_insert {
1064                 for i in range(0, expected) {
1065                     if indexes.contains(&i) {
1066                         new_lts.push(lifetime);
1067                     } else {
1068                         new_lts.push(self.life_giver.give_lifetime());
1069                     }
1070                 }
1071             }
1072         } else {
1073             for (i, lt) in last_seg.lifetimes.iter().enumerate() {
1074                 if indexes.contains(&i) {
1075                     new_lts.push(lifetime);
1076                 } else {
1077                     new_lts.push(*lt);
1078                 }
1079             }
1080         }
1081         let new_types = last_seg.types.map(|&t| {
1082             self.rebuild_arg_ty_or_output(t, lifetime, anon_nums, region_names)
1083         });
1084         let new_seg = ast::PathSegment {
1085             identifier: last_seg.identifier,
1086             lifetimes: new_lts,
1087             types: new_types,
1088         };
1089         let mut new_segs = Vec::new();
1090         new_segs.push_all(path.segments.init());
1091         new_segs.push(new_seg);
1092         ast::Path {
1093             span: path.span,
1094             global: path.global,
1095             segments: new_segs
1096         }
1097     }
1098 }
1099
1100 impl<'a> ErrorReportingHelpers for InferCtxt<'a> {
1101     fn give_expl_lifetime_param(&self,
1102                                 inputs: Vec<ast::Arg>,
1103                                 output: ast::P<ast::Ty>,
1104                                 item: ast::P<ast::Item>,
1105                                 generics: ast::Generics) {
1106         let (fn_decl, fn_style, ident) = match item.node {
1107             // FIXME: handling method
1108             ast::ItemFn(ref fn_decl, ref fn_style, _, _, _) => {
1109                 (fn_decl, fn_style, item.ident)
1110             },
1111             _ => fail!("Expect function or method")
1112
1113         };
1114         let fd = ast::FnDecl {
1115             inputs: inputs,
1116             output: output,
1117             cf: fn_decl.cf,
1118             variadic: fn_decl.variadic
1119         };
1120         let suggested_fn =
1121             pprust::fun_to_str(&fd, *fn_style, ident, None, &generics);
1122         let msg = format!("consider using an explicit lifetime \
1123                            parameter as shown: {}", suggested_fn);
1124         self.tcx.sess.span_note(item.span, msg);
1125     }
1126
1127     fn report_inference_failure(&self,
1128                                 var_origin: RegionVariableOrigin) {
1129         let var_description = match var_origin {
1130             infer::MiscVariable(_) => ~"",
1131             infer::PatternRegion(_) => ~" for pattern",
1132             infer::AddrOfRegion(_) => ~" for borrow expression",
1133             infer::AddrOfSlice(_) => ~" for slice expression",
1134             infer::Autoref(_) => ~" for autoref",
1135             infer::Coercion(_) => ~" for automatic coercion",
1136             infer::LateBoundRegion(_, br) => {
1137                 format!(" for {}in function call",
1138                         bound_region_to_str(self.tcx, "lifetime parameter ", true, br))
1139             }
1140             infer::BoundRegionInFnType(_, br) => {
1141                 format!(" for {}in function type",
1142                         bound_region_to_str(self.tcx, "lifetime parameter ", true, br))
1143             }
1144             infer::EarlyBoundRegion(_, name) => {
1145                 format!(" for lifetime parameter `{}",
1146                         token::get_name(name).get())
1147             }
1148             infer::BoundRegionInCoherence(name) => {
1149                 format!(" for lifetime parameter `{} in coherence check",
1150                         token::get_name(name).get())
1151             }
1152             infer::UpvarRegion(ref upvar_id, _) => {
1153                 format!(" for capture of `{}` by closure",
1154                         ty::local_var_name_str(self.tcx, upvar_id.var_id).get().to_str())
1155             }
1156         };
1157
1158         self.tcx.sess.span_err(
1159             var_origin.span(),
1160             format!("cannot infer an appropriate lifetime{} \
1161                     due to conflicting requirements",
1162                     var_description));
1163     }
1164
1165     fn note_region_origin(&self, origin: SubregionOrigin) {
1166         match origin {
1167             infer::Subtype(ref trace) => {
1168                 let desc = match trace.origin {
1169                     infer::Misc(_) => {
1170                         format!("types are compatible")
1171                     }
1172                     infer::MethodCompatCheck(_) => {
1173                         format!("method type is compatible with trait")
1174                     }
1175                     infer::ExprAssignable(_) => {
1176                         format!("expression is assignable")
1177                     }
1178                     infer::RelateTraitRefs(_) => {
1179                         format!("traits are compatible")
1180                     }
1181                     infer::RelateSelfType(_) => {
1182                         format!("type matches impl")
1183                     }
1184                     infer::MatchExpression(_) => {
1185                         format!("match arms have compatible types")
1186                     }
1187                     infer::IfExpression(_) => {
1188                         format!("if and else have compatible types")
1189                     }
1190                 };
1191
1192                 match self.values_str(&trace.values) {
1193                     Some(values_str) => {
1194                         self.tcx.sess.span_note(
1195                             trace.origin.span(),
1196                             format!("...so that {} ({})",
1197                                     desc, values_str));
1198                     }
1199                     None => {
1200                         // Really should avoid printing this error at
1201                         // all, since it is derived, but that would
1202                         // require more refactoring than I feel like
1203                         // doing right now. - nmatsakis
1204                         self.tcx.sess.span_note(
1205                             trace.origin.span(),
1206                             format!("...so that {}", desc));
1207                     }
1208                 }
1209             }
1210             infer::Reborrow(span) => {
1211                 self.tcx.sess.span_note(
1212                     span,
1213                     "...so that reference does not outlive \
1214                     borrowed content");
1215             }
1216             infer::ReborrowUpvar(span, ref upvar_id) => {
1217                 self.tcx.sess.span_note(
1218                     span,
1219                     format!("...so that closure can access `{}`",
1220                             ty::local_var_name_str(self.tcx, upvar_id.var_id).get().to_str()))
1221             }
1222             infer::InfStackClosure(span) => {
1223                 self.tcx.sess.span_note(
1224                     span,
1225                     "...so that closure does not outlive its stack frame");
1226             }
1227             infer::InvokeClosure(span) => {
1228                 self.tcx.sess.span_note(
1229                     span,
1230                     "...so that closure is not invoked outside its lifetime");
1231             }
1232             infer::DerefPointer(span) => {
1233                 self.tcx.sess.span_note(
1234                     span,
1235                     "...so that pointer is not dereferenced \
1236                     outside its lifetime");
1237             }
1238             infer::FreeVariable(span, id) => {
1239                 self.tcx.sess.span_note(
1240                     span,
1241                     format!("...so that captured variable `{}` \
1242                             does not outlive the enclosing closure",
1243                             ty::local_var_name_str(self.tcx, id).get().to_str()));
1244             }
1245             infer::IndexSlice(span) => {
1246                 self.tcx.sess.span_note(
1247                     span,
1248                     "...so that slice is not indexed outside the lifetime");
1249             }
1250             infer::RelateObjectBound(span) => {
1251                 self.tcx.sess.span_note(
1252                     span,
1253                     "...so that source pointer does not outlive \
1254                      lifetime bound of the object type");
1255             }
1256             infer::CallRcvr(span) => {
1257                 self.tcx.sess.span_note(
1258                     span,
1259                     "...so that method receiver is valid for the method call");
1260             }
1261             infer::CallArg(span) => {
1262                 self.tcx.sess.span_note(
1263                     span,
1264                     "...so that argument is valid for the call");
1265             }
1266             infer::CallReturn(span) => {
1267                 self.tcx.sess.span_note(
1268                     span,
1269                     "...so that return value is valid for the call");
1270             }
1271             infer::AddrOf(span) => {
1272                 self.tcx.sess.span_note(
1273                     span,
1274                     "...so that reference is valid \
1275                      at the time of borrow");
1276             }
1277             infer::AutoBorrow(span) => {
1278                 self.tcx.sess.span_note(
1279                     span,
1280                     "...so that automatically reference is valid \
1281                      at the time of borrow");
1282             }
1283             infer::BindingTypeIsNotValidAtDecl(span) => {
1284                 self.tcx.sess.span_note(
1285                     span,
1286                     "...so that variable is valid at time of its declaration");
1287             }
1288             infer::ReferenceOutlivesReferent(_, span) => {
1289                 self.tcx.sess.span_note(
1290                     span,
1291                     "...so that the pointer does not outlive the \
1292                     data it points at");
1293             }
1294         }
1295     }
1296 }
1297
1298 trait Resolvable {
1299     fn resolve(&self, infcx: &InferCtxt) -> Self;
1300     fn contains_error(&self) -> bool;
1301 }
1302
1303 impl Resolvable for ty::t {
1304     fn resolve(&self, infcx: &InferCtxt) -> ty::t {
1305         infcx.resolve_type_vars_if_possible(*self)
1306     }
1307     fn contains_error(&self) -> bool {
1308         ty::type_is_error(*self)
1309     }
1310 }
1311
1312 impl Resolvable for @ty::TraitRef {
1313     fn resolve(&self, infcx: &InferCtxt) -> @ty::TraitRef {
1314         @infcx.resolve_type_vars_in_trait_ref_if_possible(*self)
1315     }
1316     fn contains_error(&self) -> bool {
1317         ty::trait_ref_contains_error(*self)
1318     }
1319 }
1320
1321 // LifeGiver is responsible for generating fresh lifetime names
1322 struct LifeGiver {
1323     taken: HashSet<~str>,
1324     counter: Cell<uint>,
1325     generated: RefCell<Vec<ast::Lifetime>>,
1326 }
1327
1328 impl LifeGiver {
1329     // FIXME: `taken` needs to include names from higher scope, too
1330     fn with_taken(taken: &[ast::Lifetime]) -> LifeGiver {
1331         let mut taken_ = HashSet::new();
1332         for lt in taken.iter() {
1333             let lt_name = token::get_name(lt.name).get().to_owned();
1334             taken_.insert(lt_name);
1335         }
1336         LifeGiver {
1337             taken: taken_,
1338             counter: Cell::new(0),
1339             generated: RefCell::new(Vec::new()),
1340         }
1341     }
1342
1343     fn inc_counter(&self) {
1344         let c = self.counter.get();
1345         self.counter.set(c+1);
1346     }
1347
1348     fn give_lifetime(&self) -> ast::Lifetime {
1349         let mut lifetime;
1350         loop {
1351             let s = num_to_str(self.counter.get());
1352             if !self.taken.contains(&s) {
1353                 lifetime = name_to_dummy_lifetime(
1354                                     token::str_to_ident(s.as_slice()).name);
1355                 self.generated.borrow_mut().push(lifetime);
1356                 break;
1357             }
1358             self.inc_counter();
1359         }
1360         self.inc_counter();
1361         return lifetime;
1362
1363         // 0 .. 25 generates a .. z, 26 .. 51 generates aa .. zz, and so on
1364         fn num_to_str(counter: uint) -> ~str {
1365             let mut s = StrBuf::new();
1366             let (n, r) = (counter/26 + 1, counter % 26);
1367             let letter: char = from_u32((r+97) as u32).unwrap();
1368             for _ in range(0, n) {
1369                 s.push_char(letter);
1370             }
1371             s.into_owned()
1372         }
1373     }
1374
1375     fn get_generated_lifetimes(&self) -> Vec<ast::Lifetime> {
1376         self.generated.borrow().clone()
1377     }
1378 }