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 hir::def_id::DefId;
73 use infer::{self, GenericKind, InferCtxt, RegionObligation, SubregionOrigin, VerifyBound};
76 use ty::outlives::Component;
77 use ty::subst::{Subst, Substs};
78 use ty::{self, Ty, TyCtxt, TypeFoldable};
80 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
81 /// Registers that the given region obligation must be resolved
82 /// from within the scope of `body_id`. These regions are enqueued
83 /// and later processed by regionck, when full type information is
84 /// available (see `region_obligations` field for more
86 pub fn register_region_obligation(
89 obligation: RegionObligation<'tcx>,
92 "register_region_obligation(body_id={:?}, obligation={:?})",
96 self.region_obligations
98 .push((body_id, obligation));
101 /// Trait queries just want to pass back type obligations "as is"
102 pub fn take_registered_region_obligations(&self) -> Vec<(ast::NodeId, RegionObligation<'tcx>)> {
103 ::std::mem::replace(&mut *self.region_obligations.borrow_mut(), vec![])
106 /// Process the region obligations that must be proven (during
107 /// `regionck`) for the given `body_id`, given information about
108 /// the region bounds in scope and so forth. This function must be
109 /// invoked for all relevant body-ids before region inference is
110 /// done (or else an assert will fire).
112 /// See the `region_obligations` field of `InferCtxt` for some
113 /// comments about how this function fits into the overall expected
114 /// flow of the the inferencer. The key point is that it is
115 /// invoked after all type-inference variables have been bound --
116 /// towards the end of regionck. This also ensures that the
117 /// region-bound-pairs are available (see comments above regarding
122 /// - `region_bound_pairs`: the set of region bounds implied by
123 /// the parameters and where-clauses. In particular, each pair
124 /// `('a, K)` in this list tells us that the bounds in scope
125 /// indicate that `K: 'a`, where `K` is either a generic
126 /// parameter like `T` or a projection like `T::Item`.
127 /// - `implicit_region_bound`: if some, this is a region bound
128 /// that is considered to hold for all type parameters (the
130 /// - `param_env` is the parameter environment for the enclosing function.
131 /// - `body_id` is the body-id whose region obligations are being
136 /// This function may have to perform normalizations, and hence it
137 /// returns an `InferOk` with subobligations that must be
139 pub fn process_registered_region_obligations(
141 region_bound_pairs: &[(ty::Region<'tcx>, GenericKind<'tcx>)],
142 implicit_region_bound: Option<ty::Region<'tcx>>,
143 param_env: ty::ParamEnv<'tcx>,
144 body_id: ast::NodeId,
147 !self.in_snapshot.get(),
148 "cannot process registered region obligations in a snapshot"
151 debug!("process_registered_region_obligations()");
153 // pull out the region obligations with the given `body_id` (leaving the rest)
154 let mut my_region_obligations = Vec::with_capacity(self.region_obligations.borrow().len());
156 let mut r_o = self.region_obligations.borrow_mut();
157 for (_, obligation) in r_o.drain_filter(|(ro_body_id, _)| *ro_body_id == body_id) {
158 my_region_obligations.push(obligation);
162 let outlives = &mut TypeOutlives::new(
166 implicit_region_bound,
170 for RegionObligation {
174 } in my_region_obligations
177 "process_registered_region_obligations: sup_type={:?} sub_region={:?} cause={:?}",
178 sup_type, sub_region, cause
181 let origin = SubregionOrigin::from_obligation_cause(&cause, || {
182 infer::RelateParamBound(cause.span, sup_type)
185 let sup_type = self.resolve_type_vars_if_possible(&sup_type);
186 outlives.type_must_outlive(origin, sup_type, sub_region);
190 /// Processes a single ad-hoc region obligation that was not
191 /// registered in advance.
192 pub fn type_must_outlive(
194 region_bound_pairs: &[(ty::Region<'tcx>, GenericKind<'tcx>)],
195 implicit_region_bound: Option<ty::Region<'tcx>>,
196 param_env: ty::ParamEnv<'tcx>,
197 origin: infer::SubregionOrigin<'tcx>,
199 region: ty::Region<'tcx>,
201 let outlives = &mut TypeOutlives::new(
205 implicit_region_bound,
208 let ty = self.resolve_type_vars_if_possible(&ty);
209 outlives.type_must_outlive(origin, ty, region);
213 /// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
214 /// obligation into a series of `'a: 'b` constraints and "verifys", as
215 /// described on the module comment. The final constraints are emitted
216 /// via a "delegate" of type `D` -- this is usually the `infcx`, which
217 /// accrues them into the `region_obligations` code, but for NLL we
218 /// use something else.
219 pub struct TypeOutlives<'cx, 'gcx: 'tcx, 'tcx: 'cx, D>
221 D: TypeOutlivesDelegate<'tcx>,
223 // See the comments on `process_registered_region_obligations` for the meaning
226 tcx: TyCtxt<'cx, 'gcx, 'tcx>,
227 region_bound_pairs: &'cx [(ty::Region<'tcx>, GenericKind<'tcx>)],
228 implicit_region_bound: Option<ty::Region<'tcx>>,
229 param_env: ty::ParamEnv<'tcx>,
232 pub trait TypeOutlivesDelegate<'tcx> {
233 fn push_sub_region_constraint(
235 origin: SubregionOrigin<'tcx>,
242 origin: SubregionOrigin<'tcx>,
243 kind: GenericKind<'tcx>,
245 bound: VerifyBound<'tcx>,
249 impl<'cx, 'gcx, 'tcx, D> TypeOutlives<'cx, 'gcx, 'tcx, D>
251 D: TypeOutlivesDelegate<'tcx>,
255 tcx: TyCtxt<'cx, 'gcx, 'tcx>,
256 region_bound_pairs: &'cx [(ty::Region<'tcx>, GenericKind<'tcx>)],
257 implicit_region_bound: Option<ty::Region<'tcx>>,
258 param_env: ty::ParamEnv<'tcx>,
264 implicit_region_bound,
269 /// Adds constraints to inference such that `T: 'a` holds (or
270 /// reports an error if it cannot).
274 /// - `origin`, the reason we need this constraint
275 /// - `ty`, the type `T`
276 /// - `region`, the region `'a`
277 pub fn type_must_outlive(
279 origin: infer::SubregionOrigin<'tcx>,
281 region: ty::Region<'tcx>,
284 "type_must_outlive(ty={:?}, region={:?}, origin={:?})",
288 assert!(!ty.has_escaping_regions());
290 let components = self.tcx.outlives_components(ty);
291 self.components_must_outlive(origin, components, region);
294 fn components_must_outlive(
296 origin: infer::SubregionOrigin<'tcx>,
297 components: Vec<Component<'tcx>>,
298 region: ty::Region<'tcx>,
300 for component in components {
301 let origin = origin.clone();
303 Component::Region(region1) => {
304 self.delegate.push_sub_region_constraint(origin, region, region1);
306 Component::Param(param_ty) => {
307 self.param_ty_must_outlive(origin, region, param_ty);
309 Component::Projection(projection_ty) => {
310 self.projection_must_outlive(origin, region, projection_ty);
312 Component::EscapingProjection(subcomponents) => {
313 self.components_must_outlive(origin, subcomponents, region);
315 Component::UnresolvedInferenceVariable(v) => {
316 // ignore this, we presume it will yield an error
317 // later, since if a type variable is not resolved by
318 // this point it never will be
319 self.tcx.sess.delay_span_bug(
321 &format!("unresolved inference variable in outlives: {:?}", v),
328 fn param_ty_must_outlive(
330 origin: infer::SubregionOrigin<'tcx>,
331 region: ty::Region<'tcx>,
332 param_ty: ty::ParamTy,
335 "param_ty_must_outlive(region={:?}, param_ty={:?}, origin={:?})",
336 region, param_ty, origin
339 let verify_bound = self.param_bound(param_ty);
340 let generic = GenericKind::Param(param_ty);
342 .push_verify(origin, generic, region, verify_bound);
345 fn projection_must_outlive(
347 origin: infer::SubregionOrigin<'tcx>,
348 region: ty::Region<'tcx>,
349 projection_ty: ty::ProjectionTy<'tcx>,
352 "projection_must_outlive(region={:?}, projection_ty={:?}, origin={:?})",
353 region, projection_ty, origin
356 // This case is thorny for inference. The fundamental problem is
357 // that there are many cases where we have choice, and inference
358 // doesn't like choice (the current region inference in
359 // particular). :) First off, we have to choose between using the
360 // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and
361 // OutlivesProjectionComponent rules, any one of which is
362 // sufficient. If there are no inference variables involved, it's
363 // not hard to pick the right rule, but if there are, we're in a
364 // bit of a catch 22: if we picked which rule we were going to
365 // use, we could add constraints to the region inference graph
366 // that make it apply, but if we don't add those constraints, the
367 // rule might not apply (but another rule might). For now, we err
368 // on the side of adding too few edges into the graph.
370 // Compute the bounds we can derive from the environment or trait
371 // definition. We know that the projection outlives all the
372 // regions in this list.
373 let env_bounds = self.projection_declared_bounds(projection_ty);
375 debug!("projection_must_outlive: env_bounds={:?}", env_bounds);
377 // If we know that the projection outlives 'static, then we're
379 if env_bounds.contains(&&ty::ReStatic) {
380 debug!("projection_must_outlive: 'static as declared bound");
384 // If declared bounds list is empty, the only applicable rule is
385 // OutlivesProjectionComponent. If there are inference variables,
386 // then, we can break down the outlives into more primitive
387 // components without adding unnecessary edges.
389 // If there are *no* inference variables, however, we COULD do
390 // this, but we choose not to, because the error messages are less
391 // good. For example, a requirement like `T::Item: 'r` would be
392 // translated to a requirement that `T: 'r`; when this is reported
393 // to the user, it will thus say "T: 'r must hold so that T::Item:
394 // 'r holds". But that makes it sound like the only way to fix
395 // the problem is to add `T: 'r`, which isn't true. So, if there are no
396 // inference variables, we use a verify constraint instead of adding
397 // edges, which winds up enforcing the same condition.
398 let needs_infer = projection_ty.needs_infer();
399 if env_bounds.is_empty() && needs_infer {
400 debug!("projection_must_outlive: no declared bounds");
402 for component_ty in projection_ty.substs.types() {
403 self.type_must_outlive(origin.clone(), component_ty, region);
406 for r in projection_ty.substs.regions() {
407 self.delegate.push_sub_region_constraint(origin.clone(), region, r);
413 // If we find that there is a unique declared bound `'b`, and this bound
414 // appears in the trait reference, then the best action is to require that `'b:'r`,
415 // so do that. This is best no matter what rule we use:
417 // - OutlivesProjectionEnv or OutlivesProjectionTraitDef: these would translate to
418 // the requirement that `'b:'r`
419 // - OutlivesProjectionComponent: this would require `'b:'r` in addition to
421 if !env_bounds.is_empty() && env_bounds[1..].iter().all(|b| *b == env_bounds[0]) {
422 let unique_bound = env_bounds[0];
424 "projection_must_outlive: unique declared bound = {:?}",
430 .any(|r| env_bounds.contains(&r))
432 debug!("projection_must_outlive: unique declared bound appears in trait ref");
434 .push_sub_region_constraint(origin.clone(), 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 verify_bound = self.projection_bound(env_bounds, projection_ty);
445 let generic = GenericKind::Projection(projection_ty);
447 .push_verify(origin, generic.clone(), region, verify_bound);
450 fn type_bound(&self, ty: Ty<'tcx>) -> VerifyBound<'tcx> {
452 ty::TyParam(p) => self.param_bound(p),
453 ty::TyProjection(data) => {
454 let declared_bounds = self.projection_declared_bounds(data);
455 self.projection_bound(declared_bounds, data)
457 _ => self.recursive_type_bound(ty),
461 fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> {
462 debug!("param_bound(param_ty={:?})", param_ty);
464 let mut param_bounds = self.declared_generic_bounds_from_env(GenericKind::Param(param_ty));
466 // Add in the default bound of fn body that applies to all in
467 // scope type parameters:
468 param_bounds.extend(self.implicit_region_bound);
470 VerifyBound::AnyRegion(param_bounds)
473 fn projection_declared_bounds(
475 projection_ty: ty::ProjectionTy<'tcx>,
476 ) -> Vec<ty::Region<'tcx>> {
477 // First assemble bounds from where clauses and traits.
479 let mut declared_bounds =
480 self.declared_generic_bounds_from_env(GenericKind::Projection(projection_ty));
483 .extend_from_slice(&self.declared_projection_bounds_from_trait(projection_ty));
490 declared_bounds: Vec<ty::Region<'tcx>>,
491 projection_ty: ty::ProjectionTy<'tcx>,
492 ) -> VerifyBound<'tcx> {
494 "projection_bound(declared_bounds={:?}, projection_ty={:?})",
495 declared_bounds, projection_ty
498 // see the extensive comment in projection_must_outlive
501 .mk_projection(projection_ty.item_def_id, projection_ty.substs);
502 let recursive_bound = self.recursive_type_bound(ty);
504 VerifyBound::AnyRegion(declared_bounds).or(recursive_bound)
507 fn recursive_type_bound(&self, ty: Ty<'tcx>) -> VerifyBound<'tcx> {
508 let mut bounds = vec![];
510 for subty in ty.walk_shallow() {
511 bounds.push(self.type_bound(subty));
514 let mut regions = ty.regions();
515 regions.retain(|r| !r.is_late_bound()); // ignore late-bound regions
516 bounds.push(VerifyBound::AllRegions(regions));
518 // remove bounds that must hold, since they are not interesting
519 bounds.retain(|b| !b.must_hold());
521 if bounds.len() == 1 {
522 bounds.pop().unwrap()
524 VerifyBound::AllBounds(bounds)
528 fn declared_generic_bounds_from_env(
530 generic: GenericKind<'tcx>,
531 ) -> Vec<ty::Region<'tcx>> {
534 // To start, collect bounds from user environment. Note that
535 // parameter environments are already elaborated, so we don't
536 // have to worry about that. Comparing using `==` is a bit
537 // dubious for projections, but it will work for simple cases
538 // like `T` and `T::Item`. It may not work as well for things
539 // like `<T as Foo<'a>>::Item`.
540 let generic_ty = generic.to_ty(tcx);
541 let c_b = self.param_env.caller_bounds;
542 let mut param_bounds = self.collect_outlives_from_predicate_list(generic_ty, c_b);
544 // Next, collect regions we scraped from the well-formedness
545 // constraints in the fn signature. To do that, we walk the list
546 // of known relations from the fn ctxt.
548 // This is crucial because otherwise code like this fails:
550 // fn foo<'a, A>(x: &'a A) { x.bar() }
552 // The problem is that the type of `x` is `&'a A`. To be
553 // well-formed, then, A must be lower-generic by `'a`, but we
554 // don't know that this holds from first principles.
555 for &(r, p) in self.region_bound_pairs {
556 debug!("generic={:?} p={:?}", generic, p);
558 param_bounds.push(r);
565 /// Given a projection like `<T as Foo<'x>>::Bar`, returns any bounds
566 /// declared in the trait definition. For example, if the trait were
574 /// then this function would return `'x`. This is subject to the
575 /// limitations around higher-ranked bounds described in
576 /// `region_bounds_declared_on_associated_item`.
577 fn declared_projection_bounds_from_trait(
579 projection_ty: ty::ProjectionTy<'tcx>,
580 ) -> Vec<ty::Region<'tcx>> {
581 debug!("projection_bounds(projection_ty={:?})", projection_ty);
582 let mut bounds = self.region_bounds_declared_on_associated_item(projection_ty.item_def_id);
583 for r in &mut bounds {
584 *r = r.subst(self.tcx, projection_ty.substs);
589 /// Given the def-id of an associated item, returns any region
590 /// bounds attached to that associated item from the trait definition.
600 /// If we were given the def-id of `Foo::Bar`, we would return
601 /// `'a`. You could then apply the substitutions from the
602 /// projection to convert this into your namespace. This also
603 /// works if the user writes `where <Self as Foo<'a>>::Bar: 'a` on
604 /// the trait. In fact, it works by searching for just such a
607 /// It will not, however, work for higher-ranked bounds like:
610 /// trait Foo<'a, 'b>
611 /// where for<'x> <Self as Foo<'x, 'b>>::Bar: 'x
617 /// This is for simplicity, and because we are not really smart
618 /// enough to cope with such bounds anywhere.
619 fn region_bounds_declared_on_associated_item(
621 assoc_item_def_id: DefId,
622 ) -> Vec<ty::Region<'tcx>> {
624 let assoc_item = tcx.associated_item(assoc_item_def_id);
625 let trait_def_id = assoc_item.container.assert_trait();
626 let trait_predicates = tcx.predicates_of(trait_def_id);
627 let identity_substs = Substs::identity_for_item(tcx, assoc_item_def_id);
628 let identity_proj = tcx.mk_projection(assoc_item_def_id, identity_substs);
629 self.collect_outlives_from_predicate_list(
631 traits::elaborate_predicates(tcx, trait_predicates.predicates),
635 /// Searches through a predicate list for a predicate `T: 'a`.
637 /// Careful: does not elaborate predicates, and just uses `==`
638 /// when comparing `ty` for equality, so `ty` must be something
639 /// that does not involve inference variables and where you
640 /// otherwise want a precise match.
641 fn collect_outlives_from_predicate_list<I, P>(
645 ) -> Vec<ty::Region<'tcx>>
647 I: IntoIterator<Item = P>,
648 P: AsRef<ty::Predicate<'tcx>>,
652 .filter_map(|p| p.as_ref().to_opt_type_outlives())
653 .filter_map(|p| p.no_late_bound_regions())
654 .filter(|p| p.0 == ty)
660 impl<'cx, 'gcx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'gcx, 'tcx> {
661 fn push_sub_region_constraint(
663 origin: SubregionOrigin<'tcx>,
667 self.sub_regions(origin, a, b)
672 origin: SubregionOrigin<'tcx>,
673 kind: GenericKind<'tcx>,
675 bound: VerifyBound<'tcx>,
677 self.verify_generic_bound(origin, kind, a, bound)