1# `TypeFoldable` and `TypeFolder` 2 3How is this `subst` query actually implemented? As you can imagine, we might want to do 4substitutions on a lot of different things. For example, we might want to do a substitution directly 5on a type like we did with `Vec` above. But we might also have a more complex type with other types 6nested inside that also need substitutions. 7 8The answer is a couple of traits: 9[`TypeFoldable`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/fold/trait.TypeFoldable.html) 10and 11[`TypeFolder`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/fold/trait.TypeFolder.html). 12 13- `TypeFoldable` is implemented by types that embed type information. It allows you to recursively 14 process the contents of the `TypeFoldable` and do stuff to them. 15- `TypeFolder` defines what you want to do with the types you encounter while processing the 16 `TypeFoldable`. 17 18For example, the `TypeFolder` trait has a method 19[`fold_ty`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/fold/trait.TypeFolder.html#method.fold_ty) 20that takes a type as input a type and returns a new type as a result. `TypeFoldable` invokes the 21`TypeFolder` `fold_foo` methods on itself, giving the `TypeFolder` access to its contents (the 22types, regions, etc that are contained within). 23 24You can think of it with this analogy to the iterator combinators we have come to love in rust: 25 26```rust,ignore 27vec.iter().map(|e1| foo(e2)).collect() 28// ^^^^^^^^^^^^ analogous to `TypeFolder` 29// ^^^ analogous to `TypeFoldable` 30``` 31 32So to reiterate: 33 34- `TypeFolder` is a trait that defines a “map” operation. 35- `TypeFoldable` is a trait that is implemented by things that embed types. 36 37In the case of `subst`, we can see that it is implemented as a `TypeFolder`: 38[`SubstFolder`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/subst/struct.SubstFolder.html). 39Looking at its implementation, we see where the actual substitutions are happening. 40 41However, you might also notice that the implementation calls this `super_fold_with` method. What is 42that? It is a method of `TypeFoldable`. Consider the following `TypeFoldable` type `MyFoldable`: 43 44```rust,ignore 45struct MyFoldable<'tcx> { 46 def_id: DefId, 47 ty: Ty<'tcx>, 48} 49``` 50 51The `TypeFolder` can call `super_fold_with` on `MyFoldable` if it just wants to replace some of the 52fields of `MyFoldable` with new values. If it instead wants to replace the whole `MyFoldable` with a 53different one, it would call `fold_with` instead (a different method on `TypeFoldable`). 54 55In almost all cases, we don’t want to replace the whole struct; we only want to replace `ty::Ty`s in 56the struct, so usually we call `super_fold_with`. A typical implementation that `MyFoldable` could 57have might do something like this: 58 59```rust,ignore 60my_foldable: MyFoldable<'tcx> 61my_foldable.subst(..., subst) 62 63impl TypeFoldable for MyFoldable { 64 fn super_fold_with(&self, folder: &mut impl TypeFolder<'tcx>) -> MyFoldable { 65 MyFoldable { 66 def_id: self.def_id.fold_with(folder), 67 ty: self.ty.fold_with(folder), 68 } 69 } 70 71 fn super_visit_with(..) { } 72} 73``` 74 75Notice that here, we implement `super_fold_with` to go over the fields of `MyFoldable` and call 76`fold_with` on *them*. That is, a folder may replace `def_id` and `ty`, but not the whole 77`MyFoldable` struct. 78 79Here is another example to put things together: suppose we have a type like `Vec<Vec<X>>`. The 80`ty::Ty` would look like: `Adt(Vec, &[Adt(Vec, &[Param(X)])])`. If we want to do `subst(X => u32)`, 81then we would first look at the overall type. We would see that there are no substitutions to be 82made at the outer level, so we would descend one level and look at `Adt(Vec, &[Param(X)])`. There 83are still no substitutions to be made here, so we would descend again. Now we are looking at 84`Param(X)`, which can be substituted, so we replace it with `u32`. We can’t descend any more, so we 85are done, and the overall result is `Adt(Vec, &[Adt(Vec, &[u32])])`. 86 87One last thing to mention: often when folding over a `TypeFoldable`, we don’t want to change most 88things. We only want to do something when we reach a type. That means there may be a lot of 89`TypeFoldable` types whose implementations basically just forward to their fields’ `TypeFoldable` 90implementations. Such implementations of `TypeFoldable` tend to be pretty tedious to write by hand. 91For this reason, there is a `derive` macro that allows you to `#![derive(TypeFoldable)]`. It is 92defined 93[here](https://github.com/rust-lang/rust/blob/master/compiler/rustc_macros/src/type_foldable.rs). 94 95**`subst`** In the case of substitutions the [actual 96folder](https://github.com/rust-lang/rust/blob/75ff3110ac6d8a0259023b83fd20d7ab295f8dd6/src/librustc_middle/ty/subst.rs#L440-L451) 97is going to be doing the indexing we’ve already mentioned. There we define a `Folder` and call 98`fold_with` on the `TypeFoldable` to process yourself. Then 99[fold_ty](https://github.com/rust-lang/rust/blob/75ff3110ac6d8a0259023b83fd20d7ab295f8dd6/src/librustc_middle/ty/subst.rs#L512-L536) 100the method that process each type it looks for a `ty::Param` and for those it replaces it for 101something from the list of substitutions, otherwise recursively process the type. To replace it, 102calls 103[ty_for_param](https://github.com/rust-lang/rust/blob/75ff3110ac6d8a0259023b83fd20d7ab295f8dd6/src/librustc_middle/ty/subst.rs#L552-L587) 104and all that does is index into the list of substitutions with the index of the `Param`. 105 106