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