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::parse::token::special_idents;
  25 use syntax::parse::token;
  26 use syntax::print::pprust::{lifetime_to_string};
  27 use syntax::visit;
  28 use syntax::visit::Visitor;
  29 use util::nodemap::NodeMap;
  30
  31 #[deriving(Clone, PartialEq, Eq, Hash, Encodable, Decodable, Show)]
  32 pub enum DefRegion {
  33     DefStaticRegion,
  34     DefEarlyBoundRegion(/* space */ subst::ParamSpace,
  35                         /* index */ uint,
  36                         /* lifetime decl */ ast::NodeId),
  37     DefLateBoundRegion(/* binder_id */ ast::NodeId,
  38                        /* depth */ uint,
  39                        /* lifetime decl */ ast::NodeId),
  40     DefFreeRegion(/* block scope */ ast::NodeId,
  41                   /* lifetime decl */ ast::NodeId),
  42 }
  43
  44 // maps the id of each lifetime reference to the lifetime decl
  45 // that it corresponds to
  46 pub type NamedRegionMap = NodeMap<DefRegion>;
  47
  48 // Returns an instance of some type that implements std::fmt::Show
  49 fn lifetime_show(lt_name: &ast::Name) -> token::InternedString {
  50     token::get_name(*lt_name)
  51 }
  52
  53 struct LifetimeContext<'a> {
  54     sess: &'a Session,
  55     named_region_map: &'a mut NamedRegionMap,
  56     scope: Scope<'a>
  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(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::LifetimeDef>, 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 static ROOT_SCOPE: ScopeChain<'static> = RootScope;
  75
  76 pub fn krate(sess: &Session, krate: &ast::Crate) -> 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     }, krate);
  83     sess.abort_if_errors();
  84     named_region_map
  85 }
  86
  87 impl<'a, 'v> Visitor<'v> for LifetimeContext<'a> {
  88     fn visit_item(&mut self, item: &ast::Item) {
  89         let lifetimes = 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                 self.with(|_, f| f(RootScope), |v| visit::walk_item(v, item));
  96                 return;
  97             }
  98             ast::ItemTy(_, ref generics) |
  99             ast::ItemEnum(_, ref generics) |
 100             ast::ItemStruct(_, ref generics) |
 101             ast::ItemImpl(ref generics, _, _, _) |
 102             ast::ItemTrait(ref generics, _, _, _) => &generics.lifetimes
 103         };
 104
 105         self.with(|_, f| f(EarlyScope(subst::TypeSpace, lifetimes, &ROOT_SCOPE)), |v| {
 106             debug!("entering scope {:?}", v.scope);
 107             v.check_lifetime_defs(lifetimes);
 108             visit::walk_item(v, item);
 109             debug!("exiting scope {:?}", v.scope);
 110         });
 111     }
 112
 113     fn visit_fn(&mut self, fk: visit::FnKind<'v>, fd: &'v ast::FnDecl,
 114                 b: &'v ast::Block, s: Span, n: ast::NodeId) {
 115         match fk {
 116             visit::FkItemFn(_, generics, _, _) |
 117             visit::FkMethod(_, generics, _) => {
 118                 self.visit_fn_decl(n, generics, |v| visit::walk_fn(v, fk, fd, b, s))
 119             }
 120             visit::FkFnBlock(..) => {
 121                 visit::walk_fn(self, fk, fd, b, s)
 122             }
 123         }
 124     }
 125
 126     fn visit_ty(&mut self, ty: &ast::Ty) {
 127         let lifetimes = match ty.node {
 128             ast::TyClosure(ref c) | ast::TyProc(ref c) => &c.lifetimes,
 129             ast::TyBareFn(ref c) => &c.lifetimes,
 130             _ => return visit::walk_ty(self, ty)
 131         };
 132
 133         self.with(|scope, f| f(LateScope(ty.id, lifetimes, scope)), |v| {
 134             v.check_lifetime_defs(lifetimes);
 135             debug!("pushing fn scope id={} due to type", ty.id);
 136             visit::walk_ty(v, ty);
 137             debug!("popping fn scope id={} due to type", ty.id);
 138         });
 139     }
 140
 141     fn visit_ty_method(&mut self, m: &ast::TypeMethod) {
 142         self.visit_fn_decl(m.id, &m.generics, |v| visit::walk_ty_method(v, m))
 143     }
 144
 145     fn visit_block(&mut self, b: &ast::Block) {
 146         debug!("pushing block scope {}", b.id);
 147         self.with(|scope, f| f(BlockScope(b.id, scope)), |v| visit::walk_block(v, b));
 148         debug!("popping block scope {}", b.id);
 149     }
 150
 151     fn visit_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 152         if lifetime_ref.name == special_idents::static_lifetime.name {
 153             self.insert_lifetime(lifetime_ref, DefStaticRegion);
 154             return;
 155         }
 156         self.resolve_lifetime_ref(lifetime_ref);
 157     }
 158 }
 159
 160 impl<'a> LifetimeContext<'a> {
 161     fn with(&mut self, wrap_scope: |Scope, |ScopeChain||, f: |&mut LifetimeContext|) {
 162         let LifetimeContext { sess, ref mut named_region_map, scope} = *self;
 163         wrap_scope(scope, |scope1| f(&mut LifetimeContext {
 164             sess: sess,
 165             named_region_map: *named_region_map,
 166             scope: &scope1
 167         }))
 168     }
 169
 170     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
 171     fn visit_fn_decl(&mut self,
 172                      n: ast::NodeId,
 173                      generics: &ast::Generics,
 174                      walk: |&mut LifetimeContext|) {
 175         /*!
 176          * Handles visiting fns and methods. These are a bit
 177          * complicated because we must distinguish early- vs late-bound
 178          * lifetime parameters. We do this by checking which lifetimes
 179          * appear within type bounds; those are early bound lifetimes,
 180          * and the rest are late bound.
 181          *
 182          * For example:
 183          *
 184          *    fn foo<'a,'b,'c,T:Trait<'b>>(...)
 185          *
 186          * Here `'a` and `'c` are late bound but `'b` is early
 187          * bound. Note that early- and late-bound lifetimes may be
 188          * interspersed together.
 189          *
 190          * If early bound lifetimes are present, we separate them into
 191          * their own list (and likewise for late bound). They will be
 192          * numbered sequentially, starting from the lowest index that
 193          * is already in scope (for a fn item, that will be 0, but for
 194          * a method it might not be). Late bound lifetimes are
 195          * resolved by name and associated with a binder id (`n`), so
 196          * the ordering is not important there.
 197          */
 198
 199         let referenced_idents = early_bound_lifetime_names(generics);
 200         debug!("pushing fn scope id={} due to fn item/method\
 201                referenced_idents={:?}",
 202                n,
 203                referenced_idents.iter().map(lifetime_show).collect::<Vec<token::InternedString>>());
 204         let lifetimes = &generics.lifetimes;
 205         if referenced_idents.is_empty() {
 206             self.with(|scope, f| f(LateScope(n, lifetimes, scope)), |v| {
 207                 v.check_lifetime_defs(lifetimes);
 208                 walk(v);
 209             });
 210         } else {
 211             let (early, late) = lifetimes.clone().partition(
 212                 |l| referenced_idents.iter().any(|&i| i == l.lifetime.name));
 213
 214             self.with(|scope, f| f(EarlyScope(subst::FnSpace, &early, scope)), |v| {
 215                 v.with(|scope1, f| f(LateScope(n, &late, scope1)), |v| {
 216                     v.check_lifetime_defs(lifetimes);
 217                     walk(v);
 218                 });
 219             });
 220         }
 221         debug!("popping fn scope id={} due to fn item/method", n);
 222     }
 223
 224     fn resolve_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 225         // Walk up the scope chain, tracking the number of fn scopes
 226         // that we pass through, until we find a lifetime with the
 227         // given name or we run out of scopes. If we encounter a code
 228         // block, then the lifetime is not bound but free, so switch
 229         // over to `resolve_free_lifetime_ref()` to complete the
 230         // search.
 231         let mut depth = 0;
 232         let mut scope = self.scope;
 233         loop {
 234             match *scope {
 235                 BlockScope(id, s) => {
 236                     return self.resolve_free_lifetime_ref(id, lifetime_ref, s);
 237                 }
 238
 239                 RootScope => {
 240                     break;
 241                 }
 242
 243                 EarlyScope(space, lifetimes, s) => {
 244                     match search_lifetimes(lifetimes, lifetime_ref) {
 245                         Some((index, decl_id)) => {
 246                             let def = DefEarlyBoundRegion(space, index, decl_id);
 247                             self.insert_lifetime(lifetime_ref, def);
 248                             return;
 249                         }
 250                         None => {
 251                             depth += 1;
 252                             scope = s;
 253                         }
 254                     }
 255                 }
 256
 257                 LateScope(binder_id, lifetimes, s) => {
 258                     match search_lifetimes(lifetimes, lifetime_ref) {
 259                         Some((_index, decl_id)) => {
 260                             let def = DefLateBoundRegion(binder_id, depth, decl_id);
 261                             self.insert_lifetime(lifetime_ref, def);
 262                             return;
 263                         }
 264
 265                         None => {
 266                             depth += 1;
 267                             scope = s;
 268                         }
 269                     }
 270                 }
 271             }
 272         }
 273
 274         self.unresolved_lifetime_ref(lifetime_ref);
 275     }
 276
 277     fn resolve_free_lifetime_ref(&mut self,
 278                                  scope_id: ast::NodeId,
 279                                  lifetime_ref: &ast::Lifetime,
 280                                  scope: Scope) {
 281         // Walk up the scope chain, tracking the outermost free scope,
 282         // until we encounter a scope that contains the named lifetime
 283         // or we run out of scopes.
 284         let mut scope_id = scope_id;
 285         let mut scope = scope;
 286         let mut search_result = None;
 287         loop {
 288             match *scope {
 289                 BlockScope(id, s) => {
 290                     scope_id = id;
 291                     scope = s;
 292                 }
 293
 294                 RootScope => {
 295                     break;
 296                 }
 297
 298                 EarlyScope(_, lifetimes, s) |
 299                 LateScope(_, lifetimes, s) => {
 300                     search_result = search_lifetimes(lifetimes, lifetime_ref);
 301                     if search_result.is_some() {
 302                         break;
 303                     }
 304                     scope = s;
 305                 }
 306             }
 307         }
 308
 309         match search_result {
 310             Some((_depth, decl_id)) => {
 311                 let def = DefFreeRegion(scope_id, decl_id);
 312                 self.insert_lifetime(lifetime_ref, def);
 313             }
 314
 315             None => {
 316                 self.unresolved_lifetime_ref(lifetime_ref);
 317             }
 318         }
 319
 320     }
 321
 322     fn unresolved_lifetime_ref(&self, lifetime_ref: &ast::Lifetime) {
 323         self.sess.span_err(
 324             lifetime_ref.span,
 325             format!("use of undeclared lifetime name `{}`",
 326                     token::get_name(lifetime_ref.name)).as_slice());
 327     }
 328
 329     fn check_lifetime_defs(&mut self, lifetimes: &Vec<ast::LifetimeDef>) {
 330         for i in range(0, lifetimes.len()) {
 331             let lifetime_i = lifetimes.get(i);
 332
 333             let special_idents = [special_idents::static_lifetime];
 334             for lifetime in lifetimes.iter() {
 335                 if special_idents.iter().any(|&i| i.name == lifetime.lifetime.name) {
 336                     self.sess.span_err(
 337                         lifetime.lifetime.span,
 338                         format!("illegal lifetime parameter name: `{}`",
 339                                 token::get_name(lifetime.lifetime.name))
 340                             .as_slice());
 341                 }
 342             }
 343
 344             for j in range(i + 1, lifetimes.len()) {
 345                 let lifetime_j = lifetimes.get(j);
 346
 347                 if lifetime_i.lifetime.name == lifetime_j.lifetime.name {
 348                     self.sess.span_err(
 349                         lifetime_j.lifetime.span,
 350                         format!("lifetime name `{}` declared twice in \
 351                                 the same scope",
 352                                 token::get_name(lifetime_j.lifetime.name))
 353                             .as_slice());
 354                 }
 355             }
 356
 357             for bound in lifetime_i.bounds.iter() {
 358                 self.resolve_lifetime_ref(bound);
 359             }
 360         }
 361     }
 362
 363     fn insert_lifetime(&mut self,
 364                        lifetime_ref: &ast::Lifetime,
 365                        def: DefRegion) {
 366         if lifetime_ref.id == ast::DUMMY_NODE_ID {
 367             self.sess.span_bug(lifetime_ref.span,
 368                                "lifetime reference not renumbered, \
 369                                probably a bug in syntax::fold");
 370         }
 371
 372         debug!("lifetime_ref={} id={} resolved to {:?}",
 373                 lifetime_to_string(lifetime_ref),
 374                 lifetime_ref.id,
 375                 def);
 376         self.named_region_map.insert(lifetime_ref.id, def);
 377     }
 378 }
 379
 380 fn search_lifetimes(lifetimes: &Vec<ast::LifetimeDef>,
 381                     lifetime_ref: &ast::Lifetime)
 382                     -> Option<(uint, ast::NodeId)> {
 383     for (i, lifetime_decl) in lifetimes.iter().enumerate() {
 384         if lifetime_decl.lifetime.name == lifetime_ref.name {
 385             return Some((i, lifetime_decl.lifetime.id));
 386         }
 387     }
 388     return None;
 389 }
 390
 391 ///////////////////////////////////////////////////////////////////////////
 392
 393 pub fn early_bound_lifetimes<'a>(generics: &'a ast::Generics) -> Vec<ast::LifetimeDef> {
 394     let referenced_idents = early_bound_lifetime_names(generics);
 395     if referenced_idents.is_empty() {
 396         return Vec::new();
 397     }
 398
 399     generics.lifetimes.iter()
 400         .filter(|l| referenced_idents.iter().any(|&i| i == l.lifetime.name))
 401         .map(|l| (*l).clone())
 402         .collect()
 403 }
 404
 405 fn early_bound_lifetime_names(generics: &ast::Generics) -> Vec<ast::Name> {
 406     /*!
 407      * Given a set of generic declarations, returns a list of names
 408      * containing all early bound lifetime names for those
 409      * generics. (In fact, this list may also contain other names.)
 410      */
 411
 412     // Create two lists, dividing the lifetimes into early/late bound.
 413     // Initially, all of them are considered late, but we will move
 414     // things from late into early as we go if we find references to
 415     // them.
 416     let mut early_bound = Vec::new();
 417     let mut late_bound = generics.lifetimes.iter()
 418                                            .map(|l| l.lifetime.name)
 419                                            .collect();
 420
 421     // Any lifetime that appears in a type bound is early.
 422     {
 423         let mut collector =
 424             FreeLifetimeCollector { early_bound: &mut early_bound,
 425                                     late_bound: &mut late_bound };
 426         for ty_param in generics.ty_params.iter() {
 427             visit::walk_ty_param_bounds(&mut collector, &ty_param.bounds);
 428         }
 429         for predicate in generics.where_clause.predicates.iter() {
 430             visit::walk_ty_param_bounds(&mut collector, &predicate.bounds);
 431         }
 432     }
 433
 434     // Any lifetime that either has a bound or is referenced by a
 435     // bound is early.
 436     for lifetime_def in generics.lifetimes.iter() {
 437         if !lifetime_def.bounds.is_empty() {
 438             shuffle(&mut early_bound, &mut late_bound,
 439                     lifetime_def.lifetime.name);
 440             for bound in lifetime_def.bounds.iter() {
 441                 shuffle(&mut early_bound, &mut late_bound,
 442                         bound.name);
 443             }
 444         }
 445     }
 446     return early_bound;
 447
 448     struct FreeLifetimeCollector<'a> {
 449         early_bound: &'a mut Vec<ast::Name>,
 450         late_bound: &'a mut Vec<ast::Name>,
 451     }
 452
 453     impl<'a, 'v> Visitor<'v> for FreeLifetimeCollector<'a> {
 454         fn visit_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) {
 455             shuffle(self.early_bound, self.late_bound,
 456                     lifetime_ref.name);
 457         }
 458     }
 459
 460     fn shuffle(early_bound: &mut Vec<ast::Name>,
 461                late_bound: &mut Vec<ast::Name>,
 462                name: ast::Name) {
 463         match late_bound.iter().position(|n| *n == name) {
 464             Some(index) => {
 465                 late_bound.swap_remove(index);
 466                 early_bound.push(name);
 467             }
 468             None => { }
 469         }
 470     }
 471 }