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