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.
19 use hir::def_id::{CrateNum, DefId, LocalDefId, LOCAL_CRATE};
22 use hir::LifetimeName;
23 use ty::{self, TyCtxt, GenericParamDefKind};
25 use errors::DiagnosticBuilder;
27 use rustc_data_structures::sync::Lrc;
30 use std::mem::replace;
36 use util::nodemap::{DefIdMap, FxHashMap, FxHashSet, NodeMap, NodeSet};
38 use hir::intravisit::{self, NestedVisitorMap, Visitor};
39 use hir::{self, GenericParamsExt};
41 /// The origin of a named lifetime definition.
43 /// This is used to prevent the usage of in-band lifetimes in `Fn`/`fn` syntax.
44 #[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
45 pub enum LifetimeDefOrigin {
46 // Explicit binders like `fn foo<'a>(x: &'a u8)`
48 // In-band declarations like `fn foo(x: &'a u8)`
52 impl LifetimeDefOrigin {
53 fn from_is_in_band(is_in_band: bool) -> Self {
55 LifetimeDefOrigin::InBand
57 LifetimeDefOrigin::Explicit
62 // This counts the no of times a lifetime is used
63 #[derive(Clone, Copy, Debug)]
64 pub enum LifetimeUseSet<'tcx> {
65 One(&'tcx hir::Lifetime),
69 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
74 /* lifetime decl */ DefId,
79 /* lifetime decl */ DefId,
82 LateBoundAnon(ty::DebruijnIndex, /* anon index */ u32),
83 Free(DefId, /* lifetime decl */ DefId),
90 def: &hir::LifetimeDef,
91 ) -> (hir::LifetimeName, Region) {
94 let def_id = hir_map.local_def_id(def.lifetime.id);
95 let origin = LifetimeDefOrigin::from_is_in_band(def.in_band);
96 debug!("Region::early: index={} def_id={:?}", i, def_id);
97 (def.lifetime.name, Region::EarlyBound(i, def_id, origin))
100 fn late(hir_map: &Map, def: &hir::LifetimeDef) -> (hir::LifetimeName, Region) {
101 let depth = ty::INNERMOST;
102 let def_id = hir_map.local_def_id(def.lifetime.id);
103 let origin = LifetimeDefOrigin::from_is_in_band(def.in_band);
105 "Region::late: def={:?} depth={:?} def_id={:?} origin={:?}",
111 (def.lifetime.name, Region::LateBound(depth, def_id, origin))
114 fn late_anon(index: &Cell<u32>) -> Region {
117 let depth = ty::INNERMOST;
118 Region::LateBoundAnon(depth, i)
121 fn id(&self) -> Option<DefId> {
123 Region::Static | Region::LateBoundAnon(..) => None,
125 Region::EarlyBound(_, id, _) | Region::LateBound(_, id, _) | Region::Free(_, id) => {
131 fn shifted(self, amount: u32) -> Region {
133 Region::LateBound(debruijn, id, origin) => {
134 Region::LateBound(debruijn.shifted_in(amount), id, origin)
136 Region::LateBoundAnon(debruijn, index) => {
137 Region::LateBoundAnon(debruijn.shifted_in(amount), index)
143 fn shifted_out_to_binder(self, binder: ty::DebruijnIndex) -> Region {
145 Region::LateBound(debruijn, id, origin) => Region::LateBound(
146 debruijn.shifted_out_to_binder(binder),
150 Region::LateBoundAnon(debruijn, index) => Region::LateBoundAnon(
151 debruijn.shifted_out_to_binder(binder),
158 fn subst(self, params: &[hir::Lifetime], map: &NamedRegionMap) -> Option<Region> {
159 if let Region::EarlyBound(index, _, _) = self {
162 .and_then(|lifetime| map.defs.get(&lifetime.id).cloned())
169 /// A set containing, at most, one known element.
170 /// If two distinct values are inserted into a set, then it
171 /// becomes `Many`, which can be used to detect ambiguities.
172 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
179 impl<T: PartialEq> Set1<T> {
180 pub fn insert(&mut self, value: T) {
181 if let Set1::Empty = *self {
182 *self = Set1::One(value);
185 if let Set1::One(ref old) = *self {
194 pub type ObjectLifetimeDefault = Set1<Region>;
196 /// Maps the id of each lifetime reference to the lifetime decl
197 /// that it corresponds to.
199 /// FIXME. This struct gets converted to a `ResolveLifetimes` for
200 /// actual use. It has the same data, but indexed by `DefIndex`. This
203 struct NamedRegionMap {
204 // maps from every use of a named (not anonymous) lifetime to a
205 // `Region` describing how that region is bound
206 pub defs: NodeMap<Region>,
208 // the set of lifetime def ids that are late-bound; a region can
209 // be late-bound if (a) it does NOT appear in a where-clause and
210 // (b) it DOES appear in the arguments.
211 pub late_bound: NodeSet,
213 // For each type and trait definition, maps type parameters
214 // to the trait object lifetime defaults computed from them.
215 pub object_lifetime_defaults: NodeMap<Vec<ObjectLifetimeDefault>>,
218 /// See `NamedRegionMap`.
219 pub struct ResolveLifetimes {
220 defs: FxHashMap<LocalDefId, Lrc<FxHashMap<ItemLocalId, Region>>>,
221 late_bound: FxHashMap<LocalDefId, Lrc<FxHashSet<ItemLocalId>>>,
222 object_lifetime_defaults:
223 FxHashMap<LocalDefId, Lrc<FxHashMap<ItemLocalId, Lrc<Vec<ObjectLifetimeDefault>>>>>,
226 impl_stable_hash_for!(struct ::middle::resolve_lifetime::ResolveLifetimes {
229 object_lifetime_defaults
232 struct LifetimeContext<'a, 'tcx: 'a> {
233 tcx: TyCtxt<'a, 'tcx, 'tcx>,
234 map: &'a mut NamedRegionMap,
237 /// Deep breath. Our representation for poly trait refs contains a single
238 /// binder and thus we only allow a single level of quantification. However,
239 /// the syntax of Rust permits quantification in two places, e.g., `T: for <'a> Foo<'a>`
240 /// and `for <'a, 'b> &'b T: Foo<'a>`. In order to get the de Bruijn indices
241 /// correct when representing these constraints, we should only introduce one
242 /// scope. However, we want to support both locations for the quantifier and
243 /// during lifetime resolution we want precise information (so we can't
244 /// desugar in an earlier phase).
246 /// SO, if we encounter a quantifier at the outer scope, we set
247 /// trait_ref_hack to true (and introduce a scope), and then if we encounter
248 /// a quantifier at the inner scope, we error. If trait_ref_hack is false,
249 /// then we introduce the scope at the inner quantifier.
252 trait_ref_hack: bool,
254 /// Used to disallow the use of in-band lifetimes in `fn` or `Fn` syntax.
255 is_in_fn_syntax: bool,
257 /// List of labels in the function/method currently under analysis.
258 labels_in_fn: Vec<(ast::Name, Span)>,
260 /// Cache for cross-crate per-definition object lifetime defaults.
261 xcrate_object_lifetime_defaults: DefIdMap<Vec<ObjectLifetimeDefault>>,
263 lifetime_uses: &'a mut DefIdMap<LifetimeUseSet<'tcx>>,
268 /// Declares lifetimes, and each can be early-bound or late-bound.
269 /// The `DebruijnIndex` of late-bound lifetimes starts at `1` and
270 /// it should be shifted by the number of `Binder`s in between the
271 /// declaration `Binder` and the location it's referenced from.
273 lifetimes: FxHashMap<hir::LifetimeName, Region>,
275 /// if we extend this scope with another scope, what is the next index
276 /// we should use for an early-bound region?
277 next_early_index: u32,
279 /// Flag is set to true if, in this binder, `'_` would be
280 /// equivalent to a "single-use region". This is true on
281 /// impls, but not other kinds of items.
282 track_lifetime_uses: bool,
284 /// Whether or not this binder would serve as the parent
285 /// binder for abstract types introduced within. For example:
287 /// fn foo<'a>() -> impl for<'b> Trait<Item = impl Trait2<'a>>
289 /// Here, the abstract types we create for the `impl Trait`
290 /// and `impl Trait2` references will both have the `foo` item
291 /// as their parent. When we get to `impl Trait2`, we find
292 /// that it is nested within the `for<>` binder -- this flag
293 /// allows us to skip that when looking for the parent binder
294 /// of the resulting abstract type.
295 abstract_type_parent: bool,
300 /// Lifetimes introduced by a fn are scoped to the call-site for that fn,
301 /// if this is a fn body, otherwise the original definitions are used.
302 /// Unspecified lifetimes are inferred, unless an elision scope is nested,
303 /// e.g. `(&T, fn(&T) -> &T);` becomes `(&'_ T, for<'a> fn(&'a T) -> &'a T)`.
309 /// A scope which either determines unspecified lifetimes or errors
310 /// on them (e.g. due to ambiguity). For more details, see `Elide`.
316 /// Use a specific lifetime (if `Some`) or leave it unset (to be
317 /// inferred in a function body or potentially error outside one),
318 /// for the default choice of lifetime in a trait object type.
319 ObjectLifetimeDefault {
320 lifetime: Option<Region>,
327 #[derive(Clone, Debug)]
329 /// Use a fresh anonymous late-bound lifetime each time, by
330 /// incrementing the counter to generate sequential indices.
331 FreshLateAnon(Cell<u32>),
332 /// Always use this one lifetime.
334 /// Less or more than one lifetime were found, error on unspecified.
335 Error(Vec<ElisionFailureInfo>),
338 #[derive(Clone, Debug)]
339 struct ElisionFailureInfo {
340 /// Where we can find the argument pattern.
341 parent: Option<hir::BodyId>,
342 /// The index of the argument in the original definition.
344 lifetime_count: usize,
345 have_bound_regions: bool,
348 type ScopeRef<'a> = &'a Scope<'a>;
350 const ROOT_SCOPE: ScopeRef<'static> = &Scope::Root;
352 pub fn provide(providers: &mut ty::query::Providers) {
353 *providers = ty::query::Providers {
356 named_region_map: |tcx, id| {
357 let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
358 tcx.resolve_lifetimes(LOCAL_CRATE).defs.get(&id).cloned()
361 is_late_bound_map: |tcx, id| {
362 let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
363 tcx.resolve_lifetimes(LOCAL_CRATE)
369 object_lifetime_defaults_map: |tcx, id| {
370 let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
371 tcx.resolve_lifetimes(LOCAL_CRATE)
372 .object_lifetime_defaults
380 // (*) FIXME the query should be defined to take a LocalDefId
383 /// Computes the `ResolveLifetimes` map that contains data for the
384 /// entire crate. You should not read the result of this query
385 /// directly, but rather use `named_region_map`, `is_late_bound_map`,
387 fn resolve_lifetimes<'tcx>(
388 tcx: TyCtxt<'_, 'tcx, 'tcx>,
390 ) -> Lrc<ResolveLifetimes> {
391 assert_eq!(for_krate, LOCAL_CRATE);
393 let named_region_map = krate(tcx);
395 let mut defs = FxHashMap();
396 for (k, v) in named_region_map.defs {
397 let hir_id = tcx.hir.node_to_hir_id(k);
398 let map = defs.entry(hir_id.owner_local_def_id())
399 .or_insert_with(|| Lrc::new(FxHashMap()));
400 Lrc::get_mut(map).unwrap().insert(hir_id.local_id, v);
402 let mut late_bound = FxHashMap();
403 for k in named_region_map.late_bound {
404 let hir_id = tcx.hir.node_to_hir_id(k);
406 .entry(hir_id.owner_local_def_id())
407 .or_insert_with(|| Lrc::new(FxHashSet()));
408 Lrc::get_mut(map).unwrap().insert(hir_id.local_id);
410 let mut object_lifetime_defaults = FxHashMap();
411 for (k, v) in named_region_map.object_lifetime_defaults {
412 let hir_id = tcx.hir.node_to_hir_id(k);
413 let map = object_lifetime_defaults
414 .entry(hir_id.owner_local_def_id())
415 .or_insert_with(|| Lrc::new(FxHashMap()));
418 .insert(hir_id.local_id, Lrc::new(v));
421 Lrc::new(ResolveLifetimes {
424 object_lifetime_defaults,
428 fn krate<'tcx>(tcx: TyCtxt<'_, 'tcx, 'tcx>) -> NamedRegionMap {
429 let krate = tcx.hir.krate();
430 let mut map = NamedRegionMap {
432 late_bound: NodeSet(),
433 object_lifetime_defaults: compute_object_lifetime_defaults(tcx),
436 let mut visitor = LifetimeContext {
440 trait_ref_hack: false,
441 is_in_fn_syntax: false,
442 labels_in_fn: vec![],
443 xcrate_object_lifetime_defaults: DefIdMap(),
444 lifetime_uses: &mut DefIdMap(),
446 for (_, item) in &krate.items {
447 visitor.visit_item(item);
453 impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
454 fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
455 NestedVisitorMap::All(&self.tcx.hir)
458 // We want to nest trait/impl items in their parent, but nothing else.
459 fn visit_nested_item(&mut self, _: hir::ItemId) {}
461 fn visit_nested_body(&mut self, body: hir::BodyId) {
462 // Each body has their own set of labels, save labels.
463 let saved = replace(&mut self.labels_in_fn, vec![]);
464 let body = self.tcx.hir.body(body);
465 extract_labels(self, body);
472 this.visit_body(body);
475 replace(&mut self.labels_in_fn, saved);
478 fn visit_item(&mut self, item: &'tcx hir::Item) {
480 hir::ItemFn(ref decl, _, _, _, ref generics, _) => {
481 self.visit_early_late(None, decl, generics, |this| {
482 intravisit::walk_item(this, item);
486 hir::ItemExternCrate(_)
489 | hir::ItemForeignMod(..)
490 | hir::ItemGlobalAsm(..) => {
491 // These sorts of items have no lifetime parameters at all.
492 intravisit::walk_item(self, item);
494 hir::ItemStatic(..) | hir::ItemConst(..) => {
495 // No lifetime parameters, but implied 'static.
496 let scope = Scope::Elision {
497 elide: Elide::Exact(Region::Static),
500 self.with(scope, |_, this| intravisit::walk_item(this, item));
502 hir::ItemExistential(hir::ExistTy { impl_trait_fn: Some(_), .. }) => {
503 // currently existential type declarations are just generated from impl Trait
504 // items. doing anything on this node is irrelevant, as we currently don't need
507 hir::ItemTy(_, ref generics)
508 | hir::ItemExistential(hir::ExistTy { impl_trait_fn: None, ref generics, .. })
509 | hir::ItemEnum(_, ref generics)
510 | hir::ItemStruct(_, ref generics)
511 | hir::ItemUnion(_, ref generics)
512 | hir::ItemTrait(_, _, ref generics, ..)
513 | hir::ItemTraitAlias(ref generics, ..)
514 | hir::ItemImpl(_, _, _, ref generics, ..) => {
515 // Impls permit `'_` to be used and it is equivalent to "some fresh lifetime name".
516 // This is not true for other kinds of items.x
517 let track_lifetime_uses = match item.node {
518 hir::ItemImpl(..) => true,
521 // These kinds of items have only early bound lifetime parameters.
522 let mut index = if let hir::ItemTrait(..) = item.node {
523 1 // Self comes before lifetimes
527 let lifetimes = generics
529 .map(|def| Region::early(&self.tcx.hir, &mut index, def))
531 let next_early_index = index + generics.ty_params().count() as u32;
532 let scope = Scope::Binder {
535 abstract_type_parent: true,
539 self.with(scope, |old_scope, this| {
540 this.check_lifetime_params(old_scope, &generics.params);
541 intravisit::walk_item(this, item);
547 fn visit_foreign_item(&mut self, item: &'tcx hir::ForeignItem) {
549 hir::ForeignItemFn(ref decl, _, ref generics) => {
550 self.visit_early_late(None, decl, generics, |this| {
551 intravisit::walk_foreign_item(this, item);
554 hir::ForeignItemStatic(..) => {
555 intravisit::walk_foreign_item(self, item);
557 hir::ForeignItemType => {
558 intravisit::walk_foreign_item(self, item);
563 fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
564 debug!("visit_ty: id={:?} ty={:?}", ty.id, ty);
566 hir::TyBareFn(ref c) => {
567 let next_early_index = self.next_early_index();
568 let was_in_fn_syntax = self.is_in_fn_syntax;
569 self.is_in_fn_syntax = true;
570 let scope = Scope::Binder {
571 lifetimes: c.generic_params
573 .map(|def| Region::late(&self.tcx.hir, def))
577 track_lifetime_uses: true,
578 abstract_type_parent: false,
580 self.with(scope, |old_scope, this| {
581 // a bare fn has no bounds, so everything
582 // contained within is scoped within its binder.
583 this.check_lifetime_params(old_scope, &c.generic_params);
584 intravisit::walk_ty(this, ty);
586 self.is_in_fn_syntax = was_in_fn_syntax;
588 hir::TyTraitObject(ref bounds, ref lifetime) => {
589 for bound in bounds {
590 self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
592 match lifetime.name {
593 LifetimeName::Implicit => {
594 // If the user does not write *anything*, we
595 // use the object lifetime defaulting
596 // rules. So e.g. `Box<dyn Debug>` becomes
597 // `Box<dyn Debug + 'static>`.
598 self.resolve_object_lifetime_default(lifetime)
600 LifetimeName::Underscore => {
601 // If the user writes `'_`, we use the *ordinary* elision
602 // rules. So the `'_` in e.g. `Box<dyn Debug + '_>` will be
603 // resolved the same as the `'_` in `&'_ Foo`.
606 self.resolve_elided_lifetimes(slice::from_ref(lifetime), false)
608 LifetimeName::Fresh(_) | LifetimeName::Static | LifetimeName::Name(_) => {
609 // If the user wrote an explicit name, use that.
610 self.visit_lifetime(lifetime);
614 hir::TyRptr(ref lifetime_ref, ref mt) => {
615 self.visit_lifetime(lifetime_ref);
616 let scope = Scope::ObjectLifetimeDefault {
617 lifetime: self.map.defs.get(&lifetime_ref.id).cloned(),
620 self.with(scope, |_, this| this.visit_ty(&mt.ty));
622 hir::TyImplTraitExistential(item_id, _, ref lifetimes) => {
623 // Resolve the lifetimes that are applied to the existential type.
624 // These are resolved in the current scope.
625 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
626 // `fn foo<'a>() -> MyAnonTy<'a> { ... }`
627 // ^ ^this gets resolved in the current scope
628 for lifetime in lifetimes {
629 self.visit_lifetime(lifetime);
631 // Check for predicates like `impl for<'a> SomeTrait<impl OtherTrait<'a>>`
632 // and ban them. Type variables instantiated inside binders aren't
633 // well-supported at the moment, so this doesn't work.
634 // In the future, this should be fixed and this error should be removed.
635 let def = self.map.defs.get(&lifetime.id);
636 if let Some(&Region::LateBound(_, def_id, _)) = def {
637 if let Some(node_id) = self.tcx.hir.as_local_node_id(def_id) {
638 // Ensure that the parent of the def is an item, not HRTB
639 let parent_id = self.tcx.hir.get_parent_node(node_id);
640 let parent_impl_id = hir::ImplItemId { node_id: parent_id };
641 let parent_trait_id = hir::TraitItemId { node_id: parent_id };
642 let krate = self.tcx.hir.forest.krate();
643 if !(krate.items.contains_key(&parent_id)
644 || krate.impl_items.contains_key(&parent_impl_id)
645 || krate.trait_items.contains_key(&parent_trait_id))
651 "`impl Trait` can only capture lifetimes \
652 bound at the fn or impl level"
659 // Resolve the lifetimes in the bounds to the lifetime defs in the generics.
660 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
661 // `abstract type MyAnonTy<'b>: MyTrait<'b>;`
662 // ^ ^ this gets resolved in the scope of
663 // the exist_ty generics
664 let (generics, bounds) = match self.tcx.hir.expect_item(item_id.id).node {
665 hir::ItemExistential(hir::ExistTy{ ref generics, ref bounds, .. }) => (
669 ref i => bug!("impl Trait pointed to non-existential type?? {:#?}", i),
672 // We want to start our early-bound indices at the end of the parent scope,
673 // not including any parent `impl Trait`s.
674 let mut index = self.next_early_index_for_abstract_type();
675 debug!("visit_ty: index = {}", index);
677 let mut elision = None;
678 let mut lifetimes = FxHashMap();
679 for lt_def in generics.lifetimes() {
680 let (lt_name, region) = Region::early(&self.tcx.hir, &mut index, <_def);
681 if let hir::LifetimeName::Underscore = lt_name {
682 // Pick the elided lifetime "definition" if one exists and use it to make
684 elision = Some(region);
686 lifetimes.insert(lt_name, region);
690 let next_early_index = index + generics.ty_params().count() as u32;
692 if let Some(elision_region) = elision {
693 let scope = Scope::Elision {
694 elide: Elide::Exact(elision_region),
697 self.with(scope, |_old_scope, this| {
698 let scope = Scope::Binder {
702 track_lifetime_uses: true,
703 abstract_type_parent: false,
705 this.with(scope, |_old_scope, this| {
706 this.visit_generics(generics);
707 for bound in bounds {
708 this.visit_ty_param_bound(bound);
713 let scope = Scope::Binder {
717 track_lifetime_uses: true,
718 abstract_type_parent: false,
720 self.with(scope, |_old_scope, this| {
721 this.visit_generics(generics);
722 for bound in bounds {
723 this.visit_ty_param_bound(bound);
728 _ => intravisit::walk_ty(self, ty),
732 fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
733 use self::hir::TraitItemKind::*;
734 match trait_item.node {
735 Method(ref sig, _) => {
737 self.visit_early_late(
738 Some(tcx.hir.get_parent(trait_item.id)),
740 &trait_item.generics,
741 |this| intravisit::walk_trait_item(this, trait_item),
744 Type(ref bounds, ref ty) => {
745 let generics = &trait_item.generics;
746 let mut index = self.next_early_index();
747 debug!("visit_ty: index = {}", index);
748 let lifetimes = generics
750 .map(|lt_def| Region::early(&self.tcx.hir, &mut index, lt_def))
753 let next_early_index = index + generics.ty_params().count() as u32;
754 let scope = Scope::Binder {
758 track_lifetime_uses: true,
759 abstract_type_parent: true,
761 self.with(scope, |_old_scope, this| {
762 this.visit_generics(generics);
763 for bound in bounds {
764 this.visit_ty_param_bound(bound);
766 if let Some(ty) = ty {
772 // Only methods and types support generics.
773 assert!(trait_item.generics.params.is_empty());
774 intravisit::walk_trait_item(self, trait_item);
779 fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
780 use self::hir::ImplItemKind::*;
781 match impl_item.node {
782 Method(ref sig, _) => {
784 self.visit_early_late(
785 Some(tcx.hir.get_parent(impl_item.id)),
788 |this| intravisit::walk_impl_item(this, impl_item),
792 let generics = &impl_item.generics;
793 let mut index = self.next_early_index();
794 debug!("visit_ty: index = {}", index);
795 let lifetimes = generics
797 .map(|lt_def| Region::early(&self.tcx.hir, &mut index, lt_def))
800 let next_early_index = index + generics.ty_params().count() as u32;
801 let scope = Scope::Binder {
805 track_lifetime_uses: true,
806 abstract_type_parent: true,
808 self.with(scope, |_old_scope, this| {
809 this.visit_generics(generics);
814 // Only methods and types support generics.
815 assert!(impl_item.generics.params.is_empty());
816 intravisit::walk_impl_item(self, impl_item);
821 fn visit_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
822 if lifetime_ref.is_elided() {
823 self.resolve_elided_lifetimes(slice::from_ref(lifetime_ref), false);
826 if lifetime_ref.is_static() {
827 self.insert_lifetime(lifetime_ref, Region::Static);
830 self.resolve_lifetime_ref(lifetime_ref);
833 fn visit_path(&mut self, path: &'tcx hir::Path, _: ast::NodeId) {
834 for (i, segment) in path.segments.iter().enumerate() {
835 let depth = path.segments.len() - i - 1;
836 if let Some(ref parameters) = segment.parameters {
837 self.visit_segment_parameters(path.def, depth, parameters);
842 fn visit_fn_decl(&mut self, fd: &'tcx hir::FnDecl) {
843 let output = match fd.output {
844 hir::DefaultReturn(_) => None,
845 hir::Return(ref ty) => Some(ty),
847 self.visit_fn_like_elision(&fd.inputs, output);
850 fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
851 check_mixed_explicit_and_in_band_defs(
853 &generics.lifetimes().cloned().collect::<Vec<_>>(),
855 for ty_param in generics.ty_params() {
856 walk_list!(self, visit_ty_param_bound, &ty_param.bounds);
857 if let Some(ref ty) = ty_param.default {
861 for predicate in &generics.where_clause.predicates {
863 &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate {
866 ref bound_generic_params,
869 if bound_generic_params.iter().any(|p| p.is_lifetime_param()) {
870 self.trait_ref_hack = true;
871 let next_early_index = self.next_early_index();
872 let scope = Scope::Binder {
873 lifetimes: bound_generic_params
875 .map(|def| Region::late(&self.tcx.hir, def))
879 track_lifetime_uses: true,
880 abstract_type_parent: false,
882 let result = self.with(scope, |old_scope, this| {
883 this.check_lifetime_params(old_scope, &bound_generic_params);
884 this.visit_ty(&bounded_ty);
885 walk_list!(this, visit_ty_param_bound, bounds);
887 self.trait_ref_hack = false;
890 self.visit_ty(&bounded_ty);
891 walk_list!(self, visit_ty_param_bound, bounds);
894 &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate {
899 self.visit_lifetime(lifetime);
900 for bound in bounds {
901 self.visit_lifetime(bound);
904 &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate {
909 self.visit_ty(lhs_ty);
910 self.visit_ty(rhs_ty);
916 fn visit_poly_trait_ref(
918 trait_ref: &'tcx hir::PolyTraitRef,
919 _modifier: hir::TraitBoundModifier,
921 debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
923 if !self.trait_ref_hack
925 .bound_generic_params
927 .any(|p| p.is_lifetime_param())
929 if self.trait_ref_hack {
934 "nested quantification of lifetimes"
937 let next_early_index = self.next_early_index();
938 let scope = Scope::Binder {
940 .bound_generic_params
942 .map(|def| Region::late(&self.tcx.hir, def))
946 track_lifetime_uses: true,
947 abstract_type_parent: false,
949 self.with(scope, |old_scope, this| {
950 this.check_lifetime_params(old_scope, &trait_ref.bound_generic_params);
951 walk_list!(this, visit_generic_param, &trait_ref.bound_generic_params);
952 this.visit_trait_ref(&trait_ref.trait_ref)
955 self.visit_trait_ref(&trait_ref.trait_ref)
960 #[derive(Copy, Clone, PartialEq)]
974 fn original_label(span: Span) -> Original {
976 kind: ShadowKind::Label,
980 fn shadower_label(span: Span) -> Shadower {
982 kind: ShadowKind::Label,
986 fn original_lifetime(span: Span) -> Original {
988 kind: ShadowKind::Lifetime,
992 fn shadower_lifetime(l: &hir::Lifetime) -> Shadower {
994 kind: ShadowKind::Lifetime,
1000 fn desc(&self) -> &'static str {
1002 ShadowKind::Label => "label",
1003 ShadowKind::Lifetime => "lifetime",
1008 fn check_mixed_explicit_and_in_band_defs(
1009 tcx: TyCtxt<'_, '_, '_>,
1010 lifetime_defs: &[hir::LifetimeDef],
1012 let oob_def = lifetime_defs.iter().find(|lt| !lt.in_band);
1013 let in_band_def = lifetime_defs.iter().find(|lt| lt.in_band);
1015 if let (Some(oob_def), Some(in_band_def)) = (oob_def, in_band_def) {
1018 in_band_def.lifetime.span,
1020 "cannot mix in-band and explicit lifetime definitions"
1022 in_band_def.lifetime.span,
1023 "in-band lifetime definition here",
1025 .span_label(oob_def.lifetime.span, "explicit lifetime definition here")
1030 fn signal_shadowing_problem(
1031 tcx: TyCtxt<'_, '_, '_>,
1036 let mut err = if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
1037 // lifetime/lifetime shadowing is an error
1042 "{} name `{}` shadows a \
1043 {} name that is already in scope",
1044 shadower.kind.desc(),
1049 // shadowing involving a label is only a warning, due to issues with
1050 // labels and lifetimes not being macro-hygienic.
1051 tcx.sess.struct_span_warn(
1054 "{} name `{}` shadows a \
1055 {} name that is already in scope",
1056 shadower.kind.desc(),
1062 err.span_label(orig.span, "first declared here");
1063 err.span_label(shadower.span, format!("lifetime {} already in scope", name));
1067 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
1068 // if one of the label shadows a lifetime or another label.
1069 fn extract_labels(ctxt: &mut LifetimeContext<'_, '_>, body: &hir::Body) {
1070 struct GatherLabels<'a, 'tcx: 'a> {
1071 tcx: TyCtxt<'a, 'tcx, 'tcx>,
1072 scope: ScopeRef<'a>,
1073 labels_in_fn: &'a mut Vec<(ast::Name, Span)>,
1076 let mut gather = GatherLabels {
1079 labels_in_fn: &mut ctxt.labels_in_fn,
1081 gather.visit_body(body);
1083 impl<'v, 'a, 'tcx> Visitor<'v> for GatherLabels<'a, 'tcx> {
1084 fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1085 NestedVisitorMap::None
1088 fn visit_expr(&mut self, ex: &hir::Expr) {
1089 if let Some((label, label_span)) = expression_label(ex) {
1090 for &(prior, prior_span) in &self.labels_in_fn[..] {
1091 // FIXME (#24278): non-hygienic comparison
1093 signal_shadowing_problem(
1096 original_label(prior_span),
1097 shadower_label(label_span),
1102 check_if_label_shadows_lifetime(self.tcx, self.scope, label, label_span);
1104 self.labels_in_fn.push((label, label_span));
1106 intravisit::walk_expr(self, ex)
1110 fn expression_label(ex: &hir::Expr) -> Option<(ast::Name, Span)> {
1112 hir::ExprWhile(.., Some(label)) | hir::ExprLoop(_, Some(label), _) => {
1113 Some((label.name, label.span))
1119 fn check_if_label_shadows_lifetime(
1120 tcx: TyCtxt<'_, '_, '_>,
1121 mut scope: ScopeRef<'_>,
1127 Scope::Body { s, .. }
1128 | Scope::Elision { s, .. }
1129 | Scope::ObjectLifetimeDefault { s, .. } => {
1138 ref lifetimes, s, ..
1140 // FIXME (#24278): non-hygienic comparison
1141 if let Some(def) = lifetimes.get(&hir::LifetimeName::Name(label)) {
1142 let node_id = tcx.hir.as_local_node_id(def.id().unwrap()).unwrap();
1144 signal_shadowing_problem(
1147 original_lifetime(tcx.hir.span(node_id)),
1148 shadower_label(label_span),
1159 fn compute_object_lifetime_defaults(
1160 tcx: TyCtxt<'_, '_, '_>,
1161 ) -> NodeMap<Vec<ObjectLifetimeDefault>> {
1162 let mut map = NodeMap();
1163 for item in tcx.hir.krate().items.values() {
1165 hir::ItemStruct(_, ref generics)
1166 | hir::ItemUnion(_, ref generics)
1167 | hir::ItemEnum(_, ref generics)
1168 | hir::ItemTy(_, ref generics)
1169 | hir::ItemTrait(_, _, ref generics, ..) => {
1170 let result = object_lifetime_defaults_for_item(tcx, generics);
1173 if attr::contains_name(&item.attrs, "rustc_object_lifetime_default") {
1174 let object_lifetime_default_reprs: String = result
1176 .map(|set| match *set {
1177 Set1::Empty => "BaseDefault".to_string(),
1178 Set1::One(Region::Static) => "'static".to_string(),
1179 Set1::One(Region::EarlyBound(i, _, _)) => generics
1187 Set1::One(_) => bug!(),
1188 Set1::Many => "Ambiguous".to_string(),
1190 .collect::<Vec<String>>()
1192 tcx.sess.span_err(item.span, &object_lifetime_default_reprs);
1195 map.insert(item.id, result);
1203 /// Scan the bounds and where-clauses on parameters to extract bounds
1204 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`
1205 /// for each type parameter.
1206 fn object_lifetime_defaults_for_item(
1207 tcx: TyCtxt<'_, '_, '_>,
1208 generics: &hir::Generics,
1209 ) -> Vec<ObjectLifetimeDefault> {
1210 fn add_bounds(set: &mut Set1<hir::LifetimeName>, bounds: &[hir::TyParamBound]) {
1211 for bound in bounds {
1212 if let hir::RegionTyParamBound(ref lifetime) = *bound {
1213 set.insert(lifetime.name);
1221 let mut set = Set1::Empty;
1223 add_bounds(&mut set, ¶m.bounds);
1225 let param_def_id = tcx.hir.local_def_id(param.id);
1226 for predicate in &generics.where_clause.predicates {
1227 // Look for `type: ...` where clauses.
1228 let data = match *predicate {
1229 hir::WherePredicate::BoundPredicate(ref data) => data,
1233 // Ignore `for<'a> type: ...` as they can change what
1234 // lifetimes mean (although we could "just" handle it).
1235 if !data.bound_generic_params.is_empty() {
1239 let def = match data.bounded_ty.node {
1240 hir::TyPath(hir::QPath::Resolved(None, ref path)) => path.def,
1244 if def == Def::TyParam(param_def_id) {
1245 add_bounds(&mut set, &data.bounds);
1250 Set1::Empty => Set1::Empty,
1251 Set1::One(name) => {
1252 if name == hir::LifetimeName::Static {
1253 Set1::One(Region::Static)
1258 .find(|&(_, def)| def.lifetime.name == name)
1259 .map_or(Set1::Many, |(i, def)| {
1260 let def_id = tcx.hir.local_def_id(def.lifetime.id);
1261 let origin = LifetimeDefOrigin::from_is_in_band(def.in_band);
1262 Set1::One(Region::EarlyBound(i as u32, def_id, origin))
1266 Set1::Many => Set1::Many,
1272 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
1273 // FIXME(#37666) this works around a limitation in the region inferencer
1274 fn hack<F>(&mut self, f: F)
1276 F: for<'b> FnOnce(&mut LifetimeContext<'b, 'tcx>),
1281 fn with<F>(&mut self, wrap_scope: Scope, f: F)
1283 F: for<'b> FnOnce(ScopeRef, &mut LifetimeContext<'b, 'tcx>),
1285 let LifetimeContext {
1291 let labels_in_fn = replace(&mut self.labels_in_fn, vec![]);
1292 let xcrate_object_lifetime_defaults =
1293 replace(&mut self.xcrate_object_lifetime_defaults, DefIdMap());
1294 let mut this = LifetimeContext {
1298 trait_ref_hack: self.trait_ref_hack,
1299 is_in_fn_syntax: self.is_in_fn_syntax,
1301 xcrate_object_lifetime_defaults,
1302 lifetime_uses: lifetime_uses,
1304 debug!("entering scope {:?}", this.scope);
1305 f(self.scope, &mut this);
1306 this.check_uses_for_lifetimes_defined_by_scope();
1307 debug!("exiting scope {:?}", this.scope);
1308 self.labels_in_fn = this.labels_in_fn;
1309 self.xcrate_object_lifetime_defaults = this.xcrate_object_lifetime_defaults;
1312 fn check_uses_for_lifetimes_defined_by_scope(&mut self) {
1313 let defined_by = match self.scope {
1314 Scope::Binder { lifetimes, .. } => lifetimes,
1316 debug!("check_uses_for_lifetimes_defined_by_scope: not in a binder scope");
1321 let mut def_ids: Vec<_> = defined_by.values()
1322 .flat_map(|region| match region {
1323 Region::EarlyBound(_, def_id, _)
1324 | Region::LateBound(_, def_id, _)
1325 | Region::Free(_, def_id) => Some(*def_id),
1327 Region::LateBoundAnon(..) | Region::Static => None,
1331 // ensure that we issue lints in a repeatable order
1332 def_ids.sort_by_key(|&def_id| self.tcx.def_path_hash(def_id));
1334 for def_id in def_ids {
1336 "check_uses_for_lifetimes_defined_by_scope: def_id = {:?}",
1340 let lifetimeuseset = self.lifetime_uses.remove(&def_id);
1342 "check_uses_for_lifetimes_defined_by_scope: lifetimeuseset = {:?}",
1345 match lifetimeuseset {
1346 Some(LifetimeUseSet::One(_)) => {
1347 let node_id = self.tcx.hir.as_local_node_id(def_id).unwrap();
1348 debug!("node id first={:?}", node_id);
1349 if let hir::map::NodeLifetime(hir_lifetime) = self.tcx.hir.get(node_id) {
1350 let span = hir_lifetime.span;
1351 let id = hir_lifetime.id;
1353 "id ={:?} span = {:?} hir_lifetime = {:?}",
1354 node_id, span, hir_lifetime
1358 .struct_span_lint_node(
1359 lint::builtin::SINGLE_USE_LIFETIMES,
1363 "lifetime parameter `{}` only used once",
1364 hir_lifetime.name.name()
1370 Some(LifetimeUseSet::Many) => {
1371 debug!("Not one use lifetime");
1374 let node_id = self.tcx.hir.as_local_node_id(def_id).unwrap();
1375 if let hir::map::NodeLifetime(hir_lifetime) = self.tcx.hir.get(node_id) {
1376 let span = hir_lifetime.span;
1377 let id = hir_lifetime.id;
1380 .struct_span_lint_node(
1381 lint::builtin::UNUSED_LIFETIMES,
1385 "lifetime parameter `{}` never used",
1386 hir_lifetime.name.name()
1396 /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
1398 /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
1399 /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
1400 /// within type bounds; those are early bound lifetimes, and the rest are late bound.
1404 /// fn foo<'a,'b,'c,T:Trait<'b>>(...)
1406 /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
1407 /// lifetimes may be interspersed together.
1409 /// If early bound lifetimes are present, we separate them into their own list (and likewise
1410 /// for late bound). They will be numbered sequentially, starting from the lowest index that is
1411 /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
1412 /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
1413 /// ordering is not important there.
1414 fn visit_early_late<F>(
1416 parent_id: Option<ast::NodeId>,
1417 decl: &'tcx hir::FnDecl,
1418 generics: &'tcx hir::Generics,
1421 F: for<'b, 'c> FnOnce(&'b mut LifetimeContext<'c, 'tcx>),
1423 insert_late_bound_lifetimes(self.map, decl, generics);
1425 // Find the start of nested early scopes, e.g. in methods.
1427 if let Some(parent_id) = parent_id {
1428 let parent = self.tcx.hir.expect_item(parent_id);
1429 if let hir::ItemTrait(..) = parent.node {
1430 index += 1; // Self comes first.
1433 hir::ItemTrait(_, _, ref generics, ..)
1434 | hir::ItemImpl(_, _, _, ref generics, ..) => {
1435 index += generics.params.len() as u32;
1441 let lifetimes = generics
1444 if self.map.late_bound.contains(&def.lifetime.id) {
1445 Region::late(&self.tcx.hir, def)
1447 Region::early(&self.tcx.hir, &mut index, def)
1452 let next_early_index = index + generics.ty_params().count() as u32;
1454 let scope = Scope::Binder {
1458 abstract_type_parent: true,
1459 track_lifetime_uses: false,
1461 self.with(scope, move |old_scope, this| {
1462 this.check_lifetime_params(old_scope, &generics.params);
1463 this.hack(walk); // FIXME(#37666) workaround in place of `walk(this)`
1467 fn next_early_index_helper(&self, only_abstract_type_parent: bool) -> u32 {
1468 let mut scope = self.scope;
1471 Scope::Root => return 0,
1475 abstract_type_parent,
1477 } if (!only_abstract_type_parent || abstract_type_parent) =>
1479 return next_early_index
1482 Scope::Binder { s, .. }
1483 | Scope::Body { s, .. }
1484 | Scope::Elision { s, .. }
1485 | Scope::ObjectLifetimeDefault { s, .. } => scope = s,
1490 /// Returns the next index one would use for an early-bound-region
1491 /// if extending the current scope.
1492 fn next_early_index(&self) -> u32 {
1493 self.next_early_index_helper(true)
1496 /// Returns the next index one would use for an `impl Trait` that
1497 /// is being converted into an `abstract type`. This will be the
1498 /// next early index from the enclosing item, for the most
1499 /// part. See the `abstract_type_parent` field for more info.
1500 fn next_early_index_for_abstract_type(&self) -> u32 {
1501 self.next_early_index_helper(false)
1504 fn resolve_lifetime_ref(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
1505 debug!("resolve_lifetime_ref(lifetime_ref={:?})", lifetime_ref);
1506 // Walk up the scope chain, tracking the number of fn scopes
1507 // that we pass through, until we find a lifetime with the
1508 // given name or we run out of scopes.
1510 let mut late_depth = 0;
1511 let mut scope = self.scope;
1512 let mut outermost_body = None;
1515 Scope::Body { id, s } => {
1516 outermost_body = Some(id);
1525 ref lifetimes, s, ..
1527 if let Some(&def) = lifetimes.get(&lifetime_ref.name) {
1528 break Some(def.shifted(late_depth));
1535 Scope::Elision { s, .. } | Scope::ObjectLifetimeDefault { s, .. } => {
1541 if let Some(mut def) = result {
1542 if let Region::EarlyBound(..) = def {
1543 // Do not free early-bound regions, only late-bound ones.
1544 } else if let Some(body_id) = outermost_body {
1545 let fn_id = self.tcx.hir.body_owner(body_id);
1546 match self.tcx.hir.get(fn_id) {
1547 hir::map::NodeItem(&hir::Item {
1548 node: hir::ItemFn(..),
1551 | hir::map::NodeTraitItem(&hir::TraitItem {
1552 node: hir::TraitItemKind::Method(..),
1555 | hir::map::NodeImplItem(&hir::ImplItem {
1556 node: hir::ImplItemKind::Method(..),
1559 let scope = self.tcx.hir.local_def_id(fn_id);
1560 def = Region::Free(scope, def.id().unwrap());
1566 // Check for fn-syntax conflicts with in-band lifetime definitions
1567 if self.is_in_fn_syntax {
1569 Region::EarlyBound(_, _, LifetimeDefOrigin::InBand)
1570 | Region::LateBound(_, _, LifetimeDefOrigin::InBand) => {
1575 "lifetimes used in `fn` or `Fn` syntax must be \
1576 explicitly declared using `<...>` binders"
1577 ).span_label(lifetime_ref.span, "in-band lifetime definition")
1582 | Region::EarlyBound(_, _, LifetimeDefOrigin::Explicit)
1583 | Region::LateBound(_, _, LifetimeDefOrigin::Explicit)
1584 | Region::LateBoundAnon(..)
1585 | Region::Free(..) => {}
1589 self.insert_lifetime(lifetime_ref, def);
1595 "use of undeclared lifetime name `{}`",
1596 lifetime_ref.name.name()
1597 ).span_label(lifetime_ref.span, "undeclared lifetime")
1602 fn visit_segment_parameters(
1606 params: &'tcx hir::PathParameters,
1608 if params.parenthesized {
1609 let was_in_fn_syntax = self.is_in_fn_syntax;
1610 self.is_in_fn_syntax = true;
1611 self.visit_fn_like_elision(params.inputs(), Some(¶ms.bindings[0].ty));
1612 self.is_in_fn_syntax = was_in_fn_syntax;
1616 if params.lifetimes.iter().all(|l| l.is_elided()) {
1617 self.resolve_elided_lifetimes(¶ms.lifetimes, true);
1619 for l in ¶ms.lifetimes {
1620 self.visit_lifetime(l);
1624 // Figure out if this is a type/trait segment,
1625 // which requires object lifetime defaults.
1626 let parent_def_id = |this: &mut Self, def_id: DefId| {
1627 let def_key = this.tcx.def_key(def_id);
1629 krate: def_id.krate,
1630 index: def_key.parent.expect("missing parent"),
1633 let type_def_id = match def {
1634 Def::AssociatedTy(def_id) if depth == 1 => Some(parent_def_id(self, def_id)),
1635 Def::Variant(def_id) if depth == 0 => Some(parent_def_id(self, def_id)),
1637 | Def::Union(def_id)
1639 | Def::TyAlias(def_id)
1640 | Def::Trait(def_id) if depth == 0 =>
1647 let object_lifetime_defaults = type_def_id.map_or(vec![], |def_id| {
1649 let mut scope = self.scope;
1652 Scope::Root => break false,
1654 Scope::Body { .. } => break true,
1656 Scope::Binder { s, .. }
1657 | Scope::Elision { s, .. }
1658 | Scope::ObjectLifetimeDefault { s, .. } => {
1665 let map = &self.map;
1666 let unsubst = if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1667 &map.object_lifetime_defaults[&id]
1670 self.xcrate_object_lifetime_defaults
1672 .or_insert_with(|| {
1673 tcx.generics_of(def_id).params.iter().filter_map(|param| {
1675 GenericParamDefKind::Type { object_lifetime_default, .. } => {
1676 Some(object_lifetime_default)
1678 GenericParamDefKind::Lifetime => None,
1685 .map(|set| match *set {
1686 Set1::Empty => if in_body {
1689 Some(Region::Static)
1691 Set1::One(r) => r.subst(¶ms.lifetimes, map),
1697 for (i, ty) in params.types.iter().enumerate() {
1698 if let Some(<) = object_lifetime_defaults.get(i) {
1699 let scope = Scope::ObjectLifetimeDefault {
1703 self.with(scope, |_, this| this.visit_ty(ty));
1709 for b in ¶ms.bindings {
1710 self.visit_assoc_type_binding(b);
1714 fn visit_fn_like_elision(
1716 inputs: &'tcx [P<hir::Ty>],
1717 output: Option<&'tcx P<hir::Ty>>,
1719 debug!("visit_fn_like_elision: enter");
1720 let mut arg_elide = Elide::FreshLateAnon(Cell::new(0));
1721 let arg_scope = Scope::Elision {
1722 elide: arg_elide.clone(),
1725 self.with(arg_scope, |_, this| {
1726 for input in inputs {
1727 this.visit_ty(input);
1730 Scope::Elision { ref elide, .. } => {
1731 arg_elide = elide.clone();
1737 let output = match output {
1742 debug!("visit_fn_like_elision: determine output");
1744 // Figure out if there's a body we can get argument names from,
1745 // and whether there's a `self` argument (treated specially).
1746 let mut assoc_item_kind = None;
1747 let mut impl_self = None;
1748 let parent = self.tcx.hir.get_parent_node(output.id);
1749 let body = match self.tcx.hir.get(parent) {
1750 // `fn` definitions and methods.
1751 hir::map::NodeItem(&hir::Item {
1752 node: hir::ItemFn(.., body),
1756 hir::map::NodeTraitItem(&hir::TraitItem {
1757 node: hir::TraitItemKind::Method(_, ref m),
1762 .expect_item(self.tcx.hir.get_parent(parent))
1765 hir::ItemTrait(.., ref trait_items) => {
1766 assoc_item_kind = trait_items
1768 .find(|ti| ti.id.node_id == parent)
1774 hir::TraitMethod::Required(_) => None,
1775 hir::TraitMethod::Provided(body) => Some(body),
1779 hir::map::NodeImplItem(&hir::ImplItem {
1780 node: hir::ImplItemKind::Method(_, body),
1785 .expect_item(self.tcx.hir.get_parent(parent))
1788 hir::ItemImpl(.., ref self_ty, ref impl_items) => {
1789 impl_self = Some(self_ty);
1790 assoc_item_kind = impl_items
1792 .find(|ii| ii.id.node_id == parent)
1800 // Foreign functions, `fn(...) -> R` and `Trait(...) -> R` (both types and bounds).
1801 hir::map::NodeForeignItem(_) | hir::map::NodeTy(_) | hir::map::NodeTraitRef(_) => None,
1802 // Everything else (only closures?) doesn't
1803 // actually enjoy elision in return types.
1805 self.visit_ty(output);
1810 let has_self = match assoc_item_kind {
1811 Some(hir::AssociatedItemKind::Method { has_self }) => has_self,
1815 // In accordance with the rules for lifetime elision, we can determine
1816 // what region to use for elision in the output type in two ways.
1817 // First (determined here), if `self` is by-reference, then the
1818 // implied output region is the region of the self parameter.
1820 // Look for `self: &'a Self` - also desugared from `&'a self`,
1821 // and if that matches, use it for elision and return early.
1822 let is_self_ty = |def: Def| {
1823 if let Def::SelfTy(..) = def {
1827 // Can't always rely on literal (or implied) `Self` due
1828 // to the way elision rules were originally specified.
1829 let impl_self = impl_self.map(|ty| &ty.node);
1830 if let Some(&hir::TyPath(hir::QPath::Resolved(None, ref path))) = impl_self {
1832 // Whitelist the types that unambiguously always
1833 // result in the same type constructor being used
1834 // (it can't differ between `Self` and `self`).
1835 Def::Struct(_) | Def::Union(_) | Def::Enum(_) | Def::PrimTy(_) => {
1836 return def == path.def
1845 if let hir::TyRptr(lifetime_ref, ref mt) = inputs[0].node {
1846 if let hir::TyPath(hir::QPath::Resolved(None, ref path)) = mt.ty.node {
1847 if is_self_ty(path.def) {
1848 if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
1849 let scope = Scope::Elision {
1850 elide: Elide::Exact(lifetime),
1853 self.with(scope, |_, this| this.visit_ty(output));
1861 // Second, if there was exactly one lifetime (either a substitution or a
1862 // reference) in the arguments, then any anonymous regions in the output
1863 // have that lifetime.
1864 let mut possible_implied_output_region = None;
1865 let mut lifetime_count = 0;
1866 let arg_lifetimes = inputs
1869 .skip(has_self as usize)
1871 let mut gather = GatherLifetimes {
1873 outer_index: ty::INNERMOST,
1874 have_bound_regions: false,
1875 lifetimes: FxHashSet(),
1877 gather.visit_ty(input);
1879 lifetime_count += gather.lifetimes.len();
1881 if lifetime_count == 1 && gather.lifetimes.len() == 1 {
1882 // there's a chance that the unique lifetime of this
1883 // iteration will be the appropriate lifetime for output
1884 // parameters, so lets store it.
1885 possible_implied_output_region = gather.lifetimes.iter().cloned().next();
1888 ElisionFailureInfo {
1891 lifetime_count: gather.lifetimes.len(),
1892 have_bound_regions: gather.have_bound_regions,
1897 let elide = if lifetime_count == 1 {
1898 Elide::Exact(possible_implied_output_region.unwrap())
1900 Elide::Error(arg_lifetimes)
1903 debug!("visit_fn_like_elision: elide={:?}", elide);
1905 let scope = Scope::Elision {
1909 self.with(scope, |_, this| this.visit_ty(output));
1910 debug!("visit_fn_like_elision: exit");
1912 struct GatherLifetimes<'a> {
1913 map: &'a NamedRegionMap,
1914 outer_index: ty::DebruijnIndex,
1915 have_bound_regions: bool,
1916 lifetimes: FxHashSet<Region>,
1919 impl<'v, 'a> Visitor<'v> for GatherLifetimes<'a> {
1920 fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1921 NestedVisitorMap::None
1924 fn visit_ty(&mut self, ty: &hir::Ty) {
1925 if let hir::TyBareFn(_) = ty.node {
1926 self.outer_index.shift_in(1);
1928 if let hir::TyTraitObject(ref bounds, ref lifetime) = ty.node {
1929 for bound in bounds {
1930 self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
1933 // Stay on the safe side and don't include the object
1934 // lifetime default (which may not end up being used).
1935 if !lifetime.is_elided() {
1936 self.visit_lifetime(lifetime);
1939 intravisit::walk_ty(self, ty);
1941 if let hir::TyBareFn(_) = ty.node {
1942 self.outer_index.shift_out(1);
1946 fn visit_generic_param(&mut self, param: &hir::GenericParam) {
1947 if let hir::GenericParam::Lifetime(_) = *param {
1948 // FIXME(eddyb) Do we want this? It only makes a difference
1949 // if this `for<'a>` lifetime parameter is never used.
1950 self.have_bound_regions = true;
1953 intravisit::walk_generic_param(self, param);
1956 fn visit_poly_trait_ref(
1958 trait_ref: &hir::PolyTraitRef,
1959 modifier: hir::TraitBoundModifier,
1961 self.outer_index.shift_in(1);
1962 intravisit::walk_poly_trait_ref(self, trait_ref, modifier);
1963 self.outer_index.shift_out(1);
1966 fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
1967 if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
1969 Region::LateBound(debruijn, _, _) | Region::LateBoundAnon(debruijn, _)
1970 if debruijn < self.outer_index =>
1972 self.have_bound_regions = true;
1976 .insert(lifetime.shifted_out_to_binder(self.outer_index));
1984 fn resolve_elided_lifetimes(&mut self, lifetime_refs: &'tcx [hir::Lifetime], deprecated: bool) {
1985 if lifetime_refs.is_empty() {
1989 let span = lifetime_refs[0].span;
1990 let id = lifetime_refs[0].id;
1991 let mut late_depth = 0;
1992 let mut scope = self.scope;
1995 .struct_span_lint_node(
1996 lint::builtin::ELIDED_LIFETIMES_IN_PATHS,
1999 &format!("hidden lifetime parameters are deprecated, try `Foo<'_>`"),
2005 // Do not assign any resolution, it will be inferred.
2006 Scope::Body { .. } => return,
2008 Scope::Root => break None,
2010 Scope::Binder { s, .. } => {
2015 Scope::Elision { ref elide, .. } => {
2016 let lifetime = match *elide {
2017 Elide::FreshLateAnon(ref counter) => {
2018 for lifetime_ref in lifetime_refs {
2019 let lifetime = Region::late_anon(counter).shifted(late_depth);
2020 self.insert_lifetime(lifetime_ref, lifetime);
2024 Elide::Exact(l) => l.shifted(late_depth),
2025 Elide::Error(ref e) => break Some(e),
2027 for lifetime_ref in lifetime_refs {
2028 self.insert_lifetime(lifetime_ref, lifetime);
2033 Scope::ObjectLifetimeDefault { s, .. } => {
2039 let mut err = report_missing_lifetime_specifiers(self.tcx.sess, span, lifetime_refs.len());
2041 if let Some(params) = error {
2042 if lifetime_refs.len() == 1 {
2043 self.report_elision_failure(&mut err, params);
2050 fn report_elision_failure(
2052 db: &mut DiagnosticBuilder,
2053 params: &[ElisionFailureInfo],
2055 let mut m = String::new();
2056 let len = params.len();
2058 let elided_params: Vec<_> = params
2061 .filter(|info| info.lifetime_count > 0)
2064 let elided_len = elided_params.len();
2066 for (i, info) in elided_params.into_iter().enumerate() {
2067 let ElisionFailureInfo {
2074 let help_name = if let Some(body) = parent {
2075 let arg = &self.tcx.hir.body(body).arguments[index];
2076 format!("`{}`", self.tcx.hir.node_to_pretty_string(arg.pat.id))
2078 format!("argument {}", index + 1)
2086 "one of {}'s {} {}lifetimes",
2089 if have_bound_regions { "free " } else { "" }
2094 if elided_len == 2 && i == 0 {
2096 } else if i + 2 == elided_len {
2097 m.push_str(", or ");
2098 } else if i != elided_len - 1 {
2106 "this function's return type contains a borrowed value, but \
2107 there is no value for it to be borrowed from"
2109 help!(db, "consider giving it a 'static lifetime");
2110 } else if elided_len == 0 {
2113 "this function's return type contains a borrowed value with \
2114 an elided lifetime, but the lifetime cannot be derived from \
2119 "consider giving it an explicit bounded or 'static \
2122 } else if elided_len == 1 {
2125 "this function's return type contains a borrowed value, but \
2126 the signature does not say which {} it is borrowed from",
2132 "this function's return type contains a borrowed value, but \
2133 the signature does not say whether it is borrowed from {}",
2139 fn resolve_object_lifetime_default(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
2140 let mut late_depth = 0;
2141 let mut scope = self.scope;
2142 let lifetime = loop {
2144 Scope::Binder { s, .. } => {
2149 Scope::Root | Scope::Elision { .. } => break Region::Static,
2151 Scope::Body { .. } | Scope::ObjectLifetimeDefault { lifetime: None, .. } => return,
2153 Scope::ObjectLifetimeDefault {
2154 lifetime: Some(l), ..
2158 self.insert_lifetime(lifetime_ref, lifetime.shifted(late_depth));
2161 fn check_lifetime_params(&mut self, old_scope: ScopeRef, params: &'tcx [hir::GenericParam]) {
2162 for (i, lifetime_i) in params.lifetimes().enumerate() {
2163 match lifetime_i.lifetime.name {
2164 hir::LifetimeName::Static | hir::LifetimeName::Underscore => {
2165 let lifetime = lifetime_i.lifetime;
2166 let name = lifetime.name.name();
2167 let mut err = struct_span_err!(
2171 "invalid lifetime parameter name: `{}`",
2176 format!("{} is a reserved lifetime name", name),
2180 hir::LifetimeName::Fresh(_)
2181 | hir::LifetimeName::Implicit
2182 | hir::LifetimeName::Name(_) => {}
2185 // It is a hard error to shadow a lifetime within the same scope.
2186 for lifetime_j in params.lifetimes().skip(i + 1) {
2187 if lifetime_i.lifetime.name == lifetime_j.lifetime.name {
2190 lifetime_j.lifetime.span,
2192 "lifetime name `{}` declared twice in the same scope",
2193 lifetime_j.lifetime.name.name()
2194 ).span_label(lifetime_j.lifetime.span, "declared twice")
2195 .span_label(lifetime_i.lifetime.span, "previous declaration here")
2200 // It is a soft error to shadow a lifetime within a parent scope.
2201 self.check_lifetime_def_for_shadowing(old_scope, &lifetime_i.lifetime);
2203 for bound in &lifetime_i.bounds {
2205 hir::LifetimeName::Underscore => {
2206 let mut err = struct_span_err!(
2210 "invalid lifetime bound name: `'_`"
2212 err.span_label(bound.span, "`'_` is a reserved lifetime name");
2215 hir::LifetimeName::Static => {
2216 self.insert_lifetime(bound, Region::Static);
2220 lifetime_i.lifetime.span.to(bound.span),
2222 "unnecessary lifetime parameter `{}`",
2223 lifetime_i.lifetime.name.name()
2227 "you can use the `'static` lifetime directly, in place \
2229 lifetime_i.lifetime.name.name()
2233 hir::LifetimeName::Fresh(_)
2234 | hir::LifetimeName::Implicit
2235 | hir::LifetimeName::Name(_) => {
2236 self.resolve_lifetime_ref(bound);
2243 fn check_lifetime_def_for_shadowing(
2245 mut old_scope: ScopeRef,
2246 lifetime: &'tcx hir::Lifetime,
2248 for &(label, label_span) in &self.labels_in_fn {
2249 // FIXME (#24278): non-hygienic comparison
2250 if lifetime.name.name() == label {
2251 signal_shadowing_problem(
2254 original_label(label_span),
2255 shadower_lifetime(&lifetime),
2263 Scope::Body { s, .. }
2264 | Scope::Elision { s, .. }
2265 | Scope::ObjectLifetimeDefault { s, .. } => {
2274 ref lifetimes, s, ..
2276 if let Some(&def) = lifetimes.get(&lifetime.name) {
2277 let node_id = self.tcx.hir.as_local_node_id(def.id().unwrap()).unwrap();
2279 signal_shadowing_problem(
2281 lifetime.name.name(),
2282 original_lifetime(self.tcx.hir.span(node_id)),
2283 shadower_lifetime(&lifetime),
2294 /// Returns true if, in the current scope, replacing `'_` would be
2295 /// equivalent to a single-use lifetime.
2296 fn track_lifetime_uses(&self) -> bool {
2297 let mut scope = self.scope;
2300 Scope::Root => break false,
2302 // Inside of items, it depends on the kind of item.
2304 track_lifetime_uses,
2306 } => break track_lifetime_uses,
2308 // Inside a body, `'_` will use an inference variable,
2310 Scope::Body { .. } => break true,
2312 // A lifetime only used in a fn argument could as well
2313 // be replaced with `'_`, as that would generate a
2316 elide: Elide::FreshLateAnon(_),
2320 // In the return type or other such place, `'_` is not
2321 // going to make a fresh name, so we cannot
2322 // necessarily replace a single-use lifetime with
2325 elide: Elide::Exact(_),
2329 elide: Elide::Error(_),
2333 Scope::ObjectLifetimeDefault { s, .. } => scope = s,
2338 fn insert_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime, def: Region) {
2339 if lifetime_ref.id == ast::DUMMY_NODE_ID {
2342 "lifetime reference not renumbered, \
2343 probably a bug in syntax::fold"
2348 "insert_lifetime: {} resolved to {:?} span={:?}",
2349 self.tcx.hir.node_to_string(lifetime_ref.id),
2351 self.tcx.sess.codemap().span_to_string(lifetime_ref.span)
2353 self.map.defs.insert(lifetime_ref.id, def);
2356 Region::LateBoundAnon(..) | Region::Static => {
2357 // These are anonymous lifetimes or lifetimes that are not declared.
2360 Region::Free(_, def_id)
2361 | Region::LateBound(_, def_id, _)
2362 | Region::EarlyBound(_, def_id, _) => {
2363 // A lifetime declared by the user.
2364 let track_lifetime_uses = self.track_lifetime_uses();
2366 "insert_lifetime: track_lifetime_uses={}",
2369 if track_lifetime_uses && !self.lifetime_uses.contains_key(&def_id) {
2370 debug!("insert_lifetime: first use of {:?}", def_id);
2372 .insert(def_id, LifetimeUseSet::One(lifetime_ref));
2374 debug!("insert_lifetime: many uses of {:?}", def_id);
2375 self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
2382 ///////////////////////////////////////////////////////////////////////////
2384 /// Detects late-bound lifetimes and inserts them into
2385 /// `map.late_bound`.
2387 /// A region declared on a fn is **late-bound** if:
2388 /// - it is constrained by an argument type;
2389 /// - it does not appear in a where-clause.
2391 /// "Constrained" basically means that it appears in any type but
2392 /// not amongst the inputs to a projection. In other words, `<&'a
2393 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
2394 fn insert_late_bound_lifetimes(
2395 map: &mut NamedRegionMap,
2397 generics: &hir::Generics,
2400 "insert_late_bound_lifetimes(decl={:?}, generics={:?})",
2404 let mut constrained_by_input = ConstrainedCollector {
2405 regions: FxHashSet(),
2407 for arg_ty in &decl.inputs {
2408 constrained_by_input.visit_ty(arg_ty);
2411 let mut appears_in_output = AllCollector {
2412 regions: FxHashSet(),
2414 intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
2417 "insert_late_bound_lifetimes: constrained_by_input={:?}",
2418 constrained_by_input.regions
2421 // Walk the lifetimes that appear in where clauses.
2423 // Subtle point: because we disallow nested bindings, we can just
2424 // ignore binders here and scrape up all names we see.
2425 let mut appears_in_where_clause = AllCollector {
2426 regions: FxHashSet(),
2428 appears_in_where_clause.visit_generics(generics);
2430 for param in &generics.params {
2432 hir::GenericParam::Lifetime(ref lifetime_def) => {
2433 if !lifetime_def.bounds.is_empty() {
2434 // `'a: 'b` means both `'a` and `'b` are referenced
2435 appears_in_where_clause.regions.insert(lifetime_def.lifetime.name);
2438 hir::GenericParam::Type(_) => {}
2443 "insert_late_bound_lifetimes: appears_in_where_clause={:?}",
2444 appears_in_where_clause.regions
2447 // Late bound regions are those that:
2448 // - appear in the inputs
2449 // - do not appear in the where-clauses
2450 // - are not implicitly captured by `impl Trait`
2451 for lifetime in generics.lifetimes() {
2452 let name = lifetime.lifetime.name;
2454 // appears in the where clauses? early-bound.
2455 if appears_in_where_clause.regions.contains(&name) {
2459 // does not appear in the inputs, but appears in the return type? early-bound.
2460 if !constrained_by_input.regions.contains(&name)
2461 && appears_in_output.regions.contains(&name)
2467 "insert_late_bound_lifetimes: \
2468 lifetime {:?} with id {:?} is late-bound",
2469 lifetime.lifetime.name, lifetime.lifetime.id
2472 let inserted = map.late_bound.insert(lifetime.lifetime.id);
2475 "visited lifetime {:?} twice",
2476 lifetime.lifetime.id
2482 struct ConstrainedCollector {
2483 regions: FxHashSet<hir::LifetimeName>,
2486 impl<'v> Visitor<'v> for ConstrainedCollector {
2487 fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2488 NestedVisitorMap::None
2491 fn visit_ty(&mut self, ty: &'v hir::Ty) {
2493 hir::TyPath(hir::QPath::Resolved(Some(_), _))
2494 | hir::TyPath(hir::QPath::TypeRelative(..)) => {
2495 // ignore lifetimes appearing in associated type
2496 // projections, as they are not *constrained*
2500 hir::TyPath(hir::QPath::Resolved(None, ref path)) => {
2501 // consider only the lifetimes on the final
2502 // segment; I am not sure it's even currently
2503 // valid to have them elsewhere, but even if it
2504 // is, those would be potentially inputs to
2506 if let Some(last_segment) = path.segments.last() {
2507 self.visit_path_segment(path.span, last_segment);
2512 intravisit::walk_ty(self, ty);
2517 fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
2518 self.regions.insert(lifetime_ref.name);
2522 struct AllCollector {
2523 regions: FxHashSet<hir::LifetimeName>,
2526 impl<'v> Visitor<'v> for AllCollector {
2527 fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2528 NestedVisitorMap::None
2531 fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
2532 self.regions.insert(lifetime_ref.name);
2537 pub fn report_missing_lifetime_specifiers(
2541 ) -> DiagnosticBuilder<'_> {
2542 let mut err = struct_span_err!(
2546 "missing lifetime specifier{}",
2547 if count > 1 { "s" } else { "" }
2550 let msg = if count > 1 {
2551 format!("expected {} lifetime parameters", count)
2553 format!("expected lifetime parameter")
2556 err.span_label(span, msg);