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