rustc_borrowck/type_check/
free_region_relations.rs

1use 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    /// Stores the outlives relations that are known to hold from the
25    /// implied bounds, in-scope where-clauses, and that sort of
26    /// thing.
27    outlives: TransitiveRelation<RegionVid>,
28
29    /// This is the `<=` relation; that is, if `a: b`, then `b <= a`,
30    /// and we store that here. This is useful when figuring out how
31    /// to express some local region in terms of external regions our
32    /// caller will understand.
33    inverse_outlives: TransitiveRelation<RegionVid>,
34}
35
36/// As part of computing the free region relations, we also have to
37/// normalize the input-output types, which we then need later. So we
38/// return those. This vector consists of first the input types and
39/// then the output type as the last element.
40type 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    /// Given two universal regions, returns the postdominating
69    /// upper-bound (effectively the least upper bound).
70    ///
71    /// (See `TransitiveRelation::postdom_upper_bound` for details on
72    /// the postdominating upper bound in general.)
73    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    /// Finds an "upper bound" for `fr` that is not local. In other
82    /// words, returns the smallest (*) known region `fr1` that (a)
83    /// outlives `fr` and (b) is not local.
84    ///
85    /// (*) If there are multiple competing choices, we return all of them.
86    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    /// Finds a "lower bound" for `fr` that is not local. In other
94    /// words, returns the largest (*) known region `fr1` that (a) is
95    /// outlived by `fr` and (b) is not local.
96    ///
97    /// (*) If there are multiple competing choices, we pick the "postdominating"
98    /// one. See `TransitiveRelation::postdom_upper_bound` for details.
99    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        // In case we find more than one, reduce to one for
104        // convenience. This is to prevent us from generating more
105        // complex constraints, but it will cause spurious errors.
106        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 the mutual immediate postdom is not local, then
112            // there is no non-local result we can return.
113            if !self.universal_regions.is_local_free_region(post_dom) {
114                Some(post_dom)
115            } else {
116                None
117            }
118        })
119    }
120
121    /// Helper for `non_local_upper_bounds` and `non_local_lower_bounds`.
122    /// Repeatedly invokes `postdom_parent` until we find something that is not
123    /// local. Returns `None` if we never do so.
124    fn non_local_bounds(
125        &self,
126        relation: &TransitiveRelation<RegionVid>,
127        fr0: RegionVid,
128    ) -> Vec<RegionVid> {
129        // This method assumes that `fr0` is one of the universally
130        // quantified region variables.
131        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        // Keep expanding `fr` into its parents until we reach
138        // non-local regions.
139        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    /// Returns `true` if fr1 is known to outlive fr2.
154    ///
155    /// This will only ever be true for universally quantified regions.
156    pub(crate) fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
157        self.outlives.contains(fr1, fr2)
158    }
159
160    /// Returns `true` if fr1 is known to equal fr2.
161    ///
162    /// This will only ever be true for universally quantified regions.
163    pub(crate) fn equal(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
164        self.outlives.contains(fr1, fr2) && self.outlives.contains(fr2, fr1)
165    }
166
167    /// Returns a vector of free regions `x` such that `fr1: x` is
168    /// known to hold.
169    pub(crate) fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<RegionVid> {
170        self.outlives.reachable_from(fr1)
171    }
172
173    /// Returns the _non-transitive_ set of known `outlives` constraints between free regions.
174    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    // outputs:
186    outlives: TransitiveRelationBuilder<RegionVid>,
187    inverse_outlives: TransitiveRelationBuilder<RegionVid>,
188    region_bound_pairs: RegionBoundPairs<'tcx>,
189}
190
191impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> {
192    /// Records in the `outlives_relation` (and
193    /// `inverse_outlives_relation`) that `fr_a: fr_b`.
194    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        // Insert the `'a: 'b` we know from the predicates.
207        // This does not consider the type-outlives.
208        let param_env = self.param_env;
209        self.add_outlives_bounds(outlives::explicit_outlives_bounds(param_env));
210
211        // - outlives is reflexive, so `'r: 'r` for every region `'r`
212        // - `'static: 'r` for every region `'r`
213        // - `'r: 'fn_body` for every (other) universally quantified
214        //   region `'r`, all of which are provided by our caller
215        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        // Normalize the assumptions we use to borrowck the program.
225        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        // For each of the input/output types:
246        // - Normalize the type. This will create some region
247        //   constraints, which we buffer up because we are
248        //   not ready to process them yet.
249        // - Then compute the implied bounds. This will adjust
250        //   the `region_bound_pairs` and so forth.
251        // - After this is done, we'll process the constraints, once
252        //   the `relations` is built.
253        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            // We add implied bounds from both the unnormalized and normalized ty.
258            // See issue #87748
259            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            // Note: we need this in examples like
277            // ```
278            // trait Foo {
279            //   type Bar;
280            //   fn foo(&self) -> &Self::Bar;
281            // }
282            // impl Foo for () {
283            //   type Bar = ();
284            //   fn foo(&self) ->&() {}
285            // }
286            // ```
287            // Both &Self::Bar and &() are WF
288            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        // Add implied bounds from impl header.
299        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                // We currently add implied bounds from the normalized ty only.
310                // This is more conservative and matches wfcheck behavior.
311                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        // In the new solver, normalize the type-outlives obligation assumptions.
351        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    /// Update the type of a single local, which should represent
374    /// either the return type of the MIR or one of its arguments. At
375    /// the same time, compute and add any implied bounds that come
376    /// from this local.
377    #[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        // Because of #109628, we may have unexpected placeholders. Ignore them!
391        // FIXME(#109628): panic in this case once the issue is fixed.
392        let bounds = bounds.into_iter().filter(|bound| !bound.has_placeholders());
393        self.add_outlives_bounds(bounds);
394        constraints
395    }
396
397    /// Registers the `OutlivesBound` items from `outlives_bounds` in
398    /// the outlives relation as well as the region-bound pairs
399    /// listing.
400    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                    // The bound says that `r1 <= r2`; we store `r2: r1`.
410                    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}