rustc_infer/infer/outlives/obligations.rs
1//! Code that handles "type-outlives" constraints like `T: 'a`. This
2//! is based on the `push_outlives_components` function defined in rustc_infer,
3//! but it adds a bit of heuristics on top, in particular to deal with
4//! associated types and projections.
5//!
6//! When we process a given `T: 'a` obligation, we may produce two
7//! kinds of constraints for the region inferencer:
8//!
9//! - Relationships between inference variables and other regions.
10//! For example, if we have `&'?0 u32: 'a`, then we would produce
11//! a constraint that `'a <= '?0`.
12//! - "Verifys" that must be checked after inferencing is done.
13//! For example, if we know that, for some type parameter `T`,
14//! `T: 'a + 'b`, and we have a requirement that `T: '?1`,
15//! then we add a "verify" that checks that `'?1 <= 'a || '?1 <= 'b`.
16//! - Note the difference with the previous case: here, the region
17//! variable must be less than something else, so this doesn't
18//! affect how inference works (it finds the smallest region that
19//! will do); it's just a post-condition that we have to check.
20//!
21//! **The key point is that once this function is done, we have
22//! reduced all of our "type-region outlives" obligations into relationships
23//! between individual regions.**
24//!
25//! One key input to this function is the set of "region-bound pairs".
26//! These are basically the relationships between type parameters and
27//! regions that are in scope at the point where the outlives
28//! obligation was incurred. **When type-checking a function,
29//! particularly in the face of closures, this is not known until
30//! regionck runs!** This is because some of those bounds come
31//! from things we have yet to infer.
32//!
33//! Consider:
34//!
35//! ```
36//! fn bar<T>(a: T, b: impl for<'a> Fn(&'a T)) {}
37//! fn foo<T>(x: T) {
38//! bar(x, |y| { /* ... */})
39//! // ^ closure arg
40//! }
41//! ```
42//!
43//! Here, the type of `y` may involve inference variables and the
44//! like, and it may also contain implied bounds that are needed to
45//! type-check the closure body (e.g., here it informs us that `T`
46//! outlives the late-bound region `'a`).
47//!
48//! Note that by delaying the gathering of implied bounds until all
49//! inference information is known, we may find relationships between
50//! bound regions and other regions in the environment. For example,
51//! when we first check a closure like the one expected as argument
52//! to `foo`:
53//!
54//! ```
55//! fn foo<U, F: for<'a> FnMut(&'a U)>(_f: F) {}
56//! ```
57//!
58//! the type of the closure's first argument would be `&'a ?U`. We
59//! might later infer `?U` to something like `&'b u32`, which would
60//! imply that `'b: 'a`.
61
62use rustc_data_structures::undo_log::UndoLogs;
63use rustc_middle::bug;
64use rustc_middle::mir::ConstraintCategory;
65use rustc_middle::traits::query::NoSolution;
66use rustc_middle::ty::outlives::{Component, push_outlives_components};
67use rustc_middle::ty::{
68 self, GenericArgKind, GenericArgsRef, PolyTypeOutlivesPredicate, Region, Ty, TyCtxt,
69 TypeFoldable as _, TypeVisitableExt,
70};
71use smallvec::smallvec;
72use tracing::{debug, instrument};
73
74use super::env::OutlivesEnvironment;
75use crate::infer::outlives::env::RegionBoundPairs;
76use crate::infer::outlives::verify::VerifyBoundCx;
77use crate::infer::resolve::OpportunisticRegionResolver;
78use crate::infer::snapshot::undo_log::UndoLog;
79use crate::infer::{
80 self, GenericKind, InferCtxt, SubregionOrigin, TypeOutlivesConstraint, VerifyBound,
81};
82use crate::traits::{ObligationCause, ObligationCauseCode};
83
84impl<'tcx> InferCtxt<'tcx> {
85 pub fn register_outlives_constraint(
86 &self,
87 ty::OutlivesPredicate(arg, r2): ty::OutlivesPredicate<'tcx, ty::GenericArg<'tcx>>,
88 cause: &ObligationCause<'tcx>,
89 ) {
90 match arg.kind() {
91 ty::GenericArgKind::Lifetime(r1) => {
92 self.register_region_outlives_constraint(ty::OutlivesPredicate(r1, r2), cause);
93 }
94 ty::GenericArgKind::Type(ty1) => {
95 self.register_type_outlives_constraint(ty1, r2, cause);
96 }
97 ty::GenericArgKind::Const(_) => unreachable!(),
98 }
99 }
100
101 pub fn register_region_outlives_constraint(
102 &self,
103 ty::OutlivesPredicate(r_a, r_b): ty::RegionOutlivesPredicate<'tcx>,
104 cause: &ObligationCause<'tcx>,
105 ) {
106 let origin = SubregionOrigin::from_obligation_cause(cause, || {
107 SubregionOrigin::RelateRegionParamBound(cause.span, None)
108 });
109 // `'a: 'b` ==> `'b <= 'a`
110 self.sub_regions(origin, r_b, r_a);
111 }
112
113 /// Registers that the given region obligation must be resolved
114 /// from within the scope of `body_id`. These regions are enqueued
115 /// and later processed by regionck, when full type information is
116 /// available (see `region_obligations` field for more
117 /// information).
118 #[instrument(level = "debug", skip(self))]
119 pub fn register_type_outlives_constraint_inner(
120 &self,
121 obligation: TypeOutlivesConstraint<'tcx>,
122 ) {
123 let mut inner = self.inner.borrow_mut();
124 inner.undo_log.push(UndoLog::PushTypeOutlivesConstraint);
125 inner.region_obligations.push(obligation);
126 }
127
128 pub fn register_type_outlives_constraint(
129 &self,
130 sup_type: Ty<'tcx>,
131 sub_region: Region<'tcx>,
132 cause: &ObligationCause<'tcx>,
133 ) {
134 // `is_global` means the type has no params, infer, placeholder, or non-`'static`
135 // free regions. If the type has none of these things, then we can skip registering
136 // this outlives obligation since it has no components which affect lifetime
137 // checking in an interesting way.
138 if sup_type.is_global() {
139 return;
140 }
141
142 debug!(?sup_type, ?sub_region, ?cause);
143 let origin = SubregionOrigin::from_obligation_cause(cause, || {
144 SubregionOrigin::RelateParamBound(
145 cause.span,
146 sup_type,
147 match cause.code().peel_derives() {
148 ObligationCauseCode::WhereClause(_, span)
149 | ObligationCauseCode::WhereClauseInExpr(_, span, ..)
150 | ObligationCauseCode::OpaqueTypeBound(span, _)
151 if !span.is_dummy() =>
152 {
153 Some(*span)
154 }
155 _ => None,
156 },
157 )
158 });
159
160 self.register_type_outlives_constraint_inner(TypeOutlivesConstraint {
161 sup_type,
162 sub_region,
163 origin,
164 });
165 }
166
167 /// Trait queries just want to pass back type obligations "as is"
168 pub fn take_registered_region_obligations(&self) -> Vec<TypeOutlivesConstraint<'tcx>> {
169 std::mem::take(&mut self.inner.borrow_mut().region_obligations)
170 }
171
172 /// Process the region obligations that must be proven (during
173 /// `regionck`) for the given `body_id`, given information about
174 /// the region bounds in scope and so forth.
175 ///
176 /// See the `region_obligations` field of `InferCtxt` for some
177 /// comments about how this function fits into the overall expected
178 /// flow of the inferencer. The key point is that it is
179 /// invoked after all type-inference variables have been bound --
180 /// right before lexical region resolution.
181 #[instrument(level = "debug", skip(self, outlives_env, deeply_normalize_ty))]
182 pub fn process_registered_region_obligations(
183 &self,
184 outlives_env: &OutlivesEnvironment<'tcx>,
185 mut deeply_normalize_ty: impl FnMut(
186 PolyTypeOutlivesPredicate<'tcx>,
187 SubregionOrigin<'tcx>,
188 )
189 -> Result<PolyTypeOutlivesPredicate<'tcx>, NoSolution>,
190 ) -> Result<(), (PolyTypeOutlivesPredicate<'tcx>, SubregionOrigin<'tcx>)> {
191 assert!(!self.in_snapshot(), "cannot process registered region obligations in a snapshot");
192
193 // Must loop since the process of normalizing may itself register region obligations.
194 for iteration in 0.. {
195 let my_region_obligations = self.take_registered_region_obligations();
196 if my_region_obligations.is_empty() {
197 break;
198 }
199
200 if !self.tcx.recursion_limit().value_within_limit(iteration) {
201 // This may actually be reachable. If so, we should convert
202 // this to a proper error/consider whether we should detect
203 // this somewhere else.
204 bug!(
205 "unexpected overflowed when processing region obligations: {my_region_obligations:#?}"
206 );
207 }
208
209 for TypeOutlivesConstraint { sup_type, sub_region, origin } in my_region_obligations {
210 let outlives = ty::Binder::dummy(ty::OutlivesPredicate(sup_type, sub_region));
211 let ty::OutlivesPredicate(sup_type, sub_region) =
212 deeply_normalize_ty(outlives, origin.clone())
213 .map_err(|NoSolution| (outlives, origin.clone()))?
214 .no_bound_vars()
215 .expect("started with no bound vars, should end with no bound vars");
216 // `TypeOutlives` is structural, so we should try to opportunistically resolve all
217 // region vids before processing regions, so we have a better chance to match clauses
218 // in our param-env.
219 let (sup_type, sub_region) =
220 (sup_type, sub_region).fold_with(&mut OpportunisticRegionResolver::new(self));
221
222 debug!(?sup_type, ?sub_region, ?origin);
223
224 let outlives = &mut TypeOutlives::new(
225 self,
226 self.tcx,
227 outlives_env.region_bound_pairs(),
228 None,
229 outlives_env.known_type_outlives(),
230 );
231 let category = origin.to_constraint_category();
232 outlives.type_must_outlive(origin, sup_type, sub_region, category);
233 }
234 }
235
236 Ok(())
237 }
238}
239
240/// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
241/// obligation into a series of `'a: 'b` constraints and "verify"s, as
242/// described on the module comment. The final constraints are emitted
243/// via a "delegate" of type `D` -- this is usually the `infcx`, which
244/// accrues them into the `region_obligations` code, but for NLL we
245/// use something else.
246pub struct TypeOutlives<'cx, 'tcx, D>
247where
248 D: TypeOutlivesDelegate<'tcx>,
249{
250 // See the comments on `process_registered_region_obligations` for the meaning
251 // of these fields.
252 delegate: D,
253 tcx: TyCtxt<'tcx>,
254 verify_bound: VerifyBoundCx<'cx, 'tcx>,
255}
256
257pub trait TypeOutlivesDelegate<'tcx> {
258 fn push_sub_region_constraint(
259 &mut self,
260 origin: SubregionOrigin<'tcx>,
261 a: ty::Region<'tcx>,
262 b: ty::Region<'tcx>,
263 constraint_category: ConstraintCategory<'tcx>,
264 );
265
266 fn push_verify(
267 &mut self,
268 origin: SubregionOrigin<'tcx>,
269 kind: GenericKind<'tcx>,
270 a: ty::Region<'tcx>,
271 bound: VerifyBound<'tcx>,
272 );
273}
274
275impl<'cx, 'tcx, D> TypeOutlives<'cx, 'tcx, D>
276where
277 D: TypeOutlivesDelegate<'tcx>,
278{
279 pub fn new(
280 delegate: D,
281 tcx: TyCtxt<'tcx>,
282 region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
283 implicit_region_bound: Option<ty::Region<'tcx>>,
284 caller_bounds: &'cx [ty::PolyTypeOutlivesPredicate<'tcx>],
285 ) -> Self {
286 Self {
287 delegate,
288 tcx,
289 verify_bound: VerifyBoundCx::new(
290 tcx,
291 region_bound_pairs,
292 implicit_region_bound,
293 caller_bounds,
294 ),
295 }
296 }
297
298 /// Adds constraints to inference such that `T: 'a` holds (or
299 /// reports an error if it cannot).
300 ///
301 /// # Parameters
302 ///
303 /// - `origin`, the reason we need this constraint
304 /// - `ty`, the type `T`
305 /// - `region`, the region `'a`
306 #[instrument(level = "debug", skip(self))]
307 pub fn type_must_outlive(
308 &mut self,
309 origin: infer::SubregionOrigin<'tcx>,
310 ty: Ty<'tcx>,
311 region: ty::Region<'tcx>,
312 category: ConstraintCategory<'tcx>,
313 ) {
314 assert!(!ty.has_escaping_bound_vars());
315
316 let mut components = smallvec![];
317 push_outlives_components(self.tcx, ty, &mut components);
318 self.components_must_outlive(origin, &components, region, category);
319 }
320
321 fn components_must_outlive(
322 &mut self,
323 origin: infer::SubregionOrigin<'tcx>,
324 components: &[Component<TyCtxt<'tcx>>],
325 region: ty::Region<'tcx>,
326 category: ConstraintCategory<'tcx>,
327 ) {
328 for component in components.iter() {
329 let origin = origin.clone();
330 match component {
331 Component::Region(region1) => {
332 self.delegate.push_sub_region_constraint(origin, region, *region1, category);
333 }
334 Component::Param(param_ty) => {
335 self.param_ty_must_outlive(origin, region, *param_ty);
336 }
337 Component::Placeholder(placeholder_ty) => {
338 self.placeholder_ty_must_outlive(origin, region, *placeholder_ty);
339 }
340 Component::Alias(alias_ty) => self.alias_ty_must_outlive(origin, region, *alias_ty),
341 Component::EscapingAlias(subcomponents) => {
342 self.components_must_outlive(origin, subcomponents, region, category);
343 }
344 Component::UnresolvedInferenceVariable(v) => {
345 // Ignore this, we presume it will yield an error later,
346 // since if a type variable is not resolved by this point
347 // it never will be.
348 self.tcx.dcx().span_delayed_bug(
349 origin.span(),
350 format!("unresolved inference variable in outlives: {v:?}"),
351 );
352 }
353 }
354 }
355 }
356
357 #[instrument(level = "debug", skip(self))]
358 fn param_ty_must_outlive(
359 &mut self,
360 origin: infer::SubregionOrigin<'tcx>,
361 region: ty::Region<'tcx>,
362 param_ty: ty::ParamTy,
363 ) {
364 let verify_bound = self.verify_bound.param_or_placeholder_bound(param_ty.to_ty(self.tcx));
365 self.delegate.push_verify(origin, GenericKind::Param(param_ty), region, verify_bound);
366 }
367
368 #[instrument(level = "debug", skip(self))]
369 fn placeholder_ty_must_outlive(
370 &mut self,
371 origin: infer::SubregionOrigin<'tcx>,
372 region: ty::Region<'tcx>,
373 placeholder_ty: ty::PlaceholderType,
374 ) {
375 let verify_bound = self
376 .verify_bound
377 .param_or_placeholder_bound(Ty::new_placeholder(self.tcx, placeholder_ty));
378 self.delegate.push_verify(
379 origin,
380 GenericKind::Placeholder(placeholder_ty),
381 region,
382 verify_bound,
383 );
384 }
385
386 #[instrument(level = "debug", skip(self))]
387 fn alias_ty_must_outlive(
388 &mut self,
389 origin: infer::SubregionOrigin<'tcx>,
390 region: ty::Region<'tcx>,
391 alias_ty: ty::AliasTy<'tcx>,
392 ) {
393 // An optimization for a common case with opaque types.
394 if alias_ty.args.is_empty() {
395 return;
396 }
397
398 if alias_ty.has_non_region_infer() {
399 self.tcx
400 .dcx()
401 .span_delayed_bug(origin.span(), "an alias has infers during region solving");
402 return;
403 }
404
405 // This case is thorny for inference. The fundamental problem is
406 // that there are many cases where we have choice, and inference
407 // doesn't like choice (the current region inference in
408 // particular). :) First off, we have to choose between using the
409 // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and
410 // OutlivesProjectionComponent rules, any one of which is
411 // sufficient. If there are no inference variables involved, it's
412 // not hard to pick the right rule, but if there are, we're in a
413 // bit of a catch 22: if we picked which rule we were going to
414 // use, we could add constraints to the region inference graph
415 // that make it apply, but if we don't add those constraints, the
416 // rule might not apply (but another rule might). For now, we err
417 // on the side of adding too few edges into the graph.
418
419 // Compute the bounds we can derive from the trait definition.
420 // These are guaranteed to apply, no matter the inference
421 // results.
422 let trait_bounds: Vec<_> =
423 self.verify_bound.declared_bounds_from_definition(alias_ty).collect();
424
425 debug!(?trait_bounds);
426
427 // Compute the bounds we can derive from the environment. This
428 // is an "approximate" match -- in some cases, these bounds
429 // may not apply.
430 let approx_env_bounds = self.verify_bound.approx_declared_bounds_from_env(alias_ty);
431 debug!(?approx_env_bounds);
432
433 // If declared bounds list is empty, the only applicable rule is
434 // OutlivesProjectionComponent. If there are inference variables,
435 // then, we can break down the outlives into more primitive
436 // components without adding unnecessary edges.
437 //
438 // If there are *no* inference variables, however, we COULD do
439 // this, but we choose not to, because the error messages are less
440 // good. For example, a requirement like `T::Item: 'r` would be
441 // translated to a requirement that `T: 'r`; when this is reported
442 // to the user, it will thus say "T: 'r must hold so that T::Item:
443 // 'r holds". But that makes it sound like the only way to fix
444 // the problem is to add `T: 'r`, which isn't true. So, if there are no
445 // inference variables, we use a verify constraint instead of adding
446 // edges, which winds up enforcing the same condition.
447 let kind = alias_ty.kind(self.tcx);
448 if approx_env_bounds.is_empty()
449 && trait_bounds.is_empty()
450 && (alias_ty.has_infer_regions() || kind == ty::Opaque)
451 {
452 debug!("no declared bounds");
453 let opt_variances = self.tcx.opt_alias_variances(kind, alias_ty.def_id);
454 self.args_must_outlive(alias_ty.args, origin, region, opt_variances);
455 return;
456 }
457
458 // If we found a unique bound `'b` from the trait, and we
459 // found nothing else from the environment, then the best
460 // action is to require that `'b: 'r`, so do that.
461 //
462 // This is best no matter what rule we use:
463 //
464 // - OutlivesProjectionEnv: these would translate to the requirement that `'b:'r`
465 // - OutlivesProjectionTraitDef: these would translate to the requirement that `'b:'r`
466 // - OutlivesProjectionComponent: this would require `'b:'r`
467 // in addition to other conditions
468 if !trait_bounds.is_empty()
469 && trait_bounds[1..]
470 .iter()
471 .map(|r| Some(*r))
472 .chain(
473 // NB: The environment may contain `for<'a> T: 'a` style bounds.
474 // In that case, we don't know if they are equal to the trait bound
475 // or not (since we don't *know* whether the environment bound even applies),
476 // so just map to `None` here if there are bound vars, ensuring that
477 // the call to `all` will fail below.
478 approx_env_bounds.iter().map(|b| b.map_bound(|b| b.1).no_bound_vars()),
479 )
480 .all(|b| b == Some(trait_bounds[0]))
481 {
482 let unique_bound = trait_bounds[0];
483 debug!(?unique_bound);
484 debug!("unique declared bound appears in trait ref");
485 let category = origin.to_constraint_category();
486 self.delegate.push_sub_region_constraint(origin, region, unique_bound, category);
487 return;
488 }
489
490 // Fallback to verifying after the fact that there exists a
491 // declared bound, or that all the components appearing in the
492 // projection outlive; in some cases, this may add insufficient
493 // edges into the inference graph, leading to inference failures
494 // even though a satisfactory solution exists.
495 let verify_bound = self.verify_bound.alias_bound(alias_ty);
496 debug!("alias_must_outlive: pushing {:?}", verify_bound);
497 self.delegate.push_verify(origin, GenericKind::Alias(alias_ty), region, verify_bound);
498 }
499
500 #[instrument(level = "debug", skip(self))]
501 fn args_must_outlive(
502 &mut self,
503 args: GenericArgsRef<'tcx>,
504 origin: infer::SubregionOrigin<'tcx>,
505 region: ty::Region<'tcx>,
506 opt_variances: Option<&[ty::Variance]>,
507 ) {
508 let constraint = origin.to_constraint_category();
509 for (index, arg) in args.iter().enumerate() {
510 match arg.kind() {
511 GenericArgKind::Lifetime(lt) => {
512 let variance = if let Some(variances) = opt_variances {
513 variances[index]
514 } else {
515 ty::Invariant
516 };
517 if variance == ty::Invariant {
518 self.delegate.push_sub_region_constraint(
519 origin.clone(),
520 region,
521 lt,
522 constraint,
523 );
524 }
525 }
526 GenericArgKind::Type(ty) => {
527 self.type_must_outlive(origin.clone(), ty, region, constraint);
528 }
529 GenericArgKind::Const(_) => {
530 // Const parameters don't impose constraints.
531 }
532 }
533 }
534 }
535}
536
537impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'tcx> {
538 fn push_sub_region_constraint(
539 &mut self,
540 origin: SubregionOrigin<'tcx>,
541 a: ty::Region<'tcx>,
542 b: ty::Region<'tcx>,
543 _constraint_category: ConstraintCategory<'tcx>,
544 ) {
545 self.sub_regions(origin, a, b)
546 }
547
548 fn push_verify(
549 &mut self,
550 origin: SubregionOrigin<'tcx>,
551 kind: GenericKind<'tcx>,
552 a: ty::Region<'tcx>,
553 bound: VerifyBound<'tcx>,
554 ) {
555 self.verify_generic_bound(origin, kind, a, bound)
556 }
557}