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