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