src/librustc/middle/resolve_lifetime.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 //! Name resolution for lifetimes.
  12 //!
  13 //! Name resolution for lifetimes follows MUCH simpler rules than the
  14 //! full resolve. For example, lifetime names are never exported or
  15 //! used between functions, and they operate in a purely top-down
  16 //! way. Therefore we break lifetime name resolution into a separate pass.
  17
  18 pub use self::DefRegion::*;
  19 use self::ScopeChain::*;
  20
  21 use session::Session;
  22 use middle::def::{self, DefMap};
  23 use middle::region;
  24 use middle::subst;
  25 use middle::ty;
  26 use std::fmt;
  27 use std::mem::replace;
  28 use syntax::ast;
  29 use syntax::codemap::Span;
  30 use syntax::parse::token::special_idents;
  31 use syntax::parse::token;
  32 use syntax::print::pprust::lifetime_to_string;
  33 use syntax::visit;
  34 use syntax::visit::Visitor;
  35 use util::nodemap::NodeMap;
  36
  37 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
  38 pub enum DefRegion {
  39     DefStaticRegion,
  40     DefEarlyBoundRegion(/* space */ subst::ParamSpace,
  41                         /* index */ u32,
  42                         /* lifetime decl */ ast::NodeId),
  43     DefLateBoundRegion(ty::DebruijnIndex,
  44                        /* lifetime decl */ ast::NodeId),
  45     DefFreeRegion(/* block scope */ region::DestructionScopeData,
  46                   /* lifetime decl */ ast::NodeId),
  47 }
  48
  49 // Maps the id of each lifetime reference to the lifetime decl
  50 // that it corresponds to.
  51 pub type NamedRegionMap = NodeMap<DefRegion>;
  52
  53 struct LifetimeContext<'a> {
  54     sess: &'a Session,
  55     named_region_map: &'a mut NamedRegionMap,
  56     scope: Scope<'a>,
  57     def_map: &'a DefMap,
  58     // Deep breath. Our representation for poly trait refs contains a single
  59     // binder and thus we only allow a single level of quantification. However,
  60     // the syntax of Rust permits quantification in two places, e.g., `T: for <'a> Foo<'a>`
  61     // and `for <'a, 'b> &'b T: Foo<'a>`. In order to get the de Bruijn indices
  62     // correct when representing these constraints, we should only introduce one
  63     // scope. However, we want to support both locations for the quantifier and
  64     // during lifetime resolution we want precise information (so we can't
  65     // desugar in an earlier phase).
  66
  67     // SO, if we encounter a quantifier at the outer scope, we set
  68     // trait_ref_hack to true (and introduce a scope), and then if we encounter
  69     // a quantifier at the inner scope, we error. If trait_ref_hack is false,
  70     // then we introduce the scope at the inner quantifier.
  71
  72     // I'm sorry.
  73     trait_ref_hack: bool,
  74
  75     // List of labels in the function/method currently under analysis.
  76     labels_in_fn: Vec<(ast::Ident, Span)>,
  77 }
  78
  79 enum ScopeChain<'a> {
  80     /// EarlyScope(i, ['a, 'b, ...], s) extends s with early-bound
  81     /// lifetimes, assigning indexes 'a => i, 'b => i+1, ... etc.
  82     EarlyScope(subst::ParamSpace, &'a Vec<ast::LifetimeDef>, Scope<'a>),
  83     /// LateScope(['a, 'b, ...], s) extends s with late-bound
  84     /// lifetimes introduced by the declaration binder_id.
  85     LateScope(&'a Vec<ast::LifetimeDef>, Scope<'a>),
  86     /// lifetimes introduced by items within a code block are scoped
  87     /// to that block.
  88     BlockScope(region::DestructionScopeData, Scope<'a>),
  89     RootScope
  90 }
  91
  92 type Scope<'a> = &'a ScopeChain<'a>;
  93
  94 static ROOT_SCOPE: ScopeChain<'static> = RootScope;
  95
  96 pub fn krate(sess: &Session, krate: &ast::Crate, def_map: &DefMap) -> NamedRegionMap {
  97     let mut named_region_map = NodeMap();
  98     visit::walk_crate(&mut LifetimeContext {
  99         sess: sess,
 100         named_region_map: &mut named_region_map,
 101         scope: &ROOT_SCOPE,
 102         def_map: def_map,
 103         trait_ref_hack: false,
 104         labels_in_fn: vec![],
 105     }, krate);
 106     sess.abort_if_errors();
 107     named_region_map
 108 }
 109
 110 impl<'a, 'v> Visitor<'v> for LifetimeContext<'a> {
 111     fn visit_item(&mut self, item: &ast::Item) {
 112         // Items save/restore the set of labels. This way innner items
 113         // can freely reuse names, be they loop labels or lifetimes.
 114         let saved = replace(&mut self.labels_in_fn, vec![]);
 115
 116         // Items always introduce a new root scope
 117         self.with(RootScope, |_, this| {
 118             match item.node {
 119                 ast::ItemFn(..) => {
 120                     // Fn lifetimes get added in visit_fn below:
 121                     visit::walk_item(this, item);
 122                 }
 123                 ast::ItemExternCrate(_) |
 124                 ast::ItemUse(_) |
 125                 ast::ItemMod(..) |
 126                 ast::ItemMac(..) |
 127                 ast::ItemDefaultImpl(..) |
 128                 ast::ItemForeignMod(..) |
 129                 ast::ItemStatic(..) |
 130                 ast::ItemConst(..) => {
 131                     // These sorts of items have no lifetime parameters at all.
 132                     visit::walk_item(this, item);
 133                 }
 134                 ast::ItemTy(_, ref generics) |
 135                 ast::ItemEnum(_, ref generics) |
 136                 ast::ItemStruct(_, ref generics) |
 137                 ast::ItemTrait(_, ref generics, _, _) |
 138                 ast::ItemImpl(_, _, ref generics, _, _, _) => {
 139                     // These kinds of items have only early bound lifetime parameters.
 140                     let lifetimes = &generics.lifetimes;
 141                     let early_scope = EarlyScope(subst::TypeSpace, lifetimes, &ROOT_SCOPE);
 142                     this.with(early_scope, |old_scope, this| {
 143                         this.check_lifetime_defs(old_scope, lifetimes);
 144                         visit::walk_item(this, item);
 145                     });
 146                 }
 147             }
 148         });
 149
 150         // Done traversing the item; restore saved set of labels.
 151         replace(&mut self.labels_in_fn, saved);
 152     }
 153
 154     fn visit_fn(&mut self, fk: visit::FnKind<'v>, fd: &'v ast::FnDecl,
 155                 b: &'v ast::Block, s: Span, _: ast::NodeId) {
 156         match fk {
 157             visit::FkItemFn(_, generics, _, _, _) => {
 158                 self.visit_early_late(subst::FnSpace, generics, |this| {
 159                     this.walk_fn(fk, fd, b, s)
 160                 })
 161             }
 162             visit::FkMethod(_, sig, _) => {
 163                 self.visit_early_late(subst::FnSpace, &sig.generics, |this| {
 164                     this.walk_fn(fk, fd, b, s)
 165                 })
 166             }
 167             visit::FkFnBlock(..) => {
 168                 self.walk_fn(fk, fd, b, s)
 169             }
 170         }
 171     }
 172
 173     fn visit_ty(&mut self, ty: &ast::Ty) {
 174         match ty.node {
 175             ast::TyBareFn(ref c) => {
 176                 visit::walk_lifetime_decls_helper(self, &c.lifetimes);
 177                 self.with(LateScope(&c.lifetimes, self.scope), |old_scope, this| {
 178                     // a bare fn has no bounds, so everything
 179                     // contained within is scoped within its binder.
 180                     this.check_lifetime_defs(old_scope, &c.lifetimes);
 181                     visit::walk_ty(this, ty);
 182                 });
 183             }
 184             ast::TyPath(None, ref path) => {
 185                 // if this path references a trait, then this will resolve to
 186                 // a trait ref, which introduces a binding scope.
 187                 match self.def_map.borrow().get(&ty.id).map(|d| (d.base_def, d.depth)) {
 188                     Some((def::DefTrait(..), 0)) => {
 189                         self.with(LateScope(&Vec::new(), self.scope), |_, this| {
 190                             this.visit_path(path, ty.id);
 191                         });
 192                     }
 193                     _ => {
 194                         visit::walk_ty(self, ty);
 195                     }
 196                 }
 197             }
 198             _ => {
 199                 visit::walk_ty(self, ty)
 200             }
 201         }
 202     }
 203
 204     fn visit_trait_item(&mut self, trait_item: &ast::TraitItem) {
 205         // We reset the labels on every trait item, so that different
 206         // methods in an impl can reuse label names.
 207         let saved = replace(&mut self.labels_in_fn, vec![]);
 208
 209         if let ast::MethodTraitItem(ref sig, None) = trait_item.node {
 210             self.visit_early_late(
 211                 subst::FnSpace, &sig.generics,
 212                 |this| visit::walk_trait_item(this, trait_item))
 213         } else {
 214             visit::walk_trait_item(self, trait_item);
 215         }
 216
 217         replace(&mut self.labels_in_fn, saved);
 218     }
 219
 220     fn visit_block(&mut self, b: &ast::Block) {
 221         self.with(BlockScope(region::DestructionScopeData::new(b.id),
 222                              self.scope),
 223                   |_, this| visit::walk_block(this, b));
 224     }
 225
 226     fn visit_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 227         if lifetime_ref.name == special_idents::static_lifetime.name {
 228             self.insert_lifetime(lifetime_ref, DefStaticRegion);
 229             return;
 230         }
 231         self.resolve_lifetime_ref(lifetime_ref);
 232     }
 233
 234     fn visit_generics(&mut self, generics: &ast::Generics) {
 235         for ty_param in &*generics.ty_params {
 236             visit::walk_ty_param_bounds_helper(self, &ty_param.bounds);
 237             match ty_param.default {
 238                 Some(ref ty) => self.visit_ty(&**ty),
 239                 None => {}
 240             }
 241         }
 242         for predicate in &generics.where_clause.predicates {
 243             match predicate {
 244                 &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ ref bounded_ty,
 245                                                                                ref bounds,
 246                                                                                ref bound_lifetimes,
 247                                                                                .. }) => {
 248                     if !bound_lifetimes.is_empty() {
 249                         self.trait_ref_hack = true;
 250                         let result = self.with(LateScope(bound_lifetimes, self.scope),
 251                                                |old_scope, this| {
 252                             this.check_lifetime_defs(old_scope, bound_lifetimes);
 253                             this.visit_ty(&**bounded_ty);
 254                             visit::walk_ty_param_bounds_helper(this, bounds);
 255                         });
 256                         self.trait_ref_hack = false;
 257                         result
 258                     } else {
 259                         self.visit_ty(&**bounded_ty);
 260                         visit::walk_ty_param_bounds_helper(self, bounds);
 261                     }
 262                 }
 263                 &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime,
 264                                                                                 ref bounds,
 265                                                                                 .. }) => {
 266
 267                     self.visit_lifetime_ref(lifetime);
 268                     for bound in bounds {
 269                         self.visit_lifetime_ref(bound);
 270                     }
 271                 }
 272                 &ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{ id,
 273                                                                          ref path,
 274                                                                          ref ty,
 275                                                                          .. }) => {
 276                     self.visit_path(path, id);
 277                     self.visit_ty(&**ty);
 278                 }
 279             }
 280         }
 281     }
 282
 283     fn visit_poly_trait_ref(&mut self,
 284                             trait_ref: &ast::PolyTraitRef,
 285                             _modifier: &ast::TraitBoundModifier) {
 286         debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
 287
 288         if !self.trait_ref_hack || !trait_ref.bound_lifetimes.is_empty() {
 289             if self.trait_ref_hack {
 290                 println!("{:?}", trait_ref.span);
 291                 span_err!(self.sess, trait_ref.span, E0316,
 292                           "nested quantification of lifetimes");
 293             }
 294             self.with(LateScope(&trait_ref.bound_lifetimes, self.scope), |old_scope, this| {
 295                 this.check_lifetime_defs(old_scope, &trait_ref.bound_lifetimes);
 296                 for lifetime in &trait_ref.bound_lifetimes {
 297                     this.visit_lifetime_def(lifetime);
 298                 }
 299                 visit::walk_path(this, &trait_ref.trait_ref.path)
 300             })
 301         } else {
 302             self.visit_trait_ref(&trait_ref.trait_ref)
 303         }
 304     }
 305 }
 306
 307 #[derive(Copy, Clone, PartialEq)]
 308 enum ShadowKind { Label, Lifetime }
 309 struct Original { kind: ShadowKind, span: Span }
 310 struct Shadower { kind: ShadowKind, span: Span }
 311
 312 fn original_label(span: Span) -> Original {
 313     Original { kind: ShadowKind::Label, span: span }
 314 }
 315 fn shadower_label(span: Span) -> Shadower {
 316     Shadower { kind: ShadowKind::Label, span: span }
 317 }
 318 fn original_lifetime(l: &ast::Lifetime) -> Original {
 319     Original { kind: ShadowKind::Lifetime, span: l.span }
 320 }
 321 fn shadower_lifetime(l: &ast::Lifetime) -> Shadower {
 322     Shadower { kind: ShadowKind::Lifetime, span: l.span }
 323 }
 324
 325 impl ShadowKind {
 326     fn desc(&self) -> &'static str {
 327         match *self {
 328             ShadowKind::Label => "label",
 329             ShadowKind::Lifetime => "lifetime",
 330         }
 331     }
 332 }
 333
 334 fn signal_shadowing_problem(
 335     sess: &Session, name: ast::Name, orig: Original, shadower: Shadower) {
 336     if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
 337         // lifetime/lifetime shadowing is an error
 338         sess.span_err(shadower.span,
 339                       &format!("{} name `{}` shadows a \
 340                                 {} name that is already in scope",
 341                                shadower.kind.desc(), name, orig.kind.desc()));
 342     } else {
 343         // shadowing involving a label is only a warning, due to issues with
 344         // labels and lifetimes not being macro-hygienic.
 345         sess.span_warn(shadower.span,
 346                       &format!("{} name `{}` shadows a \
 347                                 {} name that is already in scope",
 348                                shadower.kind.desc(), name, orig.kind.desc()));
 349     }
 350     sess.span_note(orig.span,
 351                    &format!("shadowed {} `{}` declared here",
 352                             orig.kind.desc(), name));
 353 }
 354
 355 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
 356 // if one of the label shadows a lifetime or another label.
 357 fn extract_labels<'v, 'a>(ctxt: &mut LifetimeContext<'a>, b: &'v ast::Block) {
 358
 359     struct GatherLabels<'a> {
 360         sess: &'a Session,
 361         scope: Scope<'a>,
 362         labels_in_fn: &'a mut Vec<(ast::Ident, Span)>,
 363     }
 364
 365     let mut gather = GatherLabels {
 366         sess: ctxt.sess,
 367         scope: ctxt.scope,
 368         labels_in_fn: &mut ctxt.labels_in_fn,
 369     };
 370     gather.visit_block(b);
 371     return;
 372
 373     impl<'v, 'a> Visitor<'v> for GatherLabels<'a> {
 374         fn visit_expr(&mut self, ex: &'v ast::Expr) {
 375             if let Some(label) = expression_label(ex) {
 376                 for &(prior, prior_span) in &self.labels_in_fn[..] {
 377                     // FIXME (#24278): non-hygienic comparison
 378                     if label.name == prior.name {
 379                         signal_shadowing_problem(self.sess,
 380                                                  label.name,
 381                                                  original_label(prior_span),
 382                                                  shadower_label(ex.span));
 383                     }
 384                 }
 385
 386                 check_if_label_shadows_lifetime(self.sess,
 387                                                 self.scope,
 388                                                 label,
 389                                                 ex.span);
 390
 391                 self.labels_in_fn.push((label, ex.span));
 392             }
 393             visit::walk_expr(self, ex)
 394         }
 395
 396         fn visit_item(&mut self, _: &ast::Item) {
 397             // do not recurse into items defined in the block
 398         }
 399     }
 400
 401     fn expression_label(ex: &ast::Expr) -> Option<ast::Ident> {
 402         match ex.node {
 403             ast::ExprWhile(_, _, Some(label))       |
 404             ast::ExprWhileLet(_, _, _, Some(label)) |
 405             ast::ExprForLoop(_, _, _, Some(label))  |
 406             ast::ExprLoop(_, Some(label))          => Some(label),
 407             _ => None,
 408         }
 409     }
 410
 411     fn check_if_label_shadows_lifetime<'a>(sess: &'a Session,
 412                                            mut scope: Scope<'a>,
 413                                            label: ast::Ident,
 414                                            label_span: Span) {
 415         loop {
 416             match *scope {
 417                 BlockScope(_, s) => { scope = s; }
 418                 RootScope => { return; }
 419
 420                 EarlyScope(_, lifetimes, s) |
 421                 LateScope(lifetimes, s) => {
 422                     for lifetime_def in lifetimes {
 423                         // FIXME (#24278): non-hygienic comparison
 424                         if label.name == lifetime_def.lifetime.name {
 425                             signal_shadowing_problem(
 426                                 sess,
 427                                 label.name,
 428                                 original_lifetime(&lifetime_def.lifetime),
 429                                 shadower_label(label_span));
 430                             return;
 431                         }
 432                     }
 433                     scope = s;
 434                 }
 435             }
 436         }
 437     }
 438 }
 439
 440 impl<'a> LifetimeContext<'a> {
 441     // This is just like visit::walk_fn, except that it extracts the
 442     // labels of the function body and swaps them in before visiting
 443     // the function body itself.
 444     fn walk_fn<'b>(&mut self,
 445                    fk: visit::FnKind,
 446                    fd: &ast::FnDecl,
 447                    fb: &'b ast::Block,
 448                    _span: Span) {
 449         match fk {
 450             visit::FkItemFn(_, generics, _, _, _) => {
 451                 visit::walk_fn_decl(self, fd);
 452                 self.visit_generics(generics);
 453             }
 454             visit::FkMethod(_, sig, _) => {
 455                 visit::walk_fn_decl(self, fd);
 456                 self.visit_generics(&sig.generics);
 457                 self.visit_explicit_self(&sig.explicit_self);
 458             }
 459             visit::FkFnBlock(..) => {
 460                 visit::walk_fn_decl(self, fd);
 461             }
 462         }
 463
 464         // After inpsecting the decl, add all labels from the body to
 465         // `self.labels_in_fn`.
 466         extract_labels(self, fb);
 467
 468         self.visit_block(fb);
 469     }
 470
 471     fn with<F>(&mut self, wrap_scope: ScopeChain, f: F) where
 472         F: FnOnce(Scope, &mut LifetimeContext),
 473     {
 474         let LifetimeContext {sess, ref mut named_region_map, ..} = *self;
 475         let mut this = LifetimeContext {
 476             sess: sess,
 477             named_region_map: *named_region_map,
 478             scope: &wrap_scope,
 479             def_map: self.def_map,
 480             trait_ref_hack: self.trait_ref_hack,
 481             labels_in_fn: self.labels_in_fn.clone(),
 482         };
 483         debug!("entering scope {:?}", this.scope);
 484         f(self.scope, &mut this);
 485         debug!("exiting scope {:?}", this.scope);
 486     }
 487
 488     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
 489     ///
 490     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
 491     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
 492     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
 493     ///
 494     /// For example:
 495     ///
 496     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
 497     ///
 498     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
 499     /// lifetimes may be interspersed together.
 500     ///
 501     /// If early bound lifetimes are present, we separate them into their own list (and likewise
 502     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
 503     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
 504     /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
 505     /// ordering is not important there.
 506     fn visit_early_late<F>(&mut self,
 507                            early_space: subst::ParamSpace,
 508                            generics: &ast::Generics,
 509                            walk: F) where
 510         F: FnOnce(&mut LifetimeContext),
 511     {
 512         let referenced_idents = early_bound_lifetime_names(generics);
 513
 514         debug!("visit_early_late: referenced_idents={:?}",
 515                referenced_idents);
 516
 517         let (early, late): (Vec<_>, _) = generics.lifetimes.iter().cloned().partition(
 518             |l| referenced_idents.iter().any(|&i| i == l.lifetime.name));
 519
 520         self.with(EarlyScope(early_space, &early, self.scope), move |old_scope, this| {
 521             this.with(LateScope(&late, this.scope), move |_, this| {
 522                 this.check_lifetime_defs(old_scope, &generics.lifetimes);
 523                 walk(this);
 524             });
 525         });
 526     }
 527
 528     fn resolve_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 529         // Walk up the scope chain, tracking the number of fn scopes
 530         // that we pass through, until we find a lifetime with the
 531         // given name or we run out of scopes. If we encounter a code
 532         // block, then the lifetime is not bound but free, so switch
 533         // over to `resolve_free_lifetime_ref()` to complete the
 534         // search.
 535         let mut late_depth = 0;
 536         let mut scope = self.scope;
 537         loop {
 538             match *scope {
 539                 BlockScope(blk_scope, s) => {
 540                     return self.resolve_free_lifetime_ref(blk_scope, lifetime_ref, s);
 541                 }
 542
 543                 RootScope => {
 544                     break;
 545                 }
 546
 547                 EarlyScope(space, lifetimes, s) => {
 548                     match search_lifetimes(lifetimes, lifetime_ref) {
 549                         Some((index, lifetime_def)) => {
 550                             let decl_id = lifetime_def.id;
 551                             let def = DefEarlyBoundRegion(space, index, decl_id);
 552                             self.insert_lifetime(lifetime_ref, def);
 553                             return;
 554                         }
 555                         None => {
 556                             scope = s;
 557                         }
 558                     }
 559                 }
 560
 561                 LateScope(lifetimes, s) => {
 562                     match search_lifetimes(lifetimes, lifetime_ref) {
 563                         Some((_index, lifetime_def)) => {
 564                             let decl_id = lifetime_def.id;
 565                             let debruijn = ty::DebruijnIndex::new(late_depth + 1);
 566                             let def = DefLateBoundRegion(debruijn, decl_id);
 567                             self.insert_lifetime(lifetime_ref, def);
 568                             return;
 569                         }
 570
 571                         None => {
 572                             late_depth += 1;
 573                             scope = s;
 574                         }
 575                     }
 576                 }
 577             }
 578         }
 579
 580         self.unresolved_lifetime_ref(lifetime_ref);
 581     }
 582
 583     fn resolve_free_lifetime_ref(&mut self,
 584                                  scope_data: region::DestructionScopeData,
 585                                  lifetime_ref: &ast::Lifetime,
 586                                  scope: Scope) {
 587         debug!("resolve_free_lifetime_ref \
 588                 scope_data: {:?} lifetime_ref: {:?} scope: {:?}",
 589                scope_data, lifetime_ref, scope);
 590
 591         // Walk up the scope chain, tracking the outermost free scope,
 592         // until we encounter a scope that contains the named lifetime
 593         // or we run out of scopes.
 594         let mut scope_data = scope_data;
 595         let mut scope = scope;
 596         let mut search_result = None;
 597         loop {
 598             debug!("resolve_free_lifetime_ref \
 599                     scope_data: {:?} scope: {:?} search_result: {:?}",
 600                    scope_data, scope, search_result);
 601             match *scope {
 602                 BlockScope(blk_scope_data, s) => {
 603                     scope_data = blk_scope_data;
 604                     scope = s;
 605                 }
 606
 607                 RootScope => {
 608                     break;
 609                 }
 610
 611                 EarlyScope(_, lifetimes, s) |
 612                 LateScope(lifetimes, s) => {
 613                     search_result = search_lifetimes(lifetimes, lifetime_ref);
 614                     if search_result.is_some() {
 615                         break;
 616                     }
 617                     scope = s;
 618                 }
 619             }
 620         }
 621
 622         match search_result {
 623             Some((_depth, lifetime)) => {
 624                 let def = DefFreeRegion(scope_data, lifetime.id);
 625                 self.insert_lifetime(lifetime_ref, def);
 626             }
 627
 628             None => {
 629                 self.unresolved_lifetime_ref(lifetime_ref);
 630             }
 631         }
 632
 633     }
 634
 635     fn unresolved_lifetime_ref(&self, lifetime_ref: &ast::Lifetime) {
 636         span_err!(self.sess, lifetime_ref.span, E0261,
 637             "use of undeclared lifetime name `{}`",
 638                     token::get_name(lifetime_ref.name));
 639     }
 640
 641     fn check_lifetime_defs(&mut self, old_scope: Scope, lifetimes: &Vec<ast::LifetimeDef>) {
 642         for i in 0..lifetimes.len() {
 643             let lifetime_i = &lifetimes[i];
 644
 645             let special_idents = [special_idents::static_lifetime];
 646             for lifetime in lifetimes {
 647                 if special_idents.iter().any(|&i| i.name == lifetime.lifetime.name) {
 648                     span_err!(self.sess, lifetime.lifetime.span, E0262,
 649                         "illegal lifetime parameter name: `{}`",
 650                                 token::get_name(lifetime.lifetime.name));
 651                 }
 652             }
 653
 654             // It is a hard error to shadow a lifetime within the same scope.
 655             for j in i + 1..lifetimes.len() {
 656                 let lifetime_j = &lifetimes[j];
 657
 658                 if lifetime_i.lifetime.name == lifetime_j.lifetime.name {
 659                     span_err!(self.sess, lifetime_j.lifetime.span, E0263,
 660                         "lifetime name `{}` declared twice in \
 661                                 the same scope",
 662                                 token::get_name(lifetime_j.lifetime.name));
 663                 }
 664             }
 665
 666             // It is a soft error to shadow a lifetime within a parent scope.
 667             self.check_lifetime_def_for_shadowing(old_scope, &lifetime_i.lifetime);
 668
 669             for bound in &lifetime_i.bounds {
 670                 self.resolve_lifetime_ref(bound);
 671             }
 672         }
 673     }
 674
 675     fn check_lifetime_def_for_shadowing(&self,
 676                                         mut old_scope: Scope,
 677                                         lifetime: &ast::Lifetime)
 678     {
 679         for &(label, label_span) in &self.labels_in_fn {
 680             // FIXME (#24278): non-hygienic comparison
 681             if lifetime.name == label.name {
 682                 signal_shadowing_problem(self.sess,
 683                                          lifetime.name,
 684                                          original_label(label_span),
 685                                          shadower_lifetime(&lifetime));
 686                 return;
 687             }
 688         }
 689
 690         loop {
 691             match *old_scope {
 692                 BlockScope(_, s) => {
 693                     old_scope = s;
 694                 }
 695
 696                 RootScope => {
 697                     return;
 698                 }
 699
 700                 EarlyScope(_, lifetimes, s) |
 701                 LateScope(lifetimes, s) => {
 702                     if let Some((_, lifetime_def)) = search_lifetimes(lifetimes, lifetime) {
 703                         signal_shadowing_problem(
 704                             self.sess,
 705                             lifetime.name,
 706                             original_lifetime(&lifetime_def),
 707                             shadower_lifetime(&lifetime));
 708                         return;
 709                     }
 710
 711                     old_scope = s;
 712                 }
 713             }
 714         }
 715     }
 716
 717     fn insert_lifetime(&mut self,
 718                        lifetime_ref: &ast::Lifetime,
 719                        def: DefRegion) {
 720         if lifetime_ref.id == ast::DUMMY_NODE_ID {
 721             self.sess.span_bug(lifetime_ref.span,
 722                                "lifetime reference not renumbered, \
 723                                probably a bug in syntax::fold");
 724         }
 725
 726         debug!("lifetime_ref={:?} id={:?} resolved to {:?}",
 727                 lifetime_to_string(lifetime_ref),
 728                 lifetime_ref.id,
 729                 def);
 730         self.named_region_map.insert(lifetime_ref.id, def);
 731     }
 732 }
 733
 734 fn search_lifetimes<'a>(lifetimes: &'a Vec<ast::LifetimeDef>,
 735                     lifetime_ref: &ast::Lifetime)
 736                     -> Option<(u32, &'a ast::Lifetime)> {
 737     for (i, lifetime_decl) in lifetimes.iter().enumerate() {
 738         if lifetime_decl.lifetime.name == lifetime_ref.name {
 739             return Some((i as u32, &lifetime_decl.lifetime));
 740         }
 741     }
 742     return None;
 743 }
 744
 745 ///////////////////////////////////////////////////////////////////////////
 746
 747 pub fn early_bound_lifetimes<'a>(generics: &'a ast::Generics) -> Vec<ast::LifetimeDef> {
 748     let referenced_idents = early_bound_lifetime_names(generics);
 749     if referenced_idents.is_empty() {
 750         return Vec::new();
 751     }
 752
 753     generics.lifetimes.iter()
 754         .filter(|l| referenced_idents.iter().any(|&i| i == l.lifetime.name))
 755         .cloned()
 756         .collect()
 757 }
 758
 759 /// Given a set of generic declarations, returns a list of names containing all early bound
 760 /// lifetime names for those generics. (In fact, this list may also contain other names.)
 761 fn early_bound_lifetime_names(generics: &ast::Generics) -> Vec<ast::Name> {
 762     // Create two lists, dividing the lifetimes into early/late bound.
 763     // Initially, all of them are considered late, but we will move
 764     // things from late into early as we go if we find references to
 765     // them.
 766     let mut early_bound = Vec::new();
 767     let mut late_bound = generics.lifetimes.iter()
 768                                            .map(|l| l.lifetime.name)
 769                                            .collect();
 770
 771     // Any lifetime that appears in a type bound is early.
 772     {
 773         let mut collector =
 774             FreeLifetimeCollector { early_bound: &mut early_bound,
 775                                     late_bound: &mut late_bound };
 776         for ty_param in &*generics.ty_params {
 777             visit::walk_ty_param_bounds_helper(&mut collector, &ty_param.bounds);
 778         }
 779         for predicate in &generics.where_clause.predicates {
 780             match predicate {
 781                 &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ref bounds,
 782                                                                               ref bounded_ty,
 783                                                                               ..}) => {
 784                     collector.visit_ty(&**bounded_ty);
 785                     visit::walk_ty_param_bounds_helper(&mut collector, bounds);
 786                 }
 787                 &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime,
 788                                                                                 ref bounds,
 789                                                                                 ..}) => {
 790                     collector.visit_lifetime_ref(lifetime);
 791
 792                     for bound in bounds {
 793                         collector.visit_lifetime_ref(bound);
 794                     }
 795                 }
 796                 &ast::WherePredicate::EqPredicate(_) => unimplemented!()
 797             }
 798         }
 799     }
 800
 801     // Any lifetime that either has a bound or is referenced by a
 802     // bound is early.
 803     for lifetime_def in &generics.lifetimes {
 804         if !lifetime_def.bounds.is_empty() {
 805             shuffle(&mut early_bound, &mut late_bound,
 806                     lifetime_def.lifetime.name);
 807             for bound in &lifetime_def.bounds {
 808                 shuffle(&mut early_bound, &mut late_bound,
 809                         bound.name);
 810             }
 811         }
 812     }
 813     return early_bound;
 814
 815     struct FreeLifetimeCollector<'a> {
 816         early_bound: &'a mut Vec<ast::Name>,
 817         late_bound: &'a mut Vec<ast::Name>,
 818     }
 819
 820     impl<'a, 'v> Visitor<'v> for FreeLifetimeCollector<'a> {
 821         fn visit_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 822             shuffle(self.early_bound, self.late_bound,
 823                     lifetime_ref.name);
 824         }
 825     }
 826
 827     fn shuffle(early_bound: &mut Vec<ast::Name>,
 828                late_bound: &mut Vec<ast::Name>,
 829                name: ast::Name) {
 830         match late_bound.iter().position(|n| *n == name) {
 831             Some(index) => {
 832                 late_bound.swap_remove(index);
 833                 early_bound.push(name);
 834             }
 835             None => { }
 836         }
 837     }
 838 }
 839
 840 impl<'a> fmt::Debug for ScopeChain<'a> {
 841     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 842         match *self {
 843             EarlyScope(space, defs, _) => write!(fmt, "EarlyScope({:?}, {:?})", space, defs),
 844             LateScope(defs, _) => write!(fmt, "LateScope({:?})", defs),
 845             BlockScope(id, _) => write!(fmt, "BlockScope({:?})", id),
 846             RootScope => write!(fmt, "RootScope"),
 847         }
 848     }
 849 }