1use std::convert::Infallible;
49use std::mem;
50use std::sync::Arc;
51
52use rustc_index::{Idx, IndexVec};
53use thin_vec::ThinVec;
54use tracing::{debug, instrument};
55
56use crate::inherent::*;
57use crate::visit::{TypeVisitable, TypeVisitableExt as _};
58use crate::{self as ty, Interner, TypeFlags};
59
60pub trait TypeFoldable<I: Interner>: TypeVisitable<I> + Clone {
72 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error>;
83
84 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self;
98}
99
100pub trait TypeSuperFoldable<I: Interner>: TypeFoldable<I> {
102 fn try_super_fold_with<F: FallibleTypeFolder<I>>(
109 self,
110 folder: &mut F,
111 ) -> Result<Self, F::Error>;
112
113 fn super_fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self;
117}
118
119pub trait TypeFolder<I: Interner>: Sized {
129 fn cx(&self) -> I;
130
131 fn fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T>
132 where
133 T: TypeFoldable<I>,
134 {
135 t.super_fold_with(self)
136 }
137
138 fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
139 t.super_fold_with(self)
140 }
141
142 fn fold_region(&mut self, r: I::Region) -> I::Region {
145 r
146 }
147
148 fn fold_const(&mut self, c: I::Const) -> I::Const {
149 c.super_fold_with(self)
150 }
151
152 fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
153 p.super_fold_with(self)
154 }
155}
156
157pub trait FallibleTypeFolder<I: Interner>: Sized {
165 type Error;
166
167 fn cx(&self) -> I;
168
169 fn try_fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> Result<ty::Binder<I, T>, Self::Error>
170 where
171 T: TypeFoldable<I>,
172 {
173 t.try_super_fold_with(self)
174 }
175
176 fn try_fold_ty(&mut self, t: I::Ty) -> Result<I::Ty, Self::Error> {
177 t.try_super_fold_with(self)
178 }
179
180 fn try_fold_region(&mut self, r: I::Region) -> Result<I::Region, Self::Error> {
183 Ok(r)
184 }
185
186 fn try_fold_const(&mut self, c: I::Const) -> Result<I::Const, Self::Error> {
187 c.try_super_fold_with(self)
188 }
189
190 fn try_fold_predicate(&mut self, p: I::Predicate) -> Result<I::Predicate, Self::Error> {
191 p.try_super_fold_with(self)
192 }
193}
194
195impl<I: Interner, T: TypeFoldable<I>, U: TypeFoldable<I>> TypeFoldable<I> for (T, U) {
199 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<(T, U), F::Error> {
200 Ok((self.0.try_fold_with(folder)?, self.1.try_fold_with(folder)?))
201 }
202
203 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
204 (self.0.fold_with(folder), self.1.fold_with(folder))
205 }
206}
207
208impl<I: Interner, A: TypeFoldable<I>, B: TypeFoldable<I>, C: TypeFoldable<I>> TypeFoldable<I>
209 for (A, B, C)
210{
211 fn try_fold_with<F: FallibleTypeFolder<I>>(
212 self,
213 folder: &mut F,
214 ) -> Result<(A, B, C), F::Error> {
215 Ok((
216 self.0.try_fold_with(folder)?,
217 self.1.try_fold_with(folder)?,
218 self.2.try_fold_with(folder)?,
219 ))
220 }
221
222 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
223 (self.0.fold_with(folder), self.1.fold_with(folder), self.2.fold_with(folder))
224 }
225}
226
227impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Option<T> {
228 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
229 Ok(match self {
230 Some(v) => Some(v.try_fold_with(folder)?),
231 None => None,
232 })
233 }
234
235 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
236 Some(self?.fold_with(folder))
237 }
238}
239
240impl<I: Interner, T: TypeFoldable<I>, E: TypeFoldable<I>> TypeFoldable<I> for Result<T, E> {
241 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
242 Ok(match self {
243 Ok(v) => Ok(v.try_fold_with(folder)?),
244 Err(e) => Err(e.try_fold_with(folder)?),
245 })
246 }
247
248 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
249 match self {
250 Ok(v) => Ok(v.fold_with(folder)),
251 Err(e) => Err(e.fold_with(folder)),
252 }
253 }
254}
255
256fn fold_arc<T: Clone, E>(
257 mut arc: Arc<T>,
258 fold: impl FnOnce(T) -> Result<T, E>,
259) -> Result<Arc<T>, E> {
260 unsafe {
264 Arc::make_mut(&mut arc);
270
271 let ptr = Arc::into_raw(arc).cast::<mem::ManuallyDrop<T>>();
274 let mut unique = Arc::from_raw(ptr);
275
276 let slot = Arc::get_mut(&mut unique).unwrap_unchecked();
280
281 let owned = mem::ManuallyDrop::take(slot);
286 let folded = fold(owned)?;
287 *slot = mem::ManuallyDrop::new(folded);
288
289 Ok(Arc::from_raw(Arc::into_raw(unique).cast()))
291 }
292}
293
294impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Arc<T> {
295 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
296 fold_arc(self, |t| t.try_fold_with(folder))
297 }
298
299 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
300 match fold_arc::<T, Infallible>(self, |t| Ok(t.fold_with(folder))) {
301 Ok(t) => t,
302 }
303 }
304}
305
306impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Box<T> {
307 fn try_fold_with<F: FallibleTypeFolder<I>>(mut self, folder: &mut F) -> Result<Self, F::Error> {
308 *self = (*self).try_fold_with(folder)?;
309 Ok(self)
310 }
311
312 fn fold_with<F: TypeFolder<I>>(mut self, folder: &mut F) -> Self {
313 *self = (*self).fold_with(folder);
314 self
315 }
316}
317
318impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Vec<T> {
319 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
320 self.into_iter().map(|t| t.try_fold_with(folder)).collect()
321 }
322
323 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
324 self.into_iter().map(|t| t.fold_with(folder)).collect()
325 }
326}
327
328impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for ThinVec<T> {
329 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
330 self.into_iter().map(|t| t.try_fold_with(folder)).collect()
331 }
332
333 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
334 self.into_iter().map(|t| t.fold_with(folder)).collect()
335 }
336}
337
338impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Box<[T]> {
339 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
340 Vec::from(self).try_fold_with(folder).map(Vec::into_boxed_slice)
341 }
342
343 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
344 Vec::into_boxed_slice(Vec::from(self).fold_with(folder))
345 }
346}
347
348impl<I: Interner, T: TypeFoldable<I>, Ix: Idx> TypeFoldable<I> for IndexVec<Ix, T> {
349 fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
350 self.raw.try_fold_with(folder).map(IndexVec::from_raw)
351 }
352
353 fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
354 IndexVec::from_raw(self.raw.fold_with(folder))
355 }
356}
357
358struct Shifter<I: Interner> {
368 cx: I,
369 current_index: ty::DebruijnIndex,
370 amount: u32,
371}
372
373impl<I: Interner> Shifter<I> {
374 fn new(cx: I, amount: u32) -> Self {
375 Shifter { cx, current_index: ty::INNERMOST, amount }
376 }
377}
378
379impl<I: Interner> TypeFolder<I> for Shifter<I> {
380 fn cx(&self) -> I {
381 self.cx
382 }
383
384 fn fold_binder<T: TypeFoldable<I>>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T> {
385 self.current_index.shift_in(1);
386 let t = t.super_fold_with(self);
387 self.current_index.shift_out(1);
388 t
389 }
390
391 fn fold_region(&mut self, r: I::Region) -> I::Region {
392 match r.kind() {
393 ty::ReBound(debruijn, br) if debruijn >= self.current_index => {
394 let debruijn = debruijn.shifted_in(self.amount);
395 Region::new_bound(self.cx, debruijn, br)
396 }
397 _ => r,
398 }
399 }
400
401 fn fold_ty(&mut self, ty: I::Ty) -> I::Ty {
402 match ty.kind() {
403 ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => {
404 let debruijn = debruijn.shifted_in(self.amount);
405 Ty::new_bound(self.cx, debruijn, bound_ty)
406 }
407
408 _ if ty.has_vars_bound_at_or_above(self.current_index) => ty.super_fold_with(self),
409 _ => ty,
410 }
411 }
412
413 fn fold_const(&mut self, ct: I::Const) -> I::Const {
414 match ct.kind() {
415 ty::ConstKind::Bound(debruijn, bound_ct) if debruijn >= self.current_index => {
416 let debruijn = debruijn.shifted_in(self.amount);
417 Const::new_bound(self.cx, debruijn, bound_ct)
418 }
419 _ => ct.super_fold_with(self),
420 }
421 }
422
423 fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
424 if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
425 }
426}
427
428pub fn shift_region<I: Interner>(cx: I, region: I::Region, amount: u32) -> I::Region {
429 match region.kind() {
430 ty::ReBound(debruijn, br) if amount > 0 => {
431 Region::new_bound(cx, debruijn.shifted_in(amount), br)
432 }
433 _ => region,
434 }
435}
436
437#[instrument(level = "trace", skip(cx), ret)]
438pub fn shift_vars<I: Interner, T>(cx: I, value: T, amount: u32) -> T
439where
440 T: TypeFoldable<I>,
441{
442 if amount == 0 || !value.has_escaping_bound_vars() {
443 value
444 } else {
445 value.fold_with(&mut Shifter::new(cx, amount))
446 }
447}
448
449pub fn fold_regions<I: Interner, T>(
453 cx: I,
454 value: T,
455 f: impl FnMut(I::Region, ty::DebruijnIndex) -> I::Region,
456) -> T
457where
458 T: TypeFoldable<I>,
459{
460 value.fold_with(&mut RegionFolder::new(cx, f))
461}
462
463pub struct RegionFolder<I, F> {
471 cx: I,
472
473 current_index: ty::DebruijnIndex,
477
478 fold_region_fn: F,
482}
483
484impl<I, F> RegionFolder<I, F> {
485 #[inline]
486 pub fn new(cx: I, fold_region_fn: F) -> RegionFolder<I, F> {
487 RegionFolder { cx, current_index: ty::INNERMOST, fold_region_fn }
488 }
489}
490
491impl<I, F> TypeFolder<I> for RegionFolder<I, F>
492where
493 I: Interner,
494 F: FnMut(I::Region, ty::DebruijnIndex) -> I::Region,
495{
496 fn cx(&self) -> I {
497 self.cx
498 }
499
500 fn fold_binder<T: TypeFoldable<I>>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T> {
501 self.current_index.shift_in(1);
502 let t = t.super_fold_with(self);
503 self.current_index.shift_out(1);
504 t
505 }
506
507 #[instrument(skip(self), level = "debug", ret)]
508 fn fold_region(&mut self, r: I::Region) -> I::Region {
509 match r.kind() {
510 ty::ReBound(debruijn, _) if debruijn < self.current_index => {
511 debug!(?self.current_index, "skipped bound region");
512 r
513 }
514 _ => {
515 debug!(?self.current_index, "folding free region");
516 (self.fold_region_fn)(r, self.current_index)
517 }
518 }
519 }
520
521 fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
522 if t.has_type_flags(
523 TypeFlags::HAS_FREE_REGIONS | TypeFlags::HAS_RE_BOUND | TypeFlags::HAS_RE_ERASED,
524 ) {
525 t.super_fold_with(self)
526 } else {
527 t
528 }
529 }
530
531 fn fold_const(&mut self, ct: I::Const) -> I::Const {
532 if ct.has_type_flags(
533 TypeFlags::HAS_FREE_REGIONS | TypeFlags::HAS_RE_BOUND | TypeFlags::HAS_RE_ERASED,
534 ) {
535 ct.super_fold_with(self)
536 } else {
537 ct
538 }
539 }
540
541 fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
542 if p.has_type_flags(
543 TypeFlags::HAS_FREE_REGIONS | TypeFlags::HAS_RE_BOUND | TypeFlags::HAS_RE_ERASED,
544 ) {
545 p.super_fold_with(self)
546 } else {
547 p
548 }
549 }
550}