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 pub fn process_registered_region_obligations(
158 region_bound_pairs_map: &FxHashMap<hir::HirId, RegionBoundPairs<'tcx>>,
159 implicit_region_bound: Option<ty::Region<'tcx>>,
160 param_env: ty::ParamEnv<'tcx>,
163 !self.in_snapshot.get(),
164 "cannot process registered region obligations in a snapshot"
167 debug!(?param_env, "process_registered_region_obligations()");
169 let my_region_obligations = self.take_registered_region_obligations();
171 for (body_id, RegionObligation { sup_type, sub_region, origin }) in my_region_obligations {
173 "process_registered_region_obligations: sup_type={:?} sub_region={:?} origin={:?}",
174 sup_type, sub_region, origin
177 let sup_type = self.resolve_vars_if_possible(sup_type);
179 if let Some(region_bound_pairs) = region_bound_pairs_map.get(&body_id) {
180 let outlives = &mut TypeOutlives::new(
184 implicit_region_bound,
187 outlives.type_must_outlive(origin, sup_type, sub_region);
189 self.tcx.sess.delay_span_bug(
191 &format!("no region-bound-pairs for {:?}", body_id),
198 /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
199 /// obligation into a series of `'a: 'b` constraints and "verify"s, as
200 /// described on the module comment. The final constraints are emitted
201 /// via a "delegate" of type `D` -- this is usually the `infcx`, which
202 /// accrues them into the `region_obligations` code, but for NLL we
203 /// use something else.
204 pub struct TypeOutlives<'cx, 'tcx, D>
206 D: TypeOutlivesDelegate<'tcx>,
208 // See the comments on `process_registered_region_obligations` for the meaning
212 verify_bound: VerifyBoundCx<'cx, 'tcx>,
215 pub trait TypeOutlivesDelegate<'tcx> {
216 fn push_sub_region_constraint(
218 origin: SubregionOrigin<'tcx>,
225 origin: SubregionOrigin<'tcx>,
226 kind: GenericKind<'tcx>,
228 bound: VerifyBound<'tcx>,
232 impl<'cx, 'tcx, D> TypeOutlives<'cx, 'tcx, D>
234 D: TypeOutlivesDelegate<'tcx>,
239 region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
240 implicit_region_bound: Option<ty::Region<'tcx>>,
241 param_env: ty::ParamEnv<'tcx>,
246 verify_bound: VerifyBoundCx::new(
249 implicit_region_bound,
255 /// Adds constraints to inference such that `T: 'a` holds (or
256 /// reports an error if it cannot).
260 /// - `origin`, the reason we need this constraint
261 /// - `ty`, the type `T`
262 /// - `region`, the region `'a`
263 pub fn type_must_outlive(
265 origin: infer::SubregionOrigin<'tcx>,
267 region: ty::Region<'tcx>,
269 debug!("type_must_outlive(ty={:?}, region={:?}, origin={:?})", ty, region, origin);
271 assert!(!ty.has_escaping_bound_vars());
273 let mut components = smallvec![];
274 push_outlives_components(self.tcx, ty, &mut components);
275 self.components_must_outlive(origin, &components, region);
278 fn components_must_outlive(
280 origin: infer::SubregionOrigin<'tcx>,
281 components: &[Component<'tcx>],
282 region: ty::Region<'tcx>,
284 for component in components.iter() {
285 let origin = origin.clone();
287 Component::Region(region1) => {
288 self.delegate.push_sub_region_constraint(origin, region, *region1);
290 Component::Param(param_ty) => {
291 self.param_ty_must_outlive(origin, region, *param_ty);
293 Component::Projection(projection_ty) => {
294 self.projection_must_outlive(origin, region, *projection_ty);
296 Component::EscapingProjection(subcomponents) => {
297 self.components_must_outlive(origin, &subcomponents, region);
299 Component::UnresolvedInferenceVariable(v) => {
300 // ignore this, we presume it will yield an error
301 // later, since if a type variable is not resolved by
302 // this point it never will be
303 self.tcx.sess.delay_span_bug(
305 &format!("unresolved inference variable in outlives: {:?}", v),
312 fn param_ty_must_outlive(
314 origin: infer::SubregionOrigin<'tcx>,
315 region: ty::Region<'tcx>,
316 param_ty: ty::ParamTy,
319 "param_ty_must_outlive(region={:?}, param_ty={:?}, origin={:?})",
320 region, param_ty, origin
323 let generic = GenericKind::Param(param_ty);
324 let verify_bound = self.verify_bound.generic_bound(generic);
325 self.delegate.push_verify(origin, generic, region, verify_bound);
328 fn projection_must_outlive(
330 origin: infer::SubregionOrigin<'tcx>,
331 region: ty::Region<'tcx>,
332 projection_ty: ty::ProjectionTy<'tcx>,
335 "projection_must_outlive(region={:?}, projection_ty={:?}, origin={:?})",
336 region, projection_ty, origin
339 // This case is thorny for inference. The fundamental problem is
340 // that there are many cases where we have choice, and inference
341 // doesn't like choice (the current region inference in
342 // particular). :) First off, we have to choose between using the
343 // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and
344 // OutlivesProjectionComponent rules, any one of which is
345 // sufficient. If there are no inference variables involved, it's
346 // not hard to pick the right rule, but if there are, we're in a
347 // bit of a catch 22: if we picked which rule we were going to
348 // use, we could add constraints to the region inference graph
349 // that make it apply, but if we don't add those constraints, the
350 // rule might not apply (but another rule might). For now, we err
351 // on the side of adding too few edges into the graph.
353 // Compute the bounds we can derive from the trait definition.
354 // These are guaranteed to apply, no matter the inference
356 let trait_bounds: Vec<_> =
357 self.verify_bound.projection_declared_bounds_from_trait(projection_ty).collect();
359 debug!(?trait_bounds);
361 // Compute the bounds we can derive from the environment. This
362 // is an "approximate" match -- in some cases, these bounds
364 let mut approx_env_bounds =
365 self.verify_bound.projection_approx_declared_bounds_from_env(projection_ty);
366 debug!("projection_must_outlive: approx_env_bounds={:?}", approx_env_bounds);
368 // Remove outlives bounds that we get from the environment but
369 // which are also deducable from the trait. This arises (cc
370 // #55756) in cases where you have e.g., `<T as Foo<'a>>::Item:
371 // 'a` in the environment but `trait Foo<'b> { type Item: 'b
372 // }` in the trait definition.
373 approx_env_bounds.retain(|bound| match *bound.0.kind() {
374 ty::Projection(projection_ty) => self
376 .projection_declared_bounds_from_trait(projection_ty)
377 .all(|r| r != bound.1),
379 _ => panic!("expected only projection types from env, not {:?}", bound.0),
382 // If declared bounds list is empty, the only applicable rule is
383 // OutlivesProjectionComponent. If there are inference variables,
384 // then, we can break down the outlives into more primitive
385 // components without adding unnecessary edges.
387 // If there are *no* inference variables, however, we COULD do
388 // this, but we choose not to, because the error messages are less
389 // good. For example, a requirement like `T::Item: 'r` would be
390 // translated to a requirement that `T: 'r`; when this is reported
391 // to the user, it will thus say "T: 'r must hold so that T::Item:
392 // 'r holds". But that makes it sound like the only way to fix
393 // the problem is to add `T: 'r`, which isn't true. So, if there are no
394 // inference variables, we use a verify constraint instead of adding
395 // edges, which winds up enforcing the same condition.
396 let needs_infer = projection_ty.needs_infer();
397 if approx_env_bounds.is_empty() && trait_bounds.is_empty() && needs_infer {
398 debug!("projection_must_outlive: no declared bounds");
400 for k in projection_ty.substs {
402 GenericArgKind::Lifetime(lt) => {
403 self.delegate.push_sub_region_constraint(origin.clone(), region, lt);
405 GenericArgKind::Type(ty) => {
406 self.type_must_outlive(origin.clone(), ty, region);
408 GenericArgKind::Const(_) => {
409 // Const parameters don't impose constraints.
417 // If we found a unique bound `'b` from the trait, and we
418 // found nothing else from the environment, then the best
419 // action is to require that `'b: 'r`, so do that.
421 // This is best no matter what rule we use:
423 // - OutlivesProjectionEnv: these would translate to the requirement that `'b:'r`
424 // - OutlivesProjectionTraitDef: these would translate to the requirement that `'b:'r`
425 // - OutlivesProjectionComponent: this would require `'b:'r`
426 // in addition to other conditions
427 if !trait_bounds.is_empty()
430 .chain(approx_env_bounds.iter().map(|b| &b.1))
431 .all(|b| *b == trait_bounds[0])
433 let unique_bound = trait_bounds[0];
434 debug!("projection_must_outlive: unique trait bound = {:?}", unique_bound);
435 debug!("projection_must_outlive: unique declared bound appears in trait ref");
436 self.delegate.push_sub_region_constraint(origin, region, unique_bound);
440 // Fallback to verifying after the fact that there exists a
441 // declared bound, or that all the components appearing in the
442 // projection outlive; in some cases, this may add insufficient
443 // edges into the inference graph, leading to inference failures
444 // even though a satisfactory solution exists.
445 let generic = GenericKind::Projection(projection_ty);
446 let verify_bound = self.verify_bound.generic_bound(generic);
447 self.delegate.push_verify(origin, generic, region, verify_bound);
451 impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'tcx> {
452 fn push_sub_region_constraint(
454 origin: SubregionOrigin<'tcx>,
458 self.sub_regions(origin, a, b)
463 origin: SubregionOrigin<'tcx>,
464 kind: GenericKind<'tcx>,
466 bound: VerifyBound<'tcx>,
468 self.verify_generic_bound(origin, kind, a, bound)