1 use crate::infer::free_regions::FreeRegionMap;
2 use crate::infer::{GenericKind, InferCtxt};
3 use crate::traits::query::OutlivesBound;
4 use rustc_data_structures::fx::FxIndexSet;
5 use rustc_data_structures::transitive_relation::TransitiveRelationBuilder;
6 use rustc_middle::ty::{self, ReEarlyBound, ReFree, ReVar, Region};
8 use super::explicit_outlives_bounds;
10 /// The `OutlivesEnvironment` collects information about what outlives
11 /// what in a given type-checking setting. For example, if we have a
12 /// where-clause like `where T: 'a` in scope, then the
13 /// `OutlivesEnvironment` would record that (in its
14 /// `region_bound_pairs` field). Similarly, it contains methods for
15 /// processing and adding implied bounds into the outlives
18 /// Other code at present does not typically take a
19 /// `&OutlivesEnvironment`, but rather takes some of its fields (e.g.,
20 /// `process_registered_region_obligations` wants the
21 /// region-bound-pairs). There is no mistaking it: the current setup
22 /// of tracking region information is quite scattered! The
23 /// `OutlivesEnvironment`, for example, needs to sometimes be combined
24 /// with the `middle::RegionRelations`, to yield a full picture of how
25 /// (lexical) lifetimes interact. However, I'm reluctant to do more
26 /// refactoring here, since the setup with NLL is quite different.
27 /// For example, NLL has no need of `RegionRelations`, and is solely
28 /// interested in the `OutlivesEnvironment`. -nmatsakis
30 pub struct OutlivesEnvironment<'tcx> {
31 pub param_env: ty::ParamEnv<'tcx>,
32 free_region_map: FreeRegionMap<'tcx>,
34 // Contains the implied region bounds in scope for our current body.
39 // fn foo<'a, 'b, T>(x: &'a T, y: &'b ()) {
40 // bar(x, y, |y: &'b T| { .. } // body B1)
44 // Here, when checking the body B0, the list would be `[T: 'a]`, because we
45 // infer that `T` must outlive `'a` from the implied bounds on the
48 // For the body B1 however, the list would be `[T: 'a, T: 'b]`, because we
49 // also can see that -- within the closure body! -- `T` must
50 // outlive `'b`. This is not necessarily true outside the closure
51 // body, since the closure may never be called.
52 region_bound_pairs: RegionBoundPairs<'tcx>,
55 /// Builder of OutlivesEnvironment.
56 struct OutlivesEnvironmentBuilder<'tcx> {
57 param_env: ty::ParamEnv<'tcx>,
58 region_relation: TransitiveRelationBuilder<Region<'tcx>>,
59 region_bound_pairs: RegionBoundPairs<'tcx>,
62 /// "Region-bound pairs" tracks outlives relations that are known to
63 /// be true, either because of explicit where-clauses like `T: 'a` or
64 /// because of implied bounds.
65 pub type RegionBoundPairs<'tcx> =
66 FxIndexSet<ty::OutlivesPredicate<GenericKind<'tcx>, Region<'tcx>>>;
68 impl<'tcx> OutlivesEnvironment<'tcx> {
69 /// Create a builder using `ParamEnv` and add explicit outlives bounds into it.
70 fn builder(param_env: ty::ParamEnv<'tcx>) -> OutlivesEnvironmentBuilder<'tcx> {
71 let mut builder = OutlivesEnvironmentBuilder {
73 region_relation: Default::default(),
74 region_bound_pairs: Default::default(),
77 builder.add_outlives_bounds(None, explicit_outlives_bounds(param_env));
83 /// Create a new `OutlivesEnvironment` without extra outlives bounds.
84 pub fn new(param_env: ty::ParamEnv<'tcx>) -> Self {
85 Self::builder(param_env).build()
88 /// Create a new `OutlivesEnvironment` with extra outlives bounds.
89 pub fn with_bounds<'a>(
90 param_env: ty::ParamEnv<'tcx>,
91 infcx: Option<&InferCtxt<'a, 'tcx>>,
92 extra_bounds: impl IntoIterator<Item = OutlivesBound<'tcx>>,
94 let mut builder = Self::builder(param_env);
95 builder.add_outlives_bounds(infcx, extra_bounds);
99 /// Borrows current value of the `free_region_map`.
100 pub fn free_region_map(&self) -> &FreeRegionMap<'tcx> {
101 &self.free_region_map
104 /// Borrows current `region_bound_pairs`.
105 pub fn region_bound_pairs(&self) -> &RegionBoundPairs<'tcx> {
106 &self.region_bound_pairs
110 impl<'a, 'tcx> OutlivesEnvironmentBuilder<'tcx> {
112 pub fn build(self) -> OutlivesEnvironment<'tcx> {
113 OutlivesEnvironment {
114 param_env: self.param_env,
115 free_region_map: FreeRegionMap { relation: self.region_relation.freeze() },
116 region_bound_pairs: self.region_bound_pairs,
120 /// Processes outlives bounds that are known to hold, whether from implied or other sources.
122 /// The `infcx` parameter is optional; if the implied bounds may
123 /// contain inference variables, it must be supplied, in which
124 /// case we will register "givens" on the inference context. (See
125 /// `RegionConstraintData`.)
126 fn add_outlives_bounds<I>(&mut self, infcx: Option<&InferCtxt<'a, 'tcx>>, outlives_bounds: I)
128 I: IntoIterator<Item = OutlivesBound<'tcx>>,
130 // Record relationships such as `T:'x` that don't go into the
131 // free-region-map but which we use here.
132 for outlives_bound in outlives_bounds {
133 debug!("add_outlives_bounds: outlives_bound={:?}", outlives_bound);
134 match outlives_bound {
135 OutlivesBound::RegionSubParam(r_a, param_b) => {
136 self.region_bound_pairs
137 .insert(ty::OutlivesPredicate(GenericKind::Param(param_b), r_a));
139 OutlivesBound::RegionSubProjection(r_a, projection_b) => {
140 self.region_bound_pairs
141 .insert(ty::OutlivesPredicate(GenericKind::Projection(projection_b), r_a));
143 OutlivesBound::RegionSubRegion(r_a, r_b) => {
144 if let (ReEarlyBound(_) | ReFree(_), ReVar(vid_b)) = (r_a.kind(), r_b.kind()) {
146 .expect("no infcx provided but region vars found")
147 .add_given(r_a, vid_b);
149 // In principle, we could record (and take
150 // advantage of) every relationship here, but
151 // we are also free not to -- it simply means
152 // strictly less that we can successfully type
153 // check. Right now we only look for things
154 // relationships between free regions. (It may
155 // also be that we should revise our inference
156 // system to be more general and to make use
157 // of *every* relationship that arises here,
158 // but presently we do not.)
159 if r_a.is_free_or_static() && r_b.is_free() {
160 self.region_relation.add(r_a, r_b)