src/librustc/middle/infer/error_reporting.rs

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