src/librustc/middle/resolve_lifetime.rs

   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 use hir::def::Def;
  19 use hir::def_id::{CrateNum, DefId, LocalDefId, LOCAL_CRATE};
  20 use hir::map::Map;
  21 use hir::{GenericArg, GenericParam, ItemLocalId, LifetimeName, ParamName, Node};
  22 use ty::{self, TyCtxt, GenericParamDefKind};
  23
  24 use errors::DiagnosticBuilder;
  25 use rustc::lint;
  26 use rustc_data_structures::sync::Lrc;
  27 use session::Session;
  28 use std::cell::Cell;
  29 use std::mem::replace;
  30 use syntax::ast;
  31 use syntax::attr;
  32 use syntax::ptr::P;
  33 use syntax::symbol::keywords;
  34 use syntax_pos::Span;
  35 use util::nodemap::{DefIdMap, FxHashMap, FxHashSet, NodeMap, NodeSet};
  36
  37 use hir::intravisit::{self, NestedVisitorMap, Visitor};
  38 use hir::{self, GenericParamKind};
  39
  40 /// The origin of a named lifetime definition.
  41 ///
  42 /// This is used to prevent the usage of in-band lifetimes in `Fn`/`fn` syntax.
  43 #[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
  44 pub enum LifetimeDefOrigin {
  45     // Explicit binders like `fn foo<'a>(x: &'a u8)`
  46     Explicit,
  47     // In-band declarations like `fn foo(x: &'a u8)`
  48     InBand,
  49 }
  50
  51 impl LifetimeDefOrigin {
  52     fn from_param(param: &GenericParam) -> Self {
  53         match param.kind {
  54             GenericParamKind::Lifetime { in_band } => {
  55                 if in_band {
  56                     LifetimeDefOrigin::InBand
  57                 } else {
  58                     LifetimeDefOrigin::Explicit
  59                 }
  60             }
  61             _ => bug!("expected a lifetime param"),
  62         }
  63     }
  64 }
  65
  66 // This counts the no of times a lifetime is used
  67 #[derive(Clone, Copy, Debug)]
  68 pub enum LifetimeUseSet<'tcx> {
  69     One(&'tcx hir::Lifetime),
  70     Many,
  71 }
  72
  73 #[derive(Clone, Copy, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
  74 pub enum Region {
  75     Static,
  76     EarlyBound(
  77         /* index */ u32,
  78         /* lifetime decl */ DefId,
  79         LifetimeDefOrigin,
  80     ),
  81     LateBound(
  82         ty::DebruijnIndex,
  83         /* lifetime decl */ DefId,
  84         LifetimeDefOrigin,
  85     ),
  86     LateBoundAnon(ty::DebruijnIndex, /* anon index */ u32),
  87     Free(DefId, /* lifetime decl */ DefId),
  88 }
  89
  90 impl Region {
  91     fn early(hir_map: &Map, index: &mut u32, param: &GenericParam) -> (ParamName, Region) {
  92         let i = *index;
  93         *index += 1;
  94         let def_id = hir_map.local_def_id(param.id);
  95         let origin = LifetimeDefOrigin::from_param(param);
  96         debug!("Region::early: index={} def_id={:?}", i, def_id);
  97         (param.name.modern(), Region::EarlyBound(i, def_id, origin))
  98     }
  99
 100     fn late(hir_map: &Map, param: &GenericParam) -> (ParamName, Region) {
 101         let depth = ty::INNERMOST;
 102         let def_id = hir_map.local_def_id(param.id);
 103         let origin = LifetimeDefOrigin::from_param(param);
 104         debug!(
 105             "Region::late: param={:?} depth={:?} def_id={:?} origin={:?}",
 106             param,
 107             depth,
 108             def_id,
 109             origin,
 110         );
 111         (param.name.modern(), Region::LateBound(depth, def_id, origin))
 112     }
 113
 114     fn late_anon(index: &Cell<u32>) -> Region {
 115         let i = index.get();
 116         index.set(i + 1);
 117         let depth = ty::INNERMOST;
 118         Region::LateBoundAnon(depth, i)
 119     }
 120
 121     fn id(&self) -> Option<DefId> {
 122         match *self {
 123             Region::Static | Region::LateBoundAnon(..) => None,
 124
 125             Region::EarlyBound(_, id, _) | Region::LateBound(_, id, _) | Region::Free(_, id) => {
 126                 Some(id)
 127             }
 128         }
 129     }
 130
 131     fn shifted(self, amount: u32) -> Region {
 132         match self {
 133             Region::LateBound(debruijn, id, origin) => {
 134                 Region::LateBound(debruijn.shifted_in(amount), id, origin)
 135             }
 136             Region::LateBoundAnon(debruijn, index) => {
 137                 Region::LateBoundAnon(debruijn.shifted_in(amount), index)
 138             }
 139             _ => self,
 140         }
 141     }
 142
 143     fn shifted_out_to_binder(self, binder: ty::DebruijnIndex) -> Region {
 144         match self {
 145             Region::LateBound(debruijn, id, origin) => Region::LateBound(
 146                 debruijn.shifted_out_to_binder(binder),
 147                 id,
 148                 origin,
 149             ),
 150             Region::LateBoundAnon(debruijn, index) => Region::LateBoundAnon(
 151                 debruijn.shifted_out_to_binder(binder),
 152                 index,
 153             ),
 154             _ => self,
 155         }
 156     }
 157
 158     fn subst<'a, L>(self, mut params: L, map: &NamedRegionMap) -> Option<Region>
 159             where L: Iterator<Item = &'a hir::Lifetime>  {
 160         if let Region::EarlyBound(index, _, _) = self {
 161             params.nth(index as usize).and_then(|lifetime| map.defs.get(&lifetime.id).cloned())
 162         } else {
 163             Some(self)
 164         }
 165     }
 166 }
 167
 168 /// A set containing, at most, one known element.
 169 /// If two distinct values are inserted into a set, then it
 170 /// becomes `Many`, which can be used to detect ambiguities.
 171 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
 172 pub enum Set1<T> {
 173     Empty,
 174     One(T),
 175     Many,
 176 }
 177
 178 impl<T: PartialEq> Set1<T> {
 179     pub fn insert(&mut self, value: T) {
 180         if let Set1::Empty = *self {
 181             *self = Set1::One(value);
 182             return;
 183         }
 184         if let Set1::One(ref old) = *self {
 185             if *old == value {
 186                 return;
 187             }
 188         }
 189         *self = Set1::Many;
 190     }
 191 }
 192
 193 pub type ObjectLifetimeDefault = Set1<Region>;
 194
 195 /// Maps the id of each lifetime reference to the lifetime decl
 196 /// that it corresponds to.
 197 ///
 198 /// FIXME. This struct gets converted to a `ResolveLifetimes` for
 199 /// actual use. It has the same data, but indexed by `DefIndex`.  This
 200 /// is silly.
 201 #[derive(Default)]
 202 struct NamedRegionMap {
 203     // maps from every use of a named (not anonymous) lifetime to a
 204     // `Region` describing how that region is bound
 205     pub defs: NodeMap<Region>,
 206
 207     // the set of lifetime def ids that are late-bound; a region can
 208     // be late-bound if (a) it does NOT appear in a where-clause and
 209     // (b) it DOES appear in the arguments.
 210     pub late_bound: NodeSet,
 211
 212     // For each type and trait definition, maps type parameters
 213     // to the trait object lifetime defaults computed from them.
 214     pub object_lifetime_defaults: NodeMap<Vec<ObjectLifetimeDefault>>,
 215 }
 216
 217 /// See `NamedRegionMap`.
 218 pub struct ResolveLifetimes {
 219     defs: FxHashMap<LocalDefId, Lrc<FxHashMap<ItemLocalId, Region>>>,
 220     late_bound: FxHashMap<LocalDefId, Lrc<FxHashSet<ItemLocalId>>>,
 221     object_lifetime_defaults:
 222         FxHashMap<LocalDefId, Lrc<FxHashMap<ItemLocalId, Lrc<Vec<ObjectLifetimeDefault>>>>>,
 223 }
 224
 225 impl_stable_hash_for!(struct ::middle::resolve_lifetime::ResolveLifetimes {
 226     defs,
 227     late_bound,
 228     object_lifetime_defaults
 229 });
 230
 231 struct LifetimeContext<'a, 'tcx: 'a> {
 232     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 233     map: &'a mut NamedRegionMap,
 234     scope: ScopeRef<'a>,
 235
 236     /// Deep breath. Our representation for poly trait refs contains a single
 237     /// binder and thus we only allow a single level of quantification. However,
 238     /// the syntax of Rust permits quantification in two places, e.g., `T: for <'a> Foo<'a>`
 239     /// and `for <'a, 'b> &'b T: Foo<'a>`. In order to get the de Bruijn indices
 240     /// correct when representing these constraints, we should only introduce one
 241     /// scope. However, we want to support both locations for the quantifier and
 242     /// during lifetime resolution we want precise information (so we can't
 243     /// desugar in an earlier phase).
 244     ///
 245     /// SO, if we encounter a quantifier at the outer scope, we set
 246     /// trait_ref_hack to true (and introduce a scope), and then if we encounter
 247     /// a quantifier at the inner scope, we error. If trait_ref_hack is false,
 248     /// then we introduce the scope at the inner quantifier.
 249     ///
 250     /// I'm sorry.
 251     trait_ref_hack: bool,
 252
 253     /// Used to disallow the use of in-band lifetimes in `fn` or `Fn` syntax.
 254     is_in_fn_syntax: bool,
 255
 256     /// List of labels in the function/method currently under analysis.
 257     labels_in_fn: Vec<ast::Ident>,
 258
 259     /// Cache for cross-crate per-definition object lifetime defaults.
 260     xcrate_object_lifetime_defaults: DefIdMap<Vec<ObjectLifetimeDefault>>,
 261
 262     lifetime_uses: &'a mut DefIdMap<LifetimeUseSet<'tcx>>,
 263 }
 264
 265 #[derive(Debug)]
 266 enum Scope<'a> {
 267     /// Declares lifetimes, and each can be early-bound or late-bound.
 268     /// The `DebruijnIndex` of late-bound lifetimes starts at `1` and
 269     /// it should be shifted by the number of `Binder`s in between the
 270     /// declaration `Binder` and the location it's referenced from.
 271     Binder {
 272         lifetimes: FxHashMap<hir::ParamName, Region>,
 273
 274         /// if we extend this scope with another scope, what is the next index
 275         /// we should use for an early-bound region?
 276         next_early_index: u32,
 277
 278         /// Flag is set to true if, in this binder, `'_` would be
 279         /// equivalent to a "single-use region". This is true on
 280         /// impls, but not other kinds of items.
 281         track_lifetime_uses: bool,
 282
 283         /// Whether or not this binder would serve as the parent
 284         /// binder for abstract types introduced within. For example:
 285         ///
 286         ///     fn foo<'a>() -> impl for<'b> Trait<Item = impl Trait2<'a>>
 287         ///
 288         /// Here, the abstract types we create for the `impl Trait`
 289         /// and `impl Trait2` references will both have the `foo` item
 290         /// as their parent. When we get to `impl Trait2`, we find
 291         /// that it is nested within the `for<>` binder -- this flag
 292         /// allows us to skip that when looking for the parent binder
 293         /// of the resulting abstract type.
 294         abstract_type_parent: bool,
 295
 296         s: ScopeRef<'a>,
 297     },
 298
 299     /// Lifetimes introduced by a fn are scoped to the call-site for that fn,
 300     /// if this is a fn body, otherwise the original definitions are used.
 301     /// Unspecified lifetimes are inferred, unless an elision scope is nested,
 302     /// e.g. `(&T, fn(&T) -> &T);` becomes `(&'_ T, for<'a> fn(&'a T) -> &'a T)`.
 303     Body {
 304         id: hir::BodyId,
 305         s: ScopeRef<'a>,
 306     },
 307
 308     /// A scope which either determines unspecified lifetimes or errors
 309     /// on them (e.g. due to ambiguity). For more details, see `Elide`.
 310     Elision {
 311         elide: Elide,
 312         s: ScopeRef<'a>,
 313     },
 314
 315     /// Use a specific lifetime (if `Some`) or leave it unset (to be
 316     /// inferred in a function body or potentially error outside one),
 317     /// for the default choice of lifetime in a trait object type.
 318     ObjectLifetimeDefault {
 319         lifetime: Option<Region>,
 320         s: ScopeRef<'a>,
 321     },
 322
 323     Root,
 324 }
 325
 326 #[derive(Clone, Debug)]
 327 enum Elide {
 328     /// Use a fresh anonymous late-bound lifetime each time, by
 329     /// incrementing the counter to generate sequential indices.
 330     FreshLateAnon(Cell<u32>),
 331     /// Always use this one lifetime.
 332     Exact(Region),
 333     /// Less or more than one lifetime were found, error on unspecified.
 334     Error(Vec<ElisionFailureInfo>),
 335 }
 336
 337 #[derive(Clone, Debug)]
 338 struct ElisionFailureInfo {
 339     /// Where we can find the argument pattern.
 340     parent: Option<hir::BodyId>,
 341     /// The index of the argument in the original definition.
 342     index: usize,
 343     lifetime_count: usize,
 344     have_bound_regions: bool,
 345 }
 346
 347 type ScopeRef<'a> = &'a Scope<'a>;
 348
 349 const ROOT_SCOPE: ScopeRef<'static> = &Scope::Root;
 350
 351 pub fn provide(providers: &mut ty::query::Providers) {
 352     *providers = ty::query::Providers {
 353         resolve_lifetimes,
 354
 355         named_region_map: |tcx, id| {
 356             let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
 357             tcx.resolve_lifetimes(LOCAL_CRATE).defs.get(&id).cloned()
 358         },
 359
 360         is_late_bound_map: |tcx, id| {
 361             let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
 362             tcx.resolve_lifetimes(LOCAL_CRATE)
 363                 .late_bound
 364                 .get(&id)
 365                 .cloned()
 366         },
 367
 368         object_lifetime_defaults_map: |tcx, id| {
 369             let id = LocalDefId::from_def_id(DefId::local(id)); // (*)
 370             tcx.resolve_lifetimes(LOCAL_CRATE)
 371                 .object_lifetime_defaults
 372                 .get(&id)
 373                 .cloned()
 374         },
 375
 376         ..*providers
 377     };
 378
 379     // (*) FIXME the query should be defined to take a LocalDefId
 380 }
 381
 382 /// Computes the `ResolveLifetimes` map that contains data for the
 383 /// entire crate. You should not read the result of this query
 384 /// directly, but rather use `named_region_map`, `is_late_bound_map`,
 385 /// etc.
 386 fn resolve_lifetimes<'tcx>(
 387     tcx: TyCtxt<'_, 'tcx, 'tcx>,
 388     for_krate: CrateNum,
 389 ) -> Lrc<ResolveLifetimes> {
 390     assert_eq!(for_krate, LOCAL_CRATE);
 391
 392     let named_region_map = krate(tcx);
 393
 394     let mut rl = ResolveLifetimes {
 395         defs: FxHashMap(),
 396         late_bound: FxHashMap(),
 397         object_lifetime_defaults: FxHashMap(),
 398     };
 399
 400     for (k, v) in named_region_map.defs {
 401         let hir_id = tcx.hir.node_to_hir_id(k);
 402         let map = rl.defs.entry(hir_id.owner_local_def_id()).or_default();
 403         Lrc::get_mut(map).unwrap().insert(hir_id.local_id, v);
 404     }
 405     for k in named_region_map.late_bound {
 406         let hir_id = tcx.hir.node_to_hir_id(k);
 407         let map = rl.late_bound.entry(hir_id.owner_local_def_id()).or_default();
 408         Lrc::get_mut(map).unwrap().insert(hir_id.local_id);
 409     }
 410     for (k, v) in named_region_map.object_lifetime_defaults {
 411         let hir_id = tcx.hir.node_to_hir_id(k);
 412         let map = rl.object_lifetime_defaults
 413             .entry(hir_id.owner_local_def_id())
 414             .or_default();
 415         Lrc::get_mut(map)
 416             .unwrap()
 417             .insert(hir_id.local_id, Lrc::new(v));
 418     }
 419
 420     Lrc::new(rl)
 421 }
 422
 423 fn krate<'tcx>(tcx: TyCtxt<'_, 'tcx, 'tcx>) -> NamedRegionMap {
 424     let krate = tcx.hir.krate();
 425     let mut map = NamedRegionMap {
 426         defs: NodeMap(),
 427         late_bound: NodeSet(),
 428         object_lifetime_defaults: compute_object_lifetime_defaults(tcx),
 429     };
 430     {
 431         let mut visitor = LifetimeContext {
 432             tcx,
 433             map: &mut map,
 434             scope: ROOT_SCOPE,
 435             trait_ref_hack: false,
 436             is_in_fn_syntax: false,
 437             labels_in_fn: vec![],
 438             xcrate_object_lifetime_defaults: DefIdMap(),
 439             lifetime_uses: &mut DefIdMap(),
 440         };
 441         for (_, item) in &krate.items {
 442             visitor.visit_item(item);
 443         }
 444     }
 445     map
 446 }
 447
 448 impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
 449     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 450         NestedVisitorMap::All(&self.tcx.hir)
 451     }
 452
 453     // We want to nest trait/impl items in their parent, but nothing else.
 454     fn visit_nested_item(&mut self, _: hir::ItemId) {}
 455
 456     fn visit_nested_body(&mut self, body: hir::BodyId) {
 457         // Each body has their own set of labels, save labels.
 458         let saved = replace(&mut self.labels_in_fn, vec![]);
 459         let body = self.tcx.hir.body(body);
 460         extract_labels(self, body);
 461         self.with(
 462             Scope::Body {
 463                 id: body.id(),
 464                 s: self.scope,
 465             },
 466             |_, this| {
 467                 this.visit_body(body);
 468             },
 469         );
 470         replace(&mut self.labels_in_fn, saved);
 471     }
 472
 473     fn visit_item(&mut self, item: &'tcx hir::Item) {
 474         match item.node {
 475             hir::ItemKind::Fn(ref decl, _, ref generics, _) => {
 476                 self.visit_early_late(None, decl, generics, |this| {
 477                     intravisit::walk_item(this, item);
 478                 });
 479             }
 480
 481             hir::ItemKind::ExternCrate(_)
 482             | hir::ItemKind::Use(..)
 483             | hir::ItemKind::Mod(..)
 484             | hir::ItemKind::ForeignMod(..)
 485             | hir::ItemKind::GlobalAsm(..) => {
 486                 // These sorts of items have no lifetime parameters at all.
 487                 intravisit::walk_item(self, item);
 488             }
 489             hir::ItemKind::Static(..) | hir::ItemKind::Const(..) => {
 490                 // No lifetime parameters, but implied 'static.
 491                 let scope = Scope::Elision {
 492                     elide: Elide::Exact(Region::Static),
 493                     s: ROOT_SCOPE,
 494                 };
 495                 self.with(scope, |_, this| intravisit::walk_item(this, item));
 496             }
 497             hir::ItemKind::Existential(hir::ExistTy { impl_trait_fn: Some(_), .. }) => {
 498                 // currently existential type declarations are just generated from impl Trait
 499                 // items. doing anything on this node is irrelevant, as we currently don't need
 500                 // it.
 501             }
 502             hir::ItemKind::Ty(_, ref generics)
 503             | hir::ItemKind::Existential(hir::ExistTy { impl_trait_fn: None, ref generics, .. })
 504             | hir::ItemKind::Enum(_, ref generics)
 505             | hir::ItemKind::Struct(_, ref generics)
 506             | hir::ItemKind::Union(_, ref generics)
 507             | hir::ItemKind::Trait(_, _, ref generics, ..)
 508             | hir::ItemKind::TraitAlias(ref generics, ..)
 509             | hir::ItemKind::Impl(_, _, _, ref generics, ..) => {
 510                 // Impls permit `'_` to be used and it is equivalent to "some fresh lifetime name".
 511                 // This is not true for other kinds of items.x
 512                 let track_lifetime_uses = match item.node {
 513                     hir::ItemKind::Impl(..) => true,
 514                     _ => false,
 515                 };
 516                 // These kinds of items have only early bound lifetime parameters.
 517                 let mut index = if let hir::ItemKind::Trait(..) = item.node {
 518                     1 // Self comes before lifetimes
 519                 } else {
 520                     0
 521                 };
 522                 let mut type_count = 0;
 523                 let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
 524                     GenericParamKind::Lifetime { .. } => {
 525                         Some(Region::early(&self.tcx.hir, &mut index, param))
 526                     }
 527                     GenericParamKind::Type { .. } => {
 528                         type_count += 1;
 529                         None
 530                     }
 531                 }).collect();
 532                 let scope = Scope::Binder {
 533                     lifetimes,
 534                     next_early_index: index + type_count,
 535                     abstract_type_parent: true,
 536                     track_lifetime_uses,
 537                     s: ROOT_SCOPE,
 538                 };
 539                 self.with(scope, |old_scope, this| {
 540                     this.check_lifetime_params(old_scope, &generics.params);
 541                     intravisit::walk_item(this, item);
 542                 });
 543             }
 544         }
 545     }
 546
 547     fn visit_foreign_item(&mut self, item: &'tcx hir::ForeignItem) {
 548         match item.node {
 549             hir::ForeignItemKind::Fn(ref decl, _, ref generics) => {
 550                 self.visit_early_late(None, decl, generics, |this| {
 551                     intravisit::walk_foreign_item(this, item);
 552                 })
 553             }
 554             hir::ForeignItemKind::Static(..) => {
 555                 intravisit::walk_foreign_item(self, item);
 556             }
 557             hir::ForeignItemKind::Type => {
 558                 intravisit::walk_foreign_item(self, item);
 559             }
 560         }
 561     }
 562
 563     fn visit_ty(&mut self, ty: &'tcx hir::Ty) {
 564         debug!("visit_ty: id={:?} ty={:?}", ty.id, ty);
 565         match ty.node {
 566             hir::TyKind::BareFn(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.iter().filter_map(|param| match param.kind {
 572                         GenericParamKind::Lifetime { .. } => {
 573                             Some(Region::late(&self.tcx.hir, param))
 574                         }
 575                         _ => None,
 576                     }).collect(),
 577                     s: self.scope,
 578                     next_early_index,
 579                     track_lifetime_uses: true,
 580                     abstract_type_parent: false,
 581                 };
 582                 self.with(scope, |old_scope, this| {
 583                     // a bare fn has no bounds, so everything
 584                     // contained within is scoped within its binder.
 585                     this.check_lifetime_params(old_scope, &c.generic_params);
 586                     intravisit::walk_ty(this, ty);
 587                 });
 588                 self.is_in_fn_syntax = was_in_fn_syntax;
 589             }
 590             hir::TyKind::TraitObject(ref bounds, ref lifetime) => {
 591                 for bound in bounds {
 592                     self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
 593                 }
 594                 match lifetime.name {
 595                     LifetimeName::Implicit => {
 596                         // If the user does not write *anything*, we
 597                         // use the object lifetime defaulting
 598                         // rules. So e.g. `Box<dyn Debug>` becomes
 599                         // `Box<dyn Debug + 'static>`.
 600                         self.resolve_object_lifetime_default(lifetime)
 601                     }
 602                     LifetimeName::Underscore => {
 603                         // If the user writes `'_`, we use the *ordinary* elision
 604                         // rules. So the `'_` in e.g. `Box<dyn Debug + '_>` will be
 605                         // resolved the same as the `'_` in `&'_ Foo`.
 606                         //
 607                         // cc #48468
 608                         self.resolve_elided_lifetimes(vec![lifetime])
 609                     }
 610                     LifetimeName::Param(_) | LifetimeName::Static => {
 611                         // If the user wrote an explicit name, use that.
 612                         self.visit_lifetime(lifetime);
 613                     }
 614                 }
 615             }
 616             hir::TyKind::Rptr(ref lifetime_ref, ref mt) => {
 617                 self.visit_lifetime(lifetime_ref);
 618                 let scope = Scope::ObjectLifetimeDefault {
 619                     lifetime: self.map.defs.get(&lifetime_ref.id).cloned(),
 620                     s: self.scope,
 621                 };
 622                 self.with(scope, |_, this| this.visit_ty(&mt.ty));
 623             }
 624             hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
 625                 if let Def::Existential(exist_ty_did) = path.def {
 626                     let id = self.tcx.hir.as_local_node_id(exist_ty_did).unwrap();
 627
 628                     // Resolve the lifetimes in the bounds to the lifetime defs in the generics.
 629                     // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 630                     // `abstract type MyAnonTy<'b>: MyTrait<'b>;`
 631                     //                          ^            ^ this gets resolved in the scope of
 632                     //                                         the exist_ty generics
 633                     let (generics, bounds) = match self.tcx.hir.expect_item(id).node {
 634                         // named existential types don't need these hacks
 635                         hir::ItemKind::Existential(hir::ExistTy{ impl_trait_fn: None, .. }) => {
 636                             intravisit::walk_ty(self, ty);
 637                             return;
 638                         },
 639                         hir::ItemKind::Existential(hir::ExistTy{
 640                             ref generics,
 641                             ref bounds,
 642                             ..
 643                         }) => (
 644                             generics,
 645                             bounds,
 646                         ),
 647                         ref i => bug!("impl Trait pointed to non-existential type?? {:#?}", i),
 648                     };
 649
 650                     assert!(exist_ty_did.is_local());
 651                     // Resolve the lifetimes that are applied to the existential type.
 652                     // These are resolved in the current scope.
 653                     // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 654                     // `fn foo<'a>() -> MyAnonTy<'a> { ... }`
 655                     //          ^                 ^this gets resolved in the current scope
 656                     for lifetime in &path.segments[0].args.as_ref().unwrap().args {
 657                         if let hir::GenericArg::Lifetime(lifetime) = lifetime {
 658                             self.visit_lifetime(lifetime);
 659
 660                             // Check for predicates like `impl for<'a> Trait<impl OtherTrait<'a>>`
 661                             // and ban them. Type variables instantiated inside binders aren't
 662                             // well-supported at the moment, so this doesn't work.
 663                             // In the future, this should be fixed and this error should be removed.
 664                             let def = self.map.defs.get(&lifetime.id).cloned();
 665                             if let Some(Region::LateBound(_, def_id, _)) = def {
 666                                 if let Some(node_id) = self.tcx.hir.as_local_node_id(def_id) {
 667                                     // Ensure that the parent of the def is an item, not HRTB
 668                                     let parent_id = self.tcx.hir.get_parent_node(node_id);
 669                                     let parent_impl_id = hir::ImplItemId { node_id: parent_id };
 670                                     let parent_trait_id = hir::TraitItemId { node_id: parent_id };
 671                                     let krate = self.tcx.hir.forest.krate();
 672                                     if !(krate.items.contains_key(&parent_id)
 673                                         || krate.impl_items.contains_key(&parent_impl_id)
 674                                         || krate.trait_items.contains_key(&parent_trait_id))
 675                                     {
 676                                         span_err!(
 677                                             self.tcx.sess,
 678                                             lifetime.span,
 679                                             E0657,
 680                                             "`impl Trait` can only capture lifetimes \
 681                                             bound at the fn or impl level"
 682                                         );
 683                                         self.uninsert_lifetime_on_error(lifetime, def.unwrap());
 684                                     }
 685                                 }
 686                             }
 687                         }
 688                     }
 689
 690                     // We want to start our early-bound indices at the end of the parent scope,
 691                     // not including any parent `impl Trait`s.
 692                     let mut index = self.next_early_index_for_abstract_type();
 693                     debug!("visit_ty: index = {}", index);
 694
 695                     let mut elision = None;
 696                     let mut lifetimes = FxHashMap();
 697                     let mut type_count = 0;
 698                     for param in &generics.params {
 699                         match param.kind {
 700                             GenericParamKind::Lifetime { .. } => {
 701                                 let (name, reg) = Region::early(&self.tcx.hir, &mut index, &param);
 702                                 if let hir::ParamName::Plain(param_name) = name {
 703                                     if param_name.name == keywords::UnderscoreLifetime.name() {
 704                                         // Pick the elided lifetime "definition" if one exists
 705                                         // and use it to make an elision scope.
 706                                         elision = Some(reg);
 707                                     } else {
 708                                         lifetimes.insert(name, reg);
 709                                     }
 710                                 } else {
 711                                     lifetimes.insert(name, reg);
 712                                 }
 713                             }
 714                             GenericParamKind::Type { .. } => {
 715                                 type_count += 1;
 716                             }
 717                         }
 718                     }
 719                     let next_early_index = index + type_count;
 720
 721                     if let Some(elision_region) = elision {
 722                         let scope = Scope::Elision {
 723                             elide: Elide::Exact(elision_region),
 724                             s: self.scope,
 725                         };
 726                         self.with(scope, |_old_scope, this| {
 727                             let scope = Scope::Binder {
 728                                 lifetimes,
 729                                 next_early_index,
 730                                 s: this.scope,
 731                                 track_lifetime_uses: true,
 732                                 abstract_type_parent: false,
 733                             };
 734                             this.with(scope, |_old_scope, this| {
 735                                 this.visit_generics(generics);
 736                                 for bound in bounds {
 737                                     this.visit_param_bound(bound);
 738                                 }
 739                             });
 740                         });
 741                     } else {
 742                         let scope = Scope::Binder {
 743                             lifetimes,
 744                             next_early_index,
 745                             s: self.scope,
 746                             track_lifetime_uses: true,
 747                             abstract_type_parent: false,
 748                         };
 749                         self.with(scope, |_old_scope, this| {
 750                             this.visit_generics(generics);
 751                             for bound in bounds {
 752                                 this.visit_param_bound(bound);
 753                             }
 754                         });
 755                     }
 756                 } else {
 757                     intravisit::walk_ty(self, ty)
 758                 }
 759             }
 760             _ => intravisit::walk_ty(self, ty),
 761         }
 762     }
 763
 764     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 765         use self::hir::TraitItemKind::*;
 766         match trait_item.node {
 767             Method(ref sig, _) => {
 768                 let tcx = self.tcx;
 769                 self.visit_early_late(
 770                     Some(tcx.hir.get_parent(trait_item.id)),
 771                     &sig.decl,
 772                     &trait_item.generics,
 773                     |this| intravisit::walk_trait_item(this, trait_item),
 774                 );
 775             }
 776             Type(ref bounds, ref ty) => {
 777                 let generics = &trait_item.generics;
 778                 let mut index = self.next_early_index();
 779                 debug!("visit_ty: index = {}", index);
 780                 let mut type_count = 0;
 781                 let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
 782                     GenericParamKind::Lifetime { .. } => {
 783                         Some(Region::early(&self.tcx.hir, &mut index, param))
 784                     }
 785                     GenericParamKind::Type { .. } => {
 786                         type_count += 1;
 787                         None
 788                     }
 789                 }).collect();
 790                 let scope = Scope::Binder {
 791                     lifetimes,
 792                     next_early_index: index + type_count,
 793                     s: self.scope,
 794                     track_lifetime_uses: true,
 795                     abstract_type_parent: true,
 796                 };
 797                 self.with(scope, |_old_scope, this| {
 798                     this.visit_generics(generics);
 799                     for bound in bounds {
 800                         this.visit_param_bound(bound);
 801                     }
 802                     if let Some(ty) = ty {
 803                         this.visit_ty(ty);
 804                     }
 805                 });
 806             }
 807             Const(_, _) => {
 808                 // Only methods and types support generics.
 809                 assert!(trait_item.generics.params.is_empty());
 810                 intravisit::walk_trait_item(self, trait_item);
 811             }
 812         }
 813     }
 814
 815     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 816         use self::hir::ImplItemKind::*;
 817         match impl_item.node {
 818             Method(ref sig, _) => {
 819                 let tcx = self.tcx;
 820                 self.visit_early_late(
 821                     Some(tcx.hir.get_parent(impl_item.id)),
 822                     &sig.decl,
 823                     &impl_item.generics,
 824                     |this| intravisit::walk_impl_item(this, impl_item),
 825                 )
 826             }
 827             Type(ref ty) => {
 828                 let generics = &impl_item.generics;
 829                 let mut index = self.next_early_index();
 830                 let mut next_early_index = index;
 831                 debug!("visit_ty: index = {}", index);
 832                 let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
 833                     GenericParamKind::Lifetime { .. } => {
 834                         Some(Region::early(&self.tcx.hir, &mut index, param))
 835                     }
 836                     GenericParamKind::Type { .. } => {
 837                         next_early_index += 1;
 838                         None
 839                     }
 840                 }).collect();
 841                 let scope = Scope::Binder {
 842                     lifetimes,
 843                     next_early_index,
 844                     s: self.scope,
 845                     track_lifetime_uses: true,
 846                     abstract_type_parent: true,
 847                 };
 848                 self.with(scope, |_old_scope, this| {
 849                     this.visit_generics(generics);
 850                     this.visit_ty(ty);
 851                 });
 852             }
 853             Existential(ref bounds) => {
 854                 let generics = &impl_item.generics;
 855                 let mut index = self.next_early_index();
 856                 let mut next_early_index = index;
 857                 debug!("visit_ty: index = {}", index);
 858                 let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
 859                     GenericParamKind::Lifetime { .. } => {
 860                         Some(Region::early(&self.tcx.hir, &mut index, param))
 861                     }
 862                     GenericParamKind::Type { .. } => {
 863                         next_early_index += 1;
 864                         None
 865                     }
 866                 }).collect();
 867
 868                 let scope = Scope::Binder {
 869                     lifetimes,
 870                     next_early_index,
 871                     s: self.scope,
 872                     track_lifetime_uses: true,
 873                     abstract_type_parent: true,
 874                 };
 875                 self.with(scope, |_old_scope, this| {
 876                     this.visit_generics(generics);
 877                     for bound in bounds {
 878                         this.visit_param_bound(bound);
 879                     }
 880                 });
 881             }
 882             Const(_, _) => {
 883                 // Only methods and types support generics.
 884                 assert!(impl_item.generics.params.is_empty());
 885                 intravisit::walk_impl_item(self, impl_item);
 886             }
 887         }
 888     }
 889
 890     fn visit_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
 891         if lifetime_ref.is_elided() {
 892             self.resolve_elided_lifetimes(vec![lifetime_ref]);
 893             return;
 894         }
 895         if lifetime_ref.is_static() {
 896             self.insert_lifetime(lifetime_ref, Region::Static);
 897             return;
 898         }
 899         self.resolve_lifetime_ref(lifetime_ref);
 900     }
 901
 902     fn visit_path(&mut self, path: &'tcx hir::Path, _: hir::HirId) {
 903         for (i, segment) in path.segments.iter().enumerate() {
 904             let depth = path.segments.len() - i - 1;
 905             if let Some(ref args) = segment.args {
 906                 self.visit_segment_args(path.def, depth, args);
 907             }
 908         }
 909     }
 910
 911     fn visit_fn_decl(&mut self, fd: &'tcx hir::FnDecl) {
 912         let output = match fd.output {
 913             hir::DefaultReturn(_) => None,
 914             hir::Return(ref ty) => Some(ty),
 915         };
 916         self.visit_fn_like_elision(&fd.inputs, output);
 917     }
 918
 919     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
 920         check_mixed_explicit_and_in_band_defs(self.tcx, &generics.params);
 921         for param in &generics.params {
 922             match param.kind {
 923                 GenericParamKind::Lifetime { .. } => {}
 924                 GenericParamKind::Type { ref default, .. } => {
 925                     walk_list!(self, visit_param_bound, &param.bounds);
 926                     if let Some(ref ty) = default {
 927                         self.visit_ty(&ty);
 928                     }
 929                 }
 930             }
 931         }
 932         for predicate in &generics.where_clause.predicates {
 933             match predicate {
 934                 &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate {
 935                     ref bounded_ty,
 936                     ref bounds,
 937                     ref bound_generic_params,
 938                     ..
 939                 }) => {
 940                     let lifetimes: FxHashMap<_, _> = bound_generic_params.iter()
 941                         .filter_map(|param| match param.kind {
 942                             GenericParamKind::Lifetime { .. } => {
 943                                 Some(Region::late(&self.tcx.hir, param))
 944                             }
 945                             _ => None,
 946                         }).collect();
 947                     if !lifetimes.is_empty() {
 948                         self.trait_ref_hack = true;
 949                         let next_early_index = self.next_early_index();
 950                         let scope = Scope::Binder {
 951                             lifetimes,
 952                             s: self.scope,
 953                             next_early_index,
 954                             track_lifetime_uses: true,
 955                             abstract_type_parent: false,
 956                         };
 957                         let result = self.with(scope, |old_scope, this| {
 958                             this.check_lifetime_params(old_scope, &bound_generic_params);
 959                             this.visit_ty(&bounded_ty);
 960                             walk_list!(this, visit_param_bound, bounds);
 961                         });
 962                         self.trait_ref_hack = false;
 963                         result
 964                     } else {
 965                         self.visit_ty(&bounded_ty);
 966                         walk_list!(self, visit_param_bound, bounds);
 967                     }
 968                 }
 969                 &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate {
 970                     ref lifetime,
 971                     ref bounds,
 972                     ..
 973                 }) => {
 974                     self.visit_lifetime(lifetime);
 975                     walk_list!(self, visit_param_bound, bounds);
 976                 }
 977                 &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate {
 978                     ref lhs_ty,
 979                     ref rhs_ty,
 980                     ..
 981                 }) => {
 982                     self.visit_ty(lhs_ty);
 983                     self.visit_ty(rhs_ty);
 984                 }
 985             }
 986         }
 987     }
 988
 989     fn visit_poly_trait_ref(
 990         &mut self,
 991         trait_ref: &'tcx hir::PolyTraitRef,
 992         _modifier: hir::TraitBoundModifier,
 993     ) {
 994         debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
 995
 996         if !self.trait_ref_hack
 997             || trait_ref
 998                 .bound_generic_params
 999                 .iter()
1000                 .any(|param| match param.kind {
1001                     GenericParamKind::Lifetime { .. } => true,
1002                     _ => false,
1003                 })
1004         {
1005             if self.trait_ref_hack {
1006                 span_err!(
1007                     self.tcx.sess,
1008                     trait_ref.span,
1009                     E0316,
1010                     "nested quantification of lifetimes"
1011                 );
1012             }
1013             let next_early_index = self.next_early_index();
1014             let scope = Scope::Binder {
1015                 lifetimes: trait_ref.bound_generic_params.iter()
1016                     .filter_map(|param| match param.kind {
1017                         GenericParamKind::Lifetime { .. } => {
1018                             Some(Region::late(&self.tcx.hir, param))
1019                         }
1020                         _ => None,
1021                     }).collect(),
1022                 s: self.scope,
1023                 next_early_index,
1024                 track_lifetime_uses: true,
1025                 abstract_type_parent: false,
1026             };
1027             self.with(scope, |old_scope, this| {
1028                 this.check_lifetime_params(old_scope, &trait_ref.bound_generic_params);
1029                 walk_list!(this, visit_generic_param, &trait_ref.bound_generic_params);
1030                 this.visit_trait_ref(&trait_ref.trait_ref)
1031             })
1032         } else {
1033             self.visit_trait_ref(&trait_ref.trait_ref)
1034         }
1035     }
1036 }
1037
1038 #[derive(Copy, Clone, PartialEq)]
1039 enum ShadowKind {
1040     Label,
1041     Lifetime,
1042 }
1043 struct Original {
1044     kind: ShadowKind,
1045     span: Span,
1046 }
1047 struct Shadower {
1048     kind: ShadowKind,
1049     span: Span,
1050 }
1051
1052 fn original_label(span: Span) -> Original {
1053     Original {
1054         kind: ShadowKind::Label,
1055         span: span,
1056     }
1057 }
1058 fn shadower_label(span: Span) -> Shadower {
1059     Shadower {
1060         kind: ShadowKind::Label,
1061         span: span,
1062     }
1063 }
1064 fn original_lifetime(span: Span) -> Original {
1065     Original {
1066         kind: ShadowKind::Lifetime,
1067         span: span,
1068     }
1069 }
1070 fn shadower_lifetime(param: &hir::GenericParam) -> Shadower {
1071     Shadower {
1072         kind: ShadowKind::Lifetime,
1073         span: param.span,
1074     }
1075 }
1076
1077 impl ShadowKind {
1078     fn desc(&self) -> &'static str {
1079         match *self {
1080             ShadowKind::Label => "label",
1081             ShadowKind::Lifetime => "lifetime",
1082         }
1083     }
1084 }
1085
1086 fn check_mixed_explicit_and_in_band_defs(
1087     tcx: TyCtxt<'_, '_, '_>,
1088     params: &P<[hir::GenericParam]>,
1089 ) {
1090     let in_bands: Vec<_> = params.iter().filter_map(|param| match param.kind {
1091         GenericParamKind::Lifetime { in_band, .. } => Some((in_band, param.span)),
1092         _ => None,
1093     }).collect();
1094     let out_of_band = in_bands.iter().find(|(in_band, _)| !in_band);
1095     let in_band = in_bands.iter().find(|(in_band, _)| *in_band);
1096
1097     if let (Some((_, out_of_band_span)), Some((_, in_band_span)))
1098         = (out_of_band, in_band) {
1099         struct_span_err!(
1100             tcx.sess,
1101             *in_band_span,
1102             E0688,
1103             "cannot mix in-band and explicit lifetime definitions"
1104         ).span_label(
1105             *in_band_span,
1106             "in-band lifetime definition here",
1107         ).span_label(*out_of_band_span, "explicit lifetime definition here")
1108         .emit();
1109     }
1110 }
1111
1112 fn signal_shadowing_problem(
1113     tcx: TyCtxt<'_, '_, '_>,
1114     name: ast::Name,
1115     orig: Original,
1116     shadower: Shadower,
1117 ) {
1118     let mut err = if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
1119         // lifetime/lifetime shadowing is an error
1120         struct_span_err!(
1121             tcx.sess,
1122             shadower.span,
1123             E0496,
1124             "{} name `{}` shadows a \
1125              {} name that is already in scope",
1126             shadower.kind.desc(),
1127             name,
1128             orig.kind.desc()
1129         )
1130     } else {
1131         // shadowing involving a label is only a warning, due to issues with
1132         // labels and lifetimes not being macro-hygienic.
1133         tcx.sess.struct_span_warn(
1134             shadower.span,
1135             &format!(
1136                 "{} name `{}` shadows a \
1137                  {} name that is already in scope",
1138                 shadower.kind.desc(),
1139                 name,
1140                 orig.kind.desc()
1141             ),
1142         )
1143     };
1144     err.span_label(orig.span, "first declared here");
1145     err.span_label(shadower.span, format!("lifetime {} already in scope", name));
1146     err.emit();
1147 }
1148
1149 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
1150 // if one of the label shadows a lifetime or another label.
1151 fn extract_labels(ctxt: &mut LifetimeContext<'_, '_>, body: &hir::Body) {
1152     struct GatherLabels<'a, 'tcx: 'a> {
1153         tcx: TyCtxt<'a, 'tcx, 'tcx>,
1154         scope: ScopeRef<'a>,
1155         labels_in_fn: &'a mut Vec<ast::Ident>,
1156     }
1157
1158     let mut gather = GatherLabels {
1159         tcx: ctxt.tcx,
1160         scope: ctxt.scope,
1161         labels_in_fn: &mut ctxt.labels_in_fn,
1162     };
1163     gather.visit_body(body);
1164
1165     impl<'v, 'a, 'tcx> Visitor<'v> for GatherLabels<'a, 'tcx> {
1166         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1167             NestedVisitorMap::None
1168         }
1169
1170         fn visit_expr(&mut self, ex: &hir::Expr) {
1171             if let Some(label) = expression_label(ex) {
1172                 for prior_label in &self.labels_in_fn[..] {
1173                     // FIXME (#24278): non-hygienic comparison
1174                     if label.name == prior_label.name {
1175                         signal_shadowing_problem(
1176                             self.tcx,
1177                             label.name,
1178                             original_label(prior_label.span),
1179                             shadower_label(label.span),
1180                         );
1181                     }
1182                 }
1183
1184                 check_if_label_shadows_lifetime(self.tcx, self.scope, label);
1185
1186                 self.labels_in_fn.push(label);
1187             }
1188             intravisit::walk_expr(self, ex)
1189         }
1190     }
1191
1192     fn expression_label(ex: &hir::Expr) -> Option<ast::Ident> {
1193         match ex.node {
1194             hir::ExprKind::While(.., Some(label)) |
1195             hir::ExprKind::Loop(_, Some(label), _) => Some(label.ident),
1196             _ => None,
1197         }
1198     }
1199
1200     fn check_if_label_shadows_lifetime(
1201         tcx: TyCtxt<'_, '_, '_>,
1202         mut scope: ScopeRef<'_>,
1203         label: ast::Ident,
1204     ) {
1205         loop {
1206             match *scope {
1207                 Scope::Body { s, .. }
1208                 | Scope::Elision { s, .. }
1209                 | Scope::ObjectLifetimeDefault { s, .. } => {
1210                     scope = s;
1211                 }
1212
1213                 Scope::Root => {
1214                     return;
1215                 }
1216
1217                 Scope::Binder {
1218                     ref lifetimes, s, ..
1219                 } => {
1220                     // FIXME (#24278): non-hygienic comparison
1221                     if let Some(def) = lifetimes.get(&hir::ParamName::Plain(label.modern())) {
1222                         let node_id = tcx.hir.as_local_node_id(def.id().unwrap()).unwrap();
1223
1224                         signal_shadowing_problem(
1225                             tcx,
1226                             label.name,
1227                             original_lifetime(tcx.hir.span(node_id)),
1228                             shadower_label(label.span),
1229                         );
1230                         return;
1231                     }
1232                     scope = s;
1233                 }
1234             }
1235         }
1236     }
1237 }
1238
1239 fn compute_object_lifetime_defaults(
1240     tcx: TyCtxt<'_, '_, '_>,
1241 ) -> NodeMap<Vec<ObjectLifetimeDefault>> {
1242     let mut map = NodeMap();
1243     for item in tcx.hir.krate().items.values() {
1244         match item.node {
1245             hir::ItemKind::Struct(_, ref generics)
1246             | hir::ItemKind::Union(_, ref generics)
1247             | hir::ItemKind::Enum(_, ref generics)
1248             | hir::ItemKind::Existential(hir::ExistTy { ref generics, impl_trait_fn: None, .. })
1249             | hir::ItemKind::Ty(_, ref generics)
1250             | hir::ItemKind::Trait(_, _, ref generics, ..) => {
1251                 let result = object_lifetime_defaults_for_item(tcx, generics);
1252
1253                 // Debugging aid.
1254                 if attr::contains_name(&item.attrs, "rustc_object_lifetime_default") {
1255                     let object_lifetime_default_reprs: String = result
1256                         .iter()
1257                         .map(|set| match *set {
1258                             Set1::Empty => "BaseDefault".to_string(),
1259                             Set1::One(Region::Static) => "'static".to_string(),
1260                             Set1::One(Region::EarlyBound(mut i, _, _)) => {
1261                                 generics.params.iter().find_map(|param| match param.kind {
1262                                         GenericParamKind::Lifetime { .. } => {
1263                                             if i == 0 {
1264                                                 return Some(param.name.ident().to_string());
1265                                             }
1266                                             i -= 1;
1267                                             None
1268                                         }
1269                                         _ => None,
1270                                     }).unwrap()
1271                             }
1272                             Set1::One(_) => bug!(),
1273                             Set1::Many => "Ambiguous".to_string(),
1274                         })
1275                         .collect::<Vec<String>>()
1276                         .join(",");
1277                     tcx.sess.span_err(item.span, &object_lifetime_default_reprs);
1278                 }
1279
1280                 map.insert(item.id, result);
1281             }
1282             _ => {}
1283         }
1284     }
1285     map
1286 }
1287
1288 /// Scan the bounds and where-clauses on parameters to extract bounds
1289 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`
1290 /// for each type parameter.
1291 fn object_lifetime_defaults_for_item(
1292     tcx: TyCtxt<'_, '_, '_>,
1293     generics: &hir::Generics,
1294 ) -> Vec<ObjectLifetimeDefault> {
1295     fn add_bounds(set: &mut Set1<hir::LifetimeName>, bounds: &[hir::GenericBound]) {
1296         for bound in bounds {
1297             if let hir::GenericBound::Outlives(ref lifetime) = *bound {
1298                 set.insert(lifetime.name.modern());
1299             }
1300         }
1301     }
1302
1303     generics.params.iter().filter_map(|param| match param.kind {
1304         GenericParamKind::Lifetime { .. } => None,
1305         GenericParamKind::Type { .. } => {
1306             let mut set = Set1::Empty;
1307
1308             add_bounds(&mut set, &param.bounds);
1309
1310             let param_def_id = tcx.hir.local_def_id(param.id);
1311             for predicate in &generics.where_clause.predicates {
1312                 // Look for `type: ...` where clauses.
1313                 let data = match *predicate {
1314                     hir::WherePredicate::BoundPredicate(ref data) => data,
1315                     _ => continue,
1316                 };
1317
1318                 // Ignore `for<'a> type: ...` as they can change what
1319                 // lifetimes mean (although we could "just" handle it).
1320                 if !data.bound_generic_params.is_empty() {
1321                     continue;
1322                 }
1323
1324                 let def = match data.bounded_ty.node {
1325                     hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => path.def,
1326                     _ => continue,
1327                 };
1328
1329                 if def == Def::TyParam(param_def_id) {
1330                     add_bounds(&mut set, &data.bounds);
1331                 }
1332             }
1333
1334             Some(match set {
1335                 Set1::Empty => Set1::Empty,
1336                 Set1::One(name) => {
1337                     if name == hir::LifetimeName::Static {
1338                         Set1::One(Region::Static)
1339                     } else {
1340                         generics.params.iter().filter_map(|param| match param.kind {
1341                             GenericParamKind::Lifetime { .. } => {
1342                                 Some((
1343                                     param.id,
1344                                     hir::LifetimeName::Param(param.name),
1345                                     LifetimeDefOrigin::from_param(param),
1346                                 ))
1347                             }
1348                             _ => None,
1349                         })
1350                         .enumerate()
1351                         .find(|&(_, (_, lt_name, _))| lt_name == name)
1352                         .map_or(Set1::Many, |(i, (id, _, origin))| {
1353                             let def_id = tcx.hir.local_def_id(id);
1354                             Set1::One(Region::EarlyBound(i as u32, def_id, origin))
1355                         })
1356                     }
1357                 }
1358                 Set1::Many => Set1::Many,
1359             })
1360         }
1361     })
1362     .collect()
1363 }
1364
1365 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
1366     // FIXME(#37666) this works around a limitation in the region inferencer
1367     fn hack<F>(&mut self, f: F)
1368     where
1369         F: for<'b> FnOnce(&mut LifetimeContext<'b, 'tcx>),
1370     {
1371         f(self)
1372     }
1373
1374     fn with<F>(&mut self, wrap_scope: Scope, f: F)
1375     where
1376         F: for<'b> FnOnce(ScopeRef, &mut LifetimeContext<'b, 'tcx>),
1377     {
1378         let LifetimeContext {
1379             tcx,
1380             map,
1381             lifetime_uses,
1382             ..
1383         } = self;
1384         let labels_in_fn = replace(&mut self.labels_in_fn, vec![]);
1385         let xcrate_object_lifetime_defaults =
1386             replace(&mut self.xcrate_object_lifetime_defaults, DefIdMap());
1387         let mut this = LifetimeContext {
1388             tcx: *tcx,
1389             map: map,
1390             scope: &wrap_scope,
1391             trait_ref_hack: self.trait_ref_hack,
1392             is_in_fn_syntax: self.is_in_fn_syntax,
1393             labels_in_fn,
1394             xcrate_object_lifetime_defaults,
1395             lifetime_uses: lifetime_uses,
1396         };
1397         debug!("entering scope {:?}", this.scope);
1398         f(self.scope, &mut this);
1399         this.check_uses_for_lifetimes_defined_by_scope();
1400         debug!("exiting scope {:?}", this.scope);
1401         self.labels_in_fn = this.labels_in_fn;
1402         self.xcrate_object_lifetime_defaults = this.xcrate_object_lifetime_defaults;
1403     }
1404
1405     fn check_uses_for_lifetimes_defined_by_scope(&mut self) {
1406         let defined_by = match self.scope {
1407             Scope::Binder { lifetimes, .. } => lifetimes,
1408             _ => {
1409                 debug!("check_uses_for_lifetimes_defined_by_scope: not in a binder scope");
1410                 return;
1411             }
1412         };
1413
1414         let mut def_ids: Vec<_> = defined_by.values()
1415             .flat_map(|region| match region {
1416                 Region::EarlyBound(_, def_id, _)
1417                 | Region::LateBound(_, def_id, _)
1418                 | Region::Free(_, def_id) => Some(*def_id),
1419
1420                 Region::LateBoundAnon(..) | Region::Static => None,
1421             })
1422             .collect();
1423
1424         // ensure that we issue lints in a repeatable order
1425         def_ids.sort_by_key(|&def_id| self.tcx.def_path_hash(def_id));
1426
1427         for def_id in def_ids {
1428             debug!(
1429                 "check_uses_for_lifetimes_defined_by_scope: def_id = {:?}",
1430                 def_id,
1431             );
1432
1433             let lifetimeuseset = self.lifetime_uses.remove(&def_id);
1434             debug!(
1435                 "check_uses_for_lifetimes_defined_by_scope: lifetimeuseset = {:?}",
1436                 lifetimeuseset
1437             );
1438             match lifetimeuseset {
1439                 Some(LifetimeUseSet::One(lifetime)) => {
1440                     let node_id = self.tcx.hir.as_local_node_id(def_id).unwrap();
1441                     debug!("node id first={:?}", node_id);
1442                     if let Some((id, span, name)) = match self.tcx.hir.get(node_id) {
1443                         Node::Lifetime(hir_lifetime) => {
1444                             Some((hir_lifetime.id, hir_lifetime.span, hir_lifetime.name.ident()))
1445                         }
1446                         Node::GenericParam(param) => {
1447                             Some((param.id, param.span, param.name.ident()))
1448                         }
1449                         _ => None,
1450                     } {
1451                         debug!("id = {:?} span = {:?} name = {:?}", node_id, span, name);
1452                         let mut err = self.tcx.struct_span_lint_node(
1453                             lint::builtin::SINGLE_USE_LIFETIMES,
1454                             id,
1455                             span,
1456                             &format!("lifetime parameter `{}` only used once", name),
1457                         );
1458                         err.span_label(span, "this lifetime...");
1459                         err.span_label(lifetime.span, "...is used only here");
1460                         err.emit();
1461                     }
1462                 }
1463                 Some(LifetimeUseSet::Many) => {
1464                     debug!("Not one use lifetime");
1465                 }
1466                 None => {
1467                     let node_id = self.tcx.hir.as_local_node_id(def_id).unwrap();
1468                     if let Some((id, span, name)) = match self.tcx.hir.get(node_id) {
1469                         Node::Lifetime(hir_lifetime) => {
1470                             Some((hir_lifetime.id, hir_lifetime.span, hir_lifetime.name.ident()))
1471                         }
1472                         Node::GenericParam(param) => {
1473                             Some((param.id, param.span, param.name.ident()))
1474                         }
1475                         _ => None,
1476                     } {
1477                         debug!("id ={:?} span = {:?} name = {:?}", node_id, span, name);
1478                         self.tcx.struct_span_lint_node(
1479                             lint::builtin::UNUSED_LIFETIMES,
1480                             id,
1481                             span,
1482                             &format!("lifetime parameter `{}` never used", name)
1483                         ).emit();
1484                     }
1485                 }
1486             }
1487         }
1488     }
1489
1490     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
1491     ///
1492     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
1493     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
1494     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
1495     ///
1496     /// For example:
1497     ///
1498     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
1499     ///
1500     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
1501     /// lifetimes may be interspersed together.
1502     ///
1503     /// If early bound lifetimes are present, we separate them into their own list (and likewise
1504     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
1505     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
1506     /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
1507     /// ordering is not important there.
1508     fn visit_early_late<F>(
1509         &mut self,
1510         parent_id: Option<ast::NodeId>,
1511         decl: &'tcx hir::FnDecl,
1512         generics: &'tcx hir::Generics,
1513         walk: F,
1514     ) where
1515         F: for<'b, 'c> FnOnce(&'b mut LifetimeContext<'c, 'tcx>),
1516     {
1517         insert_late_bound_lifetimes(self.map, decl, generics);
1518
1519         // Find the start of nested early scopes, e.g. in methods.
1520         let mut index = 0;
1521         if let Some(parent_id) = parent_id {
1522             let parent = self.tcx.hir.expect_item(parent_id);
1523             if let hir::ItemKind::Trait(..) = parent.node {
1524                 index += 1; // Self comes first.
1525             }
1526             match parent.node {
1527                 hir::ItemKind::Trait(_, _, ref generics, ..)
1528                 | hir::ItemKind::Impl(_, _, _, ref generics, ..) => {
1529                     index += generics.params.len() as u32;
1530                 }
1531                 _ => {}
1532             }
1533         }
1534
1535         let mut type_count = 0;
1536         let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
1537             GenericParamKind::Lifetime { .. } => {
1538                 if self.map.late_bound.contains(&param.id) {
1539                     Some(Region::late(&self.tcx.hir, param))
1540                 } else {
1541                     Some(Region::early(&self.tcx.hir, &mut index, param))
1542                 }
1543             }
1544             GenericParamKind::Type { .. } => {
1545                 type_count += 1;
1546                 None
1547             }
1548         }).collect();
1549         let next_early_index = index + type_count;
1550
1551         let scope = Scope::Binder {
1552             lifetimes,
1553             next_early_index,
1554             s: self.scope,
1555             abstract_type_parent: true,
1556             track_lifetime_uses: false,
1557         };
1558         self.with(scope, move |old_scope, this| {
1559             this.check_lifetime_params(old_scope, &generics.params);
1560             this.hack(walk); // FIXME(#37666) workaround in place of `walk(this)`
1561         });
1562     }
1563
1564     fn next_early_index_helper(&self, only_abstract_type_parent: bool) -> u32 {
1565         let mut scope = self.scope;
1566         loop {
1567             match *scope {
1568                 Scope::Root => return 0,
1569
1570                 Scope::Binder {
1571                     next_early_index,
1572                     abstract_type_parent,
1573                     ..
1574                 } if (!only_abstract_type_parent || abstract_type_parent) =>
1575                 {
1576                     return next_early_index
1577                 }
1578
1579                 Scope::Binder { s, .. }
1580                 | Scope::Body { s, .. }
1581                 | Scope::Elision { s, .. }
1582                 | Scope::ObjectLifetimeDefault { s, .. } => scope = s,
1583             }
1584         }
1585     }
1586
1587     /// Returns the next index one would use for an early-bound-region
1588     /// if extending the current scope.
1589     fn next_early_index(&self) -> u32 {
1590         self.next_early_index_helper(true)
1591     }
1592
1593     /// Returns the next index one would use for an `impl Trait` that
1594     /// is being converted into an `abstract type`. This will be the
1595     /// next early index from the enclosing item, for the most
1596     /// part. See the `abstract_type_parent` field for more info.
1597     fn next_early_index_for_abstract_type(&self) -> u32 {
1598         self.next_early_index_helper(false)
1599     }
1600
1601     fn resolve_lifetime_ref(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
1602         debug!("resolve_lifetime_ref(lifetime_ref={:?})", lifetime_ref);
1603         // Walk up the scope chain, tracking the number of fn scopes
1604         // that we pass through, until we find a lifetime with the
1605         // given name or we run out of scopes.
1606         // search.
1607         let mut late_depth = 0;
1608         let mut scope = self.scope;
1609         let mut outermost_body = None;
1610         let result = loop {
1611             match *scope {
1612                 Scope::Body { id, s } => {
1613                     outermost_body = Some(id);
1614                     scope = s;
1615                 }
1616
1617                 Scope::Root => {
1618                     break None;
1619                 }
1620
1621                 Scope::Binder { ref lifetimes, s, .. } => {
1622                     let name = match lifetime_ref.name {
1623                         LifetimeName::Param(param_name) => param_name,
1624                         _ => bug!("expected LifetimeName::Param"),
1625                     };
1626                     if let Some(&def) = lifetimes.get(&name.modern()) {
1627                         break Some(def.shifted(late_depth));
1628                     } else {
1629                         late_depth += 1;
1630                         scope = s;
1631                     }
1632                 }
1633
1634                 Scope::Elision { s, .. } | Scope::ObjectLifetimeDefault { s, .. } => {
1635                     scope = s;
1636                 }
1637             }
1638         };
1639
1640         if let Some(mut def) = result {
1641             if let Region::EarlyBound(..) = def {
1642                 // Do not free early-bound regions, only late-bound ones.
1643             } else if let Some(body_id) = outermost_body {
1644                 let fn_id = self.tcx.hir.body_owner(body_id);
1645                 match self.tcx.hir.get(fn_id) {
1646                     Node::Item(&hir::Item {
1647                         node: hir::ItemKind::Fn(..),
1648                         ..
1649                     })
1650                     | Node::TraitItem(&hir::TraitItem {
1651                         node: hir::TraitItemKind::Method(..),
1652                         ..
1653                     })
1654                     | Node::ImplItem(&hir::ImplItem {
1655                         node: hir::ImplItemKind::Method(..),
1656                         ..
1657                     }) => {
1658                         let scope = self.tcx.hir.local_def_id(fn_id);
1659                         def = Region::Free(scope, def.id().unwrap());
1660                     }
1661                     _ => {}
1662                 }
1663             }
1664
1665             // Check for fn-syntax conflicts with in-band lifetime definitions
1666             if self.is_in_fn_syntax {
1667                 match def {
1668                     Region::EarlyBound(_, _, LifetimeDefOrigin::InBand)
1669                     | Region::LateBound(_, _, LifetimeDefOrigin::InBand) => {
1670                         struct_span_err!(
1671                             self.tcx.sess,
1672                             lifetime_ref.span,
1673                             E0687,
1674                             "lifetimes used in `fn` or `Fn` syntax must be \
1675                              explicitly declared using `<...>` binders"
1676                         ).span_label(lifetime_ref.span, "in-band lifetime definition")
1677                             .emit();
1678                     }
1679
1680                     Region::Static
1681                     | Region::EarlyBound(_, _, LifetimeDefOrigin::Explicit)
1682                     | Region::LateBound(_, _, LifetimeDefOrigin::Explicit)
1683                     | Region::LateBoundAnon(..)
1684                     | Region::Free(..) => {}
1685                 }
1686             }
1687
1688             self.insert_lifetime(lifetime_ref, def);
1689         } else {
1690             struct_span_err!(
1691                 self.tcx.sess,
1692                 lifetime_ref.span,
1693                 E0261,
1694                 "use of undeclared lifetime name `{}`",
1695                 lifetime_ref
1696             ).span_label(lifetime_ref.span, "undeclared lifetime")
1697                 .emit();
1698         }
1699     }
1700
1701     fn visit_segment_args(
1702         &mut self,
1703         def: Def,
1704         depth: usize,
1705         generic_args: &'tcx hir::GenericArgs,
1706     ) {
1707         if generic_args.parenthesized {
1708             let was_in_fn_syntax = self.is_in_fn_syntax;
1709             self.is_in_fn_syntax = true;
1710             self.visit_fn_like_elision(generic_args.inputs(),
1711                                        Some(&generic_args.bindings[0].ty));
1712             self.is_in_fn_syntax = was_in_fn_syntax;
1713             return;
1714         }
1715
1716         let mut elide_lifetimes = true;
1717         let lifetimes = generic_args.args.iter().filter_map(|arg| match arg {
1718             hir::GenericArg::Lifetime(lt) => {
1719                 if !lt.is_elided() {
1720                     elide_lifetimes = false;
1721                 }
1722                 Some(lt)
1723             }
1724             _ => None,
1725         }).collect();
1726         if elide_lifetimes {
1727             self.resolve_elided_lifetimes(lifetimes);
1728         } else {
1729             lifetimes.iter().for_each(|lt| self.visit_lifetime(lt));
1730         }
1731
1732         // Figure out if this is a type/trait segment,
1733         // which requires object lifetime defaults.
1734         let parent_def_id = |this: &mut Self, def_id: DefId| {
1735             let def_key = this.tcx.def_key(def_id);
1736             DefId {
1737                 krate: def_id.krate,
1738                 index: def_key.parent.expect("missing parent"),
1739             }
1740         };
1741         let type_def_id = match def {
1742             Def::AssociatedTy(def_id) if depth == 1 => Some(parent_def_id(self, def_id)),
1743             Def::Variant(def_id) if depth == 0 => Some(parent_def_id(self, def_id)),
1744             Def::Struct(def_id)
1745             | Def::Union(def_id)
1746             | Def::Enum(def_id)
1747             | Def::TyAlias(def_id)
1748             | Def::Trait(def_id) if depth == 0 =>
1749             {
1750                 Some(def_id)
1751             }
1752             _ => None,
1753         };
1754
1755         let object_lifetime_defaults = type_def_id.map_or(vec![], |def_id| {
1756             let in_body = {
1757                 let mut scope = self.scope;
1758                 loop {
1759                     match *scope {
1760                         Scope::Root => break false,
1761
1762                         Scope::Body { .. } => break true,
1763
1764                         Scope::Binder { s, .. }
1765                         | Scope::Elision { s, .. }
1766                         | Scope::ObjectLifetimeDefault { s, .. } => {
1767                             scope = s;
1768                         }
1769                     }
1770                 }
1771             };
1772
1773             let map = &self.map;
1774             let unsubst = if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1775                 &map.object_lifetime_defaults[&id]
1776             } else {
1777                 let tcx = self.tcx;
1778                 self.xcrate_object_lifetime_defaults
1779                     .entry(def_id)
1780                     .or_insert_with(|| {
1781                         tcx.generics_of(def_id).params.iter().filter_map(|param| {
1782                             match param.kind {
1783                                 GenericParamDefKind::Type { object_lifetime_default, .. } => {
1784                                     Some(object_lifetime_default)
1785                                 }
1786                                 GenericParamDefKind::Lifetime => None,
1787                             }
1788                         }).collect()
1789                     })
1790             };
1791             unsubst.iter()
1792                    .map(|set| match *set {
1793                        Set1::Empty => if in_body {
1794                            None
1795                        } else {
1796                            Some(Region::Static)
1797                        },
1798                        Set1::One(r) => {
1799                            let lifetimes = generic_args.args.iter().filter_map(|arg| match arg {
1800                                GenericArg::Lifetime(lt) => Some(lt),
1801                                _ => None,
1802                            });
1803                            r.subst(lifetimes, map)
1804                        }
1805                        Set1::Many => None,
1806                    })
1807                    .collect()
1808         });
1809
1810         let mut i = 0;
1811         for arg in &generic_args.args {
1812             match arg {
1813                 GenericArg::Lifetime(_) => {}
1814                 GenericArg::Type(ty) => {
1815                     if let Some(&lt) = object_lifetime_defaults.get(i) {
1816                         let scope = Scope::ObjectLifetimeDefault {
1817                             lifetime: lt,
1818                             s: self.scope,
1819                         };
1820                         self.with(scope, |_, this| this.visit_ty(ty));
1821                     } else {
1822                         self.visit_ty(ty);
1823                     }
1824                     i += 1;
1825                 }
1826             }
1827         }
1828
1829         for b in &generic_args.bindings {
1830             self.visit_assoc_type_binding(b);
1831         }
1832     }
1833
1834     fn visit_fn_like_elision(
1835         &mut self,
1836         inputs: &'tcx [hir::Ty],
1837         output: Option<&'tcx P<hir::Ty>>,
1838     ) {
1839         debug!("visit_fn_like_elision: enter");
1840         let mut arg_elide = Elide::FreshLateAnon(Cell::new(0));
1841         let arg_scope = Scope::Elision {
1842             elide: arg_elide.clone(),
1843             s: self.scope,
1844         };
1845         self.with(arg_scope, |_, this| {
1846             for input in inputs {
1847                 this.visit_ty(input);
1848             }
1849             match *this.scope {
1850                 Scope::Elision { ref elide, .. } => {
1851                     arg_elide = elide.clone();
1852                 }
1853                 _ => bug!(),
1854             }
1855         });
1856
1857         let output = match output {
1858             Some(ty) => ty,
1859             None => return,
1860         };
1861
1862         debug!("visit_fn_like_elision: determine output");
1863
1864         // Figure out if there's a body we can get argument names from,
1865         // and whether there's a `self` argument (treated specially).
1866         let mut assoc_item_kind = None;
1867         let mut impl_self = None;
1868         let parent = self.tcx.hir.get_parent_node(output.id);
1869         let body = match self.tcx.hir.get(parent) {
1870             // `fn` definitions and methods.
1871             Node::Item(&hir::Item {
1872                 node: hir::ItemKind::Fn(.., body),
1873                 ..
1874             }) => Some(body),
1875
1876             Node::TraitItem(&hir::TraitItem {
1877                 node: hir::TraitItemKind::Method(_, ref m),
1878                 ..
1879             }) => {
1880                 match self.tcx
1881                     .hir
1882                     .expect_item(self.tcx.hir.get_parent(parent))
1883                     .node
1884                 {
1885                     hir::ItemKind::Trait(.., ref trait_items) => {
1886                         assoc_item_kind = trait_items
1887                             .iter()
1888                             .find(|ti| ti.id.node_id == parent)
1889                             .map(|ti| ti.kind);
1890                     }
1891                     _ => {}
1892                 }
1893                 match *m {
1894                     hir::TraitMethod::Required(_) => None,
1895                     hir::TraitMethod::Provided(body) => Some(body),
1896                 }
1897             }
1898
1899             Node::ImplItem(&hir::ImplItem {
1900                 node: hir::ImplItemKind::Method(_, body),
1901                 ..
1902             }) => {
1903                 match self.tcx
1904                     .hir
1905                     .expect_item(self.tcx.hir.get_parent(parent))
1906                     .node
1907                 {
1908                     hir::ItemKind::Impl(.., ref self_ty, ref impl_items) => {
1909                         impl_self = Some(self_ty);
1910                         assoc_item_kind = impl_items
1911                             .iter()
1912                             .find(|ii| ii.id.node_id == parent)
1913                             .map(|ii| ii.kind);
1914                     }
1915                     _ => {}
1916                 }
1917                 Some(body)
1918             }
1919
1920             // Foreign functions, `fn(...) -> R` and `Trait(...) -> R` (both types and bounds).
1921             Node::ForeignItem(_) | Node::Ty(_) | Node::TraitRef(_) => None,
1922             // Everything else (only closures?) doesn't
1923             // actually enjoy elision in return types.
1924             _ => {
1925                 self.visit_ty(output);
1926                 return;
1927             }
1928         };
1929
1930         let has_self = match assoc_item_kind {
1931             Some(hir::AssociatedItemKind::Method { has_self }) => has_self,
1932             _ => false,
1933         };
1934
1935         // In accordance with the rules for lifetime elision, we can determine
1936         // what region to use for elision in the output type in two ways.
1937         // First (determined here), if `self` is by-reference, then the
1938         // implied output region is the region of the self parameter.
1939         if has_self {
1940             // Look for `self: &'a Self` - also desugared from `&'a self`,
1941             // and if that matches, use it for elision and return early.
1942             let is_self_ty = |def: Def| {
1943                 if let Def::SelfTy(..) = def {
1944                     return true;
1945                 }
1946
1947                 // Can't always rely on literal (or implied) `Self` due
1948                 // to the way elision rules were originally specified.
1949                 let impl_self = impl_self.map(|ty| &ty.node);
1950                 if let Some(&hir::TyKind::Path(hir::QPath::Resolved(None, ref path))) = impl_self {
1951                     match path.def {
1952                         // Whitelist the types that unambiguously always
1953                         // result in the same type constructor being used
1954                         // (it can't differ between `Self` and `self`).
1955                         Def::Struct(_) | Def::Union(_) | Def::Enum(_) | Def::PrimTy(_) => {
1956                             return def == path.def
1957                         }
1958                         _ => {}
1959                     }
1960                 }
1961
1962                 false
1963             };
1964
1965             if let hir::TyKind::Rptr(lifetime_ref, ref mt) = inputs[0].node {
1966                 if let hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) = mt.ty.node {
1967                     if is_self_ty(path.def) {
1968                         if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
1969                             let scope = Scope::Elision {
1970                                 elide: Elide::Exact(lifetime),
1971                                 s: self.scope,
1972                             };
1973                             self.with(scope, |_, this| this.visit_ty(output));
1974                             return;
1975                         }
1976                     }
1977                 }
1978             }
1979         }
1980
1981         // Second, if there was exactly one lifetime (either a substitution or a
1982         // reference) in the arguments, then any anonymous regions in the output
1983         // have that lifetime.
1984         let mut possible_implied_output_region = None;
1985         let mut lifetime_count = 0;
1986         let arg_lifetimes = inputs
1987             .iter()
1988             .enumerate()
1989             .skip(has_self as usize)
1990             .map(|(i, input)| {
1991                 let mut gather = GatherLifetimes {
1992                     map: self.map,
1993                     outer_index: ty::INNERMOST,
1994                     have_bound_regions: false,
1995                     lifetimes: FxHashSet(),
1996                 };
1997                 gather.visit_ty(input);
1998
1999                 lifetime_count += gather.lifetimes.len();
2000
2001                 if lifetime_count == 1 && gather.lifetimes.len() == 1 {
2002                     // there's a chance that the unique lifetime of this
2003                     // iteration will be the appropriate lifetime for output
2004                     // parameters, so lets store it.
2005                     possible_implied_output_region = gather.lifetimes.iter().cloned().next();
2006                 }
2007
2008                 ElisionFailureInfo {
2009                     parent: body,
2010                     index: i,
2011                     lifetime_count: gather.lifetimes.len(),
2012                     have_bound_regions: gather.have_bound_regions,
2013                 }
2014             })
2015             .collect();
2016
2017         let elide = if lifetime_count == 1 {
2018             Elide::Exact(possible_implied_output_region.unwrap())
2019         } else {
2020             Elide::Error(arg_lifetimes)
2021         };
2022
2023         debug!("visit_fn_like_elision: elide={:?}", elide);
2024
2025         let scope = Scope::Elision {
2026             elide,
2027             s: self.scope,
2028         };
2029         self.with(scope, |_, this| this.visit_ty(output));
2030         debug!("visit_fn_like_elision: exit");
2031
2032         struct GatherLifetimes<'a> {
2033             map: &'a NamedRegionMap,
2034             outer_index: ty::DebruijnIndex,
2035             have_bound_regions: bool,
2036             lifetimes: FxHashSet<Region>,
2037         }
2038
2039         impl<'v, 'a> Visitor<'v> for GatherLifetimes<'a> {
2040             fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2041                 NestedVisitorMap::None
2042             }
2043
2044             fn visit_ty(&mut self, ty: &hir::Ty) {
2045                 if let hir::TyKind::BareFn(_) = ty.node {
2046                     self.outer_index.shift_in(1);
2047                 }
2048                 if let hir::TyKind::TraitObject(ref bounds, ref lifetime) = ty.node {
2049                     for bound in bounds {
2050                         self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
2051                     }
2052
2053                     // Stay on the safe side and don't include the object
2054                     // lifetime default (which may not end up being used).
2055                     if !lifetime.is_elided() {
2056                         self.visit_lifetime(lifetime);
2057                     }
2058                 } else {
2059                     intravisit::walk_ty(self, ty);
2060                 }
2061                 if let hir::TyKind::BareFn(_) = ty.node {
2062                     self.outer_index.shift_out(1);
2063                 }
2064             }
2065
2066             fn visit_generic_param(&mut self, param: &hir::GenericParam) {
2067                 if let hir::GenericParamKind::Lifetime { .. } = param.kind {
2068                     // FIXME(eddyb) Do we want this? It only makes a difference
2069                     // if this `for<'a>` lifetime parameter is never used.
2070                     self.have_bound_regions = true;
2071                 }
2072
2073                 intravisit::walk_generic_param(self, param);
2074             }
2075
2076             fn visit_poly_trait_ref(
2077                 &mut self,
2078                 trait_ref: &hir::PolyTraitRef,
2079                 modifier: hir::TraitBoundModifier,
2080             ) {
2081                 self.outer_index.shift_in(1);
2082                 intravisit::walk_poly_trait_ref(self, trait_ref, modifier);
2083                 self.outer_index.shift_out(1);
2084             }
2085
2086             fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
2087                 if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
2088                     match lifetime {
2089                         Region::LateBound(debruijn, _, _) | Region::LateBoundAnon(debruijn, _)
2090                             if debruijn < self.outer_index =>
2091                         {
2092                             self.have_bound_regions = true;
2093                         }
2094                         _ => {
2095                             self.lifetimes
2096                                 .insert(lifetime.shifted_out_to_binder(self.outer_index));
2097                         }
2098                     }
2099                 }
2100             }
2101         }
2102     }
2103
2104     fn resolve_elided_lifetimes(&mut self,
2105                                 lifetime_refs: Vec<&'tcx hir::Lifetime>) {
2106         if lifetime_refs.is_empty() {
2107             return;
2108         }
2109
2110         let span = lifetime_refs[0].span;
2111         let mut late_depth = 0;
2112         let mut scope = self.scope;
2113         let error = loop {
2114             match *scope {
2115                 // Do not assign any resolution, it will be inferred.
2116                 Scope::Body { .. } => return,
2117
2118                 Scope::Root => break None,
2119
2120                 Scope::Binder { s, .. } => {
2121                     late_depth += 1;
2122                     scope = s;
2123                 }
2124
2125                 Scope::Elision { ref elide, .. } => {
2126                     let lifetime = match *elide {
2127                         Elide::FreshLateAnon(ref counter) => {
2128                             for lifetime_ref in lifetime_refs {
2129                                 let lifetime = Region::late_anon(counter).shifted(late_depth);
2130                                 self.insert_lifetime(lifetime_ref, lifetime);
2131                             }
2132                             return;
2133                         }
2134                         Elide::Exact(l) => l.shifted(late_depth),
2135                         Elide::Error(ref e) => break Some(e),
2136                     };
2137                     for lifetime_ref in lifetime_refs {
2138                         self.insert_lifetime(lifetime_ref, lifetime);
2139                     }
2140                     return;
2141                 }
2142
2143                 Scope::ObjectLifetimeDefault { s, .. } => {
2144                     scope = s;
2145                 }
2146             }
2147         };
2148
2149         let mut err = report_missing_lifetime_specifiers(self.tcx.sess, span, lifetime_refs.len());
2150
2151         if let Some(params) = error {
2152             if lifetime_refs.len() == 1 {
2153                 self.report_elision_failure(&mut err, params);
2154             }
2155         }
2156
2157         err.emit();
2158     }
2159
2160     fn report_elision_failure(
2161         &mut self,
2162         db: &mut DiagnosticBuilder,
2163         params: &[ElisionFailureInfo],
2164     ) {
2165         let mut m = String::new();
2166         let len = params.len();
2167
2168         let elided_params: Vec<_> = params
2169             .iter()
2170             .cloned()
2171             .filter(|info| info.lifetime_count > 0)
2172             .collect();
2173
2174         let elided_len = elided_params.len();
2175
2176         for (i, info) in elided_params.into_iter().enumerate() {
2177             let ElisionFailureInfo {
2178                 parent,
2179                 index,
2180                 lifetime_count: n,
2181                 have_bound_regions,
2182             } = info;
2183
2184             let help_name = if let Some(body) = parent {
2185                 let arg = &self.tcx.hir.body(body).arguments[index];
2186                 format!("`{}`", self.tcx.hir.node_to_pretty_string(arg.pat.id))
2187             } else {
2188                 format!("argument {}", index + 1)
2189             };
2190
2191             m.push_str(
2192                 &(if n == 1 {
2193                     help_name
2194                 } else {
2195                     format!(
2196                         "one of {}'s {} {}lifetimes",
2197                         help_name,
2198                         n,
2199                         if have_bound_regions { "free " } else { "" }
2200                     )
2201                 })[..],
2202             );
2203
2204             if elided_len == 2 && i == 0 {
2205                 m.push_str(" or ");
2206             } else if i + 2 == elided_len {
2207                 m.push_str(", or ");
2208             } else if i != elided_len - 1 {
2209                 m.push_str(", ");
2210             }
2211         }
2212
2213         if len == 0 {
2214             help!(
2215                 db,
2216                 "this function's return type contains a borrowed value, but \
2217                  there is no value for it to be borrowed from"
2218             );
2219             help!(db, "consider giving it a 'static lifetime");
2220         } else if elided_len == 0 {
2221             help!(
2222                 db,
2223                 "this function's return type contains a borrowed value with \
2224                  an elided lifetime, but the lifetime cannot be derived from \
2225                  the arguments"
2226             );
2227             help!(
2228                 db,
2229                 "consider giving it an explicit bounded or 'static \
2230                  lifetime"
2231             );
2232         } else if elided_len == 1 {
2233             help!(
2234                 db,
2235                 "this function's return type contains a borrowed value, but \
2236                  the signature does not say which {} it is borrowed from",
2237                 m
2238             );
2239         } else {
2240             help!(
2241                 db,
2242                 "this function's return type contains a borrowed value, but \
2243                  the signature does not say whether it is borrowed from {}",
2244                 m
2245             );
2246         }
2247     }
2248
2249     fn resolve_object_lifetime_default(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
2250         let mut late_depth = 0;
2251         let mut scope = self.scope;
2252         let lifetime = loop {
2253             match *scope {
2254                 Scope::Binder { s, .. } => {
2255                     late_depth += 1;
2256                     scope = s;
2257                 }
2258
2259                 Scope::Root | Scope::Elision { .. } => break Region::Static,
2260
2261                 Scope::Body { .. } | Scope::ObjectLifetimeDefault { lifetime: None, .. } => return,
2262
2263                 Scope::ObjectLifetimeDefault {
2264                     lifetime: Some(l), ..
2265                 } => break l,
2266             }
2267         };
2268         self.insert_lifetime(lifetime_ref, lifetime.shifted(late_depth));
2269     }
2270
2271     fn check_lifetime_params(&mut self, old_scope: ScopeRef, params: &'tcx [hir::GenericParam]) {
2272         let lifetimes: Vec<_> = params.iter().filter_map(|param| match param.kind {
2273             GenericParamKind::Lifetime { .. } => Some((param, param.name)),
2274             _ => None,
2275         }).collect();
2276         for (i, (lifetime_i, lifetime_i_name)) in lifetimes.iter().enumerate() {
2277             if let hir::ParamName::Plain(_) = lifetime_i_name {
2278                 let name = lifetime_i_name.ident().name;
2279                 if name == keywords::UnderscoreLifetime.name() ||
2280                    name == keywords::StaticLifetime.name() {
2281                     let mut err = struct_span_err!(
2282                         self.tcx.sess,
2283                         lifetime_i.span,
2284                         E0262,
2285                         "invalid lifetime parameter name: `{}`",
2286                         lifetime_i.name.ident(),
2287                     );
2288                     err.span_label(
2289                         lifetime_i.span,
2290                         format!("{} is a reserved lifetime name", name),
2291                     );
2292                     err.emit();
2293                 }
2294             }
2295
2296             // It is a hard error to shadow a lifetime within the same scope.
2297             for (lifetime_j, lifetime_j_name) in lifetimes.iter().skip(i + 1) {
2298                 if lifetime_i_name == lifetime_j_name {
2299                     struct_span_err!(
2300                         self.tcx.sess,
2301                         lifetime_j.span,
2302                         E0263,
2303                         "lifetime name `{}` declared twice in the same scope",
2304                         lifetime_j.name.ident()
2305                     ).span_label(lifetime_j.span, "declared twice")
2306                      .span_label(lifetime_i.span, "previous declaration here")
2307                      .emit();
2308                 }
2309             }
2310
2311             // It is a soft error to shadow a lifetime within a parent scope.
2312             self.check_lifetime_param_for_shadowing(old_scope, &lifetime_i);
2313
2314             for bound in &lifetime_i.bounds {
2315                 match bound {
2316                     hir::GenericBound::Outlives(lt) => match lt.name {
2317                         hir::LifetimeName::Underscore => {
2318                             let mut err = struct_span_err!(
2319                                 self.tcx.sess,
2320                                 lt.span,
2321                                 E0637,
2322                                 "invalid lifetime bound name: `'_`"
2323                             );
2324                             err.span_label(lt.span, "`'_` is a reserved lifetime name");
2325                             err.emit();
2326                         }
2327                         hir::LifetimeName::Static => {
2328                             self.insert_lifetime(lt, Region::Static);
2329                             self.tcx.sess.struct_span_warn(
2330                                 lifetime_i.span.to(lt.span),
2331                                 &format!(
2332                                     "unnecessary lifetime parameter `{}`",
2333                                     lifetime_i.name.ident(),
2334                                 ),
2335                             ).help(&format!(
2336                                 "you can use the `'static` lifetime directly, in place \
2337                                     of `{}`",
2338                                 lifetime_i.name.ident(),
2339                             )).emit();
2340                         }
2341                         hir::LifetimeName::Param(_)
2342                         | hir::LifetimeName::Implicit => {
2343                             self.resolve_lifetime_ref(lt);
2344                         }
2345                     }
2346                     _ => bug!(),
2347                 }
2348             }
2349         }
2350     }
2351
2352     fn check_lifetime_param_for_shadowing(
2353         &self,
2354         mut old_scope: ScopeRef,
2355         param: &'tcx hir::GenericParam,
2356     ) {
2357         for label in &self.labels_in_fn {
2358             // FIXME (#24278): non-hygienic comparison
2359             if param.name.ident().name == label.name {
2360                 signal_shadowing_problem(
2361                     self.tcx,
2362                     label.name,
2363                     original_label(label.span),
2364                     shadower_lifetime(&param),
2365                 );
2366                 return;
2367             }
2368         }
2369
2370         loop {
2371             match *old_scope {
2372                 Scope::Body { s, .. }
2373                 | Scope::Elision { s, .. }
2374                 | Scope::ObjectLifetimeDefault { s, .. } => {
2375                     old_scope = s;
2376                 }
2377
2378                 Scope::Root => {
2379                     return;
2380                 }
2381
2382                 Scope::Binder {
2383                     ref lifetimes, s, ..
2384                 } => {
2385                     if let Some(&def) = lifetimes.get(&param.name.modern()) {
2386                         let node_id = self.tcx.hir.as_local_node_id(def.id().unwrap()).unwrap();
2387
2388                         signal_shadowing_problem(
2389                             self.tcx,
2390                             param.name.ident().name,
2391                             original_lifetime(self.tcx.hir.span(node_id)),
2392                             shadower_lifetime(&param),
2393                         );
2394                         return;
2395                     }
2396
2397                     old_scope = s;
2398                 }
2399             }
2400         }
2401     }
2402
2403     /// Returns true if, in the current scope, replacing `'_` would be
2404     /// equivalent to a single-use lifetime.
2405     fn track_lifetime_uses(&self) -> bool {
2406         let mut scope = self.scope;
2407         loop {
2408             match *scope {
2409                 Scope::Root => break false,
2410
2411                 // Inside of items, it depends on the kind of item.
2412                 Scope::Binder {
2413                     track_lifetime_uses,
2414                     ..
2415                 } => break track_lifetime_uses,
2416
2417                 // Inside a body, `'_` will use an inference variable,
2418                 // should be fine.
2419                 Scope::Body { .. } => break true,
2420
2421                 // A lifetime only used in a fn argument could as well
2422                 // be replaced with `'_`, as that would generate a
2423                 // fresh name, too.
2424                 Scope::Elision {
2425                     elide: Elide::FreshLateAnon(_),
2426                     ..
2427                 } => break true,
2428
2429                 // In the return type or other such place, `'_` is not
2430                 // going to make a fresh name, so we cannot
2431                 // necessarily replace a single-use lifetime with
2432                 // `'_`.
2433                 Scope::Elision {
2434                     elide: Elide::Exact(_),
2435                     ..
2436                 } => break false,
2437                 Scope::Elision {
2438                     elide: Elide::Error(_),
2439                     ..
2440                 } => break false,
2441
2442                 Scope::ObjectLifetimeDefault { s, .. } => scope = s,
2443             }
2444         }
2445     }
2446
2447     fn insert_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime, def: Region) {
2448         if lifetime_ref.id == ast::DUMMY_NODE_ID {
2449             span_bug!(
2450                 lifetime_ref.span,
2451                 "lifetime reference not renumbered, \
2452                  probably a bug in syntax::fold"
2453             );
2454         }
2455
2456         debug!(
2457             "insert_lifetime: {} resolved to {:?} span={:?}",
2458             self.tcx.hir.node_to_string(lifetime_ref.id),
2459             def,
2460             self.tcx.sess.source_map().span_to_string(lifetime_ref.span)
2461         );
2462         self.map.defs.insert(lifetime_ref.id, def);
2463
2464         match def {
2465             Region::LateBoundAnon(..) | Region::Static => {
2466                 // These are anonymous lifetimes or lifetimes that are not declared.
2467             }
2468
2469             Region::Free(_, def_id)
2470             | Region::LateBound(_, def_id, _)
2471             | Region::EarlyBound(_, def_id, _) => {
2472                 // A lifetime declared by the user.
2473                 let track_lifetime_uses = self.track_lifetime_uses();
2474                 debug!(
2475                     "insert_lifetime: track_lifetime_uses={}",
2476                     track_lifetime_uses
2477                 );
2478                 if track_lifetime_uses && !self.lifetime_uses.contains_key(&def_id) {
2479                     debug!("insert_lifetime: first use of {:?}", def_id);
2480                     self.lifetime_uses
2481                         .insert(def_id, LifetimeUseSet::One(lifetime_ref));
2482                 } else {
2483                     debug!("insert_lifetime: many uses of {:?}", def_id);
2484                     self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
2485                 }
2486             }
2487         }
2488     }
2489
2490     /// Sometimes we resolve a lifetime, but later find that it is an
2491     /// error (esp. around impl trait). In that case, we remove the
2492     /// entry into `map.defs` so as not to confuse later code.
2493     fn uninsert_lifetime_on_error(&mut self, lifetime_ref: &'tcx hir::Lifetime, bad_def: Region) {
2494         let old_value = self.map.defs.remove(&lifetime_ref.id);
2495         assert_eq!(old_value, Some(bad_def));
2496     }
2497 }
2498
2499 ///////////////////////////////////////////////////////////////////////////
2500
2501 /// Detects late-bound lifetimes and inserts them into
2502 /// `map.late_bound`.
2503 ///
2504 /// A region declared on a fn is **late-bound** if:
2505 /// - it is constrained by an argument type;
2506 /// - it does not appear in a where-clause.
2507 ///
2508 /// "Constrained" basically means that it appears in any type but
2509 /// not amongst the inputs to a projection.  In other words, `<&'a
2510 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
2511 fn insert_late_bound_lifetimes(
2512     map: &mut NamedRegionMap,
2513     decl: &hir::FnDecl,
2514     generics: &hir::Generics,
2515 ) {
2516     debug!(
2517         "insert_late_bound_lifetimes(decl={:?}, generics={:?})",
2518         decl, generics
2519     );
2520
2521     let mut constrained_by_input = ConstrainedCollector {
2522         regions: FxHashSet(),
2523     };
2524     for arg_ty in &decl.inputs {
2525         constrained_by_input.visit_ty(arg_ty);
2526     }
2527
2528     let mut appears_in_output = AllCollector {
2529         regions: FxHashSet(),
2530     };
2531     intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
2532
2533     debug!(
2534         "insert_late_bound_lifetimes: constrained_by_input={:?}",
2535         constrained_by_input.regions
2536     );
2537
2538     // Walk the lifetimes that appear in where clauses.
2539     //
2540     // Subtle point: because we disallow nested bindings, we can just
2541     // ignore binders here and scrape up all names we see.
2542     let mut appears_in_where_clause = AllCollector {
2543         regions: FxHashSet(),
2544     };
2545     appears_in_where_clause.visit_generics(generics);
2546
2547     for param in &generics.params {
2548         match param.kind {
2549             hir::GenericParamKind::Lifetime { .. } => {
2550                 if !param.bounds.is_empty() {
2551                     // `'a: 'b` means both `'a` and `'b` are referenced
2552                     appears_in_where_clause
2553                         .regions.insert(hir::LifetimeName::Param(param.name.modern()));
2554                 }
2555             }
2556             hir::GenericParamKind::Type { .. } => {}
2557         }
2558     }
2559
2560     debug!(
2561         "insert_late_bound_lifetimes: appears_in_where_clause={:?}",
2562         appears_in_where_clause.regions
2563     );
2564
2565     // Late bound regions are those that:
2566     // - appear in the inputs
2567     // - do not appear in the where-clauses
2568     // - are not implicitly captured by `impl Trait`
2569     for param in &generics.params {
2570         let lt_name = hir::LifetimeName::Param(param.name.modern());
2571         // appears in the where clauses? early-bound.
2572         if appears_in_where_clause.regions.contains(&lt_name) {
2573             continue;
2574         }
2575
2576         // does not appear in the inputs, but appears in the return type? early-bound.
2577         if !constrained_by_input.regions.contains(&lt_name)
2578             && appears_in_output.regions.contains(&lt_name)
2579         {
2580             continue;
2581         }
2582
2583         debug!("insert_late_bound_lifetimes: lifetime {:?} with id {:?} is late-bound",
2584                param.name.ident(),
2585                param.id);
2586
2587         let inserted = map.late_bound.insert(param.id);
2588         assert!(inserted, "visited lifetime {:?} twice", param.id);
2589     }
2590
2591     return;
2592
2593     struct ConstrainedCollector {
2594         regions: FxHashSet<hir::LifetimeName>,
2595     }
2596
2597     impl<'v> Visitor<'v> for ConstrainedCollector {
2598         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2599             NestedVisitorMap::None
2600         }
2601
2602         fn visit_ty(&mut self, ty: &'v hir::Ty) {
2603             match ty.node {
2604                 hir::TyKind::Path(hir::QPath::Resolved(Some(_), _))
2605                 | hir::TyKind::Path(hir::QPath::TypeRelative(..)) => {
2606                     // ignore lifetimes appearing in associated type
2607                     // projections, as they are not *constrained*
2608                     // (defined above)
2609                 }
2610
2611                 hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
2612                     // consider only the lifetimes on the final
2613                     // segment; I am not sure it's even currently
2614                     // valid to have them elsewhere, but even if it
2615                     // is, those would be potentially inputs to
2616                     // projections
2617                     if let Some(last_segment) = path.segments.last() {
2618                         self.visit_path_segment(path.span, last_segment);
2619                     }
2620                 }
2621
2622                 _ => {
2623                     intravisit::walk_ty(self, ty);
2624                 }
2625             }
2626         }
2627
2628         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
2629             self.regions.insert(lifetime_ref.name.modern());
2630         }
2631     }
2632
2633     struct AllCollector {
2634         regions: FxHashSet<hir::LifetimeName>,
2635     }
2636
2637     impl<'v> Visitor<'v> for AllCollector {
2638         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2639             NestedVisitorMap::None
2640         }
2641
2642         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
2643             self.regions.insert(lifetime_ref.name.modern());
2644         }
2645     }
2646 }
2647
2648 pub fn report_missing_lifetime_specifiers(
2649     sess: &Session,
2650     span: Span,
2651     count: usize,
2652 ) -> DiagnosticBuilder<'_> {
2653     let mut err = struct_span_err!(
2654         sess,
2655         span,
2656         E0106,
2657         "missing lifetime specifier{}",
2658         if count > 1 { "s" } else { "" }
2659     );
2660
2661     let msg = if count > 1 {
2662         format!("expected {} lifetime parameters", count)
2663     } else {
2664         "expected lifetime parameter".to_string()
2665     };
2666
2667     err.span_label(span, msg);
2668
2669     err
2670 }