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