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