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