src/librustc/middle/typeck/infer/error_reporting.rs

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