1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Code that handles "type-outlives" constraints like `T: 'a`. This
12 //! is based on the `outlives_components` function defined on the tcx,
13 //! but it adds a bit of heuristics on top, in particular to deal with
14 //! associated types and projections.
16 //! When we process a given `T: 'a` obligation, we may produce two
17 //! kinds of constraints for the region inferencer:
19 //! - Relationships between inference variables and other regions.
20 //! For example, if we have `&'?0 u32: 'a`, then we would produce
21 //! a constraint that `'a <= '?0`.
22 //! - "Verifys" that must be checked after inferencing is done.
23 //! For example, if we know that, for some type parameter `T`,
24 //! `T: 'a + 'b`, and we have a requirement that `T: '?1`,
25 //! then we add a "verify" that checks that `'?1 <= 'a || '?1 <= 'b`.
26 //! - Note the difference with the previous case: here, the region
27 //! variable must be less than something else, so this doesn't
28 //! affect how inference works (it finds the smallest region that
29 //! will do); it's just a post-condition that we have to check.
31 //! **The key point is that once this function is done, we have
32 //! reduced all of our "type-region outlives" obligations into relationships
33 //! between individual regions.**
35 //! One key input to this function is the set of "region-bound pairs".
36 //! These are basically the relationships between type parameters and
37 //! regions that are in scope at the point where the outlives
38 //! obligation was incurred. **When type-checking a function,
39 //! particularly in the face of closures, this is not known until
40 //! regionck runs!** This is because some of those bounds come
41 //! from things we have yet to infer.
46 //! fn bar<T>(a: T, b: impl for<'a> Fn(&'a T));
48 //! bar(x, |y| { ... })
53 //! Here, the type of `y` may involve inference variables and the
54 //! like, and it may also contain implied bounds that are needed to
55 //! type-check the closure body (e.g., here it informs us that `T`
56 //! outlives the late-bound region `'a`).
58 //! Note that by delaying the gathering of implied bounds until all
59 //! inference information is known, we may find relationships between
60 //! bound regions and other regions in the environment. For example,
61 //! when we first check a closure like the one expected as argument
65 //! fn foo<U, F: for<'a> FnMut(&'a U)>(_f: F) {}
68 //! the type of the closure's first argument would be `&'a ?U`. We
69 //! might later infer `?U` to something like `&'b u32`, which would
70 //! imply that `'b: 'a`.
72 use infer::outlives::env::RegionBoundPairs;
73 use infer::outlives::verify::VerifyBoundCx;
74 use infer::{self, GenericKind, InferCtxt, RegionObligation, SubregionOrigin, VerifyBound};
75 use rustc_data_structures::fx::FxHashMap;
77 use traits::ObligationCause;
78 use ty::outlives::Component;
79 use ty::{self, Region, Ty, TyCtxt, TypeFoldable};
81 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
82 /// Registers that the given region obligation must be resolved
83 /// from within the scope of `body_id`. These regions are enqueued
84 /// and later processed by regionck, when full type information is
85 /// available (see `region_obligations` field for more
87 pub fn register_region_obligation(
90 obligation: RegionObligation<'tcx>,
93 "register_region_obligation(body_id={:?}, obligation={:?})",
97 self.region_obligations
99 .push((body_id, obligation));
102 pub fn register_region_obligation_with_cause(
105 sub_region: Region<'tcx>,
106 cause: &ObligationCause<'tcx>,
108 let origin = SubregionOrigin::from_obligation_cause(cause, || {
109 infer::RelateParamBound(cause.span, sup_type)
112 self.register_region_obligation(
122 /// Trait queries just want to pass back type obligations "as is"
123 pub fn take_registered_region_obligations(&self) -> Vec<(ast::NodeId, RegionObligation<'tcx>)> {
124 ::std::mem::replace(&mut *self.region_obligations.borrow_mut(), vec![])
127 /// Process the region obligations that must be proven (during
128 /// `regionck`) for the given `body_id`, given information about
129 /// the region bounds in scope and so forth. This function must be
130 /// invoked for all relevant body-ids before region inference is
131 /// done (or else an assert will fire).
133 /// See the `region_obligations` field of `InferCtxt` for some
134 /// comments about how this function fits into the overall expected
135 /// flow of the the inferencer. The key point is that it is
136 /// invoked after all type-inference variables have been bound --
137 /// towards the end of regionck. This also ensures that the
138 /// region-bound-pairs are available (see comments above regarding
143 /// - `region_bound_pairs`: the set of region bounds implied by
144 /// the parameters and where-clauses. In particular, each pair
145 /// `('a, K)` in this list tells us that the bounds in scope
146 /// indicate that `K: 'a`, where `K` is either a generic
147 /// parameter like `T` or a projection like `T::Item`.
148 /// - `implicit_region_bound`: if some, this is a region bound
149 /// that is considered to hold for all type parameters (the
151 /// - `param_env` is the parameter environment for the enclosing function.
152 /// - `body_id` is the body-id whose region obligations are being
157 /// This function may have to perform normalizations, and hence it
158 /// returns an `InferOk` with subobligations that must be
160 pub fn process_registered_region_obligations(
162 region_bound_pairs_map: &FxHashMap<ast::NodeId, RegionBoundPairs<'tcx>>,
163 implicit_region_bound: Option<ty::Region<'tcx>>,
164 param_env: ty::ParamEnv<'tcx>,
167 !self.in_snapshot.get(),
168 "cannot process registered region obligations in a snapshot"
171 debug!("process_registered_region_obligations()");
173 let my_region_obligations = self.take_registered_region_obligations();
182 ) in my_region_obligations
185 "process_registered_region_obligations: sup_type={:?} sub_region={:?} origin={:?}",
186 sup_type, sub_region, origin
189 let sup_type = self.resolve_type_vars_if_possible(&sup_type);
191 if let Some(region_bound_pairs) = region_bound_pairs_map.get(&body_id) {
192 let outlives = &mut TypeOutlives::new(
196 implicit_region_bound,
199 outlives.type_must_outlive(origin, sup_type, sub_region);
201 self.tcx.sess.delay_span_bug(
203 &format!("no region-bound-pairs for {:?}", body_id),
209 /// Processes a single ad-hoc region obligation that was not
210 /// registered in advance.
211 pub fn type_must_outlive(
213 region_bound_pairs: &RegionBoundPairs<'tcx>,
214 implicit_region_bound: Option<ty::Region<'tcx>>,
215 param_env: ty::ParamEnv<'tcx>,
216 origin: infer::SubregionOrigin<'tcx>,
218 region: ty::Region<'tcx>,
220 let outlives = &mut TypeOutlives::new(
224 implicit_region_bound,
227 let ty = self.resolve_type_vars_if_possible(&ty);
228 outlives.type_must_outlive(origin, ty, region);
232 /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
233 /// obligation into a series of `'a: 'b` constraints and "verifys", as
234 /// described on the module comment. The final constraints are emitted
235 /// via a "delegate" of type `D` -- this is usually the `infcx`, which
236 /// accrues them into the `region_obligations` code, but for NLL we
237 /// use something else.
238 pub struct TypeOutlives<'cx, 'gcx: 'tcx, 'tcx: 'cx, D>
240 D: TypeOutlivesDelegate<'tcx>,
242 // See the comments on `process_registered_region_obligations` for the meaning
245 tcx: TyCtxt<'cx, 'gcx, 'tcx>,
246 verify_bound: VerifyBoundCx<'cx, 'gcx, 'tcx>,
249 pub trait TypeOutlivesDelegate<'tcx> {
250 fn push_sub_region_constraint(
252 origin: SubregionOrigin<'tcx>,
259 origin: SubregionOrigin<'tcx>,
260 kind: GenericKind<'tcx>,
262 bound: VerifyBound<'tcx>,
266 impl<'cx, 'gcx, 'tcx, D> TypeOutlives<'cx, 'gcx, 'tcx, D>
268 D: TypeOutlivesDelegate<'tcx>,
272 tcx: TyCtxt<'cx, 'gcx, 'tcx>,
273 region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
274 implicit_region_bound: Option<ty::Region<'tcx>>,
275 param_env: ty::ParamEnv<'tcx>,
280 verify_bound: VerifyBoundCx::new(
283 implicit_region_bound,
289 /// Adds constraints to inference such that `T: 'a` holds (or
290 /// reports an error if it cannot).
294 /// - `origin`, the reason we need this constraint
295 /// - `ty`, the type `T`
296 /// - `region`, the region `'a`
297 pub fn type_must_outlive(
299 origin: infer::SubregionOrigin<'tcx>,
301 region: ty::Region<'tcx>,
304 "type_must_outlive(ty={:?}, region={:?}, origin={:?})",
308 assert!(!ty.has_escaping_regions());
310 let components = self.tcx.outlives_components(ty);
311 self.components_must_outlive(origin, components, region);
314 fn components_must_outlive(
316 origin: infer::SubregionOrigin<'tcx>,
317 components: Vec<Component<'tcx>>,
318 region: ty::Region<'tcx>,
320 for component in components {
321 let origin = origin.clone();
323 Component::Region(region1) => {
325 .push_sub_region_constraint(origin, region, region1);
327 Component::Param(param_ty) => {
328 self.param_ty_must_outlive(origin, region, param_ty);
330 Component::Projection(projection_ty) => {
331 self.projection_must_outlive(origin, region, projection_ty);
333 Component::EscapingProjection(subcomponents) => {
334 self.components_must_outlive(origin, subcomponents, region);
336 Component::UnresolvedInferenceVariable(v) => {
337 // ignore this, we presume it will yield an error
338 // later, since if a type variable is not resolved by
339 // this point it never will be
340 self.tcx.sess.delay_span_bug(
342 &format!("unresolved inference variable in outlives: {:?}", v),
349 fn param_ty_must_outlive(
351 origin: infer::SubregionOrigin<'tcx>,
352 region: ty::Region<'tcx>,
353 param_ty: ty::ParamTy,
356 "param_ty_must_outlive(region={:?}, param_ty={:?}, origin={:?})",
357 region, param_ty, origin
360 let generic = GenericKind::Param(param_ty);
361 let verify_bound = self.verify_bound.generic_bound(generic);
363 .push_verify(origin, generic, region, verify_bound);
366 fn projection_must_outlive(
368 origin: infer::SubregionOrigin<'tcx>,
369 region: ty::Region<'tcx>,
370 projection_ty: ty::ProjectionTy<'tcx>,
373 "projection_must_outlive(region={:?}, projection_ty={:?}, origin={:?})",
374 region, projection_ty, origin
377 // This case is thorny for inference. The fundamental problem is
378 // that there are many cases where we have choice, and inference
379 // doesn't like choice (the current region inference in
380 // particular). :) First off, we have to choose between using the
381 // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and
382 // OutlivesProjectionComponent rules, any one of which is
383 // sufficient. If there are no inference variables involved, it's
384 // not hard to pick the right rule, but if there are, we're in a
385 // bit of a catch 22: if we picked which rule we were going to
386 // use, we could add constraints to the region inference graph
387 // that make it apply, but if we don't add those constraints, the
388 // rule might not apply (but another rule might). For now, we err
389 // on the side of adding too few edges into the graph.
391 // Compute the bounds we can derive from the environment. This
392 // is an "approximate" match -- in some cases, these bounds
394 let approx_env_bounds = self.verify_bound
395 .projection_approx_declared_bounds_from_env(projection_ty);
397 "projection_must_outlive: approx_env_bounds={:?}",
401 // Compute the bounds we can derive from the trait definition.
402 // These are guaranteed to apply, no matter the inference
404 let trait_bounds: Vec<_> = self.verify_bound
405 .projection_declared_bounds_from_trait(projection_ty)
408 // If declared bounds list is empty, the only applicable rule is
409 // OutlivesProjectionComponent. If there are inference variables,
410 // then, we can break down the outlives into more primitive
411 // components without adding unnecessary edges.
413 // If there are *no* inference variables, however, we COULD do
414 // this, but we choose not to, because the error messages are less
415 // good. For example, a requirement like `T::Item: 'r` would be
416 // translated to a requirement that `T: 'r`; when this is reported
417 // to the user, it will thus say "T: 'r must hold so that T::Item:
418 // 'r holds". But that makes it sound like the only way to fix
419 // the problem is to add `T: 'r`, which isn't true. So, if there are no
420 // inference variables, we use a verify constraint instead of adding
421 // edges, which winds up enforcing the same condition.
422 let needs_infer = projection_ty.needs_infer();
423 if approx_env_bounds.is_empty() && trait_bounds.is_empty() && needs_infer {
424 debug!("projection_must_outlive: no declared bounds");
426 for component_ty in projection_ty.substs.types() {
427 self.type_must_outlive(origin.clone(), component_ty, region);
430 for r in projection_ty.substs.regions() {
432 .push_sub_region_constraint(origin.clone(), region, r);
438 // If we found a unique bound `'b` from the trait, and we
439 // found nothing else from the environment, then the best
440 // action is to require that `'b: 'r`, so do that.
442 // This is best no matter what rule we use:
444 // - OutlivesProjectionEnv: these would translate to the requirement that `'b:'r`
445 // - OutlivesProjectionTraitDef: these would translate to the requirement that `'b:'r`
446 // - OutlivesProjectionComponent: this would require `'b:'r`
447 // in addition to other conditions
448 if !trait_bounds.is_empty()
451 .chain(approx_env_bounds.iter().map(|b| &b.1))
452 .all(|b| *b == trait_bounds[0])
454 let unique_bound = trait_bounds[0];
456 "projection_must_outlive: unique trait bound = {:?}",
459 debug!("projection_must_outlive: unique declared bound appears in trait ref");
461 .push_sub_region_constraint(origin, region, unique_bound);
465 // Fallback to verifying after the fact that there exists a
466 // declared bound, or that all the components appearing in the
467 // projection outlive; in some cases, this may add insufficient
468 // edges into the inference graph, leading to inference failures
469 // even though a satisfactory solution exists.
470 let generic = GenericKind::Projection(projection_ty);
471 let verify_bound = self.verify_bound.generic_bound(generic);
473 .push_verify(origin, generic.clone(), region, verify_bound);
477 impl<'cx, 'gcx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'gcx, 'tcx> {
478 fn push_sub_region_constraint(
480 origin: SubregionOrigin<'tcx>,
484 self.sub_regions(origin, a, b)
489 origin: SubregionOrigin<'tcx>,
490 kind: GenericKind<'tcx>,
492 bound: VerifyBound<'tcx>,
494 self.verify_generic_bound(origin, kind, a, bound)