src/librustc/middle/resolve_lifetime.rs

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