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::*;
21 use dep_graph::DepNode;
24 use hir::def::{Def, DefMap};
25 use hir::def_id::DefId;
30 use std::mem::replace;
32 use syntax::parse::token::keywords;
34 use util::nodemap::NodeMap;
36 use rustc_data_structures::fnv::FnvHashSet;
38 use hir::print::lifetime_to_string;
39 use hir::intravisit::{self, Visitor, FnKind};
41 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
44 DefEarlyBoundRegion(/* space */ subst::ParamSpace,
46 /* lifetime decl */ ast::NodeId),
47 DefLateBoundRegion(ty::DebruijnIndex,
48 /* lifetime decl */ ast::NodeId),
49 DefFreeRegion(region::CallSiteScopeData,
50 /* lifetime decl */ ast::NodeId),
53 // Maps the id of each lifetime reference to the lifetime decl
54 // that it corresponds to.
55 pub struct NamedRegionMap {
56 // maps from every use of a named (not anonymous) lifetime to a
57 // `DefRegion` describing how that region is bound
58 pub defs: NodeMap<DefRegion>,
60 // the set of lifetime def ids that are late-bound; late-bound ids
61 // are named regions appearing in fn arguments that do not appear
63 pub late_bound: NodeMap<ty::Issue32330>,
66 struct LifetimeContext<'a, 'tcx: 'a> {
68 hir_map: &'a Map<'tcx>,
69 map: &'a mut NamedRegionMap,
72 // Deep breath. Our representation for poly trait refs contains a single
73 // binder and thus we only allow a single level of quantification. However,
74 // the syntax of Rust permits quantification in two places, e.g., `T: for <'a> Foo<'a>`
75 // and `for <'a, 'b> &'b T: Foo<'a>`. In order to get the de Bruijn indices
76 // correct when representing these constraints, we should only introduce one
77 // scope. However, we want to support both locations for the quantifier and
78 // during lifetime resolution we want precise information (so we can't
79 // desugar in an earlier phase).
81 // SO, if we encounter a quantifier at the outer scope, we set
82 // trait_ref_hack to true (and introduce a scope), and then if we encounter
83 // a quantifier at the inner scope, we error. If trait_ref_hack is false,
84 // then we introduce the scope at the inner quantifier.
89 // List of labels in the function/method currently under analysis.
90 labels_in_fn: Vec<(ast::Name, Span)>,
94 /// EarlyScope(i, ['a, 'b, ...], s) extends s with early-bound
95 /// lifetimes, assigning indexes 'a => i, 'b => i+1, ... etc.
96 EarlyScope(subst::ParamSpace, &'a [hir::LifetimeDef], Scope<'a>),
97 /// LateScope(['a, 'b, ...], s) extends s with late-bound
98 /// lifetimes introduced by the declaration binder_id.
99 LateScope(&'a [hir::LifetimeDef], Scope<'a>),
101 /// lifetimes introduced by a fn are scoped to the call-site for that fn.
102 FnScope { fn_id: ast::NodeId, body_id: ast::NodeId, s: Scope<'a> },
106 type Scope<'a> = &'a ScopeChain<'a>;
108 static ROOT_SCOPE: ScopeChain<'static> = RootScope;
110 pub fn krate(sess: &Session,
113 -> Result<NamedRegionMap, usize> {
114 let _task = hir_map.dep_graph.in_task(DepNode::ResolveLifetimes);
115 let krate = hir_map.krate();
116 let mut map = NamedRegionMap {
118 late_bound: NodeMap(),
120 sess.track_errors(|| {
121 krate.visit_all_items(&mut LifetimeContext {
127 trait_ref_hack: false,
128 labels_in_fn: vec![],
134 impl<'a, 'tcx, 'v> Visitor<'v> for LifetimeContext<'a, 'tcx> {
135 fn visit_item(&mut self, item: &hir::Item) {
136 assert!(self.labels_in_fn.is_empty());
138 // Items always introduce a new root scope
139 self.with(RootScope, |_, this| {
142 // Fn lifetimes get added in visit_fn below:
143 intravisit::walk_item(this, item);
145 hir::ItemExternCrate(_) |
148 hir::ItemDefaultImpl(..) |
149 hir::ItemForeignMod(..) |
150 hir::ItemStatic(..) |
151 hir::ItemConst(..) => {
152 // These sorts of items have no lifetime parameters at all.
153 intravisit::walk_item(this, item);
155 hir::ItemTy(_, ref generics) |
156 hir::ItemEnum(_, ref generics) |
157 hir::ItemStruct(_, ref generics) |
158 hir::ItemTrait(_, ref generics, _, _) |
159 hir::ItemImpl(_, _, ref generics, _, _, _) => {
160 // These kinds of items have only early bound lifetime parameters.
161 let lifetimes = &generics.lifetimes;
162 let early_scope = EarlyScope(subst::TypeSpace, lifetimes, &ROOT_SCOPE);
163 this.with(early_scope, |old_scope, this| {
164 this.check_lifetime_defs(old_scope, lifetimes);
165 intravisit::walk_item(this, item);
171 // Done traversing the item; remove any labels it created
172 self.labels_in_fn.truncate(0);
175 fn visit_foreign_item(&mut self, item: &hir::ForeignItem) {
176 // Items save/restore the set of labels. This way inner items
177 // can freely reuse names, be they loop labels or lifetimes.
178 let saved = replace(&mut self.labels_in_fn, vec![]);
180 // Items always introduce a new root scope
181 self.with(RootScope, |_, this| {
183 hir::ForeignItemFn(ref decl, ref generics) => {
184 this.visit_early_late(item.id,
189 intravisit::walk_foreign_item(this, item);
192 hir::ForeignItemStatic(..) => {
193 intravisit::walk_foreign_item(this, item);
198 // Done traversing the item; restore saved set of labels.
199 replace(&mut self.labels_in_fn, saved);
202 fn visit_fn(&mut self, fk: FnKind<'v>, decl: &'v hir::FnDecl,
203 b: &'v hir::Block, s: Span, fn_id: ast::NodeId) {
205 FnKind::ItemFn(_, generics, _, _, _, _, _) => {
206 self.visit_early_late(fn_id, subst::FnSpace, decl, generics, |this| {
207 this.add_scope_and_walk_fn(fk, decl, b, s, fn_id)
210 FnKind::Method(_, sig, _, _) => {
211 self.visit_early_late(
216 |this| this.add_scope_and_walk_fn(fk, decl, b, s, fn_id));
218 FnKind::Closure(_) => {
219 // Closures have their own set of labels, save labels just
220 // like for foreign items above.
221 let saved = replace(&mut self.labels_in_fn, vec![]);
222 let result = self.add_scope_and_walk_fn(fk, decl, b, s, fn_id);
223 replace(&mut self.labels_in_fn, saved);
229 fn visit_ty(&mut self, ty: &hir::Ty) {
231 hir::TyBareFn(ref c) => {
232 self.with(LateScope(&c.lifetimes, self.scope), |old_scope, this| {
233 // a bare fn has no bounds, so everything
234 // contained within is scoped within its binder.
235 this.check_lifetime_defs(old_scope, &c.lifetimes);
236 intravisit::walk_ty(this, ty);
239 hir::TyPath(None, ref path) => {
240 // if this path references a trait, then this will resolve to
241 // a trait ref, which introduces a binding scope.
242 match self.def_map.get(&ty.id).map(|d| (d.base_def, d.depth)) {
243 Some((Def::Trait(..), 0)) => {
244 self.with(LateScope(&[], self.scope), |_, this| {
245 this.visit_path(path, ty.id);
249 intravisit::walk_ty(self, ty);
254 intravisit::walk_ty(self, ty)
259 fn visit_trait_item(&mut self, trait_item: &hir::TraitItem) {
260 // We reset the labels on every trait item, so that different
261 // methods in an impl can reuse label names.
262 let saved = replace(&mut self.labels_in_fn, vec![]);
264 if let hir::MethodTraitItem(ref sig, None) = trait_item.node {
265 self.visit_early_late(
266 trait_item.id, subst::FnSpace,
267 &sig.decl, &sig.generics,
268 |this| intravisit::walk_trait_item(this, trait_item))
270 intravisit::walk_trait_item(self, trait_item);
273 replace(&mut self.labels_in_fn, saved);
276 fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
277 if lifetime_ref.name == keywords::StaticLifetime.name() {
278 self.insert_lifetime(lifetime_ref, DefStaticRegion);
281 self.resolve_lifetime_ref(lifetime_ref);
284 fn visit_generics(&mut self, generics: &hir::Generics) {
285 for ty_param in generics.ty_params.iter() {
286 walk_list!(self, visit_ty_param_bound, &ty_param.bounds);
287 if let Some(ref ty) = ty_param.default {
291 for predicate in &generics.where_clause.predicates {
293 &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate{ ref bounded_ty,
297 if !bound_lifetimes.is_empty() {
298 self.trait_ref_hack = true;
299 let result = self.with(LateScope(bound_lifetimes, self.scope),
301 this.check_lifetime_defs(old_scope, bound_lifetimes);
302 this.visit_ty(&bounded_ty);
303 walk_list!(this, visit_ty_param_bound, bounds);
305 self.trait_ref_hack = false;
308 self.visit_ty(&bounded_ty);
309 walk_list!(self, visit_ty_param_bound, bounds);
312 &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate{ref lifetime,
316 self.visit_lifetime(lifetime);
317 for bound in bounds {
318 self.visit_lifetime(bound);
321 &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate{ id,
325 self.visit_path(path, id);
332 fn visit_poly_trait_ref(&mut self,
333 trait_ref: &hir::PolyTraitRef,
334 _modifier: &hir::TraitBoundModifier) {
335 debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
337 if !self.trait_ref_hack || !trait_ref.bound_lifetimes.is_empty() {
338 if self.trait_ref_hack {
339 println!("{:?}", trait_ref.span);
340 span_err!(self.sess, trait_ref.span, E0316,
341 "nested quantification of lifetimes");
343 self.with(LateScope(&trait_ref.bound_lifetimes, self.scope), |old_scope, this| {
344 this.check_lifetime_defs(old_scope, &trait_ref.bound_lifetimes);
345 for lifetime in &trait_ref.bound_lifetimes {
346 this.visit_lifetime_def(lifetime);
348 intravisit::walk_path(this, &trait_ref.trait_ref.path)
351 self.visit_trait_ref(&trait_ref.trait_ref)
356 #[derive(Copy, Clone, PartialEq)]
357 enum ShadowKind { Label, Lifetime }
358 struct Original { kind: ShadowKind, span: Span }
359 struct Shadower { kind: ShadowKind, span: Span }
361 fn original_label(span: Span) -> Original {
362 Original { kind: ShadowKind::Label, span: span }
364 fn shadower_label(span: Span) -> Shadower {
365 Shadower { kind: ShadowKind::Label, span: span }
367 fn original_lifetime(l: &hir::Lifetime) -> Original {
368 Original { kind: ShadowKind::Lifetime, span: l.span }
370 fn shadower_lifetime(l: &hir::Lifetime) -> Shadower {
371 Shadower { kind: ShadowKind::Lifetime, span: l.span }
375 fn desc(&self) -> &'static str {
377 ShadowKind::Label => "label",
378 ShadowKind::Lifetime => "lifetime",
383 fn signal_shadowing_problem(sess: &Session, name: ast::Name, orig: Original, shadower: Shadower) {
384 let mut err = if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
385 // lifetime/lifetime shadowing is an error
386 struct_span_err!(sess, shadower.span, E0496,
387 "{} name `{}` shadows a \
388 {} name that is already in scope",
389 shadower.kind.desc(), name, orig.kind.desc())
391 // shadowing involving a label is only a warning, due to issues with
392 // labels and lifetimes not being macro-hygienic.
393 sess.struct_span_warn(shadower.span,
394 &format!("{} name `{}` shadows a \
395 {} name that is already in scope",
396 shadower.kind.desc(), name, orig.kind.desc()))
398 err.span_note(orig.span,
399 &format!("shadowed {} `{}` declared here",
400 orig.kind.desc(), name));
404 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
405 // if one of the label shadows a lifetime or another label.
406 fn extract_labels(ctxt: &mut LifetimeContext, b: &hir::Block) {
407 struct GatherLabels<'a> {
410 labels_in_fn: &'a mut Vec<(ast::Name, Span)>,
413 let mut gather = GatherLabels {
416 labels_in_fn: &mut ctxt.labels_in_fn,
418 gather.visit_block(b);
421 impl<'v, 'a> Visitor<'v> for GatherLabels<'a> {
422 fn visit_expr(&mut self, ex: &'v hir::Expr) {
423 // do not recurse into closures defined in the block
424 // since they are treated as separate fns from the POV of
426 if let hir::ExprClosure(..) = ex.node {
429 if let Some((label, label_span)) = expression_label(ex) {
430 for &(prior, prior_span) in &self.labels_in_fn[..] {
431 // FIXME (#24278): non-hygienic comparison
433 signal_shadowing_problem(self.sess,
435 original_label(prior_span),
436 shadower_label(label_span));
440 check_if_label_shadows_lifetime(self.sess,
445 self.labels_in_fn.push((label, label_span));
447 intravisit::walk_expr(self, ex)
450 fn visit_item(&mut self, _: &hir::Item) {
451 // do not recurse into items defined in the block
455 fn expression_label(ex: &hir::Expr) -> Option<(ast::Name, Span)> {
457 hir::ExprWhile(_, _, Some(label)) |
458 hir::ExprLoop(_, Some(label)) => Some((label.node, label.span)),
463 fn check_if_label_shadows_lifetime<'a>(sess: &'a Session,
464 mut scope: Scope<'a>,
469 FnScope { s, .. } => { scope = s; }
470 RootScope => { return; }
472 EarlyScope(_, lifetimes, s) |
473 LateScope(lifetimes, s) => {
474 for lifetime_def in lifetimes {
475 // FIXME (#24278): non-hygienic comparison
476 if label == lifetime_def.lifetime.name {
477 signal_shadowing_problem(
480 original_lifetime(&lifetime_def.lifetime),
481 shadower_label(label_span));
492 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
493 fn add_scope_and_walk_fn<'b>(&mut self,
498 fn_id: ast::NodeId) {
501 FnKind::ItemFn(_, generics, _, _, _, _, _) => {
502 intravisit::walk_fn_decl(self, fd);
503 self.visit_generics(generics);
505 FnKind::Method(_, sig, _, _) => {
506 intravisit::walk_fn_decl(self, fd);
507 self.visit_generics(&sig.generics);
509 FnKind::Closure(_) => {
510 intravisit::walk_fn_decl(self, fd);
514 // After inpsecting the decl, add all labels from the body to
515 // `self.labels_in_fn`.
516 extract_labels(self, fb);
518 self.with(FnScope { fn_id: fn_id, body_id: fb.id, s: self.scope },
519 |_old_scope, this| this.visit_block(fb))
522 fn with<F>(&mut self, wrap_scope: ScopeChain, f: F) where
523 F: FnOnce(Scope, &mut LifetimeContext),
525 let LifetimeContext {sess, hir_map, ref mut map, ..} = *self;
526 let mut this = LifetimeContext {
531 def_map: self.def_map,
532 trait_ref_hack: self.trait_ref_hack,
533 labels_in_fn: self.labels_in_fn.clone(),
535 debug!("entering scope {:?}", this.scope);
536 f(self.scope, &mut this);
537 debug!("exiting scope {:?}", this.scope);
540 /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
542 /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
543 /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
544 /// within type bounds; those are early bound lifetimes, and the rest are late bound.
548 /// fn foo<'a,'b,'c,T:Trait<'b>>(...)
550 /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
551 /// lifetimes may be interspersed together.
553 /// If early bound lifetimes are present, we separate them into their own list (and likewise
554 /// for late bound). They will be numbered sequentially, starting from the lowest index that is
555 /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
556 /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
557 /// ordering is not important there.
558 fn visit_early_late<F>(&mut self,
560 early_space: subst::ParamSpace,
562 generics: &hir::Generics,
564 F: FnOnce(&mut LifetimeContext),
566 let fn_def_id = self.hir_map.local_def_id(fn_id);
567 insert_late_bound_lifetimes(self.map,
572 let (late, early): (Vec<_>, _) =
576 .partition(|l| self.map.late_bound.contains_key(&l.lifetime.id));
579 this.with(EarlyScope(early_space, &early, this.scope), move |old_scope, this| {
580 this.with(LateScope(&late, this.scope), move |_, this| {
581 this.check_lifetime_defs(old_scope, &generics.lifetimes);
587 fn resolve_lifetime_ref(&mut self, lifetime_ref: &hir::Lifetime) {
588 // Walk up the scope chain, tracking the number of fn scopes
589 // that we pass through, until we find a lifetime with the
590 // given name or we run out of scopes. If we encounter a code
591 // block, then the lifetime is not bound but free, so switch
592 // over to `resolve_free_lifetime_ref()` to complete the
594 let mut late_depth = 0;
595 let mut scope = self.scope;
598 FnScope {fn_id, body_id, s } => {
599 return self.resolve_free_lifetime_ref(
600 region::CallSiteScopeData { fn_id: fn_id, body_id: body_id },
609 EarlyScope(space, lifetimes, s) => {
610 match search_lifetimes(lifetimes, lifetime_ref) {
611 Some((index, lifetime_def)) => {
612 let decl_id = lifetime_def.id;
613 let def = DefEarlyBoundRegion(space, index, decl_id);
614 self.insert_lifetime(lifetime_ref, def);
623 LateScope(lifetimes, s) => {
624 match search_lifetimes(lifetimes, lifetime_ref) {
625 Some((_index, lifetime_def)) => {
626 let decl_id = lifetime_def.id;
627 let debruijn = ty::DebruijnIndex::new(late_depth + 1);
628 let def = DefLateBoundRegion(debruijn, decl_id);
629 self.insert_lifetime(lifetime_ref, def);
642 self.unresolved_lifetime_ref(lifetime_ref);
645 fn resolve_free_lifetime_ref(&mut self,
646 scope_data: region::CallSiteScopeData,
647 lifetime_ref: &hir::Lifetime,
649 debug!("resolve_free_lifetime_ref \
650 scope_data: {:?} lifetime_ref: {:?} scope: {:?}",
651 scope_data, lifetime_ref, scope);
653 // Walk up the scope chain, tracking the outermost free scope,
654 // until we encounter a scope that contains the named lifetime
655 // or we run out of scopes.
656 let mut scope_data = scope_data;
657 let mut scope = scope;
658 let mut search_result = None;
660 debug!("resolve_free_lifetime_ref \
661 scope_data: {:?} scope: {:?} search_result: {:?}",
662 scope_data, scope, search_result);
664 FnScope { fn_id, body_id, s } => {
665 scope_data = region::CallSiteScopeData {
666 fn_id: fn_id, body_id: body_id
675 EarlyScope(_, lifetimes, s) |
676 LateScope(lifetimes, s) => {
677 search_result = search_lifetimes(lifetimes, lifetime_ref);
678 if search_result.is_some() {
686 match search_result {
687 Some((_depth, lifetime)) => {
688 let def = DefFreeRegion(scope_data, lifetime.id);
689 self.insert_lifetime(lifetime_ref, def);
693 self.unresolved_lifetime_ref(lifetime_ref);
699 fn unresolved_lifetime_ref(&self, lifetime_ref: &hir::Lifetime) {
700 span_err!(self.sess, lifetime_ref.span, E0261,
701 "use of undeclared lifetime name `{}`",
705 fn check_lifetime_defs(&mut self, old_scope: Scope, lifetimes: &[hir::LifetimeDef]) {
706 for i in 0..lifetimes.len() {
707 let lifetime_i = &lifetimes[i];
709 for lifetime in lifetimes {
710 if lifetime.lifetime.name == keywords::StaticLifetime.name() {
711 span_err!(self.sess, lifetime.lifetime.span, E0262,
712 "invalid lifetime parameter name: `{}`", lifetime.lifetime.name);
716 // It is a hard error to shadow a lifetime within the same scope.
717 for j in i + 1..lifetimes.len() {
718 let lifetime_j = &lifetimes[j];
720 if lifetime_i.lifetime.name == lifetime_j.lifetime.name {
721 struct_span_err!(self.sess, lifetime_j.lifetime.span, E0263,
722 "lifetime name `{}` declared twice in the same scope",
723 lifetime_j.lifetime.name)
724 .span_label(lifetime_j.lifetime.span,
725 &format!("declared twice"))
726 .span_label(lifetime_i.lifetime.span,
727 &format!("previous declaration here"))
732 // It is a soft error to shadow a lifetime within a parent scope.
733 self.check_lifetime_def_for_shadowing(old_scope, &lifetime_i.lifetime);
735 for bound in &lifetime_i.bounds {
736 self.resolve_lifetime_ref(bound);
741 fn check_lifetime_def_for_shadowing(&self,
742 mut old_scope: Scope,
743 lifetime: &hir::Lifetime)
745 for &(label, label_span) in &self.labels_in_fn {
746 // FIXME (#24278): non-hygienic comparison
747 if lifetime.name == label {
748 signal_shadowing_problem(self.sess,
750 original_label(label_span),
751 shadower_lifetime(&lifetime));
758 FnScope { s, .. } => {
766 EarlyScope(_, lifetimes, s) |
767 LateScope(lifetimes, s) => {
768 if let Some((_, lifetime_def)) = search_lifetimes(lifetimes, lifetime) {
769 signal_shadowing_problem(
772 original_lifetime(&lifetime_def),
773 shadower_lifetime(&lifetime));
783 fn insert_lifetime(&mut self,
784 lifetime_ref: &hir::Lifetime,
786 if lifetime_ref.id == ast::DUMMY_NODE_ID {
787 span_bug!(lifetime_ref.span,
788 "lifetime reference not renumbered, \
789 probably a bug in syntax::fold");
792 debug!("lifetime_ref={:?} id={:?} resolved to {:?} span={:?}",
793 lifetime_to_string(lifetime_ref),
796 self.sess.codemap().span_to_string(lifetime_ref.span));
797 self.map.defs.insert(lifetime_ref.id, def);
801 fn search_lifetimes<'a>(lifetimes: &'a [hir::LifetimeDef],
802 lifetime_ref: &hir::Lifetime)
803 -> Option<(u32, &'a hir::Lifetime)> {
804 for (i, lifetime_decl) in lifetimes.iter().enumerate() {
805 if lifetime_decl.lifetime.name == lifetime_ref.name {
806 return Some((i as u32, &lifetime_decl.lifetime));
812 ///////////////////////////////////////////////////////////////////////////
814 /// Detects late-bound lifetimes and inserts them into
815 /// `map.late_bound`.
817 /// A region declared on a fn is **late-bound** if:
818 /// - it is constrained by an argument type;
819 /// - it does not appear in a where-clause.
821 /// "Constrained" basically means that it appears in any type but
822 /// not amongst the inputs to a projection. In other words, `<&'a
823 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
824 fn insert_late_bound_lifetimes(map: &mut NamedRegionMap,
827 generics: &hir::Generics) {
828 debug!("insert_late_bound_lifetimes(decl={:?}, generics={:?})", decl, generics);
830 let mut constrained_by_input = ConstrainedCollector { regions: FnvHashSet() };
831 for arg in &decl.inputs {
832 constrained_by_input.visit_ty(&arg.ty);
835 let mut appears_in_output = AllCollector {
836 regions: FnvHashSet(),
839 intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
841 debug!("insert_late_bound_lifetimes: constrained_by_input={:?}",
842 constrained_by_input.regions);
844 // Walk the lifetimes that appear in where clauses.
846 // Subtle point: because we disallow nested bindings, we can just
847 // ignore binders here and scrape up all names we see.
848 let mut appears_in_where_clause = AllCollector {
849 regions: FnvHashSet(),
852 for ty_param in generics.ty_params.iter() {
853 walk_list!(&mut appears_in_where_clause,
854 visit_ty_param_bound,
857 walk_list!(&mut appears_in_where_clause,
858 visit_where_predicate,
859 &generics.where_clause.predicates);
860 for lifetime_def in &generics.lifetimes {
861 if !lifetime_def.bounds.is_empty() {
862 // `'a: 'b` means both `'a` and `'b` are referenced
863 appears_in_where_clause.visit_lifetime_def(lifetime_def);
867 debug!("insert_late_bound_lifetimes: appears_in_where_clause={:?}",
868 appears_in_where_clause.regions);
870 // Late bound regions are those that:
871 // - appear in the inputs
872 // - do not appear in the where-clauses
873 // - are not implicitly captured by `impl Trait`
874 for lifetime in &generics.lifetimes {
875 let name = lifetime.lifetime.name;
877 // appears in the where clauses? early-bound.
878 if appears_in_where_clause.regions.contains(&name) { continue; }
880 // any `impl Trait` in the return type? early-bound.
881 if appears_in_output.impl_trait { continue; }
883 // does not appear in the inputs, but appears in the return
884 // type? eventually this will be early-bound, but for now we
885 // just mark it so we can issue warnings.
886 let constrained_by_input = constrained_by_input.regions.contains(&name);
887 let appears_in_output = appears_in_output.regions.contains(&name);
888 let will_change = !constrained_by_input && appears_in_output;
889 let issue_32330 = if will_change {
890 ty::Issue32330::WillChange {
891 fn_def_id: fn_def_id,
895 ty::Issue32330::WontChange
898 debug!("insert_late_bound_lifetimes: \
899 lifetime {:?} with id {:?} is late-bound ({:?}",
900 lifetime.lifetime.name, lifetime.lifetime.id, issue_32330);
902 let prev = map.late_bound.insert(lifetime.lifetime.id, issue_32330);
903 assert!(prev.is_none(), "visited lifetime {:?} twice", lifetime.lifetime.id);
908 struct ConstrainedCollector {
909 regions: FnvHashSet<ast::Name>,
912 impl<'v> Visitor<'v> for ConstrainedCollector {
913 fn visit_ty(&mut self, ty: &'v hir::Ty) {
915 hir::TyPath(Some(_), _) => {
916 // ignore lifetimes appearing in associated type
917 // projections, as they are not *constrained*
921 hir::TyPath(None, ref path) => {
922 // consider only the lifetimes on the final
923 // segment; I am not sure it's even currently
924 // valid to have them elsewhere, but even if it
925 // is, those would be potentially inputs to
927 if let Some(last_segment) = path.segments.last() {
928 self.visit_path_segment(path.span, last_segment);
933 intravisit::walk_ty(self, ty);
938 fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
939 self.regions.insert(lifetime_ref.name);
943 struct AllCollector {
944 regions: FnvHashSet<ast::Name>,
948 impl<'v> Visitor<'v> for AllCollector {
949 fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
950 self.regions.insert(lifetime_ref.name);
953 fn visit_ty(&mut self, ty: &hir::Ty) {
954 if let hir::TyImplTrait(_) = ty.node {
955 self.impl_trait = true;
957 intravisit::walk_ty(self, ty);
962 impl<'a> fmt::Debug for ScopeChain<'a> {
963 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
965 EarlyScope(space, defs, _) => write!(fmt, "EarlyScope({:?}, {:?})", space, defs),
966 LateScope(defs, _) => write!(fmt, "LateScope({:?})", defs),
967 FnScope { fn_id, body_id, s: _ } => write!(fmt, "FnScope({:?}, {:?})", fn_id, body_id),
968 RootScope => write!(fmt, "RootScope"),