compiler/rustc_resolve/src/late/lifetimes.rs

   1 // ignore-tidy-filelength
   2 //! Name resolution for lifetimes.
   3 //!
   4 //! Name resolution for lifetimes follows *much* simpler rules than the
   5 //! full resolve. For example, lifetime names are never exported or
   6 //! used between functions, and they operate in a purely top-down
   7 //! way. Therefore, we break lifetime name resolution into a separate pass.
   8
   9 use crate::late::diagnostics::{ForLifetimeSpanType, MissingLifetimeSpot};
  10 use rustc_ast::walk_list;
  11 use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexMap};
  12 use rustc_errors::{struct_span_err, Applicability, Diagnostic};
  13 use rustc_hir as hir;
  14 use rustc_hir::def::{DefKind, Res};
  15 use rustc_hir::def_id::{DefIdMap, LocalDefId};
  16 use rustc_hir::hir_id::ItemLocalId;
  17 use rustc_hir::intravisit::{self, Visitor};
  18 use rustc_hir::{GenericArg, GenericParam, LifetimeName, Node, ParamName, QPath};
  19 use rustc_hir::{GenericParamKind, HirIdMap, HirIdSet};
  20 use rustc_middle::hir::map::Map;
  21 use rustc_middle::hir::nested_filter;
  22 use rustc_middle::middle::resolve_lifetime::*;
  23 use rustc_middle::ty::{self, DefIdTree, GenericParamDefKind, TyCtxt};
  24 use rustc_middle::{bug, span_bug};
  25 use rustc_session::lint;
  26 use rustc_span::def_id::DefId;
  27 use rustc_span::symbol::{kw, sym, Ident, Symbol};
  28 use rustc_span::Span;
  29 use std::borrow::Cow;
  30 use std::cell::Cell;
  31 use std::fmt;
  32 use std::mem::take;
  33
  34 use tracing::{debug, span, Level};
  35
  36 // This counts the no of times a lifetime is used
  37 #[derive(Clone, Copy, Debug)]
  38 pub enum LifetimeUseSet<'tcx> {
  39     One(&'tcx hir::Lifetime),
  40     Many,
  41 }
  42
  43 trait RegionExt {
  44     fn early(hir_map: Map<'_>, index: &mut u32, param: &GenericParam<'_>) -> (ParamName, Region);
  45
  46     fn late(index: u32, hir_map: Map<'_>, param: &GenericParam<'_>) -> (ParamName, Region);
  47
  48     fn late_anon(named_late_bound_vars: u32, index: &Cell<u32>) -> Region;
  49
  50     fn id(&self) -> Option<DefId>;
  51
  52     fn shifted(self, amount: u32) -> Region;
  53
  54     fn shifted_out_to_binder(self, binder: ty::DebruijnIndex) -> Region;
  55
  56     fn subst<'a, L>(self, params: L, map: &NamedRegionMap) -> Option<Region>
  57     where
  58         L: Iterator<Item = &'a hir::Lifetime>;
  59 }
  60
  61 impl RegionExt for Region {
  62     fn early(hir_map: Map<'_>, index: &mut u32, param: &GenericParam<'_>) -> (ParamName, Region) {
  63         let i = *index;
  64         *index += 1;
  65         let def_id = hir_map.local_def_id(param.hir_id);
  66         debug!("Region::early: index={} def_id={:?}", i, def_id);
  67         (param.name.normalize_to_macros_2_0(), Region::EarlyBound(i, def_id.to_def_id()))
  68     }
  69
  70     fn late(idx: u32, hir_map: Map<'_>, param: &GenericParam<'_>) -> (ParamName, Region) {
  71         let depth = ty::INNERMOST;
  72         let def_id = hir_map.local_def_id(param.hir_id);
  73         debug!(
  74             "Region::late: idx={:?}, param={:?} depth={:?} def_id={:?}",
  75             idx, param, depth, def_id,
  76         );
  77         (param.name.normalize_to_macros_2_0(), Region::LateBound(depth, idx, def_id.to_def_id()))
  78     }
  79
  80     fn late_anon(named_late_bound_vars: u32, index: &Cell<u32>) -> Region {
  81         let i = index.get();
  82         index.set(i + 1);
  83         let depth = ty::INNERMOST;
  84         Region::LateBoundAnon(depth, named_late_bound_vars + i, i)
  85     }
  86
  87     fn id(&self) -> Option<DefId> {
  88         match *self {
  89             Region::Static | Region::LateBoundAnon(..) => None,
  90
  91             Region::EarlyBound(_, id) | Region::LateBound(_, _, id) | Region::Free(_, id) => {
  92                 Some(id)
  93             }
  94         }
  95     }
  96
  97     fn shifted(self, amount: u32) -> Region {
  98         match self {
  99             Region::LateBound(debruijn, idx, id) => {
 100                 Region::LateBound(debruijn.shifted_in(amount), idx, id)
 101             }
 102             Region::LateBoundAnon(debruijn, index, anon_index) => {
 103                 Region::LateBoundAnon(debruijn.shifted_in(amount), index, anon_index)
 104             }
 105             _ => self,
 106         }
 107     }
 108
 109     fn shifted_out_to_binder(self, binder: ty::DebruijnIndex) -> Region {
 110         match self {
 111             Region::LateBound(debruijn, index, id) => {
 112                 Region::LateBound(debruijn.shifted_out_to_binder(binder), index, id)
 113             }
 114             Region::LateBoundAnon(debruijn, index, anon_index) => {
 115                 Region::LateBoundAnon(debruijn.shifted_out_to_binder(binder), index, anon_index)
 116             }
 117             _ => self,
 118         }
 119     }
 120
 121     fn subst<'a, L>(self, mut params: L, map: &NamedRegionMap) -> Option<Region>
 122     where
 123         L: Iterator<Item = &'a hir::Lifetime>,
 124     {
 125         if let Region::EarlyBound(index, _) = self {
 126             params.nth(index as usize).and_then(|lifetime| map.defs.get(&lifetime.hir_id).cloned())
 127         } else {
 128             Some(self)
 129         }
 130     }
 131 }
 132
 133 /// Maps the id of each lifetime reference to the lifetime decl
 134 /// that it corresponds to.
 135 ///
 136 /// FIXME. This struct gets converted to a `ResolveLifetimes` for
 137 /// actual use. It has the same data, but indexed by `LocalDefId`.  This
 138 /// is silly.
 139 #[derive(Debug, Default)]
 140 struct NamedRegionMap {
 141     // maps from every use of a named (not anonymous) lifetime to a
 142     // `Region` describing how that region is bound
 143     defs: HirIdMap<Region>,
 144
 145     // the set of lifetime def ids that are late-bound; a region can
 146     // be late-bound if (a) it does NOT appear in a where-clause and
 147     // (b) it DOES appear in the arguments.
 148     late_bound: HirIdSet,
 149
 150     // Maps relevant hir items to the bound vars on them. These include:
 151     // - function defs
 152     // - function pointers
 153     // - closures
 154     // - trait refs
 155     // - bound types (like `T` in `for<'a> T<'a>: Foo`)
 156     late_bound_vars: HirIdMap<Vec<ty::BoundVariableKind>>,
 157
 158     // maps `PathSegment` `HirId`s to lifetime scopes.
 159     scope_for_path: Option<FxHashMap<LocalDefId, FxHashMap<ItemLocalId, LifetimeScopeForPath>>>,
 160 }
 161
 162 crate struct LifetimeContext<'a, 'tcx> {
 163     crate tcx: TyCtxt<'tcx>,
 164     map: &'a mut NamedRegionMap,
 165     scope: ScopeRef<'a>,
 166
 167     /// Used to disallow the use of in-band lifetimes in `fn` or `Fn` syntax.
 168     is_in_fn_syntax: bool,
 169
 170     is_in_const_generic: bool,
 171
 172     /// Indicates that we only care about the definition of a trait. This should
 173     /// be false if the `Item` we are resolving lifetimes for is not a trait or
 174     /// we eventually need lifetimes resolve for trait items.
 175     trait_definition_only: bool,
 176
 177     /// List of labels in the function/method currently under analysis.
 178     labels_in_fn: Vec<Ident>,
 179
 180     /// Cache for cross-crate per-definition object lifetime defaults.
 181     xcrate_object_lifetime_defaults: DefIdMap<Vec<ObjectLifetimeDefault>>,
 182
 183     lifetime_uses: &'a mut DefIdMap<LifetimeUseSet<'tcx>>,
 184
 185     /// When encountering an undefined named lifetime, we will suggest introducing it in these
 186     /// places.
 187     crate missing_named_lifetime_spots: Vec<MissingLifetimeSpot<'tcx>>,
 188 }
 189
 190 #[derive(Debug)]
 191 enum Scope<'a> {
 192     /// Declares lifetimes, and each can be early-bound or late-bound.
 193     /// The `DebruijnIndex` of late-bound lifetimes starts at `1` and
 194     /// it should be shifted by the number of `Binder`s in between the
 195     /// declaration `Binder` and the location it's referenced from.
 196     Binder {
 197         /// We use an IndexMap here because we want these lifetimes in order
 198         /// for diagnostics.
 199         lifetimes: FxIndexMap<hir::ParamName, Region>,
 200
 201         /// if we extend this scope with another scope, what is the next index
 202         /// we should use for an early-bound region?
 203         next_early_index: u32,
 204
 205         /// Flag is set to true if, in this binder, `'_` would be
 206         /// equivalent to a "single-use region". This is true on
 207         /// impls, but not other kinds of items.
 208         track_lifetime_uses: bool,
 209
 210         /// Whether or not this binder would serve as the parent
 211         /// binder for opaque types introduced within. For example:
 212         ///
 213         /// ```text
 214         ///     fn foo<'a>() -> impl for<'b> Trait<Item = impl Trait2<'a>>
 215         /// ```
 216         ///
 217         /// Here, the opaque types we create for the `impl Trait`
 218         /// and `impl Trait2` references will both have the `foo` item
 219         /// as their parent. When we get to `impl Trait2`, we find
 220         /// that it is nested within the `for<>` binder -- this flag
 221         /// allows us to skip that when looking for the parent binder
 222         /// of the resulting opaque type.
 223         opaque_type_parent: bool,
 224
 225         scope_type: BinderScopeType,
 226
 227         /// The late bound vars for a given item are stored by `HirId` to be
 228         /// queried later. However, if we enter an elision scope, we have to
 229         /// later append the elided bound vars to the list and need to know what
 230         /// to append to.
 231         hir_id: hir::HirId,
 232
 233         s: ScopeRef<'a>,
 234
 235         /// In some cases not allowing late bounds allows us to avoid ICEs.
 236         /// This is almost ways set to true.
 237         allow_late_bound: bool,
 238     },
 239
 240     /// Lifetimes introduced by a fn are scoped to the call-site for that fn,
 241     /// if this is a fn body, otherwise the original definitions are used.
 242     /// Unspecified lifetimes are inferred, unless an elision scope is nested,
 243     /// e.g., `(&T, fn(&T) -> &T);` becomes `(&'_ T, for<'a> fn(&'a T) -> &'a T)`.
 244     Body {
 245         id: hir::BodyId,
 246         s: ScopeRef<'a>,
 247     },
 248
 249     /// A scope which either determines unspecified lifetimes or errors
 250     /// on them (e.g., due to ambiguity). For more details, see `Elide`.
 251     Elision {
 252         elide: Elide,
 253         s: ScopeRef<'a>,
 254     },
 255
 256     /// Use a specific lifetime (if `Some`) or leave it unset (to be
 257     /// inferred in a function body or potentially error outside one),
 258     /// for the default choice of lifetime in a trait object type.
 259     ObjectLifetimeDefault {
 260         lifetime: Option<Region>,
 261         s: ScopeRef<'a>,
 262     },
 263
 264     /// When we have nested trait refs, we concatenate late bound vars for inner
 265     /// trait refs from outer ones. But we also need to include any HRTB
 266     /// lifetimes encountered when identifying the trait that an associated type
 267     /// is declared on.
 268     Supertrait {
 269         lifetimes: Vec<ty::BoundVariableKind>,
 270         s: ScopeRef<'a>,
 271     },
 272
 273     TraitRefBoundary {
 274         s: ScopeRef<'a>,
 275     },
 276
 277     Root,
 278 }
 279
 280 #[derive(Copy, Clone, Debug)]
 281 enum BinderScopeType {
 282     /// Any non-concatenating binder scopes.
 283     Normal,
 284     /// Within a syntactic trait ref, there may be multiple poly trait refs that
 285     /// are nested (under the `associated_type_bounds` feature). The binders of
 286     /// the inner poly trait refs are extended from the outer poly trait refs
 287     /// and don't increase the late bound depth. If you had
 288     /// `T: for<'a>  Foo<Bar: for<'b> Baz<'a, 'b>>`, then the `for<'b>` scope
 289     /// would be `Concatenating`. This also used in trait refs in where clauses
 290     /// where we have two binders `for<> T: for<> Foo` (I've intentionally left
 291     /// out any lifetimes because they aren't needed to show the two scopes).
 292     /// The inner `for<>` has a scope of `Concatenating`.
 293     Concatenating,
 294 }
 295
 296 // A helper struct for debugging scopes without printing parent scopes
 297 struct TruncatedScopeDebug<'a>(&'a Scope<'a>);
 298
 299 impl<'a> fmt::Debug for TruncatedScopeDebug<'a> {
 300     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 301         match self.0 {
 302             Scope::Binder {
 303                 lifetimes,
 304                 next_early_index,
 305                 track_lifetime_uses,
 306                 opaque_type_parent,
 307                 scope_type,
 308                 hir_id,
 309                 s: _,
 310                 allow_late_bound,
 311             } => f
 312                 .debug_struct("Binder")
 313                 .field("lifetimes", lifetimes)
 314                 .field("next_early_index", next_early_index)
 315                 .field("track_lifetime_uses", track_lifetime_uses)
 316                 .field("opaque_type_parent", opaque_type_parent)
 317                 .field("scope_type", scope_type)
 318                 .field("hir_id", hir_id)
 319                 .field("s", &"..")
 320                 .field("allow_late_bound", allow_late_bound)
 321                 .finish(),
 322             Scope::Body { id, s: _ } => {
 323                 f.debug_struct("Body").field("id", id).field("s", &"..").finish()
 324             }
 325             Scope::Elision { elide, s: _ } => {
 326                 f.debug_struct("Elision").field("elide", elide).field("s", &"..").finish()
 327             }
 328             Scope::ObjectLifetimeDefault { lifetime, s: _ } => f
 329                 .debug_struct("ObjectLifetimeDefault")
 330                 .field("lifetime", lifetime)
 331                 .field("s", &"..")
 332                 .finish(),
 333             Scope::Supertrait { lifetimes, s: _ } => f
 334                 .debug_struct("Supertrait")
 335                 .field("lifetimes", lifetimes)
 336                 .field("s", &"..")
 337                 .finish(),
 338             Scope::TraitRefBoundary { s: _ } => f.debug_struct("TraitRefBoundary").finish(),
 339             Scope::Root => f.debug_struct("Root").finish(),
 340         }
 341     }
 342 }
 343
 344 #[derive(Clone, Debug)]
 345 enum Elide {
 346     /// Use a fresh anonymous late-bound lifetime each time, by
 347     /// incrementing the counter to generate sequential indices. All
 348     /// anonymous lifetimes must start *after* named bound vars.
 349     FreshLateAnon(u32, Cell<u32>),
 350     /// Always use this one lifetime.
 351     Exact(Region),
 352     /// Less or more than one lifetime were found, error on unspecified.
 353     Error(Vec<ElisionFailureInfo>),
 354     /// Forbid lifetime elision inside of a larger scope where it would be
 355     /// permitted. For example, in let position impl trait.
 356     Forbid,
 357 }
 358
 359 #[derive(Clone, Debug)]
 360 crate struct ElisionFailureInfo {
 361     /// Where we can find the argument pattern.
 362     crate parent: Option<hir::BodyId>,
 363     /// The index of the argument in the original definition.
 364     crate index: usize,
 365     crate lifetime_count: usize,
 366     crate have_bound_regions: bool,
 367     crate span: Span,
 368 }
 369
 370 type ScopeRef<'a> = &'a Scope<'a>;
 371
 372 const ROOT_SCOPE: ScopeRef<'static> = &Scope::Root;
 373
 374 pub fn provide(providers: &mut ty::query::Providers) {
 375     *providers = ty::query::Providers {
 376         resolve_lifetimes_trait_definition,
 377         resolve_lifetimes,
 378
 379         named_region_map: |tcx, id| resolve_lifetimes_for(tcx, id).defs.get(&id),
 380         is_late_bound_map,
 381         object_lifetime_defaults: |tcx, id| match tcx.hir().find_by_def_id(id) {
 382             Some(Node::Item(item)) => compute_object_lifetime_defaults(tcx, item),
 383             _ => None,
 384         },
 385         late_bound_vars_map: |tcx, id| resolve_lifetimes_for(tcx, id).late_bound_vars.get(&id),
 386         lifetime_scope_map: |tcx, id| {
 387             let item_id = item_for(tcx, id);
 388             do_resolve(tcx, item_id, false, true).scope_for_path.unwrap().remove(&id)
 389         },
 390
 391         ..*providers
 392     };
 393 }
 394
 395 /// Like `resolve_lifetimes`, but does not resolve lifetimes for trait items.
 396 /// Also does not generate any diagnostics.
 397 ///
 398 /// This is ultimately a subset of the `resolve_lifetimes` work. It effectively
 399 /// resolves lifetimes only within the trait "header" -- that is, the trait
 400 /// and supertrait list. In contrast, `resolve_lifetimes` resolves all the
 401 /// lifetimes within the trait and its items. There is room to refactor this,
 402 /// for example to resolve lifetimes for each trait item in separate queries,
 403 /// but it's convenient to do the entire trait at once because the lifetimes
 404 /// from the trait definition are in scope within the trait items as well.
 405 ///
 406 /// The reason for this separate call is to resolve what would otherwise
 407 /// be a cycle. Consider this example:
 408 ///
 409 /// ```rust
 410 /// trait Base<'a> {
 411 ///     type BaseItem;
 412 /// }
 413 /// trait Sub<'b>: for<'a> Base<'a> {
 414 ///    type SubItem: Sub<BaseItem = &'b u32>;
 415 /// }
 416 /// ```
 417 ///
 418 /// When we resolve `Sub` and all its items, we also have to resolve `Sub<BaseItem = &'b u32>`.
 419 /// To figure out the index of `'b`, we have to know about the supertraits
 420 /// of `Sub` so that we can determine that the `for<'a>` will be in scope.
 421 /// (This is because we -- currently at least -- flatten all the late-bound
 422 /// lifetimes into a single binder.) This requires us to resolve the
 423 /// *trait definition* of `Sub`; basically just enough lifetime information
 424 /// to look at the supertraits.
 425 #[tracing::instrument(level = "debug", skip(tcx))]
 426 fn resolve_lifetimes_trait_definition(
 427     tcx: TyCtxt<'_>,
 428     local_def_id: LocalDefId,
 429 ) -> ResolveLifetimes {
 430     convert_named_region_map(do_resolve(tcx, local_def_id, true, false))
 431 }
 432
 433 /// Computes the `ResolveLifetimes` map that contains data for an entire `Item`.
 434 /// You should not read the result of this query directly, but rather use
 435 /// `named_region_map`, `is_late_bound_map`, etc.
 436 #[tracing::instrument(level = "debug", skip(tcx))]
 437 fn resolve_lifetimes(tcx: TyCtxt<'_>, local_def_id: LocalDefId) -> ResolveLifetimes {
 438     convert_named_region_map(do_resolve(tcx, local_def_id, false, false))
 439 }
 440
 441 fn do_resolve(
 442     tcx: TyCtxt<'_>,
 443     local_def_id: LocalDefId,
 444     trait_definition_only: bool,
 445     with_scope_for_path: bool,
 446 ) -> NamedRegionMap {
 447     let item = tcx.hir().expect_item(local_def_id);
 448     let mut named_region_map = NamedRegionMap {
 449         defs: Default::default(),
 450         late_bound: Default::default(),
 451         late_bound_vars: Default::default(),
 452         scope_for_path: with_scope_for_path.then(|| Default::default()),
 453     };
 454     let mut visitor = LifetimeContext {
 455         tcx,
 456         map: &mut named_region_map,
 457         scope: ROOT_SCOPE,
 458         is_in_fn_syntax: false,
 459         is_in_const_generic: false,
 460         trait_definition_only,
 461         labels_in_fn: vec![],
 462         xcrate_object_lifetime_defaults: Default::default(),
 463         lifetime_uses: &mut Default::default(),
 464         missing_named_lifetime_spots: vec![],
 465     };
 466     visitor.visit_item(item);
 467
 468     named_region_map
 469 }
 470
 471 fn convert_named_region_map(named_region_map: NamedRegionMap) -> ResolveLifetimes {
 472     let mut rl = ResolveLifetimes::default();
 473
 474     for (hir_id, v) in named_region_map.defs {
 475         let map = rl.defs.entry(hir_id.owner).or_default();
 476         map.insert(hir_id.local_id, v);
 477     }
 478     for hir_id in named_region_map.late_bound {
 479         let map = rl.late_bound.entry(hir_id.owner).or_default();
 480         map.insert(hir_id.local_id);
 481     }
 482     for (hir_id, v) in named_region_map.late_bound_vars {
 483         let map = rl.late_bound_vars.entry(hir_id.owner).or_default();
 484         map.insert(hir_id.local_id, v);
 485     }
 486
 487     debug!(?rl.defs);
 488     rl
 489 }
 490
 491 /// Given `any` owner (structs, traits, trait methods, etc.), does lifetime resolution.
 492 /// There are two important things this does.
 493 /// First, we have to resolve lifetimes for
 494 /// the entire *`Item`* that contains this owner, because that's the largest "scope"
 495 /// where we can have relevant lifetimes.
 496 /// Second, if we are asking for lifetimes in a trait *definition*, we use `resolve_lifetimes_trait_definition`
 497 /// instead of `resolve_lifetimes`, which does not descend into the trait items and does not emit diagnostics.
 498 /// This allows us to avoid cycles. Importantly, if we ask for lifetimes for lifetimes that have an owner
 499 /// other than the trait itself (like the trait methods or associated types), then we just use the regular
 500 /// `resolve_lifetimes`.
 501 fn resolve_lifetimes_for<'tcx>(tcx: TyCtxt<'tcx>, def_id: LocalDefId) -> &'tcx ResolveLifetimes {
 502     let item_id = item_for(tcx, def_id);
 503     if item_id == def_id {
 504         let item = tcx.hir().item(hir::ItemId { def_id: item_id });
 505         match item.kind {
 506             hir::ItemKind::Trait(..) => tcx.resolve_lifetimes_trait_definition(item_id),
 507             _ => tcx.resolve_lifetimes(item_id),
 508         }
 509     } else {
 510         tcx.resolve_lifetimes(item_id)
 511     }
 512 }
 513
 514 /// Finds the `Item` that contains the given `LocalDefId`
 515 fn item_for(tcx: TyCtxt<'_>, local_def_id: LocalDefId) -> LocalDefId {
 516     match tcx.hir().find_by_def_id(local_def_id) {
 517         Some(Node::Item(item)) => {
 518             return item.def_id;
 519         }
 520         _ => {}
 521     }
 522     let item = {
 523         let hir_id = tcx.hir().local_def_id_to_hir_id(local_def_id);
 524         let mut parent_iter = tcx.hir().parent_iter(hir_id);
 525         loop {
 526             let node = parent_iter.next().map(|n| n.1);
 527             match node {
 528                 Some(hir::Node::Item(item)) => break item.def_id,
 529                 Some(hir::Node::Crate(_)) | None => bug!("Called `item_for` on an Item."),
 530                 _ => {}
 531             }
 532         }
 533     };
 534     item
 535 }
 536
 537 fn is_late_bound_map<'tcx>(
 538     tcx: TyCtxt<'tcx>,
 539     def_id: LocalDefId,
 540 ) -> Option<(LocalDefId, &'tcx FxHashSet<ItemLocalId>)> {
 541     match tcx.def_kind(def_id) {
 542         DefKind::AnonConst | DefKind::InlineConst => {
 543             let mut def_id = tcx
 544                 .parent(def_id.to_def_id())
 545                 .unwrap_or_else(|| bug!("anon const or closure without a parent"));
 546             // We search for the next outer anon const or fn here
 547             // while skipping closures.
 548             //
 549             // Note that for `AnonConst` we still just recurse until we
 550             // find a function body, but who cares :shrug:
 551             while tcx.is_closure(def_id) {
 552                 def_id = tcx
 553                     .parent(def_id)
 554                     .unwrap_or_else(|| bug!("anon const or closure without a parent"));
 555             }
 556
 557             tcx.is_late_bound_map(def_id.expect_local())
 558         }
 559         _ => resolve_lifetimes_for(tcx, def_id).late_bound.get(&def_id).map(|lt| (def_id, lt)),
 560     }
 561 }
 562
 563 /// In traits, there is an implicit `Self` type parameter which comes before the generics.
 564 /// We have to account for this when computing the index of the other generic parameters.
 565 /// This function returns whether there is such an implicit parameter defined on the given item.
 566 fn sub_items_have_self_param(node: &hir::ItemKind<'_>) -> bool {
 567     matches!(*node, hir::ItemKind::Trait(..) | hir::ItemKind::TraitAlias(..))
 568 }
 569
 570 fn late_region_as_bound_region<'tcx>(tcx: TyCtxt<'tcx>, region: &Region) -> ty::BoundVariableKind {
 571     match region {
 572         Region::LateBound(_, _, def_id) => {
 573             let name = tcx.hir().name(tcx.hir().local_def_id_to_hir_id(def_id.expect_local()));
 574             ty::BoundVariableKind::Region(ty::BrNamed(*def_id, name))
 575         }
 576         Region::LateBoundAnon(_, _, anon_idx) => {
 577             ty::BoundVariableKind::Region(ty::BrAnon(*anon_idx))
 578         }
 579         _ => bug!("{:?} is not a late region", region),
 580     }
 581 }
 582
 583 #[tracing::instrument(level = "debug")]
 584 fn get_lifetime_scopes_for_path(mut scope: &Scope<'_>) -> LifetimeScopeForPath {
 585     let mut available_lifetimes = vec![];
 586     loop {
 587         match scope {
 588             Scope::Binder { lifetimes, s, .. } => {
 589                 available_lifetimes.extend(lifetimes.keys().filter_map(|p| match p {
 590                     hir::ParamName::Plain(ident) => Some(ident.name.to_string()),
 591                     _ => None,
 592                 }));
 593                 scope = s;
 594             }
 595             Scope::Body { s, .. } => {
 596                 scope = s;
 597             }
 598             Scope::Elision { elide, s } => {
 599                 if let Elide::Exact(_) = elide {
 600                     return LifetimeScopeForPath::Elided;
 601                 } else {
 602                     scope = s;
 603                 }
 604             }
 605             Scope::ObjectLifetimeDefault { s, .. } => {
 606                 scope = s;
 607             }
 608             Scope::Root => {
 609                 return LifetimeScopeForPath::NonElided(available_lifetimes);
 610             }
 611             Scope::Supertrait { s, .. } | Scope::TraitRefBoundary { s, .. } => {
 612                 scope = s;
 613             }
 614         }
 615     }
 616 }
 617
 618 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 619     /// Returns the binders in scope and the type of `Binder` that should be created for a poly trait ref.
 620     fn poly_trait_ref_binder_info(&mut self) -> (Vec<ty::BoundVariableKind>, BinderScopeType) {
 621         let mut scope = self.scope;
 622         let mut supertrait_lifetimes = vec![];
 623         loop {
 624             match scope {
 625                 Scope::Body { .. } | Scope::Root => {
 626                     break (vec![], BinderScopeType::Normal);
 627                 }
 628
 629                 Scope::Elision { s, .. } | Scope::ObjectLifetimeDefault { s, .. } => {
 630                     scope = s;
 631                 }
 632
 633                 Scope::Supertrait { s, lifetimes } => {
 634                     supertrait_lifetimes = lifetimes.clone();
 635                     scope = s;
 636                 }
 637
 638                 Scope::TraitRefBoundary { .. } => {
 639                     // We should only see super trait lifetimes if there is a `Binder` above
 640                     assert!(supertrait_lifetimes.is_empty());
 641                     break (vec![], BinderScopeType::Normal);
 642                 }
 643
 644                 Scope::Binder { hir_id, .. } => {
 645                     // Nested poly trait refs have the binders concatenated
 646                     let mut full_binders =
 647                         self.map.late_bound_vars.entry(*hir_id).or_default().clone();
 648                     full_binders.extend(supertrait_lifetimes.into_iter());
 649                     break (full_binders, BinderScopeType::Concatenating);
 650                 }
 651             }
 652         }
 653     }
 654 }
 655 impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
 656     type NestedFilter = nested_filter::All;
 657
 658     fn nested_visit_map(&mut self) -> Self::Map {
 659         self.tcx.hir()
 660     }
 661
 662     // We want to nest trait/impl items in their parent, but nothing else.
 663     fn visit_nested_item(&mut self, _: hir::ItemId) {}
 664
 665     fn visit_trait_item_ref(&mut self, ii: &'tcx hir::TraitItemRef) {
 666         if !self.trait_definition_only {
 667             intravisit::walk_trait_item_ref(self, ii)
 668         }
 669     }
 670
 671     fn visit_nested_body(&mut self, body: hir::BodyId) {
 672         // Each body has their own set of labels, save labels.
 673         let saved = take(&mut self.labels_in_fn);
 674         let body = self.tcx.hir().body(body);
 675         extract_labels(self, body);
 676         self.with(Scope::Body { id: body.id(), s: self.scope }, |_, this| {
 677             this.visit_body(body);
 678         });
 679         self.labels_in_fn = saved;
 680     }
 681
 682     fn visit_fn(
 683         &mut self,
 684         fk: intravisit::FnKind<'tcx>,
 685         fd: &'tcx hir::FnDecl<'tcx>,
 686         b: hir::BodyId,
 687         s: rustc_span::Span,
 688         hir_id: hir::HirId,
 689     ) {
 690         let name = match fk {
 691             intravisit::FnKind::ItemFn(id, _, _, _) => id.name,
 692             intravisit::FnKind::Method(id, _, _) => id.name,
 693             intravisit::FnKind::Closure => sym::closure,
 694         };
 695         let name = name.as_str();
 696         let span = span!(Level::DEBUG, "visit_fn", name);
 697         let _enter = span.enter();
 698         match fk {
 699             // Any `Binders` are handled elsewhere
 700             intravisit::FnKind::ItemFn(..) | intravisit::FnKind::Method(..) => {
 701                 intravisit::walk_fn(self, fk, fd, b, s, hir_id)
 702             }
 703             intravisit::FnKind::Closure => {
 704                 self.map.late_bound_vars.insert(hir_id, vec![]);
 705                 let scope = Scope::Binder {
 706                     hir_id,
 707                     lifetimes: FxIndexMap::default(),
 708                     next_early_index: self.next_early_index(),
 709                     s: self.scope,
 710                     track_lifetime_uses: true,
 711                     opaque_type_parent: false,
 712                     scope_type: BinderScopeType::Normal,
 713                     allow_late_bound: true,
 714                 };
 715                 self.with(scope, move |_old_scope, this| {
 716                     intravisit::walk_fn(this, fk, fd, b, s, hir_id)
 717                 });
 718             }
 719         }
 720     }
 721
 722     fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) {
 723         match &item.kind {
 724             hir::ItemKind::Impl(hir::Impl { of_trait, .. }) => {
 725                 if let Some(of_trait) = of_trait {
 726                     self.map.late_bound_vars.insert(of_trait.hir_ref_id, Vec::default());
 727                 }
 728             }
 729             _ => {}
 730         }
 731         match item.kind {
 732             hir::ItemKind::Fn(ref sig, ref generics, _) => {
 733                 self.missing_named_lifetime_spots.push(generics.into());
 734                 self.visit_early_late(None, item.hir_id(), &sig.decl, generics, |this| {
 735                     intravisit::walk_item(this, item);
 736                 });
 737                 self.missing_named_lifetime_spots.pop();
 738             }
 739
 740             hir::ItemKind::ExternCrate(_)
 741             | hir::ItemKind::Use(..)
 742             | hir::ItemKind::Macro(..)
 743             | hir::ItemKind::Mod(..)
 744             | hir::ItemKind::ForeignMod { .. }
 745             | hir::ItemKind::GlobalAsm(..) => {
 746                 // These sorts of items have no lifetime parameters at all.
 747                 intravisit::walk_item(self, item);
 748             }
 749             hir::ItemKind::Static(..) | hir::ItemKind::Const(..) => {
 750                 // No lifetime parameters, but implied 'static.
 751                 let scope = Scope::Elision { elide: Elide::Exact(Region::Static), s: ROOT_SCOPE };
 752                 self.with(scope, |_, this| intravisit::walk_item(this, item));
 753             }
 754             hir::ItemKind::OpaqueTy(hir::OpaqueTy { .. }) => {
 755                 // Opaque types are visited when we visit the
 756                 // `TyKind::OpaqueDef`, so that they have the lifetimes from
 757                 // their parent opaque_ty in scope.
 758                 //
 759                 // The core idea here is that since OpaqueTys are generated with the impl Trait as
 760                 // their owner, we can keep going until we find the Item that owns that. We then
 761                 // conservatively add all resolved lifetimes. Otherwise we run into problems in
 762                 // cases like `type Foo<'a> = impl Bar<As = impl Baz + 'a>`.
 763                 for (_hir_id, node) in
 764                     self.tcx.hir().parent_iter(self.tcx.hir().local_def_id_to_hir_id(item.def_id))
 765                 {
 766                     match node {
 767                         hir::Node::Item(parent_item) => {
 768                             let resolved_lifetimes: &ResolveLifetimes =
 769                                 self.tcx.resolve_lifetimes(item_for(self.tcx, parent_item.def_id));
 770                             // We need to add *all* deps, since opaque tys may want them from *us*
 771                             for (&owner, defs) in resolved_lifetimes.defs.iter() {
 772                                 defs.iter().for_each(|(&local_id, region)| {
 773                                     self.map.defs.insert(hir::HirId { owner, local_id }, *region);
 774                                 });
 775                             }
 776                             for (&owner, late_bound) in resolved_lifetimes.late_bound.iter() {
 777                                 late_bound.iter().for_each(|&local_id| {
 778                                     self.map.late_bound.insert(hir::HirId { owner, local_id });
 779                                 });
 780                             }
 781                             for (&owner, late_bound_vars) in
 782                                 resolved_lifetimes.late_bound_vars.iter()
 783                             {
 784                                 late_bound_vars.iter().for_each(|(&local_id, late_bound_vars)| {
 785                                     self.map.late_bound_vars.insert(
 786                                         hir::HirId { owner, local_id },
 787                                         late_bound_vars.clone(),
 788                                     );
 789                                 });
 790                             }
 791                             break;
 792                         }
 793                         hir::Node::Crate(_) => bug!("No Item about an OpaqueTy"),
 794                         _ => {}
 795                     }
 796                 }
 797             }
 798             hir::ItemKind::TyAlias(_, ref generics)
 799             | hir::ItemKind::Enum(_, ref generics)
 800             | hir::ItemKind::Struct(_, ref generics)
 801             | hir::ItemKind::Union(_, ref generics)
 802             | hir::ItemKind::Trait(_, _, ref generics, ..)
 803             | hir::ItemKind::TraitAlias(ref generics, ..)
 804             | hir::ItemKind::Impl(hir::Impl { ref generics, .. }) => {
 805                 self.missing_named_lifetime_spots.push(generics.into());
 806
 807                 // Impls permit `'_` to be used and it is equivalent to "some fresh lifetime name".
 808                 // This is not true for other kinds of items.
 809                 let track_lifetime_uses = matches!(item.kind, hir::ItemKind::Impl { .. });
 810                 // These kinds of items have only early-bound lifetime parameters.
 811                 let mut index = if sub_items_have_self_param(&item.kind) {
 812                     1 // Self comes before lifetimes
 813                 } else {
 814                     0
 815                 };
 816                 let mut non_lifetime_count = 0;
 817                 let lifetimes = generics
 818                     .params
 819                     .iter()
 820                     .filter_map(|param| match param.kind {
 821                         GenericParamKind::Lifetime { .. } => {
 822                             Some(Region::early(self.tcx.hir(), &mut index, param))
 823                         }
 824                         GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => {
 825                             non_lifetime_count += 1;
 826                             None
 827                         }
 828                     })
 829                     .collect();
 830                 self.map.late_bound_vars.insert(item.hir_id(), vec![]);
 831                 let scope = Scope::Binder {
 832                     hir_id: item.hir_id(),
 833                     lifetimes,
 834                     next_early_index: index + non_lifetime_count,
 835                     opaque_type_parent: true,
 836                     track_lifetime_uses,
 837                     scope_type: BinderScopeType::Normal,
 838                     s: ROOT_SCOPE,
 839                     allow_late_bound: false,
 840                 };
 841                 self.with(scope, |old_scope, this| {
 842                     this.check_lifetime_params(old_scope, &generics.params);
 843                     let scope = Scope::TraitRefBoundary { s: this.scope };
 844                     this.with(scope, |_, this| {
 845                         intravisit::walk_item(this, item);
 846                     });
 847                 });
 848                 self.missing_named_lifetime_spots.pop();
 849             }
 850         }
 851     }
 852
 853     fn visit_foreign_item(&mut self, item: &'tcx hir::ForeignItem<'tcx>) {
 854         match item.kind {
 855             hir::ForeignItemKind::Fn(ref decl, _, ref generics) => {
 856                 self.visit_early_late(None, item.hir_id(), decl, generics, |this| {
 857                     intravisit::walk_foreign_item(this, item);
 858                 })
 859             }
 860             hir::ForeignItemKind::Static(..) => {
 861                 intravisit::walk_foreign_item(self, item);
 862             }
 863             hir::ForeignItemKind::Type => {
 864                 intravisit::walk_foreign_item(self, item);
 865             }
 866         }
 867     }
 868
 869     #[tracing::instrument(level = "debug", skip(self))]
 870     fn visit_ty(&mut self, ty: &'tcx hir::Ty<'tcx>) {
 871         match ty.kind {
 872             hir::TyKind::BareFn(ref c) => {
 873                 let next_early_index = self.next_early_index();
 874                 let was_in_fn_syntax = self.is_in_fn_syntax;
 875                 self.is_in_fn_syntax = true;
 876                 let lifetime_span: Option<Span> =
 877                     c.generic_params.iter().rev().find_map(|param| match param.kind {
 878                         GenericParamKind::Lifetime { .. } => Some(param.span),
 879                         _ => None,
 880                     });
 881                 let (span, span_type) = if let Some(span) = lifetime_span {
 882                     (span.shrink_to_hi(), ForLifetimeSpanType::TypeTail)
 883                 } else {
 884                     (ty.span.shrink_to_lo(), ForLifetimeSpanType::TypeEmpty)
 885                 };
 886                 self.missing_named_lifetime_spots
 887                     .push(MissingLifetimeSpot::HigherRanked { span, span_type });
 888                 let (lifetimes, binders): (FxIndexMap<hir::ParamName, Region>, Vec<_>) = c
 889                     .generic_params
 890                     .iter()
 891                     .filter(|param| matches!(param.kind, GenericParamKind::Lifetime { .. }))
 892                     .enumerate()
 893                     .map(|(late_bound_idx, param)| {
 894                         let pair = Region::late(late_bound_idx as u32, self.tcx.hir(), param);
 895                         let r = late_region_as_bound_region(self.tcx, &pair.1);
 896                         (pair, r)
 897                     })
 898                     .unzip();
 899                 self.map.late_bound_vars.insert(ty.hir_id, binders);
 900                 let scope = Scope::Binder {
 901                     hir_id: ty.hir_id,
 902                     lifetimes,
 903                     s: self.scope,
 904                     next_early_index,
 905                     track_lifetime_uses: true,
 906                     opaque_type_parent: false,
 907                     scope_type: BinderScopeType::Normal,
 908                     allow_late_bound: true,
 909                 };
 910                 self.with(scope, |old_scope, this| {
 911                     // a bare fn has no bounds, so everything
 912                     // contained within is scoped within its binder.
 913                     this.check_lifetime_params(old_scope, &c.generic_params);
 914                     intravisit::walk_ty(this, ty);
 915                 });
 916                 self.missing_named_lifetime_spots.pop();
 917                 self.is_in_fn_syntax = was_in_fn_syntax;
 918             }
 919             hir::TyKind::TraitObject(bounds, ref lifetime, _) => {
 920                 debug!(?bounds, ?lifetime, "TraitObject");
 921                 let scope = Scope::TraitRefBoundary { s: self.scope };
 922                 self.with(scope, |_, this| {
 923                     for bound in bounds {
 924                         this.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
 925                     }
 926                 });
 927                 match lifetime.name {
 928                     LifetimeName::Implicit(_) => {
 929                         // For types like `dyn Foo`, we should
 930                         // generate a special form of elided.
 931                         span_bug!(ty.span, "object-lifetime-default expected, not implicit",);
 932                     }
 933                     LifetimeName::ImplicitObjectLifetimeDefault => {
 934                         // If the user does not write *anything*, we
 935                         // use the object lifetime defaulting
 936                         // rules. So e.g., `Box<dyn Debug>` becomes
 937                         // `Box<dyn Debug + 'static>`.
 938                         self.resolve_object_lifetime_default(lifetime)
 939                     }
 940                     LifetimeName::Underscore => {
 941                         // If the user writes `'_`, we use the *ordinary* elision
 942                         // rules. So the `'_` in e.g., `Box<dyn Debug + '_>` will be
 943                         // resolved the same as the `'_` in `&'_ Foo`.
 944                         //
 945                         // cc #48468
 946                         self.resolve_elided_lifetimes(&[lifetime])
 947                     }
 948                     LifetimeName::Param(_) | LifetimeName::Static => {
 949                         // If the user wrote an explicit name, use that.
 950                         self.visit_lifetime(lifetime);
 951                     }
 952                     LifetimeName::Error => {}
 953                 }
 954             }
 955             hir::TyKind::Rptr(ref lifetime_ref, ref mt) => {
 956                 self.visit_lifetime(lifetime_ref);
 957                 let scope = Scope::ObjectLifetimeDefault {
 958                     lifetime: self.map.defs.get(&lifetime_ref.hir_id).cloned(),
 959                     s: self.scope,
 960                 };
 961                 self.with(scope, |_, this| this.visit_ty(&mt.ty));
 962             }
 963             hir::TyKind::OpaqueDef(item_id, lifetimes) => {
 964                 // Resolve the lifetimes in the bounds to the lifetime defs in the generics.
 965                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 966                 // `type MyAnonTy<'b> = impl MyTrait<'b>;`
 967                 //                 ^                  ^ this gets resolved in the scope of
 968                 //                                      the opaque_ty generics
 969                 let opaque_ty = self.tcx.hir().item(item_id);
 970                 let (generics, bounds) = match opaque_ty.kind {
 971                     // Named opaque `impl Trait` types are reached via `TyKind::Path`.
 972                     // This arm is for `impl Trait` in the types of statics, constants and locals.
 973                     hir::ItemKind::OpaqueTy(hir::OpaqueTy {
 974                         origin: hir::OpaqueTyOrigin::TyAlias,
 975                         ..
 976                     }) => {
 977                         intravisit::walk_ty(self, ty);
 978
 979                         // Elided lifetimes are not allowed in non-return
 980                         // position impl Trait
 981                         let scope = Scope::TraitRefBoundary { s: self.scope };
 982                         self.with(scope, |_, this| {
 983                             let scope = Scope::Elision { elide: Elide::Forbid, s: this.scope };
 984                             this.with(scope, |_, this| {
 985                                 intravisit::walk_item(this, opaque_ty);
 986                             })
 987                         });
 988
 989                         return;
 990                     }
 991                     // RPIT (return position impl trait)
 992                     hir::ItemKind::OpaqueTy(hir::OpaqueTy {
 993                         origin: hir::OpaqueTyOrigin::FnReturn(..) | hir::OpaqueTyOrigin::AsyncFn(..),
 994                         ref generics,
 995                         bounds,
 996                         ..
 997                     }) => (generics, bounds),
 998                     ref i => bug!("`impl Trait` pointed to non-opaque type?? {:#?}", i),
 999                 };
1000
1001                 // Resolve the lifetimes that are applied to the opaque type.
1002                 // These are resolved in the current scope.
1003                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
1004                 // `fn foo<'a>() -> MyAnonTy<'a> { ... }`
1005                 //          ^                 ^this gets resolved in the current scope
1006                 for lifetime in lifetimes {
1007                     let hir::GenericArg::Lifetime(lifetime) = lifetime else {
1008                         continue
1009                     };
1010                     self.visit_lifetime(lifetime);
1011
1012                     // Check for predicates like `impl for<'a> Trait<impl OtherTrait<'a>>`
1013                     // and ban them. Type variables instantiated inside binders aren't
1014                     // well-supported at the moment, so this doesn't work.
1015                     // In the future, this should be fixed and this error should be removed.
1016                     let def = self.map.defs.get(&lifetime.hir_id).cloned();
1017                     let Some(Region::LateBound(_, _, def_id)) = def else {
1018                         continue
1019                     };
1020                     let Some(def_id) = def_id.as_local() else {
1021                         continue
1022                     };
1023                     let hir_id = self.tcx.hir().local_def_id_to_hir_id(def_id);
1024                     // Ensure that the parent of the def is an item, not HRTB
1025                     let parent_id = self.tcx.hir().get_parent_node(hir_id);
1026                     if !parent_id.is_owner() {
1027                         if !self.trait_definition_only {
1028                             struct_span_err!(
1029                                 self.tcx.sess,
1030                                 lifetime.span,
1031                                 E0657,
1032                                 "`impl Trait` can only capture lifetimes \
1033                                     bound at the fn or impl level"
1034                             )
1035                             .emit();
1036                         }
1037                         self.uninsert_lifetime_on_error(lifetime, def.unwrap());
1038                     }
1039                 }
1040
1041                 // We want to start our early-bound indices at the end of the parent scope,
1042                 // not including any parent `impl Trait`s.
1043                 let mut index = self.next_early_index_for_opaque_type();
1044                 debug!(?index);
1045
1046                 let mut elision = None;
1047                 let mut lifetimes = FxIndexMap::default();
1048                 let mut non_lifetime_count = 0;
1049                 for param in generics.params {
1050                     match param.kind {
1051                         GenericParamKind::Lifetime { .. } => {
1052                             let (name, reg) = Region::early(self.tcx.hir(), &mut index, &param);
1053                             let Region::EarlyBound(_, def_id) = reg else {
1054                                 bug!();
1055                             };
1056                             // We cannot predict what lifetimes are unused in opaque type.
1057                             self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
1058                             if let hir::ParamName::Plain(Ident {
1059                                 name: kw::UnderscoreLifetime,
1060                                 ..
1061                             }) = name
1062                             {
1063                                 // Pick the elided lifetime "definition" if one exists
1064                                 // and use it to make an elision scope.
1065                                 elision = Some(reg);
1066                             } else {
1067                                 lifetimes.insert(name, reg);
1068                             }
1069                         }
1070                         GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => {
1071                             non_lifetime_count += 1;
1072                         }
1073                     }
1074                 }
1075                 let next_early_index = index + non_lifetime_count;
1076                 self.map.late_bound_vars.insert(ty.hir_id, vec![]);
1077
1078                 if let Some(elision_region) = elision {
1079                     let scope =
1080                         Scope::Elision { elide: Elide::Exact(elision_region), s: self.scope };
1081                     self.with(scope, |_old_scope, this| {
1082                         let scope = Scope::Binder {
1083                             hir_id: ty.hir_id,
1084                             lifetimes,
1085                             next_early_index,
1086                             s: this.scope,
1087                             track_lifetime_uses: true,
1088                             opaque_type_parent: false,
1089                             scope_type: BinderScopeType::Normal,
1090                             allow_late_bound: false,
1091                         };
1092                         this.with(scope, |_old_scope, this| {
1093                             this.visit_generics(generics);
1094                             let scope = Scope::TraitRefBoundary { s: this.scope };
1095                             this.with(scope, |_, this| {
1096                                 for bound in bounds {
1097                                     this.visit_param_bound(bound);
1098                                 }
1099                             })
1100                         });
1101                     });
1102                 } else {
1103                     let scope = Scope::Binder {
1104                         hir_id: ty.hir_id,
1105                         lifetimes,
1106                         next_early_index,
1107                         s: self.scope,
1108                         track_lifetime_uses: true,
1109                         opaque_type_parent: false,
1110                         scope_type: BinderScopeType::Normal,
1111                         allow_late_bound: false,
1112                     };
1113                     self.with(scope, |_old_scope, this| {
1114                         let scope = Scope::TraitRefBoundary { s: this.scope };
1115                         this.with(scope, |_, this| {
1116                             this.visit_generics(generics);
1117                             for bound in bounds {
1118                                 this.visit_param_bound(bound);
1119                             }
1120                         })
1121                     });
1122                 }
1123             }
1124             _ => intravisit::walk_ty(self, ty),
1125         }
1126     }
1127
1128     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem<'tcx>) {
1129         use self::hir::TraitItemKind::*;
1130         match trait_item.kind {
1131             Fn(ref sig, _) => {
1132                 self.missing_named_lifetime_spots.push((&trait_item.generics).into());
1133                 let tcx = self.tcx;
1134                 self.visit_early_late(
1135                     Some(tcx.hir().get_parent_item(trait_item.hir_id())),
1136                     trait_item.hir_id(),
1137                     &sig.decl,
1138                     &trait_item.generics,
1139                     |this| intravisit::walk_trait_item(this, trait_item),
1140                 );
1141                 self.missing_named_lifetime_spots.pop();
1142             }
1143             Type(bounds, ref ty) => {
1144                 self.missing_named_lifetime_spots.push((&trait_item.generics).into());
1145                 let generics = &trait_item.generics;
1146                 let mut index = self.next_early_index();
1147                 debug!("visit_ty: index = {}", index);
1148                 let mut non_lifetime_count = 0;
1149                 let lifetimes = generics
1150                     .params
1151                     .iter()
1152                     .filter_map(|param| match param.kind {
1153                         GenericParamKind::Lifetime { .. } => {
1154                             Some(Region::early(self.tcx.hir(), &mut index, param))
1155                         }
1156                         GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => {
1157                             non_lifetime_count += 1;
1158                             None
1159                         }
1160                     })
1161                     .collect();
1162                 self.map.late_bound_vars.insert(trait_item.hir_id(), vec![]);
1163                 let scope = Scope::Binder {
1164                     hir_id: trait_item.hir_id(),
1165                     lifetimes,
1166                     next_early_index: index + non_lifetime_count,
1167                     s: self.scope,
1168                     track_lifetime_uses: true,
1169                     opaque_type_parent: true,
1170                     scope_type: BinderScopeType::Normal,
1171                     allow_late_bound: false,
1172                 };
1173                 self.with(scope, |old_scope, this| {
1174                     this.check_lifetime_params(old_scope, &generics.params);
1175                     let scope = Scope::TraitRefBoundary { s: this.scope };
1176                     this.with(scope, |_, this| {
1177                         this.visit_generics(generics);
1178                         for bound in bounds {
1179                             this.visit_param_bound(bound);
1180                         }
1181                         if let Some(ty) = ty {
1182                             this.visit_ty(ty);
1183                         }
1184                     })
1185                 });
1186                 self.missing_named_lifetime_spots.pop();
1187             }
1188             Const(_, _) => {
1189                 // Only methods and types support generics.
1190                 assert!(trait_item.generics.params.is_empty());
1191                 self.missing_named_lifetime_spots.push(MissingLifetimeSpot::Static);
1192                 intravisit::walk_trait_item(self, trait_item);
1193                 self.missing_named_lifetime_spots.pop();
1194             }
1195         }
1196     }
1197
1198     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem<'tcx>) {
1199         use self::hir::ImplItemKind::*;
1200         match impl_item.kind {
1201             Fn(ref sig, _) => {
1202                 self.missing_named_lifetime_spots.push((&impl_item.generics).into());
1203                 let tcx = self.tcx;
1204                 self.visit_early_late(
1205                     Some(tcx.hir().get_parent_item(impl_item.hir_id())),
1206                     impl_item.hir_id(),
1207                     &sig.decl,
1208                     &impl_item.generics,
1209                     |this| intravisit::walk_impl_item(this, impl_item),
1210                 );
1211                 self.missing_named_lifetime_spots.pop();
1212             }
1213             TyAlias(ref ty) => {
1214                 let generics = &impl_item.generics;
1215                 self.missing_named_lifetime_spots.push(generics.into());
1216                 let mut index = self.next_early_index();
1217                 let mut non_lifetime_count = 0;
1218                 debug!("visit_ty: index = {}", index);
1219                 let lifetimes: FxIndexMap<hir::ParamName, Region> = generics
1220                     .params
1221                     .iter()
1222                     .filter_map(|param| match param.kind {
1223                         GenericParamKind::Lifetime { .. } => {
1224                             Some(Region::early(self.tcx.hir(), &mut index, param))
1225                         }
1226                         GenericParamKind::Const { .. } | GenericParamKind::Type { .. } => {
1227                             non_lifetime_count += 1;
1228                             None
1229                         }
1230                     })
1231                     .collect();
1232                 self.map.late_bound_vars.insert(ty.hir_id, vec![]);
1233                 let scope = Scope::Binder {
1234                     hir_id: ty.hir_id,
1235                     lifetimes,
1236                     next_early_index: index + non_lifetime_count,
1237                     s: self.scope,
1238                     track_lifetime_uses: true,
1239                     opaque_type_parent: true,
1240                     scope_type: BinderScopeType::Normal,
1241                     allow_late_bound: true,
1242                 };
1243                 self.with(scope, |old_scope, this| {
1244                     this.check_lifetime_params(old_scope, &generics.params);
1245                     let scope = Scope::TraitRefBoundary { s: this.scope };
1246                     this.with(scope, |_, this| {
1247                         this.visit_generics(generics);
1248                         this.visit_ty(ty);
1249                     })
1250                 });
1251                 self.missing_named_lifetime_spots.pop();
1252             }
1253             Const(_, _) => {
1254                 // Only methods and types support generics.
1255                 assert!(impl_item.generics.params.is_empty());
1256                 self.missing_named_lifetime_spots.push(MissingLifetimeSpot::Static);
1257                 intravisit::walk_impl_item(self, impl_item);
1258                 self.missing_named_lifetime_spots.pop();
1259             }
1260         }
1261     }
1262
1263     #[tracing::instrument(level = "debug", skip(self))]
1264     fn visit_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
1265         if lifetime_ref.is_elided() {
1266             self.resolve_elided_lifetimes(&[lifetime_ref]);
1267             return;
1268         }
1269         if lifetime_ref.is_static() {
1270             self.insert_lifetime(lifetime_ref, Region::Static);
1271             return;
1272         }
1273         if self.is_in_const_generic && lifetime_ref.name != LifetimeName::Error {
1274             self.emit_non_static_lt_in_const_generic_error(lifetime_ref);
1275             return;
1276         }
1277         self.resolve_lifetime_ref(lifetime_ref);
1278     }
1279
1280     fn visit_assoc_type_binding(&mut self, type_binding: &'tcx hir::TypeBinding<'_>) {
1281         let scope = self.scope;
1282         if let Some(scope_for_path) = self.map.scope_for_path.as_mut() {
1283             // We add lifetime scope information for `Ident`s in associated type bindings and use
1284             // the `HirId` of the type binding as the key in `LifetimeMap`
1285             let lifetime_scope = get_lifetime_scopes_for_path(scope);
1286             let map = scope_for_path.entry(type_binding.hir_id.owner).or_default();
1287             map.insert(type_binding.hir_id.local_id, lifetime_scope);
1288         }
1289         hir::intravisit::walk_assoc_type_binding(self, type_binding);
1290     }
1291
1292     fn visit_path(&mut self, path: &'tcx hir::Path<'tcx>, _: hir::HirId) {
1293         for (i, segment) in path.segments.iter().enumerate() {
1294             let depth = path.segments.len() - i - 1;
1295             if let Some(ref args) = segment.args {
1296                 self.visit_segment_args(path.res, depth, args);
1297             }
1298
1299             let scope = self.scope;
1300             if let Some(scope_for_path) = self.map.scope_for_path.as_mut() {
1301                 // Add lifetime scope information to path segment. Note we cannot call `visit_path_segment`
1302                 // here because that call would yield to resolution problems due to `walk_path_segment`
1303                 // being called, which processes the path segments generic args, which we have already
1304                 // processed using `visit_segment_args`.
1305                 let lifetime_scope = get_lifetime_scopes_for_path(scope);
1306                 if let Some(hir_id) = segment.hir_id {
1307                     let map = scope_for_path.entry(hir_id.owner).or_default();
1308                     map.insert(hir_id.local_id, lifetime_scope);
1309                 }
1310             }
1311         }
1312     }
1313
1314     fn visit_path_segment(&mut self, path_span: Span, path_segment: &'tcx hir::PathSegment<'tcx>) {
1315         let scope = self.scope;
1316         if let Some(scope_for_path) = self.map.scope_for_path.as_mut() {
1317             let lifetime_scope = get_lifetime_scopes_for_path(scope);
1318             if let Some(hir_id) = path_segment.hir_id {
1319                 let map = scope_for_path.entry(hir_id.owner).or_default();
1320                 map.insert(hir_id.local_id, lifetime_scope);
1321             }
1322         }
1323
1324         intravisit::walk_path_segment(self, path_span, path_segment);
1325     }
1326
1327     fn visit_fn_decl(&mut self, fd: &'tcx hir::FnDecl<'tcx>) {
1328         let output = match fd.output {
1329             hir::FnRetTy::DefaultReturn(_) => None,
1330             hir::FnRetTy::Return(ref ty) => Some(&**ty),
1331         };
1332         self.visit_fn_like_elision(&fd.inputs, output);
1333     }
1334
1335     fn visit_generics(&mut self, generics: &'tcx hir::Generics<'tcx>) {
1336         let scope = Scope::TraitRefBoundary { s: self.scope };
1337         self.with(scope, |_, this| {
1338             for param in generics.params {
1339                 match param.kind {
1340                     GenericParamKind::Lifetime { .. } => {}
1341                     GenericParamKind::Type { ref default, .. } => {
1342                         walk_list!(this, visit_param_bound, param.bounds);
1343                         if let Some(ref ty) = default {
1344                             this.visit_ty(&ty);
1345                         }
1346                     }
1347                     GenericParamKind::Const { ref ty, default } => {
1348                         let was_in_const_generic = this.is_in_const_generic;
1349                         this.is_in_const_generic = true;
1350                         walk_list!(this, visit_param_bound, param.bounds);
1351                         this.visit_ty(&ty);
1352                         if let Some(default) = default {
1353                             this.visit_body(this.tcx.hir().body(default.body));
1354                         }
1355                         this.is_in_const_generic = was_in_const_generic;
1356                     }
1357                 }
1358             }
1359             for predicate in generics.where_clause.predicates {
1360                 match predicate {
1361                     &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate {
1362                         ref bounded_ty,
1363                         bounds,
1364                         ref bound_generic_params,
1365                         ..
1366                     }) => {
1367                         let (lifetimes, binders): (FxIndexMap<hir::ParamName, Region>, Vec<_>) =
1368                             bound_generic_params
1369                                 .iter()
1370                                 .filter(|param| {
1371                                     matches!(param.kind, GenericParamKind::Lifetime { .. })
1372                                 })
1373                                 .enumerate()
1374                                 .map(|(late_bound_idx, param)| {
1375                                     let pair =
1376                                         Region::late(late_bound_idx as u32, this.tcx.hir(), param);
1377                                     let r = late_region_as_bound_region(this.tcx, &pair.1);
1378                                     (pair, r)
1379                                 })
1380                                 .unzip();
1381                         this.map.late_bound_vars.insert(bounded_ty.hir_id, binders.clone());
1382                         let next_early_index = this.next_early_index();
1383                         // Even if there are no lifetimes defined here, we still wrap it in a binder
1384                         // scope. If there happens to be a nested poly trait ref (an error), that
1385                         // will be `Concatenating` anyways, so we don't have to worry about the depth
1386                         // being wrong.
1387                         let scope = Scope::Binder {
1388                             hir_id: bounded_ty.hir_id,
1389                             lifetimes,
1390                             s: this.scope,
1391                             next_early_index,
1392                             track_lifetime_uses: true,
1393                             opaque_type_parent: false,
1394                             scope_type: BinderScopeType::Normal,
1395                             allow_late_bound: true,
1396                         };
1397                         this.with(scope, |old_scope, this| {
1398                             this.check_lifetime_params(old_scope, &bound_generic_params);
1399                             this.visit_ty(&bounded_ty);
1400                             walk_list!(this, visit_param_bound, bounds);
1401                         })
1402                     }
1403                     &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate {
1404                         ref lifetime,
1405                         bounds,
1406                         ..
1407                     }) => {
1408                         this.visit_lifetime(lifetime);
1409                         walk_list!(this, visit_param_bound, bounds);
1410                     }
1411                     &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate {
1412                         ref lhs_ty,
1413                         ref rhs_ty,
1414                         ..
1415                     }) => {
1416                         this.visit_ty(lhs_ty);
1417                         this.visit_ty(rhs_ty);
1418                     }
1419                 }
1420             }
1421         })
1422     }
1423
1424     fn visit_param_bound(&mut self, bound: &'tcx hir::GenericBound<'tcx>) {
1425         match bound {
1426             hir::GenericBound::LangItemTrait(_, _, hir_id, _) => {
1427                 // FIXME(jackh726): This is pretty weird. `LangItemTrait` doesn't go
1428                 // through the regular poly trait ref code, so we don't get another
1429                 // chance to introduce a binder. For now, I'm keeping the existing logic
1430                 // of "if there isn't a Binder scope above us, add one", but I
1431                 // imagine there's a better way to go about this.
1432                 let (binders, scope_type) = self.poly_trait_ref_binder_info();
1433
1434                 self.map.late_bound_vars.insert(*hir_id, binders);
1435                 let scope = Scope::Binder {
1436                     hir_id: *hir_id,
1437                     lifetimes: FxIndexMap::default(),
1438                     s: self.scope,
1439                     next_early_index: self.next_early_index(),
1440                     track_lifetime_uses: true,
1441                     opaque_type_parent: false,
1442                     scope_type,
1443                     allow_late_bound: true,
1444                 };
1445                 self.with(scope, |_, this| {
1446                     intravisit::walk_param_bound(this, bound);
1447                 });
1448             }
1449             _ => intravisit::walk_param_bound(self, bound),
1450         }
1451     }
1452
1453     fn visit_poly_trait_ref(
1454         &mut self,
1455         trait_ref: &'tcx hir::PolyTraitRef<'tcx>,
1456         _modifier: hir::TraitBoundModifier,
1457     ) {
1458         debug!("visit_poly_trait_ref(trait_ref={:?})", trait_ref);
1459
1460         let should_pop_missing_lt = self.is_trait_ref_fn_scope(trait_ref);
1461
1462         let next_early_index = self.next_early_index();
1463         let (mut binders, scope_type) = self.poly_trait_ref_binder_info();
1464
1465         let initial_bound_vars = binders.len() as u32;
1466         let mut lifetimes: FxIndexMap<hir::ParamName, Region> = FxIndexMap::default();
1467         let binders_iter = trait_ref
1468             .bound_generic_params
1469             .iter()
1470             .filter(|param| matches!(param.kind, GenericParamKind::Lifetime { .. }))
1471             .enumerate()
1472             .map(|(late_bound_idx, param)| {
1473                 let pair =
1474                     Region::late(initial_bound_vars + late_bound_idx as u32, self.tcx.hir(), param);
1475                 let r = late_region_as_bound_region(self.tcx, &pair.1);
1476                 lifetimes.insert(pair.0, pair.1);
1477                 r
1478             });
1479         binders.extend(binders_iter);
1480
1481         debug!(?binders);
1482         self.map.late_bound_vars.insert(trait_ref.trait_ref.hir_ref_id, binders);
1483
1484         // Always introduce a scope here, even if this is in a where clause and
1485         // we introduced the binders around the bounded Ty. In that case, we
1486         // just reuse the concatenation functionality also present in nested trait
1487         // refs.
1488         let scope = Scope::Binder {
1489             hir_id: trait_ref.trait_ref.hir_ref_id,
1490             lifetimes,
1491             s: self.scope,
1492             next_early_index,
1493             track_lifetime_uses: true,
1494             opaque_type_parent: false,
1495             scope_type,
1496             allow_late_bound: true,
1497         };
1498         self.with(scope, |old_scope, this| {
1499             this.check_lifetime_params(old_scope, &trait_ref.bound_generic_params);
1500             walk_list!(this, visit_generic_param, trait_ref.bound_generic_params);
1501             this.visit_trait_ref(&trait_ref.trait_ref);
1502         });
1503
1504         if should_pop_missing_lt {
1505             self.missing_named_lifetime_spots.pop();
1506         }
1507     }
1508 }
1509
1510 #[derive(Copy, Clone, PartialEq)]
1511 enum ShadowKind {
1512     Label,
1513     Lifetime,
1514 }
1515 struct Original {
1516     kind: ShadowKind,
1517     span: Span,
1518 }
1519 struct Shadower {
1520     kind: ShadowKind,
1521     span: Span,
1522 }
1523
1524 fn original_label(span: Span) -> Original {
1525     Original { kind: ShadowKind::Label, span }
1526 }
1527 fn shadower_label(span: Span) -> Shadower {
1528     Shadower { kind: ShadowKind::Label, span }
1529 }
1530 fn original_lifetime(span: Span) -> Original {
1531     Original { kind: ShadowKind::Lifetime, span }
1532 }
1533 fn shadower_lifetime(param: &hir::GenericParam<'_>) -> Shadower {
1534     Shadower { kind: ShadowKind::Lifetime, span: param.span }
1535 }
1536
1537 impl ShadowKind {
1538     fn desc(&self) -> &'static str {
1539         match *self {
1540             ShadowKind::Label => "label",
1541             ShadowKind::Lifetime => "lifetime",
1542         }
1543     }
1544 }
1545
1546 fn signal_shadowing_problem(tcx: TyCtxt<'_>, name: Symbol, orig: Original, shadower: Shadower) {
1547     let mut err = if let (ShadowKind::Lifetime, ShadowKind::Lifetime) = (orig.kind, shadower.kind) {
1548         // lifetime/lifetime shadowing is an error
1549         struct_span_err!(
1550             tcx.sess,
1551             shadower.span,
1552             E0496,
1553             "{} name `{}` shadows a \
1554              {} name that is already in scope",
1555             shadower.kind.desc(),
1556             name,
1557             orig.kind.desc()
1558         )
1559         .forget_guarantee()
1560     } else {
1561         // shadowing involving a label is only a warning, due to issues with
1562         // labels and lifetimes not being macro-hygienic.
1563         tcx.sess.struct_span_warn(
1564             shadower.span,
1565             &format!(
1566                 "{} name `{}` shadows a \
1567                  {} name that is already in scope",
1568                 shadower.kind.desc(),
1569                 name,
1570                 orig.kind.desc()
1571             ),
1572         )
1573     };
1574     err.span_label(orig.span, "first declared here");
1575     err.span_label(shadower.span, format!("{} `{}` already in scope", orig.kind.desc(), name));
1576     err.emit();
1577 }
1578
1579 // Adds all labels in `b` to `ctxt.labels_in_fn`, signalling a warning
1580 // if one of the label shadows a lifetime or another label.
1581 fn extract_labels(ctxt: &mut LifetimeContext<'_, '_>, body: &hir::Body<'_>) {
1582     struct GatherLabels<'a, 'tcx> {
1583         tcx: TyCtxt<'tcx>,
1584         scope: ScopeRef<'a>,
1585         labels_in_fn: &'a mut Vec<Ident>,
1586     }
1587
1588     let mut gather =
1589         GatherLabels { tcx: ctxt.tcx, scope: ctxt.scope, labels_in_fn: &mut ctxt.labels_in_fn };
1590     gather.visit_body(body);
1591
1592     impl<'v, 'a, 'tcx> Visitor<'v> for GatherLabels<'a, 'tcx> {
1593         fn visit_expr(&mut self, ex: &hir::Expr<'_>) {
1594             if let Some(label) = expression_label(ex) {
1595                 for prior_label in &self.labels_in_fn[..] {
1596                     // FIXME (#24278): non-hygienic comparison
1597                     if label.name == prior_label.name {
1598                         signal_shadowing_problem(
1599                             self.tcx,
1600                             label.name,
1601                             original_label(prior_label.span),
1602                             shadower_label(label.span),
1603                         );
1604                     }
1605                 }
1606
1607                 check_if_label_shadows_lifetime(self.tcx, self.scope, label);
1608
1609                 self.labels_in_fn.push(label);
1610             }
1611             intravisit::walk_expr(self, ex)
1612         }
1613     }
1614
1615     fn expression_label(ex: &hir::Expr<'_>) -> Option<Ident> {
1616         match ex.kind {
1617             hir::ExprKind::Loop(_, Some(label), ..) => Some(label.ident),
1618             hir::ExprKind::Block(_, Some(label)) => Some(label.ident),
1619             _ => None,
1620         }
1621     }
1622
1623     fn check_if_label_shadows_lifetime(tcx: TyCtxt<'_>, mut scope: ScopeRef<'_>, label: Ident) {
1624         loop {
1625             match *scope {
1626                 Scope::Body { s, .. }
1627                 | Scope::Elision { s, .. }
1628                 | Scope::ObjectLifetimeDefault { s, .. }
1629                 | Scope::Supertrait { s, .. }
1630                 | Scope::TraitRefBoundary { s, .. } => {
1631                     scope = s;
1632                 }
1633
1634                 Scope::Root => {
1635                     return;
1636                 }
1637
1638                 Scope::Binder { ref lifetimes, s, .. } => {
1639                     // FIXME (#24278): non-hygienic comparison
1640                     if let Some(def) =
1641                         lifetimes.get(&hir::ParamName::Plain(label.normalize_to_macros_2_0()))
1642                     {
1643                         signal_shadowing_problem(
1644                             tcx,
1645                             label.name,
1646                             original_lifetime(tcx.def_span(def.id().unwrap().expect_local())),
1647                             shadower_label(label.span),
1648                         );
1649                         return;
1650                     }
1651                     scope = s;
1652                 }
1653             }
1654         }
1655     }
1656 }
1657
1658 fn compute_object_lifetime_defaults<'tcx>(
1659     tcx: TyCtxt<'tcx>,
1660     item: &hir::Item<'_>,
1661 ) -> Option<&'tcx [ObjectLifetimeDefault]> {
1662     match item.kind {
1663         hir::ItemKind::Struct(_, ref generics)
1664         | hir::ItemKind::Union(_, ref generics)
1665         | hir::ItemKind::Enum(_, ref generics)
1666         | hir::ItemKind::OpaqueTy(hir::OpaqueTy {
1667             ref generics,
1668             origin: hir::OpaqueTyOrigin::TyAlias,
1669             ..
1670         })
1671         | hir::ItemKind::TyAlias(_, ref generics)
1672         | hir::ItemKind::Trait(_, _, ref generics, ..) => {
1673             let result = object_lifetime_defaults_for_item(tcx, generics);
1674
1675             // Debugging aid.
1676             let attrs = tcx.hir().attrs(item.hir_id());
1677             if tcx.sess.contains_name(attrs, sym::rustc_object_lifetime_default) {
1678                 let object_lifetime_default_reprs: String = result
1679                     .iter()
1680                     .map(|set| match *set {
1681                         Set1::Empty => "BaseDefault".into(),
1682                         Set1::One(Region::Static) => "'static".into(),
1683                         Set1::One(Region::EarlyBound(mut i, _)) => generics
1684                             .params
1685                             .iter()
1686                             .find_map(|param| match param.kind {
1687                                 GenericParamKind::Lifetime { .. } => {
1688                                     if i == 0 {
1689                                         return Some(param.name.ident().to_string().into());
1690                                     }
1691                                     i -= 1;
1692                                     None
1693                                 }
1694                                 _ => None,
1695                             })
1696                             .unwrap(),
1697                         Set1::One(_) => bug!(),
1698                         Set1::Many => "Ambiguous".into(),
1699                     })
1700                     .collect::<Vec<Cow<'static, str>>>()
1701                     .join(",");
1702                 tcx.sess.span_err(item.span, &object_lifetime_default_reprs);
1703             }
1704
1705             Some(result)
1706         }
1707         _ => None,
1708     }
1709 }
1710
1711 /// Scan the bounds and where-clauses on parameters to extract bounds
1712 /// of the form `T:'a` so as to determine the `ObjectLifetimeDefault`
1713 /// for each type parameter.
1714 fn object_lifetime_defaults_for_item<'tcx>(
1715     tcx: TyCtxt<'tcx>,
1716     generics: &hir::Generics<'_>,
1717 ) -> &'tcx [ObjectLifetimeDefault] {
1718     fn add_bounds(set: &mut Set1<hir::LifetimeName>, bounds: &[hir::GenericBound<'_>]) {
1719         for bound in bounds {
1720             if let hir::GenericBound::Outlives(ref lifetime) = *bound {
1721                 set.insert(lifetime.name.normalize_to_macros_2_0());
1722             }
1723         }
1724     }
1725
1726     let process_param = |param: &hir::GenericParam<'_>| match param.kind {
1727         GenericParamKind::Lifetime { .. } => None,
1728         GenericParamKind::Type { .. } => {
1729             let mut set = Set1::Empty;
1730
1731             add_bounds(&mut set, &param.bounds);
1732
1733             let param_def_id = tcx.hir().local_def_id(param.hir_id);
1734             for predicate in generics.where_clause.predicates {
1735                 // Look for `type: ...` where clauses.
1736                 let hir::WherePredicate::BoundPredicate(ref data) = *predicate else { continue };
1737
1738                 // Ignore `for<'a> type: ...` as they can change what
1739                 // lifetimes mean (although we could "just" handle it).
1740                 if !data.bound_generic_params.is_empty() {
1741                     continue;
1742                 }
1743
1744                 let res = match data.bounded_ty.kind {
1745                     hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => path.res,
1746                     _ => continue,
1747                 };
1748
1749                 if res == Res::Def(DefKind::TyParam, param_def_id.to_def_id()) {
1750                     add_bounds(&mut set, &data.bounds);
1751                 }
1752             }
1753
1754             Some(match set {
1755                 Set1::Empty => Set1::Empty,
1756                 Set1::One(name) => {
1757                     if name == hir::LifetimeName::Static {
1758                         Set1::One(Region::Static)
1759                     } else {
1760                         generics
1761                             .params
1762                             .iter()
1763                             .filter_map(|param| match param.kind {
1764                                 GenericParamKind::Lifetime { .. } => {
1765                                     Some((param.hir_id, hir::LifetimeName::Param(param.name)))
1766                                 }
1767                                 _ => None,
1768                             })
1769                             .enumerate()
1770                             .find(|&(_, (_, lt_name))| lt_name == name)
1771                             .map_or(Set1::Many, |(i, (id, _))| {
1772                                 let def_id = tcx.hir().local_def_id(id);
1773                                 Set1::One(Region::EarlyBound(i as u32, def_id.to_def_id()))
1774                             })
1775                     }
1776                 }
1777                 Set1::Many => Set1::Many,
1778             })
1779         }
1780         GenericParamKind::Const { .. } => {
1781             // Generic consts don't impose any constraints.
1782             //
1783             // We still store a dummy value here to allow generic parameters
1784             // in an arbitrary order.
1785             Some(Set1::Empty)
1786         }
1787     };
1788
1789     tcx.arena.alloc_from_iter(generics.params.iter().filter_map(process_param))
1790 }
1791
1792 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
1793     fn with<F>(&mut self, wrap_scope: Scope<'_>, f: F)
1794     where
1795         F: for<'b> FnOnce(ScopeRef<'_>, &mut LifetimeContext<'b, 'tcx>),
1796     {
1797         let LifetimeContext { tcx, map, lifetime_uses, .. } = self;
1798         let labels_in_fn = take(&mut self.labels_in_fn);
1799         let xcrate_object_lifetime_defaults = take(&mut self.xcrate_object_lifetime_defaults);
1800         let missing_named_lifetime_spots = take(&mut self.missing_named_lifetime_spots);
1801         let mut this = LifetimeContext {
1802             tcx: *tcx,
1803             map,
1804             scope: &wrap_scope,
1805             is_in_fn_syntax: self.is_in_fn_syntax,
1806             is_in_const_generic: self.is_in_const_generic,
1807             trait_definition_only: self.trait_definition_only,
1808             labels_in_fn,
1809             xcrate_object_lifetime_defaults,
1810             lifetime_uses,
1811             missing_named_lifetime_spots,
1812         };
1813         let span = tracing::debug_span!("scope", scope = ?TruncatedScopeDebug(&this.scope));
1814         {
1815             let _enter = span.enter();
1816             f(self.scope, &mut this);
1817             if !self.trait_definition_only {
1818                 this.check_uses_for_lifetimes_defined_by_scope();
1819             }
1820         }
1821         self.labels_in_fn = this.labels_in_fn;
1822         self.xcrate_object_lifetime_defaults = this.xcrate_object_lifetime_defaults;
1823         self.missing_named_lifetime_spots = this.missing_named_lifetime_spots;
1824     }
1825
1826     /// helper method to determine the span to remove when suggesting the
1827     /// deletion of a lifetime
1828     fn lifetime_deletion_span(&self, name: Ident, generics: &hir::Generics<'_>) -> Option<Span> {
1829         generics.params.iter().enumerate().find_map(|(i, param)| {
1830             if param.name.ident() == name {
1831                 if generics.params.len() == 1 {
1832                     // if sole lifetime, remove the entire `<>` brackets
1833                     Some(generics.span)
1834                 } else {
1835                     // if removing within `<>` brackets, we also want to
1836                     // delete a leading or trailing comma as appropriate
1837                     if i >= generics.params.len() - 1 {
1838                         Some(generics.params[i - 1].span.shrink_to_hi().to(param.span))
1839                     } else {
1840                         Some(param.span.to(generics.params[i + 1].span.shrink_to_lo()))
1841                     }
1842                 }
1843             } else {
1844                 None
1845             }
1846         })
1847     }
1848
1849     // helper method to issue suggestions from `fn rah<'a>(&'a T)` to `fn rah(&T)`
1850     // or from `fn rah<'a>(T<'a>)` to `fn rah(T<'_>)`
1851     fn suggest_eliding_single_use_lifetime(
1852         &self,
1853         err: &mut Diagnostic,
1854         def_id: DefId,
1855         lifetime: &hir::Lifetime,
1856     ) {
1857         let name = lifetime.name.ident();
1858         let remove_decl = self
1859             .tcx
1860             .parent(def_id)
1861             .and_then(|parent_def_id| parent_def_id.as_local())
1862             .and_then(|parent_def_id| self.tcx.hir().get_generics(parent_def_id))
1863             .and_then(|generics| self.lifetime_deletion_span(name, generics));
1864
1865         let mut remove_use = None;
1866         let mut elide_use = None;
1867         let mut find_arg_use_span = |inputs: &[hir::Ty<'_>]| {
1868             for input in inputs {
1869                 match input.kind {
1870                     hir::TyKind::Rptr(lt, _) => {
1871                         if lt.name.ident() == name {
1872                             // include the trailing whitespace between the lifetime and type names
1873                             let lt_through_ty_span = lifetime.span.to(input.span.shrink_to_hi());
1874                             remove_use = Some(
1875                                 self.tcx
1876                                     .sess
1877                                     .source_map()
1878                                     .span_until_non_whitespace(lt_through_ty_span),
1879                             );
1880                             break;
1881                         }
1882                     }
1883                     hir::TyKind::Path(QPath::Resolved(_, path)) => {
1884                         let last_segment = &path.segments[path.segments.len() - 1];
1885                         let generics = last_segment.args();
1886                         for arg in generics.args.iter() {
1887                             if let GenericArg::Lifetime(lt) = arg {
1888                                 if lt.name.ident() == name {
1889                                     elide_use = Some(lt.span);
1890                                     break;
1891                                 }
1892                             }
1893                         }
1894                         break;
1895                     }
1896                     _ => {}
1897                 }
1898             }
1899         };
1900         if let Node::Lifetime(hir_lifetime) = self.tcx.hir().get(lifetime.hir_id) {
1901             if let Some(parent) =
1902                 self.tcx.hir().find_by_def_id(self.tcx.hir().get_parent_item(hir_lifetime.hir_id))
1903             {
1904                 match parent {
1905                     Node::Item(item) => {
1906                         if let hir::ItemKind::Fn(sig, _, _) = &item.kind {
1907                             find_arg_use_span(sig.decl.inputs);
1908                         }
1909                     }
1910                     Node::ImplItem(impl_item) => {
1911                         if let hir::ImplItemKind::Fn(sig, _) = &impl_item.kind {
1912                             find_arg_use_span(sig.decl.inputs);
1913                         }
1914                     }
1915                     _ => {}
1916                 }
1917             }
1918         }
1919
1920         let msg = "elide the single-use lifetime";
1921         match (remove_decl, remove_use, elide_use) {
1922             (Some(decl_span), Some(use_span), None) => {
1923                 // if both declaration and use deletion spans start at the same
1924                 // place ("start at" because the latter includes trailing
1925                 // whitespace), then this is an in-band lifetime
1926                 if decl_span.shrink_to_lo() == use_span.shrink_to_lo() {
1927                     err.span_suggestion(
1928                         use_span,
1929                         msg,
1930                         String::new(),
1931                         Applicability::MachineApplicable,
1932                     );
1933                 } else {
1934                     err.multipart_suggestion(
1935                         msg,
1936                         vec![(decl_span, String::new()), (use_span, String::new())],
1937                         Applicability::MachineApplicable,
1938                     );
1939                 }
1940             }
1941             (Some(decl_span), None, Some(use_span)) => {
1942                 err.multipart_suggestion(
1943                     msg,
1944                     vec![(decl_span, String::new()), (use_span, "'_".to_owned())],
1945                     Applicability::MachineApplicable,
1946                 );
1947             }
1948             _ => {}
1949         }
1950     }
1951
1952     fn check_uses_for_lifetimes_defined_by_scope(&mut self) {
1953         let Scope::Binder { lifetimes: defined_by, .. } = self.scope else {
1954             debug!("check_uses_for_lifetimes_defined_by_scope: not in a binder scope");
1955             return;
1956         };
1957
1958         let def_ids: Vec<_> = defined_by
1959             .values()
1960             .flat_map(|region| match region {
1961                 Region::EarlyBound(_, def_id)
1962                 | Region::LateBound(_, _, def_id)
1963                 | Region::Free(_, def_id) => Some(*def_id),
1964
1965                 Region::LateBoundAnon(..) | Region::Static => None,
1966             })
1967             .collect();
1968
1969         'lifetimes: for def_id in def_ids {
1970             debug!("check_uses_for_lifetimes_defined_by_scope: def_id = {:?}", def_id);
1971
1972             let lifetimeuseset = self.lifetime_uses.remove(&def_id);
1973
1974             debug!(
1975                 "check_uses_for_lifetimes_defined_by_scope: lifetimeuseset = {:?}",
1976                 lifetimeuseset
1977             );
1978
1979             match lifetimeuseset {
1980                 Some(LifetimeUseSet::One(lifetime)) => {
1981                     debug!(?def_id);
1982                     if let Some((id, span, name)) =
1983                         match self.tcx.hir().get_by_def_id(def_id.expect_local()) {
1984                             Node::Lifetime(hir_lifetime) => Some((
1985                                 hir_lifetime.hir_id,
1986                                 hir_lifetime.span,
1987                                 hir_lifetime.name.ident(),
1988                             )),
1989                             Node::GenericParam(param) => {
1990                                 Some((param.hir_id, param.span, param.name.ident()))
1991                             }
1992                             _ => None,
1993                         }
1994                     {
1995                         debug!("id = {:?} span = {:?} name = {:?}", id, span, name);
1996                         if name.name == kw::UnderscoreLifetime {
1997                             continue;
1998                         }
1999
2000                         if let Some(parent_def_id) = self.tcx.parent(def_id) {
2001                             if let Some(def_id) = parent_def_id.as_local() {
2002                                 // lifetimes in `derive` expansions don't count (Issue #53738)
2003                                 if self
2004                                     .tcx
2005                                     .get_attrs(def_id.to_def_id())
2006                                     .iter()
2007                                     .any(|attr| attr.has_name(sym::automatically_derived))
2008                                 {
2009                                     continue;
2010                                 }
2011
2012                                 // opaque types generated when desugaring an async function can have a single
2013                                 // use lifetime even if it is explicitly denied (Issue #77175)
2014                                 if let hir::Node::Item(hir::Item {
2015                                     kind: hir::ItemKind::OpaqueTy(ref opaque),
2016                                     ..
2017                                 }) = self.tcx.hir().get_by_def_id(def_id)
2018                                 {
2019                                     if !matches!(opaque.origin, hir::OpaqueTyOrigin::AsyncFn(..)) {
2020                                         continue 'lifetimes;
2021                                     }
2022                                     // We want to do this only if the lifetime identifier is already defined
2023                                     // in the async function that generated this. Otherwise it could be
2024                                     // an opaque type defined by the developer and we still want this
2025                                     // lint to fail compilation
2026                                     for p in opaque.generics.params {
2027                                         if defined_by.contains_key(&p.name) {
2028                                             continue 'lifetimes;
2029                                         }
2030                                     }
2031                                 }
2032                             }
2033                         }
2034
2035                         self.tcx.struct_span_lint_hir(
2036                             lint::builtin::SINGLE_USE_LIFETIMES,
2037                             id,
2038                             span,
2039                             |lint| {
2040                                 let mut err = lint.build(&format!(
2041                                     "lifetime parameter `{}` only used once",
2042                                     name
2043                                 ));
2044                                 if span == lifetime.span {
2045                                     // spans are the same for in-band lifetime declarations
2046                                     err.span_label(span, "this lifetime is only used here");
2047                                 } else {
2048                                     err.span_label(span, "this lifetime...");
2049                                     err.span_label(lifetime.span, "...is used only here");
2050                                 }
2051                                 self.suggest_eliding_single_use_lifetime(
2052                                     &mut err, def_id, lifetime,
2053                                 );
2054                                 err.emit();
2055                             },
2056                         );
2057                     }
2058                 }
2059                 Some(LifetimeUseSet::Many) => {
2060                     debug!("not one use lifetime");
2061                 }
2062                 None => {
2063                     if let Some((id, span, name)) =
2064                         match self.tcx.hir().get_by_def_id(def_id.expect_local()) {
2065                             Node::Lifetime(hir_lifetime) => Some((
2066                                 hir_lifetime.hir_id,
2067                                 hir_lifetime.span,
2068                                 hir_lifetime.name.ident(),
2069                             )),
2070                             Node::GenericParam(param) => {
2071                                 Some((param.hir_id, param.span, param.name.ident()))
2072                             }
2073                             _ => None,
2074                         }
2075                     {
2076                         debug!("id ={:?} span = {:?} name = {:?}", id, span, name);
2077                         self.tcx.struct_span_lint_hir(
2078                             lint::builtin::UNUSED_LIFETIMES,
2079                             id,
2080                             span,
2081                             |lint| {
2082                                 let mut err = lint
2083                                     .build(&format!("lifetime parameter `{}` never used", name));
2084                                 if let Some(parent_def_id) = self.tcx.parent(def_id) {
2085                                     if let Some(generics) =
2086                                         self.tcx.hir().get_generics(parent_def_id.expect_local())
2087                                     {
2088                                         let unused_lt_span =
2089                                             self.lifetime_deletion_span(name, generics);
2090                                         if let Some(span) = unused_lt_span {
2091                                             err.span_suggestion(
2092                                                 span,
2093                                                 "elide the unused lifetime",
2094                                                 String::new(),
2095                                                 Applicability::MachineApplicable,
2096                                             );
2097                                         }
2098                                     }
2099                                 }
2100                                 err.emit();
2101                             },
2102                         );
2103                     }
2104                 }
2105             }
2106         }
2107     }
2108
2109     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
2110     ///
2111     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
2112     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
2113     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
2114     ///
2115     /// For example:
2116     ///
2117     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
2118     ///
2119     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
2120     /// lifetimes may be interspersed together.
2121     ///
2122     /// If early bound lifetimes are present, we separate them into their own list (and likewise
2123     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
2124     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
2125     /// bound lifetimes are resolved by name and associated with a binder ID (`binder_id`), so the
2126     /// ordering is not important there.
2127     fn visit_early_late<F>(
2128         &mut self,
2129         parent_id: Option<LocalDefId>,
2130         hir_id: hir::HirId,
2131         decl: &'tcx hir::FnDecl<'tcx>,
2132         generics: &'tcx hir::Generics<'tcx>,
2133         walk: F,
2134     ) where
2135         F: for<'b, 'c> FnOnce(&'b mut LifetimeContext<'c, 'tcx>),
2136     {
2137         insert_late_bound_lifetimes(self.map, decl, generics);
2138
2139         // Find the start of nested early scopes, e.g., in methods.
2140         let mut next_early_index = 0;
2141         if let Some(parent_id) = parent_id {
2142             let parent = self.tcx.hir().expect_item(parent_id);
2143             if sub_items_have_self_param(&parent.kind) {
2144                 next_early_index += 1; // Self comes before lifetimes
2145             }
2146             match parent.kind {
2147                 hir::ItemKind::Trait(_, _, ref generics, ..)
2148                 | hir::ItemKind::Impl(hir::Impl { ref generics, .. }) => {
2149                     next_early_index += generics.params.len() as u32;
2150                 }
2151                 _ => {}
2152             }
2153         }
2154
2155         let mut non_lifetime_count = 0;
2156         let mut named_late_bound_vars = 0;
2157         let lifetimes: FxIndexMap<hir::ParamName, Region> = generics
2158             .params
2159             .iter()
2160             .filter_map(|param| match param.kind {
2161                 GenericParamKind::Lifetime { .. } => {
2162                     if self.map.late_bound.contains(&param.hir_id) {
2163                         let late_bound_idx = named_late_bound_vars;
2164                         named_late_bound_vars += 1;
2165                         Some(Region::late(late_bound_idx, self.tcx.hir(), param))
2166                     } else {
2167                         Some(Region::early(self.tcx.hir(), &mut next_early_index, param))
2168                     }
2169                 }
2170                 GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => {
2171                     non_lifetime_count += 1;
2172                     None
2173                 }
2174             })
2175             .collect();
2176         let next_early_index = next_early_index + non_lifetime_count;
2177
2178         let binders: Vec<_> = generics
2179             .params
2180             .iter()
2181             .filter(|param| {
2182                 matches!(param.kind, GenericParamKind::Lifetime { .. })
2183                     && self.map.late_bound.contains(&param.hir_id)
2184             })
2185             .enumerate()
2186             .map(|(late_bound_idx, param)| {
2187                 let pair = Region::late(late_bound_idx as u32, self.tcx.hir(), param);
2188                 late_region_as_bound_region(self.tcx, &pair.1)
2189             })
2190             .collect();
2191         self.map.late_bound_vars.insert(hir_id, binders);
2192         let scope = Scope::Binder {
2193             hir_id,
2194             lifetimes,
2195             next_early_index,
2196             s: self.scope,
2197             opaque_type_parent: true,
2198             track_lifetime_uses: false,
2199             scope_type: BinderScopeType::Normal,
2200             allow_late_bound: true,
2201         };
2202         self.with(scope, move |old_scope, this| {
2203             this.check_lifetime_params(old_scope, &generics.params);
2204             walk(this);
2205         });
2206     }
2207
2208     fn next_early_index_helper(&self, only_opaque_type_parent: bool) -> u32 {
2209         let mut scope = self.scope;
2210         loop {
2211             match *scope {
2212                 Scope::Root => return 0,
2213
2214                 Scope::Binder { next_early_index, opaque_type_parent, .. }
2215                     if (!only_opaque_type_parent || opaque_type_parent) =>
2216                 {
2217                     return next_early_index;
2218                 }
2219
2220                 Scope::Binder { s, .. }
2221                 | Scope::Body { s, .. }
2222                 | Scope::Elision { s, .. }
2223                 | Scope::ObjectLifetimeDefault { s, .. }
2224                 | Scope::Supertrait { s, .. }
2225                 | Scope::TraitRefBoundary { s, .. } => scope = s,
2226             }
2227         }
2228     }
2229
2230     /// Returns the next index one would use for an early-bound-region
2231     /// if extending the current scope.
2232     fn next_early_index(&self) -> u32 {
2233         self.next_early_index_helper(true)
2234     }
2235
2236     /// Returns the next index one would use for an `impl Trait` that
2237     /// is being converted into an opaque type alias `impl Trait`. This will be the
2238     /// next early index from the enclosing item, for the most
2239     /// part. See the `opaque_type_parent` field for more info.
2240     fn next_early_index_for_opaque_type(&self) -> u32 {
2241         self.next_early_index_helper(false)
2242     }
2243
2244     fn resolve_lifetime_ref(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
2245         debug!("resolve_lifetime_ref(lifetime_ref={:?})", lifetime_ref);
2246
2247         // If we've already reported an error, just ignore `lifetime_ref`.
2248         if let LifetimeName::Error = lifetime_ref.name {
2249             return;
2250         }
2251
2252         // Walk up the scope chain, tracking the number of fn scopes
2253         // that we pass through, until we find a lifetime with the
2254         // given name or we run out of scopes.
2255         // search.
2256         let mut late_depth = 0;
2257         let mut scope = self.scope;
2258         let mut outermost_body = None;
2259         let result = loop {
2260             match *scope {
2261                 Scope::Body { id, s } => {
2262                     // Non-static lifetimes are prohibited in anonymous constants without
2263                     // `generic_const_exprs`.
2264                     self.maybe_emit_forbidden_non_static_lifetime_error(id, lifetime_ref);
2265
2266                     outermost_body = Some(id);
2267                     scope = s;
2268                 }
2269
2270                 Scope::Root => {
2271                     break None;
2272                 }
2273
2274                 Scope::Binder { ref lifetimes, scope_type, s, .. } => {
2275                     match lifetime_ref.name {
2276                         LifetimeName::Param(param_name) => {
2277                             if let Some(&def) = lifetimes.get(&param_name.normalize_to_macros_2_0())
2278                             {
2279                                 break Some(def.shifted(late_depth));
2280                             }
2281                         }
2282                         _ => bug!("expected LifetimeName::Param"),
2283                     }
2284                     match scope_type {
2285                         BinderScopeType::Normal => late_depth += 1,
2286                         BinderScopeType::Concatenating => {}
2287                     }
2288                     scope = s;
2289                 }
2290
2291                 Scope::Elision { s, .. }
2292                 | Scope::ObjectLifetimeDefault { s, .. }
2293                 | Scope::Supertrait { s, .. }
2294                 | Scope::TraitRefBoundary { s, .. } => {
2295                     scope = s;
2296                 }
2297             }
2298         };
2299
2300         if let Some(mut def) = result {
2301             if let Region::EarlyBound(..) = def {
2302                 // Do not free early-bound regions, only late-bound ones.
2303             } else if let Some(body_id) = outermost_body {
2304                 let fn_id = self.tcx.hir().body_owner(body_id);
2305                 match self.tcx.hir().get(fn_id) {
2306                     Node::Item(&hir::Item { kind: hir::ItemKind::Fn(..), .. })
2307                     | Node::TraitItem(&hir::TraitItem {
2308                         kind: hir::TraitItemKind::Fn(..), ..
2309                     })
2310                     | Node::ImplItem(&hir::ImplItem { kind: hir::ImplItemKind::Fn(..), .. }) => {
2311                         let scope = self.tcx.hir().local_def_id(fn_id);
2312                         def = Region::Free(scope.to_def_id(), def.id().unwrap());
2313                     }
2314                     _ => {}
2315                 }
2316             }
2317
2318             self.insert_lifetime(lifetime_ref, def);
2319         } else {
2320             self.emit_undeclared_lifetime_error(lifetime_ref);
2321         }
2322     }
2323
2324     fn visit_segment_args(
2325         &mut self,
2326         res: Res,
2327         depth: usize,
2328         generic_args: &'tcx hir::GenericArgs<'tcx>,
2329     ) {
2330         debug!(
2331             "visit_segment_args(res={:?}, depth={:?}, generic_args={:?})",
2332             res, depth, generic_args,
2333         );
2334
2335         if generic_args.parenthesized {
2336             let was_in_fn_syntax = self.is_in_fn_syntax;
2337             self.is_in_fn_syntax = true;
2338             self.visit_fn_like_elision(generic_args.inputs(), Some(generic_args.bindings[0].ty()));
2339             self.is_in_fn_syntax = was_in_fn_syntax;
2340             return;
2341         }
2342
2343         let mut elide_lifetimes = true;
2344         let lifetimes: Vec<_> = generic_args
2345             .args
2346             .iter()
2347             .filter_map(|arg| match arg {
2348                 hir::GenericArg::Lifetime(lt) => {
2349                     if !lt.is_elided() {
2350                         elide_lifetimes = false;
2351                     }
2352                     Some(lt)
2353                 }
2354                 _ => None,
2355             })
2356             .collect();
2357         // We short-circuit here if all are elided in order to pluralize
2358         // possible errors
2359         if elide_lifetimes {
2360             self.resolve_elided_lifetimes(&lifetimes);
2361         } else {
2362             lifetimes.iter().for_each(|lt| self.visit_lifetime(lt));
2363         }
2364
2365         // Figure out if this is a type/trait segment,
2366         // which requires object lifetime defaults.
2367         let parent_def_id = |this: &mut Self, def_id: DefId| {
2368             let def_key = this.tcx.def_key(def_id);
2369             DefId { krate: def_id.krate, index: def_key.parent.expect("missing parent") }
2370         };
2371         let type_def_id = match res {
2372             Res::Def(DefKind::AssocTy, def_id) if depth == 1 => Some(parent_def_id(self, def_id)),
2373             Res::Def(DefKind::Variant, def_id) if depth == 0 => Some(parent_def_id(self, def_id)),
2374             Res::Def(
2375                 DefKind::Struct
2376                 | DefKind::Union
2377                 | DefKind::Enum
2378                 | DefKind::TyAlias
2379                 | DefKind::Trait,
2380                 def_id,
2381             ) if depth == 0 => Some(def_id),
2382             _ => None,
2383         };
2384
2385         debug!("visit_segment_args: type_def_id={:?}", type_def_id);
2386
2387         // Compute a vector of defaults, one for each type parameter,
2388         // per the rules given in RFCs 599 and 1156. Example:
2389         //
2390         // ```rust
2391         // struct Foo<'a, T: 'a, U> { }
2392         // ```
2393         //
2394         // If you have `Foo<'x, dyn Bar, dyn Baz>`, we want to default
2395         // `dyn Bar` to `dyn Bar + 'x` (because of the `T: 'a` bound)
2396         // and `dyn Baz` to `dyn Baz + 'static` (because there is no
2397         // such bound).
2398         //
2399         // Therefore, we would compute `object_lifetime_defaults` to a
2400         // vector like `['x, 'static]`. Note that the vector only
2401         // includes type parameters.
2402         let object_lifetime_defaults = type_def_id.map_or_else(Vec::new, |def_id| {
2403             let in_body = {
2404                 let mut scope = self.scope;
2405                 loop {
2406                     match *scope {
2407                         Scope::Root => break false,
2408
2409                         Scope::Body { .. } => break true,
2410
2411                         Scope::Binder { s, .. }
2412                         | Scope::Elision { s, .. }
2413                         | Scope::ObjectLifetimeDefault { s, .. }
2414                         | Scope::Supertrait { s, .. }
2415                         | Scope::TraitRefBoundary { s, .. } => {
2416                             scope = s;
2417                         }
2418                     }
2419                 }
2420             };
2421
2422             let map = &self.map;
2423             let set_to_region = |set: &ObjectLifetimeDefault| match *set {
2424                 Set1::Empty => {
2425                     if in_body {
2426                         None
2427                     } else {
2428                         Some(Region::Static)
2429                     }
2430                 }
2431                 Set1::One(r) => {
2432                     let lifetimes = generic_args.args.iter().filter_map(|arg| match arg {
2433                         GenericArg::Lifetime(lt) => Some(lt),
2434                         _ => None,
2435                     });
2436                     r.subst(lifetimes, map)
2437                 }
2438                 Set1::Many => None,
2439             };
2440             if let Some(def_id) = def_id.as_local() {
2441                 let id = self.tcx.hir().local_def_id_to_hir_id(def_id);
2442                 self.tcx
2443                     .object_lifetime_defaults(id.owner)
2444                     .unwrap()
2445                     .iter()
2446                     .map(set_to_region)
2447                     .collect()
2448             } else {
2449                 let tcx = self.tcx;
2450                 self.xcrate_object_lifetime_defaults
2451                     .entry(def_id)
2452                     .or_insert_with(|| {
2453                         tcx.generics_of(def_id)
2454                             .params
2455                             .iter()
2456                             .filter_map(|param| match param.kind {
2457                                 GenericParamDefKind::Type { object_lifetime_default, .. } => {
2458                                     Some(object_lifetime_default)
2459                                 }
2460                                 GenericParamDefKind::Const { .. } => Some(Set1::Empty),
2461                                 GenericParamDefKind::Lifetime => None,
2462                             })
2463                             .collect()
2464                     })
2465                     .iter()
2466                     .map(set_to_region)
2467                     .collect()
2468             }
2469         });
2470
2471         debug!("visit_segment_args: object_lifetime_defaults={:?}", object_lifetime_defaults);
2472
2473         let mut i = 0;
2474         for arg in generic_args.args {
2475             match arg {
2476                 GenericArg::Lifetime(_) => {}
2477                 GenericArg::Type(ty) => {
2478                     if let Some(&lt) = object_lifetime_defaults.get(i) {
2479                         let scope = Scope::ObjectLifetimeDefault { lifetime: lt, s: self.scope };
2480                         self.with(scope, |_, this| this.visit_ty(ty));
2481                     } else {
2482                         self.visit_ty(ty);
2483                     }
2484                     i += 1;
2485                 }
2486                 GenericArg::Const(ct) => {
2487                     self.visit_anon_const(&ct.value);
2488                     i += 1;
2489                 }
2490                 GenericArg::Infer(inf) => {
2491                     self.visit_id(inf.hir_id);
2492                     i += 1;
2493                 }
2494             }
2495         }
2496
2497         // Hack: when resolving the type `XX` in binding like `dyn
2498         // Foo<'b, Item = XX>`, the current object-lifetime default
2499         // would be to examine the trait `Foo` to check whether it has
2500         // a lifetime bound declared on `Item`. e.g., if `Foo` is
2501         // declared like so, then the default object lifetime bound in
2502         // `XX` should be `'b`:
2503         //
2504         // ```rust
2505         // trait Foo<'a> {
2506         //   type Item: 'a;
2507         // }
2508         // ```
2509         //
2510         // but if we just have `type Item;`, then it would be
2511         // `'static`. However, we don't get all of this logic correct.
2512         //
2513         // Instead, we do something hacky: if there are no lifetime parameters
2514         // to the trait, then we simply use a default object lifetime
2515         // bound of `'static`, because there is no other possibility. On the other hand,
2516         // if there ARE lifetime parameters, then we require the user to give an
2517         // explicit bound for now.
2518         //
2519         // This is intended to leave room for us to implement the
2520         // correct behavior in the future.
2521         let has_lifetime_parameter =
2522             generic_args.args.iter().any(|arg| matches!(arg, GenericArg::Lifetime(_)));
2523
2524         // Resolve lifetimes found in the bindings, so either in the type `XX` in `Item = XX` or
2525         // in the trait ref `YY<...>` in `Item: YY<...>`.
2526         for binding in generic_args.bindings {
2527             let scope = Scope::ObjectLifetimeDefault {
2528                 lifetime: if has_lifetime_parameter { None } else { Some(Region::Static) },
2529                 s: self.scope,
2530             };
2531             if let Some(type_def_id) = type_def_id {
2532                 let lifetimes = LifetimeContext::supertrait_hrtb_lifetimes(
2533                     self.tcx,
2534                     type_def_id,
2535                     binding.ident,
2536                 );
2537                 self.with(scope, |_, this| {
2538                     let scope = Scope::Supertrait {
2539                         lifetimes: lifetimes.unwrap_or_default(),
2540                         s: this.scope,
2541                     };
2542                     this.with(scope, |_, this| this.visit_assoc_type_binding(binding));
2543                 });
2544             } else {
2545                 self.with(scope, |_, this| this.visit_assoc_type_binding(binding));
2546             }
2547         }
2548     }
2549
2550     /// Returns all the late-bound vars that come into scope from supertrait HRTBs, based on the
2551     /// associated type name and starting trait.
2552     /// For example, imagine we have
2553     /// ```rust
2554     /// trait Foo<'a, 'b> {
2555     ///   type As;
2556     /// }
2557     /// trait Bar<'b>: for<'a> Foo<'a, 'b> {}
2558     /// trait Bar: for<'b> Bar<'b> {}
2559     /// ```
2560     /// In this case, if we wanted to the supertrait HRTB lifetimes for `As` on
2561     /// the starting trait `Bar`, we would return `Some(['b, 'a])`.
2562     fn supertrait_hrtb_lifetimes(
2563         tcx: TyCtxt<'tcx>,
2564         def_id: DefId,
2565         assoc_name: Ident,
2566     ) -> Option<Vec<ty::BoundVariableKind>> {
2567         let trait_defines_associated_type_named = |trait_def_id: DefId| {
2568             tcx.associated_items(trait_def_id)
2569                 .find_by_name_and_kind(tcx, assoc_name, ty::AssocKind::Type, trait_def_id)
2570                 .is_some()
2571         };
2572
2573         use smallvec::{smallvec, SmallVec};
2574         let mut stack: SmallVec<[(DefId, SmallVec<[ty::BoundVariableKind; 8]>); 8]> =
2575             smallvec![(def_id, smallvec![])];
2576         let mut visited: FxHashSet<DefId> = FxHashSet::default();
2577         loop {
2578             let Some((def_id, bound_vars)) = stack.pop() else {
2579                 break None;
2580             };
2581             // See issue #83753. If someone writes an associated type on a non-trait, just treat it as
2582             // there being no supertrait HRTBs.
2583             match tcx.def_kind(def_id) {
2584                 DefKind::Trait | DefKind::TraitAlias | DefKind::Impl => {}
2585                 _ => break None,
2586             }
2587
2588             if trait_defines_associated_type_named(def_id) {
2589                 break Some(bound_vars.into_iter().collect());
2590             }
2591             let predicates =
2592                 tcx.super_predicates_that_define_assoc_type((def_id, Some(assoc_name)));
2593             let obligations = predicates.predicates.iter().filter_map(|&(pred, _)| {
2594                 let bound_predicate = pred.kind();
2595                 match bound_predicate.skip_binder() {
2596                     ty::PredicateKind::Trait(data) => {
2597                         // The order here needs to match what we would get from `subst_supertrait`
2598                         let pred_bound_vars = bound_predicate.bound_vars();
2599                         let mut all_bound_vars = bound_vars.clone();
2600                         all_bound_vars.extend(pred_bound_vars.iter());
2601                         let super_def_id = data.trait_ref.def_id;
2602                         Some((super_def_id, all_bound_vars))
2603                     }
2604                     _ => None,
2605                 }
2606             });
2607
2608             let obligations = obligations.filter(|o| visited.insert(o.0));
2609             stack.extend(obligations);
2610         }
2611     }
2612
2613     #[tracing::instrument(level = "debug", skip(self))]
2614     fn visit_fn_like_elision(
2615         &mut self,
2616         inputs: &'tcx [hir::Ty<'tcx>],
2617         output: Option<&'tcx hir::Ty<'tcx>>,
2618     ) {
2619         debug!("visit_fn_like_elision: enter");
2620         let mut scope = &*self.scope;
2621         let hir_id = loop {
2622             match scope {
2623                 Scope::Binder { hir_id, allow_late_bound: true, .. } => {
2624                     break *hir_id;
2625                 }
2626                 Scope::ObjectLifetimeDefault { ref s, .. }
2627                 | Scope::Elision { ref s, .. }
2628                 | Scope::Supertrait { ref s, .. }
2629                 | Scope::TraitRefBoundary { ref s, .. } => {
2630                     scope = *s;
2631                 }
2632                 Scope::Root
2633                 | Scope::Body { .. }
2634                 | Scope::Binder { allow_late_bound: false, .. } => {
2635                     // See issues #83907 and #83693. Just bail out from looking inside.
2636                     // See the issue #95023 for not allowing late bound
2637                     self.tcx.sess.delay_span_bug(
2638                         rustc_span::DUMMY_SP,
2639                         "In fn_like_elision without appropriate scope above",
2640                     );
2641                     return;
2642                 }
2643             }
2644         };
2645         // While not strictly necessary, we gather anon lifetimes *before* actually
2646         // visiting the argument types.
2647         let mut gather = GatherAnonLifetimes { anon_count: 0 };
2648         for input in inputs {
2649             gather.visit_ty(input);
2650         }
2651         trace!(?gather.anon_count);
2652         let late_bound_vars = self.map.late_bound_vars.entry(hir_id).or_default();
2653         let named_late_bound_vars = late_bound_vars.len() as u32;
2654         late_bound_vars.extend(
2655             (0..gather.anon_count).map(|var| ty::BoundVariableKind::Region(ty::BrAnon(var))),
2656         );
2657         let arg_scope = Scope::Elision {
2658             elide: Elide::FreshLateAnon(named_late_bound_vars, Cell::new(0)),
2659             s: self.scope,
2660         };
2661         self.with(arg_scope, |_, this| {
2662             for input in inputs {
2663                 this.visit_ty(input);
2664             }
2665         });
2666
2667         let Some(output) = output else { return };
2668
2669         debug!("determine output");
2670
2671         // Figure out if there's a body we can get argument names from,
2672         // and whether there's a `self` argument (treated specially).
2673         let mut assoc_item_kind = None;
2674         let mut impl_self = None;
2675         let parent = self.tcx.hir().get_parent_node(output.hir_id);
2676         let body = match self.tcx.hir().get(parent) {
2677             // `fn` definitions and methods.
2678             Node::Item(&hir::Item { kind: hir::ItemKind::Fn(.., body), .. }) => Some(body),
2679
2680             Node::TraitItem(&hir::TraitItem { kind: hir::TraitItemKind::Fn(_, ref m), .. }) => {
2681                 if let hir::ItemKind::Trait(.., ref trait_items) =
2682                     self.tcx.hir().expect_item(self.tcx.hir().get_parent_item(parent)).kind
2683                 {
2684                     assoc_item_kind =
2685                         trait_items.iter().find(|ti| ti.id.hir_id() == parent).map(|ti| ti.kind);
2686                 }
2687                 match *m {
2688                     hir::TraitFn::Required(_) => None,
2689                     hir::TraitFn::Provided(body) => Some(body),
2690                 }
2691             }
2692
2693             Node::ImplItem(&hir::ImplItem { kind: hir::ImplItemKind::Fn(_, body), .. }) => {
2694                 if let hir::ItemKind::Impl(hir::Impl { ref self_ty, ref items, .. }) =
2695                     self.tcx.hir().expect_item(self.tcx.hir().get_parent_item(parent)).kind
2696                 {
2697                     impl_self = Some(self_ty);
2698                     assoc_item_kind =
2699                         items.iter().find(|ii| ii.id.hir_id() == parent).map(|ii| ii.kind);
2700                 }
2701                 Some(body)
2702             }
2703
2704             // Foreign functions, `fn(...) -> R` and `Trait(...) -> R` (both types and bounds).
2705             Node::ForeignItem(_) | Node::Ty(_) | Node::TraitRef(_) => None,
2706             // Everything else (only closures?) doesn't
2707             // actually enjoy elision in return types.
2708             _ => {
2709                 self.visit_ty(output);
2710                 return;
2711             }
2712         };
2713
2714         let has_self = match assoc_item_kind {
2715             Some(hir::AssocItemKind::Fn { has_self }) => has_self,
2716             _ => false,
2717         };
2718
2719         // In accordance with the rules for lifetime elision, we can determine
2720         // what region to use for elision in the output type in two ways.
2721         // First (determined here), if `self` is by-reference, then the
2722         // implied output region is the region of the self parameter.
2723         if has_self {
2724             struct SelfVisitor<'a> {
2725                 map: &'a NamedRegionMap,
2726                 impl_self: Option<&'a hir::TyKind<'a>>,
2727                 lifetime: Set1<Region>,
2728             }
2729
2730             impl SelfVisitor<'_> {
2731                 // Look for `self: &'a Self` - also desugared from `&'a self`,
2732                 // and if that matches, use it for elision and return early.
2733                 fn is_self_ty(&self, res: Res) -> bool {
2734                     if let Res::SelfTy { .. } = res {
2735                         return true;
2736                     }
2737
2738                     // Can't always rely on literal (or implied) `Self` due
2739                     // to the way elision rules were originally specified.
2740                     if let Some(&hir::TyKind::Path(hir::QPath::Resolved(None, ref path))) =
2741                         self.impl_self
2742                     {
2743                         match path.res {
2744                             // Permit the types that unambiguously always
2745                             // result in the same type constructor being used
2746                             // (it can't differ between `Self` and `self`).
2747                             Res::Def(DefKind::Struct | DefKind::Union | DefKind::Enum, _)
2748                             | Res::PrimTy(_) => return res == path.res,
2749                             _ => {}
2750                         }
2751                     }
2752
2753                     false
2754                 }
2755             }
2756
2757             impl<'a> Visitor<'a> for SelfVisitor<'a> {
2758                 fn visit_ty(&mut self, ty: &'a hir::Ty<'a>) {
2759                     if let hir::TyKind::Rptr(lifetime_ref, ref mt) = ty.kind {
2760                         if let hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) = mt.ty.kind
2761                         {
2762                             if self.is_self_ty(path.res) {
2763                                 if let Some(lifetime) = self.map.defs.get(&lifetime_ref.hir_id) {
2764                                     self.lifetime.insert(*lifetime);
2765                                 }
2766                             }
2767                         }
2768                     }
2769                     intravisit::walk_ty(self, ty)
2770                 }
2771             }
2772
2773             let mut visitor = SelfVisitor {
2774                 map: self.map,
2775                 impl_self: impl_self.map(|ty| &ty.kind),
2776                 lifetime: Set1::Empty,
2777             };
2778             visitor.visit_ty(&inputs[0]);
2779             if let Set1::One(lifetime) = visitor.lifetime {
2780                 let scope = Scope::Elision { elide: Elide::Exact(lifetime), s: self.scope };
2781                 self.with(scope, |_, this| this.visit_ty(output));
2782                 return;
2783             }
2784         }
2785
2786         // Second, if there was exactly one lifetime (either a substitution or a
2787         // reference) in the arguments, then any anonymous regions in the output
2788         // have that lifetime.
2789         let mut possible_implied_output_region = None;
2790         let mut lifetime_count = 0;
2791         let arg_lifetimes = inputs
2792             .iter()
2793             .enumerate()
2794             .skip(has_self as usize)
2795             .map(|(i, input)| {
2796                 let mut gather = GatherLifetimes {
2797                     map: self.map,
2798                     outer_index: ty::INNERMOST,
2799                     have_bound_regions: false,
2800                     lifetimes: Default::default(),
2801                 };
2802                 gather.visit_ty(input);
2803
2804                 lifetime_count += gather.lifetimes.len();
2805
2806                 if lifetime_count == 1 && gather.lifetimes.len() == 1 {
2807                     // there's a chance that the unique lifetime of this
2808                     // iteration will be the appropriate lifetime for output
2809                     // parameters, so lets store it.
2810                     possible_implied_output_region = gather.lifetimes.iter().cloned().next();
2811                 }
2812
2813                 ElisionFailureInfo {
2814                     parent: body,
2815                     index: i,
2816                     lifetime_count: gather.lifetimes.len(),
2817                     have_bound_regions: gather.have_bound_regions,
2818                     span: input.span,
2819                 }
2820             })
2821             .collect();
2822
2823         let elide = if lifetime_count == 1 {
2824             Elide::Exact(possible_implied_output_region.unwrap())
2825         } else {
2826             Elide::Error(arg_lifetimes)
2827         };
2828
2829         debug!(?elide);
2830
2831         let scope = Scope::Elision { elide, s: self.scope };
2832         self.with(scope, |_, this| this.visit_ty(output));
2833
2834         struct GatherLifetimes<'a> {
2835             map: &'a NamedRegionMap,
2836             outer_index: ty::DebruijnIndex,
2837             have_bound_regions: bool,
2838             lifetimes: FxHashSet<Region>,
2839         }
2840
2841         impl<'v, 'a> Visitor<'v> for GatherLifetimes<'a> {
2842             fn visit_ty(&mut self, ty: &hir::Ty<'_>) {
2843                 if let hir::TyKind::BareFn(_) = ty.kind {
2844                     self.outer_index.shift_in(1);
2845                 }
2846                 match ty.kind {
2847                     hir::TyKind::TraitObject(bounds, ref lifetime, _) => {
2848                         for bound in bounds {
2849                             self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
2850                         }
2851
2852                         // Stay on the safe side and don't include the object
2853                         // lifetime default (which may not end up being used).
2854                         if !lifetime.is_elided() {
2855                             self.visit_lifetime(lifetime);
2856                         }
2857                     }
2858                     _ => {
2859                         intravisit::walk_ty(self, ty);
2860                     }
2861                 }
2862                 if let hir::TyKind::BareFn(_) = ty.kind {
2863                     self.outer_index.shift_out(1);
2864                 }
2865             }
2866
2867             fn visit_generic_param(&mut self, param: &hir::GenericParam<'_>) {
2868                 if let hir::GenericParamKind::Lifetime { .. } = param.kind {
2869                     // FIXME(eddyb) Do we want this? It only makes a difference
2870                     // if this `for<'a>` lifetime parameter is never used.
2871                     self.have_bound_regions = true;
2872                 }
2873
2874                 intravisit::walk_generic_param(self, param);
2875             }
2876
2877             fn visit_poly_trait_ref(
2878                 &mut self,
2879                 trait_ref: &hir::PolyTraitRef<'_>,
2880                 modifier: hir::TraitBoundModifier,
2881             ) {
2882                 self.outer_index.shift_in(1);
2883                 intravisit::walk_poly_trait_ref(self, trait_ref, modifier);
2884                 self.outer_index.shift_out(1);
2885             }
2886
2887             fn visit_param_bound(&mut self, bound: &hir::GenericBound<'_>) {
2888                 if let hir::GenericBound::LangItemTrait { .. } = bound {
2889                     self.outer_index.shift_in(1);
2890                     intravisit::walk_param_bound(self, bound);
2891                     self.outer_index.shift_out(1);
2892                 } else {
2893                     intravisit::walk_param_bound(self, bound);
2894                 }
2895             }
2896
2897             fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
2898                 if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.hir_id) {
2899                     match lifetime {
2900                         Region::LateBound(debruijn, _, _)
2901                         | Region::LateBoundAnon(debruijn, _, _)
2902                             if debruijn < self.outer_index =>
2903                         {
2904                             self.have_bound_regions = true;
2905                         }
2906                         _ => {
2907                             // FIXME(jackh726): nested trait refs?
2908                             self.lifetimes.insert(lifetime.shifted_out_to_binder(self.outer_index));
2909                         }
2910                     }
2911                 }
2912             }
2913         }
2914
2915         struct GatherAnonLifetimes {
2916             anon_count: u32,
2917         }
2918         impl<'v> Visitor<'v> for GatherAnonLifetimes {
2919             #[instrument(skip(self), level = "trace")]
2920             fn visit_ty(&mut self, ty: &hir::Ty<'_>) {
2921                 // If we enter a `BareFn`, then we enter a *new* binding scope
2922                 if let hir::TyKind::BareFn(_) = ty.kind {
2923                     return;
2924                 }
2925                 intravisit::walk_ty(self, ty);
2926             }
2927
2928             fn visit_generic_args(
2929                 &mut self,
2930                 path_span: Span,
2931                 generic_args: &'v hir::GenericArgs<'v>,
2932             ) {
2933                 // parenthesized args enter a new elision scope
2934                 if generic_args.parenthesized {
2935                     return;
2936                 }
2937                 intravisit::walk_generic_args(self, path_span, generic_args)
2938             }
2939
2940             #[instrument(skip(self), level = "trace")]
2941             fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
2942                 if lifetime_ref.is_elided() {
2943                     self.anon_count += 1;
2944                 }
2945             }
2946         }
2947     }
2948
2949     fn resolve_elided_lifetimes(&mut self, lifetime_refs: &[&'tcx hir::Lifetime]) {
2950         debug!("resolve_elided_lifetimes(lifetime_refs={:?})", lifetime_refs);
2951
2952         if lifetime_refs.is_empty() {
2953             return;
2954         }
2955
2956         let mut late_depth = 0;
2957         let mut scope = self.scope;
2958         let mut lifetime_names = FxHashSet::default();
2959         let mut lifetime_spans = vec![];
2960         let error = loop {
2961             match *scope {
2962                 // Do not assign any resolution, it will be inferred.
2963                 Scope::Body { .. } => break Ok(()),
2964
2965                 Scope::Root => break Err(None),
2966
2967                 Scope::Binder { s, ref lifetimes, scope_type, .. } => {
2968                     // collect named lifetimes for suggestions
2969                     for name in lifetimes.keys() {
2970                         if let hir::ParamName::Plain(name) = name {
2971                             lifetime_names.insert(name.name);
2972                             lifetime_spans.push(name.span);
2973                         }
2974                     }
2975                     match scope_type {
2976                         BinderScopeType::Normal => late_depth += 1,
2977                         BinderScopeType::Concatenating => {}
2978                     }
2979                     scope = s;
2980                 }
2981
2982                 Scope::Elision {
2983                     elide: Elide::FreshLateAnon(named_late_bound_vars, ref counter),
2984                     ..
2985                 } => {
2986                     for lifetime_ref in lifetime_refs {
2987                         let lifetime =
2988                             Region::late_anon(named_late_bound_vars, counter).shifted(late_depth);
2989
2990                         self.insert_lifetime(lifetime_ref, lifetime);
2991                     }
2992                     break Ok(());
2993                 }
2994
2995                 Scope::Elision { elide: Elide::Exact(l), .. } => {
2996                     let lifetime = l.shifted(late_depth);
2997                     for lifetime_ref in lifetime_refs {
2998                         self.insert_lifetime(lifetime_ref, lifetime);
2999                     }
3000                     break Ok(());
3001                 }
3002
3003                 Scope::Elision { elide: Elide::Error(ref e), ref s, .. } => {
3004                     let mut scope = s;
3005                     loop {
3006                         match scope {
3007                             Scope::Binder { ref lifetimes, s, .. } => {
3008                                 // Collect named lifetimes for suggestions.
3009                                 for name in lifetimes.keys() {
3010                                     if let hir::ParamName::Plain(name) = name {
3011                                         lifetime_names.insert(name.name);
3012                                         lifetime_spans.push(name.span);
3013                                     }
3014                                 }
3015                                 scope = s;
3016                             }
3017                             Scope::ObjectLifetimeDefault { ref s, .. }
3018                             | Scope::Elision { ref s, .. }
3019                             | Scope::TraitRefBoundary { ref s, .. } => {
3020                                 scope = s;
3021                             }
3022                             _ => break,
3023                         }
3024                     }
3025                     break Err(Some(&e[..]));
3026                 }
3027
3028                 Scope::Elision { elide: Elide::Forbid, .. } => break Err(None),
3029
3030                 Scope::ObjectLifetimeDefault { s, .. }
3031                 | Scope::Supertrait { s, .. }
3032                 | Scope::TraitRefBoundary { s, .. } => {
3033                     scope = s;
3034                 }
3035             }
3036         };
3037
3038         let error = match error {
3039             Ok(()) => {
3040                 self.report_elided_lifetime_in_ty(lifetime_refs);
3041                 return;
3042             }
3043             Err(error) => error,
3044         };
3045
3046         // If we specifically need the `scope_for_path` map, then we're in the
3047         // diagnostic pass and we don't want to emit more errors.
3048         if self.map.scope_for_path.is_some() {
3049             self.tcx.sess.delay_span_bug(
3050                 rustc_span::DUMMY_SP,
3051                 "Encountered unexpected errors during diagnostics related part",
3052             );
3053             return;
3054         }
3055
3056         let mut spans: Vec<_> = lifetime_refs.iter().map(|lt| lt.span).collect();
3057         spans.sort();
3058         let mut spans_dedup = spans.clone();
3059         spans_dedup.dedup();
3060         let spans_with_counts: Vec<_> = spans_dedup
3061             .into_iter()
3062             .map(|sp| (sp, spans.iter().filter(|nsp| *nsp == &sp).count()))
3063             .collect();
3064
3065         let mut err = self.report_missing_lifetime_specifiers(spans.clone(), lifetime_refs.len());
3066
3067         if let Some(params) = error {
3068             // If there's no lifetime available, suggest `'static`.
3069             if self.report_elision_failure(&mut err, params) && lifetime_names.is_empty() {
3070                 lifetime_names.insert(kw::StaticLifetime);
3071             }
3072         }
3073
3074         self.add_missing_lifetime_specifiers_label(
3075             &mut err,
3076             spans_with_counts,
3077             &lifetime_names,
3078             lifetime_spans,
3079             error.unwrap_or(&[]),
3080         );
3081         err.emit();
3082     }
3083
3084     fn resolve_object_lifetime_default(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
3085         debug!("resolve_object_lifetime_default(lifetime_ref={:?})", lifetime_ref);
3086         let mut late_depth = 0;
3087         let mut scope = self.scope;
3088         let lifetime = loop {
3089             match *scope {
3090                 Scope::Binder { s, scope_type, .. } => {
3091                     match scope_type {
3092                         BinderScopeType::Normal => late_depth += 1,
3093                         BinderScopeType::Concatenating => {}
3094                     }
3095                     scope = s;
3096                 }
3097
3098                 Scope::Root | Scope::Elision { .. } => break Region::Static,
3099
3100                 Scope::Body { .. } | Scope::ObjectLifetimeDefault { lifetime: None, .. } => return,
3101
3102                 Scope::ObjectLifetimeDefault { lifetime: Some(l), .. } => break l,
3103
3104                 Scope::Supertrait { s, .. } | Scope::TraitRefBoundary { s, .. } => {
3105                     scope = s;
3106                 }
3107             }
3108         };
3109         self.insert_lifetime(lifetime_ref, lifetime.shifted(late_depth));
3110     }
3111
3112     fn check_lifetime_params(
3113         &mut self,
3114         old_scope: ScopeRef<'_>,
3115         params: &'tcx [hir::GenericParam<'tcx>],
3116     ) {
3117         let lifetimes: Vec<_> = params
3118             .iter()
3119             .filter_map(|param| match param.kind {
3120                 GenericParamKind::Lifetime { .. } => {
3121                     Some((param, param.name.normalize_to_macros_2_0()))
3122                 }
3123                 _ => None,
3124             })
3125             .collect();
3126         for (i, (lifetime_i, lifetime_i_name)) in lifetimes.iter().enumerate() {
3127             if let hir::ParamName::Plain(_) = lifetime_i_name {
3128                 let name = lifetime_i_name.ident().name;
3129                 if name == kw::UnderscoreLifetime || name == kw::StaticLifetime {
3130                     let mut err = struct_span_err!(
3131                         self.tcx.sess,
3132                         lifetime_i.span,
3133                         E0262,
3134                         "invalid lifetime parameter name: `{}`",
3135                         lifetime_i.name.ident(),
3136                     );
3137                     err.span_label(
3138                         lifetime_i.span,
3139                         format!("{} is a reserved lifetime name", name),
3140                     );
3141                     err.emit();
3142                 }
3143             }
3144
3145             // It is a hard error to shadow a lifetime within the same scope.
3146             for (lifetime_j, lifetime_j_name) in lifetimes.iter().skip(i + 1) {
3147                 if lifetime_i_name == lifetime_j_name {
3148                     struct_span_err!(
3149                         self.tcx.sess,
3150                         lifetime_j.span,
3151                         E0263,
3152                         "lifetime name `{}` declared twice in the same scope",
3153                         lifetime_j.name.ident()
3154                     )
3155                     .span_label(lifetime_j.span, "declared twice")
3156                     .span_label(lifetime_i.span, "previous declaration here")
3157                     .emit();
3158                 }
3159             }
3160
3161             // It is a soft error to shadow a lifetime within a parent scope.
3162             self.check_lifetime_param_for_shadowing(old_scope, &lifetime_i);
3163
3164             for bound in lifetime_i.bounds {
3165                 match bound {
3166                     hir::GenericBound::Outlives(ref lt) => match lt.name {
3167                         hir::LifetimeName::Underscore => {
3168                             self.tcx.sess.delay_span_bug(
3169                                 lt.span,
3170                                 "use of `'_` in illegal place, but not caught by lowering",
3171                             );
3172                         }
3173                         hir::LifetimeName::Static => {
3174                             self.insert_lifetime(lt, Region::Static);
3175                             self.tcx
3176                                 .sess
3177                                 .struct_span_warn(
3178                                     lifetime_i.span.to(lt.span),
3179                                     &format!(
3180                                         "unnecessary lifetime parameter `{}`",
3181                                         lifetime_i.name.ident(),
3182                                     ),
3183                                 )
3184                                 .help(&format!(
3185                                     "you can use the `'static` lifetime directly, in place of `{}`",
3186                                     lifetime_i.name.ident(),
3187                                 ))
3188                                 .emit();
3189                         }
3190                         hir::LifetimeName::Param(_) | hir::LifetimeName::Implicit(_) => {
3191                             self.resolve_lifetime_ref(lt);
3192                         }
3193                         hir::LifetimeName::ImplicitObjectLifetimeDefault => {
3194                             self.tcx.sess.delay_span_bug(
3195                                 lt.span,
3196                                 "lowering generated `ImplicitObjectLifetimeDefault` \
3197                                  outside of an object type",
3198                             );
3199                         }
3200                         hir::LifetimeName::Error => {
3201                             // No need to do anything, error already reported.
3202                         }
3203                     },
3204                     _ => bug!(),
3205                 }
3206             }
3207         }
3208     }
3209
3210     fn check_lifetime_param_for_shadowing(
3211         &self,
3212         mut old_scope: ScopeRef<'_>,
3213         param: &'tcx hir::GenericParam<'tcx>,
3214     ) {
3215         for label in &self.labels_in_fn {
3216             // FIXME (#24278): non-hygienic comparison
3217             if param.name.ident().name == label.name {
3218                 signal_shadowing_problem(
3219                     self.tcx,
3220                     label.name,
3221                     original_label(label.span),
3222                     shadower_lifetime(&param),
3223                 );
3224                 return;
3225             }
3226         }
3227
3228         loop {
3229             match *old_scope {
3230                 Scope::Body { s, .. }
3231                 | Scope::Elision { s, .. }
3232                 | Scope::ObjectLifetimeDefault { s, .. }
3233                 | Scope::Supertrait { s, .. }
3234                 | Scope::TraitRefBoundary { s, .. } => {
3235                     old_scope = s;
3236                 }
3237
3238                 Scope::Root => {
3239                     return;
3240                 }
3241
3242                 Scope::Binder { ref lifetimes, s, .. } => {
3243                     if let Some(&def) = lifetimes.get(&param.name.normalize_to_macros_2_0()) {
3244                         signal_shadowing_problem(
3245                             self.tcx,
3246                             param.name.ident().name,
3247                             original_lifetime(self.tcx.def_span(def.id().unwrap())),
3248                             shadower_lifetime(&param),
3249                         );
3250                         return;
3251                     }
3252
3253                     old_scope = s;
3254                 }
3255             }
3256         }
3257     }
3258
3259     /// Returns `true` if, in the current scope, replacing `'_` would be
3260     /// equivalent to a single-use lifetime.
3261     fn track_lifetime_uses(&self) -> bool {
3262         let mut scope = self.scope;
3263         loop {
3264             match *scope {
3265                 Scope::Root => break false,
3266
3267                 // Inside of items, it depends on the kind of item.
3268                 Scope::Binder { track_lifetime_uses, .. } => break track_lifetime_uses,
3269
3270                 // Inside a body, `'_` will use an inference variable,
3271                 // should be fine.
3272                 Scope::Body { .. } => break true,
3273
3274                 // A lifetime only used in a fn argument could as well
3275                 // be replaced with `'_`, as that would generate a
3276                 // fresh name, too.
3277                 Scope::Elision { elide: Elide::FreshLateAnon(..), .. } => break true,
3278
3279                 // In the return type or other such place, `'_` is not
3280                 // going to make a fresh name, so we cannot
3281                 // necessarily replace a single-use lifetime with
3282                 // `'_`.
3283                 Scope::Elision {
3284                     elide: Elide::Exact(_) | Elide::Error(_) | Elide::Forbid, ..
3285                 } => break false,
3286
3287                 Scope::ObjectLifetimeDefault { s, .. }
3288                 | Scope::Supertrait { s, .. }
3289                 | Scope::TraitRefBoundary { s, .. } => scope = s,
3290             }
3291         }
3292     }
3293
3294     #[tracing::instrument(level = "debug", skip(self))]
3295     fn insert_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime, def: Region) {
3296         debug!(
3297             node = ?self.tcx.hir().node_to_string(lifetime_ref.hir_id),
3298             span = ?self.tcx.sess.source_map().span_to_diagnostic_string(lifetime_ref.span)
3299         );
3300         self.map.defs.insert(lifetime_ref.hir_id, def);
3301
3302         match def {
3303             Region::LateBoundAnon(..) | Region::Static => {
3304                 // These are anonymous lifetimes or lifetimes that are not declared.
3305             }
3306
3307             Region::Free(_, def_id)
3308             | Region::LateBound(_, _, def_id)
3309             | Region::EarlyBound(_, def_id) => {
3310                 // A lifetime declared by the user.
3311                 let track_lifetime_uses = self.track_lifetime_uses();
3312                 debug!(?track_lifetime_uses);
3313                 if track_lifetime_uses && !self.lifetime_uses.contains_key(&def_id) {
3314                     debug!("first use of {:?}", def_id);
3315                     self.lifetime_uses.insert(def_id, LifetimeUseSet::One(lifetime_ref));
3316                 } else {
3317                     debug!("many uses of {:?}", def_id);
3318                     self.lifetime_uses.insert(def_id, LifetimeUseSet::Many);
3319                 }
3320             }
3321         }
3322     }
3323
3324     /// Sometimes we resolve a lifetime, but later find that it is an
3325     /// error (esp. around impl trait). In that case, we remove the
3326     /// entry into `map.defs` so as not to confuse later code.
3327     fn uninsert_lifetime_on_error(&mut self, lifetime_ref: &'tcx hir::Lifetime, bad_def: Region) {
3328         let old_value = self.map.defs.remove(&lifetime_ref.hir_id);
3329         assert_eq!(old_value, Some(bad_def));
3330     }
3331 }
3332
3333 /// Detects late-bound lifetimes and inserts them into
3334 /// `map.late_bound`.
3335 ///
3336 /// A region declared on a fn is **late-bound** if:
3337 /// - it is constrained by an argument type;
3338 /// - it does not appear in a where-clause.
3339 ///
3340 /// "Constrained" basically means that it appears in any type but
3341 /// not amongst the inputs to a projection. In other words, `<&'a
3342 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
3343 #[tracing::instrument(level = "debug", skip(map))]
3344 fn insert_late_bound_lifetimes(
3345     map: &mut NamedRegionMap,
3346     decl: &hir::FnDecl<'_>,
3347     generics: &hir::Generics<'_>,
3348 ) {
3349     let mut constrained_by_input = ConstrainedCollector::default();
3350     for arg_ty in decl.inputs {
3351         constrained_by_input.visit_ty(arg_ty);
3352     }
3353
3354     let mut appears_in_output = AllCollector::default();
3355     intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
3356
3357     debug!(?constrained_by_input.regions);
3358
3359     // Walk the lifetimes that appear in where clauses.
3360     //
3361     // Subtle point: because we disallow nested bindings, we can just
3362     // ignore binders here and scrape up all names we see.
3363     let mut appears_in_where_clause = AllCollector::default();
3364     appears_in_where_clause.visit_generics(generics);
3365
3366     for param in generics.params {
3367         if let hir::GenericParamKind::Lifetime { .. } = param.kind {
3368             if !param.bounds.is_empty() {
3369                 // `'a: 'b` means both `'a` and `'b` are referenced
3370                 appears_in_where_clause
3371                     .regions
3372                     .insert(hir::LifetimeName::Param(param.name.normalize_to_macros_2_0()));
3373             }
3374         }
3375     }
3376
3377     debug!(?appears_in_where_clause.regions);
3378
3379     // Late bound regions are those that:
3380     // - appear in the inputs
3381     // - do not appear in the where-clauses
3382     // - are not implicitly captured by `impl Trait`
3383     for param in generics.params {
3384         match param.kind {
3385             hir::GenericParamKind::Lifetime { .. } => { /* fall through */ }
3386
3387             // Neither types nor consts are late-bound.
3388             hir::GenericParamKind::Type { .. } | hir::GenericParamKind::Const { .. } => continue,
3389         }
3390
3391         let lt_name = hir::LifetimeName::Param(param.name.normalize_to_macros_2_0());
3392         // appears in the where clauses? early-bound.
3393         if appears_in_where_clause.regions.contains(&lt_name) {
3394             continue;
3395         }
3396
3397         // does not appear in the inputs, but appears in the return type? early-bound.
3398         if !constrained_by_input.regions.contains(&lt_name)
3399             && appears_in_output.regions.contains(&lt_name)
3400         {
3401             continue;
3402         }
3403
3404         debug!("lifetime {:?} with id {:?} is late-bound", param.name.ident(), param.hir_id);
3405
3406         let inserted = map.late_bound.insert(param.hir_id);
3407         assert!(inserted, "visited lifetime {:?} twice", param.hir_id);
3408     }
3409
3410     return;
3411
3412     #[derive(Default)]
3413     struct ConstrainedCollector {
3414         regions: FxHashSet<hir::LifetimeName>,
3415     }
3416
3417     impl<'v> Visitor<'v> for ConstrainedCollector {
3418         fn visit_ty(&mut self, ty: &'v hir::Ty<'v>) {
3419             match ty.kind {
3420                 hir::TyKind::Path(
3421                     hir::QPath::Resolved(Some(_), _) | hir::QPath::TypeRelative(..),
3422                 ) => {
3423                     // ignore lifetimes appearing in associated type
3424                     // projections, as they are not *constrained*
3425                     // (defined above)
3426                 }
3427
3428                 hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
3429                     // consider only the lifetimes on the final
3430                     // segment; I am not sure it's even currently
3431                     // valid to have them elsewhere, but even if it
3432                     // is, those would be potentially inputs to
3433                     // projections
3434                     if let Some(last_segment) = path.segments.last() {
3435                         self.visit_path_segment(path.span, last_segment);
3436                     }
3437                 }
3438
3439                 _ => {
3440                     intravisit::walk_ty(self, ty);
3441                 }
3442             }
3443         }
3444
3445         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
3446             self.regions.insert(lifetime_ref.name.normalize_to_macros_2_0());
3447         }
3448     }
3449
3450     #[derive(Default)]
3451     struct AllCollector {
3452         regions: FxHashSet<hir::LifetimeName>,
3453     }
3454
3455     impl<'v> Visitor<'v> for AllCollector {
3456         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
3457             self.regions.insert(lifetime_ref.name.normalize_to_macros_2_0());
3458         }
3459     }
3460 }