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::{self, GenericKind, InferCtxt, RegionObligation, SubregionOrigin, VerifyBound};
80use crate::traits::{ObligationCause, ObligationCauseCode};
81
82impl<'tcx> InferCtxt<'tcx> {
83 /// Registers that the given region obligation must be resolved
84 /// from within the scope of `body_id`. These regions are enqueued
85 /// and later processed by regionck, when full type information is
86 /// available (see `region_obligations` field for more
87 /// information).
88 #[instrument(level = "debug", skip(self))]
89 pub fn register_region_obligation(&self, obligation: RegionObligation<'tcx>) {
90 let mut inner = self.inner.borrow_mut();
91 inner.undo_log.push(UndoLog::PushRegionObligation);
92 inner.region_obligations.push(obligation);
93 }
94
95 pub fn register_region_obligation_with_cause(
96 &self,
97 sup_type: Ty<'tcx>,
98 sub_region: Region<'tcx>,
99 cause: &ObligationCause<'tcx>,
100 ) {
101 // `is_global` means the type has no params, infer, placeholder, or non-`'static`
102 // free regions. If the type has none of these things, then we can skip registering
103 // this outlives obligation since it has no components which affect lifetime
104 // checking in an interesting way.
105 if sup_type.is_global() {
106 return;
107 }
108
109 debug!(?sup_type, ?sub_region, ?cause);
110 let origin = SubregionOrigin::from_obligation_cause(cause, || {
111 infer::RelateParamBound(
112 cause.span,
113 sup_type,
114 match cause.code().peel_derives() {
115 ObligationCauseCode::WhereClause(_, span)
116 | ObligationCauseCode::WhereClauseInExpr(_, span, ..)
117 | ObligationCauseCode::OpaqueTypeBound(span, _)
118 if !span.is_dummy() =>
119 {
120 Some(*span)
121 }
122 _ => None,
123 },
124 )
125 });
126
127 self.register_region_obligation(RegionObligation { sup_type, sub_region, origin });
128 }
129
130 /// Trait queries just want to pass back type obligations "as is"
131 pub fn take_registered_region_obligations(&self) -> Vec<RegionObligation<'tcx>> {
132 std::mem::take(&mut self.inner.borrow_mut().region_obligations)
133 }
134
135 /// Process the region obligations that must be proven (during
136 /// `regionck`) for the given `body_id`, given information about
137 /// the region bounds in scope and so forth.
138 ///
139 /// See the `region_obligations` field of `InferCtxt` for some
140 /// comments about how this function fits into the overall expected
141 /// flow of the inferencer. The key point is that it is
142 /// invoked after all type-inference variables have been bound --
143 /// right before lexical region resolution.
144 #[instrument(level = "debug", skip(self, outlives_env, deeply_normalize_ty))]
145 pub fn process_registered_region_obligations(
146 &self,
147 outlives_env: &OutlivesEnvironment<'tcx>,
148 mut deeply_normalize_ty: impl FnMut(
149 PolyTypeOutlivesPredicate<'tcx>,
150 SubregionOrigin<'tcx>,
151 )
152 -> Result<PolyTypeOutlivesPredicate<'tcx>, NoSolution>,
153 ) -> Result<(), (PolyTypeOutlivesPredicate<'tcx>, SubregionOrigin<'tcx>)> {
154 assert!(!self.in_snapshot(), "cannot process registered region obligations in a snapshot");
155
156 // Must loop since the process of normalizing may itself register region obligations.
157 for iteration in 0.. {
158 let my_region_obligations = self.take_registered_region_obligations();
159 if my_region_obligations.is_empty() {
160 break;
161 }
162
163 if !self.tcx.recursion_limit().value_within_limit(iteration) {
164 bug!(
165 "FIXME(-Znext-solver): Overflowed when processing region obligations: {my_region_obligations:#?}"
166 );
167 }
168
169 for RegionObligation { sup_type, sub_region, origin } in my_region_obligations {
170 let outlives = ty::Binder::dummy(ty::OutlivesPredicate(sup_type, sub_region));
171 let ty::OutlivesPredicate(sup_type, sub_region) =
172 deeply_normalize_ty(outlives, origin.clone())
173 .map_err(|NoSolution| (outlives, origin.clone()))?
174 .no_bound_vars()
175 .expect("started with no bound vars, should end with no bound vars");
176 // `TypeOutlives` is structural, so we should try to opportunistically resolve all
177 // region vids before processing regions, so we have a better chance to match clauses
178 // in our param-env.
179 let (sup_type, sub_region) =
180 (sup_type, sub_region).fold_with(&mut OpportunisticRegionResolver::new(self));
181
182 debug!(?sup_type, ?sub_region, ?origin);
183
184 let outlives = &mut TypeOutlives::new(
185 self,
186 self.tcx,
187 outlives_env.region_bound_pairs(),
188 None,
189 outlives_env.known_type_outlives(),
190 );
191 let category = origin.to_constraint_category();
192 outlives.type_must_outlive(origin, sup_type, sub_region, category);
193 }
194 }
195
196 Ok(())
197 }
198}
199
200/// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
201/// obligation into a series of `'a: 'b` constraints and "verify"s, as
202/// described on the module comment. The final constraints are emitted
203/// via a "delegate" of type `D` -- this is usually the `infcx`, which
204/// accrues them into the `region_obligations` code, but for NLL we
205/// use something else.
206pub struct TypeOutlives<'cx, 'tcx, D>
207where
208 D: TypeOutlivesDelegate<'tcx>,
209{
210 // See the comments on `process_registered_region_obligations` for the meaning
211 // of these fields.
212 delegate: D,
213 tcx: TyCtxt<'tcx>,
214 verify_bound: VerifyBoundCx<'cx, 'tcx>,
215}
216
217pub trait TypeOutlivesDelegate<'tcx> {
218 fn push_sub_region_constraint(
219 &mut self,
220 origin: SubregionOrigin<'tcx>,
221 a: ty::Region<'tcx>,
222 b: ty::Region<'tcx>,
223 constraint_category: ConstraintCategory<'tcx>,
224 );
225
226 fn push_verify(
227 &mut self,
228 origin: SubregionOrigin<'tcx>,
229 kind: GenericKind<'tcx>,
230 a: ty::Region<'tcx>,
231 bound: VerifyBound<'tcx>,
232 );
233}
234
235impl<'cx, 'tcx, D> TypeOutlives<'cx, 'tcx, D>
236where
237 D: TypeOutlivesDelegate<'tcx>,
238{
239 pub fn new(
240 delegate: D,
241 tcx: TyCtxt<'tcx>,
242 region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
243 implicit_region_bound: Option<ty::Region<'tcx>>,
244 caller_bounds: &'cx [ty::PolyTypeOutlivesPredicate<'tcx>],
245 ) -> Self {
246 Self {
247 delegate,
248 tcx,
249 verify_bound: VerifyBoundCx::new(
250 tcx,
251 region_bound_pairs,
252 implicit_region_bound,
253 caller_bounds,
254 ),
255 }
256 }
257
258 /// Adds constraints to inference such that `T: 'a` holds (or
259 /// reports an error if it cannot).
260 ///
261 /// # Parameters
262 ///
263 /// - `origin`, the reason we need this constraint
264 /// - `ty`, the type `T`
265 /// - `region`, the region `'a`
266 #[instrument(level = "debug", skip(self))]
267 pub fn type_must_outlive(
268 &mut self,
269 origin: infer::SubregionOrigin<'tcx>,
270 ty: Ty<'tcx>,
271 region: ty::Region<'tcx>,
272 category: ConstraintCategory<'tcx>,
273 ) {
274 assert!(!ty.has_escaping_bound_vars());
275
276 let mut components = smallvec![];
277 push_outlives_components(self.tcx, ty, &mut components);
278 self.components_must_outlive(origin, &components, region, category);
279 }
280
281 fn components_must_outlive(
282 &mut self,
283 origin: infer::SubregionOrigin<'tcx>,
284 components: &[Component<TyCtxt<'tcx>>],
285 region: ty::Region<'tcx>,
286 category: ConstraintCategory<'tcx>,
287 ) {
288 for component in components.iter() {
289 let origin = origin.clone();
290 match component {
291 Component::Region(region1) => {
292 self.delegate.push_sub_region_constraint(origin, region, *region1, category);
293 }
294 Component::Param(param_ty) => {
295 self.param_ty_must_outlive(origin, region, *param_ty);
296 }
297 Component::Placeholder(placeholder_ty) => {
298 self.placeholder_ty_must_outlive(origin, region, *placeholder_ty);
299 }
300 Component::Alias(alias_ty) => self.alias_ty_must_outlive(origin, region, *alias_ty),
301 Component::EscapingAlias(subcomponents) => {
302 self.components_must_outlive(origin, subcomponents, region, category);
303 }
304 Component::UnresolvedInferenceVariable(v) => {
305 // Ignore this, we presume it will yield an error later,
306 // since if a type variable is not resolved by this point
307 // it never will be.
308 self.tcx.dcx().span_delayed_bug(
309 origin.span(),
310 format!("unresolved inference variable in outlives: {v:?}"),
311 );
312 }
313 }
314 }
315 }
316
317 #[instrument(level = "debug", skip(self))]
318 fn param_ty_must_outlive(
319 &mut self,
320 origin: infer::SubregionOrigin<'tcx>,
321 region: ty::Region<'tcx>,
322 param_ty: ty::ParamTy,
323 ) {
324 let verify_bound = self.verify_bound.param_or_placeholder_bound(param_ty.to_ty(self.tcx));
325 self.delegate.push_verify(origin, GenericKind::Param(param_ty), region, verify_bound);
326 }
327
328 #[instrument(level = "debug", skip(self))]
329 fn placeholder_ty_must_outlive(
330 &mut self,
331 origin: infer::SubregionOrigin<'tcx>,
332 region: ty::Region<'tcx>,
333 placeholder_ty: ty::PlaceholderType,
334 ) {
335 let verify_bound = self
336 .verify_bound
337 .param_or_placeholder_bound(Ty::new_placeholder(self.tcx, placeholder_ty));
338 self.delegate.push_verify(
339 origin,
340 GenericKind::Placeholder(placeholder_ty),
341 region,
342 verify_bound,
343 );
344 }
345
346 #[instrument(level = "debug", skip(self))]
347 fn alias_ty_must_outlive(
348 &mut self,
349 origin: infer::SubregionOrigin<'tcx>,
350 region: ty::Region<'tcx>,
351 alias_ty: ty::AliasTy<'tcx>,
352 ) {
353 // An optimization for a common case with opaque types.
354 if alias_ty.args.is_empty() {
355 return;
356 }
357
358 if alias_ty.has_non_region_infer() {
359 self.tcx
360 .dcx()
361 .span_delayed_bug(origin.span(), "an alias has infers during region solving");
362 return;
363 }
364
365 // This case is thorny for inference. The fundamental problem is
366 // that there are many cases where we have choice, and inference
367 // doesn't like choice (the current region inference in
368 // particular). :) First off, we have to choose between using the
369 // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and
370 // OutlivesProjectionComponent rules, any one of which is
371 // sufficient. If there are no inference variables involved, it's
372 // not hard to pick the right rule, but if there are, we're in a
373 // bit of a catch 22: if we picked which rule we were going to
374 // use, we could add constraints to the region inference graph
375 // that make it apply, but if we don't add those constraints, the
376 // rule might not apply (but another rule might). For now, we err
377 // on the side of adding too few edges into the graph.
378
379 // Compute the bounds we can derive from the trait definition.
380 // These are guaranteed to apply, no matter the inference
381 // results.
382 let trait_bounds: Vec<_> =
383 self.verify_bound.declared_bounds_from_definition(alias_ty).collect();
384
385 debug!(?trait_bounds);
386
387 // Compute the bounds we can derive from the environment. This
388 // is an "approximate" match -- in some cases, these bounds
389 // may not apply.
390 let approx_env_bounds = self.verify_bound.approx_declared_bounds_from_env(alias_ty);
391 debug!(?approx_env_bounds);
392
393 // If declared bounds list is empty, the only applicable rule is
394 // OutlivesProjectionComponent. If there are inference variables,
395 // then, we can break down the outlives into more primitive
396 // components without adding unnecessary edges.
397 //
398 // If there are *no* inference variables, however, we COULD do
399 // this, but we choose not to, because the error messages are less
400 // good. For example, a requirement like `T::Item: 'r` would be
401 // translated to a requirement that `T: 'r`; when this is reported
402 // to the user, it will thus say "T: 'r must hold so that T::Item:
403 // 'r holds". But that makes it sound like the only way to fix
404 // the problem is to add `T: 'r`, which isn't true. So, if there are no
405 // inference variables, we use a verify constraint instead of adding
406 // edges, which winds up enforcing the same condition.
407 let kind = alias_ty.kind(self.tcx);
408 if approx_env_bounds.is_empty()
409 && trait_bounds.is_empty()
410 && (alias_ty.has_infer_regions() || kind == ty::Opaque)
411 {
412 debug!("no declared bounds");
413 let opt_variances = self.tcx.opt_alias_variances(kind, alias_ty.def_id);
414 self.args_must_outlive(alias_ty.args, origin, region, opt_variances);
415 return;
416 }
417
418 // If we found a unique bound `'b` from the trait, and we
419 // found nothing else from the environment, then the best
420 // action is to require that `'b: 'r`, so do that.
421 //
422 // This is best no matter what rule we use:
423 //
424 // - OutlivesProjectionEnv: these would translate to the requirement that `'b:'r`
425 // - OutlivesProjectionTraitDef: these would translate to the requirement that `'b:'r`
426 // - OutlivesProjectionComponent: this would require `'b:'r`
427 // in addition to other conditions
428 if !trait_bounds.is_empty()
429 && trait_bounds[1..]
430 .iter()
431 .map(|r| Some(*r))
432 .chain(
433 // NB: The environment may contain `for<'a> T: 'a` style bounds.
434 // In that case, we don't know if they are equal to the trait bound
435 // or not (since we don't *know* whether the environment bound even applies),
436 // so just map to `None` here if there are bound vars, ensuring that
437 // the call to `all` will fail below.
438 approx_env_bounds.iter().map(|b| b.map_bound(|b| b.1).no_bound_vars()),
439 )
440 .all(|b| b == Some(trait_bounds[0]))
441 {
442 let unique_bound = trait_bounds[0];
443 debug!(?unique_bound);
444 debug!("unique declared bound appears in trait ref");
445 let category = origin.to_constraint_category();
446 self.delegate.push_sub_region_constraint(origin, region, unique_bound, category);
447 return;
448 }
449
450 // Fallback to verifying after the fact that there exists a
451 // declared bound, or that all the components appearing in the
452 // projection outlive; in some cases, this may add insufficient
453 // edges into the inference graph, leading to inference failures
454 // even though a satisfactory solution exists.
455 let verify_bound = self.verify_bound.alias_bound(alias_ty);
456 debug!("alias_must_outlive: pushing {:?}", verify_bound);
457 self.delegate.push_verify(origin, GenericKind::Alias(alias_ty), region, verify_bound);
458 }
459
460 #[instrument(level = "debug", skip(self))]
461 fn args_must_outlive(
462 &mut self,
463 args: GenericArgsRef<'tcx>,
464 origin: infer::SubregionOrigin<'tcx>,
465 region: ty::Region<'tcx>,
466 opt_variances: Option<&[ty::Variance]>,
467 ) {
468 let constraint = origin.to_constraint_category();
469 for (index, k) in args.iter().enumerate() {
470 match k.unpack() {
471 GenericArgKind::Lifetime(lt) => {
472 let variance = if let Some(variances) = opt_variances {
473 variances[index]
474 } else {
475 ty::Invariant
476 };
477 if variance == ty::Invariant {
478 self.delegate.push_sub_region_constraint(
479 origin.clone(),
480 region,
481 lt,
482 constraint,
483 );
484 }
485 }
486 GenericArgKind::Type(ty) => {
487 self.type_must_outlive(origin.clone(), ty, region, constraint);
488 }
489 GenericArgKind::Const(_) => {
490 // Const parameters don't impose constraints.
491 }
492 }
493 }
494 }
495}
496
497impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'tcx> {
498 fn push_sub_region_constraint(
499 &mut self,
500 origin: SubregionOrigin<'tcx>,
501 a: ty::Region<'tcx>,
502 b: ty::Region<'tcx>,
503 _constraint_category: ConstraintCategory<'tcx>,
504 ) {
505 self.sub_regions(origin, a, b)
506 }
507
508 fn push_verify(
509 &mut self,
510 origin: SubregionOrigin<'tcx>,
511 kind: GenericKind<'tcx>,
512 a: ty::Region<'tcx>,
513 bound: VerifyBound<'tcx>,
514 ) {
515 self.verify_generic_bound(origin, kind, a, bound)
516 }
517}