]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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::{self, DefMap}; | |
23 | use middle::region; | |
24 | use middle::subst; | |
25 | use middle::ty; | |
26 | use std::fmt; | |
9346a6ac | 27 | use std::mem::replace; |
1a4d82fc JJ |
28 | use syntax::ast; |
29 | use syntax::codemap::Span; | |
30 | use syntax::parse::token::special_idents; | |
31 | use syntax::parse::token; | |
c34b1796 | 32 | use syntax::print::pprust::lifetime_to_string; |
1a4d82fc JJ |
33 | use syntax::visit; |
34 | use syntax::visit::Visitor; | |
35 | use util::nodemap::NodeMap; | |
36 | ||
85aaf69f | 37 | #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)] |
1a4d82fc JJ |
38 | pub enum DefRegion { |
39 | DefStaticRegion, | |
40 | DefEarlyBoundRegion(/* space */ subst::ParamSpace, | |
41 | /* index */ u32, | |
42 | /* lifetime decl */ ast::NodeId), | |
43 | DefLateBoundRegion(ty::DebruijnIndex, | |
44 | /* lifetime decl */ ast::NodeId), | |
85aaf69f | 45 | DefFreeRegion(/* block scope */ region::DestructionScopeData, |
1a4d82fc JJ |
46 | /* lifetime decl */ ast::NodeId), |
47 | } | |
48 | ||
85aaf69f SL |
49 | // Maps the id of each lifetime reference to the lifetime decl |
50 | // that it corresponds to. | |
1a4d82fc JJ |
51 | pub type NamedRegionMap = NodeMap<DefRegion>; |
52 | ||
53 | struct LifetimeContext<'a> { | |
54 | sess: &'a Session, | |
55 | named_region_map: &'a mut NamedRegionMap, | |
56 | scope: Scope<'a>, | |
57 | def_map: &'a DefMap, | |
85aaf69f SL |
58 | // Deep breath. Our representation for poly trait refs contains a single |
59 | // binder and thus we only allow a single level of quantification. However, | |
60 | // the syntax of Rust permits quantification in two places, e.g., `T: for <'a> Foo<'a>` | |
61 | // and `for <'a, 'b> &'b T: Foo<'a>`. In order to get the de Bruijn indices | |
62 | // correct when representing these constraints, we should only introduce one | |
63 | // scope. However, we want to support both locations for the quantifier and | |
64 | // during lifetime resolution we want precise information (so we can't | |
65 | // desugar in an earlier phase). | |
66 | ||
67 | // SO, if we encounter a quantifier at the outer scope, we set | |
68 | // trait_ref_hack to true (and introduce a scope), and then if we encounter | |
69 | // a quantifier at the inner scope, we error. If trait_ref_hack is false, | |
70 | // then we introduce the scope at the inner quantifier. | |
71 | ||
72 | // I'm sorry. | |
73 | trait_ref_hack: bool, | |
9346a6ac AL |
74 | |
75 | // List of labels in the function/method currently under analysis. | |
76 | labels_in_fn: Vec<(ast::Ident, Span)>, | |
1a4d82fc JJ |
77 | } |
78 | ||
79 | enum ScopeChain<'a> { | |
80 | /// EarlyScope(i, ['a, 'b, ...], s) extends s with early-bound | |
81 | /// lifetimes, assigning indexes 'a => i, 'b => i+1, ... etc. | |
82 | EarlyScope(subst::ParamSpace, &'a Vec<ast::LifetimeDef>, Scope<'a>), | |
83 | /// LateScope(['a, 'b, ...], s) extends s with late-bound | |
84 | /// lifetimes introduced by the declaration binder_id. | |
85 | LateScope(&'a Vec<ast::LifetimeDef>, Scope<'a>), | |
86 | /// lifetimes introduced by items within a code block are scoped | |
87 | /// to that block. | |
85aaf69f | 88 | BlockScope(region::DestructionScopeData, Scope<'a>), |
1a4d82fc JJ |
89 | RootScope |
90 | } | |
91 | ||
92 | type Scope<'a> = &'a ScopeChain<'a>; | |
93 | ||
94 | static ROOT_SCOPE: ScopeChain<'static> = RootScope; | |
95 | ||
96 | pub fn krate(sess: &Session, krate: &ast::Crate, def_map: &DefMap) -> NamedRegionMap { | |
85aaf69f | 97 | let mut named_region_map = NodeMap(); |
1a4d82fc JJ |
98 | visit::walk_crate(&mut LifetimeContext { |
99 | sess: sess, | |
100 | named_region_map: &mut named_region_map, | |
101 | scope: &ROOT_SCOPE, | |
102 | def_map: def_map, | |
85aaf69f | 103 | trait_ref_hack: false, |
9346a6ac | 104 | labels_in_fn: vec![], |
1a4d82fc JJ |
105 | }, krate); |
106 | sess.abort_if_errors(); | |
107 | named_region_map | |
108 | } | |
109 | ||
110 | impl<'a, 'v> Visitor<'v> for LifetimeContext<'a> { | |
111 | fn visit_item(&mut self, item: &ast::Item) { | |
9346a6ac AL |
112 | // Items save/restore the set of labels. This way innner items |
113 | // can freely reuse names, be they loop labels or lifetimes. | |
114 | let saved = replace(&mut self.labels_in_fn, vec![]); | |
115 | ||
1a4d82fc JJ |
116 | // Items always introduce a new root scope |
117 | self.with(RootScope, |_, this| { | |
118 | match item.node { | |
119 | ast::ItemFn(..) => { | |
120 | // Fn lifetimes get added in visit_fn below: | |
121 | visit::walk_item(this, item); | |
122 | } | |
85aaf69f SL |
123 | ast::ItemExternCrate(_) | |
124 | ast::ItemUse(_) | | |
1a4d82fc JJ |
125 | ast::ItemMod(..) | |
126 | ast::ItemMac(..) | | |
c34b1796 | 127 | ast::ItemDefaultImpl(..) | |
1a4d82fc JJ |
128 | ast::ItemForeignMod(..) | |
129 | ast::ItemStatic(..) | | |
130 | ast::ItemConst(..) => { | |
131 | // These sorts of items have no lifetime parameters at all. | |
132 | visit::walk_item(this, item); | |
133 | } | |
134 | ast::ItemTy(_, ref generics) | | |
135 | ast::ItemEnum(_, ref generics) | | |
136 | ast::ItemStruct(_, ref generics) | | |
137 | ast::ItemTrait(_, ref generics, _, _) | | |
138 | ast::ItemImpl(_, _, ref generics, _, _, _) => { | |
139 | // These kinds of items have only early bound lifetime parameters. | |
140 | let lifetimes = &generics.lifetimes; | |
141 | let early_scope = EarlyScope(subst::TypeSpace, lifetimes, &ROOT_SCOPE); | |
142 | this.with(early_scope, |old_scope, this| { | |
143 | this.check_lifetime_defs(old_scope, lifetimes); | |
144 | visit::walk_item(this, item); | |
145 | }); | |
146 | } | |
147 | } | |
148 | }); | |
9346a6ac AL |
149 | |
150 | // Done traversing the item; restore saved set of labels. | |
151 | replace(&mut self.labels_in_fn, saved); | |
1a4d82fc JJ |
152 | } |
153 | ||
154 | fn visit_fn(&mut self, fk: visit::FnKind<'v>, fd: &'v ast::FnDecl, | |
155 | b: &'v ast::Block, s: Span, _: ast::NodeId) { | |
156 | match fk { | |
9346a6ac | 157 | visit::FkItemFn(_, generics, _, _, _) => { |
1a4d82fc | 158 | self.visit_early_late(subst::FnSpace, generics, |this| { |
9346a6ac | 159 | this.walk_fn(fk, fd, b, s) |
1a4d82fc JJ |
160 | }) |
161 | } | |
9346a6ac | 162 | visit::FkMethod(_, sig, _) => { |
c34b1796 | 163 | self.visit_early_late(subst::FnSpace, &sig.generics, |this| { |
9346a6ac | 164 | this.walk_fn(fk, fd, b, s) |
c34b1796 AL |
165 | }) |
166 | } | |
1a4d82fc | 167 | visit::FkFnBlock(..) => { |
9346a6ac | 168 | self.walk_fn(fk, fd, b, s) |
1a4d82fc JJ |
169 | } |
170 | } | |
171 | } | |
172 | ||
173 | fn visit_ty(&mut self, ty: &ast::Ty) { | |
174 | match ty.node { | |
175 | ast::TyBareFn(ref c) => { | |
176 | visit::walk_lifetime_decls_helper(self, &c.lifetimes); | |
177 | self.with(LateScope(&c.lifetimes, self.scope), |old_scope, this| { | |
178 | // a bare fn has no bounds, so everything | |
179 | // contained within is scoped within its binder. | |
180 | this.check_lifetime_defs(old_scope, &c.lifetimes); | |
181 | visit::walk_ty(this, ty); | |
182 | }); | |
183 | } | |
c34b1796 | 184 | ast::TyPath(None, ref path) => { |
1a4d82fc JJ |
185 | // if this path references a trait, then this will resolve to |
186 | // a trait ref, which introduces a binding scope. | |
c34b1796 AL |
187 | match self.def_map.borrow().get(&ty.id).map(|d| (d.base_def, d.depth)) { |
188 | Some((def::DefTrait(..), 0)) => { | |
1a4d82fc | 189 | self.with(LateScope(&Vec::new(), self.scope), |_, this| { |
c34b1796 | 190 | this.visit_path(path, ty.id); |
1a4d82fc JJ |
191 | }); |
192 | } | |
193 | _ => { | |
194 | visit::walk_ty(self, ty); | |
195 | } | |
196 | } | |
197 | } | |
198 | _ => { | |
199 | visit::walk_ty(self, ty) | |
200 | } | |
201 | } | |
202 | } | |
203 | ||
c34b1796 | 204 | fn visit_trait_item(&mut self, trait_item: &ast::TraitItem) { |
9346a6ac AL |
205 | // We reset the labels on every trait item, so that different |
206 | // methods in an impl can reuse label names. | |
207 | let saved = replace(&mut self.labels_in_fn, vec![]); | |
208 | ||
c34b1796 AL |
209 | if let ast::MethodTraitItem(ref sig, None) = trait_item.node { |
210 | self.visit_early_late( | |
211 | subst::FnSpace, &sig.generics, | |
212 | |this| visit::walk_trait_item(this, trait_item)) | |
213 | } else { | |
214 | visit::walk_trait_item(self, trait_item); | |
215 | } | |
9346a6ac AL |
216 | |
217 | replace(&mut self.labels_in_fn, saved); | |
1a4d82fc JJ |
218 | } |
219 | ||
220 | fn visit_block(&mut self, b: &ast::Block) { | |
85aaf69f SL |
221 | self.with(BlockScope(region::DestructionScopeData::new(b.id), |
222 | self.scope), | |
1a4d82fc JJ |
223 | |_, this| visit::walk_block(this, b)); |
224 | } | |
225 | ||
226 | fn visit_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) { | |
227 | if lifetime_ref.name == special_idents::static_lifetime.name { | |
228 | self.insert_lifetime(lifetime_ref, DefStaticRegion); | |
229 | return; | |
230 | } | |
231 | self.resolve_lifetime_ref(lifetime_ref); | |
232 | } | |
233 | ||
234 | fn visit_generics(&mut self, generics: &ast::Generics) { | |
85aaf69f | 235 | for ty_param in &*generics.ty_params { |
1a4d82fc JJ |
236 | visit::walk_ty_param_bounds_helper(self, &ty_param.bounds); |
237 | match ty_param.default { | |
238 | Some(ref ty) => self.visit_ty(&**ty), | |
239 | None => {} | |
240 | } | |
241 | } | |
85aaf69f | 242 | for predicate in &generics.where_clause.predicates { |
1a4d82fc JJ |
243 | match predicate { |
244 | &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ ref bounded_ty, | |
245 | ref bounds, | |
85aaf69f | 246 | ref bound_lifetimes, |
1a4d82fc | 247 | .. }) => { |
9346a6ac | 248 | if !bound_lifetimes.is_empty() { |
85aaf69f SL |
249 | self.trait_ref_hack = true; |
250 | let result = self.with(LateScope(bound_lifetimes, self.scope), | |
251 | |old_scope, this| { | |
252 | this.check_lifetime_defs(old_scope, bound_lifetimes); | |
253 | this.visit_ty(&**bounded_ty); | |
254 | visit::walk_ty_param_bounds_helper(this, bounds); | |
255 | }); | |
256 | self.trait_ref_hack = false; | |
257 | result | |
258 | } else { | |
259 | self.visit_ty(&**bounded_ty); | |
260 | visit::walk_ty_param_bounds_helper(self, bounds); | |
261 | } | |
1a4d82fc JJ |
262 | } |
263 | &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime, | |
264 | ref bounds, | |
265 | .. }) => { | |
266 | ||
267 | self.visit_lifetime_ref(lifetime); | |
85aaf69f | 268 | for bound in bounds { |
1a4d82fc JJ |
269 | self.visit_lifetime_ref(bound); |
270 | } | |
271 | } | |
272 | &ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{ id, | |
273 | ref path, | |
274 | ref ty, | |
275 | .. }) => { | |
276 | self.visit_path(path, id); | |
277 | self.visit_ty(&**ty); | |
278 | } | |
279 | } | |
280 | } | |
281 | } | |
282 | ||
85aaf69f SL |
283 | fn visit_poly_trait_ref(&mut self, |
284 | trait_ref: &ast::PolyTraitRef, | |
1a4d82fc JJ |
285 | _modifier: &ast::TraitBoundModifier) { |
286 | debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref); | |
287 | ||
9346a6ac | 288 | if !self.trait_ref_hack || !trait_ref.bound_lifetimes.is_empty() { |
85aaf69f SL |
289 | if self.trait_ref_hack { |
290 | println!("{:?}", trait_ref.span); | |
291 | span_err!(self.sess, trait_ref.span, E0316, | |
292 | "nested quantification of lifetimes"); | |
1a4d82fc | 293 | } |
85aaf69f SL |
294 | self.with(LateScope(&trait_ref.bound_lifetimes, self.scope), |old_scope, this| { |
295 | this.check_lifetime_defs(old_scope, &trait_ref.bound_lifetimes); | |
296 | for lifetime in &trait_ref.bound_lifetimes { | |
297 | this.visit_lifetime_def(lifetime); | |
298 | } | |
c34b1796 | 299 | visit::walk_path(this, &trait_ref.trait_ref.path) |
85aaf69f SL |
300 | }) |
301 | } else { | |
302 | self.visit_trait_ref(&trait_ref.trait_ref) | |
303 | } | |
1a4d82fc | 304 | } |
1a4d82fc JJ |
305 | } |
306 | ||
9346a6ac AL |
307 | #[derive(Copy, Clone, PartialEq)] |
308 | enum ShadowKind { Label, Lifetime } | |
309 | struct Original { kind: ShadowKind, span: Span } | |
310 | struct Shadower { kind: ShadowKind, span: Span } | |
311 | ||
312 | fn original_label(span: Span) -> Original { | |
313 | Original { kind: ShadowKind::Label, span: span } | |
314 | } | |
315 | fn shadower_label(span: Span) -> Shadower { | |
316 | Shadower { kind: ShadowKind::Label, span: span } | |
317 | } | |
318 | fn original_lifetime(l: &ast::Lifetime) -> Original { | |
319 | Original { kind: ShadowKind::Lifetime, span: l.span } | |
320 | } | |
321 | fn shadower_lifetime(l: &ast::Lifetime) -> Shadower { | |
322 | Shadower { kind: ShadowKind::Lifetime, span: l.span } | |
323 | } | |
324 | ||
325 | impl ShadowKind { | |
326 | fn desc(&self) -> &'static str { | |
327 | match *self { | |
328 | ShadowKind::Label => "label", | |
329 | ShadowKind::Lifetime => "lifetime", | |
330 | } | |
331 | } | |
332 | } | |
333 | ||
334 | fn signal_shadowing_problem( | |
335 | sess: &Session, name: ast::Name, orig: Original, shadower: Shadower) { | |
336 | if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) { | |
337 | // lifetime/lifetime shadowing is an error | |
338 | sess.span_err(shadower.span, | |
339 | &format!("{} name `{}` shadows a \ | |
340 | {} name that is already in scope", | |
341 | shadower.kind.desc(), name, orig.kind.desc())); | |
342 | } else { | |
343 | // shadowing involving a label is only a warning, due to issues with | |
344 | // labels and lifetimes not being macro-hygienic. | |
345 | sess.span_warn(shadower.span, | |
346 | &format!("{} name `{}` shadows a \ | |
347 | {} name that is already in scope", | |
348 | shadower.kind.desc(), name, orig.kind.desc())); | |
349 | } | |
350 | sess.span_note(orig.span, | |
351 | &format!("shadowed {} `{}` declared here", | |
352 | orig.kind.desc(), name)); | |
353 | } | |
354 | ||
355 | // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning | |
356 | // if one of the label shadows a lifetime or another label. | |
357 | fn extract_labels<'v, 'a>(ctxt: &mut LifetimeContext<'a>, b: &'v ast::Block) { | |
358 | ||
359 | struct GatherLabels<'a> { | |
360 | sess: &'a Session, | |
361 | scope: Scope<'a>, | |
362 | labels_in_fn: &'a mut Vec<(ast::Ident, Span)>, | |
363 | } | |
364 | ||
365 | let mut gather = GatherLabels { | |
366 | sess: ctxt.sess, | |
367 | scope: ctxt.scope, | |
368 | labels_in_fn: &mut ctxt.labels_in_fn, | |
369 | }; | |
370 | gather.visit_block(b); | |
371 | return; | |
372 | ||
373 | impl<'v, 'a> Visitor<'v> for GatherLabels<'a> { | |
374 | fn visit_expr(&mut self, ex: &'v ast::Expr) { | |
375 | if let Some(label) = expression_label(ex) { | |
376 | for &(prior, prior_span) in &self.labels_in_fn[..] { | |
d9579d0f | 377 | // FIXME (#24278): non-hygienic comparison |
9346a6ac AL |
378 | if label.name == prior.name { |
379 | signal_shadowing_problem(self.sess, | |
380 | label.name, | |
381 | original_label(prior_span), | |
382 | shadower_label(ex.span)); | |
383 | } | |
384 | } | |
385 | ||
386 | check_if_label_shadows_lifetime(self.sess, | |
387 | self.scope, | |
388 | label, | |
389 | ex.span); | |
390 | ||
391 | self.labels_in_fn.push((label, ex.span)); | |
392 | } | |
393 | visit::walk_expr(self, ex) | |
394 | } | |
395 | ||
396 | fn visit_item(&mut self, _: &ast::Item) { | |
397 | // do not recurse into items defined in the block | |
398 | } | |
399 | } | |
400 | ||
401 | fn expression_label(ex: &ast::Expr) -> Option<ast::Ident> { | |
402 | match ex.node { | |
403 | ast::ExprWhile(_, _, Some(label)) | | |
404 | ast::ExprWhileLet(_, _, _, Some(label)) | | |
405 | ast::ExprForLoop(_, _, _, Some(label)) | | |
406 | ast::ExprLoop(_, Some(label)) => Some(label), | |
407 | _ => None, | |
408 | } | |
409 | } | |
410 | ||
411 | fn check_if_label_shadows_lifetime<'a>(sess: &'a Session, | |
412 | mut scope: Scope<'a>, | |
413 | label: ast::Ident, | |
414 | label_span: Span) { | |
415 | loop { | |
416 | match *scope { | |
417 | BlockScope(_, s) => { scope = s; } | |
418 | RootScope => { return; } | |
419 | ||
420 | EarlyScope(_, lifetimes, s) | | |
421 | LateScope(lifetimes, s) => { | |
422 | for lifetime_def in lifetimes { | |
d9579d0f | 423 | // FIXME (#24278): non-hygienic comparison |
9346a6ac AL |
424 | if label.name == lifetime_def.lifetime.name { |
425 | signal_shadowing_problem( | |
426 | sess, | |
427 | label.name, | |
428 | original_lifetime(&lifetime_def.lifetime), | |
429 | shadower_label(label_span)); | |
430 | return; | |
431 | } | |
432 | } | |
433 | scope = s; | |
434 | } | |
435 | } | |
436 | } | |
437 | } | |
438 | } | |
439 | ||
1a4d82fc | 440 | impl<'a> LifetimeContext<'a> { |
9346a6ac AL |
441 | // This is just like visit::walk_fn, except that it extracts the |
442 | // labels of the function body and swaps them in before visiting | |
443 | // the function body itself. | |
444 | fn walk_fn<'b>(&mut self, | |
445 | fk: visit::FnKind, | |
446 | fd: &ast::FnDecl, | |
447 | fb: &'b ast::Block, | |
448 | _span: Span) { | |
449 | match fk { | |
450 | visit::FkItemFn(_, generics, _, _, _) => { | |
451 | visit::walk_fn_decl(self, fd); | |
452 | self.visit_generics(generics); | |
453 | } | |
454 | visit::FkMethod(_, sig, _) => { | |
455 | visit::walk_fn_decl(self, fd); | |
456 | self.visit_generics(&sig.generics); | |
457 | self.visit_explicit_self(&sig.explicit_self); | |
458 | } | |
459 | visit::FkFnBlock(..) => { | |
460 | visit::walk_fn_decl(self, fd); | |
461 | } | |
462 | } | |
463 | ||
464 | // After inpsecting the decl, add all labels from the body to | |
465 | // `self.labels_in_fn`. | |
466 | extract_labels(self, fb); | |
467 | ||
468 | self.visit_block(fb); | |
469 | } | |
470 | ||
1a4d82fc JJ |
471 | fn with<F>(&mut self, wrap_scope: ScopeChain, f: F) where |
472 | F: FnOnce(Scope, &mut LifetimeContext), | |
473 | { | |
474 | let LifetimeContext {sess, ref mut named_region_map, ..} = *self; | |
475 | let mut this = LifetimeContext { | |
476 | sess: sess, | |
477 | named_region_map: *named_region_map, | |
478 | scope: &wrap_scope, | |
479 | def_map: self.def_map, | |
85aaf69f | 480 | trait_ref_hack: self.trait_ref_hack, |
9346a6ac | 481 | labels_in_fn: self.labels_in_fn.clone(), |
1a4d82fc JJ |
482 | }; |
483 | debug!("entering scope {:?}", this.scope); | |
484 | f(self.scope, &mut this); | |
485 | debug!("exiting scope {:?}", this.scope); | |
486 | } | |
487 | ||
488 | /// Visits self by adding a scope and handling recursive walk over the contents with `walk`. | |
489 | /// | |
490 | /// Handles visiting fns and methods. These are a bit complicated because we must distinguish | |
491 | /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear | |
492 | /// within type bounds; those are early bound lifetimes, and the rest are late bound. | |
493 | /// | |
494 | /// For example: | |
495 | /// | |
496 | /// fn foo<'a,'b,'c,T:Trait<'b>>(...) | |
497 | /// | |
498 | /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound | |
499 | /// lifetimes may be interspersed together. | |
500 | /// | |
501 | /// If early bound lifetimes are present, we separate them into their own list (and likewise | |
502 | /// for late bound). They will be numbered sequentially, starting from the lowest index that is | |
503 | /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late | |
504 | /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the | |
505 | /// ordering is not important there. | |
506 | fn visit_early_late<F>(&mut self, | |
507 | early_space: subst::ParamSpace, | |
508 | generics: &ast::Generics, | |
509 | walk: F) where | |
510 | F: FnOnce(&mut LifetimeContext), | |
511 | { | |
512 | let referenced_idents = early_bound_lifetime_names(generics); | |
513 | ||
514 | debug!("visit_early_late: referenced_idents={:?}", | |
515 | referenced_idents); | |
516 | ||
517 | let (early, late): (Vec<_>, _) = generics.lifetimes.iter().cloned().partition( | |
518 | |l| referenced_idents.iter().any(|&i| i == l.lifetime.name)); | |
519 | ||
520 | self.with(EarlyScope(early_space, &early, self.scope), move |old_scope, this| { | |
521 | this.with(LateScope(&late, this.scope), move |_, this| { | |
522 | this.check_lifetime_defs(old_scope, &generics.lifetimes); | |
523 | walk(this); | |
524 | }); | |
525 | }); | |
526 | } | |
527 | ||
528 | fn resolve_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) { | |
529 | // Walk up the scope chain, tracking the number of fn scopes | |
530 | // that we pass through, until we find a lifetime with the | |
531 | // given name or we run out of scopes. If we encounter a code | |
532 | // block, then the lifetime is not bound but free, so switch | |
533 | // over to `resolve_free_lifetime_ref()` to complete the | |
534 | // search. | |
535 | let mut late_depth = 0; | |
536 | let mut scope = self.scope; | |
537 | loop { | |
538 | match *scope { | |
539 | BlockScope(blk_scope, s) => { | |
540 | return self.resolve_free_lifetime_ref(blk_scope, lifetime_ref, s); | |
541 | } | |
542 | ||
543 | RootScope => { | |
544 | break; | |
545 | } | |
546 | ||
547 | EarlyScope(space, lifetimes, s) => { | |
548 | match search_lifetimes(lifetimes, lifetime_ref) { | |
549 | Some((index, lifetime_def)) => { | |
550 | let decl_id = lifetime_def.id; | |
551 | let def = DefEarlyBoundRegion(space, index, decl_id); | |
552 | self.insert_lifetime(lifetime_ref, def); | |
553 | return; | |
554 | } | |
555 | None => { | |
556 | scope = s; | |
557 | } | |
558 | } | |
559 | } | |
560 | ||
561 | LateScope(lifetimes, s) => { | |
562 | match search_lifetimes(lifetimes, lifetime_ref) { | |
563 | Some((_index, lifetime_def)) => { | |
564 | let decl_id = lifetime_def.id; | |
565 | let debruijn = ty::DebruijnIndex::new(late_depth + 1); | |
566 | let def = DefLateBoundRegion(debruijn, decl_id); | |
567 | self.insert_lifetime(lifetime_ref, def); | |
568 | return; | |
569 | } | |
570 | ||
571 | None => { | |
572 | late_depth += 1; | |
573 | scope = s; | |
574 | } | |
575 | } | |
576 | } | |
577 | } | |
578 | } | |
579 | ||
580 | self.unresolved_lifetime_ref(lifetime_ref); | |
581 | } | |
582 | ||
583 | fn resolve_free_lifetime_ref(&mut self, | |
85aaf69f | 584 | scope_data: region::DestructionScopeData, |
1a4d82fc JJ |
585 | lifetime_ref: &ast::Lifetime, |
586 | scope: Scope) { | |
85aaf69f SL |
587 | debug!("resolve_free_lifetime_ref \ |
588 | scope_data: {:?} lifetime_ref: {:?} scope: {:?}", | |
589 | scope_data, lifetime_ref, scope); | |
590 | ||
1a4d82fc JJ |
591 | // Walk up the scope chain, tracking the outermost free scope, |
592 | // until we encounter a scope that contains the named lifetime | |
593 | // or we run out of scopes. | |
594 | let mut scope_data = scope_data; | |
595 | let mut scope = scope; | |
596 | let mut search_result = None; | |
597 | loop { | |
85aaf69f SL |
598 | debug!("resolve_free_lifetime_ref \ |
599 | scope_data: {:?} scope: {:?} search_result: {:?}", | |
600 | scope_data, scope, search_result); | |
1a4d82fc JJ |
601 | match *scope { |
602 | BlockScope(blk_scope_data, s) => { | |
603 | scope_data = blk_scope_data; | |
604 | scope = s; | |
605 | } | |
606 | ||
607 | RootScope => { | |
608 | break; | |
609 | } | |
610 | ||
611 | EarlyScope(_, lifetimes, s) | | |
612 | LateScope(lifetimes, s) => { | |
613 | search_result = search_lifetimes(lifetimes, lifetime_ref); | |
614 | if search_result.is_some() { | |
615 | break; | |
616 | } | |
617 | scope = s; | |
618 | } | |
619 | } | |
620 | } | |
621 | ||
622 | match search_result { | |
623 | Some((_depth, lifetime)) => { | |
624 | let def = DefFreeRegion(scope_data, lifetime.id); | |
625 | self.insert_lifetime(lifetime_ref, def); | |
626 | } | |
627 | ||
628 | None => { | |
629 | self.unresolved_lifetime_ref(lifetime_ref); | |
630 | } | |
631 | } | |
632 | ||
633 | } | |
634 | ||
635 | fn unresolved_lifetime_ref(&self, lifetime_ref: &ast::Lifetime) { | |
85aaf69f SL |
636 | span_err!(self.sess, lifetime_ref.span, E0261, |
637 | "use of undeclared lifetime name `{}`", | |
638 | token::get_name(lifetime_ref.name)); | |
1a4d82fc JJ |
639 | } |
640 | ||
641 | fn check_lifetime_defs(&mut self, old_scope: Scope, lifetimes: &Vec<ast::LifetimeDef>) { | |
85aaf69f | 642 | for i in 0..lifetimes.len() { |
1a4d82fc JJ |
643 | let lifetime_i = &lifetimes[i]; |
644 | ||
645 | let special_idents = [special_idents::static_lifetime]; | |
85aaf69f | 646 | for lifetime in lifetimes { |
1a4d82fc | 647 | if special_idents.iter().any(|&i| i.name == lifetime.lifetime.name) { |
85aaf69f SL |
648 | span_err!(self.sess, lifetime.lifetime.span, E0262, |
649 | "illegal lifetime parameter name: `{}`", | |
650 | token::get_name(lifetime.lifetime.name)); | |
1a4d82fc JJ |
651 | } |
652 | } | |
653 | ||
654 | // It is a hard error to shadow a lifetime within the same scope. | |
85aaf69f | 655 | for j in i + 1..lifetimes.len() { |
1a4d82fc JJ |
656 | let lifetime_j = &lifetimes[j]; |
657 | ||
658 | if lifetime_i.lifetime.name == lifetime_j.lifetime.name { | |
85aaf69f SL |
659 | span_err!(self.sess, lifetime_j.lifetime.span, E0263, |
660 | "lifetime name `{}` declared twice in \ | |
1a4d82fc | 661 | the same scope", |
85aaf69f | 662 | token::get_name(lifetime_j.lifetime.name)); |
1a4d82fc JJ |
663 | } |
664 | } | |
665 | ||
666 | // It is a soft error to shadow a lifetime within a parent scope. | |
667 | self.check_lifetime_def_for_shadowing(old_scope, &lifetime_i.lifetime); | |
668 | ||
85aaf69f | 669 | for bound in &lifetime_i.bounds { |
1a4d82fc JJ |
670 | self.resolve_lifetime_ref(bound); |
671 | } | |
672 | } | |
673 | } | |
674 | ||
675 | fn check_lifetime_def_for_shadowing(&self, | |
676 | mut old_scope: Scope, | |
677 | lifetime: &ast::Lifetime) | |
678 | { | |
9346a6ac | 679 | for &(label, label_span) in &self.labels_in_fn { |
d9579d0f | 680 | // FIXME (#24278): non-hygienic comparison |
9346a6ac AL |
681 | if lifetime.name == label.name { |
682 | signal_shadowing_problem(self.sess, | |
683 | lifetime.name, | |
684 | original_label(label_span), | |
685 | shadower_lifetime(&lifetime)); | |
686 | return; | |
687 | } | |
688 | } | |
689 | ||
1a4d82fc JJ |
690 | loop { |
691 | match *old_scope { | |
692 | BlockScope(_, s) => { | |
693 | old_scope = s; | |
694 | } | |
695 | ||
696 | RootScope => { | |
697 | return; | |
698 | } | |
699 | ||
700 | EarlyScope(_, lifetimes, s) | | |
701 | LateScope(lifetimes, s) => { | |
702 | if let Some((_, lifetime_def)) = search_lifetimes(lifetimes, lifetime) { | |
9346a6ac AL |
703 | signal_shadowing_problem( |
704 | self.sess, | |
705 | lifetime.name, | |
706 | original_lifetime(&lifetime_def), | |
707 | shadower_lifetime(&lifetime)); | |
1a4d82fc JJ |
708 | return; |
709 | } | |
710 | ||
711 | old_scope = s; | |
712 | } | |
713 | } | |
714 | } | |
715 | } | |
716 | ||
717 | fn insert_lifetime(&mut self, | |
718 | lifetime_ref: &ast::Lifetime, | |
719 | def: DefRegion) { | |
720 | if lifetime_ref.id == ast::DUMMY_NODE_ID { | |
721 | self.sess.span_bug(lifetime_ref.span, | |
722 | "lifetime reference not renumbered, \ | |
723 | probably a bug in syntax::fold"); | |
724 | } | |
725 | ||
726 | debug!("lifetime_ref={:?} id={:?} resolved to {:?}", | |
727 | lifetime_to_string(lifetime_ref), | |
728 | lifetime_ref.id, | |
729 | def); | |
730 | self.named_region_map.insert(lifetime_ref.id, def); | |
731 | } | |
732 | } | |
733 | ||
734 | fn search_lifetimes<'a>(lifetimes: &'a Vec<ast::LifetimeDef>, | |
735 | lifetime_ref: &ast::Lifetime) | |
736 | -> Option<(u32, &'a ast::Lifetime)> { | |
737 | for (i, lifetime_decl) in lifetimes.iter().enumerate() { | |
738 | if lifetime_decl.lifetime.name == lifetime_ref.name { | |
739 | return Some((i as u32, &lifetime_decl.lifetime)); | |
740 | } | |
741 | } | |
742 | return None; | |
743 | } | |
744 | ||
745 | /////////////////////////////////////////////////////////////////////////// | |
746 | ||
747 | pub fn early_bound_lifetimes<'a>(generics: &'a ast::Generics) -> Vec<ast::LifetimeDef> { | |
748 | let referenced_idents = early_bound_lifetime_names(generics); | |
749 | if referenced_idents.is_empty() { | |
750 | return Vec::new(); | |
751 | } | |
752 | ||
753 | generics.lifetimes.iter() | |
754 | .filter(|l| referenced_idents.iter().any(|&i| i == l.lifetime.name)) | |
85aaf69f | 755 | .cloned() |
1a4d82fc JJ |
756 | .collect() |
757 | } | |
758 | ||
759 | /// Given a set of generic declarations, returns a list of names containing all early bound | |
760 | /// lifetime names for those generics. (In fact, this list may also contain other names.) | |
761 | fn early_bound_lifetime_names(generics: &ast::Generics) -> Vec<ast::Name> { | |
762 | // Create two lists, dividing the lifetimes into early/late bound. | |
763 | // Initially, all of them are considered late, but we will move | |
764 | // things from late into early as we go if we find references to | |
765 | // them. | |
766 | let mut early_bound = Vec::new(); | |
767 | let mut late_bound = generics.lifetimes.iter() | |
768 | .map(|l| l.lifetime.name) | |
769 | .collect(); | |
770 | ||
771 | // Any lifetime that appears in a type bound is early. | |
772 | { | |
773 | let mut collector = | |
774 | FreeLifetimeCollector { early_bound: &mut early_bound, | |
775 | late_bound: &mut late_bound }; | |
85aaf69f | 776 | for ty_param in &*generics.ty_params { |
1a4d82fc JJ |
777 | visit::walk_ty_param_bounds_helper(&mut collector, &ty_param.bounds); |
778 | } | |
85aaf69f | 779 | for predicate in &generics.where_clause.predicates { |
1a4d82fc JJ |
780 | match predicate { |
781 | &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ref bounds, | |
782 | ref bounded_ty, | |
783 | ..}) => { | |
784 | collector.visit_ty(&**bounded_ty); | |
785 | visit::walk_ty_param_bounds_helper(&mut collector, bounds); | |
786 | } | |
787 | &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime, | |
788 | ref bounds, | |
789 | ..}) => { | |
790 | collector.visit_lifetime_ref(lifetime); | |
791 | ||
85aaf69f | 792 | for bound in bounds { |
1a4d82fc JJ |
793 | collector.visit_lifetime_ref(bound); |
794 | } | |
795 | } | |
796 | &ast::WherePredicate::EqPredicate(_) => unimplemented!() | |
797 | } | |
798 | } | |
799 | } | |
800 | ||
801 | // Any lifetime that either has a bound or is referenced by a | |
802 | // bound is early. | |
85aaf69f | 803 | for lifetime_def in &generics.lifetimes { |
1a4d82fc JJ |
804 | if !lifetime_def.bounds.is_empty() { |
805 | shuffle(&mut early_bound, &mut late_bound, | |
806 | lifetime_def.lifetime.name); | |
85aaf69f | 807 | for bound in &lifetime_def.bounds { |
1a4d82fc JJ |
808 | shuffle(&mut early_bound, &mut late_bound, |
809 | bound.name); | |
810 | } | |
811 | } | |
812 | } | |
813 | return early_bound; | |
814 | ||
815 | struct FreeLifetimeCollector<'a> { | |
816 | early_bound: &'a mut Vec<ast::Name>, | |
817 | late_bound: &'a mut Vec<ast::Name>, | |
818 | } | |
819 | ||
820 | impl<'a, 'v> Visitor<'v> for FreeLifetimeCollector<'a> { | |
821 | fn visit_lifetime_ref(&mut self, lifetime_ref: &ast::Lifetime) { | |
822 | shuffle(self.early_bound, self.late_bound, | |
823 | lifetime_ref.name); | |
824 | } | |
825 | } | |
826 | ||
827 | fn shuffle(early_bound: &mut Vec<ast::Name>, | |
828 | late_bound: &mut Vec<ast::Name>, | |
829 | name: ast::Name) { | |
830 | match late_bound.iter().position(|n| *n == name) { | |
831 | Some(index) => { | |
832 | late_bound.swap_remove(index); | |
833 | early_bound.push(name); | |
834 | } | |
835 | None => { } | |
836 | } | |
837 | } | |
838 | } | |
839 | ||
85aaf69f | 840 | impl<'a> fmt::Debug for ScopeChain<'a> { |
1a4d82fc JJ |
841 | fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { |
842 | match *self { | |
843 | EarlyScope(space, defs, _) => write!(fmt, "EarlyScope({:?}, {:?})", space, defs), | |
844 | LateScope(defs, _) => write!(fmt, "LateScope({:?})", defs), | |
845 | BlockScope(id, _) => write!(fmt, "BlockScope({:?})", id), | |
846 | RootScope => write!(fmt, "RootScope"), | |
847 | } | |
848 | } | |
849 | } |