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}