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.
6 //! When we process a given `T: 'a` obligation, we may produce two
7 //! kinds of constraints for the region inferencer:
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.
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.**
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.
36 //! fn bar<T>(a: T, b: impl for<'a> Fn(&'a T)) {}
38 //! bar(x, |y| { /* ... */})
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`).
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
55 //! fn foo<U, F: for<'a> FnMut(&'a U)>(_f: F) {}
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`.
62 use crate::infer::outlives::components::{push_outlives_components, Component};
63 use crate::infer::outlives::env::RegionBoundPairs;
64 use crate::infer::outlives::verify::VerifyBoundCx;
66 self, GenericKind, InferCtxt, RegionObligation, SubregionOrigin, UndoLog, VerifyBound,
68 use crate::traits::{ObligationCause, ObligationCauseCode};
69 use rustc_middle::ty::subst::GenericArgKind;
70 use rustc_middle::ty::{self, Region, Ty, TyCtxt, TypeFoldable};
72 use rustc_data_structures::fx::FxHashMap;
73 use rustc_data_structures::undo_log::UndoLogs;
75 use smallvec::smallvec;
77 impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
78 /// Registers that the given region obligation must be resolved
79 /// from within the scope of `body_id`. These regions are enqueued
80 /// and later processed by regionck, when full type information is
81 /// available (see `region_obligations` field for more
83 pub fn register_region_obligation(
86 obligation: RegionObligation<'tcx>,
88 debug!("register_region_obligation(body_id={:?}, obligation={:?})", body_id, obligation);
90 let mut inner = self.inner.borrow_mut();
91 inner.undo_log.push(UndoLog::PushRegionObligation);
92 inner.region_obligations.push((body_id, obligation));
95 pub fn register_region_obligation_with_cause(
98 sub_region: Region<'tcx>,
99 cause: &ObligationCause<'tcx>,
101 let origin = SubregionOrigin::from_obligation_cause(cause, || {
102 infer::RelateParamBound(
105 match cause.code().peel_derives() {
106 ObligationCauseCode::BindingObligation(_, span) => Some(*span),
112 self.register_region_obligation(
114 RegionObligation { sup_type, sub_region, origin },
118 /// Trait queries just want to pass back type obligations "as is"
119 pub fn take_registered_region_obligations(&self) -> Vec<(hir::HirId, RegionObligation<'tcx>)> {
120 std::mem::take(&mut self.inner.borrow_mut().region_obligations)
123 /// Process the region obligations that must be proven (during
124 /// `regionck`) for the given `body_id`, given information about
125 /// the region bounds in scope and so forth. This function must be
126 /// invoked for all relevant body-ids before region inference is
127 /// done (or else an assert will fire).
129 /// See the `region_obligations` field of `InferCtxt` for some
130 /// comments about how this function fits into the overall expected
131 /// flow of the inferencer. The key point is that it is
132 /// invoked after all type-inference variables have been bound --
133 /// towards the end of regionck. This also ensures that the
134 /// region-bound-pairs are available (see comments above regarding
139 /// - `region_bound_pairs`: the set of region bounds implied by
140 /// the parameters and where-clauses. In particular, each pair
141 /// `('a, K)` in this list tells us that the bounds in scope
142 /// indicate that `K: 'a`, where `K` is either a generic
143 /// parameter like `T` or a projection like `T::Item`.
144 /// - `implicit_region_bound`: if some, this is a region bound
145 /// that is considered to hold for all type parameters (the
147 /// - `param_env` is the parameter environment for the enclosing function.
148 /// - `body_id` is the body-id whose region obligations are being
153 /// This function may have to perform normalizations, and hence it
154 /// returns an `InferOk` with subobligations that must be
156 #[instrument(level = "debug", skip(self, region_bound_pairs_map))]
157 pub fn process_registered_region_obligations(
159 region_bound_pairs_map: &FxHashMap<hir::HirId, RegionBoundPairs<'tcx>>,
160 implicit_region_bound: Option<ty::Region<'tcx>>,
161 param_env: ty::ParamEnv<'tcx>,
164 !self.in_snapshot.get(),
165 "cannot process registered region obligations in a snapshot"
168 let my_region_obligations = self.take_registered_region_obligations();
170 for (body_id, RegionObligation { sup_type, sub_region, origin }) in my_region_obligations {
172 "process_registered_region_obligations: sup_type={:?} sub_region={:?} origin={:?}",
173 sup_type, sub_region, origin
176 let sup_type = self.resolve_vars_if_possible(sup_type);
178 if let Some(region_bound_pairs) = region_bound_pairs_map.get(&body_id) {
179 let outlives = &mut TypeOutlives::new(
183 implicit_region_bound,
186 outlives.type_must_outlive(origin, sup_type, sub_region);
188 self.tcx.sess.delay_span_bug(
190 &format!("no region-bound-pairs for {:?}", body_id),
197 /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
198 /// obligation into a series of `'a: 'b` constraints and "verify"s, as
199 /// described on the module comment. The final constraints are emitted
200 /// via a "delegate" of type `D` -- this is usually the `infcx`, which
201 /// accrues them into the `region_obligations` code, but for NLL we
202 /// use something else.
203 pub struct TypeOutlives<'cx, 'tcx, D>
205 D: TypeOutlivesDelegate<'tcx>,
207 // See the comments on `process_registered_region_obligations` for the meaning
211 verify_bound: VerifyBoundCx<'cx, 'tcx>,
214 pub trait TypeOutlivesDelegate<'tcx> {
215 fn push_sub_region_constraint(
217 origin: SubregionOrigin<'tcx>,
224 origin: SubregionOrigin<'tcx>,
225 kind: GenericKind<'tcx>,
227 bound: VerifyBound<'tcx>,
231 impl<'cx, 'tcx, D> TypeOutlives<'cx, 'tcx, D>
233 D: TypeOutlivesDelegate<'tcx>,
238 region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
239 implicit_region_bound: Option<ty::Region<'tcx>>,
240 param_env: ty::ParamEnv<'tcx>,
245 verify_bound: VerifyBoundCx::new(
248 implicit_region_bound,
254 /// Adds constraints to inference such that `T: 'a` holds (or
255 /// reports an error if it cannot).
259 /// - `origin`, the reason we need this constraint
260 /// - `ty`, the type `T`
261 /// - `region`, the region `'a`
262 pub fn type_must_outlive(
264 origin: infer::SubregionOrigin<'tcx>,
266 region: ty::Region<'tcx>,
268 debug!("type_must_outlive(ty={:?}, region={:?}, origin={:?})", ty, region, origin);
270 assert!(!ty.has_escaping_bound_vars());
272 let mut components = smallvec![];
273 push_outlives_components(self.tcx, ty, &mut components);
274 self.components_must_outlive(origin, &components, region);
277 fn components_must_outlive(
279 origin: infer::SubregionOrigin<'tcx>,
280 components: &[Component<'tcx>],
281 region: ty::Region<'tcx>,
283 for component in components.iter() {
284 let origin = origin.clone();
286 Component::Region(region1) => {
287 self.delegate.push_sub_region_constraint(origin, region, *region1);
289 Component::Param(param_ty) => {
290 self.param_ty_must_outlive(origin, region, *param_ty);
292 Component::Projection(projection_ty) => {
293 self.projection_must_outlive(origin, region, *projection_ty);
295 Component::EscapingProjection(subcomponents) => {
296 self.components_must_outlive(origin, &subcomponents, region);
298 Component::UnresolvedInferenceVariable(v) => {
299 // ignore this, we presume it will yield an error
300 // later, since if a type variable is not resolved by
301 // this point it never will be
302 self.tcx.sess.delay_span_bug(
304 &format!("unresolved inference variable in outlives: {:?}", v),
311 fn param_ty_must_outlive(
313 origin: infer::SubregionOrigin<'tcx>,
314 region: ty::Region<'tcx>,
315 param_ty: ty::ParamTy,
318 "param_ty_must_outlive(region={:?}, param_ty={:?}, origin={:?})",
319 region, param_ty, origin
322 let generic = GenericKind::Param(param_ty);
323 let verify_bound = self.verify_bound.generic_bound(generic);
324 self.delegate.push_verify(origin, generic, region, verify_bound);
327 fn projection_must_outlive(
329 origin: infer::SubregionOrigin<'tcx>,
330 region: ty::Region<'tcx>,
331 projection_ty: ty::ProjectionTy<'tcx>,
334 "projection_must_outlive(region={:?}, projection_ty={:?}, origin={:?})",
335 region, projection_ty, origin
338 // This case is thorny for inference. The fundamental problem is
339 // that there are many cases where we have choice, and inference
340 // doesn't like choice (the current region inference in
341 // particular). :) First off, we have to choose between using the
342 // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and
343 // OutlivesProjectionComponent rules, any one of which is
344 // sufficient. If there are no inference variables involved, it's
345 // not hard to pick the right rule, but if there are, we're in a
346 // bit of a catch 22: if we picked which rule we were going to
347 // use, we could add constraints to the region inference graph
348 // that make it apply, but if we don't add those constraints, the
349 // rule might not apply (but another rule might). For now, we err
350 // on the side of adding too few edges into the graph.
352 // Compute the bounds we can derive from the trait definition.
353 // These are guaranteed to apply, no matter the inference
355 let trait_bounds: Vec<_> =
356 self.verify_bound.projection_declared_bounds_from_trait(projection_ty).collect();
358 debug!(?trait_bounds);
360 // Compute the bounds we can derive from the environment. This
361 // is an "approximate" match -- in some cases, these bounds
363 let mut approx_env_bounds =
364 self.verify_bound.projection_approx_declared_bounds_from_env(projection_ty);
365 debug!("projection_must_outlive: approx_env_bounds={:?}", approx_env_bounds);
367 // Remove outlives bounds that we get from the environment but
368 // which are also deducible from the trait. This arises (cc
369 // #55756) in cases where you have e.g., `<T as Foo<'a>>::Item:
370 // 'a` in the environment but `trait Foo<'b> { type Item: 'b
371 // }` in the trait definition.
372 approx_env_bounds.retain(|bound| match *bound.0.kind() {
373 ty::Projection(projection_ty) => self
375 .projection_declared_bounds_from_trait(projection_ty)
376 .all(|r| r != bound.1),
378 _ => panic!("expected only projection types from env, not {:?}", bound.0),
381 // If declared bounds list is empty, the only applicable rule is
382 // OutlivesProjectionComponent. If there are inference variables,
383 // then, we can break down the outlives into more primitive
384 // components without adding unnecessary edges.
386 // If there are *no* inference variables, however, we COULD do
387 // this, but we choose not to, because the error messages are less
388 // good. For example, a requirement like `T::Item: 'r` would be
389 // translated to a requirement that `T: 'r`; when this is reported
390 // to the user, it will thus say "T: 'r must hold so that T::Item:
391 // 'r holds". But that makes it sound like the only way to fix
392 // the problem is to add `T: 'r`, which isn't true. So, if there are no
393 // inference variables, we use a verify constraint instead of adding
394 // edges, which winds up enforcing the same condition.
395 let needs_infer = projection_ty.needs_infer();
396 if approx_env_bounds.is_empty() && trait_bounds.is_empty() && needs_infer {
397 debug!("projection_must_outlive: no declared bounds");
399 for k in projection_ty.substs {
401 GenericArgKind::Lifetime(lt) => {
402 self.delegate.push_sub_region_constraint(origin.clone(), region, lt);
404 GenericArgKind::Type(ty) => {
405 self.type_must_outlive(origin.clone(), ty, region);
407 GenericArgKind::Const(_) => {
408 // Const parameters don't impose constraints.
416 // If we found a unique bound `'b` from the trait, and we
417 // found nothing else from the environment, then the best
418 // action is to require that `'b: 'r`, so do that.
420 // This is best no matter what rule we use:
422 // - OutlivesProjectionEnv: these would translate to the requirement that `'b:'r`
423 // - OutlivesProjectionTraitDef: these would translate to the requirement that `'b:'r`
424 // - OutlivesProjectionComponent: this would require `'b:'r`
425 // in addition to other conditions
426 if !trait_bounds.is_empty()
429 .chain(approx_env_bounds.iter().map(|b| &b.1))
430 .all(|b| *b == trait_bounds[0])
432 let unique_bound = trait_bounds[0];
433 debug!("projection_must_outlive: unique trait bound = {:?}", unique_bound);
434 debug!("projection_must_outlive: unique declared bound appears in trait ref");
435 self.delegate.push_sub_region_constraint(origin, region, unique_bound);
439 // Fallback to verifying after the fact that there exists a
440 // declared bound, or that all the components appearing in the
441 // projection outlive; in some cases, this may add insufficient
442 // edges into the inference graph, leading to inference failures
443 // even though a satisfactory solution exists.
444 let generic = GenericKind::Projection(projection_ty);
445 let verify_bound = self.verify_bound.generic_bound(generic);
446 self.delegate.push_verify(origin, generic, region, verify_bound);
450 impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'tcx> {
451 fn push_sub_region_constraint(
453 origin: SubregionOrigin<'tcx>,
457 self.sub_regions(origin, a, b)
462 origin: SubregionOrigin<'tcx>,
463 kind: GenericKind<'tcx>,
465 bound: VerifyBound<'tcx>,
467 self.verify_generic_bound(origin, kind, a, bound)