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::Def(item_id, ref lifetimes) => {
 625                 // Resolve the lifetimes in the bounds to the lifetime defs in the generics.
 626                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 627                 // `abstract type MyAnonTy<'b>: MyTrait<'b>;`
 628                 //                          ^            ^ this gets resolved in the scope of
 629                 //                                         the exist_ty generics
 630                 let (generics, bounds) = match self.tcx.hir.expect_item(item_id.id).node {
 631                     // named existential types are reached via TyKind::Path
 632                     // this arm is for `impl Trait` in the types of statics, constants and locals
 633                     hir::ItemKind::Existential(hir::ExistTy{ impl_trait_fn: None, .. }) => {
 634                         intravisit::walk_ty(self, ty);
 635                         return;
 636                     },
 637                     // RPIT (return position impl trait)
 638                     hir::ItemKind::Existential(hir::ExistTy{
 639                         ref generics,
 640                         ref bounds,
 641                         ..
 642                     }) => (
 643                         generics,
 644                         bounds,
 645                     ),
 646                     ref i => bug!("impl Trait pointed to non-existential type?? {:#?}", i),
 647                 };
 648
 649                 // Resolve the lifetimes that are applied to the existential type.
 650                 // These are resolved in the current scope.
 651                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 652                 // `fn foo<'a>() -> MyAnonTy<'a> { ... }`
 653                 //          ^                 ^this gets resolved in the current scope
 654                 for lifetime in lifetimes {
 655                     if let hir::GenericArg::Lifetime(lifetime) = lifetime {
 656                         self.visit_lifetime(lifetime);
 657
 658                         // Check for predicates like `impl for<'a> Trait<impl OtherTrait<'a>>`
 659                         // and ban them. Type variables instantiated inside binders aren't
 660                         // well-supported at the moment, so this doesn't work.
 661                         // In the future, this should be fixed and this error should be removed.
 662                         let def = self.map.defs.get(&lifetime.id).cloned();
 663                         if let Some(Region::LateBound(_, def_id, _)) = def {
 664                             if let Some(node_id) = self.tcx.hir.as_local_node_id(def_id) {
 665                                 // Ensure that the parent of the def is an item, not HRTB
 666                                 let parent_id = self.tcx.hir.get_parent_node(node_id);
 667                                 let parent_impl_id = hir::ImplItemId { node_id: parent_id };
 668                                 let parent_trait_id = hir::TraitItemId { node_id: parent_id };
 669                                 let krate = self.tcx.hir.forest.krate();
 670                                 if !(krate.items.contains_key(&parent_id)
 671                                     || krate.impl_items.contains_key(&parent_impl_id)
 672                                     || krate.trait_items.contains_key(&parent_trait_id))
 673                                 {
 674                                     span_err!(
 675                                         self.tcx.sess,
 676                                         lifetime.span,
 677                                         E0657,
 678                                         "`impl Trait` can only capture lifetimes \
 679                                         bound at the fn or impl level"
 680                                     );
 681                                     self.uninsert_lifetime_on_error(lifetime, def.unwrap());
 682                                 }
 683                             }
 684                         }
 685                     }
 686                 }
 687
 688                 // We want to start our early-bound indices at the end of the parent scope,
 689                 // not including any parent `impl Trait`s.
 690                 let mut index = self.next_early_index_for_abstract_type();
 691                 debug!("visit_ty: index = {}", index);
 692
 693                 let mut elision = None;
 694                 let mut lifetimes = FxHashMap();
 695                 let mut type_count = 0;
 696                 for param in &generics.params {
 697                     match param.kind {
 698                         GenericParamKind::Lifetime { .. } => {
 699                             let (name, reg) = Region::early(&self.tcx.hir, &mut index, &param);
 700                             if let hir::ParamName::Plain(param_name) = name {
 701                                 if param_name.name == keywords::UnderscoreLifetime.name() {
 702                                     // Pick the elided lifetime "definition" if one exists
 703                                     // and use it to make an elision scope.
 704                                     elision = Some(reg);
 705                                 } else {
 706                                     lifetimes.insert(name, reg);
 707                                 }
 708                             } else {
 709                                 lifetimes.insert(name, reg);
 710                             }
 711                         }
 712                         GenericParamKind::Type { .. } => {
 713                             type_count += 1;
 714                         }
 715                     }
 716                 }
 717                 let next_early_index = index + type_count;
 718
 719                 if let Some(elision_region) = elision {
 720                     let scope = Scope::Elision {
 721                         elide: Elide::Exact(elision_region),
 722                         s: self.scope,
 723                     };
 724                     self.with(scope, |_old_scope, this| {
 725                         let scope = Scope::Binder {
 726                             lifetimes,
 727                             next_early_index,
 728                             s: this.scope,
 729                             track_lifetime_uses: true,
 730                             abstract_type_parent: false,
 731                         };
 732                         this.with(scope, |_old_scope, this| {
 733                             this.visit_generics(generics);
 734                             for bound in bounds {
 735                                 this.visit_param_bound(bound);
 736                             }
 737                         });
 738                     });
 739                 } else {
 740                     let scope = Scope::Binder {
 741                         lifetimes,
 742                         next_early_index,
 743                         s: self.scope,
 744                         track_lifetime_uses: true,
 745                         abstract_type_parent: false,
 746                     };
 747                     self.with(scope, |_old_scope, this| {
 748                         this.visit_generics(generics);
 749                         for bound in bounds {
 750                             this.visit_param_bound(bound);
 751                         }
 752                     });
 753                 }
 754             }
 755             _ => intravisit::walk_ty(self, ty),
 756         }
 757     }
 758
 759     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
 760         use self::hir::TraitItemKind::*;
 761         match trait_item.node {
 762             Method(ref sig, _) => {
 763                 let tcx = self.tcx;
 764                 self.visit_early_late(
 765                     Some(tcx.hir.get_parent(trait_item.id)),
 766                     &sig.decl,
 767                     &trait_item.generics,
 768                     |this| intravisit::walk_trait_item(this, trait_item),
 769                 );
 770             }
 771             Type(ref bounds, ref ty) => {
 772                 let generics = &trait_item.generics;
 773                 let mut index = self.next_early_index();
 774                 debug!("visit_ty: index = {}", index);
 775                 let mut type_count = 0;
 776                 let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
 777                     GenericParamKind::Lifetime { .. } => {
 778                         Some(Region::early(&self.tcx.hir, &mut index, param))
 779                     }
 780                     GenericParamKind::Type { .. } => {
 781                         type_count += 1;
 782                         None
 783                     }
 784                 }).collect();
 785                 let scope = Scope::Binder {
 786                     lifetimes,
 787                     next_early_index: index + type_count,
 788                     s: self.scope,
 789                     track_lifetime_uses: true,
 790                     abstract_type_parent: true,
 791                 };
 792                 self.with(scope, |_old_scope, this| {
 793                     this.visit_generics(generics);
 794                     for bound in bounds {
 795                         this.visit_param_bound(bound);
 796                     }
 797                     if let Some(ty) = ty {
 798                         this.visit_ty(ty);
 799                     }
 800                 });
 801             }
 802             Const(_, _) => {
 803                 // Only methods and types support generics.
 804                 assert!(trait_item.generics.params.is_empty());
 805                 intravisit::walk_trait_item(self, trait_item);
 806             }
 807         }
 808     }
 809
 810     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
 811         use self::hir::ImplItemKind::*;
 812         match impl_item.node {
 813             Method(ref sig, _) => {
 814                 let tcx = self.tcx;
 815                 self.visit_early_late(
 816                     Some(tcx.hir.get_parent(impl_item.id)),
 817                     &sig.decl,
 818                     &impl_item.generics,
 819                     |this| intravisit::walk_impl_item(this, impl_item),
 820                 )
 821             }
 822             Type(ref ty) => {
 823                 let generics = &impl_item.generics;
 824                 let mut index = self.next_early_index();
 825                 let mut next_early_index = index;
 826                 debug!("visit_ty: index = {}", index);
 827                 let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
 828                     GenericParamKind::Lifetime { .. } => {
 829                         Some(Region::early(&self.tcx.hir, &mut index, param))
 830                     }
 831                     GenericParamKind::Type { .. } => {
 832                         next_early_index += 1;
 833                         None
 834                     }
 835                 }).collect();
 836                 let scope = Scope::Binder {
 837                     lifetimes,
 838                     next_early_index,
 839                     s: self.scope,
 840                     track_lifetime_uses: true,
 841                     abstract_type_parent: true,
 842                 };
 843                 self.with(scope, |_old_scope, this| {
 844                     this.visit_generics(generics);
 845                     this.visit_ty(ty);
 846                 });
 847             }
 848             Existential(ref bounds) => {
 849                 let generics = &impl_item.generics;
 850                 let mut index = self.next_early_index();
 851                 let mut next_early_index = index;
 852                 debug!("visit_ty: index = {}", index);
 853                 let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
 854                     GenericParamKind::Lifetime { .. } => {
 855                         Some(Region::early(&self.tcx.hir, &mut index, param))
 856                     }
 857                     GenericParamKind::Type { .. } => {
 858                         next_early_index += 1;
 859                         None
 860                     }
 861                 }).collect();
 862
 863                 let scope = Scope::Binder {
 864                     lifetimes,
 865                     next_early_index,
 866                     s: self.scope,
 867                     track_lifetime_uses: true,
 868                     abstract_type_parent: true,
 869                 };
 870                 self.with(scope, |_old_scope, this| {
 871                     this.visit_generics(generics);
 872                     for bound in bounds {
 873                         this.visit_param_bound(bound);
 874                     }
 875                 });
 876             }
 877             Const(_, _) => {
 878                 // Only methods and types support generics.
 879                 assert!(impl_item.generics.params.is_empty());
 880                 intravisit::walk_impl_item(self, impl_item);
 881             }
 882         }
 883     }
 884
 885     fn visit_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
 886         if lifetime_ref.is_elided() {
 887             self.resolve_elided_lifetimes(vec![lifetime_ref]);
 888             return;
 889         }
 890         if lifetime_ref.is_static() {
 891             self.insert_lifetime(lifetime_ref, Region::Static);
 892             return;
 893         }
 894         self.resolve_lifetime_ref(lifetime_ref);
 895     }
 896
 897     fn visit_path(&mut self, path: &'tcx hir::Path, _: hir::HirId) {
 898         for (i, segment) in path.segments.iter().enumerate() {
 899             let depth = path.segments.len() - i - 1;
 900             if let Some(ref args) = segment.args {
 901                 self.visit_segment_args(path.def, depth, args);
 902             }
 903         }
 904     }
 905
 906     fn visit_fn_decl(&mut self, fd: &'tcx hir::FnDecl) {
 907         let output = match fd.output {
 908             hir::DefaultReturn(_) => None,
 909             hir::Return(ref ty) => Some(ty),
 910         };
 911         self.visit_fn_like_elision(&fd.inputs, output);
 912     }
 913
 914     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
 915         check_mixed_explicit_and_in_band_defs(self.tcx, &generics.params);
 916         for param in &generics.params {
 917             match param.kind {
 918                 GenericParamKind::Lifetime { .. } => {}
 919                 GenericParamKind::Type { ref default, .. } => {
 920                     walk_list!(self, visit_param_bound, &param.bounds);
 921                     if let Some(ref ty) = default {
 922                         self.visit_ty(&ty);
 923                     }
 924                 }
 925             }
 926         }
 927         for predicate in &generics.where_clause.predicates {
 928             match predicate {
 929                 &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate {
 930                     ref bounded_ty,
 931                     ref bounds,
 932                     ref bound_generic_params,
 933                     ..
 934                 }) => {
 935                     let lifetimes: FxHashMap<_, _> = bound_generic_params.iter()
 936                         .filter_map(|param| match param.kind {
 937                             GenericParamKind::Lifetime { .. } => {
 938                                 Some(Region::late(&self.tcx.hir, param))
 939                             }
 940                             _ => None,
 941                         }).collect();
 942                     if !lifetimes.is_empty() {
 943                         self.trait_ref_hack = true;
 944                         let next_early_index = self.next_early_index();
 945                         let scope = Scope::Binder {
 946                             lifetimes,
 947                             s: self.scope,
 948                             next_early_index,
 949                             track_lifetime_uses: true,
 950                             abstract_type_parent: false,
 951                         };
 952                         let result = self.with(scope, |old_scope, this| {
 953                             this.check_lifetime_params(old_scope, &bound_generic_params);
 954                             this.visit_ty(&bounded_ty);
 955                             walk_list!(this, visit_param_bound, bounds);
 956                         });
 957                         self.trait_ref_hack = false;
 958                         result
 959                     } else {
 960                         self.visit_ty(&bounded_ty);
 961                         walk_list!(self, visit_param_bound, bounds);
 962                     }
 963                 }
 964                 &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate {
 965                     ref lifetime,
 966                     ref bounds,
 967                     ..
 968                 }) => {
 969                     self.visit_lifetime(lifetime);
 970                     walk_list!(self, visit_param_bound, bounds);
 971                 }
 972                 &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate {
 973                     ref lhs_ty,
 974                     ref rhs_ty,
 975                     ..
 976                 }) => {
 977                     self.visit_ty(lhs_ty);
 978                     self.visit_ty(rhs_ty);
 979                 }
 980             }
 981         }
 982     }
 983
 984     fn visit_poly_trait_ref(
 985         &mut self,
 986         trait_ref: &'tcx hir::PolyTraitRef,
 987         _modifier: hir::TraitBoundModifier,
 988     ) {
 989         debug!("visit_poly_trait_ref trait_ref={:?}", trait_ref);
 990
 991         if !self.trait_ref_hack
 992             || trait_ref
 993                 .bound_generic_params
 994                 .iter()
 995                 .any(|param| match param.kind {
 996                     GenericParamKind::Lifetime { .. } => true,
 997                     _ => false,
 998                 })
 999         {
1000             if self.trait_ref_hack {
1001                 span_err!(
1002                     self.tcx.sess,
1003                     trait_ref.span,
1004                     E0316,
1005                     "nested quantification of lifetimes"
1006                 );
1007             }
1008             let next_early_index = self.next_early_index();
1009             let scope = Scope::Binder {
1010                 lifetimes: trait_ref.bound_generic_params.iter()
1011                     .filter_map(|param| match param.kind {
1012                         GenericParamKind::Lifetime { .. } => {
1013                             Some(Region::late(&self.tcx.hir, param))
1014                         }
1015                         _ => None,
1016                     }).collect(),
1017                 s: self.scope,
1018                 next_early_index,
1019                 track_lifetime_uses: true,
1020                 abstract_type_parent: false,
1021             };
1022             self.with(scope, |old_scope, this| {
1023                 this.check_lifetime_params(old_scope, &trait_ref.bound_generic_params);
1024                 walk_list!(this, visit_generic_param, &trait_ref.bound_generic_params);
1025                 this.visit_trait_ref(&trait_ref.trait_ref)
1026             })
1027         } else {
1028             self.visit_trait_ref(&trait_ref.trait_ref)
1029         }
1030     }
1031 }
1032
1033 #[derive(Copy, Clone, PartialEq)]
1034 enum ShadowKind {
1035     Label,
1036     Lifetime,
1037 }
1038 struct Original {
1039     kind: ShadowKind,
1040     span: Span,
1041 }
1042 struct Shadower {
1043     kind: ShadowKind,
1044     span: Span,
1045 }
1046
1047 fn original_label(span: Span) -> Original {
1048     Original {
1049         kind: ShadowKind::Label,
1050         span: span,
1051     }
1052 }
1053 fn shadower_label(span: Span) -> Shadower {
1054     Shadower {
1055         kind: ShadowKind::Label,
1056         span: span,
1057     }
1058 }
1059 fn original_lifetime(span: Span) -> Original {
1060     Original {
1061         kind: ShadowKind::Lifetime,
1062         span: span,
1063     }
1064 }
1065 fn shadower_lifetime(param: &hir::GenericParam) -> Shadower {
1066     Shadower {
1067         kind: ShadowKind::Lifetime,
1068         span: param.span,
1069     }
1070 }
1071
1072 impl ShadowKind {
1073     fn desc(&self) -> &'static str {
1074         match *self {
1075             ShadowKind::Label => "label",
1076             ShadowKind::Lifetime => "lifetime",
1077         }
1078     }
1079 }
1080
1081 fn check_mixed_explicit_and_in_band_defs(
1082     tcx: TyCtxt<'_, '_, '_>,
1083     params: &P<[hir::GenericParam]>,
1084 ) {
1085     let in_bands: Vec<_> = params.iter().filter_map(|param| match param.kind {
1086         GenericParamKind::Lifetime { in_band, .. } => Some((in_band, param.span)),
1087         _ => None,
1088     }).collect();
1089     let out_of_band = in_bands.iter().find(|(in_band, _)| !in_band);
1090     let in_band = in_bands.iter().find(|(in_band, _)| *in_band);
1091
1092     if let (Some((_, out_of_band_span)), Some((_, in_band_span)))
1093         = (out_of_band, in_band) {
1094         struct_span_err!(
1095             tcx.sess,
1096             *in_band_span,
1097             E0688,
1098             "cannot mix in-band and explicit lifetime definitions"
1099         ).span_label(
1100             *in_band_span,
1101             "in-band lifetime definition here",
1102         ).span_label(*out_of_band_span, "explicit lifetime definition here")
1103         .emit();
1104     }
1105 }
1106
1107 fn signal_shadowing_problem(
1108     tcx: TyCtxt<'_, '_, '_>,
1109     name: ast::Name,
1110     orig: Original,
1111     shadower: Shadower,
1112 ) {
1113     let mut err = if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
1114         // lifetime/lifetime shadowing is an error
1115         struct_span_err!(
1116             tcx.sess,
1117             shadower.span,
1118             E0496,
1119             "{} name `{}` shadows a \
1120              {} name that is already in scope",
1121             shadower.kind.desc(),
1122             name,
1123             orig.kind.desc()
1124         )
1125     } else {
1126         // shadowing involving a label is only a warning, due to issues with
1127         // labels and lifetimes not being macro-hygienic.
1128         tcx.sess.struct_span_warn(
1129             shadower.span,
1130             &format!(
1131                 "{} name `{}` shadows a \
1132                  {} name that is already in scope",
1133                 shadower.kind.desc(),
1134                 name,
1135                 orig.kind.desc()
1136             ),
1137         )
1138     };
1139     err.span_label(orig.span, "first declared here");
1140     err.span_label(shadower.span, format!("lifetime {} already in scope", name));
1141     err.emit();
1142 }
1143
1144 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
1145 // if one of the label shadows a lifetime or another label.
1146 fn extract_labels(ctxt: &mut LifetimeContext<'_, '_>, body: &hir::Body) {
1147     struct GatherLabels<'a, 'tcx: 'a> {
1148         tcx: TyCtxt<'a, 'tcx, 'tcx>,
1149         scope: ScopeRef<'a>,
1150         labels_in_fn: &'a mut Vec<ast::Ident>,
1151     }
1152
1153     let mut gather = GatherLabels {
1154         tcx: ctxt.tcx,
1155         scope: ctxt.scope,
1156         labels_in_fn: &mut ctxt.labels_in_fn,
1157     };
1158     gather.visit_body(body);
1159
1160     impl<'v, 'a, 'tcx> Visitor<'v> for GatherLabels<'a, 'tcx> {
1161         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
1162             NestedVisitorMap::None
1163         }
1164
1165         fn visit_expr(&mut self, ex: &hir::Expr) {
1166             if let Some(label) = expression_label(ex) {
1167                 for prior_label in &self.labels_in_fn[..] {
1168                     // FIXME (#24278): non-hygienic comparison
1169                     if label.name == prior_label.name {
1170                         signal_shadowing_problem(
1171                             self.tcx,
1172                             label.name,
1173                             original_label(prior_label.span),
1174                             shadower_label(label.span),
1175                         );
1176                     }
1177                 }
1178
1179                 check_if_label_shadows_lifetime(self.tcx, self.scope, label);
1180
1181                 self.labels_in_fn.push(label);
1182             }
1183             intravisit::walk_expr(self, ex)
1184         }
1185     }
1186
1187     fn expression_label(ex: &hir::Expr) -> Option<ast::Ident> {
1188         match ex.node {
1189             hir::ExprKind::While(.., Some(label)) |
1190             hir::ExprKind::Loop(_, Some(label), _) => Some(label.ident),
1191             _ => None,
1192         }
1193     }
1194
1195     fn check_if_label_shadows_lifetime(
1196         tcx: TyCtxt<'_, '_, '_>,
1197         mut scope: ScopeRef<'_>,
1198         label: ast::Ident,
1199     ) {
1200         loop {
1201             match *scope {
1202                 Scope::Body { s, .. }
1203                 | Scope::Elision { s, .. }
1204                 | Scope::ObjectLifetimeDefault { s, .. } => {
1205                     scope = s;
1206                 }
1207
1208                 Scope::Root => {
1209                     return;
1210                 }
1211
1212                 Scope::Binder {
1213                     ref lifetimes, s, ..
1214                 } => {
1215                     // FIXME (#24278): non-hygienic comparison
1216                     if let Some(def) = lifetimes.get(&hir::ParamName::Plain(label.modern())) {
1217                         let node_id = tcx.hir.as_local_node_id(def.id().unwrap()).unwrap();
1218
1219                         signal_shadowing_problem(
1220                             tcx,
1221                             label.name,
1222                             original_lifetime(tcx.hir.span(node_id)),
1223                             shadower_label(label.span),
1224                         );
1225                         return;
1226                     }
1227                     scope = s;
1228                 }
1229             }
1230         }
1231     }
1232 }
1233
1234 fn compute_object_lifetime_defaults(
1235     tcx: TyCtxt<'_, '_, '_>,
1236 ) -> NodeMap<Vec<ObjectLifetimeDefault>> {
1237     let mut map = NodeMap();
1238     for item in tcx.hir.krate().items.values() {
1239         match item.node {
1240             hir::ItemKind::Struct(_, ref generics)
1241             | hir::ItemKind::Union(_, ref generics)
1242             | hir::ItemKind::Enum(_, ref generics)
1243             | hir::ItemKind::Existential(hir::ExistTy { ref generics, impl_trait_fn: None, .. })
1244             | hir::ItemKind::Ty(_, ref generics)
1245             | hir::ItemKind::Trait(_, _, ref generics, ..) => {
1246                 let result = object_lifetime_defaults_for_item(tcx, generics);
1247
1248                 // Debugging aid.
1249                 if attr::contains_name(&item.attrs, "rustc_object_lifetime_default") {
1250                     let object_lifetime_default_reprs: String = result
1251                         .iter()
1252                         .map(|set| match *set {
1253                             Set1::Empty => "BaseDefault".to_string(),
1254                             Set1::One(Region::Static) => "'static".to_string(),
1255                             Set1::One(Region::EarlyBound(mut i, _, _)) => {
1256                                 generics.params.iter().find_map(|param| match param.kind {
1257                                         GenericParamKind::Lifetime { .. } => {
1258                                             if i == 0 {
1259                                                 return Some(param.name.ident().to_string());
1260                                             }
1261                                             i -= 1;
1262                                             None
1263                                         }
1264                                         _ => None,
1265                                     }).unwrap()
1266                             }
1267                             Set1::One(_) => bug!(),
1268                             Set1::Many => "Ambiguous".to_string(),
1269                         })
1270                         .collect::<Vec<String>>()
1271                         .join(",");
1272                     tcx.sess.span_err(item.span, &object_lifetime_default_reprs);
1273                 }
1274
1275                 map.insert(item.id, result);
1276             }
1277             _ => {}
1278         }
1279     }
1280     map
1281 }
1282
1283 /// Scan the bounds and where-clauses on parameters to extract bounds
1284 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`
1285 /// for each type parameter.
1286 fn object_lifetime_defaults_for_item(
1287     tcx: TyCtxt<'_, '_, '_>,
1288     generics: &hir::Generics,
1289 ) -> Vec<ObjectLifetimeDefault> {
1290     fn add_bounds(set: &mut Set1<hir::LifetimeName>, bounds: &[hir::GenericBound]) {
1291         for bound in bounds {
1292             if let hir::GenericBound::Outlives(ref lifetime) = *bound {
1293                 set.insert(lifetime.name.modern());
1294             }
1295         }
1296     }
1297
1298     generics.params.iter().filter_map(|param| match param.kind {
1299         GenericParamKind::Lifetime { .. } => None,
1300         GenericParamKind::Type { .. } => {
1301             let mut set = Set1::Empty;
1302
1303             add_bounds(&mut set, &param.bounds);
1304
1305             let param_def_id = tcx.hir.local_def_id(param.id);
1306             for predicate in &generics.where_clause.predicates {
1307                 // Look for `type: ...` where clauses.
1308                 let data = match *predicate {
1309                     hir::WherePredicate::BoundPredicate(ref data) => data,
1310                     _ => continue,
1311                 };
1312
1313                 // Ignore `for<'a> type: ...` as they can change what
1314                 // lifetimes mean (although we could "just" handle it).
1315                 if !data.bound_generic_params.is_empty() {
1316                     continue;
1317                 }
1318
1319                 let def = match data.bounded_ty.node {
1320                     hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => path.def,
1321                     _ => continue,
1322                 };
1323
1324                 if def == Def::TyParam(param_def_id) {
1325                     add_bounds(&mut set, &data.bounds);
1326                 }
1327             }
1328
1329             Some(match set {
1330                 Set1::Empty => Set1::Empty,
1331                 Set1::One(name) => {
1332                     if name == hir::LifetimeName::Static {
1333                         Set1::One(Region::Static)
1334                     } else {
1335                         generics.params.iter().filter_map(|param| match param.kind {
1336                             GenericParamKind::Lifetime { .. } => {
1337                                 Some((
1338                                     param.id,
1339                                     hir::LifetimeName::Param(param.name),
1340                                     LifetimeDefOrigin::from_param(param),
1341                                 ))
1342                             }
1343                             _ => None,
1344                         })
1345                         .enumerate()
1346                         .find(|&(_, (_, lt_name, _))| lt_name == name)
1347                         .map_or(Set1::Many, |(i, (id, _, origin))| {
1348                             let def_id = tcx.hir.local_def_id(id);
1349                             Set1::One(Region::EarlyBound(i as u32, def_id, origin))
1350                         })
1351                     }
1352                 }
1353                 Set1::Many => Set1::Many,
1354             })
1355         }
1356     })
1357     .collect()
1358 }
1359
1360 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
1361     // FIXME(#37666) this works around a limitation in the region inferencer
1362     fn hack<F>(&mut self, f: F)
1363     where
1364         F: for<'b> FnOnce(&mut LifetimeContext<'b, 'tcx>),
1365     {
1366         f(self)
1367     }
1368
1369     fn with<F>(&mut self, wrap_scope: Scope<'_>, f: F)
1370     where
1371         F: for<'b> FnOnce(ScopeRef<'_>, &mut LifetimeContext<'b, 'tcx>),
1372     {
1373         let LifetimeContext {
1374             tcx,
1375             map,
1376             lifetime_uses,
1377             ..
1378         } = self;
1379         let labels_in_fn = replace(&mut self.labels_in_fn, vec![]);
1380         let xcrate_object_lifetime_defaults =
1381             replace(&mut self.xcrate_object_lifetime_defaults, DefIdMap());
1382         let mut this = LifetimeContext {
1383             tcx: *tcx,
1384             map: map,
1385             scope: &wrap_scope,
1386             trait_ref_hack: self.trait_ref_hack,
1387             is_in_fn_syntax: self.is_in_fn_syntax,
1388             labels_in_fn,
1389             xcrate_object_lifetime_defaults,
1390             lifetime_uses: lifetime_uses,
1391         };
1392         debug!("entering scope {:?}", this.scope);
1393         f(self.scope, &mut this);
1394         this.check_uses_for_lifetimes_defined_by_scope();
1395         debug!("exiting scope {:?}", this.scope);
1396         self.labels_in_fn = this.labels_in_fn;
1397         self.xcrate_object_lifetime_defaults = this.xcrate_object_lifetime_defaults;
1398     }
1399
1400     fn check_uses_for_lifetimes_defined_by_scope(&mut self) {
1401         let defined_by = match self.scope {
1402             Scope::Binder { lifetimes, .. } => lifetimes,
1403             _ => {
1404                 debug!("check_uses_for_lifetimes_defined_by_scope: not in a binder scope");
1405                 return;
1406             }
1407         };
1408
1409         let mut def_ids: Vec<_> = defined_by.values()
1410             .flat_map(|region| match region {
1411                 Region::EarlyBound(_, def_id, _)
1412                 | Region::LateBound(_, def_id, _)
1413                 | Region::Free(_, def_id) => Some(*def_id),
1414
1415                 Region::LateBoundAnon(..) | Region::Static => None,
1416             })
1417             .collect();
1418
1419         // ensure that we issue lints in a repeatable order
1420         def_ids.sort_by_key(|&def_id| self.tcx.def_path_hash(def_id));
1421
1422         for def_id in def_ids {
1423             debug!(
1424                 "check_uses_for_lifetimes_defined_by_scope: def_id = {:?}",
1425                 def_id,
1426             );
1427
1428             let lifetimeuseset = self.lifetime_uses.remove(&def_id);
1429             debug!(
1430                 "check_uses_for_lifetimes_defined_by_scope: lifetimeuseset = {:?}",
1431                 lifetimeuseset
1432             );
1433             match lifetimeuseset {
1434                 Some(LifetimeUseSet::One(lifetime)) => {
1435                     let node_id = self.tcx.hir.as_local_node_id(def_id).unwrap();
1436                     debug!("node id first={:?}", node_id);
1437                     if let Some((id, span, name)) = match self.tcx.hir.get(node_id) {
1438                         Node::Lifetime(hir_lifetime) => {
1439                             Some((hir_lifetime.id, hir_lifetime.span, hir_lifetime.name.ident()))
1440                         }
1441                         Node::GenericParam(param) => {
1442                             Some((param.id, param.span, param.name.ident()))
1443                         }
1444                         _ => None,
1445                     } {
1446                         debug!("id = {:?} span = {:?} name = {:?}", node_id, span, name);
1447                         let mut err = self.tcx.struct_span_lint_node(
1448                             lint::builtin::SINGLE_USE_LIFETIMES,
1449                             id,
1450                             span,
1451                             &format!("lifetime parameter `{}` only used once", name),
1452                         );
1453                         err.span_label(span, "this lifetime...");
1454                         err.span_label(lifetime.span, "...is used only here");
1455                         err.emit();
1456                     }
1457                 }
1458                 Some(LifetimeUseSet::Many) => {
1459                     debug!("Not one use lifetime");
1460                 }
1461                 None => {
1462                     let node_id = self.tcx.hir.as_local_node_id(def_id).unwrap();
1463                     if let Some((id, span, name)) = match self.tcx.hir.get(node_id) {
1464                         Node::Lifetime(hir_lifetime) => {
1465                             Some((hir_lifetime.id, hir_lifetime.span, hir_lifetime.name.ident()))
1466                         }
1467                         Node::GenericParam(param) => {
1468                             Some((param.id, param.span, param.name.ident()))
1469                         }
1470                         _ => None,
1471                     } {
1472                         debug!("id ={:?} span = {:?} name = {:?}", node_id, span, name);
1473                         self.tcx.struct_span_lint_node(
1474                             lint::builtin::UNUSED_LIFETIMES,
1475                             id,
1476                             span,
1477                             &format!("lifetime parameter `{}` never used", name)
1478                         ).emit();
1479                     }
1480                 }
1481             }
1482         }
1483     }
1484
1485     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
1486     ///
1487     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
1488     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
1489     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
1490     ///
1491     /// For example:
1492     ///
1493     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
1494     ///
1495     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
1496     /// lifetimes may be interspersed together.
1497     ///
1498     /// If early bound lifetimes are present, we separate them into their own list (and likewise
1499     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
1500     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
1501     /// bound lifetimes are resolved by name and associated with a binder id (`binder_id`), so the
1502     /// ordering is not important there.
1503     fn visit_early_late<F>(
1504         &mut self,
1505         parent_id: Option<ast::NodeId>,
1506         decl: &'tcx hir::FnDecl,
1507         generics: &'tcx hir::Generics,
1508         walk: F,
1509     ) where
1510         F: for<'b, 'c> FnOnce(&'b mut LifetimeContext<'c, 'tcx>),
1511     {
1512         insert_late_bound_lifetimes(self.map, decl, generics);
1513
1514         // Find the start of nested early scopes, e.g. in methods.
1515         let mut index = 0;
1516         if let Some(parent_id) = parent_id {
1517             let parent = self.tcx.hir.expect_item(parent_id);
1518             if let hir::ItemKind::Trait(..) = parent.node {
1519                 index += 1; // Self comes first.
1520             }
1521             match parent.node {
1522                 hir::ItemKind::Trait(_, _, ref generics, ..)
1523                 | hir::ItemKind::Impl(_, _, _, ref generics, ..) => {
1524                     index += generics.params.len() as u32;
1525                 }
1526                 _ => {}
1527             }
1528         }
1529
1530         let mut type_count = 0;
1531         let lifetimes = generics.params.iter().filter_map(|param| match param.kind {
1532             GenericParamKind::Lifetime { .. } => {
1533                 if self.map.late_bound.contains(&param.id) {
1534                     Some(Region::late(&self.tcx.hir, param))
1535                 } else {
1536                     Some(Region::early(&self.tcx.hir, &mut index, param))
1537                 }
1538             }
1539             GenericParamKind::Type { .. } => {
1540                 type_count += 1;
1541                 None
1542             }
1543         }).collect();
1544         let next_early_index = index + type_count;
1545
1546         let scope = Scope::Binder {
1547             lifetimes,
1548             next_early_index,
1549             s: self.scope,
1550             abstract_type_parent: true,
1551             track_lifetime_uses: false,
1552         };
1553         self.with(scope, move |old_scope, this| {
1554             this.check_lifetime_params(old_scope, &generics.params);
1555             this.hack(walk); // FIXME(#37666) workaround in place of `walk(this)`
1556         });
1557     }
1558
1559     fn next_early_index_helper(&self, only_abstract_type_parent: bool) -> u32 {
1560         let mut scope = self.scope;
1561         loop {
1562             match *scope {
1563                 Scope::Root => return 0,
1564
1565                 Scope::Binder {
1566                     next_early_index,
1567                     abstract_type_parent,
1568                     ..
1569                 } if (!only_abstract_type_parent || abstract_type_parent) =>
1570                 {
1571                     return next_early_index
1572                 }
1573
1574                 Scope::Binder { s, .. }
1575                 | Scope::Body { s, .. }
1576                 | Scope::Elision { s, .. }
1577                 | Scope::ObjectLifetimeDefault { s, .. } => scope = s,
1578             }
1579         }
1580     }
1581
1582     /// Returns the next index one would use for an early-bound-region
1583     /// if extending the current scope.
1584     fn next_early_index(&self) -> u32 {
1585         self.next_early_index_helper(true)
1586     }
1587
1588     /// Returns the next index one would use for an `impl Trait` that
1589     /// is being converted into an `abstract type`. This will be the
1590     /// next early index from the enclosing item, for the most
1591     /// part. See the `abstract_type_parent` field for more info.
1592     fn next_early_index_for_abstract_type(&self) -> u32 {
1593         self.next_early_index_helper(false)
1594     }
1595
1596     fn resolve_lifetime_ref(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
1597         debug!("resolve_lifetime_ref(lifetime_ref={:?})", lifetime_ref);
1598         // Walk up the scope chain, tracking the number of fn scopes
1599         // that we pass through, until we find a lifetime with the
1600         // given name or we run out of scopes.
1601         // search.
1602         let mut late_depth = 0;
1603         let mut scope = self.scope;
1604         let mut outermost_body = None;
1605         let result = loop {
1606             match *scope {
1607                 Scope::Body { id, s } => {
1608                     outermost_body = Some(id);
1609                     scope = s;
1610                 }
1611
1612                 Scope::Root => {
1613                     break None;
1614                 }
1615
1616                 Scope::Binder { ref lifetimes, s, .. } => {
1617                     let name = match lifetime_ref.name {
1618                         LifetimeName::Param(param_name) => param_name,
1619                         _ => bug!("expected LifetimeName::Param"),
1620                     };
1621                     if let Some(&def) = lifetimes.get(&name.modern()) {
1622                         break Some(def.shifted(late_depth));
1623                     } else {
1624                         late_depth += 1;
1625                         scope = s;
1626                     }
1627                 }
1628
1629                 Scope::Elision { s, .. } | Scope::ObjectLifetimeDefault { s, .. } => {
1630                     scope = s;
1631                 }
1632             }
1633         };
1634
1635         if let Some(mut def) = result {
1636             if let Region::EarlyBound(..) = def {
1637                 // Do not free early-bound regions, only late-bound ones.
1638             } else if let Some(body_id) = outermost_body {
1639                 let fn_id = self.tcx.hir.body_owner(body_id);
1640                 match self.tcx.hir.get(fn_id) {
1641                     Node::Item(&hir::Item {
1642                         node: hir::ItemKind::Fn(..),
1643                         ..
1644                     })
1645                     | Node::TraitItem(&hir::TraitItem {
1646                         node: hir::TraitItemKind::Method(..),
1647                         ..
1648                     })
1649                     | Node::ImplItem(&hir::ImplItem {
1650                         node: hir::ImplItemKind::Method(..),
1651                         ..
1652                     }) => {
1653                         let scope = self.tcx.hir.local_def_id(fn_id);
1654                         def = Region::Free(scope, def.id().unwrap());
1655                     }
1656                     _ => {}
1657                 }
1658             }
1659
1660             // Check for fn-syntax conflicts with in-band lifetime definitions
1661             if self.is_in_fn_syntax {
1662                 match def {
1663                     Region::EarlyBound(_, _, LifetimeDefOrigin::InBand)
1664                     | Region::LateBound(_, _, LifetimeDefOrigin::InBand) => {
1665                         struct_span_err!(
1666                             self.tcx.sess,
1667                             lifetime_ref.span,
1668                             E0687,
1669                             "lifetimes used in `fn` or `Fn` syntax must be \
1670                              explicitly declared using `<...>` binders"
1671                         ).span_label(lifetime_ref.span, "in-band lifetime definition")
1672                             .emit();
1673                     }
1674
1675                     Region::Static
1676                     | Region::EarlyBound(_, _, LifetimeDefOrigin::Explicit)
1677                     | Region::LateBound(_, _, LifetimeDefOrigin::Explicit)
1678                     | Region::LateBoundAnon(..)
1679                     | Region::Free(..) => {}
1680                 }
1681             }
1682
1683             self.insert_lifetime(lifetime_ref, def);
1684         } else {
1685             struct_span_err!(
1686                 self.tcx.sess,
1687                 lifetime_ref.span,
1688                 E0261,
1689                 "use of undeclared lifetime name `{}`",
1690                 lifetime_ref
1691             ).span_label(lifetime_ref.span, "undeclared lifetime")
1692                 .emit();
1693         }
1694     }
1695
1696     fn visit_segment_args(
1697         &mut self,
1698         def: Def,
1699         depth: usize,
1700         generic_args: &'tcx hir::GenericArgs,
1701     ) {
1702         if generic_args.parenthesized {
1703             let was_in_fn_syntax = self.is_in_fn_syntax;
1704             self.is_in_fn_syntax = true;
1705             self.visit_fn_like_elision(generic_args.inputs(),
1706                                        Some(&generic_args.bindings[0].ty));
1707             self.is_in_fn_syntax = was_in_fn_syntax;
1708             return;
1709         }
1710
1711         let mut elide_lifetimes = true;
1712         let lifetimes = generic_args.args.iter().filter_map(|arg| match arg {
1713             hir::GenericArg::Lifetime(lt) => {
1714                 if !lt.is_elided() {
1715                     elide_lifetimes = false;
1716                 }
1717                 Some(lt)
1718             }
1719             _ => None,
1720         }).collect();
1721         if elide_lifetimes {
1722             self.resolve_elided_lifetimes(lifetimes);
1723         } else {
1724             lifetimes.iter().for_each(|lt| self.visit_lifetime(lt));
1725         }
1726
1727         // Figure out if this is a type/trait segment,
1728         // which requires object lifetime defaults.
1729         let parent_def_id = |this: &mut Self, def_id: DefId| {
1730             let def_key = this.tcx.def_key(def_id);
1731             DefId {
1732                 krate: def_id.krate,
1733                 index: def_key.parent.expect("missing parent"),
1734             }
1735         };
1736         let type_def_id = match def {
1737             Def::AssociatedTy(def_id) if depth == 1 => Some(parent_def_id(self, def_id)),
1738             Def::Variant(def_id) if depth == 0 => Some(parent_def_id(self, def_id)),
1739             Def::Struct(def_id)
1740             | Def::Union(def_id)
1741             | Def::Enum(def_id)
1742             | Def::TyAlias(def_id)
1743             | Def::Trait(def_id) if depth == 0 =>
1744             {
1745                 Some(def_id)
1746             }
1747             _ => None,
1748         };
1749
1750         let object_lifetime_defaults = type_def_id.map_or(vec![], |def_id| {
1751             let in_body = {
1752                 let mut scope = self.scope;
1753                 loop {
1754                     match *scope {
1755                         Scope::Root => break false,
1756
1757                         Scope::Body { .. } => break true,
1758
1759                         Scope::Binder { s, .. }
1760                         | Scope::Elision { s, .. }
1761                         | Scope::ObjectLifetimeDefault { s, .. } => {
1762                             scope = s;
1763                         }
1764                     }
1765                 }
1766             };
1767
1768             let map = &self.map;
1769             let unsubst = if let Some(id) = self.tcx.hir.as_local_node_id(def_id) {
1770                 &map.object_lifetime_defaults[&id]
1771             } else {
1772                 let tcx = self.tcx;
1773                 self.xcrate_object_lifetime_defaults
1774                     .entry(def_id)
1775                     .or_insert_with(|| {
1776                         tcx.generics_of(def_id).params.iter().filter_map(|param| {
1777                             match param.kind {
1778                                 GenericParamDefKind::Type { object_lifetime_default, .. } => {
1779                                     Some(object_lifetime_default)
1780                                 }
1781                                 GenericParamDefKind::Lifetime => None,
1782                             }
1783                         }).collect()
1784                     })
1785             };
1786             unsubst.iter()
1787                    .map(|set| match *set {
1788                        Set1::Empty => if in_body {
1789                            None
1790                        } else {
1791                            Some(Region::Static)
1792                        },
1793                        Set1::One(r) => {
1794                            let lifetimes = generic_args.args.iter().filter_map(|arg| match arg {
1795                                GenericArg::Lifetime(lt) => Some(lt),
1796                                _ => None,
1797                            });
1798                            r.subst(lifetimes, map)
1799                        }
1800                        Set1::Many => None,
1801                    })
1802                    .collect()
1803         });
1804
1805         let mut i = 0;
1806         for arg in &generic_args.args {
1807             match arg {
1808                 GenericArg::Lifetime(_) => {}
1809                 GenericArg::Type(ty) => {
1810                     if let Some(&lt) = object_lifetime_defaults.get(i) {
1811                         let scope = Scope::ObjectLifetimeDefault {
1812                             lifetime: lt,
1813                             s: self.scope,
1814                         };
1815                         self.with(scope, |_, this| this.visit_ty(ty));
1816                     } else {
1817                         self.visit_ty(ty);
1818                     }
1819                     i += 1;
1820                 }
1821             }
1822         }
1823
1824         for b in &generic_args.bindings {
1825             self.visit_assoc_type_binding(b);
1826         }
1827     }
1828
1829     fn visit_fn_like_elision(
1830         &mut self,
1831         inputs: &'tcx [hir::Ty],
1832         output: Option<&'tcx P<hir::Ty>>,
1833     ) {
1834         debug!("visit_fn_like_elision: enter");
1835         let mut arg_elide = Elide::FreshLateAnon(Cell::new(0));
1836         let arg_scope = Scope::Elision {
1837             elide: arg_elide.clone(),
1838             s: self.scope,
1839         };
1840         self.with(arg_scope, |_, this| {
1841             for input in inputs {
1842                 this.visit_ty(input);
1843             }
1844             match *this.scope {
1845                 Scope::Elision { ref elide, .. } => {
1846                     arg_elide = elide.clone();
1847                 }
1848                 _ => bug!(),
1849             }
1850         });
1851
1852         let output = match output {
1853             Some(ty) => ty,
1854             None => return,
1855         };
1856
1857         debug!("visit_fn_like_elision: determine output");
1858
1859         // Figure out if there's a body we can get argument names from,
1860         // and whether there's a `self` argument (treated specially).
1861         let mut assoc_item_kind = None;
1862         let mut impl_self = None;
1863         let parent = self.tcx.hir.get_parent_node(output.id);
1864         let body = match self.tcx.hir.get(parent) {
1865             // `fn` definitions and methods.
1866             Node::Item(&hir::Item {
1867                 node: hir::ItemKind::Fn(.., body),
1868                 ..
1869             }) => Some(body),
1870
1871             Node::TraitItem(&hir::TraitItem {
1872                 node: hir::TraitItemKind::Method(_, ref m),
1873                 ..
1874             }) => {
1875                 match self.tcx
1876                     .hir
1877                     .expect_item(self.tcx.hir.get_parent(parent))
1878                     .node
1879                 {
1880                     hir::ItemKind::Trait(.., ref trait_items) => {
1881                         assoc_item_kind = trait_items
1882                             .iter()
1883                             .find(|ti| ti.id.node_id == parent)
1884                             .map(|ti| ti.kind);
1885                     }
1886                     _ => {}
1887                 }
1888                 match *m {
1889                     hir::TraitMethod::Required(_) => None,
1890                     hir::TraitMethod::Provided(body) => Some(body),
1891                 }
1892             }
1893
1894             Node::ImplItem(&hir::ImplItem {
1895                 node: hir::ImplItemKind::Method(_, body),
1896                 ..
1897             }) => {
1898                 match self.tcx
1899                     .hir
1900                     .expect_item(self.tcx.hir.get_parent(parent))
1901                     .node
1902                 {
1903                     hir::ItemKind::Impl(.., ref self_ty, ref impl_items) => {
1904                         impl_self = Some(self_ty);
1905                         assoc_item_kind = impl_items
1906                             .iter()
1907                             .find(|ii| ii.id.node_id == parent)
1908                             .map(|ii| ii.kind);
1909                     }
1910                     _ => {}
1911                 }
1912                 Some(body)
1913             }
1914
1915             // Foreign functions, `fn(...) -> R` and `Trait(...) -> R` (both types and bounds).
1916             Node::ForeignItem(_) | Node::Ty(_) | Node::TraitRef(_) => None,
1917             // Everything else (only closures?) doesn't
1918             // actually enjoy elision in return types.
1919             _ => {
1920                 self.visit_ty(output);
1921                 return;
1922             }
1923         };
1924
1925         let has_self = match assoc_item_kind {
1926             Some(hir::AssociatedItemKind::Method { has_self }) => has_self,
1927             _ => false,
1928         };
1929
1930         // In accordance with the rules for lifetime elision, we can determine
1931         // what region to use for elision in the output type in two ways.
1932         // First (determined here), if `self` is by-reference, then the
1933         // implied output region is the region of the self parameter.
1934         if has_self {
1935             // Look for `self: &'a Self` - also desugared from `&'a self`,
1936             // and if that matches, use it for elision and return early.
1937             let is_self_ty = |def: Def| {
1938                 if let Def::SelfTy(..) = def {
1939                     return true;
1940                 }
1941
1942                 // Can't always rely on literal (or implied) `Self` due
1943                 // to the way elision rules were originally specified.
1944                 let impl_self = impl_self.map(|ty| &ty.node);
1945                 if let Some(&hir::TyKind::Path(hir::QPath::Resolved(None, ref path))) = impl_self {
1946                     match path.def {
1947                         // Whitelist the types that unambiguously always
1948                         // result in the same type constructor being used
1949                         // (it can't differ between `Self` and `self`).
1950                         Def::Struct(_) | Def::Union(_) | Def::Enum(_) | Def::PrimTy(_) => {
1951                             return def == path.def
1952                         }
1953                         _ => {}
1954                     }
1955                 }
1956
1957                 false
1958             };
1959
1960             if let hir::TyKind::Rptr(lifetime_ref, ref mt) = inputs[0].node {
1961                 if let hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) = mt.ty.node {
1962                     if is_self_ty(path.def) {
1963                         if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
1964                             let scope = Scope::Elision {
1965                                 elide: Elide::Exact(lifetime),
1966                                 s: self.scope,
1967                             };
1968                             self.with(scope, |_, this| this.visit_ty(output));
1969                             return;
1970                         }
1971                     }
1972                 }
1973             }
1974         }
1975
1976         // Second, if there was exactly one lifetime (either a substitution or a
1977         // reference) in the arguments, then any anonymous regions in the output
1978         // have that lifetime.
1979         let mut possible_implied_output_region = None;
1980         let mut lifetime_count = 0;
1981         let arg_lifetimes = inputs
1982             .iter()
1983             .enumerate()
1984             .skip(has_self as usize)
1985             .map(|(i, input)| {
1986                 let mut gather = GatherLifetimes {
1987                     map: self.map,
1988                     outer_index: ty::INNERMOST,
1989                     have_bound_regions: false,
1990                     lifetimes: FxHashSet(),
1991                 };
1992                 gather.visit_ty(input);
1993
1994                 lifetime_count += gather.lifetimes.len();
1995
1996                 if lifetime_count == 1 && gather.lifetimes.len() == 1 {
1997                     // there's a chance that the unique lifetime of this
1998                     // iteration will be the appropriate lifetime for output
1999                     // parameters, so lets store it.
2000                     possible_implied_output_region = gather.lifetimes.iter().cloned().next();
2001                 }
2002
2003                 ElisionFailureInfo {
2004                     parent: body,
2005                     index: i,
2006                     lifetime_count: gather.lifetimes.len(),
2007                     have_bound_regions: gather.have_bound_regions,
2008                 }
2009             })
2010             .collect();
2011
2012         let elide = if lifetime_count == 1 {
2013             Elide::Exact(possible_implied_output_region.unwrap())
2014         } else {
2015             Elide::Error(arg_lifetimes)
2016         };
2017
2018         debug!("visit_fn_like_elision: elide={:?}", elide);
2019
2020         let scope = Scope::Elision {
2021             elide,
2022             s: self.scope,
2023         };
2024         self.with(scope, |_, this| this.visit_ty(output));
2025         debug!("visit_fn_like_elision: exit");
2026
2027         struct GatherLifetimes<'a> {
2028             map: &'a NamedRegionMap,
2029             outer_index: ty::DebruijnIndex,
2030             have_bound_regions: bool,
2031             lifetimes: FxHashSet<Region>,
2032         }
2033
2034         impl<'v, 'a> Visitor<'v> for GatherLifetimes<'a> {
2035             fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2036                 NestedVisitorMap::None
2037             }
2038
2039             fn visit_ty(&mut self, ty: &hir::Ty) {
2040                 if let hir::TyKind::BareFn(_) = ty.node {
2041                     self.outer_index.shift_in(1);
2042                 }
2043                 if let hir::TyKind::TraitObject(ref bounds, ref lifetime) = ty.node {
2044                     for bound in bounds {
2045                         self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
2046                     }
2047
2048                     // Stay on the safe side and don't include the object
2049                     // lifetime default (which may not end up being used).
2050                     if !lifetime.is_elided() {
2051                         self.visit_lifetime(lifetime);
2052                     }
2053                 } else {
2054                     intravisit::walk_ty(self, ty);
2055                 }
2056                 if let hir::TyKind::BareFn(_) = ty.node {
2057                     self.outer_index.shift_out(1);
2058                 }
2059             }
2060
2061             fn visit_generic_param(&mut self, param: &hir::GenericParam) {
2062                 if let hir::GenericParamKind::Lifetime { .. } = param.kind {
2063                     // FIXME(eddyb) Do we want this? It only makes a difference
2064                     // if this `for<'a>` lifetime parameter is never used.
2065                     self.have_bound_regions = true;
2066                 }
2067
2068                 intravisit::walk_generic_param(self, param);
2069             }
2070
2071             fn visit_poly_trait_ref(
2072                 &mut self,
2073                 trait_ref: &hir::PolyTraitRef,
2074                 modifier: hir::TraitBoundModifier,
2075             ) {
2076                 self.outer_index.shift_in(1);
2077                 intravisit::walk_poly_trait_ref(self, trait_ref, modifier);
2078                 self.outer_index.shift_out(1);
2079             }
2080
2081             fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
2082                 if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
2083                     match lifetime {
2084                         Region::LateBound(debruijn, _, _) | Region::LateBoundAnon(debruijn, _)
2085                             if debruijn < self.outer_index =>
2086                         {
2087                             self.have_bound_regions = true;
2088                         }
2089                         _ => {
2090                             self.lifetimes
2091                                 .insert(lifetime.shifted_out_to_binder(self.outer_index));
2092                         }
2093                     }
2094                 }
2095             }
2096         }
2097     }
2098
2099     fn resolve_elided_lifetimes(&mut self,
2100                                 lifetime_refs: Vec<&'tcx hir::Lifetime>) {
2101         if lifetime_refs.is_empty() {
2102             return;
2103         }
2104
2105         let span = lifetime_refs[0].span;
2106         let mut late_depth = 0;
2107         let mut scope = self.scope;
2108         let error = loop {
2109             match *scope {
2110                 // Do not assign any resolution, it will be inferred.
2111                 Scope::Body { .. } => return,
2112
2113                 Scope::Root => break None,
2114
2115                 Scope::Binder { s, .. } => {
2116                     late_depth += 1;
2117                     scope = s;
2118                 }
2119
2120                 Scope::Elision { ref elide, .. } => {
2121                     let lifetime = match *elide {
2122                         Elide::FreshLateAnon(ref counter) => {
2123                             for lifetime_ref in lifetime_refs {
2124                                 let lifetime = Region::late_anon(counter).shifted(late_depth);
2125                                 self.insert_lifetime(lifetime_ref, lifetime);
2126                             }
2127                             return;
2128                         }
2129                         Elide::Exact(l) => l.shifted(late_depth),
2130                         Elide::Error(ref e) => break Some(e),
2131                     };
2132                     for lifetime_ref in lifetime_refs {
2133                         self.insert_lifetime(lifetime_ref, lifetime);
2134                     }
2135                     return;
2136                 }
2137
2138                 Scope::ObjectLifetimeDefault { s, .. } => {
2139                     scope = s;
2140                 }
2141             }
2142         };
2143
2144         let mut err = report_missing_lifetime_specifiers(self.tcx.sess, span, lifetime_refs.len());
2145
2146         if let Some(params) = error {
2147             if lifetime_refs.len() == 1 {
2148                 self.report_elision_failure(&mut err, params);
2149             }
2150         }
2151
2152         err.emit();
2153     }
2154
2155     fn report_elision_failure(
2156         &mut self,
2157         db: &mut DiagnosticBuilder<'_>,
2158         params: &[ElisionFailureInfo],
2159     ) {
2160         let mut m = String::new();
2161         let len = params.len();
2162
2163         let elided_params: Vec<_> = params
2164             .iter()
2165             .cloned()
2166             .filter(|info| info.lifetime_count > 0)
2167             .collect();
2168
2169         let elided_len = elided_params.len();
2170
2171         for (i, info) in elided_params.into_iter().enumerate() {
2172             let ElisionFailureInfo {
2173                 parent,
2174                 index,
2175                 lifetime_count: n,
2176                 have_bound_regions,
2177             } = info;
2178
2179             let help_name = if let Some(body) = parent {
2180                 let arg = &self.tcx.hir.body(body).arguments[index];
2181                 format!("`{}`", self.tcx.hir.node_to_pretty_string(arg.pat.id))
2182             } else {
2183                 format!("argument {}", index + 1)
2184             };
2185
2186             m.push_str(
2187                 &(if n == 1 {
2188                     help_name
2189                 } else {
2190                     format!(
2191                         "one of {}'s {} {}lifetimes",
2192                         help_name,
2193                         n,
2194                         if have_bound_regions { "free " } else { "" }
2195                     )
2196                 })[..],
2197             );
2198
2199             if elided_len == 2 && i == 0 {
2200                 m.push_str(" or ");
2201             } else if i + 2 == elided_len {
2202                 m.push_str(", or ");
2203             } else if i != elided_len - 1 {
2204                 m.push_str(", ");
2205             }
2206         }
2207
2208         if len == 0 {
2209             help!(
2210                 db,
2211                 "this function's return type contains a borrowed value, but \
2212                  there is no value for it to be borrowed from"
2213             );
2214             help!(db, "consider giving it a 'static lifetime");
2215         } else if elided_len == 0 {
2216             help!(
2217                 db,
2218                 "this function's return type contains a borrowed value with \
2219                  an elided lifetime, but the lifetime cannot be derived from \
2220                  the arguments"
2221             );
2222             help!(
2223                 db,
2224                 "consider giving it an explicit bounded or 'static \
2225                  lifetime"
2226             );
2227         } else if elided_len == 1 {
2228             help!(
2229                 db,
2230                 "this function's return type contains a borrowed value, but \
2231                  the signature does not say which {} it is borrowed from",
2232                 m
2233             );
2234         } else {
2235             help!(
2236                 db,
2237                 "this function's return type contains a borrowed value, but \
2238                  the signature does not say whether it is borrowed from {}",
2239                 m
2240             );
2241         }
2242     }
2243
2244     fn resolve_object_lifetime_default(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
2245         let mut late_depth = 0;
2246         let mut scope = self.scope;
2247         let lifetime = loop {
2248             match *scope {
2249                 Scope::Binder { s, .. } => {
2250                     late_depth += 1;
2251                     scope = s;
2252                 }
2253
2254                 Scope::Root | Scope::Elision { .. } => break Region::Static,
2255
2256                 Scope::Body { .. } | Scope::ObjectLifetimeDefault { lifetime: None, .. } => return,
2257
2258                 Scope::ObjectLifetimeDefault {
2259                     lifetime: Some(l), ..
2260                 } => break l,
2261             }
2262         };
2263         self.insert_lifetime(lifetime_ref, lifetime.shifted(late_depth));
2264     }
2265
2266     fn check_lifetime_params(&mut self, old_scope: ScopeRef<'_>,
2267                              params: &'tcx [hir::GenericParam]) {
2268         let lifetimes: Vec<_> = params.iter().filter_map(|param| match param.kind {
2269             GenericParamKind::Lifetime { .. } => Some((param, param.name)),
2270             _ => None,
2271         }).collect();
2272         for (i, (lifetime_i, lifetime_i_name)) in lifetimes.iter().enumerate() {
2273             if let hir::ParamName::Plain(_) = lifetime_i_name {
2274                 let name = lifetime_i_name.ident().name;
2275                 if name == keywords::UnderscoreLifetime.name() ||
2276                    name == keywords::StaticLifetime.name() {
2277                     let mut err = struct_span_err!(
2278                         self.tcx.sess,
2279                         lifetime_i.span,
2280                         E0262,
2281                         "invalid lifetime parameter name: `{}`",
2282                         lifetime_i.name.ident(),
2283                     );
2284                     err.span_label(
2285                         lifetime_i.span,
2286                         format!("{} is a reserved lifetime name", name),
2287                     );
2288                     err.emit();
2289                 }
2290             }
2291
2292             // It is a hard error to shadow a lifetime within the same scope.
2293             for (lifetime_j, lifetime_j_name) in lifetimes.iter().skip(i + 1) {
2294                 if lifetime_i_name == lifetime_j_name {
2295                     struct_span_err!(
2296                         self.tcx.sess,
2297                         lifetime_j.span,
2298                         E0263,
2299                         "lifetime name `{}` declared twice in the same scope",
2300                         lifetime_j.name.ident()
2301                     ).span_label(lifetime_j.span, "declared twice")
2302                      .span_label(lifetime_i.span, "previous declaration here")
2303                      .emit();
2304                 }
2305             }
2306
2307             // It is a soft error to shadow a lifetime within a parent scope.
2308             self.check_lifetime_param_for_shadowing(old_scope, &lifetime_i);
2309
2310             for bound in &lifetime_i.bounds {
2311                 match bound {
2312                     hir::GenericBound::Outlives(lt) => match lt.name {
2313                         hir::LifetimeName::Underscore => {
2314                             let mut err = struct_span_err!(
2315                                 self.tcx.sess,
2316                                 lt.span,
2317                                 E0637,
2318                                 "invalid lifetime bound name: `'_`"
2319                             );
2320                             err.span_label(lt.span, "`'_` is a reserved lifetime name");
2321                             err.emit();
2322                         }
2323                         hir::LifetimeName::Static => {
2324                             self.insert_lifetime(lt, Region::Static);
2325                             self.tcx.sess.struct_span_warn(
2326                                 lifetime_i.span.to(lt.span),
2327                                 &format!(
2328                                     "unnecessary lifetime parameter `{}`",
2329                                     lifetime_i.name.ident(),
2330                                 ),
2331                             ).help(&format!(
2332                                 "you can use the `'static` lifetime directly, in place \
2333                                     of `{}`",
2334                                 lifetime_i.name.ident(),
2335                             )).emit();
2336                         }
2337                         hir::LifetimeName::Param(_)
2338                         | hir::LifetimeName::Implicit => {
2339                             self.resolve_lifetime_ref(lt);
2340                         }
2341                     }
2342                     _ => bug!(),
2343                 }
2344             }
2345         }
2346     }
2347
2348     fn check_lifetime_param_for_shadowing(
2349         &self,
2350         mut old_scope: ScopeRef<'_>,
2351         param: &'tcx hir::GenericParam,
2352     ) {
2353         for label in &self.labels_in_fn {
2354             // FIXME (#24278): non-hygienic comparison
2355             if param.name.ident().name == label.name {
2356                 signal_shadowing_problem(
2357                     self.tcx,
2358                     label.name,
2359                     original_label(label.span),
2360                     shadower_lifetime(&param),
2361                 );
2362                 return;
2363             }
2364         }
2365
2366         loop {
2367             match *old_scope {
2368                 Scope::Body { s, .. }
2369                 | Scope::Elision { s, .. }
2370                 | Scope::ObjectLifetimeDefault { s, .. } => {
2371                     old_scope = s;
2372                 }
2373
2374                 Scope::Root => {
2375                     return;
2376                 }
2377
2378                 Scope::Binder {
2379                     ref lifetimes, s, ..
2380                 } => {
2381                     if let Some(&def) = lifetimes.get(&param.name.modern()) {
2382                         let node_id = self.tcx.hir.as_local_node_id(def.id().unwrap()).unwrap();
2383
2384                         signal_shadowing_problem(
2385                             self.tcx,
2386                             param.name.ident().name,
2387                             original_lifetime(self.tcx.hir.span(node_id)),
2388                             shadower_lifetime(&param),
2389                         );
2390                         return;
2391                     }
2392
2393                     old_scope = s;
2394                 }
2395             }
2396         }
2397     }
2398
2399     /// Returns true if, in the current scope, replacing `'_` would be
2400     /// equivalent to a single-use lifetime.
2401     fn track_lifetime_uses(&self) -> bool {
2402         let mut scope = self.scope;
2403         loop {
2404             match *scope {
2405                 Scope::Root => break false,
2406
2407                 // Inside of items, it depends on the kind of item.
2408                 Scope::Binder {
2409                     track_lifetime_uses,
2410                     ..
2411                 } => break track_lifetime_uses,
2412
2413                 // Inside a body, `'_` will use an inference variable,
2414                 // should be fine.
2415                 Scope::Body { .. } => break true,
2416
2417                 // A lifetime only used in a fn argument could as well
2418                 // be replaced with `'_`, as that would generate a
2419                 // fresh name, too.
2420                 Scope::Elision {
2421                     elide: Elide::FreshLateAnon(_),
2422                     ..
2423                 } => break true,
2424
2425                 // In the return type or other such place, `'_` is not
2426                 // going to make a fresh name, so we cannot
2427                 // necessarily replace a single-use lifetime with
2428                 // `'_`.
2429                 Scope::Elision {
2430                     elide: Elide::Exact(_),
2431                     ..
2432                 } => break false,
2433                 Scope::Elision {
2434                     elide: Elide::Error(_),
2435                     ..
2436                 } => break false,
2437
2438                 Scope::ObjectLifetimeDefault { s, .. } => scope = s,
2439             }
2440         }
2441     }
2442
2443     fn insert_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime, def: Region) {
2444         if lifetime_ref.id == ast::DUMMY_NODE_ID {
2445             span_bug!(
2446                 lifetime_ref.span,
2447                 "lifetime reference not renumbered, \
2448                  probably a bug in syntax::fold"
2449             );
2450         }
2451
2452         debug!(
2453             "insert_lifetime: {} resolved to {:?} span={:?}",
2454             self.tcx.hir.node_to_string(lifetime_ref.id),
2455             def,
2456             self.tcx.sess.source_map().span_to_string(lifetime_ref.span)
2457         );
2458         self.map.defs.insert(lifetime_ref.id, def);
2459
2460         match def {
2461             Region::LateBoundAnon(..) | Region::Static => {
2462                 // These are anonymous lifetimes or lifetimes that are not declared.
2463             }
2464
2465             Region::Free(_, def_id)
2466             | Region::LateBound(_, def_id, _)
2467             | Region::EarlyBound(_, def_id, _) => {
2468                 // A lifetime declared by the user.
2469                 let track_lifetime_uses = self.track_lifetime_uses();
2470                 debug!(
2471                     "insert_lifetime: track_lifetime_uses={}",
2472                     track_lifetime_uses
2473                 );
2474                 if track_lifetime_uses && !self.lifetime_uses.contains_key(&def_id) {
2475                     debug!("insert_lifetime: first use of {:?}", def_id);
2476                     self.lifetime_uses
2477                         .insert(def_id, LifetimeUseSet::One(lifetime_ref));
2478                 } else {
2479                     debug!("insert_lifetime: many uses of {:?}", def_id);
2480                     self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
2481                 }
2482             }
2483         }
2484     }
2485
2486     /// Sometimes we resolve a lifetime, but later find that it is an
2487     /// error (esp. around impl trait). In that case, we remove the
2488     /// entry into `map.defs` so as not to confuse later code.
2489     fn uninsert_lifetime_on_error(&mut self, lifetime_ref: &'tcx hir::Lifetime, bad_def: Region) {
2490         let old_value = self.map.defs.remove(&lifetime_ref.id);
2491         assert_eq!(old_value, Some(bad_def));
2492     }
2493 }
2494
2495 ///////////////////////////////////////////////////////////////////////////
2496
2497 /// Detects late-bound lifetimes and inserts them into
2498 /// `map.late_bound`.
2499 ///
2500 /// A region declared on a fn is **late-bound** if:
2501 /// - it is constrained by an argument type;
2502 /// - it does not appear in a where-clause.
2503 ///
2504 /// "Constrained" basically means that it appears in any type but
2505 /// not amongst the inputs to a projection.  In other words, `<&'a
2506 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
2507 fn insert_late_bound_lifetimes(
2508     map: &mut NamedRegionMap,
2509     decl: &hir::FnDecl,
2510     generics: &hir::Generics,
2511 ) {
2512     debug!(
2513         "insert_late_bound_lifetimes(decl={:?}, generics={:?})",
2514         decl, generics
2515     );
2516
2517     let mut constrained_by_input = ConstrainedCollector {
2518         regions: FxHashSet(),
2519     };
2520     for arg_ty in &decl.inputs {
2521         constrained_by_input.visit_ty(arg_ty);
2522     }
2523
2524     let mut appears_in_output = AllCollector {
2525         regions: FxHashSet(),
2526     };
2527     intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
2528
2529     debug!(
2530         "insert_late_bound_lifetimes: constrained_by_input={:?}",
2531         constrained_by_input.regions
2532     );
2533
2534     // Walk the lifetimes that appear in where clauses.
2535     //
2536     // Subtle point: because we disallow nested bindings, we can just
2537     // ignore binders here and scrape up all names we see.
2538     let mut appears_in_where_clause = AllCollector {
2539         regions: FxHashSet(),
2540     };
2541     appears_in_where_clause.visit_generics(generics);
2542
2543     for param in &generics.params {
2544         match param.kind {
2545             hir::GenericParamKind::Lifetime { .. } => {
2546                 if !param.bounds.is_empty() {
2547                     // `'a: 'b` means both `'a` and `'b` are referenced
2548                     appears_in_where_clause
2549                         .regions.insert(hir::LifetimeName::Param(param.name.modern()));
2550                 }
2551             }
2552             hir::GenericParamKind::Type { .. } => {}
2553         }
2554     }
2555
2556     debug!(
2557         "insert_late_bound_lifetimes: appears_in_where_clause={:?}",
2558         appears_in_where_clause.regions
2559     );
2560
2561     // Late bound regions are those that:
2562     // - appear in the inputs
2563     // - do not appear in the where-clauses
2564     // - are not implicitly captured by `impl Trait`
2565     for param in &generics.params {
2566         match param.kind {
2567             hir::GenericParamKind::Lifetime { .. } => { /* fall through */ }
2568
2569             // Types are not late-bound.
2570             hir::GenericParamKind::Type { .. } => continue,
2571         }
2572
2573         let lt_name = hir::LifetimeName::Param(param.name.modern());
2574         // appears in the where clauses? early-bound.
2575         if appears_in_where_clause.regions.contains(&lt_name) {
2576             continue;
2577         }
2578
2579         // does not appear in the inputs, but appears in the return type? early-bound.
2580         if !constrained_by_input.regions.contains(&lt_name)
2581             && appears_in_output.regions.contains(&lt_name)
2582         {
2583             continue;
2584         }
2585
2586         debug!("insert_late_bound_lifetimes: lifetime {:?} with id {:?} is late-bound",
2587                param.name.ident(),
2588                param.id);
2589
2590         let inserted = map.late_bound.insert(param.id);
2591         assert!(inserted, "visited lifetime {:?} twice", param.id);
2592     }
2593
2594     return;
2595
2596     struct ConstrainedCollector {
2597         regions: FxHashSet<hir::LifetimeName>,
2598     }
2599
2600     impl<'v> Visitor<'v> for ConstrainedCollector {
2601         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2602             NestedVisitorMap::None
2603         }
2604
2605         fn visit_ty(&mut self, ty: &'v hir::Ty) {
2606             match ty.node {
2607                 hir::TyKind::Path(hir::QPath::Resolved(Some(_), _))
2608                 | hir::TyKind::Path(hir::QPath::TypeRelative(..)) => {
2609                     // ignore lifetimes appearing in associated type
2610                     // projections, as they are not *constrained*
2611                     // (defined above)
2612                 }
2613
2614                 hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
2615                     // consider only the lifetimes on the final
2616                     // segment; I am not sure it's even currently
2617                     // valid to have them elsewhere, but even if it
2618                     // is, those would be potentially inputs to
2619                     // projections
2620                     if let Some(last_segment) = path.segments.last() {
2621                         self.visit_path_segment(path.span, last_segment);
2622                     }
2623                 }
2624
2625                 _ => {
2626                     intravisit::walk_ty(self, ty);
2627                 }
2628             }
2629         }
2630
2631         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
2632             self.regions.insert(lifetime_ref.name.modern());
2633         }
2634     }
2635
2636     struct AllCollector {
2637         regions: FxHashSet<hir::LifetimeName>,
2638     }
2639
2640     impl<'v> Visitor<'v> for AllCollector {
2641         fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> {
2642             NestedVisitorMap::None
2643         }
2644
2645         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
2646             self.regions.insert(lifetime_ref.name.modern());
2647         }
2648     }
2649 }
2650
2651 pub fn report_missing_lifetime_specifiers(
2652     sess: &Session,
2653     span: Span,
2654     count: usize,
2655 ) -> DiagnosticBuilder<'_> {
2656     let mut err = struct_span_err!(
2657         sess,
2658         span,
2659         E0106,
2660         "missing lifetime specifier{}",
2661         if count > 1 { "s" } else { "" }
2662     );
2663
2664     let msg = if count > 1 {
2665         format!("expected {} lifetime parameters", count)
2666     } else {
2667         "expected lifetime parameter".to_string()
2668     };
2669
2670     err.span_label(span, msg);
2671
2672     err
2673 }