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.
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.
11 //! Name resolution for lifetimes.
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.
18 pub use self::DefRegion
::*;
19 use self::ScopeChain
::*;
22 use middle
::def
::{self, DefMap}
;
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}
;
33 use syntax
::visit
::Visitor
;
34 use util
::nodemap
::NodeMap
;
36 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Show)]
39 DefEarlyBoundRegion(/* space */ subst
::ParamSpace
,
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
),
48 // maps the id of each lifetime reference to the lifetime decl
49 // that it corresponds to
50 pub type NamedRegionMap
= NodeMap
<DefRegion
>;
52 struct LifetimeContext
<'a
> {
54 named_region_map
: &'a
mut NamedRegionMap
,
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
68 BlockScope(region
::CodeExtent
, Scope
<'a
>),
72 type Scope
<'a
> = &'a ScopeChain
<'a
>;
74 static ROOT_SCOPE
: ScopeChain
<'
static> = RootScope
;
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
{
80 named_region_map
: &mut named_region_map
,
84 sess
.abort_if_errors();
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
| {
94 // Fn lifetimes get added in visit_fn below:
95 visit
::walk_item(this
, item
);
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
);
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
);
122 fn visit_fn(&mut self, fk
: visit
::FnKind
<'v
>, fd
: &'v ast
::FnDecl
,
123 b
: &'v ast
::Block
, s
: Span
, _
: ast
::NodeId
) {
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
)
131 visit
::FkFnBlock(..) => {
132 visit
::walk_fn(self, fk
, fd
, b
, s
)
137 fn visit_ty(&mut self, ty
: &ast
::Ty
) {
139 ast
::TyBareFn(ref c
) => {
140 visit
::walk_lifetime_decls_helper(self, &c
.lifetimes
);
141 self.with(LateScope(&c
.lifetimes
, self.scope
), |old_scope
, this
| {
142 // a bare fn has no bounds, so everything
143 // contained within is scoped within its binder.
144 this
.check_lifetime_defs(old_scope
, &c
.lifetimes
);
145 visit
::walk_ty(this
, ty
);
148 ast
::TyPath(ref path
, id
) => {
149 // if this path references a trait, then this will resolve to
150 // a trait ref, which introduces a binding scope.
151 match self.def_map
.borrow().get(&id
) {
152 Some(&def
::DefTrait(..)) => {
153 self.with(LateScope(&Vec
::new(), self.scope
), |_
, this
| {
154 this
.visit_path(path
, id
);
158 visit
::walk_ty(self, ty
);
163 visit
::walk_ty(self, ty
)
168 fn visit_ty_method(&mut self, m
: &ast
::TypeMethod
) {
169 self.visit_early_late(
170 subst
::FnSpace
, &m
.generics
,
171 |this
| visit
::walk_ty_method(this
, m
))
174 fn visit_block(&mut self, b
: &ast
::Block
) {
175 self.with(BlockScope(region
::CodeExtent
::from_node_id(b
.id
), self.scope
),
176 |_
, this
| visit
::walk_block(this
, b
));
179 fn visit_lifetime_ref(&mut self, lifetime_ref
: &ast
::Lifetime
) {
180 if lifetime_ref
.name
== special_idents
::static_lifetime
.name
{
181 self.insert_lifetime(lifetime_ref
, DefStaticRegion
);
184 self.resolve_lifetime_ref(lifetime_ref
);
187 fn visit_generics(&mut self, generics
: &ast
::Generics
) {
188 for ty_param
in generics
.ty_params
.iter() {
189 visit
::walk_ty_param_bounds_helper(self, &ty_param
.bounds
);
190 match ty_param
.default {
191 Some(ref ty
) => self.visit_ty(&**ty
),
195 for predicate
in generics
.where_clause
.predicates
.iter() {
197 &ast
::WherePredicate
::BoundPredicate(ast
::WhereBoundPredicate
{ ref bounded_ty
,
200 self.visit_ty(&**bounded_ty
);
201 visit
::walk_ty_param_bounds_helper(self, bounds
);
203 &ast
::WherePredicate
::RegionPredicate(ast
::WhereRegionPredicate
{ref lifetime
,
207 self.visit_lifetime_ref(lifetime
);
208 for bound
in bounds
.iter() {
209 self.visit_lifetime_ref(bound
);
212 &ast
::WherePredicate
::EqPredicate(ast
::WhereEqPredicate
{ id
,
216 self.visit_path(path
, id
);
217 self.visit_ty(&**ty
);
223 fn visit_poly_trait_ref(&mut self, trait_ref
:
225 _modifier
: &ast
::TraitBoundModifier
) {
226 debug
!("visit_poly_trait_ref trait_ref={:?}", trait_ref
);
228 self.with(LateScope(&trait_ref
.bound_lifetimes
, self.scope
), |old_scope
, this
| {
229 this
.check_lifetime_defs(old_scope
, &trait_ref
.bound_lifetimes
);
230 for lifetime
in trait_ref
.bound_lifetimes
.iter() {
231 this
.visit_lifetime_def(lifetime
);
233 this
.visit_trait_ref(&trait_ref
.trait_ref
)
237 fn visit_trait_ref(&mut self, trait_ref
: &ast
::TraitRef
) {
238 self.visit_path(&trait_ref
.path
, trait_ref
.ref_id
);
242 impl<'a
> LifetimeContext
<'a
> {
243 fn with
<F
>(&mut self, wrap_scope
: ScopeChain
, f
: F
) where
244 F
: FnOnce(Scope
, &mut LifetimeContext
),
246 let LifetimeContext {sess, ref mut named_region_map, ..}
= *self;
247 let mut this
= LifetimeContext
{
249 named_region_map
: *named_region_map
,
251 def_map
: self.def_map
,
253 debug
!("entering scope {:?}", this
.scope
);
254 f(self.scope
, &mut this
);
255 debug
!("exiting scope {:?}", this
.scope
);
258 /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
260 /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
261 /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
262 /// within type bounds; those are early bound lifetimes, and the rest are late bound.
266 /// fn foo<'a,'b,'c,T:Trait<'b>>(...)
268 /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
269 /// lifetimes may be interspersed together.
271 /// If early bound lifetimes are present, we separate them into their own list (and likewise
272 /// for late bound). They will be numbered sequentially, starting from the lowest index that is
273 /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
274 /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
275 /// ordering is not important there.
276 fn visit_early_late
<F
>(&mut self,
277 early_space
: subst
::ParamSpace
,
278 generics
: &ast
::Generics
,
280 F
: FnOnce(&mut LifetimeContext
),
282 let referenced_idents
= early_bound_lifetime_names(generics
);
284 debug
!("visit_early_late: referenced_idents={:?}",
287 let (early
, late
): (Vec
<_
>, _
) = generics
.lifetimes
.iter().cloned().partition(
288 |l
| referenced_idents
.iter().any(|&i
| i
== l
.lifetime
.name
));
290 self.with(EarlyScope(early_space
, &early
, self.scope
), move |old_scope
, this
| {
291 this
.with(LateScope(&late
, this
.scope
), move |_
, this
| {
292 this
.check_lifetime_defs(old_scope
, &generics
.lifetimes
);
298 fn resolve_lifetime_ref(&mut self, lifetime_ref
: &ast
::Lifetime
) {
299 // Walk up the scope chain, tracking the number of fn scopes
300 // that we pass through, until we find a lifetime with the
301 // given name or we run out of scopes. If we encounter a code
302 // block, then the lifetime is not bound but free, so switch
303 // over to `resolve_free_lifetime_ref()` to complete the
305 let mut late_depth
= 0;
306 let mut scope
= self.scope
;
309 BlockScope(blk_scope
, s
) => {
310 return self.resolve_free_lifetime_ref(blk_scope
, lifetime_ref
, s
);
317 EarlyScope(space
, lifetimes
, s
) => {
318 match search_lifetimes(lifetimes
, lifetime_ref
) {
319 Some((index
, lifetime_def
)) => {
320 let decl_id
= lifetime_def
.id
;
321 let def
= DefEarlyBoundRegion(space
, index
, decl_id
);
322 self.insert_lifetime(lifetime_ref
, def
);
331 LateScope(lifetimes
, s
) => {
332 match search_lifetimes(lifetimes
, lifetime_ref
) {
333 Some((_index
, lifetime_def
)) => {
334 let decl_id
= lifetime_def
.id
;
335 let debruijn
= ty
::DebruijnIndex
::new(late_depth
+ 1);
336 let def
= DefLateBoundRegion(debruijn
, decl_id
);
337 self.insert_lifetime(lifetime_ref
, def
);
350 self.unresolved_lifetime_ref(lifetime_ref
);
353 fn resolve_free_lifetime_ref(&mut self,
354 scope_data
: region
::CodeExtent
,
355 lifetime_ref
: &ast
::Lifetime
,
357 // Walk up the scope chain, tracking the outermost free scope,
358 // until we encounter a scope that contains the named lifetime
359 // or we run out of scopes.
360 let mut scope_data
= scope_data
;
361 let mut scope
= scope
;
362 let mut search_result
= None
;
365 BlockScope(blk_scope_data
, s
) => {
366 scope_data
= blk_scope_data
;
374 EarlyScope(_
, lifetimes
, s
) |
375 LateScope(lifetimes
, s
) => {
376 search_result
= search_lifetimes(lifetimes
, lifetime_ref
);
377 if search_result
.is_some() {
385 match search_result
{
386 Some((_depth
, lifetime
)) => {
387 let def
= DefFreeRegion(scope_data
, lifetime
.id
);
388 self.insert_lifetime(lifetime_ref
, def
);
392 self.unresolved_lifetime_ref(lifetime_ref
);
398 fn unresolved_lifetime_ref(&self, lifetime_ref
: &ast
::Lifetime
) {
401 &format
!("use of undeclared lifetime name `{}`",
402 token
::get_name(lifetime_ref
.name
))[]);
405 fn check_lifetime_defs(&mut self, old_scope
: Scope
, lifetimes
: &Vec
<ast
::LifetimeDef
>) {
406 for i
in range(0, lifetimes
.len()) {
407 let lifetime_i
= &lifetimes
[i
];
409 let special_idents
= [special_idents
::static_lifetime
];
410 for lifetime
in lifetimes
.iter() {
411 if special_idents
.iter().any(|&i
| i
.name
== lifetime
.lifetime
.name
) {
413 lifetime
.lifetime
.span
,
414 &format
!("illegal lifetime parameter name: `{}`",
415 token
::get_name(lifetime
.lifetime
.name
))
420 // It is a hard error to shadow a lifetime within the same scope.
421 for j
in range(i
+ 1, lifetimes
.len()) {
422 let lifetime_j
= &lifetimes
[j
];
424 if lifetime_i
.lifetime
.name
== lifetime_j
.lifetime
.name
{
426 lifetime_j
.lifetime
.span
,
427 &format
!("lifetime name `{}` declared twice in \
429 token
::get_name(lifetime_j
.lifetime
.name
))
434 // It is a soft error to shadow a lifetime within a parent scope.
435 self.check_lifetime_def_for_shadowing(old_scope
, &lifetime_i
.lifetime
);
437 for bound
in lifetime_i
.bounds
.iter() {
438 self.resolve_lifetime_ref(bound
);
443 fn check_lifetime_def_for_shadowing(&self,
444 mut old_scope
: Scope
,
445 lifetime
: &ast
::Lifetime
)
449 BlockScope(_
, s
) => {
457 EarlyScope(_
, lifetimes
, s
) |
458 LateScope(lifetimes
, s
) => {
459 if let Some((_
, lifetime_def
)) = search_lifetimes(lifetimes
, lifetime
) {
462 format
!("lifetime name `{}` shadows another \
463 lifetime name that is already in scope",
464 token
::get_name(lifetime
.name
)).as_slice());
467 format
!("shadowed lifetime `{}` declared here",
468 token
::get_name(lifetime
.name
)).as_slice());
471 "shadowed lifetimes are deprecated \
472 and will become a hard error before 1.0");
482 fn insert_lifetime(&mut self,
483 lifetime_ref
: &ast
::Lifetime
,
485 if lifetime_ref
.id
== ast
::DUMMY_NODE_ID
{
486 self.sess
.span_bug(lifetime_ref
.span
,
487 "lifetime reference not renumbered, \
488 probably a bug in syntax::fold");
491 debug
!("lifetime_ref={:?} id={:?} resolved to {:?}",
492 lifetime_to_string(lifetime_ref
),
495 self.named_region_map
.insert(lifetime_ref
.id
, def
);
499 fn search_lifetimes
<'a
>(lifetimes
: &'a Vec
<ast
::LifetimeDef
>,
500 lifetime_ref
: &ast
::Lifetime
)
501 -> Option
<(u32, &'a ast
::Lifetime
)> {
502 for (i
, lifetime_decl
) in lifetimes
.iter().enumerate() {
503 if lifetime_decl
.lifetime
.name
== lifetime_ref
.name
{
504 return Some((i
as u32, &lifetime_decl
.lifetime
));
510 ///////////////////////////////////////////////////////////////////////////
512 pub fn early_bound_lifetimes
<'a
>(generics
: &'a ast
::Generics
) -> Vec
<ast
::LifetimeDef
> {
513 let referenced_idents
= early_bound_lifetime_names(generics
);
514 if referenced_idents
.is_empty() {
518 generics
.lifetimes
.iter()
519 .filter(|l
| referenced_idents
.iter().any(|&i
| i
== l
.lifetime
.name
))
520 .map(|l
| (*l
).clone())
524 /// Given a set of generic declarations, returns a list of names containing all early bound
525 /// lifetime names for those generics. (In fact, this list may also contain other names.)
526 fn early_bound_lifetime_names(generics
: &ast
::Generics
) -> Vec
<ast
::Name
> {
527 // Create two lists, dividing the lifetimes into early/late bound.
528 // Initially, all of them are considered late, but we will move
529 // things from late into early as we go if we find references to
531 let mut early_bound
= Vec
::new();
532 let mut late_bound
= generics
.lifetimes
.iter()
533 .map(|l
| l
.lifetime
.name
)
536 // Any lifetime that appears in a type bound is early.
539 FreeLifetimeCollector
{ early_bound
: &mut early_bound
,
540 late_bound
: &mut late_bound
};
541 for ty_param
in generics
.ty_params
.iter() {
542 visit
::walk_ty_param_bounds_helper(&mut collector
, &ty_param
.bounds
);
544 for predicate
in generics
.where_clause
.predicates
.iter() {
546 &ast
::WherePredicate
::BoundPredicate(ast
::WhereBoundPredicate
{ref bounds
,
549 collector
.visit_ty(&**bounded_ty
);
550 visit
::walk_ty_param_bounds_helper(&mut collector
, bounds
);
552 &ast
::WherePredicate
::RegionPredicate(ast
::WhereRegionPredicate
{ref lifetime
,
555 collector
.visit_lifetime_ref(lifetime
);
557 for bound
in bounds
.iter() {
558 collector
.visit_lifetime_ref(bound
);
561 &ast
::WherePredicate
::EqPredicate(_
) => unimplemented
!()
566 // Any lifetime that either has a bound or is referenced by a
568 for lifetime_def
in generics
.lifetimes
.iter() {
569 if !lifetime_def
.bounds
.is_empty() {
570 shuffle(&mut early_bound
, &mut late_bound
,
571 lifetime_def
.lifetime
.name
);
572 for bound
in lifetime_def
.bounds
.iter() {
573 shuffle(&mut early_bound
, &mut late_bound
,
580 struct FreeLifetimeCollector
<'a
> {
581 early_bound
: &'a
mut Vec
<ast
::Name
>,
582 late_bound
: &'a
mut Vec
<ast
::Name
>,
585 impl<'a
, 'v
> Visitor
<'v
> for FreeLifetimeCollector
<'a
> {
586 fn visit_lifetime_ref(&mut self, lifetime_ref
: &ast
::Lifetime
) {
587 shuffle(self.early_bound
, self.late_bound
,
592 fn shuffle(early_bound
: &mut Vec
<ast
::Name
>,
593 late_bound
: &mut Vec
<ast
::Name
>,
595 match late_bound
.iter().position(|n
| *n
== name
) {
597 late_bound
.swap_remove(index
);
598 early_bound
.push(name
);
605 impl<'a
> fmt
::Show
for ScopeChain
<'a
> {
606 fn fmt(&self, fmt
: &mut fmt
::Formatter
) -> fmt
::Result
{
608 EarlyScope(space
, defs
, _
) => write
!(fmt
, "EarlyScope({:?}, {:?})", space
, defs
),
609 LateScope(defs
, _
) => write
!(fmt
, "LateScope({:?})", defs
),
610 BlockScope(id
, _
) => write
!(fmt
, "BlockScope({:?})", id
),
611 RootScope
=> write
!(fmt
, "RootScope"),