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 /*!
  12  * Name resolution for lifetimes.
  13  *
  14  * Name resolution for lifetimes follows MUCH simpler rules than the
  15  * full resolve. For example, lifetime names are never exported or
  16  * used between functions, and they operate in a purely top-down
  17  * way. Therefore we break lifetime name resolution into a separate pass.
  18  */
  19
  20 use driver::session::Session;
  21 use middle::subst;
  22 use syntax::ast;
  23 use syntax::codemap::Span;
  24 use syntax::owned_slice::OwnedSlice;
  25 use syntax::parse::token::special_idents;
  26 use syntax::parse::token;
  27 use syntax::print::pprust::{lifetime_to_str};
  28 use syntax::visit;
  29 use syntax::visit::Visitor;
  30 use util::nodemap::NodeMap;
  31
  32 #[deriving(Clone, PartialEq, Eq, Hash, Encodable, Decodable, Show)]
  33 pub enum DefRegion {
  34     DefStaticRegion,
  35     DefEarlyBoundRegion(/* space */ subst::ParamSpace,
  36                         /* index */ uint,
  37                         /* lifetime decl */ ast::NodeId),
  38     DefLateBoundRegion(/* binder_id */ ast::NodeId,
  39                        /* depth */ uint,
  40                        /* lifetime decl */ ast::NodeId),
  41     DefFreeRegion(/* block scope */ ast::NodeId,
  42                   /* lifetime decl */ ast::NodeId),
  43 }
  44
  45 // maps the id of each lifetime reference to the lifetime decl
  46 // that it corresponds to
  47 pub type NamedRegionMap = NodeMap<DefRegion>;
  48
  49 // Returns an instance of some type that implements std::fmt::Show
  50 fn lifetime_show(lt_name: &ast::Name) -> token::InternedString {
  51     token::get_name(*lt_name)
  52 }
  53
  54 struct LifetimeContext<'a> {
  55     sess: &'a Session,
  56     named_region_map: NamedRegionMap,
  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::Lifetime>, Scope<'a>),
  63     /// LateScope(binder_id, ['a, 'b, ...], s) extends s with late-bound
  64     /// lifetimes introduced by the declaration binder_id.
  65     LateScope(ast::NodeId, &'a Vec<ast::Lifetime>, Scope<'a>),
  66     /// lifetimes introduced by items within a code block are scoped
  67     /// to that block.
  68     BlockScope(ast::NodeId, Scope<'a>),
  69     RootScope
  70 }
  71
  72 type Scope<'a> = &'a ScopeChain<'a>;
  73
  74 pub fn krate(sess: &Session, krate: &ast::Crate) -> NamedRegionMap {
  75     let mut ctxt = LifetimeContext {
  76         sess: sess,
  77         named_region_map: NodeMap::new()
  78     };
  79     visit::walk_crate(&mut ctxt, krate, &RootScope);
  80     sess.abort_if_errors();
  81     ctxt.named_region_map
  82 }
  83
  84 impl<'a, 'b> Visitor<Scope<'a>> for LifetimeContext<'b> {
  85     fn visit_item(&mut self,
  86                   item: &ast::Item,
  87                   _: Scope<'a>) {
  88         let root = RootScope;
  89         let scope = match item.node {
  90             ast::ItemFn(..) | // fn lifetimes get added in visit_fn below
  91             ast::ItemMod(..) |
  92             ast::ItemMac(..) |
  93             ast::ItemForeignMod(..) |
  94             ast::ItemStatic(..) => {
  95                 RootScope
  96             }
  97             ast::ItemTy(_, ref generics) |
  98             ast::ItemEnum(_, ref generics) |
  99             ast::ItemStruct(_, ref generics) |
 100             ast::ItemImpl(ref generics, _, _, _) |
 101             ast::ItemTrait(ref generics, _, _, _) => {
 102                 self.check_lifetime_names(&generics.lifetimes);
 103                 EarlyScope(subst::TypeSpace, &generics.lifetimes, &root)
 104             }
 105         };
 106         debug!("entering scope {:?}", scope);
 107         visit::walk_item(self, item, &scope);
 108         debug!("exiting scope {:?}", scope);
 109     }
 110
 111     fn visit_fn(&mut self, fk: &visit::FnKind, fd: &ast::FnDecl,
 112                 b: &ast::Block, s: Span, n: ast::NodeId,
 113                 scope: Scope<'a>) {
 114         match *fk {
 115             visit::FkItemFn(_, generics, _, _) |
 116             visit::FkMethod(_, generics, _) => {
 117                 self.visit_fn_decl(
 118                     n, generics, scope,
 119                     |this, scope1| visit::walk_fn(this, fk, fd, b, s, scope1))
 120             }
 121             visit::FkFnBlock(..) => {
 122                 visit::walk_fn(self, fk, fd, b, s, scope)
 123             }
 124         }
 125     }
 126
 127     fn visit_ty(&mut self, ty: &ast::Ty, scope: Scope<'a>) {
 128         match ty.node {
 129             ast::TyClosure(c, _) | ast::TyProc(c) => {
 130                 push_fn_scope(self, ty, scope, &c.lifetimes);
 131             }
 132             ast::TyBareFn(c) => push_fn_scope(self, ty, scope, &c.lifetimes),
 133             _ => visit::walk_ty(self, ty, scope),
 134         }
 135
 136         fn push_fn_scope(this: &mut LifetimeContext,
 137                          ty: &ast::Ty,
 138                          scope: Scope,
 139                          lifetimes: &Vec<ast::Lifetime>) {
 140             let scope1 = LateScope(ty.id, lifetimes, scope);
 141             this.check_lifetime_names(lifetimes);
 142             debug!("pushing fn scope id={} due to type", ty.id);
 143             visit::walk_ty(this, ty, &scope1);
 144             debug!("popping fn scope id={} due to type", ty.id);
 145         }
 146     }
 147
 148     fn visit_ty_method(&mut self,
 149                        m: &ast::TypeMethod,
 150                        scope: Scope<'a>) {
 151         self.visit_fn_decl(
 152             m.id, &m.generics, scope,
 153             |this, scope1| visit::walk_ty_method(this, m, scope1))
 154     }
 155
 156     fn visit_block(&mut self,
 157                    b: &ast::Block,
 158                    scope: Scope<'a>) {
 159         let scope1 = BlockScope(b.id, scope);
 160         debug!("pushing block scope {}", b.id);
 161         visit::walk_block(self, b, &scope1);
 162         debug!("popping block scope {}", b.id);
 163     }
 164
 165     fn visit_lifetime_ref(&mut self,
 166                           lifetime_ref: &ast::Lifetime,
 167                           scope: Scope<'a>) {
 168         if lifetime_ref.name == special_idents::static_lifetime.name {
 169             self.insert_lifetime(lifetime_ref, DefStaticRegion);
 170             return;
 171         }
 172         self.resolve_lifetime_ref(lifetime_ref, scope);
 173     }
 174 }
 175
 176 impl<'a> LifetimeContext<'a> {
 177     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
 178     fn visit_fn_decl(&mut self,
 179                      n: ast::NodeId,
 180                      generics: &ast::Generics,
 181                      scope: Scope,
 182                      walk: |&mut LifetimeContext, Scope|) {
 183         /*!
 184          * Handles visiting fns and methods. These are a bit
 185          * complicated because we must distinguish early- vs late-bound
 186          * lifetime parameters. We do this by checking which lifetimes
 187          * appear within type bounds; those are early bound lifetimes,
 188          * and the rest are late bound.
 189          *
 190          * For example:
 191          *
 192          *    fn foo<'a,'b,'c,T:Trait<'b>>(...)
 193          *
 194          * Here `'a` and `'c` are late bound but `'b` is early
 195          * bound. Note that early- and late-bound lifetimes may be
 196          * interspersed together.
 197          *
 198          * If early bound lifetimes are present, we separate them into
 199          * their own list (and likewise for late bound). They will be
 200          * numbered sequentially, starting from the lowest index that
 201          * is already in scope (for a fn item, that will be 0, but for
 202          * a method it might not be). Late bound lifetimes are
 203          * resolved by name and associated with a binder id (`n`), so
 204          * the ordering is not important there.
 205          */
 206
 207         self.check_lifetime_names(&generics.lifetimes);
 208
 209         let referenced_idents = free_lifetimes(&generics.ty_params);
 210         debug!("pushing fn scope id={} due to fn item/method\
 211                referenced_idents={:?}",
 212                n,
 213                referenced_idents.iter().map(lifetime_show).collect::<Vec<token::InternedString>>());
 214         if referenced_idents.is_empty() {
 215             let scope1 = LateScope(n, &generics.lifetimes, scope);
 216             walk(self, &scope1)
 217         } else {
 218             let (early, late) = generics.lifetimes.clone().partition(
 219                 |l| referenced_idents.iter().any(|&i| i == l.name));
 220
 221             let scope1 = EarlyScope(subst::FnSpace, &early, scope);
 222             let scope2 = LateScope(n, &late, &scope1);
 223
 224             walk(self, &scope2);
 225         }
 226         debug!("popping fn scope id={} due to fn item/method", n);
 227     }
 228
 229     fn resolve_lifetime_ref(&mut self,
 230                             lifetime_ref: &ast::Lifetime,
 231                             scope: Scope) {
 232         // Walk up the scope chain, tracking the number of fn scopes
 233         // that we pass through, until we find a lifetime with the
 234         // given name or we run out of scopes. If we encounter a code
 235         // block, then the lifetime is not bound but free, so switch
 236         // over to `resolve_free_lifetime_ref()` to complete the
 237         // search.
 238         let mut depth = 0;
 239         let mut scope = scope;
 240         loop {
 241             match *scope {
 242                 BlockScope(id, s) => {
 243                     return self.resolve_free_lifetime_ref(id, lifetime_ref, s);
 244                 }
 245
 246                 RootScope => {
 247                     break;
 248                 }
 249
 250                 EarlyScope(space, lifetimes, s) => {
 251                     match search_lifetimes(lifetimes, lifetime_ref) {
 252                         Some((index, decl_id)) => {
 253                             let def = DefEarlyBoundRegion(space, index, decl_id);
 254                             self.insert_lifetime(lifetime_ref, def);
 255                             return;
 256                         }
 257                         None => {
 258                             depth += 1;
 259                             scope = s;
 260                         }
 261                     }
 262                 }
 263
 264                 LateScope(binder_id, lifetimes, s) => {
 265                     match search_lifetimes(lifetimes, lifetime_ref) {
 266                         Some((_index, decl_id)) => {
 267                             let def = DefLateBoundRegion(binder_id, depth, decl_id);
 268                             self.insert_lifetime(lifetime_ref, def);
 269                             return;
 270                         }
 271
 272                         None => {
 273                             depth += 1;
 274                             scope = s;
 275                         }
 276                     }
 277                 }
 278             }
 279         }
 280
 281         self.unresolved_lifetime_ref(lifetime_ref);
 282     }
 283
 284     fn resolve_free_lifetime_ref(&mut self,
 285                                  scope_id: ast::NodeId,
 286                                  lifetime_ref: &ast::Lifetime,
 287                                  scope: Scope) {
 288         // Walk up the scope chain, tracking the outermost free scope,
 289         // until we encounter a scope that contains the named lifetime
 290         // or we run out of scopes.
 291         let mut scope_id = scope_id;
 292         let mut scope = scope;
 293         let mut search_result = None;
 294         loop {
 295             match *scope {
 296                 BlockScope(id, s) => {
 297                     scope_id = id;
 298                     scope = s;
 299                 }
 300
 301                 RootScope => {
 302                     break;
 303                 }
 304
 305                 EarlyScope(_, lifetimes, s) |
 306                 LateScope(_, lifetimes, s) => {
 307                     search_result = search_lifetimes(lifetimes, lifetime_ref);
 308                     if search_result.is_some() {
 309                         break;
 310                     }
 311                     scope = s;
 312                 }
 313             }
 314         }
 315
 316         match search_result {
 317             Some((_depth, decl_id)) => {
 318                 let def = DefFreeRegion(scope_id, decl_id);
 319                 self.insert_lifetime(lifetime_ref, def);
 320             }
 321
 322             None => {
 323                 self.unresolved_lifetime_ref(lifetime_ref);
 324             }
 325         }
 326
 327     }
 328
 329     fn unresolved_lifetime_ref(&self,
 330                                lifetime_ref: &ast::Lifetime) {
 331         self.sess.span_err(
 332             lifetime_ref.span,
 333             format!("use of undeclared lifetime name `{}`",
 334                     token::get_name(lifetime_ref.name)).as_slice());
 335     }
 336
 337     fn check_lifetime_names(&self, lifetimes: &Vec<ast::Lifetime>) {
 338         for i in range(0, lifetimes.len()) {
 339             let lifetime_i = lifetimes.get(i);
 340
 341             let special_idents = [special_idents::static_lifetime];
 342             for lifetime in lifetimes.iter() {
 343                 if special_idents.iter().any(|&i| i.name == lifetime.name) {
 344                     self.sess.span_err(
 345                         lifetime.span,
 346                         format!("illegal lifetime parameter name: `{}`",
 347                                 token::get_name(lifetime.name)).as_slice());
 348                 }
 349             }
 350
 351             for j in range(i + 1, lifetimes.len()) {
 352                 let lifetime_j = lifetimes.get(j);
 353
 354                 if lifetime_i.name == lifetime_j.name {
 355                     self.sess.span_err(
 356                         lifetime_j.span,
 357                         format!("lifetime name `{}` declared twice in \
 358                                 the same scope",
 359                                 token::get_name(lifetime_j.name)).as_slice());
 360                 }
 361             }
 362         }
 363     }
 364
 365     fn insert_lifetime(&mut self,
 366                        lifetime_ref: &ast::Lifetime,
 367                        def: DefRegion) {
 368         if lifetime_ref.id == ast::DUMMY_NODE_ID {
 369             self.sess.span_bug(lifetime_ref.span,
 370                                "lifetime reference not renumbered, \
 371                                probably a bug in syntax::fold");
 372         }
 373
 374         debug!("lifetime_ref={} id={} resolved to {:?}",
 375                 lifetime_to_str(lifetime_ref),
 376                 lifetime_ref.id,
 377                 def);
 378         self.named_region_map.insert(lifetime_ref.id, def);
 379     }
 380 }
 381
 382 fn search_lifetimes(lifetimes: &Vec<ast::Lifetime>,
 383                     lifetime_ref: &ast::Lifetime)
 384                     -> Option<(uint, ast::NodeId)> {
 385     for (i, lifetime_decl) in lifetimes.iter().enumerate() {
 386         if lifetime_decl.name == lifetime_ref.name {
 387             return Some((i, lifetime_decl.id));
 388         }
 389     }
 390     return None;
 391 }
 392
 393 ///////////////////////////////////////////////////////////////////////////
 394
 395 pub fn early_bound_lifetimes<'a>(generics: &'a ast::Generics) -> Vec<ast::Lifetime> {
 396     let referenced_idents = free_lifetimes(&generics.ty_params);
 397     if referenced_idents.is_empty() {
 398         return Vec::new();
 399     }
 400
 401     generics.lifetimes.iter()
 402         .filter(|l| referenced_idents.iter().any(|&i| i == l.name))
 403         .map(|l| *l)
 404         .collect()
 405 }
 406
 407 pub fn free_lifetimes(ty_params: &OwnedSlice<ast::TyParam>) -> Vec<ast::Name> {
 408     /*!
 409      * Gathers up and returns the names of any lifetimes that appear
 410      * free in `ty_params`. Of course, right now, all lifetimes appear
 411      * free, since we don't currently have any binders in type parameter
 412      * declarations; just being forwards compatible with future extensions.
 413      */
 414
 415     let mut collector = FreeLifetimeCollector { names: vec!() };
 416     for ty_param in ty_params.iter() {
 417         visit::walk_ty_param_bounds(&mut collector, &ty_param.bounds, ());
 418     }
 419     return collector.names;
 420
 421     struct FreeLifetimeCollector {
 422         names: Vec<ast::Name>,
 423     }
 424
 425     impl Visitor<()> for FreeLifetimeCollector {
 426         fn visit_lifetime_ref(&mut self,
 427                               lifetime_ref: &ast::Lifetime,
 428                               _: ()) {
 429             self.names.push(lifetime_ref.name);
 430         }
 431     }
 432 }