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