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