compiler/rustc_infer/src/infer/outlives/test_type_match.rs

   1 use std::collections::hash_map::Entry;
   2
   3 use rustc_data_structures::fx::FxHashMap;
   4 use rustc_middle::ty::TypeVisitable;
   5 use rustc_middle::ty::{
   6     self,
   7     error::TypeError,
   8     relate::{self, Relate, RelateResult, TypeRelation},
   9     Ty, TyCtxt,
  10 };
  11
  12 use crate::infer::region_constraints::VerifyIfEq;
  13
  14 /// Given a "verify-if-eq" type test like:
  15 ///
  16 ///     exists<'a...> {
  17 ///         verify_if_eq(some_type, bound_region)
  18 ///     }
  19 ///
  20 /// and the type `test_ty` that the type test is being tested against,
  21 /// returns:
  22 ///
  23 /// * `None` if `some_type` cannot be made equal to `test_ty`,
  24 ///   no matter the values of the variables in `exists`.
  25 /// * `Some(r)` with a suitable bound (typically the value of `bound_region`, modulo
  26 ///   any bound existential variables, which will be substituted) for the
  27 ///   type under test.
  28 ///
  29 /// NB: This function uses a simplistic, syntactic version of type equality.
  30 /// In other words, it may spuriously return `None` even if the type-under-test
  31 /// is in fact equal to `some_type`. In practice, though, this is used on types
  32 /// that are either projections like `T::Item` or `T` and it works fine, but it
  33 /// could have trouble when complex types with higher-ranked binders and the
  34 /// like are used. This is a particular challenge since this function is invoked
  35 /// very late in inference and hence cannot make use of the normal inference
  36 /// machinery.
  37 #[tracing::instrument(level = "debug", skip(tcx, param_env))]
  38 pub fn extract_verify_if_eq<'tcx>(
  39     tcx: TyCtxt<'tcx>,
  40     param_env: ty::ParamEnv<'tcx>,
  41     verify_if_eq_b: &ty::Binder<'tcx, VerifyIfEq<'tcx>>,
  42     test_ty: Ty<'tcx>,
  43 ) -> Option<ty::Region<'tcx>> {
  44     assert!(!verify_if_eq_b.has_escaping_bound_vars());
  45     let mut m = Match::new(tcx, param_env);
  46     let verify_if_eq = verify_if_eq_b.skip_binder();
  47     m.relate(verify_if_eq.ty, test_ty).ok()?;
  48
  49     if let ty::RegionKind::ReLateBound(depth, br) = verify_if_eq.bound.kind() {
  50         assert!(depth == ty::INNERMOST);
  51         match m.map.get(&br) {
  52             Some(&r) => Some(r),
  53             None => {
  54                 // If there is no mapping, then this region is unconstrained.
  55                 // In that case, we escalate to `'static`.
  56                 Some(tcx.lifetimes.re_static)
  57             }
  58         }
  59     } else {
  60         // The region does not contain any bound variables, so we don't need
  61         // to do any substitution.
  62         //
  63         // Example:
  64         //
  65         // for<'a> <T as Foo<'a>>::Item: 'b
  66         //
  67         // In this case, we've now matched and found a value for
  68         // `'a`, but it doesn't affect the bound `'b`.
  69         Some(verify_if_eq.bound)
  70     }
  71 }
  72
  73 /// True if a (potentially higher-ranked) outlives
  74 #[tracing::instrument(level = "debug", skip(tcx, param_env))]
  75 pub(super) fn can_match_erased_ty<'tcx>(
  76     tcx: TyCtxt<'tcx>,
  77     param_env: ty::ParamEnv<'tcx>,
  78     outlives_predicate: ty::Binder<'tcx, ty::TypeOutlivesPredicate<'tcx>>,
  79     erased_ty: Ty<'tcx>,
  80 ) -> bool {
  81     assert!(!outlives_predicate.has_escaping_bound_vars());
  82     let erased_outlives_predicate = tcx.erase_regions(outlives_predicate);
  83     let outlives_ty = erased_outlives_predicate.skip_binder().0;
  84     if outlives_ty == erased_ty {
  85         // pointless micro-optimization
  86         true
  87     } else {
  88         Match::new(tcx, param_env).relate(outlives_ty, erased_ty).is_ok()
  89     }
  90 }
  91
  92 struct Match<'tcx> {
  93     tcx: TyCtxt<'tcx>,
  94     param_env: ty::ParamEnv<'tcx>,
  95     pattern_depth: ty::DebruijnIndex,
  96     map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>,
  97 }
  98
  99 impl<'tcx> Match<'tcx> {
 100     fn new(tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Match<'tcx> {
 101         Match { tcx, param_env, pattern_depth: ty::INNERMOST, map: FxHashMap::default() }
 102     }
 103 }
 104
 105 impl<'tcx> Match<'tcx> {
 106     /// Creates the "Error" variant that signals "no match".
 107     fn no_match<T>(&self) -> RelateResult<'tcx, T> {
 108         Err(TypeError::Mismatch)
 109     }
 110
 111     /// Binds the pattern variable `br` to `value`; returns an `Err` if the pattern
 112     /// is already bound to a different value.
 113     #[tracing::instrument(level = "debug", skip(self))]
 114     fn bind(
 115         &mut self,
 116         br: ty::BoundRegion,
 117         value: ty::Region<'tcx>,
 118     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 119         match self.map.entry(br) {
 120             Entry::Occupied(entry) => {
 121                 if *entry.get() == value {
 122                     Ok(value)
 123                 } else {
 124                     self.no_match()
 125                 }
 126             }
 127             Entry::Vacant(entry) => {
 128                 entry.insert(value);
 129                 Ok(value)
 130             }
 131         }
 132     }
 133 }
 134
 135 impl<'tcx> TypeRelation<'tcx> for Match<'tcx> {
 136     fn tag(&self) -> &'static str {
 137         "Match"
 138     }
 139     fn tcx(&self) -> TyCtxt<'tcx> {
 140         self.tcx
 141     }
 142     fn param_env(&self) -> ty::ParamEnv<'tcx> {
 143         self.param_env
 144     }
 145     fn a_is_expected(&self) -> bool {
 146         true
 147     } // irrelevant
 148
 149     fn relate_with_variance<T: Relate<'tcx>>(
 150         &mut self,
 151         _: ty::Variance,
 152         _: ty::VarianceDiagInfo<'tcx>,
 153         a: T,
 154         b: T,
 155     ) -> RelateResult<'tcx, T> {
 156         self.relate(a, b)
 157     }
 158
 159     #[instrument(skip(self), level = "debug")]
 160     fn regions(
 161         &mut self,
 162         pattern: ty::Region<'tcx>,
 163         value: ty::Region<'tcx>,
 164     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 165         debug!("self.pattern_depth = {:?}", self.pattern_depth);
 166         if let ty::RegionKind::ReLateBound(depth, br) = pattern.kind() && depth == self.pattern_depth {
 167             self.bind(br, value)
 168         } else if pattern == value {
 169             Ok(pattern)
 170         } else {
 171             self.no_match()
 172         }
 173     }
 174
 175     #[instrument(skip(self), level = "debug")]
 176     fn tys(&mut self, pattern: Ty<'tcx>, value: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
 177         if pattern == value { Ok(pattern) } else { relate::super_relate_tys(self, pattern, value) }
 178     }
 179
 180     #[instrument(skip(self), level = "debug")]
 181     fn consts(
 182         &mut self,
 183         pattern: ty::Const<'tcx>,
 184         value: ty::Const<'tcx>,
 185     ) -> RelateResult<'tcx, ty::Const<'tcx>> {
 186         debug!("{}.consts({:?}, {:?})", self.tag(), pattern, value);
 187         if pattern == value {
 188             Ok(pattern)
 189         } else {
 190             relate::super_relate_consts(self, pattern, value)
 191         }
 192     }
 193
 194     fn binders<T>(
 195         &mut self,
 196         pattern: ty::Binder<'tcx, T>,
 197         value: ty::Binder<'tcx, T>,
 198     ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
 199     where
 200         T: Relate<'tcx>,
 201     {
 202         self.pattern_depth.shift_in(1);
 203         let result = Ok(pattern.rebind(self.relate(pattern.skip_binder(), value.skip_binder())?));
 204         self.pattern_depth.shift_out(1);
 205         result
 206     }
 207 }