compiler/rustc_hir_analysis/src/collect/lifetimes.rs

   1 //! Resolution of early vs late bound lifetimes.
   2 //!
   3 //! Name resolution for lifetimes is performed on the AST and embedded into HIR.  From this
   4 //! information, typechecking needs to transform the lifetime parameters into bound lifetimes.
   5 //! Lifetimes can be early-bound or late-bound.  Construction of typechecking terms needs to visit
   6 //! the types in HIR to identify late-bound lifetimes and assign their Debruijn indices.  This file
   7 //! is also responsible for assigning their semantics to implicit lifetimes in trait objects.
   8
   9 use rustc_ast::walk_list;
  10 use rustc_data_structures::fx::{FxHashSet, FxIndexMap, FxIndexSet};
  11 use rustc_errors::struct_span_err;
  12 use rustc_hir as hir;
  13 use rustc_hir::def::{DefKind, Res};
  14 use rustc_hir::def_id::LocalDefId;
  15 use rustc_hir::intravisit::{self, Visitor};
  16 use rustc_hir::{GenericArg, GenericParam, GenericParamKind, HirIdMap, LifetimeName, Node};
  17 use rustc_middle::bug;
  18 use rustc_middle::hir::map::Map;
  19 use rustc_middle::hir::nested_filter;
  20 use rustc_middle::middle::resolve_lifetime::*;
  21 use rustc_middle::ty::{self, DefIdTree, TyCtxt, TypeSuperVisitable, TypeVisitor};
  22 use rustc_span::def_id::DefId;
  23 use rustc_span::symbol::{sym, Ident};
  24 use rustc_span::Span;
  25 use std::fmt;
  26
  27 trait RegionExt {
  28     fn early(hir_map: Map<'_>, param: &GenericParam<'_>) -> (LocalDefId, Region);
  29
  30     fn late(index: u32, hir_map: Map<'_>, param: &GenericParam<'_>) -> (LocalDefId, Region);
  31
  32     fn id(&self) -> Option<DefId>;
  33
  34     fn shifted(self, amount: u32) -> Region;
  35 }
  36
  37 impl RegionExt for Region {
  38     fn early(hir_map: Map<'_>, param: &GenericParam<'_>) -> (LocalDefId, Region) {
  39         let def_id = hir_map.local_def_id(param.hir_id);
  40         debug!("Region::early: def_id={:?}", def_id);
  41         (def_id, Region::EarlyBound(def_id.to_def_id()))
  42     }
  43
  44     fn late(idx: u32, hir_map: Map<'_>, param: &GenericParam<'_>) -> (LocalDefId, Region) {
  45         let depth = ty::INNERMOST;
  46         let def_id = hir_map.local_def_id(param.hir_id);
  47         debug!(
  48             "Region::late: idx={:?}, param={:?} depth={:?} def_id={:?}",
  49             idx, param, depth, def_id,
  50         );
  51         (def_id, Region::LateBound(depth, idx, def_id.to_def_id()))
  52     }
  53
  54     fn id(&self) -> Option<DefId> {
  55         match *self {
  56             Region::Static => None,
  57
  58             Region::EarlyBound(id) | Region::LateBound(_, _, id) | Region::Free(_, id) => Some(id),
  59         }
  60     }
  61
  62     fn shifted(self, amount: u32) -> Region {
  63         match self {
  64             Region::LateBound(debruijn, idx, id) => {
  65                 Region::LateBound(debruijn.shifted_in(amount), idx, id)
  66             }
  67             _ => self,
  68         }
  69     }
  70 }
  71
  72 /// Maps the id of each lifetime reference to the lifetime decl
  73 /// that it corresponds to.
  74 ///
  75 /// FIXME. This struct gets converted to a `ResolveLifetimes` for
  76 /// actual use. It has the same data, but indexed by `LocalDefId`.  This
  77 /// is silly.
  78 #[derive(Debug, Default)]
  79 struct NamedRegionMap {
  80     // maps from every use of a named (not anonymous) lifetime to a
  81     // `Region` describing how that region is bound
  82     defs: HirIdMap<Region>,
  83
  84     // Maps relevant hir items to the bound vars on them. These include:
  85     // - function defs
  86     // - function pointers
  87     // - closures
  88     // - trait refs
  89     // - bound types (like `T` in `for<'a> T<'a>: Foo`)
  90     late_bound_vars: HirIdMap<Vec<ty::BoundVariableKind>>,
  91 }
  92
  93 struct LifetimeContext<'a, 'tcx> {
  94     tcx: TyCtxt<'tcx>,
  95     map: &'a mut NamedRegionMap,
  96     scope: ScopeRef<'a>,
  97 }
  98
  99 #[derive(Debug)]
 100 enum Scope<'a> {
 101     /// Declares lifetimes, and each can be early-bound or late-bound.
 102     /// The `DebruijnIndex` of late-bound lifetimes starts at `1` and
 103     /// it should be shifted by the number of `Binder`s in between the
 104     /// declaration `Binder` and the location it's referenced from.
 105     Binder {
 106         /// We use an IndexMap here because we want these lifetimes in order
 107         /// for diagnostics.
 108         lifetimes: FxIndexMap<LocalDefId, Region>,
 109
 110         scope_type: BinderScopeType,
 111
 112         /// The late bound vars for a given item are stored by `HirId` to be
 113         /// queried later. However, if we enter an elision scope, we have to
 114         /// later append the elided bound vars to the list and need to know what
 115         /// to append to.
 116         hir_id: hir::HirId,
 117
 118         s: ScopeRef<'a>,
 119
 120         /// If this binder comes from a where clause, specify how it was created.
 121         /// This is used to diagnose inaccessible lifetimes in APIT:
 122         /// ```ignore (illustrative)
 123         /// fn foo(x: impl for<'a> Trait<'a, Assoc = impl Copy + 'a>) {}
 124         /// ```
 125         where_bound_origin: Option<hir::PredicateOrigin>,
 126     },
 127
 128     /// Lifetimes introduced by a fn are scoped to the call-site for that fn,
 129     /// if this is a fn body, otherwise the original definitions are used.
 130     /// Unspecified lifetimes are inferred, unless an elision scope is nested,
 131     /// e.g., `(&T, fn(&T) -> &T);` becomes `(&'_ T, for<'a> fn(&'a T) -> &'a T)`.
 132     Body {
 133         id: hir::BodyId,
 134         s: ScopeRef<'a>,
 135     },
 136
 137     /// A scope which either determines unspecified lifetimes or errors
 138     /// on them (e.g., due to ambiguity).
 139     Elision {
 140         s: ScopeRef<'a>,
 141     },
 142
 143     /// Use a specific lifetime (if `Some`) or leave it unset (to be
 144     /// inferred in a function body or potentially error outside one),
 145     /// for the default choice of lifetime in a trait object type.
 146     ObjectLifetimeDefault {
 147         lifetime: Option<Region>,
 148         s: ScopeRef<'a>,
 149     },
 150
 151     /// When we have nested trait refs, we concatenate late bound vars for inner
 152     /// trait refs from outer ones. But we also need to include any HRTB
 153     /// lifetimes encountered when identifying the trait that an associated type
 154     /// is declared on.
 155     Supertrait {
 156         lifetimes: Vec<ty::BoundVariableKind>,
 157         s: ScopeRef<'a>,
 158     },
 159
 160     TraitRefBoundary {
 161         s: ScopeRef<'a>,
 162     },
 163
 164     Root {
 165         opt_parent_item: Option<LocalDefId>,
 166     },
 167 }
 168
 169 #[derive(Copy, Clone, Debug)]
 170 enum BinderScopeType {
 171     /// Any non-concatenating binder scopes.
 172     Normal,
 173     /// Within a syntactic trait ref, there may be multiple poly trait refs that
 174     /// are nested (under the `associated_type_bounds` feature). The binders of
 175     /// the inner poly trait refs are extended from the outer poly trait refs
 176     /// and don't increase the late bound depth. If you had
 177     /// `T: for<'a>  Foo<Bar: for<'b> Baz<'a, 'b>>`, then the `for<'b>` scope
 178     /// would be `Concatenating`. This also used in trait refs in where clauses
 179     /// where we have two binders `for<> T: for<> Foo` (I've intentionally left
 180     /// out any lifetimes because they aren't needed to show the two scopes).
 181     /// The inner `for<>` has a scope of `Concatenating`.
 182     Concatenating,
 183 }
 184
 185 // A helper struct for debugging scopes without printing parent scopes
 186 struct TruncatedScopeDebug<'a>(&'a Scope<'a>);
 187
 188 impl<'a> fmt::Debug for TruncatedScopeDebug<'a> {
 189     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 190         match self.0 {
 191             Scope::Binder { lifetimes, scope_type, hir_id, where_bound_origin, s: _ } => f
 192                 .debug_struct("Binder")
 193                 .field("lifetimes", lifetimes)
 194                 .field("scope_type", scope_type)
 195                 .field("hir_id", hir_id)
 196                 .field("where_bound_origin", where_bound_origin)
 197                 .field("s", &"..")
 198                 .finish(),
 199             Scope::Body { id, s: _ } => {
 200                 f.debug_struct("Body").field("id", id).field("s", &"..").finish()
 201             }
 202             Scope::Elision { s: _ } => f.debug_struct("Elision").field("s", &"..").finish(),
 203             Scope::ObjectLifetimeDefault { lifetime, s: _ } => f
 204                 .debug_struct("ObjectLifetimeDefault")
 205                 .field("lifetime", lifetime)
 206                 .field("s", &"..")
 207                 .finish(),
 208             Scope::Supertrait { lifetimes, s: _ } => f
 209                 .debug_struct("Supertrait")
 210                 .field("lifetimes", lifetimes)
 211                 .field("s", &"..")
 212                 .finish(),
 213             Scope::TraitRefBoundary { s: _ } => f.debug_struct("TraitRefBoundary").finish(),
 214             Scope::Root { opt_parent_item } => {
 215                 f.debug_struct("Root").field("opt_parent_item", &opt_parent_item).finish()
 216             }
 217         }
 218     }
 219 }
 220
 221 type ScopeRef<'a> = &'a Scope<'a>;
 222
 223 pub(crate) fn provide(providers: &mut ty::query::Providers) {
 224     *providers = ty::query::Providers {
 225         resolve_lifetimes,
 226
 227         named_region_map: |tcx, id| tcx.resolve_lifetimes(id).defs.get(&id),
 228         is_late_bound_map,
 229         object_lifetime_default,
 230         late_bound_vars_map: |tcx, id| tcx.resolve_lifetimes(id).late_bound_vars.get(&id),
 231
 232         ..*providers
 233     };
 234 }
 235
 236 /// Computes the `ResolveLifetimes` map that contains data for an entire `Item`.
 237 /// You should not read the result of this query directly, but rather use
 238 /// `named_region_map`, `is_late_bound_map`, etc.
 239 #[instrument(level = "debug", skip(tcx))]
 240 fn resolve_lifetimes(tcx: TyCtxt<'_>, local_def_id: hir::OwnerId) -> ResolveLifetimes {
 241     let mut named_region_map =
 242         NamedRegionMap { defs: Default::default(), late_bound_vars: Default::default() };
 243     let mut visitor = LifetimeContext {
 244         tcx,
 245         map: &mut named_region_map,
 246         scope: &Scope::Root { opt_parent_item: None },
 247     };
 248     match tcx.hir().owner(local_def_id) {
 249         hir::OwnerNode::Item(item) => visitor.visit_item(item),
 250         hir::OwnerNode::ForeignItem(item) => visitor.visit_foreign_item(item),
 251         hir::OwnerNode::TraitItem(item) => {
 252             let scope =
 253                 Scope::Root { opt_parent_item: Some(tcx.local_parent(item.owner_id.def_id)) };
 254             visitor.scope = &scope;
 255             visitor.visit_trait_item(item)
 256         }
 257         hir::OwnerNode::ImplItem(item) => {
 258             let scope =
 259                 Scope::Root { opt_parent_item: Some(tcx.local_parent(item.owner_id.def_id)) };
 260             visitor.scope = &scope;
 261             visitor.visit_impl_item(item)
 262         }
 263         hir::OwnerNode::Crate(_) => {}
 264     }
 265
 266     let mut rl = ResolveLifetimes::default();
 267
 268     for (hir_id, v) in named_region_map.defs {
 269         let map = rl.defs.entry(hir_id.owner).or_default();
 270         map.insert(hir_id.local_id, v);
 271     }
 272     for (hir_id, v) in named_region_map.late_bound_vars {
 273         let map = rl.late_bound_vars.entry(hir_id.owner).or_default();
 274         map.insert(hir_id.local_id, v);
 275     }
 276
 277     debug!(?rl.defs);
 278     debug!(?rl.late_bound_vars);
 279     rl
 280 }
 281
 282 fn late_region_as_bound_region<'tcx>(tcx: TyCtxt<'tcx>, region: &Region) -> ty::BoundVariableKind {
 283     match region {
 284         Region::LateBound(_, _, def_id) => {
 285             let name = tcx.hir().name(tcx.hir().local_def_id_to_hir_id(def_id.expect_local()));
 286             ty::BoundVariableKind::Region(ty::BrNamed(*def_id, name))
 287         }
 288         _ => bug!("{:?} is not a late region", region),
 289     }
 290 }
 291
 292 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 293     /// Returns the binders in scope and the type of `Binder` that should be created for a poly trait ref.
 294     fn poly_trait_ref_binder_info(&mut self) -> (Vec<ty::BoundVariableKind>, BinderScopeType) {
 295         let mut scope = self.scope;
 296         let mut supertrait_lifetimes = vec![];
 297         loop {
 298             match scope {
 299                 Scope::Body { .. } | Scope::Root { .. } => {
 300                     break (vec![], BinderScopeType::Normal);
 301                 }
 302
 303                 Scope::Elision { s, .. } | Scope::ObjectLifetimeDefault { s, .. } => {
 304                     scope = s;
 305                 }
 306
 307                 Scope::Supertrait { s, lifetimes } => {
 308                     supertrait_lifetimes = lifetimes.clone();
 309                     scope = s;
 310                 }
 311
 312                 Scope::TraitRefBoundary { .. } => {
 313                     // We should only see super trait lifetimes if there is a `Binder` above
 314                     assert!(supertrait_lifetimes.is_empty());
 315                     break (vec![], BinderScopeType::Normal);
 316                 }
 317
 318                 Scope::Binder { hir_id, .. } => {
 319                     // Nested poly trait refs have the binders concatenated
 320                     let mut full_binders =
 321                         self.map.late_bound_vars.entry(*hir_id).or_default().clone();
 322                     full_binders.extend(supertrait_lifetimes.into_iter());
 323                     break (full_binders, BinderScopeType::Concatenating);
 324                 }
 325             }
 326         }
 327     }
 328 }
 329 impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
 330     type NestedFilter = nested_filter::OnlyBodies;
 331
 332     fn nested_visit_map(&mut self) -> Self::Map {
 333         self.tcx.hir()
 334     }
 335
 336     fn visit_nested_body(&mut self, body: hir::BodyId) {
 337         let body = self.tcx.hir().body(body);
 338         self.with(Scope::Body { id: body.id(), s: self.scope }, |this| {
 339             this.visit_body(body);
 340         });
 341     }
 342
 343     fn visit_expr(&mut self, e: &'tcx hir::Expr<'tcx>) {
 344         if let hir::ExprKind::Closure(hir::Closure {
 345             binder, bound_generic_params, fn_decl, ..
 346         }) = e.kind
 347         {
 348             if let &hir::ClosureBinder::For { span: for_sp, .. } = binder {
 349                 fn span_of_infer(ty: &hir::Ty<'_>) -> Option<Span> {
 350                     struct V(Option<Span>);
 351
 352                     impl<'v> Visitor<'v> for V {
 353                         fn visit_ty(&mut self, t: &'v hir::Ty<'v>) {
 354                             match t.kind {
 355                                 _ if self.0.is_some() => (),
 356                                 hir::TyKind::Infer => {
 357                                     self.0 = Some(t.span);
 358                                 }
 359                                 _ => intravisit::walk_ty(self, t),
 360                             }
 361                         }
 362                     }
 363
 364                     let mut v = V(None);
 365                     v.visit_ty(ty);
 366                     v.0
 367                 }
 368
 369                 let infer_in_rt_sp = match fn_decl.output {
 370                     hir::FnRetTy::DefaultReturn(sp) => Some(sp),
 371                     hir::FnRetTy::Return(ty) => span_of_infer(ty),
 372                 };
 373
 374                 let infer_spans = fn_decl
 375                     .inputs
 376                     .into_iter()
 377                     .filter_map(span_of_infer)
 378                     .chain(infer_in_rt_sp)
 379                     .collect::<Vec<_>>();
 380
 381                 if !infer_spans.is_empty() {
 382                     self.tcx.sess
 383                         .struct_span_err(
 384                             infer_spans,
 385                             "implicit types in closure signatures are forbidden when `for<...>` is present",
 386                         )
 387                         .span_label(for_sp, "`for<...>` is here")
 388                         .emit();
 389                 }
 390             }
 391
 392             let (lifetimes, binders): (FxIndexMap<LocalDefId, Region>, Vec<_>) =
 393                 bound_generic_params
 394                     .iter()
 395                     .filter(|param| matches!(param.kind, GenericParamKind::Lifetime { .. }))
 396                     .enumerate()
 397                     .map(|(late_bound_idx, param)| {
 398                         let pair = Region::late(late_bound_idx as u32, self.tcx.hir(), param);
 399                         let r = late_region_as_bound_region(self.tcx, &pair.1);
 400                         (pair, r)
 401                     })
 402                     .unzip();
 403
 404             self.record_late_bound_vars(e.hir_id, binders);
 405             let scope = Scope::Binder {
 406                 hir_id: e.hir_id,
 407                 lifetimes,
 408                 s: self.scope,
 409                 scope_type: BinderScopeType::Normal,
 410                 where_bound_origin: None,
 411             };
 412
 413             self.with(scope, |this| {
 414                 // a closure has no bounds, so everything
 415                 // contained within is scoped within its binder.
 416                 intravisit::walk_expr(this, e)
 417             });
 418         } else {
 419             intravisit::walk_expr(self, e)
 420         }
 421     }
 422
 423     #[instrument(level = "debug", skip(self))]
 424     fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) {
 425         match &item.kind {
 426             hir::ItemKind::Impl(hir::Impl { of_trait, .. }) => {
 427                 if let Some(of_trait) = of_trait {
 428                     self.record_late_bound_vars(of_trait.hir_ref_id, Vec::default());
 429                 }
 430             }
 431             _ => {}
 432         }
 433         match item.kind {
 434             hir::ItemKind::Fn(_, ref generics, _) => {
 435                 self.visit_early_late(item.hir_id(), generics, |this| {
 436                     intravisit::walk_item(this, item);
 437                 });
 438             }
 439
 440             hir::ItemKind::ExternCrate(_)
 441             | hir::ItemKind::Use(..)
 442             | hir::ItemKind::Macro(..)
 443             | hir::ItemKind::Mod(..)
 444             | hir::ItemKind::ForeignMod { .. }
 445             | hir::ItemKind::GlobalAsm(..) => {
 446                 // These sorts of items have no lifetime parameters at all.
 447                 intravisit::walk_item(self, item);
 448             }
 449             hir::ItemKind::Static(..) | hir::ItemKind::Const(..) => {
 450                 // No lifetime parameters, but implied 'static.
 451                 self.with(Scope::Elision { s: self.scope }, |this| {
 452                     intravisit::walk_item(this, item)
 453                 });
 454             }
 455             hir::ItemKind::OpaqueTy(hir::OpaqueTy {
 456                 origin: hir::OpaqueTyOrigin::TyAlias, ..
 457             }) => {
 458                 // Opaque types are visited when we visit the
 459                 // `TyKind::OpaqueDef`, so that they have the lifetimes from
 460                 // their parent opaque_ty in scope.
 461                 //
 462                 // The core idea here is that since OpaqueTys are generated with the impl Trait as
 463                 // their owner, we can keep going until we find the Item that owns that. We then
 464                 // conservatively add all resolved lifetimes. Otherwise we run into problems in
 465                 // cases like `type Foo<'a> = impl Bar<As = impl Baz + 'a>`.
 466                 let parent_item = self.tcx.hir().get_parent_item(item.hir_id());
 467                 let resolved_lifetimes: &ResolveLifetimes = self.tcx.resolve_lifetimes(parent_item);
 468                 // We need to add *all* deps, since opaque tys may want them from *us*
 469                 for (&owner, defs) in resolved_lifetimes.defs.iter() {
 470                     defs.iter().for_each(|(&local_id, region)| {
 471                         self.map.defs.insert(hir::HirId { owner, local_id }, *region);
 472                     });
 473                 }
 474                 for (&owner, late_bound_vars) in resolved_lifetimes.late_bound_vars.iter() {
 475                     late_bound_vars.iter().for_each(|(&local_id, late_bound_vars)| {
 476                         self.record_late_bound_vars(
 477                             hir::HirId { owner, local_id },
 478                             late_bound_vars.clone(),
 479                         );
 480                     });
 481                 }
 482             }
 483             hir::ItemKind::OpaqueTy(hir::OpaqueTy {
 484                 origin: hir::OpaqueTyOrigin::FnReturn(_) | hir::OpaqueTyOrigin::AsyncFn(_),
 485                 generics,
 486                 ..
 487             }) => {
 488                 // We want to start our early-bound indices at the end of the parent scope,
 489                 // not including any parent `impl Trait`s.
 490                 let mut lifetimes = FxIndexMap::default();
 491                 debug!(?generics.params);
 492                 for param in generics.params {
 493                     match param.kind {
 494                         GenericParamKind::Lifetime { .. } => {
 495                             let (def_id, reg) = Region::early(self.tcx.hir(), &param);
 496                             lifetimes.insert(def_id, reg);
 497                         }
 498                         GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => {}
 499                     }
 500                 }
 501
 502                 let scope = Scope::Binder {
 503                     hir_id: item.hir_id(),
 504                     lifetimes,
 505                     s: self.scope,
 506                     scope_type: BinderScopeType::Normal,
 507                     where_bound_origin: None,
 508                 };
 509                 self.with(scope, |this| {
 510                     let scope = Scope::TraitRefBoundary { s: this.scope };
 511                     this.with(scope, |this| intravisit::walk_item(this, item))
 512                 });
 513             }
 514             hir::ItemKind::TyAlias(_, ref generics)
 515             | hir::ItemKind::Enum(_, ref generics)
 516             | hir::ItemKind::Struct(_, ref generics)
 517             | hir::ItemKind::Union(_, ref generics)
 518             | hir::ItemKind::Trait(_, _, ref generics, ..)
 519             | hir::ItemKind::TraitAlias(ref generics, ..)
 520             | hir::ItemKind::Impl(hir::Impl { ref generics, .. }) => {
 521                 // These kinds of items have only early-bound lifetime parameters.
 522                 let lifetimes = generics
 523                     .params
 524                     .iter()
 525                     .filter_map(|param| match param.kind {
 526                         GenericParamKind::Lifetime { .. } => {
 527                             Some(Region::early(self.tcx.hir(), param))
 528                         }
 529                         GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => None,
 530                     })
 531                     .collect();
 532                 self.record_late_bound_vars(item.hir_id(), vec![]);
 533                 let scope = Scope::Binder {
 534                     hir_id: item.hir_id(),
 535                     lifetimes,
 536                     scope_type: BinderScopeType::Normal,
 537                     s: self.scope,
 538                     where_bound_origin: None,
 539                 };
 540                 self.with(scope, |this| {
 541                     let scope = Scope::TraitRefBoundary { s: this.scope };
 542                     this.with(scope, |this| {
 543                         intravisit::walk_item(this, item);
 544                     });
 545                 });
 546             }
 547         }
 548     }
 549
 550     fn visit_foreign_item(&mut self, item: &'tcx hir::ForeignItem<'tcx>) {
 551         match item.kind {
 552             hir::ForeignItemKind::Fn(_, _, ref generics) => {
 553                 self.visit_early_late(item.hir_id(), generics, |this| {
 554                     intravisit::walk_foreign_item(this, item);
 555                 })
 556             }
 557             hir::ForeignItemKind::Static(..) => {
 558                 intravisit::walk_foreign_item(self, item);
 559             }
 560             hir::ForeignItemKind::Type => {
 561                 intravisit::walk_foreign_item(self, item);
 562             }
 563         }
 564     }
 565
 566     #[instrument(level = "debug", skip(self))]
 567     fn visit_ty(&mut self, ty: &'tcx hir::Ty<'tcx>) {
 568         match ty.kind {
 569             hir::TyKind::BareFn(ref c) => {
 570                 let (lifetimes, binders): (FxIndexMap<LocalDefId, Region>, Vec<_>) = c
 571                     .generic_params
 572                     .iter()
 573                     .filter(|param| matches!(param.kind, GenericParamKind::Lifetime { .. }))
 574                     .enumerate()
 575                     .map(|(late_bound_idx, param)| {
 576                         let pair = Region::late(late_bound_idx as u32, self.tcx.hir(), param);
 577                         let r = late_region_as_bound_region(self.tcx, &pair.1);
 578                         (pair, r)
 579                     })
 580                     .unzip();
 581                 self.record_late_bound_vars(ty.hir_id, binders);
 582                 let scope = Scope::Binder {
 583                     hir_id: ty.hir_id,
 584                     lifetimes,
 585                     s: self.scope,
 586                     scope_type: BinderScopeType::Normal,
 587                     where_bound_origin: None,
 588                 };
 589                 self.with(scope, |this| {
 590                     // a bare fn has no bounds, so everything
 591                     // contained within is scoped within its binder.
 592                     intravisit::walk_ty(this, ty);
 593                 });
 594             }
 595             hir::TyKind::TraitObject(bounds, ref lifetime, _) => {
 596                 debug!(?bounds, ?lifetime, "TraitObject");
 597                 let scope = Scope::TraitRefBoundary { s: self.scope };
 598                 self.with(scope, |this| {
 599                     for bound in bounds {
 600                         this.visit_poly_trait_ref(bound);
 601                     }
 602                 });
 603                 match lifetime.name {
 604                     LifetimeName::ImplicitObjectLifetimeDefault => {
 605                         // If the user does not write *anything*, we
 606                         // use the object lifetime defaulting
 607                         // rules. So e.g., `Box<dyn Debug>` becomes
 608                         // `Box<dyn Debug + 'static>`.
 609                         self.resolve_object_lifetime_default(lifetime)
 610                     }
 611                     LifetimeName::Infer => {
 612                         // If the user writes `'_`, we use the *ordinary* elision
 613                         // rules. So the `'_` in e.g., `Box<dyn Debug + '_>` will be
 614                         // resolved the same as the `'_` in `&'_ Foo`.
 615                         //
 616                         // cc #48468
 617                     }
 618                     LifetimeName::Param(..) | LifetimeName::Static => {
 619                         // If the user wrote an explicit name, use that.
 620                         self.visit_lifetime(lifetime);
 621                     }
 622                     LifetimeName::Error => {}
 623                 }
 624             }
 625             hir::TyKind::Rptr(ref lifetime_ref, ref mt) => {
 626                 self.visit_lifetime(lifetime_ref);
 627                 let scope = Scope::ObjectLifetimeDefault {
 628                     lifetime: self.map.defs.get(&lifetime_ref.hir_id).cloned(),
 629                     s: self.scope,
 630                 };
 631                 self.with(scope, |this| this.visit_ty(&mt.ty));
 632             }
 633             hir::TyKind::OpaqueDef(item_id, lifetimes, _in_trait) => {
 634                 // Resolve the lifetimes in the bounds to the lifetime defs in the generics.
 635                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 636                 // `type MyAnonTy<'b> = impl MyTrait<'b>;`
 637                 //                 ^                  ^ this gets resolved in the scope of
 638                 //                                      the opaque_ty generics
 639                 let opaque_ty = self.tcx.hir().item(item_id);
 640                 match opaque_ty.kind {
 641                     hir::ItemKind::OpaqueTy(hir::OpaqueTy {
 642                         origin: hir::OpaqueTyOrigin::TyAlias,
 643                         ..
 644                     }) => {
 645                         intravisit::walk_ty(self, ty);
 646
 647                         // Elided lifetimes are not allowed in non-return
 648                         // position impl Trait
 649                         let scope = Scope::TraitRefBoundary { s: self.scope };
 650                         self.with(scope, |this| {
 651                             let scope = Scope::Elision { s: this.scope };
 652                             this.with(scope, |this| {
 653                                 intravisit::walk_item(this, opaque_ty);
 654                             })
 655                         });
 656
 657                         return;
 658                     }
 659                     hir::ItemKind::OpaqueTy(hir::OpaqueTy {
 660                         origin: hir::OpaqueTyOrigin::FnReturn(..) | hir::OpaqueTyOrigin::AsyncFn(..),
 661                         ..
 662                     }) => {}
 663                     ref i => bug!("`impl Trait` pointed to non-opaque type?? {:#?}", i),
 664                 };
 665
 666                 // Resolve the lifetimes that are applied to the opaque type.
 667                 // These are resolved in the current scope.
 668                 // `fn foo<'a>() -> impl MyTrait<'a> { ... }` desugars to
 669                 // `fn foo<'a>() -> MyAnonTy<'a> { ... }`
 670                 //          ^                 ^this gets resolved in the current scope
 671                 for lifetime in lifetimes {
 672                     let hir::GenericArg::Lifetime(lifetime) = lifetime else {
 673                         continue
 674                     };
 675                     self.visit_lifetime(lifetime);
 676
 677                     // Check for predicates like `impl for<'a> Trait<impl OtherTrait<'a>>`
 678                     // and ban them. Type variables instantiated inside binders aren't
 679                     // well-supported at the moment, so this doesn't work.
 680                     // In the future, this should be fixed and this error should be removed.
 681                     let def = self.map.defs.get(&lifetime.hir_id).cloned();
 682                     let Some(Region::LateBound(_, _, def_id)) = def else {
 683                         continue
 684                     };
 685                     let Some(def_id) = def_id.as_local() else {
 686                         continue
 687                     };
 688                     let hir_id = self.tcx.hir().local_def_id_to_hir_id(def_id);
 689                     // Ensure that the parent of the def is an item, not HRTB
 690                     let parent_id = self.tcx.hir().get_parent_node(hir_id);
 691                     if !parent_id.is_owner() {
 692                         struct_span_err!(
 693                             self.tcx.sess,
 694                             lifetime.span,
 695                             E0657,
 696                             "`impl Trait` can only capture lifetimes bound at the fn or impl level"
 697                         )
 698                         .emit();
 699                         self.uninsert_lifetime_on_error(lifetime, def.unwrap());
 700                     }
 701                     if let hir::Node::Item(hir::Item {
 702                         kind: hir::ItemKind::OpaqueTy { .. }, ..
 703                     }) = self.tcx.hir().get(parent_id)
 704                     {
 705                         let mut err = self.tcx.sess.struct_span_err(
 706                             lifetime.span,
 707                             "higher kinded lifetime bounds on nested opaque types are not supported yet",
 708                         );
 709                         err.span_note(self.tcx.def_span(def_id), "lifetime declared here");
 710                         err.emit();
 711                         self.uninsert_lifetime_on_error(lifetime, def.unwrap());
 712                     }
 713                 }
 714             }
 715             _ => intravisit::walk_ty(self, ty),
 716         }
 717     }
 718
 719     #[instrument(level = "debug", skip(self))]
 720     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem<'tcx>) {
 721         use self::hir::TraitItemKind::*;
 722         match trait_item.kind {
 723             Fn(_, _) => {
 724                 self.visit_early_late(trait_item.hir_id(), &trait_item.generics, |this| {
 725                     intravisit::walk_trait_item(this, trait_item)
 726                 });
 727             }
 728             Type(bounds, ref ty) => {
 729                 let generics = &trait_item.generics;
 730                 let lifetimes = generics
 731                     .params
 732                     .iter()
 733                     .filter_map(|param| match param.kind {
 734                         GenericParamKind::Lifetime { .. } => {
 735                             Some(Region::early(self.tcx.hir(), param))
 736                         }
 737                         GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => None,
 738                     })
 739                     .collect();
 740                 self.record_late_bound_vars(trait_item.hir_id(), vec![]);
 741                 let scope = Scope::Binder {
 742                     hir_id: trait_item.hir_id(),
 743                     lifetimes,
 744                     s: self.scope,
 745                     scope_type: BinderScopeType::Normal,
 746                     where_bound_origin: None,
 747                 };
 748                 self.with(scope, |this| {
 749                     let scope = Scope::TraitRefBoundary { s: this.scope };
 750                     this.with(scope, |this| {
 751                         this.visit_generics(generics);
 752                         for bound in bounds {
 753                             this.visit_param_bound(bound);
 754                         }
 755                         if let Some(ty) = ty {
 756                             this.visit_ty(ty);
 757                         }
 758                     })
 759                 });
 760             }
 761             Const(_, _) => {
 762                 // Only methods and types support generics.
 763                 assert!(trait_item.generics.params.is_empty());
 764                 intravisit::walk_trait_item(self, trait_item);
 765             }
 766         }
 767     }
 768
 769     #[instrument(level = "debug", skip(self))]
 770     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem<'tcx>) {
 771         use self::hir::ImplItemKind::*;
 772         match impl_item.kind {
 773             Fn(..) => self.visit_early_late(impl_item.hir_id(), &impl_item.generics, |this| {
 774                 intravisit::walk_impl_item(this, impl_item)
 775             }),
 776             Type(ref ty) => {
 777                 let generics = &impl_item.generics;
 778                 let lifetimes: FxIndexMap<LocalDefId, Region> = generics
 779                     .params
 780                     .iter()
 781                     .filter_map(|param| match param.kind {
 782                         GenericParamKind::Lifetime { .. } => {
 783                             Some(Region::early(self.tcx.hir(), param))
 784                         }
 785                         GenericParamKind::Const { .. } | GenericParamKind::Type { .. } => None,
 786                     })
 787                     .collect();
 788                 self.record_late_bound_vars(impl_item.hir_id(), vec![]);
 789                 let scope = Scope::Binder {
 790                     hir_id: impl_item.hir_id(),
 791                     lifetimes,
 792                     s: self.scope,
 793                     scope_type: BinderScopeType::Normal,
 794                     where_bound_origin: None,
 795                 };
 796                 self.with(scope, |this| {
 797                     let scope = Scope::TraitRefBoundary { s: this.scope };
 798                     this.with(scope, |this| {
 799                         this.visit_generics(generics);
 800                         this.visit_ty(ty);
 801                     })
 802                 });
 803             }
 804             Const(_, _) => {
 805                 // Only methods and types support generics.
 806                 assert!(impl_item.generics.params.is_empty());
 807                 intravisit::walk_impl_item(self, impl_item);
 808             }
 809         }
 810     }
 811
 812     #[instrument(level = "debug", skip(self))]
 813     fn visit_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
 814         match lifetime_ref.name {
 815             hir::LifetimeName::Static => self.insert_lifetime(lifetime_ref, Region::Static),
 816             hir::LifetimeName::Param(param_def_id, _) => {
 817                 self.resolve_lifetime_ref(param_def_id, lifetime_ref)
 818             }
 819             // If we've already reported an error, just ignore `lifetime_ref`.
 820             hir::LifetimeName::Error => {}
 821             // Those will be resolved by typechecking.
 822             hir::LifetimeName::ImplicitObjectLifetimeDefault | hir::LifetimeName::Infer => {}
 823         }
 824     }
 825
 826     fn visit_path(&mut self, path: &'tcx hir::Path<'tcx>, _: hir::HirId) {
 827         for (i, segment) in path.segments.iter().enumerate() {
 828             let depth = path.segments.len() - i - 1;
 829             if let Some(ref args) = segment.args {
 830                 self.visit_segment_args(path.res, depth, args);
 831             }
 832         }
 833     }
 834
 835     fn visit_fn(
 836         &mut self,
 837         fk: intravisit::FnKind<'tcx>,
 838         fd: &'tcx hir::FnDecl<'tcx>,
 839         body_id: hir::BodyId,
 840         _: Span,
 841         _: hir::HirId,
 842     ) {
 843         let output = match fd.output {
 844             hir::FnRetTy::DefaultReturn(_) => None,
 845             hir::FnRetTy::Return(ref ty) => Some(&**ty),
 846         };
 847         self.visit_fn_like_elision(&fd.inputs, output, matches!(fk, intravisit::FnKind::Closure));
 848         intravisit::walk_fn_kind(self, fk);
 849         self.visit_nested_body(body_id)
 850     }
 851
 852     fn visit_generics(&mut self, generics: &'tcx hir::Generics<'tcx>) {
 853         let scope = Scope::TraitRefBoundary { s: self.scope };
 854         self.with(scope, |this| {
 855             for param in generics.params {
 856                 match param.kind {
 857                     GenericParamKind::Lifetime { .. } => {}
 858                     GenericParamKind::Type { ref default, .. } => {
 859                         if let Some(ref ty) = default {
 860                             this.visit_ty(&ty);
 861                         }
 862                     }
 863                     GenericParamKind::Const { ref ty, default } => {
 864                         this.visit_ty(&ty);
 865                         if let Some(default) = default {
 866                             this.visit_body(this.tcx.hir().body(default.body));
 867                         }
 868                     }
 869                 }
 870             }
 871             for predicate in generics.predicates {
 872                 match predicate {
 873                     &hir::WherePredicate::BoundPredicate(hir::WhereBoundPredicate {
 874                         hir_id,
 875                         ref bounded_ty,
 876                         bounds,
 877                         ref bound_generic_params,
 878                         origin,
 879                         ..
 880                     }) => {
 881                         let lifetimes: FxIndexMap<LocalDefId, Region> =
 882                             bound_generic_params
 883                                 .iter()
 884                                 .filter(|param| {
 885                                     matches!(param.kind, GenericParamKind::Lifetime { .. })
 886                                 })
 887                                 .enumerate()
 888                                 .map(|(late_bound_idx, param)| {
 889                                         Region::late(late_bound_idx as u32, this.tcx.hir(), param)
 890                                 })
 891                                 .collect();
 892                         let binders: Vec<_> =
 893                             lifetimes
 894                                 .iter()
 895                                 .map(|(_, region)| {
 896                                      late_region_as_bound_region(this.tcx, region)
 897                                 })
 898                                 .collect();
 899                         this.record_late_bound_vars(hir_id, binders.clone());
 900                         // Even if there are no lifetimes defined here, we still wrap it in a binder
 901                         // scope. If there happens to be a nested poly trait ref (an error), that
 902                         // will be `Concatenating` anyways, so we don't have to worry about the depth
 903                         // being wrong.
 904                         let scope = Scope::Binder {
 905                             hir_id,
 906                             lifetimes,
 907                             s: this.scope,
 908                             scope_type: BinderScopeType::Normal,
 909                             where_bound_origin: Some(origin),
 910                         };
 911                         this.with(scope, |this| {
 912                             this.visit_ty(&bounded_ty);
 913                             walk_list!(this, visit_param_bound, bounds);
 914                         })
 915                     }
 916                     &hir::WherePredicate::RegionPredicate(hir::WhereRegionPredicate {
 917                         ref lifetime,
 918                         bounds,
 919                         ..
 920                     }) => {
 921                         this.visit_lifetime(lifetime);
 922                         walk_list!(this, visit_param_bound, bounds);
 923
 924                         if lifetime.name != hir::LifetimeName::Static {
 925                             for bound in bounds {
 926                                 let hir::GenericBound::Outlives(ref lt) = bound else {
 927                                     continue;
 928                                 };
 929                                 if lt.name != hir::LifetimeName::Static {
 930                                     continue;
 931                                 }
 932                                 this.insert_lifetime(lt, Region::Static);
 933                                 this.tcx
 934                                     .sess
 935                                     .struct_span_warn(
 936                                         lifetime.span,
 937                                         &format!(
 938                                             "unnecessary lifetime parameter `{}`",
 939                                             lifetime.name.ident(),
 940                                         ),
 941                                     )
 942                                     .help(&format!(
 943                                         "you can use the `'static` lifetime directly, in place of `{}`",
 944                                         lifetime.name.ident(),
 945                                     ))
 946                                     .emit();
 947                             }
 948                         }
 949                     }
 950                     &hir::WherePredicate::EqPredicate(hir::WhereEqPredicate {
 951                         ref lhs_ty,
 952                         ref rhs_ty,
 953                         ..
 954                     }) => {
 955                         this.visit_ty(lhs_ty);
 956                         this.visit_ty(rhs_ty);
 957                     }
 958                 }
 959             }
 960         })
 961     }
 962
 963     fn visit_param_bound(&mut self, bound: &'tcx hir::GenericBound<'tcx>) {
 964         match bound {
 965             hir::GenericBound::LangItemTrait(_, _, hir_id, _) => {
 966                 // FIXME(jackh726): This is pretty weird. `LangItemTrait` doesn't go
 967                 // through the regular poly trait ref code, so we don't get another
 968                 // chance to introduce a binder. For now, I'm keeping the existing logic
 969                 // of "if there isn't a Binder scope above us, add one", but I
 970                 // imagine there's a better way to go about this.
 971                 let (binders, scope_type) = self.poly_trait_ref_binder_info();
 972
 973                 self.record_late_bound_vars(*hir_id, binders);
 974                 let scope = Scope::Binder {
 975                     hir_id: *hir_id,
 976                     lifetimes: FxIndexMap::default(),
 977                     s: self.scope,
 978                     scope_type,
 979                     where_bound_origin: None,
 980                 };
 981                 self.with(scope, |this| {
 982                     intravisit::walk_param_bound(this, bound);
 983                 });
 984             }
 985             _ => intravisit::walk_param_bound(self, bound),
 986         }
 987     }
 988
 989     fn visit_poly_trait_ref(&mut self, trait_ref: &'tcx hir::PolyTraitRef<'tcx>) {
 990         debug!("visit_poly_trait_ref(trait_ref={:?})", trait_ref);
 991
 992         let (mut binders, scope_type) = self.poly_trait_ref_binder_info();
 993
 994         let initial_bound_vars = binders.len() as u32;
 995         let mut lifetimes: FxIndexMap<LocalDefId, Region> = FxIndexMap::default();
 996         let binders_iter = trait_ref
 997             .bound_generic_params
 998             .iter()
 999             .filter(|param| matches!(param.kind, GenericParamKind::Lifetime { .. }))
1000             .enumerate()
1001             .map(|(late_bound_idx, param)| {
1002                 let pair =
1003                     Region::late(initial_bound_vars + late_bound_idx as u32, self.tcx.hir(), param);
1004                 let r = late_region_as_bound_region(self.tcx, &pair.1);
1005                 lifetimes.insert(pair.0, pair.1);
1006                 r
1007             });
1008         binders.extend(binders_iter);
1009
1010         debug!(?binders);
1011         self.record_late_bound_vars(trait_ref.trait_ref.hir_ref_id, binders);
1012
1013         // Always introduce a scope here, even if this is in a where clause and
1014         // we introduced the binders around the bounded Ty. In that case, we
1015         // just reuse the concatenation functionality also present in nested trait
1016         // refs.
1017         let scope = Scope::Binder {
1018             hir_id: trait_ref.trait_ref.hir_ref_id,
1019             lifetimes,
1020             s: self.scope,
1021             scope_type,
1022             where_bound_origin: None,
1023         };
1024         self.with(scope, |this| {
1025             walk_list!(this, visit_generic_param, trait_ref.bound_generic_params);
1026             this.visit_trait_ref(&trait_ref.trait_ref);
1027         });
1028     }
1029 }
1030
1031 fn object_lifetime_default<'tcx>(tcx: TyCtxt<'tcx>, param_def_id: DefId) -> ObjectLifetimeDefault {
1032     debug_assert_eq!(tcx.def_kind(param_def_id), DefKind::TyParam);
1033     let param_def_id = param_def_id.expect_local();
1034     let parent_def_id = tcx.local_parent(param_def_id);
1035     let generics = tcx.hir().get_generics(parent_def_id).unwrap();
1036     let param_hir_id = tcx.local_def_id_to_hir_id(param_def_id);
1037     let param = generics.params.iter().find(|p| p.hir_id == param_hir_id).unwrap();
1038
1039     // Scan the bounds and where-clauses on parameters to extract bounds
1040     // of the form `T:'a` so as to determine the `ObjectLifetimeDefault`
1041     // for each type parameter.
1042     match param.kind {
1043         GenericParamKind::Type { .. } => {
1044             let mut set = Set1::Empty;
1045
1046             // Look for `type: ...` where clauses.
1047             for bound in generics.bounds_for_param(param_def_id) {
1048                 // Ignore `for<'a> type: ...` as they can change what
1049                 // lifetimes mean (although we could "just" handle it).
1050                 if !bound.bound_generic_params.is_empty() {
1051                     continue;
1052                 }
1053
1054                 for bound in bound.bounds {
1055                     if let hir::GenericBound::Outlives(ref lifetime) = *bound {
1056                         set.insert(lifetime.name.normalize_to_macros_2_0());
1057                     }
1058                 }
1059             }
1060
1061             match set {
1062                 Set1::Empty => ObjectLifetimeDefault::Empty,
1063                 Set1::One(hir::LifetimeName::Static) => ObjectLifetimeDefault::Static,
1064                 Set1::One(hir::LifetimeName::Param(param_def_id, _)) => {
1065                     ObjectLifetimeDefault::Param(param_def_id.to_def_id())
1066                 }
1067                 _ => ObjectLifetimeDefault::Ambiguous,
1068             }
1069         }
1070         _ => {
1071             bug!("object_lifetime_default_raw must only be called on a type parameter")
1072         }
1073     }
1074 }
1075
1076 impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
1077     fn with<F>(&mut self, wrap_scope: Scope<'_>, f: F)
1078     where
1079         F: for<'b> FnOnce(&mut LifetimeContext<'b, 'tcx>),
1080     {
1081         let LifetimeContext { tcx, map, .. } = self;
1082         let mut this = LifetimeContext { tcx: *tcx, map, scope: &wrap_scope };
1083         let span = debug_span!("scope", scope = ?TruncatedScopeDebug(&this.scope));
1084         {
1085             let _enter = span.enter();
1086             f(&mut this);
1087         }
1088     }
1089
1090     fn record_late_bound_vars(&mut self, hir_id: hir::HirId, binder: Vec<ty::BoundVariableKind>) {
1091         if let Some(old) = self.map.late_bound_vars.insert(hir_id, binder) {
1092             bug!(
1093                 "overwrote bound vars for {hir_id:?}:\nold={old:?}\nnew={:?}",
1094                 self.map.late_bound_vars[&hir_id]
1095             )
1096         }
1097     }
1098
1099     /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
1100     ///
1101     /// Handles visiting fns and methods. These are a bit complicated because we must distinguish
1102     /// early- vs late-bound lifetime parameters. We do this by checking which lifetimes appear
1103     /// within type bounds; those are early bound lifetimes, and the rest are late bound.
1104     ///
1105     /// For example:
1106     ///
1107     ///    fn foo<'a,'b,'c,T:Trait<'b>>(...)
1108     ///
1109     /// Here `'a` and `'c` are late bound but `'b` is early bound. Note that early- and late-bound
1110     /// lifetimes may be interspersed together.
1111     ///
1112     /// If early bound lifetimes are present, we separate them into their own list (and likewise
1113     /// for late bound). They will be numbered sequentially, starting from the lowest index that is
1114     /// already in scope (for a fn item, that will be 0, but for a method it might not be). Late
1115     /// bound lifetimes are resolved by name and associated with a binder ID (`binder_id`), so the
1116     /// ordering is not important there.
1117     fn visit_early_late<F>(
1118         &mut self,
1119         hir_id: hir::HirId,
1120         generics: &'tcx hir::Generics<'tcx>,
1121         walk: F,
1122     ) where
1123         F: for<'b, 'c> FnOnce(&'b mut LifetimeContext<'c, 'tcx>),
1124     {
1125         let mut named_late_bound_vars = 0;
1126         let lifetimes: FxIndexMap<LocalDefId, Region> = generics
1127             .params
1128             .iter()
1129             .filter_map(|param| match param.kind {
1130                 GenericParamKind::Lifetime { .. } => {
1131                     if self.tcx.is_late_bound(param.hir_id) {
1132                         let late_bound_idx = named_late_bound_vars;
1133                         named_late_bound_vars += 1;
1134                         Some(Region::late(late_bound_idx, self.tcx.hir(), param))
1135                     } else {
1136                         Some(Region::early(self.tcx.hir(), param))
1137                     }
1138                 }
1139                 GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => None,
1140             })
1141             .collect();
1142
1143         let binders: Vec<_> = generics
1144             .params
1145             .iter()
1146             .filter(|param| {
1147                 matches!(param.kind, GenericParamKind::Lifetime { .. })
1148                     && self.tcx.is_late_bound(param.hir_id)
1149             })
1150             .enumerate()
1151             .map(|(late_bound_idx, param)| {
1152                 let pair = Region::late(late_bound_idx as u32, self.tcx.hir(), param);
1153                 late_region_as_bound_region(self.tcx, &pair.1)
1154             })
1155             .collect();
1156         self.record_late_bound_vars(hir_id, binders);
1157         let scope = Scope::Binder {
1158             hir_id,
1159             lifetimes,
1160             s: self.scope,
1161             scope_type: BinderScopeType::Normal,
1162             where_bound_origin: None,
1163         };
1164         self.with(scope, walk);
1165     }
1166
1167     #[instrument(level = "debug", skip(self))]
1168     fn resolve_lifetime_ref(
1169         &mut self,
1170         region_def_id: LocalDefId,
1171         lifetime_ref: &'tcx hir::Lifetime,
1172     ) {
1173         // Walk up the scope chain, tracking the number of fn scopes
1174         // that we pass through, until we find a lifetime with the
1175         // given name or we run out of scopes.
1176         // search.
1177         let mut late_depth = 0;
1178         let mut scope = self.scope;
1179         let mut outermost_body = None;
1180         let result = loop {
1181             match *scope {
1182                 Scope::Body { id, s } => {
1183                     outermost_body = Some(id);
1184                     scope = s;
1185                 }
1186
1187                 Scope::Root { opt_parent_item } => {
1188                     if let Some(parent_item) = opt_parent_item
1189                         && let parent_generics = self.tcx.generics_of(parent_item)
1190                         && parent_generics.param_def_id_to_index.contains_key(&region_def_id.to_def_id())
1191                     {
1192                         break Some(Region::EarlyBound(region_def_id.to_def_id()));
1193                     }
1194                     break None;
1195                 }
1196
1197                 Scope::Binder { ref lifetimes, scope_type, s, where_bound_origin, .. } => {
1198                     if let Some(&def) = lifetimes.get(&region_def_id) {
1199                         break Some(def.shifted(late_depth));
1200                     }
1201                     match scope_type {
1202                         BinderScopeType::Normal => late_depth += 1,
1203                         BinderScopeType::Concatenating => {}
1204                     }
1205                     // Fresh lifetimes in APIT used to be allowed in async fns and forbidden in
1206                     // regular fns.
1207                     if let Some(hir::PredicateOrigin::ImplTrait) = where_bound_origin
1208                         && let hir::LifetimeName::Param(_, hir::ParamName::Fresh) = lifetime_ref.name
1209                         && let hir::IsAsync::NotAsync = self.tcx.asyncness(lifetime_ref.hir_id.owner.def_id)
1210                         && !self.tcx.features().anonymous_lifetime_in_impl_trait
1211                     {
1212                         let mut diag =  rustc_session::parse::feature_err(
1213                             &self.tcx.sess.parse_sess,
1214                             sym::anonymous_lifetime_in_impl_trait,
1215                             lifetime_ref.span,
1216                             "anonymous lifetimes in `impl Trait` are unstable",
1217                         );
1218
1219                         match self.tcx.hir().get_generics(lifetime_ref.hir_id.owner.def_id) {
1220                             Some(generics) => {
1221
1222                                 let new_param_sugg_tuple;
1223
1224                                 new_param_sugg_tuple = match generics.span_for_param_suggestion() {
1225                                     Some(_) => {
1226                                         Some((self.tcx.sess.source_map().span_through_char(generics.span, '<').shrink_to_hi(), "'a, ".to_owned()))
1227                                     },
1228                                     None => Some((generics.span, "<'a>".to_owned()))
1229                                 };
1230
1231                                 let mut multi_sugg_vec = vec![(lifetime_ref.span.shrink_to_hi(), "'a ".to_owned())];
1232
1233                                 if let Some(new_tuple) =  new_param_sugg_tuple{
1234                                     multi_sugg_vec.push(new_tuple);
1235                                 }
1236
1237                                 diag.span_label(lifetime_ref.span, "expected named lifetime parameter");
1238                                 diag.multipart_suggestion("consider introducing a named lifetime parameter",
1239                                 multi_sugg_vec,
1240                                 rustc_errors::Applicability::MaybeIncorrect);
1241
1242                             },
1243                             None => { }
1244                         }
1245
1246                         diag.emit();
1247                         return;
1248                     }
1249                     scope = s;
1250                 }
1251
1252                 Scope::Elision { s, .. }
1253                 | Scope::ObjectLifetimeDefault { s, .. }
1254                 | Scope::Supertrait { s, .. }
1255                 | Scope::TraitRefBoundary { s, .. } => {
1256                     scope = s;
1257                 }
1258             }
1259         };
1260
1261         if let Some(mut def) = result {
1262             if let Region::EarlyBound(..) = def {
1263                 // Do not free early-bound regions, only late-bound ones.
1264             } else if let Some(body_id) = outermost_body {
1265                 let fn_id = self.tcx.hir().body_owner(body_id);
1266                 match self.tcx.hir().get(fn_id) {
1267                     Node::Item(hir::Item { kind: hir::ItemKind::Fn(..), .. })
1268                     | Node::TraitItem(hir::TraitItem {
1269                         kind: hir::TraitItemKind::Fn(..), ..
1270                     })
1271                     | Node::ImplItem(hir::ImplItem { kind: hir::ImplItemKind::Fn(..), .. })
1272                     | Node::Expr(hir::Expr { kind: hir::ExprKind::Closure(..), .. }) => {
1273                         let scope = self.tcx.hir().local_def_id(fn_id);
1274                         def = Region::Free(scope.to_def_id(), def.id().unwrap());
1275                     }
1276                     _ => {}
1277                 }
1278             }
1279
1280             self.insert_lifetime(lifetime_ref, def);
1281             return;
1282         }
1283
1284         // We may fail to resolve higher-ranked lifetimes that are mentioned by APIT.
1285         // AST-based resolution does not care for impl-trait desugaring, which are the
1286         // responibility of lowering.  This may create a mismatch between the resolution
1287         // AST found (`region_def_id`) which points to HRTB, and what HIR allows.
1288         // ```
1289         // fn foo(x: impl for<'a> Trait<'a, Assoc = impl Copy + 'a>) {}
1290         // ```
1291         //
1292         // In such case, walk back the binders to diagnose it properly.
1293         let mut scope = self.scope;
1294         loop {
1295             match *scope {
1296                 Scope::Binder {
1297                     where_bound_origin: Some(hir::PredicateOrigin::ImplTrait), ..
1298                 } => {
1299                     let mut err = self.tcx.sess.struct_span_err(
1300                         lifetime_ref.span,
1301                         "`impl Trait` can only mention lifetimes bound at the fn or impl level",
1302                     );
1303                     err.span_note(self.tcx.def_span(region_def_id), "lifetime declared here");
1304                     err.emit();
1305                     return;
1306                 }
1307                 Scope::Root { .. } => break,
1308                 Scope::Binder { s, .. }
1309                 | Scope::Body { s, .. }
1310                 | Scope::Elision { s, .. }
1311                 | Scope::ObjectLifetimeDefault { s, .. }
1312                 | Scope::Supertrait { s, .. }
1313                 | Scope::TraitRefBoundary { s, .. } => {
1314                     scope = s;
1315                 }
1316             }
1317         }
1318
1319         self.tcx.sess.delay_span_bug(
1320             lifetime_ref.span,
1321             &format!("Could not resolve {:?} in scope {:#?}", lifetime_ref, self.scope,),
1322         );
1323     }
1324
1325     #[instrument(level = "debug", skip(self))]
1326     fn visit_segment_args(
1327         &mut self,
1328         res: Res,
1329         depth: usize,
1330         generic_args: &'tcx hir::GenericArgs<'tcx>,
1331     ) {
1332         if generic_args.parenthesized {
1333             self.visit_fn_like_elision(
1334                 generic_args.inputs(),
1335                 Some(generic_args.bindings[0].ty()),
1336                 false,
1337             );
1338             return;
1339         }
1340
1341         for arg in generic_args.args {
1342             if let hir::GenericArg::Lifetime(lt) = arg {
1343                 self.visit_lifetime(lt);
1344             }
1345         }
1346
1347         // Figure out if this is a type/trait segment,
1348         // which requires object lifetime defaults.
1349         let type_def_id = match res {
1350             Res::Def(DefKind::AssocTy, def_id) if depth == 1 => Some(self.tcx.parent(def_id)),
1351             Res::Def(DefKind::Variant, def_id) if depth == 0 => Some(self.tcx.parent(def_id)),
1352             Res::Def(
1353                 DefKind::Struct
1354                 | DefKind::Union
1355                 | DefKind::Enum
1356                 | DefKind::TyAlias
1357                 | DefKind::Trait,
1358                 def_id,
1359             ) if depth == 0 => Some(def_id),
1360             _ => None,
1361         };
1362
1363         debug!(?type_def_id);
1364
1365         // Compute a vector of defaults, one for each type parameter,
1366         // per the rules given in RFCs 599 and 1156. Example:
1367         //
1368         // ```rust
1369         // struct Foo<'a, T: 'a, U> { }
1370         // ```
1371         //
1372         // If you have `Foo<'x, dyn Bar, dyn Baz>`, we want to default
1373         // `dyn Bar` to `dyn Bar + 'x` (because of the `T: 'a` bound)
1374         // and `dyn Baz` to `dyn Baz + 'static` (because there is no
1375         // such bound).
1376         //
1377         // Therefore, we would compute `object_lifetime_defaults` to a
1378         // vector like `['x, 'static]`. Note that the vector only
1379         // includes type parameters.
1380         let object_lifetime_defaults = type_def_id.map_or_else(Vec::new, |def_id| {
1381             let in_body = {
1382                 let mut scope = self.scope;
1383                 loop {
1384                     match *scope {
1385                         Scope::Root { .. } => break false,
1386
1387                         Scope::Body { .. } => break true,
1388
1389                         Scope::Binder { s, .. }
1390                         | Scope::Elision { s, .. }
1391                         | Scope::ObjectLifetimeDefault { s, .. }
1392                         | Scope::Supertrait { s, .. }
1393                         | Scope::TraitRefBoundary { s, .. } => {
1394                             scope = s;
1395                         }
1396                     }
1397                 }
1398             };
1399
1400             let map = &self.map;
1401             let generics = self.tcx.generics_of(def_id);
1402
1403             // `type_def_id` points to an item, so there is nothing to inherit generics from.
1404             debug_assert_eq!(generics.parent_count, 0);
1405
1406             let set_to_region = |set: ObjectLifetimeDefault| match set {
1407                 ObjectLifetimeDefault::Empty => {
1408                     if in_body {
1409                         None
1410                     } else {
1411                         Some(Region::Static)
1412                     }
1413                 }
1414                 ObjectLifetimeDefault::Static => Some(Region::Static),
1415                 ObjectLifetimeDefault::Param(param_def_id) => {
1416                     // This index can be used with `generic_args` since `parent_count == 0`.
1417                     let index = generics.param_def_id_to_index[&param_def_id] as usize;
1418                     generic_args.args.get(index).and_then(|arg| match arg {
1419                         GenericArg::Lifetime(lt) => map.defs.get(&lt.hir_id).copied(),
1420                         _ => None,
1421                     })
1422                 }
1423                 ObjectLifetimeDefault::Ambiguous => None,
1424             };
1425             generics
1426                 .params
1427                 .iter()
1428                 .filter_map(|param| {
1429                     match self.tcx.def_kind(param.def_id) {
1430                         // Generic consts don't impose any constraints.
1431                         //
1432                         // We still store a dummy value here to allow generic parameters
1433                         // in an arbitrary order.
1434                         DefKind::ConstParam => Some(ObjectLifetimeDefault::Empty),
1435                         DefKind::TyParam => Some(self.tcx.object_lifetime_default(param.def_id)),
1436                         // We may also get a `Trait` or `TraitAlias` because of how generics `Self` parameter
1437                         // works.  Ignore it because it can't have a meaningful lifetime default.
1438                         DefKind::LifetimeParam | DefKind::Trait | DefKind::TraitAlias => None,
1439                         dk => bug!("unexpected def_kind {:?}", dk),
1440                     }
1441                 })
1442                 .map(set_to_region)
1443                 .collect()
1444         });
1445
1446         debug!(?object_lifetime_defaults);
1447
1448         let mut i = 0;
1449         for arg in generic_args.args {
1450             match arg {
1451                 GenericArg::Lifetime(_) => {}
1452                 GenericArg::Type(ty) => {
1453                     if let Some(&lt) = object_lifetime_defaults.get(i) {
1454                         let scope = Scope::ObjectLifetimeDefault { lifetime: lt, s: self.scope };
1455                         self.with(scope, |this| this.visit_ty(ty));
1456                     } else {
1457                         self.visit_ty(ty);
1458                     }
1459                     i += 1;
1460                 }
1461                 GenericArg::Const(ct) => {
1462                     self.visit_anon_const(&ct.value);
1463                     i += 1;
1464                 }
1465                 GenericArg::Infer(inf) => {
1466                     self.visit_id(inf.hir_id);
1467                     i += 1;
1468                 }
1469             }
1470         }
1471
1472         // Hack: when resolving the type `XX` in binding like `dyn
1473         // Foo<'b, Item = XX>`, the current object-lifetime default
1474         // would be to examine the trait `Foo` to check whether it has
1475         // a lifetime bound declared on `Item`. e.g., if `Foo` is
1476         // declared like so, then the default object lifetime bound in
1477         // `XX` should be `'b`:
1478         //
1479         // ```rust
1480         // trait Foo<'a> {
1481         //   type Item: 'a;
1482         // }
1483         // ```
1484         //
1485         // but if we just have `type Item;`, then it would be
1486         // `'static`. However, we don't get all of this logic correct.
1487         //
1488         // Instead, we do something hacky: if there are no lifetime parameters
1489         // to the trait, then we simply use a default object lifetime
1490         // bound of `'static`, because there is no other possibility. On the other hand,
1491         // if there ARE lifetime parameters, then we require the user to give an
1492         // explicit bound for now.
1493         //
1494         // This is intended to leave room for us to implement the
1495         // correct behavior in the future.
1496         let has_lifetime_parameter =
1497             generic_args.args.iter().any(|arg| matches!(arg, GenericArg::Lifetime(_)));
1498
1499         // Resolve lifetimes found in the bindings, so either in the type `XX` in `Item = XX` or
1500         // in the trait ref `YY<...>` in `Item: YY<...>`.
1501         for binding in generic_args.bindings {
1502             let scope = Scope::ObjectLifetimeDefault {
1503                 lifetime: if has_lifetime_parameter { None } else { Some(Region::Static) },
1504                 s: self.scope,
1505             };
1506             if let Some(type_def_id) = type_def_id {
1507                 let lifetimes = LifetimeContext::supertrait_hrtb_lifetimes(
1508                     self.tcx,
1509                     type_def_id,
1510                     binding.ident,
1511                 );
1512                 self.with(scope, |this| {
1513                     let scope = Scope::Supertrait {
1514                         lifetimes: lifetimes.unwrap_or_default(),
1515                         s: this.scope,
1516                     };
1517                     this.with(scope, |this| this.visit_assoc_type_binding(binding));
1518                 });
1519             } else {
1520                 self.with(scope, |this| this.visit_assoc_type_binding(binding));
1521             }
1522         }
1523     }
1524
1525     /// Returns all the late-bound vars that come into scope from supertrait HRTBs, based on the
1526     /// associated type name and starting trait.
1527     /// For example, imagine we have
1528     /// ```ignore (illustrative)
1529     /// trait Foo<'a, 'b> {
1530     ///   type As;
1531     /// }
1532     /// trait Bar<'b>: for<'a> Foo<'a, 'b> {}
1533     /// trait Bar: for<'b> Bar<'b> {}
1534     /// ```
1535     /// In this case, if we wanted to the supertrait HRTB lifetimes for `As` on
1536     /// the starting trait `Bar`, we would return `Some(['b, 'a])`.
1537     fn supertrait_hrtb_lifetimes(
1538         tcx: TyCtxt<'tcx>,
1539         def_id: DefId,
1540         assoc_name: Ident,
1541     ) -> Option<Vec<ty::BoundVariableKind>> {
1542         let trait_defines_associated_type_named = |trait_def_id: DefId| {
1543             tcx.associated_items(trait_def_id)
1544                 .find_by_name_and_kind(tcx, assoc_name, ty::AssocKind::Type, trait_def_id)
1545                 .is_some()
1546         };
1547
1548         use smallvec::{smallvec, SmallVec};
1549         let mut stack: SmallVec<[(DefId, SmallVec<[ty::BoundVariableKind; 8]>); 8]> =
1550             smallvec![(def_id, smallvec![])];
1551         let mut visited: FxHashSet<DefId> = FxHashSet::default();
1552         loop {
1553             let Some((def_id, bound_vars)) = stack.pop() else {
1554                 break None;
1555             };
1556             // See issue #83753. If someone writes an associated type on a non-trait, just treat it as
1557             // there being no supertrait HRTBs.
1558             match tcx.def_kind(def_id) {
1559                 DefKind::Trait | DefKind::TraitAlias | DefKind::Impl => {}
1560                 _ => break None,
1561             }
1562
1563             if trait_defines_associated_type_named(def_id) {
1564                 break Some(bound_vars.into_iter().collect());
1565             }
1566             let predicates =
1567                 tcx.super_predicates_that_define_assoc_type((def_id, Some(assoc_name)));
1568             let obligations = predicates.predicates.iter().filter_map(|&(pred, _)| {
1569                 let bound_predicate = pred.kind();
1570                 match bound_predicate.skip_binder() {
1571                     ty::PredicateKind::Trait(data) => {
1572                         // The order here needs to match what we would get from `subst_supertrait`
1573                         let pred_bound_vars = bound_predicate.bound_vars();
1574                         let mut all_bound_vars = bound_vars.clone();
1575                         all_bound_vars.extend(pred_bound_vars.iter());
1576                         let super_def_id = data.trait_ref.def_id;
1577                         Some((super_def_id, all_bound_vars))
1578                     }
1579                     _ => None,
1580                 }
1581             });
1582
1583             let obligations = obligations.filter(|o| visited.insert(o.0));
1584             stack.extend(obligations);
1585         }
1586     }
1587
1588     #[instrument(level = "debug", skip(self))]
1589     fn visit_fn_like_elision(
1590         &mut self,
1591         inputs: &'tcx [hir::Ty<'tcx>],
1592         output: Option<&'tcx hir::Ty<'tcx>>,
1593         in_closure: bool,
1594     ) {
1595         self.with(Scope::Elision { s: self.scope }, |this| {
1596             for input in inputs {
1597                 this.visit_ty(input);
1598             }
1599             if !in_closure && let Some(output) = output {
1600                 this.visit_ty(output);
1601             }
1602         });
1603         if in_closure && let Some(output) = output {
1604             self.visit_ty(output);
1605         }
1606     }
1607
1608     fn resolve_object_lifetime_default(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
1609         debug!("resolve_object_lifetime_default(lifetime_ref={:?})", lifetime_ref);
1610         let mut late_depth = 0;
1611         let mut scope = self.scope;
1612         let lifetime = loop {
1613             match *scope {
1614                 Scope::Binder { s, scope_type, .. } => {
1615                     match scope_type {
1616                         BinderScopeType::Normal => late_depth += 1,
1617                         BinderScopeType::Concatenating => {}
1618                     }
1619                     scope = s;
1620                 }
1621
1622                 Scope::Root { .. } | Scope::Elision { .. } => break Region::Static,
1623
1624                 Scope::Body { .. } | Scope::ObjectLifetimeDefault { lifetime: None, .. } => return,
1625
1626                 Scope::ObjectLifetimeDefault { lifetime: Some(l), .. } => break l,
1627
1628                 Scope::Supertrait { s, .. } | Scope::TraitRefBoundary { s, .. } => {
1629                     scope = s;
1630                 }
1631             }
1632         };
1633         self.insert_lifetime(lifetime_ref, lifetime.shifted(late_depth));
1634     }
1635
1636     #[instrument(level = "debug", skip(self))]
1637     fn insert_lifetime(&mut self, lifetime_ref: &'tcx hir::Lifetime, def: Region) {
1638         debug!(
1639             node = ?self.tcx.hir().node_to_string(lifetime_ref.hir_id),
1640             span = ?self.tcx.sess.source_map().span_to_diagnostic_string(lifetime_ref.span)
1641         );
1642         self.map.defs.insert(lifetime_ref.hir_id, def);
1643     }
1644
1645     /// Sometimes we resolve a lifetime, but later find that it is an
1646     /// error (esp. around impl trait). In that case, we remove the
1647     /// entry into `map.defs` so as not to confuse later code.
1648     fn uninsert_lifetime_on_error(&mut self, lifetime_ref: &'tcx hir::Lifetime, bad_def: Region) {
1649         let old_value = self.map.defs.remove(&lifetime_ref.hir_id);
1650         assert_eq!(old_value, Some(bad_def));
1651     }
1652 }
1653
1654 /// Detects late-bound lifetimes and inserts them into
1655 /// `late_bound`.
1656 ///
1657 /// A region declared on a fn is **late-bound** if:
1658 /// - it is constrained by an argument type;
1659 /// - it does not appear in a where-clause.
1660 ///
1661 /// "Constrained" basically means that it appears in any type but
1662 /// not amongst the inputs to a projection. In other words, `<&'a
1663 /// T as Trait<''b>>::Foo` does not constrain `'a` or `'b`.
1664 fn is_late_bound_map(tcx: TyCtxt<'_>, def_id: LocalDefId) -> Option<&FxIndexSet<LocalDefId>> {
1665     let hir_id = tcx.hir().local_def_id_to_hir_id(def_id);
1666     let decl = tcx.hir().fn_decl_by_hir_id(hir_id)?;
1667     let generics = tcx.hir().get_generics(def_id)?;
1668
1669     let mut late_bound = FxIndexSet::default();
1670
1671     let mut constrained_by_input = ConstrainedCollector { regions: Default::default(), tcx };
1672     for arg_ty in decl.inputs {
1673         constrained_by_input.visit_ty(arg_ty);
1674     }
1675
1676     let mut appears_in_output = AllCollector::default();
1677     intravisit::walk_fn_ret_ty(&mut appears_in_output, &decl.output);
1678
1679     debug!(?constrained_by_input.regions);
1680
1681     // Walk the lifetimes that appear in where clauses.
1682     //
1683     // Subtle point: because we disallow nested bindings, we can just
1684     // ignore binders here and scrape up all names we see.
1685     let mut appears_in_where_clause = AllCollector::default();
1686     appears_in_where_clause.visit_generics(generics);
1687     debug!(?appears_in_where_clause.regions);
1688
1689     // Late bound regions are those that:
1690     // - appear in the inputs
1691     // - do not appear in the where-clauses
1692     // - are not implicitly captured by `impl Trait`
1693     for param in generics.params {
1694         match param.kind {
1695             hir::GenericParamKind::Lifetime { .. } => { /* fall through */ }
1696
1697             // Neither types nor consts are late-bound.
1698             hir::GenericParamKind::Type { .. } | hir::GenericParamKind::Const { .. } => continue,
1699         }
1700
1701         let param_def_id = tcx.hir().local_def_id(param.hir_id);
1702
1703         // appears in the where clauses? early-bound.
1704         if appears_in_where_clause.regions.contains(&param_def_id) {
1705             continue;
1706         }
1707
1708         // does not appear in the inputs, but appears in the return type? early-bound.
1709         if !constrained_by_input.regions.contains(&param_def_id)
1710             && appears_in_output.regions.contains(&param_def_id)
1711         {
1712             continue;
1713         }
1714
1715         debug!("lifetime {:?} with id {:?} is late-bound", param.name.ident(), param.hir_id);
1716
1717         let inserted = late_bound.insert(param_def_id);
1718         assert!(inserted, "visited lifetime {:?} twice", param.hir_id);
1719     }
1720
1721     debug!(?late_bound);
1722     return Some(tcx.arena.alloc(late_bound));
1723
1724     /// Visits a `ty::Ty` collecting information about what generic parameters are constrained.
1725     ///
1726     /// The visitor does not operate on `hir::Ty` so that it can be called on the rhs of a `type Alias<...> = ...;`
1727     /// which may live in a separate crate so there would not be any hir available. Instead we use the `type_of`
1728     /// query to obtain a `ty::Ty` which will be present even in cross crate scenarios. It also naturally
1729     /// handles cycle detection as we go through the query system.
1730     ///
1731     /// This is necessary in the first place for the following case:
1732     /// ```
1733     /// type Alias<'a, T> = <T as Trait<'a>>::Assoc;
1734     /// fn foo<'a>(_: Alias<'a, ()>) -> Alias<'a, ()> { ... }
1735     /// ```
1736     ///
1737     /// If we conservatively considered `'a` unconstrained then we could break users who had written code before
1738     /// we started correctly handling aliases. If we considered `'a` constrained then it would become late bound
1739     /// causing an error during astconv as the `'a` is not constrained by the input type `<() as Trait<'a>>::Assoc`
1740     /// but appears in the output type `<() as Trait<'a>>::Assoc`.
1741     ///
1742     /// We must therefore "look into" the `Alias` to see whether we should consider `'a` constrained or not.
1743     ///
1744     /// See #100508 #85533 #47511 for additional context
1745     struct ConstrainedCollectorPostAstConv {
1746         arg_is_constrained: Box<[bool]>,
1747     }
1748
1749     use std::ops::ControlFlow;
1750     use ty::Ty;
1751     impl<'tcx> TypeVisitor<'tcx> for ConstrainedCollectorPostAstConv {
1752         fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<!> {
1753             match t.kind() {
1754                 ty::Param(param_ty) => {
1755                     self.arg_is_constrained[param_ty.index as usize] = true;
1756                 }
1757                 ty::Projection(_) => return ControlFlow::Continue(()),
1758                 _ => (),
1759             }
1760             t.super_visit_with(self)
1761         }
1762
1763         fn visit_const(&mut self, _: ty::Const<'tcx>) -> ControlFlow<!> {
1764             ControlFlow::Continue(())
1765         }
1766
1767         fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<!> {
1768             debug!("r={:?}", r.kind());
1769             if let ty::RegionKind::ReEarlyBound(region) = r.kind() {
1770                 self.arg_is_constrained[region.index as usize] = true;
1771             }
1772
1773             ControlFlow::Continue(())
1774         }
1775     }
1776
1777     struct ConstrainedCollector<'tcx> {
1778         tcx: TyCtxt<'tcx>,
1779         regions: FxHashSet<LocalDefId>,
1780     }
1781
1782     impl<'v> Visitor<'v> for ConstrainedCollector<'_> {
1783         fn visit_ty(&mut self, ty: &'v hir::Ty<'v>) {
1784             match ty.kind {
1785                 hir::TyKind::Path(
1786                     hir::QPath::Resolved(Some(_), _) | hir::QPath::TypeRelative(..),
1787                 ) => {
1788                     // ignore lifetimes appearing in associated type
1789                     // projections, as they are not *constrained*
1790                     // (defined above)
1791                 }
1792
1793                 hir::TyKind::Path(hir::QPath::Resolved(
1794                     None,
1795                     hir::Path { res: Res::Def(DefKind::TyAlias, alias_def), segments, span },
1796                 )) => {
1797                     // See comments on `ConstrainedCollectorPostAstConv` for why this arm does not just consider
1798                     // substs to be unconstrained.
1799                     let generics = self.tcx.generics_of(alias_def);
1800                     let mut walker = ConstrainedCollectorPostAstConv {
1801                         arg_is_constrained: vec![false; generics.params.len()].into_boxed_slice(),
1802                     };
1803                     walker.visit_ty(self.tcx.type_of(alias_def));
1804
1805                     match segments.last() {
1806                         Some(hir::PathSegment { args: Some(args), .. }) => {
1807                             let tcx = self.tcx;
1808                             for constrained_arg in
1809                                 args.args.iter().enumerate().flat_map(|(n, arg)| {
1810                                     match walker.arg_is_constrained.get(n) {
1811                                         Some(true) => Some(arg),
1812                                         Some(false) => None,
1813                                         None => {
1814                                             tcx.sess.delay_span_bug(
1815                                                 *span,
1816                                                 format!(
1817                                                     "Incorrect generic arg count for alias {:?}",
1818                                                     alias_def
1819                                                 ),
1820                                             );
1821                                             None
1822                                         }
1823                                     }
1824                                 })
1825                             {
1826                                 self.visit_generic_arg(constrained_arg);
1827                             }
1828                         }
1829                         Some(_) => (),
1830                         None => bug!("Path with no segments or self type"),
1831                     }
1832                 }
1833
1834                 hir::TyKind::Path(hir::QPath::Resolved(None, ref path)) => {
1835                     // consider only the lifetimes on the final
1836                     // segment; I am not sure it's even currently
1837                     // valid to have them elsewhere, but even if it
1838                     // is, those would be potentially inputs to
1839                     // projections
1840                     if let Some(last_segment) = path.segments.last() {
1841                         self.visit_path_segment(last_segment);
1842                     }
1843                 }
1844
1845                 _ => {
1846                     intravisit::walk_ty(self, ty);
1847                 }
1848             }
1849         }
1850
1851         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
1852             if let hir::LifetimeName::Param(def_id, _) = lifetime_ref.name {
1853                 self.regions.insert(def_id);
1854             }
1855         }
1856     }
1857
1858     #[derive(Default)]
1859     struct AllCollector {
1860         regions: FxHashSet<LocalDefId>,
1861     }
1862
1863     impl<'v> Visitor<'v> for AllCollector {
1864         fn visit_lifetime(&mut self, lifetime_ref: &'v hir::Lifetime) {
1865             if let hir::LifetimeName::Param(def_id, _) = lifetime_ref.name {
1866                 self.regions.insert(def_id);
1867             }
1868         }
1869     }
1870 }