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