rustc_type_ir/
fold.rs

1//! A folding traversal mechanism for complex data structures that contain type
2//! information.
3//!
4//! This is a modifying traversal. It consumes the data structure, producing a
5//! (possibly) modified version of it. Both fallible and infallible versions are
6//! available. The name is potentially confusing, because this traversal is more
7//! like `Iterator::map` than `Iterator::fold`.
8//!
9//! This traversal has limited flexibility. Only a small number of "types of
10//! interest" within the complex data structures can receive custom
11//! modification. These are the ones containing the most important type-related
12//! information, such as `Ty`, `Predicate`, `Region`, and `Const`.
13//!
14//! There are three traits involved in each traversal.
15//! - `TypeFoldable`. This is implemented once for many types, including:
16//!   - Types of interest, for which the methods delegate to the folder.
17//!   - All other types, including generic containers like `Vec` and `Option`.
18//!     It defines a "skeleton" of how they should be folded.
19//! - `TypeSuperFoldable`. This is implemented only for recursive types of
20//!   interest, and defines the folding "skeleton" for these types. (This
21//!   excludes `Region` because it is non-recursive, i.e. it never contains
22//!   other types of interest.)
23//! - `TypeFolder`/`FallibleTypeFolder`. One of these is implemented for each
24//!   folder. This defines how types of interest are folded.
25//!
26//! This means each fold is a mixture of (a) generic folding operations, and (b)
27//! custom fold operations that are specific to the folder.
28//! - The `TypeFoldable` impls handle most of the traversal, and call into
29//!   `TypeFolder`/`FallibleTypeFolder` when they encounter a type of interest.
30//! - A `TypeFolder`/`FallibleTypeFolder` may call into another `TypeFoldable`
31//!   impl, because some of the types of interest are recursive and can contain
32//!   other types of interest.
33//! - A `TypeFolder`/`FallibleTypeFolder` may also call into a `TypeSuperFoldable`
34//!   impl, because each folder might provide custom handling only for some types
35//!   of interest, or only for some variants of each type of interest, and then
36//!   use default traversal for the remaining cases.
37//!
38//! For example, if you have `struct S(Ty, U)` where `S: TypeFoldable` and `U:
39//! TypeFoldable`, and an instance `s = S(ty, u)`, it would be folded like so:
40//! ```text
41//! s.fold_with(folder) calls
42//! - ty.fold_with(folder) calls
43//!   - folder.fold_ty(ty) may call
44//!     - ty.super_fold_with(folder)
45//! - u.fold_with(folder)
46//! ```
47
48use std::mem;
49use std::sync::Arc;
50
51use rustc_index::{Idx, IndexVec};
52use thin_vec::ThinVec;
53use tracing::{debug, instrument};
54
55use crate::inherent::*;
56use crate::visit::{TypeVisitable, TypeVisitableExt as _};
57use crate::{self as ty, Interner};
58
59#[cfg(feature = "nightly")]
60type Never = !;
61
62#[cfg(not(feature = "nightly"))]
63type Never = std::convert::Infallible;
64
65/// This trait is implemented for every type that can be folded,
66/// providing the skeleton of the traversal.
67///
68/// To implement this conveniently, use the derive macro located in
69/// `rustc_macros`.
70///
71/// This trait is a sub-trait of `TypeVisitable`. This is because many
72/// `TypeFolder` instances use the methods in `TypeVisitableExt` while folding,
73/// which means in practice almost every foldable type needs to also be
74/// visitable. (However, there are some types that are visitable without being
75/// foldable.)
76pub trait TypeFoldable<I: Interner>: TypeVisitable<I> + Clone {
77    /// The entry point for folding. To fold a value `t` with a folder `f`
78    /// call: `t.try_fold_with(f)`.
79    ///
80    /// For most types, this just traverses the value, calling `try_fold_with`
81    /// on each field/element.
82    ///
83    /// For types of interest (such as `Ty`), the implementation of this method
84    /// calls a folder method specifically for that type (such as
85    /// `F::try_fold_ty`). This is where control transfers from `TypeFoldable`
86    /// to `TypeFolder`.
87    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error>;
88
89    /// A convenient alternative to `try_fold_with` for use with infallible
90    /// folders. Do not override this method, to ensure coherence with
91    /// `try_fold_with`.
92    fn fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
93        match self.try_fold_with(folder) {
94            Ok(t) => t,
95        }
96    }
97}
98
99// This trait is implemented for types of interest.
100pub trait TypeSuperFoldable<I: Interner>: TypeFoldable<I> {
101    /// Provides a default fold for a recursive type of interest. This should
102    /// only be called within `TypeFolder` methods, when a non-custom traversal
103    /// is desired for the value of the type of interest passed to that method.
104    /// For example, in `MyFolder::try_fold_ty(ty)`, it is valid to call
105    /// `ty.try_super_fold_with(self)`, but any other folding should be done
106    /// with `xyz.try_fold_with(self)`.
107    fn try_super_fold_with<F: FallibleTypeFolder<I>>(
108        self,
109        folder: &mut F,
110    ) -> Result<Self, F::Error>;
111
112    /// A convenient alternative to `try_super_fold_with` for use with
113    /// infallible folders. Do not override this method, to ensure coherence
114    /// with `try_super_fold_with`.
115    fn super_fold_with<F: TypeFolder<I>>(self, folder: &mut F) -> Self {
116        match self.try_super_fold_with(folder) {
117            Ok(t) => t,
118        }
119    }
120}
121
122/// This trait is implemented for every infallible folding traversal. There is
123/// a fold method defined for every type of interest. Each such method has a
124/// default that does an "identity" fold. Implementations of these methods
125/// often fall back to a `super_fold_with` method if the primary argument
126/// doesn't satisfy a particular condition.
127///
128/// A blanket implementation of [`FallibleTypeFolder`] will defer to
129/// the infallible methods of this trait to ensure that the two APIs
130/// are coherent.
131pub trait TypeFolder<I: Interner>: FallibleTypeFolder<I, Error = Never> {
132    fn cx(&self) -> I;
133
134    fn fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T>
135    where
136        T: TypeFoldable<I>,
137    {
138        t.super_fold_with(self)
139    }
140
141    fn fold_ty(&mut self, t: I::Ty) -> I::Ty {
142        t.super_fold_with(self)
143    }
144
145    // The default region folder is a no-op because `Region` is non-recursive
146    // and has no `super_fold_with` method to call.
147    fn fold_region(&mut self, r: I::Region) -> I::Region {
148        r
149    }
150
151    fn fold_const(&mut self, c: I::Const) -> I::Const {
152        c.super_fold_with(self)
153    }
154
155    fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
156        p.super_fold_with(self)
157    }
158}
159
160/// This trait is implemented for every folding traversal. There is a fold
161/// method defined for every type of interest. Each such method has a default
162/// that does an "identity" fold.
163///
164/// A blanket implementation of this trait (that defers to the relevant
165/// method of [`TypeFolder`]) is provided for all infallible folders in
166/// order to ensure the two APIs are coherent.
167pub trait FallibleTypeFolder<I: Interner>: Sized {
168    type Error;
169
170    fn cx(&self) -> I;
171
172    fn try_fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> Result<ty::Binder<I, T>, Self::Error>
173    where
174        T: TypeFoldable<I>,
175    {
176        t.try_super_fold_with(self)
177    }
178
179    fn try_fold_ty(&mut self, t: I::Ty) -> Result<I::Ty, Self::Error> {
180        t.try_super_fold_with(self)
181    }
182
183    // The default region folder is a no-op because `Region` is non-recursive
184    // and has no `super_fold_with` method to call.
185    fn try_fold_region(&mut self, r: I::Region) -> Result<I::Region, Self::Error> {
186        Ok(r)
187    }
188
189    fn try_fold_const(&mut self, c: I::Const) -> Result<I::Const, Self::Error> {
190        c.try_super_fold_with(self)
191    }
192
193    fn try_fold_predicate(&mut self, p: I::Predicate) -> Result<I::Predicate, Self::Error> {
194        p.try_super_fold_with(self)
195    }
196}
197
198// This blanket implementation of the fallible trait for infallible folders
199// delegates to infallible methods to ensure coherence.
200impl<I: Interner, F> FallibleTypeFolder<I> for F
201where
202    F: TypeFolder<I>,
203{
204    type Error = Never;
205
206    fn cx(&self) -> I {
207        TypeFolder::cx(self)
208    }
209
210    fn try_fold_binder<T>(&mut self, t: ty::Binder<I, T>) -> Result<ty::Binder<I, T>, Never>
211    where
212        T: TypeFoldable<I>,
213    {
214        Ok(self.fold_binder(t))
215    }
216
217    fn try_fold_ty(&mut self, t: I::Ty) -> Result<I::Ty, Never> {
218        Ok(self.fold_ty(t))
219    }
220
221    fn try_fold_region(&mut self, r: I::Region) -> Result<I::Region, Never> {
222        Ok(self.fold_region(r))
223    }
224
225    fn try_fold_const(&mut self, c: I::Const) -> Result<I::Const, Never> {
226        Ok(self.fold_const(c))
227    }
228
229    fn try_fold_predicate(&mut self, p: I::Predicate) -> Result<I::Predicate, Never> {
230        Ok(self.fold_predicate(p))
231    }
232}
233
234///////////////////////////////////////////////////////////////////////////
235// Traversal implementations.
236
237impl<I: Interner, T: TypeFoldable<I>, U: TypeFoldable<I>> TypeFoldable<I> for (T, U) {
238    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<(T, U), F::Error> {
239        Ok((self.0.try_fold_with(folder)?, self.1.try_fold_with(folder)?))
240    }
241}
242
243impl<I: Interner, A: TypeFoldable<I>, B: TypeFoldable<I>, C: TypeFoldable<I>> TypeFoldable<I>
244    for (A, B, C)
245{
246    fn try_fold_with<F: FallibleTypeFolder<I>>(
247        self,
248        folder: &mut F,
249    ) -> Result<(A, B, C), F::Error> {
250        Ok((
251            self.0.try_fold_with(folder)?,
252            self.1.try_fold_with(folder)?,
253            self.2.try_fold_with(folder)?,
254        ))
255    }
256}
257
258impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Option<T> {
259    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
260        Ok(match self {
261            Some(v) => Some(v.try_fold_with(folder)?),
262            None => None,
263        })
264    }
265}
266
267impl<I: Interner, T: TypeFoldable<I>, E: TypeFoldable<I>> TypeFoldable<I> for Result<T, E> {
268    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
269        Ok(match self {
270            Ok(v) => Ok(v.try_fold_with(folder)?),
271            Err(e) => Err(e.try_fold_with(folder)?),
272        })
273    }
274}
275
276impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Arc<T> {
277    fn try_fold_with<F: FallibleTypeFolder<I>>(mut self, folder: &mut F) -> Result<Self, F::Error> {
278        // We merely want to replace the contained `T`, if at all possible,
279        // so that we don't needlessly allocate a new `Arc` or indeed clone
280        // the contained type.
281        unsafe {
282            // First step is to ensure that we have a unique reference to
283            // the contained type, which `Arc::make_mut` will accomplish (by
284            // allocating a new `Arc` and cloning the `T` only if required).
285            // This is done *before* casting to `Arc<ManuallyDrop<T>>` so that
286            // panicking during `make_mut` does not leak the `T`.
287            Arc::make_mut(&mut self);
288
289            // Casting to `Arc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
290            // is `repr(transparent)`.
291            let ptr = Arc::into_raw(self).cast::<mem::ManuallyDrop<T>>();
292            let mut unique = Arc::from_raw(ptr);
293
294            // Call to `Arc::make_mut` above guarantees that `unique` is the
295            // sole reference to the contained value, so we can avoid doing
296            // a checked `get_mut` here.
297            let slot = Arc::get_mut(&mut unique).unwrap_unchecked();
298
299            // Semantically move the contained type out from `unique`, fold
300            // it, then move the folded value back into `unique`. Should
301            // folding fail, `ManuallyDrop` ensures that the "moved-out"
302            // value is not re-dropped.
303            let owned = mem::ManuallyDrop::take(slot);
304            let folded = owned.try_fold_with(folder)?;
305            *slot = mem::ManuallyDrop::new(folded);
306
307            // Cast back to `Arc<T>`.
308            Ok(Arc::from_raw(Arc::into_raw(unique).cast()))
309        }
310    }
311}
312
313impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Box<T> {
314    fn try_fold_with<F: FallibleTypeFolder<I>>(mut self, folder: &mut F) -> Result<Self, F::Error> {
315        *self = (*self).try_fold_with(folder)?;
316        Ok(self)
317    }
318}
319
320impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Vec<T> {
321    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
322        self.into_iter().map(|t| t.try_fold_with(folder)).collect()
323    }
324}
325
326impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for ThinVec<T> {
327    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
328        self.into_iter().map(|t| t.try_fold_with(folder)).collect()
329    }
330}
331
332impl<I: Interner, T: TypeFoldable<I>> TypeFoldable<I> for Box<[T]> {
333    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
334        Vec::from(self).try_fold_with(folder).map(Vec::into_boxed_slice)
335    }
336}
337
338impl<I: Interner, T: TypeFoldable<I>, Ix: Idx> TypeFoldable<I> for IndexVec<Ix, T> {
339    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
340        self.raw.try_fold_with(folder).map(IndexVec::from_raw)
341    }
342}
343
344///////////////////////////////////////////////////////////////////////////
345// Shifter
346//
347// Shifts the De Bruijn indices on all escaping bound vars by a
348// fixed amount. Useful in instantiation or when otherwise introducing
349// a binding level that is not intended to capture the existing bound
350// vars. See comment on `shift_vars_through_binders` method in
351// `rustc_middle/src/ty/generic_args.rs` for more details.
352
353struct Shifter<I: Interner> {
354    cx: I,
355    current_index: ty::DebruijnIndex,
356    amount: u32,
357}
358
359impl<I: Interner> Shifter<I> {
360    fn new(cx: I, amount: u32) -> Self {
361        Shifter { cx, current_index: ty::INNERMOST, amount }
362    }
363}
364
365impl<I: Interner> TypeFolder<I> for Shifter<I> {
366    fn cx(&self) -> I {
367        self.cx
368    }
369
370    fn fold_binder<T: TypeFoldable<I>>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T> {
371        self.current_index.shift_in(1);
372        let t = t.super_fold_with(self);
373        self.current_index.shift_out(1);
374        t
375    }
376
377    fn fold_region(&mut self, r: I::Region) -> I::Region {
378        match r.kind() {
379            ty::ReBound(debruijn, br) if debruijn >= self.current_index => {
380                let debruijn = debruijn.shifted_in(self.amount);
381                Region::new_bound(self.cx, debruijn, br)
382            }
383            _ => r,
384        }
385    }
386
387    fn fold_ty(&mut self, ty: I::Ty) -> I::Ty {
388        match ty.kind() {
389            ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => {
390                let debruijn = debruijn.shifted_in(self.amount);
391                Ty::new_bound(self.cx, debruijn, bound_ty)
392            }
393
394            _ if ty.has_vars_bound_at_or_above(self.current_index) => ty.super_fold_with(self),
395            _ => ty,
396        }
397    }
398
399    fn fold_const(&mut self, ct: I::Const) -> I::Const {
400        match ct.kind() {
401            ty::ConstKind::Bound(debruijn, bound_ct) if debruijn >= self.current_index => {
402                let debruijn = debruijn.shifted_in(self.amount);
403                Const::new_bound(self.cx, debruijn, bound_ct)
404            }
405            _ => ct.super_fold_with(self),
406        }
407    }
408
409    fn fold_predicate(&mut self, p: I::Predicate) -> I::Predicate {
410        if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p }
411    }
412}
413
414pub fn shift_region<I: Interner>(cx: I, region: I::Region, amount: u32) -> I::Region {
415    match region.kind() {
416        ty::ReBound(debruijn, br) if amount > 0 => {
417            Region::new_bound(cx, debruijn.shifted_in(amount), br)
418        }
419        _ => region,
420    }
421}
422
423#[instrument(level = "trace", skip(cx), ret)]
424pub fn shift_vars<I: Interner, T>(cx: I, value: T, amount: u32) -> T
425where
426    T: TypeFoldable<I>,
427{
428    if amount == 0 || !value.has_escaping_bound_vars() {
429        value
430    } else {
431        value.fold_with(&mut Shifter::new(cx, amount))
432    }
433}
434
435///////////////////////////////////////////////////////////////////////////
436// Region folder
437
438pub fn fold_regions<I: Interner, T>(
439    cx: I,
440    value: T,
441    mut f: impl FnMut(I::Region, ty::DebruijnIndex) -> I::Region,
442) -> T
443where
444    T: TypeFoldable<I>,
445{
446    value.fold_with(&mut RegionFolder::new(cx, &mut f))
447}
448
449/// Folds over the substructure of a type, visiting its component
450/// types and all regions that occur *free* within it.
451///
452/// That is, function pointer types and trait object can introduce
453/// new bound regions which are not visited by this visitors as
454/// they are not free; only regions that occur free will be
455/// visited by `fld_r`.
456pub struct RegionFolder<'a, I: Interner> {
457    cx: I,
458
459    /// Stores the index of a binder *just outside* the stuff we have
460    /// visited. So this begins as INNERMOST; when we pass through a
461    /// binder, it is incremented (via `shift_in`).
462    current_index: ty::DebruijnIndex,
463
464    /// Callback invokes for each free region. The `DebruijnIndex`
465    /// points to the binder *just outside* the ones we have passed
466    /// through.
467    fold_region_fn: &'a mut (dyn FnMut(I::Region, ty::DebruijnIndex) -> I::Region + 'a),
468}
469
470impl<'a, I: Interner> RegionFolder<'a, I> {
471    #[inline]
472    pub fn new(
473        cx: I,
474        fold_region_fn: &'a mut dyn FnMut(I::Region, ty::DebruijnIndex) -> I::Region,
475    ) -> RegionFolder<'a, I> {
476        RegionFolder { cx, current_index: ty::INNERMOST, fold_region_fn }
477    }
478}
479
480impl<'a, I: Interner> TypeFolder<I> for RegionFolder<'a, I> {
481    fn cx(&self) -> I {
482        self.cx
483    }
484
485    fn fold_binder<T: TypeFoldable<I>>(&mut self, t: ty::Binder<I, T>) -> ty::Binder<I, T> {
486        self.current_index.shift_in(1);
487        let t = t.super_fold_with(self);
488        self.current_index.shift_out(1);
489        t
490    }
491
492    #[instrument(skip(self), level = "debug", ret)]
493    fn fold_region(&mut self, r: I::Region) -> I::Region {
494        match r.kind() {
495            ty::ReBound(debruijn, _) if debruijn < self.current_index => {
496                debug!(?self.current_index, "skipped bound region");
497                r
498            }
499            _ => {
500                debug!(?self.current_index, "folding free region");
501                (self.fold_region_fn)(r, self.current_index)
502            }
503        }
504    }
505}