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}