src/doc/rustc-dev-guide/src/ty-fold.md

   1 # `TypeFoldable` and `TypeFolder`
   2
   3 How is this `subst` query actually implemented? As you can imagine, we might want to do
   4 substitutions on a lot of different things. For example, we might want to do a substitution directly
   5 on a type like we did with `Vec` above. But we might also have a more complex type with other types
   6 nested inside that also need substitutions.
   7
   8 The answer is a couple of traits:
   9 [`TypeFoldable`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/fold/trait.TypeFoldable.html)
  10 and
  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
  18 For 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)
  20 that 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
  22 types, regions, etc that are contained within).
  23
  24 You can think of it with this analogy to the iterator combinators we have come to love in rust:
  25
  26 ```rust,ignore
  27 vec.iter().map(|e1| foo(e2)).collect()
  28 //             ^^^^^^^^^^^^ analogous to `TypeFolder`
  29 //         ^^^ analogous to `TypeFoldable`
  30 ```
  31
  32 So 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
  37 In 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).
  39 Looking at its implementation, we see where the actual substitutions are happening.
  40
  41 However, you might also notice that the implementation calls this `super_fold_with` method. What is
  42 that? It is a method of `TypeFoldable`. Consider the following `TypeFoldable` type `MyFoldable`:
  43
  44 ```rust,ignore
  45 struct MyFoldable<'tcx> {
  46   def_id: DefId,
  47   ty: Ty<'tcx>,
  48 }
  49 ```
  50
  51 The `TypeFolder` can call `super_fold_with` on `MyFoldable` if it just wants to replace some of the
  52 fields of `MyFoldable` with new values. If it instead wants to replace the whole `MyFoldable` with a
  53 different one, it would call `fold_with` instead (a different method on `TypeFoldable`).
  54
  55 In almost all cases, we don’t want to replace the whole struct; we only want to replace `ty::Ty`s in
  56 the struct, so usually we call `super_fold_with`. A typical implementation that `MyFoldable` could
  57 have might do something like this:
  58
  59 ```rust,ignore
  60 my_foldable: MyFoldable<'tcx>
  61 my_foldable.subst(..., subst)
  62
  63 impl 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
  75 Notice 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
  79 Here 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)`,
  81 then we would first look at the overall type. We would see that there are no substitutions to be
  82 made at the outer level, so we would descend one level and look at `Adt(Vec, &[Param(X)])`. There
  83 are 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
  85 are done, and  the overall result is `Adt(Vec, &[Adt(Vec, &[u32])])`.
  86
  87 One last thing to mention: often when folding over a `TypeFoldable`, we don’t want to change most
  88 things. 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`
  90 implementations. Such implementations of `TypeFoldable` tend to be pretty tedious to write by hand.
  91 For this reason, there is a `derive` macro that allows you to `#![derive(TypeFoldable)]`. It is
  92 defined
  93 [here](https://github.com/rust-lang/rust/blob/master/src/librustc_macros/src/type_foldable.rs).
  94
  95 **`subst`** In the case of substitutions the [actual
  96 folder](https://github.com/rust-lang/rust/blob/75ff3110ac6d8a0259023b83fd20d7ab295f8dd6/src/librustc_middle/ty/subst.rs#L440-L451)
  97 is 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)
 100 the method that process each type it looks for a `ty::Param` and for those it replaces it for
 101 something from the list of substitutions, otherwise recursively process the type.  To replace it,
 102 calls
 103 [ty_for_param](https://github.com/rust-lang/rust/blob/75ff3110ac6d8a0259023b83fd20d7ab295f8dd6/src/librustc_middle/ty/subst.rs#L552-L587)
 104 and all that does is index into the list of substitutions with the index of the `Param`.
 105