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