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 syntax::ast;
  28 use syntax::codemap::Span;
  29 use syntax::parse::token::special_idents;
  30 use syntax::parse::token;
  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
  75 enum ScopeChain<'a> {
  76     /// EarlyScope(i, ['a, 'b, ...], s) extends s with early-bound
  77     /// lifetimes, assigning indexes 'a => i, 'b => i+1, ... etc.
  78     EarlyScope(subst::ParamSpace, &'a Vec<ast::LifetimeDef>, Scope<'a>),
  79     /// LateScope(['a, 'b, ...], s) extends s with late-bound
  80     /// lifetimes introduced by the declaration binder_id.
  81     LateScope(&'a Vec<ast::LifetimeDef>, Scope<'a>),
  82     /// lifetimes introduced by items within a code block are scoped
  83     /// to that block.
  84     BlockScope(region::DestructionScopeData, Scope<'a>),
  85     RootScope
  86 }
  87
  88 type Scope<'a> = &'a ScopeChain<'a>;
  89
  90 static ROOT_SCOPE: ScopeChain<'static> = RootScope;
  91
  92 pub fn krate(sess: &Session, krate: &ast::Crate, def_map: &DefMap) -> NamedRegionMap {
  93     let mut named_region_map = NodeMap();
  94     visit::walk_crate(&mut LifetimeContext {
  95         sess: sess,
  96         named_region_map: &mut named_region_map,
  97         scope: &ROOT_SCOPE,
  98         def_map: def_map,
  99         trait_ref_hack: false,
 100     }, krate);
 101     sess.abort_if_errors();
 102     named_region_map
 103 }
 104
 105 impl<'a, 'v> Visitor<'v> for LifetimeContext<'a> {
 106     fn visit_item(&mut self, item: &ast::Item) {
 107         // Items always introduce a new root scope
 108         self.with(RootScope, |_, this| {
 109             match item.node {
 110                 ast::ItemFn(..) => {
 111                     // Fn lifetimes get added in visit_fn below:
 112                     visit::walk_item(this, item);
 113                 }
 114                 ast::ItemExternCrate(_) |
 115                 ast::ItemUse(_) |
 116                 ast::ItemMod(..) |
 117                 ast::ItemMac(..) |
 118                 ast::ItemForeignMod(..) |
 119                 ast::ItemStatic(..) |
 120                 ast::ItemConst(..) => {
 121                     // These sorts of items have no lifetime parameters at all.
 122                     visit::walk_item(this, item);
 123                 }
 124                 ast::ItemTy(_, ref generics) |
 125                 ast::ItemEnum(_, ref generics) |
 126                 ast::ItemStruct(_, ref generics) |
 127                 ast::ItemTrait(_, ref generics, _, _) |
 128                 ast::ItemImpl(_, _, ref generics, _, _, _) => {
 129                     // These kinds of items have only early bound lifetime parameters.
 130                     let lifetimes = &generics.lifetimes;
 131                     let early_scope = EarlyScope(subst::TypeSpace, lifetimes, &ROOT_SCOPE);
 132                     this.with(early_scope, |old_scope, this| {
 133                         this.check_lifetime_defs(old_scope, lifetimes);
 134                         visit::walk_item(this, item);
 135                     });
 136                 }
 137             }
 138         });
 139     }
 140
 141     fn visit_fn(&mut self, fk: visit::FnKind<'v>, fd: &'v ast::FnDecl,
 142                 b: &'v ast::Block, s: Span, _: ast::NodeId) {
 143         match fk {
 144             visit::FkItemFn(_, generics, _, _) |
 145             visit::FkMethod(_, generics, _) => {
 146                 self.visit_early_late(subst::FnSpace, generics, |this| {
 147                     visit::walk_fn(this, fk, fd, b, s)
 148                 })
 149             }
 150             visit::FkFnBlock(..) => {
 151                 visit::walk_fn(self, fk, fd, b, s)
 152             }
 153         }
 154     }
 155
 156     fn visit_ty(&mut self, ty: &ast::Ty) {
 157         match ty.node {
 158             ast::TyBareFn(ref c) => {
 159                 visit::walk_lifetime_decls_helper(self, &c.lifetimes);
 160                 self.with(LateScope(&c.lifetimes, self.scope), |old_scope, this| {
 161                     // a bare fn has no bounds, so everything
 162                     // contained within is scoped within its binder.
 163                     this.check_lifetime_defs(old_scope, &c.lifetimes);
 164                     visit::walk_ty(this, ty);
 165                 });
 166             }
 167             ast::TyPath(ref path, id) => {
 168                 // if this path references a trait, then this will resolve to
 169                 // a trait ref, which introduces a binding scope.
 170                 match self.def_map.borrow().get(&id) {
 171                     Some(&def::DefTrait(..)) => {
 172                         self.with(LateScope(&Vec::new(), self.scope), |_, this| {
 173                             this.visit_path(path, id);
 174                         });
 175                     }
 176                     _ => {
 177                         visit::walk_ty(self, ty);
 178                     }
 179                 }
 180             }
 181             _ => {
 182                 visit::walk_ty(self, ty)
 183             }
 184         }
 185     }
 186
 187     fn visit_ty_method(&mut self, m: &ast::TypeMethod) {
 188         self.visit_early_late(
 189             subst::FnSpace, &m.generics,
 190             |this| visit::walk_ty_method(this, m))
 191     }
 192
 193     fn visit_block(&mut self, b: &ast::Block) {
 194         self.with(BlockScope(region::DestructionScopeData::new(b.id),
 195                              self.scope),
 196                   |_, this| visit::walk_block(this, b));
 197     }
 198
 199     fn visit_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 200         if lifetime_ref.name == special_idents::static_lifetime.name {
 201             self.insert_lifetime(lifetime_ref, DefStaticRegion);
 202             return;
 203         }
 204         self.resolve_lifetime_ref(lifetime_ref);
 205     }
 206
 207     fn visit_generics(&mut self, generics: &ast::Generics) {
 208         for ty_param in &*generics.ty_params {
 209             visit::walk_ty_param_bounds_helper(self, &ty_param.bounds);
 210             match ty_param.default {
 211                 Some(ref ty) => self.visit_ty(&**ty),
 212                 None => {}
 213             }
 214         }
 215         for predicate in &generics.where_clause.predicates {
 216             match predicate {
 217                 &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ ref bounded_ty,
 218                                                                                ref bounds,
 219                                                                                ref bound_lifetimes,
 220                                                                                .. }) => {
 221                     if bound_lifetimes.len() > 0 {
 222                         self.trait_ref_hack = true;
 223                         let result = self.with(LateScope(bound_lifetimes, self.scope),
 224                                                |old_scope, this| {
 225                             this.check_lifetime_defs(old_scope, bound_lifetimes);
 226                             this.visit_ty(&**bounded_ty);
 227                             visit::walk_ty_param_bounds_helper(this, bounds);
 228                         });
 229                         self.trait_ref_hack = false;
 230                         result
 231                     } else {
 232                         self.visit_ty(&**bounded_ty);
 233                         visit::walk_ty_param_bounds_helper(self, bounds);
 234                     }
 235                 }
 236                 &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime,
 237                                                                                 ref bounds,
 238                                                                                 .. }) => {
 239
 240                     self.visit_lifetime_ref(lifetime);
 241                     for bound in bounds {
 242                         self.visit_lifetime_ref(bound);
 243                     }
 244                 }
 245                 &ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{ id,
 246                                                                          ref path,
 247                                                                          ref ty,
 248                                                                          .. }) => {
 249                     self.visit_path(path, id);
 250                     self.visit_ty(&**ty);
 251                 }
 252             }
 253         }
 254     }
 255
 256     fn visit_poly_trait_ref(&mut self,
 257                             trait_ref: &ast::PolyTraitRef,
 258                             _modifier: &ast::TraitBoundModifier) {
 259         debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
 260
 261         if !self.trait_ref_hack || trait_ref.bound_lifetimes.len() > 0 {
 262             if self.trait_ref_hack {
 263                 println!("{:?}", trait_ref.span);
 264                 span_err!(self.sess, trait_ref.span, E0316,
 265                           "nested quantification of lifetimes");
 266             }
 267             self.with(LateScope(&trait_ref.bound_lifetimes, self.scope), |old_scope, this| {
 268                 this.check_lifetime_defs(old_scope, &trait_ref.bound_lifetimes);
 269                 for lifetime in &trait_ref.bound_lifetimes {
 270                     this.visit_lifetime_def(lifetime);
 271                 }
 272                 this.visit_trait_ref(&trait_ref.trait_ref)
 273             })
 274         } else {
 275             self.visit_trait_ref(&trait_ref.trait_ref)
 276         }
 277     }
 278
 279     fn visit_trait_ref(&mut self, trait_ref: &ast::TraitRef) {
 280         self.visit_path(&trait_ref.path, trait_ref.ref_id);
 281     }
 282 }
 283
 284 impl<'a> LifetimeContext<'a> {
 285     fn with<F>(&mut self, wrap_scope: ScopeChain, f: F) where
 286         F: FnOnce(Scope, &mut LifetimeContext),
 287     {
 288         let LifetimeContext {sess, ref mut named_region_map, ..} = *self;
 289         let mut this = LifetimeContext {
 290             sess: sess,
 291             named_region_map: *named_region_map,
 292             scope: &wrap_scope,
 293             def_map: self.def_map,
 294             trait_ref_hack: self.trait_ref_hack,
 295         };
 296         debug!("entering scope {:?}", this.scope);
 297         f(self.scope, &mut this);
 298         debug!("exiting scope {:?}", this.scope);
 299     }
 300
 301     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
 302     ///
 303     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
 304     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
 305     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
 306     ///
 307     /// For example:
 308     ///
 309     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
 310     ///
 311     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
 312     /// lifetimes may be interspersed together.
 313     ///
 314     /// If early bound lifetimes are present, we separate them into their own list (and likewise
 315     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
 316     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
 317     /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
 318     /// ordering is not important there.
 319     fn visit_early_late<F>(&mut self,
 320                            early_space: subst::ParamSpace,
 321                            generics: &ast::Generics,
 322                            walk: F) where
 323         F: FnOnce(&mut LifetimeContext),
 324     {
 325         let referenced_idents = early_bound_lifetime_names(generics);
 326
 327         debug!("visit_early_late: referenced_idents={:?}",
 328                referenced_idents);
 329
 330         let (early, late): (Vec<_>, _) = generics.lifetimes.iter().cloned().partition(
 331             |l| referenced_idents.iter().any(|&i| i == l.lifetime.name));
 332
 333         self.with(EarlyScope(early_space, &early, self.scope), move |old_scope, this| {
 334             this.with(LateScope(&late, this.scope), move |_, this| {
 335                 this.check_lifetime_defs(old_scope, &generics.lifetimes);
 336                 walk(this);
 337             });
 338         });
 339     }
 340
 341     fn resolve_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 342         // Walk up the scope chain, tracking the number of fn scopes
 343         // that we pass through, until we find a lifetime with the
 344         // given name or we run out of scopes. If we encounter a code
 345         // block, then the lifetime is not bound but free, so switch
 346         // over to `resolve_free_lifetime_ref()` to complete the
 347         // search.
 348         let mut late_depth = 0;
 349         let mut scope = self.scope;
 350         loop {
 351             match *scope {
 352                 BlockScope(blk_scope, s) => {
 353                     return self.resolve_free_lifetime_ref(blk_scope, lifetime_ref, s);
 354                 }
 355
 356                 RootScope => {
 357                     break;
 358                 }
 359
 360                 EarlyScope(space, lifetimes, s) => {
 361                     match search_lifetimes(lifetimes, lifetime_ref) {
 362                         Some((index, lifetime_def)) => {
 363                             let decl_id = lifetime_def.id;
 364                             let def = DefEarlyBoundRegion(space, index, decl_id);
 365                             self.insert_lifetime(lifetime_ref, def);
 366                             return;
 367                         }
 368                         None => {
 369                             scope = s;
 370                         }
 371                     }
 372                 }
 373
 374                 LateScope(lifetimes, s) => {
 375                     match search_lifetimes(lifetimes, lifetime_ref) {
 376                         Some((_index, lifetime_def)) => {
 377                             let decl_id = lifetime_def.id;
 378                             let debruijn = ty::DebruijnIndex::new(late_depth + 1);
 379                             let def = DefLateBoundRegion(debruijn, decl_id);
 380                             self.insert_lifetime(lifetime_ref, def);
 381                             return;
 382                         }
 383
 384                         None => {
 385                             late_depth += 1;
 386                             scope = s;
 387                         }
 388                     }
 389                 }
 390             }
 391         }
 392
 393         self.unresolved_lifetime_ref(lifetime_ref);
 394     }
 395
 396     fn resolve_free_lifetime_ref(&mut self,
 397                                  scope_data: region::DestructionScopeData,
 398                                  lifetime_ref: &ast::Lifetime,
 399                                  scope: Scope) {
 400         debug!("resolve_free_lifetime_ref \
 401                 scope_data: {:?} lifetime_ref: {:?} scope: {:?}",
 402                scope_data, lifetime_ref, scope);
 403
 404         // Walk up the scope chain, tracking the outermost free scope,
 405         // until we encounter a scope that contains the named lifetime
 406         // or we run out of scopes.
 407         let mut scope_data = scope_data;
 408         let mut scope = scope;
 409         let mut search_result = None;
 410         loop {
 411             debug!("resolve_free_lifetime_ref \
 412                     scope_data: {:?} scope: {:?} search_result: {:?}",
 413                    scope_data, scope, search_result);
 414             match *scope {
 415                 BlockScope(blk_scope_data, s) => {
 416                     scope_data = blk_scope_data;
 417                     scope = s;
 418                 }
 419
 420                 RootScope => {
 421                     break;
 422                 }
 423
 424                 EarlyScope(_, lifetimes, s) |
 425                 LateScope(lifetimes, s) => {
 426                     search_result = search_lifetimes(lifetimes, lifetime_ref);
 427                     if search_result.is_some() {
 428                         break;
 429                     }
 430                     scope = s;
 431                 }
 432             }
 433         }
 434
 435         match search_result {
 436             Some((_depth, lifetime)) => {
 437                 let def = DefFreeRegion(scope_data, lifetime.id);
 438                 self.insert_lifetime(lifetime_ref, def);
 439             }
 440
 441             None => {
 442                 self.unresolved_lifetime_ref(lifetime_ref);
 443             }
 444         }
 445
 446     }
 447
 448     fn unresolved_lifetime_ref(&self, lifetime_ref: &ast::Lifetime) {
 449         span_err!(self.sess, lifetime_ref.span, E0261,
 450             "use of undeclared lifetime name `{}`",
 451                     token::get_name(lifetime_ref.name));
 452     }
 453
 454     fn check_lifetime_defs(&mut self, old_scope: Scope, lifetimes: &Vec<ast::LifetimeDef>) {
 455         for i in 0..lifetimes.len() {
 456             let lifetime_i = &lifetimes[i];
 457
 458             let special_idents = [special_idents::static_lifetime];
 459             for lifetime in lifetimes {
 460                 if special_idents.iter().any(|&i| i.name == lifetime.lifetime.name) {
 461                     span_err!(self.sess, lifetime.lifetime.span, E0262,
 462                         "illegal lifetime parameter name: `{}`",
 463                                 token::get_name(lifetime.lifetime.name));
 464                 }
 465             }
 466
 467             // It is a hard error to shadow a lifetime within the same scope.
 468             for j in i + 1..lifetimes.len() {
 469                 let lifetime_j = &lifetimes[j];
 470
 471                 if lifetime_i.lifetime.name == lifetime_j.lifetime.name {
 472                     span_err!(self.sess, lifetime_j.lifetime.span, E0263,
 473                         "lifetime name `{}` declared twice in \
 474                                 the same scope",
 475                                 token::get_name(lifetime_j.lifetime.name));
 476                 }
 477             }
 478
 479             // It is a soft error to shadow a lifetime within a parent scope.
 480             self.check_lifetime_def_for_shadowing(old_scope, &lifetime_i.lifetime);
 481
 482             for bound in &lifetime_i.bounds {
 483                 self.resolve_lifetime_ref(bound);
 484             }
 485         }
 486     }
 487
 488     fn check_lifetime_def_for_shadowing(&self,
 489                                         mut old_scope: Scope,
 490                                         lifetime: &ast::Lifetime)
 491     {
 492         loop {
 493             match *old_scope {
 494                 BlockScope(_, s) => {
 495                     old_scope = s;
 496                 }
 497
 498                 RootScope => {
 499                     return;
 500                 }
 501
 502                 EarlyScope(_, lifetimes, s) |
 503                 LateScope(lifetimes, s) => {
 504                     if let Some((_, lifetime_def)) = search_lifetimes(lifetimes, lifetime) {
 505                         self.sess.span_warn(
 506                             lifetime.span,
 507                             &format!("lifetime name `{}` shadows another \
 508                                      lifetime name that is already in scope",
 509                                      token::get_name(lifetime.name)));
 510                         self.sess.span_note(
 511                             lifetime_def.span,
 512                             &format!("shadowed lifetime `{}` declared here",
 513                                      token::get_name(lifetime.name)));
 514                         self.sess.span_note(
 515                             lifetime.span,
 516                             "shadowed lifetimes are deprecated \
 517                              and will become a hard error before 1.0");
 518                         return;
 519                     }
 520
 521                     old_scope = s;
 522                 }
 523             }
 524         }
 525     }
 526
 527     fn insert_lifetime(&mut self,
 528                        lifetime_ref: &ast::Lifetime,
 529                        def: DefRegion) {
 530         if lifetime_ref.id == ast::DUMMY_NODE_ID {
 531             self.sess.span_bug(lifetime_ref.span,
 532                                "lifetime reference not renumbered, \
 533                                probably a bug in syntax::fold");
 534         }
 535
 536         debug!("lifetime_ref={:?} id={:?} resolved to {:?}",
 537                 lifetime_to_string(lifetime_ref),
 538                 lifetime_ref.id,
 539                 def);
 540         self.named_region_map.insert(lifetime_ref.id, def);
 541     }
 542 }
 543
 544 fn search_lifetimes<'a>(lifetimes: &'a Vec<ast::LifetimeDef>,
 545                     lifetime_ref: &ast::Lifetime)
 546                     -> Option<(u32, &'a ast::Lifetime)> {
 547     for (i, lifetime_decl) in lifetimes.iter().enumerate() {
 548         if lifetime_decl.lifetime.name == lifetime_ref.name {
 549             return Some((i as u32, &lifetime_decl.lifetime));
 550         }
 551     }
 552     return None;
 553 }
 554
 555 ///////////////////////////////////////////////////////////////////////////
 556
 557 pub fn early_bound_lifetimes<'a>(generics: &'a ast::Generics) -> Vec<ast::LifetimeDef> {
 558     let referenced_idents = early_bound_lifetime_names(generics);
 559     if referenced_idents.is_empty() {
 560         return Vec::new();
 561     }
 562
 563     generics.lifetimes.iter()
 564         .filter(|l| referenced_idents.iter().any(|&i| i == l.lifetime.name))
 565         .cloned()
 566         .collect()
 567 }
 568
 569 /// Given a set of generic declarations, returns a list of names containing all early bound
 570 /// lifetime names for those generics. (In fact, this list may also contain other names.)
 571 fn early_bound_lifetime_names(generics: &ast::Generics) -> Vec<ast::Name> {
 572     // Create two lists, dividing the lifetimes into early/late bound.
 573     // Initially, all of them are considered late, but we will move
 574     // things from late into early as we go if we find references to
 575     // them.
 576     let mut early_bound = Vec::new();
 577     let mut late_bound = generics.lifetimes.iter()
 578                                            .map(|l| l.lifetime.name)
 579                                            .collect();
 580
 581     // Any lifetime that appears in a type bound is early.
 582     {
 583         let mut collector =
 584             FreeLifetimeCollector { early_bound: &mut early_bound,
 585                                     late_bound: &mut late_bound };
 586         for ty_param in &*generics.ty_params {
 587             visit::walk_ty_param_bounds_helper(&mut collector, &ty_param.bounds);
 588         }
 589         for predicate in &generics.where_clause.predicates {
 590             match predicate {
 591                 &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ref bounds,
 592                                                                               ref bounded_ty,
 593                                                                               ..}) => {
 594                     collector.visit_ty(&**bounded_ty);
 595                     visit::walk_ty_param_bounds_helper(&mut collector, bounds);
 596                 }
 597                 &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime,
 598                                                                                 ref bounds,
 599                                                                                 ..}) => {
 600                     collector.visit_lifetime_ref(lifetime);
 601
 602                     for bound in bounds {
 603                         collector.visit_lifetime_ref(bound);
 604                     }
 605                 }
 606                 &ast::WherePredicate::EqPredicate(_) => unimplemented!()
 607             }
 608         }
 609     }
 610
 611     // Any lifetime that either has a bound or is referenced by a
 612     // bound is early.
 613     for lifetime_def in &generics.lifetimes {
 614         if !lifetime_def.bounds.is_empty() {
 615             shuffle(&mut early_bound, &mut late_bound,
 616                     lifetime_def.lifetime.name);
 617             for bound in &lifetime_def.bounds {
 618                 shuffle(&mut early_bound, &mut late_bound,
 619                         bound.name);
 620             }
 621         }
 622     }
 623     return early_bound;
 624
 625     struct FreeLifetimeCollector<'a> {
 626         early_bound: &'a mut Vec<ast::Name>,
 627         late_bound: &'a mut Vec<ast::Name>,
 628     }
 629
 630     impl<'a, 'v> Visitor<'v> for FreeLifetimeCollector<'a> {
 631         fn visit_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 632             shuffle(self.early_bound, self.late_bound,
 633                     lifetime_ref.name);
 634         }
 635     }
 636
 637     fn shuffle(early_bound: &mut Vec<ast::Name>,
 638                late_bound: &mut Vec<ast::Name>,
 639                name: ast::Name) {
 640         match late_bound.iter().position(|n| *n == name) {
 641             Some(index) => {
 642                 late_bound.swap_remove(index);
 643                 early_bound.push(name);
 644             }
 645             None => { }
 646         }
 647     }
 648 }
 649
 650 impl<'a> fmt::Debug for ScopeChain<'a> {
 651     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 652         match *self {
 653             EarlyScope(space, defs, _) => write!(fmt, "EarlyScope({:?}, {:?})", space, defs),
 654             LateScope(defs, _) => write!(fmt, "LateScope({:?})", defs),
 655             BlockScope(id, _) => write!(fmt, "BlockScope({:?})", id),
 656             RootScope => write!(fmt, "RootScope"),
 657         }
 658     }
 659 }