Split Bound into Canonical and Bound

4 files changed, 46 insertions, 105 deletions

diff --git a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
index 3c5e4a91c98..e445def4faa 100644
--- a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
+++ b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
@@ -303,8 +303,6 @@ struct Canonicalizer<'cx, 'tcx> {
     sub_root_lookup_table: SsoHashMap<ty::TyVid, usize>,
     canonicalize_mode: &'cx dyn CanonicalizeMode,
     needs_canonical_flags: TypeFlags,
-
-    binder_index: ty::DebruijnIndex,
 }
 
 impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
@@ -312,24 +310,12 @@ impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
         self.tcx
     }
 
-    fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
-    where
-        T: TypeFoldable<TyCtxt<'tcx>>,
-    {
-        self.binder_index.shift_in(1);
-        let t = t.super_fold_with(self);
-        self.binder_index.shift_out(1);
-        t
-    }
-
     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
         match r.kind() {
-            ty::ReBound(index, ..) => {
-                if index >= self.binder_index {
-                    bug!("escaping late-bound region during canonicalization");
-                } else {
-                    r
-                }
+            ty::ReBound(ty::BoundVarIndexKind::Bound(_), ..) => r,
+
+            ty::ReBound(ty::BoundVarIndexKind::Canonical, _) => {
+                bug!("canonicalized bound var found during canonicalization");
             }
 
             ty::ReStatic
@@ -403,12 +389,10 @@ impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
                 self.canonicalize_ty_var(CanonicalVarKind::PlaceholderTy(placeholder), t)
             }
 
-            ty::Bound(debruijn, _) => {
-                if debruijn >= self.binder_index {
-                    bug!("escaping bound type during canonicalization")
-                } else {
-                    t
-                }
+            ty::Bound(ty::BoundVarIndexKind::Bound(_), _) => t,
+
+            ty::Bound(ty::BoundVarIndexKind::Canonical, _) => {
+                bug!("canonicalized bound var found during canonicalization");
             }
 
             ty::Closure(..)
@@ -479,12 +463,11 @@ impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
             ty::ConstKind::Infer(InferConst::Fresh(_)) => {
                 bug!("encountered a fresh const during canonicalization")
             }
-            ty::ConstKind::Bound(debruijn, _) => {
-                if debruijn >= self.binder_index {
-                    bug!("escaping bound const during canonicalization")
-                } else {
-                    return ct;
-                }
+            ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(_), _) => {
+                return ct;
+            }
+            ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, _) => {
+                bug!("canonicalized bound var found during canonicalization");
             }
             ty::ConstKind::Placeholder(placeholder) => {
                 return self
@@ -569,7 +552,6 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
             query_state,
             indices: FxHashMap::default(),
             sub_root_lookup_table: Default::default(),
-            binder_index: ty::INNERMOST,
         };
         if canonicalizer.query_state.var_values.spilled() {
             canonicalizer.indices = canonicalizer
@@ -751,8 +733,7 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
         r: ty::Region<'tcx>,
     ) -> ty::Region<'tcx> {
         let var = self.canonical_var(var_kind, r.into());
-        let br = ty::BoundRegion { var, kind: ty::BoundRegionKind::Anon };
-        ty::Region::new_bound(self.cx(), self.binder_index, br)
+        ty::Region::new_canonical_bound(self.cx(), var)
     }
 
     /// Given a type variable `ty_var` of the given kind, first check
@@ -766,8 +747,7 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
     ) -> Ty<'tcx> {
         debug_assert!(!self.infcx.is_some_and(|infcx| ty_var != infcx.shallow_resolve(ty_var)));
         let var = self.canonical_var(var_kind, ty_var.into());
-        let bt = ty::BoundTy { var, kind: ty::BoundTyKind::Anon };
-        Ty::new_bound(self.tcx, self.binder_index, bt)
+        Ty::new_canonical_bound(self.tcx, var)
     }
 
     /// Given a type variable `const_var` of the given kind, first check
@@ -783,7 +763,6 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
             !self.infcx.is_some_and(|infcx| ct_var != infcx.shallow_resolve_const(ct_var))
         );
         let var = self.canonical_var(var_kind, ct_var.into());
-        let bc = ty::BoundConst { var };
-        ty::Const::new_bound(self.tcx, self.binder_index, bc)
+        ty::Const::new_canonical_bound(self.tcx, var)
     }
 }
diff --git a/compiler/rustc_infer/src/infer/canonical/instantiate.rs b/compiler/rustc_infer/src/infer/canonical/instantiate.rs
index cc052fbd85c..c215a9db2a0 100644
--- a/compiler/rustc_infer/src/infer/canonical/instantiate.rs
+++ b/compiler/rustc_infer/src/infer/canonical/instantiate.rs
@@ -11,7 +11,7 @@ use rustc_middle::ty::{
     self, DelayedMap, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeSuperVisitable,
     TypeVisitableExt, TypeVisitor,
 };
-use rustc_type_ir::TypeVisitable;
+use rustc_type_ir::{TypeFlags, TypeVisitable};
 
 use crate::infer::canonical::{Canonical, CanonicalVarValues};
 
@@ -66,7 +66,6 @@ where
 
     value.fold_with(&mut CanonicalInstantiator {
         tcx,
-        current_index: ty::INNERMOST,
         var_values: var_values.var_values,
         cache: Default::default(),
     })
@@ -79,12 +78,9 @@ struct CanonicalInstantiator<'tcx> {
     // The values that the bound vars are are being instantiated with.
     var_values: ty::GenericArgsRef<'tcx>,
 
-    /// As with `BoundVarReplacer`, represents the index of a binder *just outside*
-    /// the ones we have visited.
-    current_index: ty::DebruijnIndex,
-
-    // Instantiation is a pure function of `DebruijnIndex` and `Ty`.
-    cache: DelayedMap<(ty::DebruijnIndex, Ty<'tcx>), Ty<'tcx>>,
+    // Because we use `ty::BoundVarIndexKind::Canonical`, we can cache
+    // based only on the entire ty, not worrying about a `DebruijnIndex`
+    cache: DelayedMap<Ty<'tcx>, Ty<'tcx>>,
 }
 
 impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
@@ -92,29 +88,19 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
         self.tcx
     }
 
-    fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
-        &mut self,
-        t: ty::Binder<'tcx, T>,
-    ) -> ty::Binder<'tcx, T> {
-        self.current_index.shift_in(1);
-        let t = t.super_fold_with(self);
-        self.current_index.shift_out(1);
-        t
-    }
-
     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
         match *t.kind() {
-            ty::Bound(debruijn, bound_ty) if debruijn == self.current_index => {
+            ty::Bound(ty::BoundVarIndexKind::Canonical, bound_ty) => {
                 self.var_values[bound_ty.var.as_usize()].expect_ty()
             }
             _ => {
-                if !t.has_vars_bound_at_or_above(self.current_index) {
+                if !t.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
                     t
-                } else if let Some(&t) = self.cache.get(&(self.current_index, t)) {
+                } else if let Some(&t) = self.cache.get(&t) {
                     t
                 } else {
                     let res = t.super_fold_with(self);
-                    assert!(self.cache.insert((self.current_index, t), res));
+                    assert!(self.cache.insert(t, res));
                     res
                 }
             }
@@ -123,7 +109,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
 
     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
         match r.kind() {
-            ty::ReBound(debruijn, br) if debruijn == self.current_index => {
+            ty::ReBound(ty::BoundVarIndexKind::Canonical, br) => {
                 self.var_values[br.var.as_usize()].expect_region()
             }
             _ => r,
@@ -132,7 +118,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
 
     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
         match ct.kind() {
-            ty::ConstKind::Bound(debruijn, bound_const) if debruijn == self.current_index => {
+            ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, bound_const) => {
                 self.var_values[bound_const.var.as_usize()].expect_const()
             }
             _ => ct.super_fold_with(self),
@@ -140,22 +126,14 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
     }
 
     fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
-        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
+        if p.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) { p.super_fold_with(self) } else { p }
     }
 
     fn fold_clauses(&mut self, c: ty::Clauses<'tcx>) -> ty::Clauses<'tcx> {
-        if !c.has_vars_bound_at_or_above(self.current_index) {
+        if !c.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
             return c;
         }
 
-        // Since instantiation is a function of `DebruijnIndex`, we don't want
-        // to have to cache more copies of clauses when we're inside of binders.
-        // Since we currently expect to only have clauses in the outermost
-        // debruijn index, we just fold if we're inside of a binder.
-        if self.current_index > ty::INNERMOST {
-            return c.super_fold_with(self);
-        }
-
         // Our cache key is `(clauses, var_values)`, but we also don't care about
         // var values that aren't named in the clauses, since they can change without
         // affecting the output. Since `ParamEnv`s are cached first, we compute the
@@ -185,45 +163,29 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
 fn highest_var_in_clauses<'tcx>(c: ty::Clauses<'tcx>) -> usize {
     struct HighestVarInClauses {
         max_var: usize,
-        current_index: ty::DebruijnIndex,
     }
     impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for HighestVarInClauses {
-        fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
-            &mut self,
-            t: &ty::Binder<'tcx, T>,
-        ) -> Self::Result {
-            self.current_index.shift_in(1);
-            let t = t.super_visit_with(self);
-            self.current_index.shift_out(1);
-            t
-        }
         fn visit_ty(&mut self, t: Ty<'tcx>) {
-            if let ty::Bound(debruijn, bound_ty) = *t.kind()
-                && debruijn == self.current_index
-            {
+            if let ty::Bound(ty::BoundVarIndexKind::Canonical, bound_ty) = *t.kind() {
                 self.max_var = self.max_var.max(bound_ty.var.as_usize());
-            } else if t.has_vars_bound_at_or_above(self.current_index) {
+            } else if t.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
                 t.super_visit_with(self);
             }
         }
         fn visit_region(&mut self, r: ty::Region<'tcx>) {
-            if let ty::ReBound(debruijn, bound_region) = r.kind()
-                && debruijn == self.current_index
-            {
+            if let ty::ReBound(ty::BoundVarIndexKind::Canonical, bound_region) = r.kind() {
                 self.max_var = self.max_var.max(bound_region.var.as_usize());
             }
         }
         fn visit_const(&mut self, ct: ty::Const<'tcx>) {
-            if let ty::ConstKind::Bound(debruijn, bound_const) = ct.kind()
-                && debruijn == self.current_index
-            {
+            if let ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, bound_const) = ct.kind() {
                 self.max_var = self.max_var.max(bound_const.var.as_usize());
-            } else if ct.has_vars_bound_at_or_above(self.current_index) {
+            } else if ct.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
                 ct.super_visit_with(self);
             }
         }
     }
-    let mut visitor = HighestVarInClauses { max_var: 0, current_index: ty::INNERMOST };
+    let mut visitor = HighestVarInClauses { max_var: 0 };
     c.visit_with(&mut visitor);
     visitor.max_var
 }
diff --git a/compiler/rustc_infer/src/infer/canonical/query_response.rs b/compiler/rustc_infer/src/infer/canonical/query_response.rs
index 5d1b4be9e57..3c20bdd9391 100644
--- a/compiler/rustc_infer/src/infer/canonical/query_response.rs
+++ b/compiler/rustc_infer/src/infer/canonical/query_response.rs
@@ -422,28 +422,28 @@ impl<'tcx> InferCtxt<'tcx> {
                     // and only use it for placeholders. We need to handle the
                     // `sub_root` of type inference variables which would make this
                     // more involved. They are also a lot rarer than region variables.
-                    if let ty::Bound(debruijn, b) = *result_value.kind()
+                    if let ty::Bound(index_kind, b) = *result_value.kind()
                         && !matches!(
                             query_response.variables[b.var.as_usize()],
                             CanonicalVarKind::Ty { .. }
                         )
                     {
-                        // We only allow a `ty::INNERMOST` index in generic parameters.
-                        assert_eq!(debruijn, ty::INNERMOST);
+                        // We only allow a `Canonical` index in generic parameters.
+                        assert!(matches!(index_kind, ty::BoundVarIndexKind::Canonical));
                         opt_values[b.var] = Some(*original_value);
                     }
                 }
                 GenericArgKind::Lifetime(result_value) => {
-                    if let ty::ReBound(debruijn, b) = result_value.kind() {
-                        // We only allow a `ty::INNERMOST` index in generic parameters.
-                        assert_eq!(debruijn, ty::INNERMOST);
+                    if let ty::ReBound(index_kind, b) = result_value.kind() {
+                        // We only allow a `Canonical` index in generic parameters.
+                        assert!(matches!(index_kind, ty::BoundVarIndexKind::Canonical));
                         opt_values[b.var] = Some(*original_value);
                     }
                 }
                 GenericArgKind::Const(result_value) => {
-                    if let ty::ConstKind::Bound(debruijn, b) = result_value.kind() {
-                        // We only allow a `ty::INNERMOST` index in generic parameters.
-                        assert_eq!(debruijn, ty::INNERMOST);
+                    if let ty::ConstKind::Bound(index_kind, b) = result_value.kind() {
+                        // We only allow a `Canonical` index in generic parameters.
+                        assert!(matches!(index_kind, ty::BoundVarIndexKind::Canonical));
                         opt_values[b.var] = Some(*original_value);
                     }
                 }
diff --git a/compiler/rustc_infer/src/infer/outlives/test_type_match.rs b/compiler/rustc_infer/src/infer/outlives/test_type_match.rs
index f06eb58a371..6592360cf0a 100644
--- a/compiler/rustc_infer/src/infer/outlives/test_type_match.rs
+++ b/compiler/rustc_infer/src/infer/outlives/test_type_match.rs
@@ -44,8 +44,8 @@ pub fn extract_verify_if_eq<'tcx>(
     let verify_if_eq = verify_if_eq_b.skip_binder();
     m.relate(verify_if_eq.ty, test_ty).ok()?;
 
-    if let ty::RegionKind::ReBound(depth, br) = verify_if_eq.bound.kind() {
-        assert!(depth == ty::INNERMOST);
+    if let ty::RegionKind::ReBound(index_kind, br) = verify_if_eq.bound.kind() {
+        assert!(matches!(index_kind, ty::BoundVarIndexKind::Bound(ty::INNERMOST)));
         match m.map.get(&br) {
             Some(&r) => Some(r),
             None => {
@@ -156,7 +156,7 @@ impl<'tcx> TypeRelation<TyCtxt<'tcx>> for MatchAgainstHigherRankedOutlives<'tcx>
         pattern: ty::Region<'tcx>,
         value: ty::Region<'tcx>,
     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
-        if let ty::RegionKind::ReBound(depth, br) = pattern.kind()
+        if let ty::RegionKind::ReBound(ty::BoundVarIndexKind::Bound(depth), br) = pattern.kind()
             && depth == self.pattern_depth
         {
             self.bind(br, value)