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