1use rustc_data_structures::fx::FxIndexMap;
2use rustc_hir::def_id::DefId;
3use rustc_type_ir::data_structures::DelayedMap;
4pub use rustc_type_ir::fold::{
5 FallibleTypeFolder, TypeFoldable, TypeFolder, TypeSuperFoldable, fold_regions, shift_region,
6 shift_vars,
7};
8
9use crate::ty::{self, Binder, BoundTy, Ty, TyCtxt, TypeVisitableExt};
10
11pub struct BottomUpFolder<'tcx, F, G, H>
15where
16 F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
17 G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
18 H: FnMut(ty::Const<'tcx>) -> ty::Const<'tcx>,
19{
20 pub tcx: TyCtxt<'tcx>,
21 pub ty_op: F,
22 pub lt_op: G,
23 pub ct_op: H,
24}
25
26impl<'tcx, F, G, H> TypeFolder<TyCtxt<'tcx>> for BottomUpFolder<'tcx, F, G, H>
27where
28 F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
29 G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
30 H: FnMut(ty::Const<'tcx>) -> ty::Const<'tcx>,
31{
32 fn cx(&self) -> TyCtxt<'tcx> {
33 self.tcx
34 }
35
36 fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
37 let t = ty.super_fold_with(self);
38 (self.ty_op)(t)
39 }
40
41 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
42 (self.lt_op)(r)
45 }
46
47 fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
48 let ct = ct.super_fold_with(self);
49 (self.ct_op)(ct)
50 }
51}
52
53pub trait BoundVarReplacerDelegate<'tcx> {
62 fn replace_region(&mut self, br: ty::BoundRegion) -> ty::Region<'tcx>;
63 fn replace_ty(&mut self, bt: ty::BoundTy) -> Ty<'tcx>;
64 fn replace_const(&mut self, bv: ty::BoundVar) -> ty::Const<'tcx>;
65}
66
67pub struct FnMutDelegate<'a, 'tcx> {
71 pub regions: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a),
72 pub types: &'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a),
73 pub consts: &'a mut (dyn FnMut(ty::BoundVar) -> ty::Const<'tcx> + 'a),
74}
75
76impl<'a, 'tcx> BoundVarReplacerDelegate<'tcx> for FnMutDelegate<'a, 'tcx> {
77 fn replace_region(&mut self, br: ty::BoundRegion) -> ty::Region<'tcx> {
78 (self.regions)(br)
79 }
80 fn replace_ty(&mut self, bt: ty::BoundTy) -> Ty<'tcx> {
81 (self.types)(bt)
82 }
83 fn replace_const(&mut self, bv: ty::BoundVar) -> ty::Const<'tcx> {
84 (self.consts)(bv)
85 }
86}
87
88struct BoundVarReplacer<'tcx, D> {
90 tcx: TyCtxt<'tcx>,
91
92 current_index: ty::DebruijnIndex,
95
96 delegate: D,
97
98 cache: DelayedMap<(ty::DebruijnIndex, Ty<'tcx>), Ty<'tcx>>,
101}
102
103impl<'tcx, D: BoundVarReplacerDelegate<'tcx>> BoundVarReplacer<'tcx, D> {
104 fn new(tcx: TyCtxt<'tcx>, delegate: D) -> Self {
105 BoundVarReplacer { tcx, current_index: ty::INNERMOST, delegate, cache: Default::default() }
106 }
107}
108
109impl<'tcx, D> TypeFolder<TyCtxt<'tcx>> for BoundVarReplacer<'tcx, D>
110where
111 D: BoundVarReplacerDelegate<'tcx>,
112{
113 fn cx(&self) -> TyCtxt<'tcx> {
114 self.tcx
115 }
116
117 fn fold_binder<T: TypeFoldable<TyCtxt<'tcx>>>(
118 &mut self,
119 t: ty::Binder<'tcx, T>,
120 ) -> ty::Binder<'tcx, T> {
121 self.current_index.shift_in(1);
122 let t = t.super_fold_with(self);
123 self.current_index.shift_out(1);
124 t
125 }
126
127 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
128 match *t.kind() {
129 ty::Bound(debruijn, bound_ty) if debruijn == self.current_index => {
130 let ty = self.delegate.replace_ty(bound_ty);
131 debug_assert!(!ty.has_vars_bound_above(ty::INNERMOST));
132 ty::fold::shift_vars(self.tcx, ty, self.current_index.as_u32())
133 }
134 _ => {
135 if !t.has_vars_bound_at_or_above(self.current_index) {
136 t
137 } else if let Some(&t) = self.cache.get(&(self.current_index, t)) {
138 t
139 } else {
140 let res = t.super_fold_with(self);
141 assert!(self.cache.insert((self.current_index, t), res));
142 res
143 }
144 }
145 }
146 }
147
148 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
149 match *r {
150 ty::ReBound(debruijn, br) if debruijn == self.current_index => {
151 let region = self.delegate.replace_region(br);
152 if let ty::ReBound(debruijn1, br) = *region {
153 assert_eq!(debruijn1, ty::INNERMOST);
158 ty::Region::new_bound(self.tcx, debruijn, br)
159 } else {
160 region
161 }
162 }
163 _ => r,
164 }
165 }
166
167 fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
168 match ct.kind() {
169 ty::ConstKind::Bound(debruijn, bound_const) if debruijn == self.current_index => {
170 let ct = self.delegate.replace_const(bound_const);
171 debug_assert!(!ct.has_vars_bound_above(ty::INNERMOST));
172 ty::fold::shift_vars(self.tcx, ct, self.current_index.as_u32())
173 }
174 _ => ct.super_fold_with(self),
175 }
176 }
177
178 fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
179 if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
180 }
181}
182
183impl<'tcx> TyCtxt<'tcx> {
184 pub fn instantiate_bound_regions<T, F>(
198 self,
199 value: Binder<'tcx, T>,
200 mut fld_r: F,
201 ) -> (T, FxIndexMap<ty::BoundRegion, ty::Region<'tcx>>)
202 where
203 F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
204 T: TypeFoldable<TyCtxt<'tcx>>,
205 {
206 let mut region_map = FxIndexMap::default();
207 let real_fld_r = |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br));
208 let value = self.instantiate_bound_regions_uncached(value, real_fld_r);
209 (value, region_map)
210 }
211
212 pub fn instantiate_bound_regions_uncached<T, F>(
213 self,
214 value: Binder<'tcx, T>,
215 mut replace_regions: F,
216 ) -> T
217 where
218 F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
219 T: TypeFoldable<TyCtxt<'tcx>>,
220 {
221 let value = value.skip_binder();
222 if !value.has_escaping_bound_vars() {
223 value
224 } else {
225 let delegate = FnMutDelegate {
226 regions: &mut replace_regions,
227 types: &mut |b| bug!("unexpected bound ty in binder: {b:?}"),
228 consts: &mut |b| bug!("unexpected bound ct in binder: {b:?}"),
229 };
230 let mut replacer = BoundVarReplacer::new(self, delegate);
231 value.fold_with(&mut replacer)
232 }
233 }
234
235 pub fn replace_escaping_bound_vars_uncached<T: TypeFoldable<TyCtxt<'tcx>>>(
239 self,
240 value: T,
241 delegate: impl BoundVarReplacerDelegate<'tcx>,
242 ) -> T {
243 if !value.has_escaping_bound_vars() {
244 value
245 } else {
246 let mut replacer = BoundVarReplacer::new(self, delegate);
247 value.fold_with(&mut replacer)
248 }
249 }
250
251 pub fn replace_bound_vars_uncached<T: TypeFoldable<TyCtxt<'tcx>>>(
255 self,
256 value: Binder<'tcx, T>,
257 delegate: impl BoundVarReplacerDelegate<'tcx>,
258 ) -> T {
259 self.replace_escaping_bound_vars_uncached(value.skip_binder(), delegate)
260 }
261
262 pub fn liberate_late_bound_regions<T>(
265 self,
266 all_outlive_scope: DefId,
267 value: ty::Binder<'tcx, T>,
268 ) -> T
269 where
270 T: TypeFoldable<TyCtxt<'tcx>>,
271 {
272 self.instantiate_bound_regions_uncached(value, |br| {
273 let kind = ty::LateParamRegionKind::from_bound(br.var, br.kind);
274 ty::Region::new_late_param(self, all_outlive_scope, kind)
275 })
276 }
277
278 pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T
279 where
280 T: TypeFoldable<TyCtxt<'tcx>>,
281 {
282 let shift_bv = |bv: ty::BoundVar| ty::BoundVar::from_usize(bv.as_usize() + bound_vars);
283 self.replace_escaping_bound_vars_uncached(
284 value,
285 FnMutDelegate {
286 regions: &mut |r: ty::BoundRegion| {
287 ty::Region::new_bound(
288 self,
289 ty::INNERMOST,
290 ty::BoundRegion { var: shift_bv(r.var), kind: r.kind },
291 )
292 },
293 types: &mut |t: ty::BoundTy| {
294 Ty::new_bound(
295 self,
296 ty::INNERMOST,
297 ty::BoundTy { var: shift_bv(t.var), kind: t.kind },
298 )
299 },
300 consts: &mut |c| ty::Const::new_bound(self, ty::INNERMOST, shift_bv(c)),
301 },
302 )
303 }
304
305 pub fn instantiate_bound_regions_with_erased<T>(self, value: Binder<'tcx, T>) -> T
308 where
309 T: TypeFoldable<TyCtxt<'tcx>>,
310 {
311 self.instantiate_bound_regions(value, |_| self.lifetimes.re_erased).0
312 }
313
314 pub fn anonymize_bound_vars<T>(self, value: Binder<'tcx, T>) -> Binder<'tcx, T>
316 where
317 T: TypeFoldable<TyCtxt<'tcx>>,
318 {
319 struct Anonymize<'a, 'tcx> {
320 tcx: TyCtxt<'tcx>,
321 map: &'a mut FxIndexMap<ty::BoundVar, ty::BoundVariableKind>,
322 }
323 impl<'tcx> BoundVarReplacerDelegate<'tcx> for Anonymize<'_, 'tcx> {
324 fn replace_region(&mut self, br: ty::BoundRegion) -> ty::Region<'tcx> {
325 let entry = self.map.entry(br.var);
326 let index = entry.index();
327 let var = ty::BoundVar::from_usize(index);
328 let kind = entry
329 .or_insert_with(|| ty::BoundVariableKind::Region(ty::BoundRegionKind::Anon))
330 .expect_region();
331 let br = ty::BoundRegion { var, kind };
332 ty::Region::new_bound(self.tcx, ty::INNERMOST, br)
333 }
334 fn replace_ty(&mut self, bt: ty::BoundTy) -> Ty<'tcx> {
335 let entry = self.map.entry(bt.var);
336 let index = entry.index();
337 let var = ty::BoundVar::from_usize(index);
338 let kind = entry
339 .or_insert_with(|| ty::BoundVariableKind::Ty(ty::BoundTyKind::Anon))
340 .expect_ty();
341 Ty::new_bound(self.tcx, ty::INNERMOST, BoundTy { var, kind })
342 }
343 fn replace_const(&mut self, bv: ty::BoundVar) -> ty::Const<'tcx> {
344 let entry = self.map.entry(bv);
345 let index = entry.index();
346 let var = ty::BoundVar::from_usize(index);
347 let () = entry.or_insert_with(|| ty::BoundVariableKind::Const).expect_const();
348 ty::Const::new_bound(self.tcx, ty::INNERMOST, var)
349 }
350 }
351
352 let mut map = Default::default();
353 let delegate = Anonymize { tcx: self, map: &mut map };
354 let inner = self.replace_escaping_bound_vars_uncached(value.skip_binder(), delegate);
355 let bound_vars = self.mk_bound_variable_kinds_from_iter(map.into_values());
356 Binder::bind_with_vars(inner, bound_vars)
357 }
358}