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 use crate::infer::CombinedSnapshot;
   7 use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
   8 use rustc_middle::ty::{self, Binder, TypeFoldable};
   9
  10 impl<'a, 'tcx> CombineFields<'a, 'tcx> {
  11     /// Checks whether `for<..> sub <: for<..> sup` holds.
  12     ///
  13     /// For this to hold, **all** instantiations of the super type
  14     /// have to be a super type of **at least one** instantiation of
  15     /// the subtype.
  16     ///
  17     /// This is implemented by first entering a new universe.
  18     /// We then replace all bound variables in `sup` with placeholders,
  19     /// and all bound variables in `sup` with inference vars.
  20     /// We can then just relate the two resulting types as normal.
  21     ///
  22     /// Note: this is a subtle algorithm. For a full explanation, please see
  23     /// the [rustc dev guide][rd]
  24     ///
  25     /// [rd]: https://rustc-dev-guide.rust-lang.org/borrow_check/region_inference/placeholders_and_universes.html
  26     #[instrument(skip(self), level = "debug")]
  27     pub fn higher_ranked_sub<T>(
  28         &mut self,
  29         sub: Binder<'tcx, T>,
  30         sup: Binder<'tcx, T>,
  31         sub_is_expected: bool,
  32     ) -> RelateResult<'tcx, ()>
  33     where
  34         T: Relate<'tcx>,
  35     {
  36         let span = self.trace.cause.span;
  37
  38         self.infcx.commit_if_ok(|_| {
  39             // First, we instantiate each bound region in the supertype with a
  40             // fresh placeholder region. Note that this automatically creates
  41             // a new universe if needed.
  42             let sup_prime = self.infcx.replace_bound_vars_with_placeholders(sup);
  43
  44             // Next, we instantiate each bound region in the subtype
  45             // with a fresh region variable. These region variables --
  46             // but no other pre-existing region variables -- can name
  47             // the placeholders.
  48             let sub_prime =
  49                 self.infcx.replace_bound_vars_with_fresh_vars(span, HigherRankedType, sub);
  50
  51             debug!("a_prime={:?}", sub_prime);
  52             debug!("b_prime={:?}", sup_prime);
  53
  54             // Compare types now that bound regions have been replaced.
  55             let result = self.sub(sub_is_expected).relate(sub_prime, sup_prime)?;
  56
  57             debug!("higher_ranked_sub: OK result={result:?}");
  58             // NOTE: returning the result here would be dangerous as it contains
  59             // placeholders which **must not** be named afterwards.
  60             Ok(())
  61         })
  62     }
  63 }
  64
  65 impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
  66     /// Replaces all bound variables (lifetimes, types, and constants) bound by
  67     /// `binder` with placeholder variables in a new universe. This means that the
  68     /// new placeholders can only be named by inference variables created after
  69     /// this method has been called.
  70     ///
  71     /// This is the first step of checking subtyping when higher-ranked things are involved.
  72     /// For more details visit the relevant sections of the [rustc dev guide].
  73     ///
  74     /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
  75     #[instrument(level = "debug", skip(self))]
  76     pub fn replace_bound_vars_with_placeholders<T>(&self, binder: ty::Binder<'tcx, T>) -> T
  77     where
  78         T: TypeFoldable<'tcx> + Copy,
  79     {
  80         if let Some(inner) = binder.no_bound_vars() {
  81             return inner;
  82         }
  83
  84         let next_universe = self.create_next_universe();
  85
  86         let fld_r = |br: ty::BoundRegion| {
  87             self.tcx.mk_region(ty::RePlaceholder(ty::PlaceholderRegion {
  88                 universe: next_universe,
  89                 name: br.kind,
  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::ConstS {
 102                 val: ty::ConstKind::Placeholder(ty::PlaceholderConst {
 103                     universe: next_universe,
 104                     name: ty::BoundConst { var: bound_var, ty },
 105                 }),
 106                 ty,
 107             })
 108         };
 109
 110         let result = self.tcx.replace_bound_vars_uncached(binder, fld_r, fld_t, fld_c);
 111         debug!(?next_universe, ?result);
 112         result
 113     }
 114
 115     /// See [RegionConstraintCollector::leak_check][1].
 116     ///
 117     /// [1]: crate::infer::region_constraints::RegionConstraintCollector::leak_check
 118     pub fn leak_check(
 119         &self,
 120         overly_polymorphic: bool,
 121         snapshot: &CombinedSnapshot<'_, 'tcx>,
 122     ) -> RelateResult<'tcx, ()> {
 123         // If the user gave `-Zno-leak-check`, or we have been
 124         // configured to skip the leak check, then skip the leak check
 125         // completely. The leak check is deprecated. Any legitimate
 126         // subtyping errors that it would have caught will now be
 127         // caught later on, during region checking. However, we
 128         // continue to use it for a transition period.
 129         if self.tcx.sess.opts.debugging_opts.no_leak_check || self.skip_leak_check.get() {
 130             return Ok(());
 131         }
 132
 133         self.inner.borrow_mut().unwrap_region_constraints().leak_check(
 134             self.tcx,
 135             overly_polymorphic,
 136             self.universe(),
 137             snapshot,
 138         )
 139     }
 140 }