compiler/rustc_borrowck/src/type_check/free_region_relations.rs

   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};
  12 use std::rc::Rc;
  13 use type_op::TypeOpOutput;
  14
  15 use crate::{
  16     type_check::constraint_conversion,
  17     type_check::{Locations, MirTypeckRegionConstraints},
  18     universal_regions::UniversalRegions,
  19 };
  20
  21 #[derive(Debug)]
  22 pub(crate) struct UniversalRegionRelations<'tcx> {
  23     universal_regions: Rc<UniversalRegions<'tcx>>,
  24
  25     /// Stores the outlives relations that are known to hold from the
  26     /// implied bounds, in-scope where-clauses, and that sort of
  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
  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>>;
  42
  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>,
  47 }
  48
  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 {
  57         infcx,
  58         param_env,
  59         implicit_region_bound,
  60         constraints,
  61         universal_regions: universal_regions.clone(),
  62         region_bound_pairs: Default::default(),
  63         outlives: Default::default(),
  64         inverse_outlives: Default::default(),
  65     }
  66     .create()
  67 }
  68
  69 impl UniversalRegionRelations<'_> {
  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.)
  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));
  78         self.inverse_outlives
  79             .postdom_upper_bound(fr1, fr2)
  80             .unwrap_or(self.universal_regions.fr_static)
  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)
  85     /// outlives `fr` and (b) is not local.
  86     ///
  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!?");
  92         res
  93     }
  94
  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);
  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.
 103         let post_dom = self.inverse_outlives.mutual_immediate_postdominator(upper_bounds);
 104
 105         debug!("non_local_bound: post_dom={:?}", post_dom);
 106
 107         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) {
 112                     Some(post_dom)
 113                 } else {
 114                     None
 115                 }
 116             })
 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
 122     /// outlived by `fr` and (b) is not local.
 123     ///
 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);
 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.
 133         let post_dom = self.outlives.mutual_immediate_postdominator(lower_bounds);
 134
 135         debug!("non_local_bound: post_dom={:?}", post_dom);
 136
 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) {
 141                 Some(post_dom)
 142             } else {
 143                 None
 144             }
 145         })
 146     }
 147
 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(
 152         &self,
 153         relation: &TransitiveRelation<RegionVid>,
 154         fr0: 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));
 159
 160         let mut external_parents = vec![];
 161         let mut queue = vec![fr0];
 162
 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);
 168                 continue;
 169             }
 170
 171             queue.extend(relation.parents(fr));
 172         }
 173
 174         debug!("non_local_bound: external_parents={:?}", external_parents);
 175
 176         external_parents
 177     }
 178
 179     /// Returns `true` if fr1 is known to outlive fr2.
 180     ///
 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)
 184     }
 185
 186     /// Returns a vector of free regions `x` such that `fr1: x` is
 187     /// known to hold.
 188     pub(crate) fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<RegionVid> {
 189         self.outlives.reachable_from(fr1)
 190     }
 191
 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()
 195     }
 196 }
 197
 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>,
 204
 205     // outputs:
 206     outlives: TransitiveRelationBuilder<RegionVid>,
 207     inverse_outlives: TransitiveRelationBuilder<RegionVid>,
 208     region_bound_pairs: RegionBoundPairs<'tcx>,
 209 }
 210
 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);
 218     }
 219
 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
 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);
 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);
 245                 let TypeOpOutput { output: norm_ty, constraints: constraints1, .. } = self
 246                     .param_env
 247                     .and(type_op::normalize::Normalize::new(ty))
 248                     .fully_perform(self.infcx)
 249                     .unwrap_or_else(|_| {
 250                         let reported = self
 251                             .infcx
 252                             .tcx
 253                             .sess
 254                             .delay_span_bug(span, &format!("failed to normalize {:?}", ty));
 255                         TypeOpOutput {
 256                             output: self.infcx.tcx.ty_error_with_guaranteed(reported),
 257                             constraints: None,
 258                             error_info: None,
 259                         }
 260                     });
 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 = ();
 269                 //   fn foo(&self) -> &() {}
 270                 // }
 271                 // ```
 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)
 277             })
 278             .collect();
 279
 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));
 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() {
 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);
 296         }
 297
 298         for data in &constraint_sets {
 299             constraint_conversion::ConstraintConversion::new(
 300                 self.infcx,
 301                 &self.universal_regions,
 302                 &self.region_bound_pairs,
 303                 self.implicit_region_bound,
 304                 self.param_env,
 305                 Locations::All(span),
 306                 span,
 307                 ConstraintCategory::Internal,
 308                 &mut self.constraints,
 309             )
 310             .convert_all(data);
 311         }
 312
 313         CreateResult {
 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             }),
 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.
 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
 331             .param_env
 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);
 336         constraints
 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);
 354                     self.relate_universal_regions(r2, r1);
 355                 }
 356
 357                 OutlivesBound::RegionSubParam(r_a, param_b) => {
 358                     self.region_bound_pairs
 359                         .insert(ty::OutlivesPredicate(GenericKind::Param(param_b), r_a));
 360                 }
 361
 362                 OutlivesBound::RegionSubAlias(r_a, alias_b) => {
 363                     self.region_bound_pairs
 364                         .insert(ty::OutlivesPredicate(GenericKind::Alias(alias_b), r_a));
 365                 }
 366             }
 367         }
 368     }
 369 }