compiler/rustc_infer/src/infer/higher_ranked/mod.rs

   1 //! Helper routines for higher-ranked things. See the `doc` module at
   2 //! the end of the file for details.
   3
   4 use super::combine::CombineFields;
   5 use super::{HigherRankedType, InferCtxt};
   6
   7 use crate::infer::CombinedSnapshot;
   8 use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
   9 use rustc_middle::ty::{self, Binder, TypeFoldable};
  10
  11 impl<'a, 'tcx> CombineFields<'a, 'tcx> {
  12     #[instrument(skip(self), level = "debug")]
  13     pub fn higher_ranked_sub<T>(
  14         &mut self,
  15         a: Binder<'tcx, T>,
  16         b: Binder<'tcx, T>,
  17         a_is_expected: bool,
  18     ) -> RelateResult<'tcx, Binder<'tcx, T>>
  19     where
  20         T: Relate<'tcx>,
  21     {
  22         // Rather than checking the subtype relationship between `a` and `b`
  23         // as-is, we need to do some extra work here in order to make sure
  24         // that function subtyping works correctly with respect to regions
  25         //
  26         // Note: this is a subtle algorithm.  For a full explanation, please see
  27         // the rustc dev guide:
  28         // <https://rustc-dev-guide.rust-lang.org/borrow_check/region_inference/placeholders_and_universes.html>
  29
  30         let span = self.trace.cause.span;
  31
  32         self.infcx.commit_if_ok(|_| {
  33             // First, we instantiate each bound region in the supertype with a
  34             // fresh placeholder region.
  35             let b_prime = self.infcx.replace_bound_vars_with_placeholders(b);
  36
  37             // Next, we instantiate each bound region in the subtype
  38             // with a fresh region variable. These region variables --
  39             // but no other pre-existing region variables -- can name
  40             // the placeholders.
  41             let (a_prime, _) =
  42                 self.infcx.replace_bound_vars_with_fresh_vars(span, HigherRankedType, a);
  43
  44             debug!("a_prime={:?}", a_prime);
  45             debug!("b_prime={:?}", b_prime);
  46
  47             // Compare types now that bound regions have been replaced.
  48             let result = self.sub(a_is_expected).relate(a_prime, b_prime)?;
  49
  50             debug!("higher_ranked_sub: OK result={:?}", result);
  51
  52             // We related `a_prime` and `b_prime`, which just had any bound vars
  53             // replaced with placeholders or infer vars, respectively. Relating
  54             // them should not introduce new bound vars.
  55             Ok(ty::Binder::dummy(result))
  56         })
  57     }
  58 }
  59
  60 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
  61     /// Replaces all regions (resp. types) bound by `binder` with placeholder
  62     /// regions (resp. types) and return a map indicating which bound-region
  63     /// placeholder region. This is the first step of checking subtyping
  64     /// when higher-ranked things are involved.
  65     ///
  66     /// **Important:** You have to be careful to not leak these placeholders,
  67     /// for more information about how placeholders and HRTBs work, see
  68     /// the [rustc dev guide].
  69     ///
  70     /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
  71     pub fn replace_bound_vars_with_placeholders<T>(&self, binder: ty::Binder<'tcx, T>) -> T
  72     where
  73         T: TypeFoldable<'tcx>,
  74     {
  75         // Figure out what the next universe will be, but don't actually create
  76         // it until after we've done the substitution (in particular there may
  77         // be no bound variables). This is a performance optimization, since the
  78         // leak check for example can be skipped if no new universes are created
  79         // (i.e., if there are no placeholders).
  80         let next_universe = self.universe().next_universe();
  81
  82         let fld_r = |br: ty::BoundRegion| {
  83             self.tcx.mk_region(ty::RePlaceholder(ty::PlaceholderRegion {
  84                 universe: next_universe,
  85                 name: br.kind,
  86             }))
  87         };
  88
  89         let fld_t = |bound_ty: ty::BoundTy| {
  90             self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
  91                 universe: next_universe,
  92                 name: bound_ty.var,
  93             }))
  94         };
  95
  96         let fld_c = |bound_var: ty::BoundVar, ty| {
  97             self.tcx.mk_const(ty::ConstS {
  98                 val: ty::ConstKind::Placeholder(ty::PlaceholderConst {
  99                     universe: next_universe,
 100                     name: ty::BoundConst { var: bound_var, ty },
 101                 }),
 102                 ty,
 103             })
 104         };
 105
 106         let (result, map) = self.tcx.replace_bound_vars(binder, fld_r, fld_t, fld_c);
 107
 108         // If there were higher-ranked regions to replace, then actually create
 109         // the next universe (this avoids needlessly creating universes).
 110         if !map.is_empty() {
 111             let n_u = self.create_next_universe();
 112             assert_eq!(n_u, next_universe);
 113         }
 114
 115         debug!(
 116             "replace_bound_vars_with_placeholders(\
 117              next_universe={:?}, \
 118              result={:?}, \
 119              map={:?})",
 120             next_universe, result, map,
 121         );
 122
 123         result
 124     }
 125
 126     /// See `infer::region_constraints::RegionConstraintCollector::leak_check`.
 127     pub fn leak_check(
 128         &self,
 129         overly_polymorphic: bool,
 130         snapshot: &CombinedSnapshot<'_, 'tcx>,
 131     ) -> RelateResult<'tcx, ()> {
 132         // If the user gave `-Zno-leak-check`, or we have been
 133         // configured to skip the leak check, then skip the leak check
 134         // completely. The leak check is deprecated. Any legitimate
 135         // subtyping errors that it would have caught will now be
 136         // caught later on, during region checking. However, we
 137         // continue to use it for a transition period.
 138         if self.tcx.sess.opts.debugging_opts.no_leak_check || self.skip_leak_check.get() {
 139             return Ok(());
 140         }
 141
 142         self.inner.borrow_mut().unwrap_region_constraints().leak_check(
 143             self.tcx,
 144             overly_polymorphic,
 145             self.universe(),
 146             snapshot,
 147         )
 148     }
 149 }