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