rustc_borrowck/type_check/
free_region_relations.rs1use rustc_data_structures::frozen::Frozen;
2use rustc_data_structures::transitive_relation::{TransitiveRelation, TransitiveRelationBuilder};
3use rustc_hir::def::DefKind;
4use rustc_infer::infer::canonical::QueryRegionConstraints;
5use rustc_infer::infer::outlives::env::RegionBoundPairs;
6use rustc_infer::infer::region_constraints::GenericKind;
7use rustc_infer::infer::{InferCtxt, outlives};
8use rustc_infer::traits::query::type_op::DeeplyNormalize;
9use rustc_middle::mir::ConstraintCategory;
10use rustc_middle::traits::query::OutlivesBound;
11use rustc_middle::ty::{self, RegionVid, Ty, TypeVisitableExt};
12use rustc_span::{ErrorGuaranteed, Span};
13use rustc_trait_selection::traits::query::type_op::{self, TypeOp};
14use tracing::{debug, instrument};
15use type_op::TypeOpOutput;
16
17use crate::type_check::{Locations, MirTypeckRegionConstraints, constraint_conversion};
18use crate::universal_regions::UniversalRegions;
19
20#[derive(Debug)]
21pub(crate) struct UniversalRegionRelations<'tcx> {
22 pub(crate) universal_regions: UniversalRegions<'tcx>,
23
24 outlives: TransitiveRelation<RegionVid>,
28
29 inverse_outlives: TransitiveRelation<RegionVid>,
34}
35
36type NormalizedInputsAndOutput<'tcx> = Vec<Ty<'tcx>>;
41
42pub(crate) struct CreateResult<'tcx> {
43 pub(crate) universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>,
44 pub(crate) region_bound_pairs: Frozen<RegionBoundPairs<'tcx>>,
45 pub(crate) known_type_outlives_obligations: Frozen<Vec<ty::PolyTypeOutlivesPredicate<'tcx>>>,
46 pub(crate) normalized_inputs_and_output: NormalizedInputsAndOutput<'tcx>,
47}
48
49pub(crate) fn create<'tcx>(
50 infcx: &InferCtxt<'tcx>,
51 param_env: ty::ParamEnv<'tcx>,
52 universal_regions: UniversalRegions<'tcx>,
53 constraints: &mut MirTypeckRegionConstraints<'tcx>,
54) -> CreateResult<'tcx> {
55 UniversalRegionRelationsBuilder {
56 infcx,
57 param_env,
58 constraints,
59 universal_regions,
60 region_bound_pairs: Default::default(),
61 outlives: Default::default(),
62 inverse_outlives: Default::default(),
63 }
64 .create()
65}
66
67impl UniversalRegionRelations<'_> {
68 pub(crate) fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid {
74 assert!(self.universal_regions.is_universal_region(fr1));
75 assert!(self.universal_regions.is_universal_region(fr2));
76 self.inverse_outlives
77 .postdom_upper_bound(fr1, fr2)
78 .unwrap_or(self.universal_regions.fr_static)
79 }
80
81 pub(crate) fn non_local_upper_bounds(&self, fr: RegionVid) -> Vec<RegionVid> {
87 debug!("non_local_upper_bound(fr={:?})", fr);
88 let res = self.non_local_bounds(&self.inverse_outlives, fr);
89 assert!(!res.is_empty(), "can't find an upper bound!?");
90 res
91 }
92
93 pub(crate) fn non_local_lower_bound(&self, fr: RegionVid) -> Option<RegionVid> {
100 debug!("non_local_lower_bound(fr={:?})", fr);
101 let lower_bounds = self.non_local_bounds(&self.outlives, fr);
102
103 let post_dom = self.outlives.mutual_immediate_postdominator(lower_bounds);
107
108 debug!("non_local_bound: post_dom={:?}", post_dom);
109
110 post_dom.and_then(|post_dom| {
111 if !self.universal_regions.is_local_free_region(post_dom) {
114 Some(post_dom)
115 } else {
116 None
117 }
118 })
119 }
120
121 fn non_local_bounds(
125 &self,
126 relation: &TransitiveRelation<RegionVid>,
127 fr0: RegionVid,
128 ) -> Vec<RegionVid> {
129 assert!(self.universal_regions.is_universal_region(fr0));
132
133 let mut external_parents = vec![];
134
135 let mut queue = vec![relation.minimal_scc_representative(fr0)];
136
137 while let Some(fr) = queue.pop() {
140 if !self.universal_regions.is_local_free_region(fr) {
141 external_parents.push(fr);
142 continue;
143 }
144
145 queue.extend(relation.parents(fr));
146 }
147
148 debug!("non_local_bound: external_parents={:?}", external_parents);
149
150 external_parents
151 }
152
153 pub(crate) fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
157 self.outlives.contains(fr1, fr2)
158 }
159
160 pub(crate) fn equal(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
164 self.outlives.contains(fr1, fr2) && self.outlives.contains(fr2, fr1)
165 }
166
167 pub(crate) fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<RegionVid> {
170 self.outlives.reachable_from(fr1)
171 }
172
173 pub(crate) fn known_outlives(&self) -> impl Iterator<Item = (RegionVid, RegionVid)> {
175 self.outlives.base_edges()
176 }
177}
178
179struct UniversalRegionRelationsBuilder<'a, 'tcx> {
180 infcx: &'a InferCtxt<'tcx>,
181 param_env: ty::ParamEnv<'tcx>,
182 universal_regions: UniversalRegions<'tcx>,
183 constraints: &'a mut MirTypeckRegionConstraints<'tcx>,
184
185 outlives: TransitiveRelationBuilder<RegionVid>,
187 inverse_outlives: TransitiveRelationBuilder<RegionVid>,
188 region_bound_pairs: RegionBoundPairs<'tcx>,
189}
190
191impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> {
192 fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) {
195 debug!("relate_universal_regions: fr_a={:?} outlives fr_b={:?}", fr_a, fr_b);
196 self.outlives.add(fr_a, fr_b);
197 self.inverse_outlives.add(fr_b, fr_a);
198 }
199
200 #[instrument(level = "debug", skip(self))]
201 pub(crate) fn create(mut self) -> CreateResult<'tcx> {
202 let tcx = self.infcx.tcx;
203 let defining_ty_def_id = self.universal_regions.defining_ty.def_id().expect_local();
204 let span = tcx.def_span(defining_ty_def_id);
205
206 let param_env = self.param_env;
209 self.add_outlives_bounds(outlives::explicit_outlives_bounds(param_env));
210
211 let fr_static = self.universal_regions.fr_static;
216 let fr_fn_body = self.universal_regions.fr_fn_body;
217 for fr in self.universal_regions.universal_regions_iter() {
218 debug!("build: relating free region {:?} to itself and to 'static", fr);
219 self.relate_universal_regions(fr, fr);
220 self.relate_universal_regions(fr_static, fr);
221 self.relate_universal_regions(fr, fr_fn_body);
222 }
223
224 let mut constraints = vec![];
226 let mut known_type_outlives_obligations = vec![];
227 for bound in param_env.caller_bounds() {
228 if let Some(outlives) = bound.as_type_outlives_clause() {
229 self.normalize_and_push_type_outlives_obligation(
230 outlives,
231 span,
232 &mut known_type_outlives_obligations,
233 &mut constraints,
234 );
235 };
236 }
237
238 let unnormalized_input_output_tys = self
239 .universal_regions
240 .unnormalized_input_tys
241 .iter()
242 .cloned()
243 .chain(Some(self.universal_regions.unnormalized_output_ty));
244
245 let mut normalized_inputs_and_output =
254 Vec::with_capacity(self.universal_regions.unnormalized_input_tys.len() + 1);
255 for ty in unnormalized_input_output_tys {
256 debug!("build: input_or_output={:?}", ty);
257 let constraints_unnorm = self.add_implied_bounds(ty, span);
260 if let Some(c) = constraints_unnorm {
261 constraints.push(c)
262 }
263 let TypeOpOutput { output: norm_ty, constraints: constraints_normalize, .. } =
264 param_env
265 .and(DeeplyNormalize { value: ty })
266 .fully_perform(self.infcx, span)
267 .unwrap_or_else(|guar| TypeOpOutput {
268 output: Ty::new_error(self.infcx.tcx, guar),
269 constraints: None,
270 error_info: None,
271 });
272 if let Some(c) = constraints_normalize {
273 constraints.push(c)
274 }
275
276 if ty != norm_ty {
289 let constraints_norm = self.add_implied_bounds(norm_ty, span);
290 if let Some(c) = constraints_norm {
291 constraints.push(c)
292 }
293 }
294
295 normalized_inputs_and_output.push(norm_ty);
296 }
297
298 if matches!(tcx.def_kind(defining_ty_def_id), DefKind::AssocFn | DefKind::AssocConst) {
300 for &(ty, _) in tcx.assumed_wf_types(tcx.local_parent(defining_ty_def_id)) {
301 let result: Result<_, ErrorGuaranteed> =
302 param_env.and(DeeplyNormalize { value: ty }).fully_perform(self.infcx, span);
303 let Ok(TypeOpOutput { output: norm_ty, constraints: c, .. }) = result else {
304 continue;
305 };
306
307 constraints.extend(c);
308
309 let c = self.add_implied_bounds(norm_ty, span);
312 constraints.extend(c);
313 }
314 }
315
316 for c in constraints {
317 constraint_conversion::ConstraintConversion::new(
318 self.infcx,
319 &self.universal_regions,
320 &self.region_bound_pairs,
321 param_env,
322 &known_type_outlives_obligations,
323 Locations::All(span),
324 span,
325 ConstraintCategory::Internal,
326 self.constraints,
327 )
328 .convert_all(c);
329 }
330
331 CreateResult {
332 universal_region_relations: Frozen::freeze(UniversalRegionRelations {
333 universal_regions: self.universal_regions,
334 outlives: self.outlives.freeze(),
335 inverse_outlives: self.inverse_outlives.freeze(),
336 }),
337 known_type_outlives_obligations: Frozen::freeze(known_type_outlives_obligations),
338 region_bound_pairs: Frozen::freeze(self.region_bound_pairs),
339 normalized_inputs_and_output,
340 }
341 }
342
343 fn normalize_and_push_type_outlives_obligation(
344 &self,
345 mut outlives: ty::PolyTypeOutlivesPredicate<'tcx>,
346 span: Span,
347 known_type_outlives_obligations: &mut Vec<ty::PolyTypeOutlivesPredicate<'tcx>>,
348 constraints: &mut Vec<&QueryRegionConstraints<'tcx>>,
349 ) {
350 if self.infcx.next_trait_solver() {
352 let Ok(TypeOpOutput {
353 output: normalized_outlives,
354 constraints: constraints_normalize,
355 error_info: _,
356 }) = self
357 .param_env
358 .and(DeeplyNormalize { value: outlives })
359 .fully_perform(self.infcx, span)
360 else {
361 self.infcx.dcx().delayed_bug(format!("could not normalize {outlives:?}"));
362 return;
363 };
364 outlives = normalized_outlives;
365 if let Some(c) = constraints_normalize {
366 constraints.push(c);
367 }
368 }
369
370 known_type_outlives_obligations.push(outlives);
371 }
372
373 #[instrument(level = "debug", skip(self))]
378 fn add_implied_bounds(
379 &mut self,
380 ty: Ty<'tcx>,
381 span: Span,
382 ) -> Option<&'tcx QueryRegionConstraints<'tcx>> {
383 let TypeOpOutput { output: bounds, constraints, .. } = self
384 .param_env
385 .and(type_op::ImpliedOutlivesBounds { ty })
386 .fully_perform(self.infcx, span)
387 .map_err(|_: ErrorGuaranteed| debug!("failed to compute implied bounds {:?}", ty))
388 .ok()?;
389 debug!(?bounds, ?constraints);
390 let bounds = bounds.into_iter().filter(|bound| !bound.has_placeholders());
393 self.add_outlives_bounds(bounds);
394 constraints
395 }
396
397 fn add_outlives_bounds<I>(&mut self, outlives_bounds: I)
401 where
402 I: IntoIterator<Item = OutlivesBound<'tcx>>,
403 {
404 for outlives_bound in outlives_bounds {
405 debug!("add_outlives_bounds(bound={:?})", outlives_bound);
406
407 match outlives_bound {
408 OutlivesBound::RegionSubRegion(r1, r2) => {
409 let r1 = self.universal_regions.to_region_vid(r1);
411 let r2 = self.universal_regions.to_region_vid(r2);
412 self.relate_universal_regions(r2, r1);
413 }
414
415 OutlivesBound::RegionSubParam(r_a, param_b) => {
416 self.region_bound_pairs
417 .insert(ty::OutlivesPredicate(GenericKind::Param(param_b), r_a));
418 }
419
420 OutlivesBound::RegionSubAlias(r_a, alias_b) => {
421 self.region_bound_pairs
422 .insert(ty::OutlivesPredicate(GenericKind::Alias(alias_b), r_a));
423 }
424 }
425 }
426 }
427}