1 //! Helper routines for higher-ranked things. See the `doc` module at
2 //! the end of the file for details.
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};
11 impl<'a, 'tcx> CombineFields<'a, 'tcx> {
12 /// Checks whether `for<..> sub <: for<..> sup` holds.
14 /// For this to hold, **all** instantiations of the super type
15 /// have to be a super type of **at least one** instantiation of
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.
23 /// Note: this is a subtle algorithm. For a full explanation, please see
24 /// the [rustc dev guide][rd]
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>(
32 sub_is_expected: bool,
33 ) -> RelateResult<'tcx, ()>
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);
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
47 let sub_prime = self.infcx.replace_bound_vars_with_fresh_vars(span, HigherRankedType, sub);
49 debug!("a_prime={:?}", sub_prime);
50 debug!("b_prime={:?}", sup_prime);
52 // Compare types now that bound regions have been replaced.
53 let result = self.sub(sub_is_expected).relate(sub_prime, sup_prime)?;
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.
62 impl<'tcx> InferCtxt<'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.
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].
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
75 T: TypeFoldable<'tcx> + Copy,
77 if let Some(inner) = binder.no_bound_vars() {
81 let next_universe = self.create_next_universe();
83 let delegate = FnMutDelegate {
84 regions: &mut |br: ty::BoundRegion| {
85 self.tcx.mk_region(ty::RePlaceholder(ty::PlaceholderRegion {
86 universe: next_universe,
90 types: &mut |bound_ty: ty::BoundTy| {
91 self.tcx.mk_ty(ty::Placeholder(ty::PlaceholderType {
92 universe: next_universe,
96 consts: &mut |bound_var: ty::BoundVar, ty| {
98 .mk_const(ty::PlaceholderConst { universe: next_universe, name: bound_var }, ty)
102 debug!(?next_universe);
103 self.tcx.replace_bound_vars_uncached(binder, delegate)
106 /// See [RegionConstraintCollector::leak_check][1].
108 /// [1]: crate::infer::region_constraints::RegionConstraintCollector::leak_check
111 overly_polymorphic: bool,
112 snapshot: &CombinedSnapshot<'tcx>,
113 ) -> RelateResult<'tcx, ()> {
114 // If the user gave `-Zno-leak-check`, or we have been
115 // configured to skip the leak check, then skip the leak check
116 // completely. The leak check is deprecated. Any legitimate
117 // subtyping errors that it would have caught will now be
118 // caught later on, during region checking. However, we
119 // continue to use it for a transition period.
120 if self.tcx.sess.opts.unstable_opts.no_leak_check || self.skip_leak_check.get() {
124 self.inner.borrow_mut().unwrap_region_constraints().leak_check(