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;
   3 use rustc_infer::infer::canonical::QueryRegionConstraints;
   4 use rustc_infer::infer::outlives;
   5 use rustc_infer::infer::region_constraints::GenericKind;
   6 use rustc_infer::infer::InferCtxt;
   7 use rustc_middle::mir::ConstraintCategory;
   8 use rustc_middle::traits::query::OutlivesBound;
   9 use rustc_middle::ty::{self, RegionVid, Ty};
  10 use rustc_span::DUMMY_SP;
  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 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 /// Each RBP `('a, GK)` indicates that `GK: 'a` can be assumed to
  38 /// be true. These encode relationships like `T: 'a` that are
  39 /// added via implicit bounds.
  40 ///
  41 /// Each region here is guaranteed to be a key in the `indices`
  42 /// map. We use the "original" regions (i.e., the keys from the
  43 /// map, and not the values) because the code in
  44 /// `process_registered_region_obligations` has some special-cased
  45 /// logic expecting to see (e.g.) `ReStatic`, and if we supplied
  46 /// our special inference variable there, we would mess that up.
  47 type RegionBoundPairs<'tcx> = Vec<(ty::Region<'tcx>, GenericKind<'tcx>)>;
  48
  49 /// As part of computing the free region relations, we also have to
  50 /// normalize the input-output types, which we then need later. So we
  51 /// return those. This vector consists of first the input types and
  52 /// then the output type as the last element.
  53 type NormalizedInputsAndOutput<'tcx> = Vec<Ty<'tcx>>;
  54
  55 crate struct CreateResult<'tcx> {
  56     crate universal_region_relations: Frozen<UniversalRegionRelations<'tcx>>,
  57     crate region_bound_pairs: RegionBoundPairs<'tcx>,
  58     crate normalized_inputs_and_output: NormalizedInputsAndOutput<'tcx>,
  59 }
  60
  61 crate fn create<'tcx>(
  62     infcx: &InferCtxt<'_, 'tcx>,
  63     param_env: ty::ParamEnv<'tcx>,
  64     implicit_region_bound: Option<ty::Region<'tcx>>,
  65     universal_regions: &Rc<UniversalRegions<'tcx>>,
  66     constraints: &mut MirTypeckRegionConstraints<'tcx>,
  67 ) -> CreateResult<'tcx> {
  68     UniversalRegionRelationsBuilder {
  69         infcx,
  70         param_env,
  71         implicit_region_bound,
  72         constraints,
  73         universal_regions: universal_regions.clone(),
  74         region_bound_pairs: Vec::new(),
  75         relations: UniversalRegionRelations {
  76             universal_regions: universal_regions.clone(),
  77             outlives: Default::default(),
  78             inverse_outlives: Default::default(),
  79         },
  80     }
  81     .create()
  82 }
  83
  84 impl UniversalRegionRelations<'_> {
  85     /// Records in the `outlives_relation` (and
  86     /// `inverse_outlives_relation`) that `fr_a: fr_b`. Invoked by the
  87     /// builder below.
  88     fn relate_universal_regions(&mut self, fr_a: RegionVid, fr_b: RegionVid) {
  89         debug!("relate_universal_regions: fr_a={:?} outlives fr_b={:?}", fr_a, fr_b);
  90         self.outlives.add(fr_a, fr_b);
  91         self.inverse_outlives.add(fr_b, fr_a);
  92     }
  93
  94     /// Given two universal regions, returns the postdominating
  95     /// upper-bound (effectively the least upper bound).
  96     ///
  97     /// (See `TransitiveRelation::postdom_upper_bound` for details on
  98     /// the postdominating upper bound in general.)
  99     crate fn postdom_upper_bound(&self, fr1: RegionVid, fr2: RegionVid) -> RegionVid {
 100         assert!(self.universal_regions.is_universal_region(fr1));
 101         assert!(self.universal_regions.is_universal_region(fr2));
 102         self.inverse_outlives
 103             .postdom_upper_bound(fr1, fr2)
 104             .unwrap_or(self.universal_regions.fr_static)
 105     }
 106
 107     /// Finds an "upper bound" for `fr` that is not local. In other
 108     /// words, returns the smallest (*) known region `fr1` that (a)
 109     /// outlives `fr` and (b) is not local.
 110     ///
 111     /// (*) If there are multiple competing choices, we return all of them.
 112     crate fn non_local_upper_bounds<'a>(&'a self, fr: RegionVid) -> Vec<RegionVid> {
 113         debug!("non_local_upper_bound(fr={:?})", fr);
 114         let res = self.non_local_bounds(&self.inverse_outlives, fr);
 115         assert!(!res.is_empty(), "can't find an upper bound!?");
 116         res
 117     }
 118
 119     /// Returns the "postdominating" bound of the set of
 120     /// `non_local_upper_bounds` for the given region.
 121     crate fn non_local_upper_bound(&self, fr: RegionVid) -> RegionVid {
 122         let upper_bounds = self.non_local_upper_bounds(fr);
 123
 124         // In case we find more than one, reduce to one for
 125         // convenience.  This is to prevent us from generating more
 126         // complex constraints, but it will cause spurious errors.
 127         let post_dom = self.inverse_outlives.mutual_immediate_postdominator(upper_bounds);
 128
 129         debug!("non_local_bound: post_dom={:?}", post_dom);
 130
 131         post_dom
 132             .and_then(|post_dom| {
 133                 // If the mutual immediate postdom is not local, then
 134                 // there is no non-local result we can return.
 135                 if !self.universal_regions.is_local_free_region(post_dom) {
 136                     Some(post_dom)
 137                 } else {
 138                     None
 139                 }
 140             })
 141             .unwrap_or(self.universal_regions.fr_static)
 142     }
 143
 144     /// Finds a "lower bound" for `fr` that is not local. In other
 145     /// words, returns the largest (*) known region `fr1` that (a) is
 146     /// outlived by `fr` and (b) is not local.
 147     ///
 148     /// (*) If there are multiple competing choices, we pick the "postdominating"
 149     /// one. See `TransitiveRelation::postdom_upper_bound` for details.
 150     crate fn non_local_lower_bound(&self, fr: RegionVid) -> Option<RegionVid> {
 151         debug!("non_local_lower_bound(fr={:?})", fr);
 152         let lower_bounds = self.non_local_bounds(&self.outlives, fr);
 153
 154         // In case we find more than one, reduce to one for
 155         // convenience.  This is to prevent us from generating more
 156         // complex constraints, but it will cause spurious errors.
 157         let post_dom = self.outlives.mutual_immediate_postdominator(lower_bounds);
 158
 159         debug!("non_local_bound: post_dom={:?}", post_dom);
 160
 161         post_dom.and_then(|post_dom| {
 162             // If the mutual immediate postdom is not local, then
 163             // there is no non-local result we can return.
 164             if !self.universal_regions.is_local_free_region(post_dom) {
 165                 Some(post_dom)
 166             } else {
 167                 None
 168             }
 169         })
 170     }
 171
 172     /// Helper for `non_local_upper_bounds` and `non_local_lower_bounds`.
 173     /// Repeatedly invokes `postdom_parent` until we find something that is not
 174     /// local. Returns `None` if we never do so.
 175     fn non_local_bounds<'a>(
 176         &self,
 177         relation: &'a TransitiveRelation<RegionVid>,
 178         fr0: RegionVid,
 179     ) -> Vec<RegionVid> {
 180         // This method assumes that `fr0` is one of the universally
 181         // quantified region variables.
 182         assert!(self.universal_regions.is_universal_region(fr0));
 183
 184         let mut external_parents = vec![];
 185         let mut queue = vec![fr0];
 186
 187         // Keep expanding `fr` into its parents until we reach
 188         // non-local regions.
 189         while let Some(fr) = queue.pop() {
 190             if !self.universal_regions.is_local_free_region(fr) {
 191                 external_parents.push(fr);
 192                 continue;
 193             }
 194
 195             queue.extend(relation.parents(fr));
 196         }
 197
 198         debug!("non_local_bound: external_parents={:?}", external_parents);
 199
 200         external_parents
 201     }
 202
 203     /// Returns `true` if fr1 is known to outlive fr2.
 204     ///
 205     /// This will only ever be true for universally quantified regions.
 206     crate fn outlives(&self, fr1: RegionVid, fr2: RegionVid) -> bool {
 207         self.outlives.contains(fr1, fr2)
 208     }
 209
 210     /// Returns a vector of free regions `x` such that `fr1: x` is
 211     /// known to hold.
 212     crate fn regions_outlived_by(&self, fr1: RegionVid) -> Vec<RegionVid> {
 213         self.outlives.reachable_from(fr1)
 214     }
 215
 216     /// Returns the _non-transitive_ set of known `outlives` constraints between free regions.
 217     crate fn known_outlives(&self) -> impl Iterator<Item = (RegionVid, RegionVid)> + '_ {
 218         self.outlives.base_edges()
 219     }
 220 }
 221
 222 struct UniversalRegionRelationsBuilder<'this, 'tcx> {
 223     infcx: &'this InferCtxt<'this, 'tcx>,
 224     param_env: ty::ParamEnv<'tcx>,
 225     universal_regions: Rc<UniversalRegions<'tcx>>,
 226     implicit_region_bound: Option<ty::Region<'tcx>>,
 227     constraints: &'this mut MirTypeckRegionConstraints<'tcx>,
 228
 229     // outputs:
 230     relations: UniversalRegionRelations<'tcx>,
 231     region_bound_pairs: RegionBoundPairs<'tcx>,
 232 }
 233
 234 impl<'tcx> UniversalRegionRelationsBuilder<'_, 'tcx> {
 235     crate fn create(mut self) -> CreateResult<'tcx> {
 236         let unnormalized_input_output_tys = self
 237             .universal_regions
 238             .unnormalized_input_tys
 239             .iter()
 240             .cloned()
 241             .chain(Some(self.universal_regions.unnormalized_output_ty));
 242
 243         // For each of the input/output types:
 244         // - Normalize the type. This will create some region
 245         //   constraints, which we buffer up because we are
 246         //   not ready to process them yet.
 247         // - Then compute the implied bounds. This will adjust
 248         //   the `region_bound_pairs` and so forth.
 249         // - After this is done, we'll process the constraints, once
 250         //   the `relations` is built.
 251         let mut normalized_inputs_and_output =
 252             Vec::with_capacity(self.universal_regions.unnormalized_input_tys.len() + 1);
 253         let constraint_sets: Vec<_> = unnormalized_input_output_tys
 254             .flat_map(|ty| {
 255                 debug!("build: input_or_output={:?}", ty);
 256                 // We add implied bounds from both the unnormalized and normalized ty
 257                 // See issue #87748
 258                 let TypeOpOutput { output: norm_ty, constraints: constraints1, .. } = self
 259                     .param_env
 260                     .and(type_op::normalize::Normalize::new(ty))
 261                     .fully_perform(self.infcx)
 262                     .unwrap_or_else(|_| {
 263                         self.infcx
 264                             .tcx
 265                             .sess
 266                             .delay_span_bug(DUMMY_SP, &format!("failed to normalize {:?}", ty));
 267                         TypeOpOutput {
 268                             output: self.infcx.tcx.ty_error(),
 269                             constraints: None,
 270                             error_info: None,
 271                         }
 272                     });
 273                 // Note: we need this in examples like
 274                 // ```
 275                 // trait Foo {
 276                 //   type Bar;
 277                 //   fn foo(&self) -> &Self::Bar;
 278                 // }
 279                 // impl Foo for () {
 280                 //   type Bar = ();
 281                 //   fn foo(&self) ->&() {}
 282                 // }
 283                 // ```
 284                 // Both &Self::Bar and &() are WF
 285                 let constraints_implied = self.add_implied_bounds(norm_ty);
 286                 normalized_inputs_and_output.push(norm_ty);
 287                 constraints1.into_iter().chain(constraints_implied)
 288             })
 289             .collect();
 290
 291         // Insert the facts we know from the predicates. Why? Why not.
 292         let param_env = self.param_env;
 293         self.add_outlives_bounds(outlives::explicit_outlives_bounds(param_env));
 294
 295         // Finally:
 296         // - outlives is reflexive, so `'r: 'r` for every region `'r`
 297         // - `'static: 'r` for every region `'r`
 298         // - `'r: 'fn_body` for every (other) universally quantified
 299         //   region `'r`, all of which are provided by our caller
 300         let fr_static = self.universal_regions.fr_static;
 301         let fr_fn_body = self.universal_regions.fr_fn_body;
 302         for fr in self.universal_regions.universal_regions() {
 303             debug!("build: relating free region {:?} to itself and to 'static", fr);
 304             self.relations.relate_universal_regions(fr, fr);
 305             self.relations.relate_universal_regions(fr_static, fr);
 306             self.relations.relate_universal_regions(fr, fr_fn_body);
 307         }
 308
 309         for data in &constraint_sets {
 310             constraint_conversion::ConstraintConversion::new(
 311                 self.infcx,
 312                 &self.universal_regions,
 313                 &self.region_bound_pairs,
 314                 self.implicit_region_bound,
 315                 self.param_env,
 316                 Locations::All(DUMMY_SP),
 317                 ConstraintCategory::Internal,
 318                 &mut self.constraints,
 319             )
 320             .convert_all(data);
 321         }
 322
 323         CreateResult {
 324             universal_region_relations: Frozen::freeze(self.relations),
 325             region_bound_pairs: self.region_bound_pairs,
 326             normalized_inputs_and_output,
 327         }
 328     }
 329
 330     /// Update the type of a single local, which should represent
 331     /// either the return type of the MIR or one of its arguments. At
 332     /// the same time, compute and add any implied bounds that come
 333     /// from this local.
 334     fn add_implied_bounds(&mut self, ty: Ty<'tcx>) -> Option<Rc<QueryRegionConstraints<'tcx>>> {
 335         debug!("add_implied_bounds(ty={:?})", ty);
 336         let TypeOpOutput { output: bounds, constraints, .. } = self
 337             .param_env
 338             .and(type_op::implied_outlives_bounds::ImpliedOutlivesBounds { ty })
 339             .fully_perform(self.infcx)
 340             .unwrap_or_else(|_| bug!("failed to compute implied bounds {:?}", ty));
 341         self.add_outlives_bounds(bounds);
 342         constraints
 343     }
 344
 345     /// Registers the `OutlivesBound` items from `outlives_bounds` in
 346     /// the outlives relation as well as the region-bound pairs
 347     /// listing.
 348     fn add_outlives_bounds<I>(&mut self, outlives_bounds: I)
 349     where
 350         I: IntoIterator<Item = OutlivesBound<'tcx>>,
 351     {
 352         for outlives_bound in outlives_bounds {
 353             debug!("add_outlives_bounds(bound={:?})", outlives_bound);
 354
 355             match outlives_bound {
 356                 OutlivesBound::RegionSubRegion(r1, r2) => {
 357                     // `where Type:` is lowered to `where Type: 'empty` so that
 358                     // we check `Type` is well formed, but there's no use for
 359                     // this bound here.
 360                     if r1.is_empty() {
 361                         return;
 362                     }
 363
 364                     // The bound says that `r1 <= r2`; we store `r2: r1`.
 365                     let r1 = self.universal_regions.to_region_vid(r1);
 366                     let r2 = self.universal_regions.to_region_vid(r2);
 367                     self.relations.relate_universal_regions(r2, r1);
 368                 }
 369
 370                 OutlivesBound::RegionSubParam(r_a, param_b) => {
 371                     self.region_bound_pairs.push((r_a, GenericKind::Param(param_b)));
 372                 }
 373
 374                 OutlivesBound::RegionSubProjection(r_a, projection_b) => {
 375                     self.region_bound_pairs.push((r_a, GenericKind::Projection(projection_b)));
 376                 }
 377             }
 378         }
 379     }
 380 }