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