src/librustc/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 crate::ty::relate::{Relate, RelateResult, TypeRelation};
   9 use crate::ty::{self, Binder, TypeFoldable};
  10 use crate::mir::interpret::ConstValue;
  11
  12 impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
  13     pub fn higher_ranked_sub<T>(
  14         &mut self,
  15         a: &Binder<T>,
  16         b: &Binder<T>,
  17         a_is_expected: bool,
  18     ) -> RelateResult<'tcx, Binder<T>>
  19     where
  20         T: Relate<'tcx>,
  21     {
  22         debug!("higher_ranked_sub(a={:?}, b={:?})", a, b);
  23
  24         // Rather than checking the subtype relationship between `a` and `b`
  25         // as-is, we need to do some extra work here in order to make sure
  26         // that function subtyping works correctly with respect to regions
  27         //
  28         // Note: this is a subtle algorithm.  For a full explanation,
  29         // please see the large comment at the end of the file in the (inlined) module
  30         // `doc`.
  31
  32         let span = self.trace.cause.span;
  33
  34         return self.infcx.commit_if_ok(|snapshot| {
  35             // First, we instantiate each bound region in the supertype with a
  36             // fresh placeholder region.
  37             let (b_prime, placeholder_map) = self.infcx.replace_bound_vars_with_placeholders(b);
  38
  39             // Next, we instantiate each bound region in the subtype
  40             // with a fresh region variable. These region variables --
  41             // but no other pre-existing region variables -- can name
  42             // the placeholders.
  43             let (a_prime, _) =
  44                 self.infcx
  45                     .replace_bound_vars_with_fresh_vars(span, HigherRankedType, a);
  46
  47             debug!("a_prime={:?}", a_prime);
  48             debug!("b_prime={:?}", b_prime);
  49
  50             // Compare types now that bound regions have been replaced.
  51             let result = self.sub(a_is_expected).relate(&a_prime, &b_prime)?;
  52
  53             self.infcx
  54                 .leak_check(!a_is_expected, &placeholder_map, snapshot)?;
  55
  56             debug!("higher_ranked_sub: OK result={:?}", result);
  57
  58             Ok(ty::Binder::bind(result))
  59         });
  60     }
  61 }
  62
  63 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
  64     /// Replaces all regions (resp. types) bound by `binder` with placeholder
  65     /// regions (resp. types) and return a map indicating which bound-region
  66     /// placeholder region. This is the first step of checking subtyping
  67     /// when higher-ranked things are involved.
  68     ///
  69     /// **Important:** you must call this function from within a snapshot.
  70     /// Moreover, before committing the snapshot, you must eventually call
  71     /// either `plug_leaks` or `pop_placeholders` to remove the placeholder
  72     /// regions. If you rollback the snapshot (or are using a probe), then
  73     /// the pop occurs as part of the rollback, so an explicit call is not
  74     /// needed (but is also permitted).
  75     ///
  76     /// For more information about how placeholders and HRTBs work, see
  77     /// the [rustc guide].
  78     ///
  79     /// [rustc guide]: https://rust-lang.github.io/rustc-guide/traits/hrtb.html
  80     pub fn replace_bound_vars_with_placeholders<T>(
  81         &self,
  82         binder: &ty::Binder<T>,
  83     ) -> (T, PlaceholderMap<'tcx>)
  84     where
  85         T: TypeFoldable<'tcx>,
  86     {
  87         let next_universe = self.create_next_universe();
  88
  89         let fld_r = |br| {
  90             self.tcx.mk_region(ty::RePlaceholder(ty::PlaceholderRegion {
  91                 universe: next_universe,
  92                 name: br,
  93             }))
  94         };
  95
  96         let fld_t = |bound_ty: ty::BoundTy| {
  97             self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
  98                 universe: next_universe,
  99                 name: bound_ty.var,
 100             }))
 101         };
 102
 103         let fld_c = |bound_var: ty::BoundVar, ty| {
 104             self.tcx.mk_lazy_const(ty::LazyConst::Evaluated(
 105                 ty::Const {
 106                     val: ConstValue::Placeholder(ty::PlaceholderConst {
 107                         universe: next_universe,
 108                         name: bound_var,
 109                     }),
 110                     ty,
 111                 }
 112             ))
 113         };
 114
 115         let (result, map) = self.tcx.replace_bound_vars(binder, fld_r, fld_t, fld_c);
 116
 117         debug!(
 118             "replace_bound_vars_with_placeholders(\
 119              next_universe={:?}, \
 120              binder={:?}, \
 121              result={:?}, \
 122              map={:?})",
 123             next_universe, binder, result, map,
 124         );
 125
 126         (result, map)
 127     }
 128
 129     /// See `infer::region_constraints::RegionConstraintCollector::leak_check`.
 130     pub fn leak_check(
 131         &self,
 132         overly_polymorphic: bool,
 133         placeholder_map: &PlaceholderMap<'tcx>,
 134         snapshot: &CombinedSnapshot<'_, 'tcx>,
 135     ) -> RelateResult<'tcx, ()> {
 136         self.borrow_region_constraints()
 137             .leak_check(self.tcx, overly_polymorphic, placeholder_map, snapshot)
 138     }
 139 }