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