]>
Commit | Line | Data |
---|---|---|
ba9703b0 | 1 | use rustc_data_structures::frozen::Frozen; |
f2b60f7d | 2 | use rustc_data_structures::transitive_relation::{TransitiveRelation, TransitiveRelationBuilder}; |
74b04a01 | 3 | use rustc_infer::infer::canonical::QueryRegionConstraints; |
ba9703b0 | 4 | use rustc_infer::infer::outlives; |
064997fb | 5 | use rustc_infer::infer::outlives::env::RegionBoundPairs; |
74b04a01 XL |
6 | use rustc_infer::infer::region_constraints::GenericKind; |
7 | use rustc_infer::infer::InferCtxt; | |
ba9703b0 XL |
8 | use rustc_middle::mir::ConstraintCategory; |
9 | use rustc_middle::traits::query::OutlivesBound; | |
3c0e092e | 10 | use rustc_middle::ty::{self, RegionVid, Ty}; |
ba9703b0 | 11 | use rustc_trait_selection::traits::query::type_op::{self, TypeOp}; |
8faf50e0 | 12 | use std::rc::Rc; |
94222f64 | 13 | use type_op::TypeOpOutput; |
8faf50e0 | 14 | |
c295e0f8 | 15 | use crate::{ |
60c5eb7d XL |
16 | type_check::constraint_conversion, |
17 | type_check::{Locations, MirTypeckRegionConstraints}, | |
18 | universal_regions::UniversalRegions, | |
60c5eb7d XL |
19 | }; |
20 | ||
8faf50e0 | 21 | #[derive(Debug)] |
923072b8 | 22 | pub(crate) struct UniversalRegionRelations<'tcx> { |
8faf50e0 XL |
23 | universal_regions: Rc<UniversalRegions<'tcx>>, |
24 | ||
25 | /// Stores the outlives relations that are known to hold from the | |
9fa01778 | 26 | /// implied bounds, in-scope where-clauses, and that sort of |
8faf50e0 XL |
27 | /// thing. |
28 | outlives: TransitiveRelation<RegionVid>, | |
29 | ||
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>, | |
35 | } | |
36 | ||
8faf50e0 XL |
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 | |
9fa01778 | 39 | /// return those. This vector consists of first the input types and |
8faf50e0 XL |
40 | /// then the output type as the last element. |
41 | type NormalizedInputsAndOutput<'tcx> = Vec<Ty<'tcx>>; | |
42 | ||
923072b8 FG |
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>, | |
8faf50e0 XL |
47 | } |
48 | ||
923072b8 | 49 | pub(crate) fn create<'tcx>( |
2b03887a | 50 | infcx: &InferCtxt<'tcx>, |
8faf50e0 | 51 | param_env: ty::ParamEnv<'tcx>, |
064997fb | 52 | implicit_region_bound: ty::Region<'tcx>, |
8faf50e0 XL |
53 | universal_regions: &Rc<UniversalRegions<'tcx>>, |
54 | constraints: &mut MirTypeckRegionConstraints<'tcx>, | |
8faf50e0 | 55 | ) -> CreateResult<'tcx> { |
8faf50e0 XL |
56 | UniversalRegionRelationsBuilder { |
57 | infcx, | |
8faf50e0 XL |
58 | param_env, |
59 | implicit_region_bound, | |
60 | constraints, | |
8faf50e0 | 61 | universal_regions: universal_regions.clone(), |
064997fb | 62 | region_bound_pairs: Default::default(), |
f2b60f7d FG |
63 | outlives: Default::default(), |
64 | inverse_outlives: Default::default(), | |
dfeec247 XL |
65 | } |
66 | .create() | |
8faf50e0 XL |
67 | } |
68 | ||
a2a8927a | 69 | impl UniversalRegionRelations<'_> { |
8faf50e0 XL |
70 | /// Given two universal regions, returns the postdominating |
71 | /// upper-bound (effectively the least upper bound). | |
72 | /// | |
73 | /// (See `TransitiveRelation::postdom_upper_bound` for details on | |
74 | /// the postdominating upper bound in general.) | |
923072b8 | 75 | pub(crate) fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid { |
8faf50e0 XL |
76 | assert!(self.universal_regions.is_universal_region(fr1)); |
77 | assert!(self.universal_regions.is_universal_region(fr2)); | |
5e7ed085 FG |
78 | self.inverse_outlives |
79 | .postdom_upper_bound(fr1, fr2) | |
80 | .unwrap_or(self.universal_regions.fr_static) | |
8faf50e0 XL |
81 | } |
82 | ||
83 | /// Finds an "upper bound" for `fr` that is not local. In other | |
84 | /// words, returns the smallest (*) known region `fr1` that (a) | |
9fa01778 | 85 | /// outlives `fr` and (b) is not local. |
8faf50e0 | 86 | /// |
9fa01778 | 87 | /// (*) If there are multiple competing choices, we return all of them. |
923072b8 | 88 | pub(crate) fn non_local_upper_bounds<'a>(&'a self, fr: RegionVid) -> Vec<RegionVid> { |
8faf50e0 | 89 | debug!("non_local_upper_bound(fr={:?})", fr); |
9fa01778 XL |
90 | let res = self.non_local_bounds(&self.inverse_outlives, fr); |
91 | assert!(!res.is_empty(), "can't find an upper bound!?"); | |
92 | res | |
93 | } | |
94 | ||
95 | /// Returns the "postdominating" bound of the set of | |
96 | /// `non_local_upper_bounds` for the given region. | |
923072b8 | 97 | pub(crate) fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid { |
5e7ed085 | 98 | let upper_bounds = self.non_local_upper_bounds(fr); |
9fa01778 XL |
99 | |
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. | |
dfeec247 | 103 | let post_dom = self.inverse_outlives.mutual_immediate_postdominator(upper_bounds); |
9fa01778 XL |
104 | |
105 | debug!("non_local_bound: post_dom={:?}", post_dom); | |
106 | ||
107 | post_dom | |
5e7ed085 | 108 | .and_then(|post_dom| { |
9fa01778 XL |
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) { | |
112 | Some(post_dom) | |
113 | } else { | |
114 | None | |
115 | } | |
116 | }) | |
8faf50e0 XL |
117 | .unwrap_or(self.universal_regions.fr_static) |
118 | } | |
119 | ||
120 | /// Finds a "lower bound" for `fr` that is not local. In other | |
121 | /// words, returns the largest (*) known region `fr1` that (a) is | |
9fa01778 | 122 | /// outlived by `fr` and (b) is not local. |
8faf50e0 XL |
123 | /// |
124 | /// (*) If there are multiple competing choices, we pick the "postdominating" | |
125 | /// one. See `TransitiveRelation::postdom_upper_bound` for details. | |
923072b8 | 126 | pub(crate) fn non_local_lower_bound(&self, fr: RegionVid) -> Option<RegionVid> { |
8faf50e0 | 127 | debug!("non_local_lower_bound(fr={:?})", fr); |
5e7ed085 | 128 | let lower_bounds = self.non_local_bounds(&self.outlives, fr); |
9fa01778 XL |
129 | |
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. | |
dfeec247 | 133 | let post_dom = self.outlives.mutual_immediate_postdominator(lower_bounds); |
9fa01778 XL |
134 | |
135 | debug!("non_local_bound: post_dom={:?}", post_dom); | |
136 | ||
5e7ed085 | 137 | post_dom.and_then(|post_dom| { |
dfeec247 XL |
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) { | |
141 | Some(post_dom) | |
142 | } else { | |
143 | None | |
144 | } | |
145 | }) | |
8faf50e0 XL |
146 | } |
147 | ||
9fa01778 XL |
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. | |
151 | fn non_local_bounds<'a>( | |
8faf50e0 | 152 | &self, |
9fa01778 | 153 | relation: &'a TransitiveRelation<RegionVid>, |
5e7ed085 FG |
154 | fr0: RegionVid, |
155 | ) -> Vec<RegionVid> { | |
8faf50e0 XL |
156 | // This method assumes that `fr0` is one of the universally |
157 | // quantified region variables. | |
5e7ed085 | 158 | assert!(self.universal_regions.is_universal_region(fr0)); |
8faf50e0 XL |
159 | |
160 | let mut external_parents = vec![]; | |
9fa01778 | 161 | let mut queue = vec![fr0]; |
8faf50e0 XL |
162 | |
163 | // Keep expanding `fr` into its parents until we reach | |
164 | // non-local regions. | |
165 | while let Some(fr) = queue.pop() { | |
5e7ed085 | 166 | if !self.universal_regions.is_local_free_region(fr) { |
8faf50e0 XL |
167 | external_parents.push(fr); |
168 | continue; | |
169 | } | |
170 | ||
171 | queue.extend(relation.parents(fr)); | |
172 | } | |
173 | ||
174 | debug!("non_local_bound: external_parents={:?}", external_parents); | |
175 | ||
9fa01778 | 176 | external_parents |
8faf50e0 XL |
177 | } |
178 | ||
9fa01778 | 179 | /// Returns `true` if fr1 is known to outlive fr2. |
8faf50e0 XL |
180 | /// |
181 | /// This will only ever be true for universally quantified regions. | |
923072b8 | 182 | pub(crate) fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool { |
5e7ed085 | 183 | self.outlives.contains(fr1, fr2) |
8faf50e0 XL |
184 | } |
185 | ||
186 | /// Returns a vector of free regions `x` such that `fr1: x` is | |
187 | /// known to hold. | |
923072b8 | 188 | pub(crate) fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<RegionVid> { |
5e7ed085 | 189 | self.outlives.reachable_from(fr1) |
8faf50e0 | 190 | } |
60c5eb7d XL |
191 | |
192 | /// Returns the _non-transitive_ set of known `outlives` constraints between free regions. | |
923072b8 | 193 | pub(crate) fn known_outlives(&self) -> impl Iterator<Item = (RegionVid, RegionVid)> + '_ { |
60c5eb7d XL |
194 | self.outlives.base_edges() |
195 | } | |
8faf50e0 XL |
196 | } |
197 | ||
dc9dc135 | 198 | struct UniversalRegionRelationsBuilder<'this, 'tcx> { |
2b03887a | 199 | infcx: &'this InferCtxt<'tcx>, |
8faf50e0 | 200 | param_env: ty::ParamEnv<'tcx>, |
8faf50e0 | 201 | universal_regions: Rc<UniversalRegions<'tcx>>, |
064997fb | 202 | implicit_region_bound: ty::Region<'tcx>, |
8faf50e0 | 203 | constraints: &'this mut MirTypeckRegionConstraints<'tcx>, |
8faf50e0 XL |
204 | |
205 | // outputs: | |
f2b60f7d FG |
206 | outlives: TransitiveRelationBuilder<RegionVid>, |
207 | inverse_outlives: TransitiveRelationBuilder<RegionVid>, | |
8faf50e0 XL |
208 | region_bound_pairs: RegionBoundPairs<'tcx>, |
209 | } | |
210 | ||
a2a8927a | 211 | impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> { |
f2b60f7d FG |
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); | |
218 | } | |
219 | ||
923072b8 | 220 | pub(crate) fn create(mut self) -> CreateResult<'tcx> { |
2b03887a | 221 | let span = self.infcx.tcx.def_span(self.universal_regions.defining_ty.def_id()); |
8faf50e0 XL |
222 | let unnormalized_input_output_tys = self |
223 | .universal_regions | |
224 | .unnormalized_input_tys | |
225 | .iter() | |
226 | .cloned() | |
227 | .chain(Some(self.universal_regions.unnormalized_output_ty)); | |
228 | ||
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 | |
240 | .flat_map(|ty| { | |
241 | debug!("build: input_or_output={:?}", ty); | |
f2b60f7d FG |
242 | // We add implied bounds from both the unnormalized and normalized ty. |
243 | // See issue #87748 | |
244 | let constraints_implied1 = self.add_implied_bounds(ty); | |
c295e0f8 | 245 | let TypeOpOutput { output: norm_ty, constraints: constraints1, .. } = self |
8faf50e0 XL |
246 | .param_env |
247 | .and(type_op::normalize::Normalize::new(ty)) | |
248 | .fully_perform(self.infcx) | |
f035d41b | 249 | .unwrap_or_else(|_| { |
487cf647 FG |
250 | let reported = self |
251 | .infcx | |
f035d41b XL |
252 | .tcx |
253 | .sess | |
2b03887a | 254 | .delay_span_bug(span, &format!("failed to normalize {:?}", ty)); |
94222f64 | 255 | TypeOpOutput { |
487cf647 | 256 | output: self.infcx.tcx.ty_error_with_guaranteed(reported), |
94222f64 | 257 | constraints: None, |
5e7ed085 | 258 | error_info: None, |
94222f64 | 259 | } |
f035d41b | 260 | }); |
94222f64 XL |
261 | // Note: we need this in examples like |
262 | // ``` | |
263 | // trait Foo { | |
264 | // type Bar; | |
265 | // fn foo(&self) -> &Self::Bar; | |
266 | // } | |
267 | // impl Foo for () { | |
268 | // type Bar = (); | |
f2b60f7d | 269 | // fn foo(&self) -> &() {} |
94222f64 XL |
270 | // } |
271 | // ``` | |
272 | // Both &Self::Bar and &() are WF | |
f2b60f7d FG |
273 | let constraints_implied2 = |
274 | if ty != norm_ty { self.add_implied_bounds(norm_ty) } else { None }; | |
c295e0f8 | 275 | normalized_inputs_and_output.push(norm_ty); |
f2b60f7d | 276 | constraints1.into_iter().chain(constraints_implied1).chain(constraints_implied2) |
8faf50e0 XL |
277 | }) |
278 | .collect(); | |
279 | ||
280 | // Insert the facts we know from the predicates. Why? Why not. | |
281 | let param_env = self.param_env; | |
ba9703b0 | 282 | self.add_outlives_bounds(outlives::explicit_outlives_bounds(param_env)); |
8faf50e0 XL |
283 | |
284 | // Finally: | |
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() { | |
dfeec247 | 292 | debug!("build: relating free region {:?} to itself and to 'static", fr); |
f2b60f7d FG |
293 | self.relate_universal_regions(fr, fr); |
294 | self.relate_universal_regions(fr_static, fr); | |
295 | self.relate_universal_regions(fr, fr_fn_body); | |
8faf50e0 XL |
296 | } |
297 | ||
dc9dc135 | 298 | for data in &constraint_sets { |
8faf50e0 | 299 | constraint_conversion::ConstraintConversion::new( |
a1dfa0c6 | 300 | self.infcx, |
8faf50e0 | 301 | &self.universal_regions, |
8faf50e0 XL |
302 | &self.region_bound_pairs, |
303 | self.implicit_region_bound, | |
304 | self.param_env, | |
2b03887a FG |
305 | Locations::All(span), |
306 | span, | |
0bf4aa26 | 307 | ConstraintCategory::Internal, |
a1dfa0c6 | 308 | &mut self.constraints, |
dfeec247 XL |
309 | ) |
310 | .convert_all(data); | |
8faf50e0 XL |
311 | } |
312 | ||
313 | CreateResult { | |
f2b60f7d FG |
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(), | |
318 | }), | |
8faf50e0 XL |
319 | region_bound_pairs: self.region_bound_pairs, |
320 | normalized_inputs_and_output, | |
321 | } | |
322 | } | |
323 | ||
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 | |
327 | /// from this local. | |
923072b8 | 328 | #[instrument(level = "debug", skip(self))] |
064997fb | 329 | fn add_implied_bounds(&mut self, ty: Ty<'tcx>) -> Option<&'tcx QueryRegionConstraints<'tcx>> { |
94222f64 | 330 | let TypeOpOutput { output: bounds, constraints, .. } = self |
dfeec247 | 331 | .param_env |
b7449926 XL |
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)); | |
8faf50e0 | 335 | self.add_outlives_bounds(bounds); |
b7449926 | 336 | constraints |
8faf50e0 XL |
337 | } |
338 | ||
339 | /// Registers the `OutlivesBound` items from `outlives_bounds` in | |
340 | /// the outlives relation as well as the region-bound pairs | |
341 | /// listing. | |
342 | fn add_outlives_bounds<I>(&mut self, outlives_bounds: I) | |
343 | where | |
344 | I: IntoIterator<Item = OutlivesBound<'tcx>>, | |
345 | { | |
346 | for outlives_bound in outlives_bounds { | |
347 | debug!("add_outlives_bounds(bound={:?})", outlives_bound); | |
348 | ||
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); | |
f2b60f7d | 354 | self.relate_universal_regions(r2, r1); |
8faf50e0 XL |
355 | } |
356 | ||
357 | OutlivesBound::RegionSubParam(r_a, param_b) => { | |
064997fb FG |
358 | self.region_bound_pairs |
359 | .insert(ty::OutlivesPredicate(GenericKind::Param(param_b), r_a)); | |
8faf50e0 XL |
360 | } |
361 | ||
362 | OutlivesBound::RegionSubProjection(r_a, projection_b) => { | |
064997fb FG |
363 | self.region_bound_pairs |
364 | .insert(ty::OutlivesPredicate(GenericKind::Projection(projection_b), r_a)); | |
8faf50e0 | 365 | } |
2b03887a FG |
366 | |
367 | OutlivesBound::RegionSubOpaque(r_a, def_id, substs) => { | |
368 | self.region_bound_pairs | |
369 | .insert(ty::OutlivesPredicate(GenericKind::Opaque(def_id, substs), r_a)); | |
370 | } | |
8faf50e0 XL |
371 | } |
372 | } | |
373 | } | |
374 | } |