1 use rustc_data_structures::frozen::Frozen;
2 use rustc_data_structures::transitive_relation::{TransitiveRelation, TransitiveRelationBuilder};
3 use rustc_infer::infer::canonical::QueryRegionConstraints;
4 use rustc_infer::infer::outlives;
5 use rustc_infer::infer::outlives::env::RegionBoundPairs;
6 use rustc_infer::infer::region_constraints::GenericKind;
7 use rustc_infer::infer::InferCtxt;
8 use rustc_middle::mir::ConstraintCategory;
9 use rustc_middle::traits::query::OutlivesBound;
10 use rustc_middle::ty::{self, RegionVid, Ty};
11 use rustc_trait_selection::traits::query::type_op::{self, TypeOp};
13 use type_op::TypeOpOutput;
16 type_check::constraint_conversion,
17 type_check::{Locations, MirTypeckRegionConstraints},
18 universal_regions::UniversalRegions,
22 pub(crate) struct UniversalRegionRelations<'tcx> {
23 universal_regions: Rc<UniversalRegions<'tcx>>,
25 /// Stores the outlives relations that are known to hold from the
26 /// implied bounds, in-scope where-clauses, and that sort of
28 outlives: TransitiveRelation<RegionVid>,
30 /// This is the `<=` relation; that is, if `a: b`, then `b <= a`,
31 /// and we store that here. This is useful when figuring out how
32 /// to express some local region in terms of external regions our
33 /// caller will understand.
34 inverse_outlives: TransitiveRelation<RegionVid>,
37 /// As part of computing the free region relations, we also have to
38 /// normalize the input-output types, which we then need later. So we
39 /// return those. This vector consists of first the input types and
40 /// then the output type as the last element.
41 type NormalizedInputsAndOutput<'tcx> = Vec<Ty<'tcx>>;
43 pub(crate) struct CreateResult<'tcx> {
44 pub(crate) universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>,
45 pub(crate) region_bound_pairs: RegionBoundPairs<'tcx>,
46 pub(crate) normalized_inputs_and_output: NormalizedInputsAndOutput<'tcx>,
49 pub(crate) fn create<'tcx>(
50 infcx: &InferCtxt<'tcx>,
51 param_env: ty::ParamEnv<'tcx>,
52 implicit_region_bound: ty::Region<'tcx>,
53 universal_regions: &Rc<UniversalRegions<'tcx>>,
54 constraints: &mut MirTypeckRegionConstraints<'tcx>,
55 ) -> CreateResult<'tcx> {
56 UniversalRegionRelationsBuilder {
59 implicit_region_bound,
61 universal_regions: universal_regions.clone(),
62 region_bound_pairs: Default::default(),
63 outlives: Default::default(),
64 inverse_outlives: Default::default(),
69 impl UniversalRegionRelations<'_> {
70 /// Given two universal regions, returns the postdominating
71 /// upper-bound (effectively the least upper bound).
73 /// (See `TransitiveRelation::postdom_upper_bound` for details on
74 /// the postdominating upper bound in general.)
75 pub(crate) fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid {
76 assert!(self.universal_regions.is_universal_region(fr1));
77 assert!(self.universal_regions.is_universal_region(fr2));
79 .postdom_upper_bound(fr1, fr2)
80 .unwrap_or(self.universal_regions.fr_static)
83 /// Finds an "upper bound" for `fr` that is not local. In other
84 /// words, returns the smallest (*) known region `fr1` that (a)
85 /// outlives `fr` and (b) is not local.
87 /// (*) If there are multiple competing choices, we return all of them.
88 pub(crate) fn non_local_upper_bounds(&self, fr: RegionVid) -> Vec<RegionVid> {
89 debug!("non_local_upper_bound(fr={:?})", fr);
90 let res = self.non_local_bounds(&self.inverse_outlives, fr);
91 assert!(!res.is_empty(), "can't find an upper bound!?");
95 /// Returns the "postdominating" bound of the set of
96 /// `non_local_upper_bounds` for the given region.
97 pub(crate) fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid {
98 let upper_bounds = self.non_local_upper_bounds(fr);
100 // In case we find more than one, reduce to one for
101 // convenience. This is to prevent us from generating more
102 // complex constraints, but it will cause spurious errors.
103 let post_dom = self.inverse_outlives.mutual_immediate_postdominator(upper_bounds);
105 debug!("non_local_bound: post_dom={:?}", post_dom);
108 .and_then(|post_dom| {
109 // If the mutual immediate postdom is not local, then
110 // there is no non-local result we can return.
111 if !self.universal_regions.is_local_free_region(post_dom) {
117 .unwrap_or(self.universal_regions.fr_static)
120 /// Finds a "lower bound" for `fr` that is not local. In other
121 /// words, returns the largest (*) known region `fr1` that (a) is
122 /// outlived by `fr` and (b) is not local.
124 /// (*) If there are multiple competing choices, we pick the "postdominating"
125 /// one. See `TransitiveRelation::postdom_upper_bound` for details.
126 pub(crate) fn non_local_lower_bound(&self, fr: RegionVid) -> Option<RegionVid> {
127 debug!("non_local_lower_bound(fr={:?})", fr);
128 let lower_bounds = self.non_local_bounds(&self.outlives, fr);
130 // In case we find more than one, reduce to one for
131 // convenience. This is to prevent us from generating more
132 // complex constraints, but it will cause spurious errors.
133 let post_dom = self.outlives.mutual_immediate_postdominator(lower_bounds);
135 debug!("non_local_bound: post_dom={:?}", post_dom);
137 post_dom.and_then(|post_dom| {
138 // If the mutual immediate postdom is not local, then
139 // there is no non-local result we can return.
140 if !self.universal_regions.is_local_free_region(post_dom) {
148 /// Helper for `non_local_upper_bounds` and `non_local_lower_bounds`.
149 /// Repeatedly invokes `postdom_parent` until we find something that is not
150 /// local. Returns `None` if we never do so.
153 relation: &TransitiveRelation<RegionVid>,
155 ) -> Vec<RegionVid> {
156 // This method assumes that `fr0` is one of the universally
157 // quantified region variables.
158 assert!(self.universal_regions.is_universal_region(fr0));
160 let mut external_parents = vec![];
161 let mut queue = vec![fr0];
163 // Keep expanding `fr` into its parents until we reach
164 // non-local regions.
165 while let Some(fr) = queue.pop() {
166 if !self.universal_regions.is_local_free_region(fr) {
167 external_parents.push(fr);
171 queue.extend(relation.parents(fr));
174 debug!("non_local_bound: external_parents={:?}", external_parents);
179 /// Returns `true` if fr1 is known to outlive fr2.
181 /// This will only ever be true for universally quantified regions.
182 pub(crate) fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
183 self.outlives.contains(fr1, fr2)
186 /// Returns a vector of free regions `x` such that `fr1: x` is
188 pub(crate) fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<RegionVid> {
189 self.outlives.reachable_from(fr1)
192 /// Returns the _non-transitive_ set of known `outlives` constraints between free regions.
193 pub(crate) fn known_outlives(&self) -> impl Iterator<Item = (RegionVid, RegionVid)> + '_ {
194 self.outlives.base_edges()
198 struct UniversalRegionRelationsBuilder<'this, 'tcx> {
199 infcx: &'this InferCtxt<'tcx>,
200 param_env: ty::ParamEnv<'tcx>,
201 universal_regions: Rc<UniversalRegions<'tcx>>,
202 implicit_region_bound: ty::Region<'tcx>,
203 constraints: &'this mut MirTypeckRegionConstraints<'tcx>,
206 outlives: TransitiveRelationBuilder<RegionVid>,
207 inverse_outlives: TransitiveRelationBuilder<RegionVid>,
208 region_bound_pairs: RegionBoundPairs<'tcx>,
211 impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> {
212 /// Records in the `outlives_relation` (and
213 /// `inverse_outlives_relation`) that `fr_a: fr_b`.
214 fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) {
215 debug!("relate_universal_regions: fr_a={:?} outlives fr_b={:?}", fr_a, fr_b);
216 self.outlives.add(fr_a, fr_b);
217 self.inverse_outlives.add(fr_b, fr_a);
220 pub(crate) fn create(mut self) -> CreateResult<'tcx> {
221 let span = self.infcx.tcx.def_span(self.universal_regions.defining_ty.def_id());
222 let unnormalized_input_output_tys = self
224 .unnormalized_input_tys
227 .chain(Some(self.universal_regions.unnormalized_output_ty));
229 // For each of the input/output types:
230 // - Normalize the type. This will create some region
231 // constraints, which we buffer up because we are
232 // not ready to process them yet.
233 // - Then compute the implied bounds. This will adjust
234 // the `region_bound_pairs` and so forth.
235 // - After this is done, we'll process the constraints, once
236 // the `relations` is built.
237 let mut normalized_inputs_and_output =
238 Vec::with_capacity(self.universal_regions.unnormalized_input_tys.len() + 1);
239 let constraint_sets: Vec<_> = unnormalized_input_output_tys
241 debug!("build: input_or_output={:?}", ty);
242 // We add implied bounds from both the unnormalized and normalized ty.
244 let constraints_implied1 = self.add_implied_bounds(ty);
245 let TypeOpOutput { output: norm_ty, constraints: constraints1, .. } = self
247 .and(type_op::normalize::Normalize::new(ty))
248 .fully_perform(self.infcx)
249 .unwrap_or_else(|_| {
254 .delay_span_bug(span, &format!("failed to normalize {:?}", ty));
256 output: self.infcx.tcx.ty_error_with_guaranteed(reported),
261 // Note: we need this in examples like
265 // fn foo(&self) -> &Self::Bar;
269 // fn foo(&self) -> &() {}
272 // Both &Self::Bar and &() are WF
273 let constraints_implied2 =
274 if ty != norm_ty { self.add_implied_bounds(norm_ty) } else { None };
275 normalized_inputs_and_output.push(norm_ty);
276 constraints1.into_iter().chain(constraints_implied1).chain(constraints_implied2)
280 // Insert the facts we know from the predicates. Why? Why not.
281 let param_env = self.param_env;
282 self.add_outlives_bounds(outlives::explicit_outlives_bounds(param_env));
285 // - outlives is reflexive, so `'r: 'r` for every region `'r`
286 // - `'static: 'r` for every region `'r`
287 // - `'r: 'fn_body` for every (other) universally quantified
288 // region `'r`, all of which are provided by our caller
289 let fr_static = self.universal_regions.fr_static;
290 let fr_fn_body = self.universal_regions.fr_fn_body;
291 for fr in self.universal_regions.universal_regions() {
292 debug!("build: relating free region {:?} to itself and to 'static", fr);
293 self.relate_universal_regions(fr, fr);
294 self.relate_universal_regions(fr_static, fr);
295 self.relate_universal_regions(fr, fr_fn_body);
298 for data in &constraint_sets {
299 constraint_conversion::ConstraintConversion::new(
301 &self.universal_regions,
302 &self.region_bound_pairs,
303 self.implicit_region_bound,
305 Locations::All(span),
307 ConstraintCategory::Internal,
308 &mut self.constraints,
314 universal_region_relations: Frozen::freeze(UniversalRegionRelations {
315 universal_regions: self.universal_regions,
316 outlives: self.outlives.freeze(),
317 inverse_outlives: self.inverse_outlives.freeze(),
319 region_bound_pairs: self.region_bound_pairs,
320 normalized_inputs_and_output,
324 /// Update the type of a single local, which should represent
325 /// either the return type of the MIR or one of its arguments. At
326 /// the same time, compute and add any implied bounds that come
328 #[instrument(level = "debug", skip(self))]
329 fn add_implied_bounds(&mut self, ty: Ty<'tcx>) -> Option<&'tcx QueryRegionConstraints<'tcx>> {
330 let TypeOpOutput { output: bounds, constraints, .. } = self
332 .and(type_op::implied_outlives_bounds::ImpliedOutlivesBounds { ty })
333 .fully_perform(self.infcx)
334 .unwrap_or_else(|_| bug!("failed to compute implied bounds {:?}", ty));
335 self.add_outlives_bounds(bounds);
339 /// Registers the `OutlivesBound` items from `outlives_bounds` in
340 /// the outlives relation as well as the region-bound pairs
342 fn add_outlives_bounds<I>(&mut self, outlives_bounds: I)
344 I: IntoIterator<Item = OutlivesBound<'tcx>>,
346 for outlives_bound in outlives_bounds {
347 debug!("add_outlives_bounds(bound={:?})", outlives_bound);
349 match outlives_bound {
350 OutlivesBound::RegionSubRegion(r1, r2) => {
351 // The bound says that `r1 <= r2`; we store `r2: r1`.
352 let r1 = self.universal_regions.to_region_vid(r1);
353 let r2 = self.universal_regions.to_region_vid(r2);
354 self.relate_universal_regions(r2, r1);
357 OutlivesBound::RegionSubParam(r_a, param_b) => {
358 self.region_bound_pairs
359 .insert(ty::OutlivesPredicate(GenericKind::Param(param_b), r_a));
362 OutlivesBound::RegionSubAlias(r_a, alias_b) => {
363 self.region_bound_pairs
364 .insert(ty::OutlivesPredicate(GenericKind::Alias(alias_b), r_a));