Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 4b9c62b

Browse files
committed
Auto merge of rust-lang#147138 - jackh726:split-canonical-bound, r=lcnr
Split Bound index into Canonical and Bound See [#t-types/trait-system-refactor > perf &rust-lang#96;async-closures/post-mono-higher-ranked-hang.rs&rust-lang#96;](https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/perf.20.60async-closures.2Fpost-mono-higher-ranked-hang.2Ers.60/with/541535613) for context Things compile and tests pass, but not sure if this actually solves the perf issue (edit: it does). Opening up this to do a perf (and maybe crater) run. r? lcnr
2 parents 42b384e + d1bbd39 commit 4b9c62b

File tree

45 files changed

+391
-247
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

45 files changed

+391
-247
lines changed

‎compiler/rustc_borrowck/src/lib.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -278,7 +278,7 @@ impl<'tcx> ClosureOutlivesSubjectTy<'tcx> {
278278
mut map: impl FnMut(ty::RegionVid) -> ty::Region<'tcx>,
279279
) -> Ty<'tcx> {
280280
fold_regions(tcx, self.inner, |r, depth| match r.kind() {
281-
ty::ReBound(debruijn, br) => {
281+
ty::ReBound(ty::BoundVarIndexKind::Bound(debruijn), br) => {
282282
debug_assert_eq!(debruijn, depth);
283283
map(ty::RegionVid::from_usize(br.var.index()))
284284
}

‎compiler/rustc_hir_analysis/src/collect/item_bounds.rs‎

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -181,21 +181,25 @@ fn remap_gat_vars_and_recurse_into_nested_projections<'tcx>(
181181
for (param, var) in std::iter::zip(&generics.own_params, gat_vars) {
182182
let existing = match var.kind() {
183183
ty::GenericArgKind::Lifetime(re) => {
184-
if let ty::RegionKind::ReBound(ty::INNERMOST, bv) = re.kind() {
184+
if let ty::RegionKind::ReBound(ty::BoundVarIndexKind::Bound(ty::INNERMOST), bv) =
185+
re.kind()
186+
{
185187
mapping.insert(bv.var, tcx.mk_param_from_def(param))
186188
} else {
187189
return None;
188190
}
189191
}
190192
ty::GenericArgKind::Type(ty) => {
191-
if let ty::Bound(ty::INNERMOST, bv) = *ty.kind() {
193+
if let ty::Bound(ty::BoundVarIndexKind::Bound(ty::INNERMOST), bv) = *ty.kind() {
192194
mapping.insert(bv.var, tcx.mk_param_from_def(param))
193195
} else {
194196
return None;
195197
}
196198
}
197199
ty::GenericArgKind::Const(ct) => {
198-
if let ty::ConstKind::Bound(ty::INNERMOST, bv) = ct.kind() {
200+
if let ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(ty::INNERMOST), bv) =
201+
ct.kind()
202+
{
199203
mapping.insert(bv.var, tcx.mk_param_from_def(param))
200204
} else {
201205
return None;
@@ -260,7 +264,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for MapAndCompressBoundVars<'tcx> {
260264
return ty;
261265
}
262266

263-
if let ty::Bound(binder, old_bound) = *ty.kind()
267+
if let ty::Bound(ty::BoundVarIndexKind::Bound(binder), old_bound) = *ty.kind()
264268
&& self.binder == binder
265269
{
266270
let mapped = if let Some(mapped) = self.mapping.get(&old_bound.var) {
@@ -286,7 +290,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for MapAndCompressBoundVars<'tcx> {
286290
}
287291

288292
fn fold_region(&mut self, re: ty::Region<'tcx>) -> ty::Region<'tcx> {
289-
if let ty::ReBound(binder, old_bound) = re.kind()
293+
if let ty::ReBound(ty::BoundVarIndexKind::Bound(binder), old_bound) = re.kind()
290294
&& self.binder == binder
291295
{
292296
let mapped = if let Some(mapped) = self.mapping.get(&old_bound.var) {
@@ -314,7 +318,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for MapAndCompressBoundVars<'tcx> {
314318
return ct;
315319
}
316320

317-
if let ty::ConstKind::Bound(binder, old_bound) = ct.kind()
321+
if let ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(binder), old_bound) = ct.kind()
318322
&& self.binder == binder
319323
{
320324
let mapped = if let Some(mapped) = self.mapping.get(&old_bound.var) {

‎compiler/rustc_hir_analysis/src/hir_ty_lowering/bounds.rs‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -921,7 +921,7 @@ impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for GenericParamAndBoundVarCollector<'_, 't
921921
ty::Param(param) => {
922922
self.params.insert(param.index);
923923
}
924-
ty::Bound(db, bt) if *db >= self.depth => {
924+
ty::Bound(ty::BoundVarIndexKind::Bound(db), bt) if *db >= self.depth => {
925925
self.vars.insert(match bt.kind {
926926
ty::BoundTyKind::Param(def_id) => def_id,
927927
ty::BoundTyKind::Anon => {
@@ -944,7 +944,7 @@ impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for GenericParamAndBoundVarCollector<'_, 't
944944
ty::ReEarlyParam(param) => {
945945
self.params.insert(param.index);
946946
}
947-
ty::ReBound(db, br) if db >= self.depth => {
947+
ty::ReBound(ty::BoundVarIndexKind::Bound(db), br) if db >= self.depth => {
948948
self.vars.insert(match br.kind {
949949
ty::BoundRegionKind::Named(def_id) => def_id,
950950
ty::BoundRegionKind::Anon | ty::BoundRegionKind::ClosureEnv => {
@@ -967,7 +967,7 @@ impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for GenericParamAndBoundVarCollector<'_, 't
967967
ty::ConstKind::Param(param) => {
968968
self.params.insert(param.index);
969969
}
970-
ty::ConstKind::Bound(db, _) if db >= self.depth => {
970+
ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(db), _) if db >= self.depth => {
971971
let guar = self.cx.dcx().delayed_bug("unexpected escaping late-bound const var");
972972
return ControlFlow::Break(guar);
973973
}

‎compiler/rustc_infer/src/infer/canonical/canonicalizer.rs‎

Lines changed: 16 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -303,33 +303,19 @@ struct Canonicalizer<'cx, 'tcx> {
303303
sub_root_lookup_table: SsoHashMap<ty::TyVid, usize>,
304304
canonicalize_mode: &'cx dyn CanonicalizeMode,
305305
needs_canonical_flags: TypeFlags,
306-
307-
binder_index: ty::DebruijnIndex,
308306
}
309307

310308
impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
311309
fn cx(&self) -> TyCtxt<'tcx> {
312310
self.tcx
313311
}
314312

315-
fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
316-
where
317-
T: TypeFoldable<TyCtxt<'tcx>>,
318-
{
319-
self.binder_index.shift_in(1);
320-
let t = t.super_fold_with(self);
321-
self.binder_index.shift_out(1);
322-
t
323-
}
324-
325313
fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
326314
match r.kind() {
327-
ty::ReBound(index, ..) => {
328-
if index >= self.binder_index {
329-
bug!("escaping late-bound region during canonicalization");
330-
} else {
331-
r
332-
}
315+
ty::ReBound(ty::BoundVarIndexKind::Bound(_), ..) => r,
316+
317+
ty::ReBound(ty::BoundVarIndexKind::Canonical, _) => {
318+
bug!("canonicalized bound var found during canonicalization");
333319
}
334320

335321
ty::ReStatic
@@ -403,12 +389,10 @@ impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
403389
self.canonicalize_ty_var(CanonicalVarKind::PlaceholderTy(placeholder), t)
404390
}
405391

406-
ty::Bound(debruijn, _) => {
407-
if debruijn >= self.binder_index {
408-
bug!("escaping bound type during canonicalization")
409-
} else {
410-
t
411-
}
392+
ty::Bound(ty::BoundVarIndexKind::Bound(_), _) => t,
393+
394+
ty::Bound(ty::BoundVarIndexKind::Canonical, _) => {
395+
bug!("canonicalized bound var found during canonicalization");
412396
}
413397

414398
ty::Closure(..)
@@ -479,12 +463,11 @@ impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
479463
ty::ConstKind::Infer(InferConst::Fresh(_)) => {
480464
bug!("encountered a fresh const during canonicalization")
481465
}
482-
ty::ConstKind::Bound(debruijn, _) => {
483-
if debruijn >= self.binder_index {
484-
bug!("escaping bound const during canonicalization")
485-
} else {
486-
return ct;
487-
}
466+
ty::ConstKind::Bound(ty::BoundVarIndexKind::Bound(_), _) => {
467+
return ct;
468+
}
469+
ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, _) => {
470+
bug!("canonicalized bound var found during canonicalization");
488471
}
489472
ty::ConstKind::Placeholder(placeholder) => {
490473
return self
@@ -569,7 +552,6 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
569552
query_state,
570553
indices: FxHashMap::default(),
571554
sub_root_lookup_table: Default::default(),
572-
binder_index: ty::INNERMOST,
573555
};
574556
if canonicalizer.query_state.var_values.spilled() {
575557
canonicalizer.indices = canonicalizer
@@ -751,8 +733,7 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
751733
r: ty::Region<'tcx>,
752734
) -> ty::Region<'tcx> {
753735
let var = self.canonical_var(var_kind, r.into());
754-
let br = ty::BoundRegion { var, kind: ty::BoundRegionKind::Anon };
755-
ty::Region::new_bound(self.cx(), self.binder_index, br)
736+
ty::Region::new_canonical_bound(self.cx(), var)
756737
}
757738

758739
/// Given a type variable `ty_var` of the given kind, first check
@@ -766,8 +747,7 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
766747
) -> Ty<'tcx> {
767748
debug_assert!(!self.infcx.is_some_and(|infcx| ty_var != infcx.shallow_resolve(ty_var)));
768749
let var = self.canonical_var(var_kind, ty_var.into());
769-
let bt = ty::BoundTy { var, kind: ty::BoundTyKind::Anon };
770-
Ty::new_bound(self.tcx, self.binder_index, bt)
750+
Ty::new_canonical_bound(self.tcx, var)
771751
}
772752

773753
/// Given a type variable `const_var` of the given kind, first check
@@ -783,7 +763,6 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
783763
!self.infcx.is_some_and(|infcx| ct_var != infcx.shallow_resolve_const(ct_var))
784764
);
785765
let var = self.canonical_var(var_kind, ct_var.into());
786-
let bc = ty::BoundConst { var };
787-
ty::Const::new_bound(self.tcx, self.binder_index, bc)
766+
ty::Const::new_canonical_bound(self.tcx, var)
788767
}
789768
}

‎compiler/rustc_infer/src/infer/canonical/instantiate.rs‎

Lines changed: 18 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ use rustc_middle::ty::{
1111
self, DelayedMap, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeSuperVisitable,
1212
TypeVisitableExt, TypeVisitor,
1313
};
14-
use rustc_type_ir::TypeVisitable;
14+
use rustc_type_ir::{TypeFlags,TypeVisitable};
1515

1616
use crate::infer::canonical::{Canonical, CanonicalVarValues};
1717

@@ -66,7 +66,6 @@ where
6666

6767
value.fold_with(&mut CanonicalInstantiator {
6868
tcx,
69-
current_index: ty::INNERMOST,
7069
var_values: var_values.var_values,
7170
cache: Default::default(),
7271
})
@@ -79,42 +78,29 @@ struct CanonicalInstantiator<'tcx> {
7978
// The values that the bound vars are are being instantiated with.
8079
var_values: ty::GenericArgsRef<'tcx>,
8180

82-
/// As with `BoundVarReplacer`, represents the index of a binder *just outside*
83-
/// the ones we have visited.
84-
current_index: ty::DebruijnIndex,
85-
86-
// Instantiation is a pure function of `DebruijnIndex` and `Ty`.
87-
cache: DelayedMap<(ty::DebruijnIndex, Ty<'tcx>), Ty<'tcx>>,
81+
// Because we use `ty::BoundVarIndexKind::Canonical`, we can cache
82+
// based only on the entire ty, not worrying about a `DebruijnIndex`
83+
cache: DelayedMap<Ty<'tcx>, Ty<'tcx>>,
8884
}
8985

9086
impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
9187
fn cx(&self) -> TyCtxt<'tcx> {
9288
self.tcx
9389
}
9490

95-
fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
96-
&mut self,
97-
t: ty::Binder<'tcx, T>,
98-
) -> ty::Binder<'tcx, T> {
99-
self.current_index.shift_in(1);
100-
let t = t.super_fold_with(self);
101-
self.current_index.shift_out(1);
102-
t
103-
}
104-
10591
fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
10692
match *t.kind() {
107-
ty::Bound(debruijn, bound_ty)if debruijn == self.current_index => {
93+
ty::Bound(ty::BoundVarIndexKind::Canonical, bound_ty) => {
10894
self.var_values[bound_ty.var.as_usize()].expect_ty()
10995
}
11096
_ => {
111-
if !t.has_vars_bound_at_or_above(self.current_index) {
97+
if !t.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
11298
t
113-
} else if let Some(&t) = self.cache.get(&(self.current_index, t)) {
99+
} else if let Some(&t) = self.cache.get(&t) {
114100
t
115101
} else {
116102
let res = t.super_fold_with(self);
117-
assert!(self.cache.insert((self.current_index, t), res));
103+
assert!(self.cache.insert(t, res));
118104
res
119105
}
120106
}
@@ -123,7 +109,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
123109

124110
fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
125111
match r.kind() {
126-
ty::ReBound(debruijn, br)if debruijn == self.current_index => {
112+
ty::ReBound(ty::BoundVarIndexKind::Canonical, br) => {
127113
self.var_values[br.var.as_usize()].expect_region()
128114
}
129115
_ => r,
@@ -132,30 +118,22 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
132118

133119
fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
134120
match ct.kind() {
135-
ty::ConstKind::Bound(debruijn, bound_const)if debruijn == self.current_index => {
121+
ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, bound_const) => {
136122
self.var_values[bound_const.var.as_usize()].expect_const()
137123
}
138124
_ => ct.super_fold_with(self),
139125
}
140126
}
141127

142128
fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
143-
if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
129+
if p.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) { p.super_fold_with(self) } else { p }
144130
}
145131

146132
fn fold_clauses(&mut self, c: ty::Clauses<'tcx>) -> ty::Clauses<'tcx> {
147-
if !c.has_vars_bound_at_or_above(self.current_index) {
133+
if !c.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
148134
return c;
149135
}
150136

151-
// Since instantiation is a function of `DebruijnIndex`, we don't want
152-
// to have to cache more copies of clauses when we're inside of binders.
153-
// Since we currently expect to only have clauses in the outermost
154-
// debruijn index, we just fold if we're inside of a binder.
155-
if self.current_index > ty::INNERMOST {
156-
return c.super_fold_with(self);
157-
}
158-
159137
// Our cache key is `(clauses, var_values)`, but we also don't care about
160138
// var values that aren't named in the clauses, since they can change without
161139
// affecting the output. Since `ParamEnv`s are cached first, we compute the
@@ -185,45 +163,29 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for CanonicalInstantiator<'tcx> {
185163
fn highest_var_in_clauses<'tcx>(c: ty::Clauses<'tcx>) -> usize {
186164
struct HighestVarInClauses {
187165
max_var: usize,
188-
current_index: ty::DebruijnIndex,
189166
}
190167
impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for HighestVarInClauses {
191-
fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
192-
&mut self,
193-
t: &ty::Binder<'tcx, T>,
194-
) -> Self::Result {
195-
self.current_index.shift_in(1);
196-
let t = t.super_visit_with(self);
197-
self.current_index.shift_out(1);
198-
t
199-
}
200168
fn visit_ty(&mut self, t: Ty<'tcx>) {
201-
if let ty::Bound(debruijn, bound_ty) = *t.kind()
202-
&& debruijn == self.current_index
203-
{
169+
if let ty::Bound(ty::BoundVarIndexKind::Canonical, bound_ty) = *t.kind() {
204170
self.max_var = self.max_var.max(bound_ty.var.as_usize());
205-
} else if t.has_vars_bound_at_or_above(self.current_index) {
171+
} else if t.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
206172
t.super_visit_with(self);
207173
}
208174
}
209175
fn visit_region(&mut self, r: ty::Region<'tcx>) {
210-
if let ty::ReBound(debruijn, bound_region) = r.kind()
211-
&& debruijn == self.current_index
212-
{
176+
if let ty::ReBound(ty::BoundVarIndexKind::Canonical, bound_region) = r.kind() {
213177
self.max_var = self.max_var.max(bound_region.var.as_usize());
214178
}
215179
}
216180
fn visit_const(&mut self, ct: ty::Const<'tcx>) {
217-
if let ty::ConstKind::Bound(debruijn, bound_const) = ct.kind()
218-
&& debruijn == self.current_index
219-
{
181+
if let ty::ConstKind::Bound(ty::BoundVarIndexKind::Canonical, bound_const) = ct.kind() {
220182
self.max_var = self.max_var.max(bound_const.var.as_usize());
221-
} else if ct.has_vars_bound_at_or_above(self.current_index) {
183+
} else if ct.has_type_flags(TypeFlags::HAS_CANONICAL_BOUND) {
222184
ct.super_visit_with(self);
223185
}
224186
}
225187
}
226-
let mut visitor = HighestVarInClauses { max_var: 0,current_index: ty::INNERMOST };
188+
let mut visitor = HighestVarInClauses { max_var: 0 };
227189
c.visit_with(&mut visitor);
228190
visitor.max_var
229191
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /