src/librustc_infer/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, PlaceholderMap};
   6
   7 use crate::infer::CombinedSnapshot;
   8 use rustc::ty::relate::{Relate, RelateResult, TypeRelation};
   9 use rustc::ty::{self, Binder, TypeFoldable};
  10
  11 impl<'a, 'tcx> CombineFields<'a, 'tcx> {
  12     pub fn higher_ranked_sub<T>(
  13         &mut self,
  14         a: &Binder<T>,
  15         b: &Binder<T>,
  16         a_is_expected: bool,
  17     ) -> RelateResult<'tcx, Binder<T>>
  18     where
  19         T: Relate<'tcx>,
  20     {
  21         debug!("higher_ranked_sub(a={:?}, b={:?})", a, b);
  22
  23         // Rather than checking the subtype relationship between `a` and `b`
  24         // as-is, we need to do some extra work here in order to make sure
  25         // that function subtyping works correctly with respect to regions
  26         //
  27         // Note: this is a subtle algorithm.  For a full explanation,
  28         // please see the large comment at the end of the file in the (inlined) module
  29         // `doc`.
  30
  31         let span = self.trace.cause.span;
  32
  33         return self.infcx.commit_if_ok(|snapshot| {
  34             // First, we instantiate each bound region in the supertype with a
  35             // fresh placeholder region.
  36             let (b_prime, placeholder_map) = self.infcx.replace_bound_vars_with_placeholders(b);
  37
  38             // Next, we instantiate each bound region in the subtype
  39             // with a fresh region variable. These region variables --
  40             // but no other pre-existing region variables -- can name
  41             // the placeholders.
  42             let (a_prime, _) =
  43                 self.infcx.replace_bound_vars_with_fresh_vars(span, HigherRankedType, a);
  44
  45             debug!("a_prime={:?}", a_prime);
  46             debug!("b_prime={:?}", b_prime);
  47
  48             // Compare types now that bound regions have been replaced.
  49             let result = self.sub(a_is_expected).relate(&a_prime, &b_prime)?;
  50
  51             self.infcx.leak_check(!a_is_expected, &placeholder_map, snapshot)?;
  52
  53             debug!("higher_ranked_sub: OK result={:?}", result);
  54
  55             Ok(ty::Binder::bind(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 must call this function from within a snapshot.
  67     /// Moreover, before committing the snapshot, you must eventually call
  68     /// either `plug_leaks` or `pop_placeholders` to remove the placeholder
  69     /// regions. If you rollback the snapshot (or are using a probe), then
  70     /// the pop occurs as part of the rollback, so an explicit call is not
  71     /// needed (but is also permitted).
  72     ///
  73     /// For more information about how placeholders and HRTBs work, see
  74     /// the [rustc dev guide].
  75     ///
  76     /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
  77     pub fn replace_bound_vars_with_placeholders<T>(
  78         &self,
  79         binder: &ty::Binder<T>,
  80     ) -> (T, PlaceholderMap<'tcx>)
  81     where
  82         T: TypeFoldable<'tcx>,
  83     {
  84         let next_universe = self.create_next_universe();
  85
  86         let fld_r = |br| {
  87             self.tcx.mk_region(ty::RePlaceholder(ty::PlaceholderRegion {
  88                 universe: next_universe,
  89                 name: br,
  90             }))
  91         };
  92
  93         let fld_t = |bound_ty: ty::BoundTy| {
  94             self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
  95                 universe: next_universe,
  96                 name: bound_ty.var,
  97             }))
  98         };
  99
 100         let fld_c = |bound_var: ty::BoundVar, ty| {
 101             self.tcx.mk_const(ty::Const {
 102                 val: ty::ConstKind::Placeholder(ty::PlaceholderConst {
 103                     universe: next_universe,
 104                     name: bound_var,
 105                 }),
 106                 ty,
 107             })
 108         };
 109
 110         let (result, map) = self.tcx.replace_bound_vars(binder, fld_r, fld_t, fld_c);
 111
 112         debug!(
 113             "replace_bound_vars_with_placeholders(\
 114              next_universe={:?}, \
 115              binder={:?}, \
 116              result={:?}, \
 117              map={:?})",
 118             next_universe, binder, result, map,
 119         );
 120
 121         (result, map)
 122     }
 123
 124     /// See `infer::region_constraints::RegionConstraintCollector::leak_check`.
 125     pub fn leak_check(
 126         &self,
 127         overly_polymorphic: bool,
 128         placeholder_map: &PlaceholderMap<'tcx>,
 129         snapshot: &CombinedSnapshot<'_, 'tcx>,
 130     ) -> RelateResult<'tcx, ()> {
 131         // If the user gave `-Zno-leak-check`, or we have been
 132         // configured to skip the leak check, then skip the leak check
 133         // completely. The leak check is deprecated. Any legitimate
 134         // subtyping errors that it would have caught will now be
 135         // caught later on, during region checking. However, we
 136         // continue to use it for a transition period.
 137         if self.tcx.sess.opts.debugging_opts.no_leak_check || self.skip_leak_check.get() {
 138             return Ok(());
 139         }
 140
 141         self.inner.borrow_mut().unwrap_region_constraints().leak_check(
 142             self.tcx,
 143             overly_polymorphic,
 144             placeholder_map,
 145             snapshot,
 146         )
 147     }
 148 }