src/doc/rustc-dev-guide/src/generics.md

   1 # Generics and substitutions
   2
   3 Given a generic type `MyType<A, B, …>`, we may want to swap out the generics `A, B, …` for some
   4 other types (possibly other generics or concrete types). We do this a lot while doing type
   5 inference, type checking, and trait solving. Conceptually, during these routines, we may find out
   6 that one type is equal to another type and want to swap one out for the other and then swap that out
   7 for another type and so on until we eventually get some concrete types (or an error).
   8
   9 In rustc this is done using [SubstsRef] (“substs” = “substitutions”).
  10 Conceptually, you can think of `SubstsRef` as a list of types that are to be substituted for the
  11 generic type parameters of the ADT.
  12
  13 `SubstsRef` is a type alias of `&'tcx List<GenericArg<'tcx>>` (see [`List` rustdocs][list]).
  14 [`GenericArg`] is essentially a space-efficient wrapper around [`GenericArgKind`], which is an enum
  15 indicating what kind of generic the type parameter is (type, lifetime, or const).  Thus, `SubstsRef`
  16 is conceptually like a `&'tcx [GenericArgKind<'tcx>]` slice (but it is actually a `List`).
  17
  18 [list]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.List.html
  19 [`GenericArg`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/subst/struct.GenericArg.html
  20 [`GenericArgKind`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/subst/enum.GenericArgKind.html
  21 [SubstsRef]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/subst/type.SubstsRef.html
  22
  23 So why do we use this `List` type instead of making it really a slice? It has the length "inline",
  24 so `&List` is only 32 bits. As a consequence, it cannot be "subsliced" (that only works if the
  25 length is out of line).
  26
  27 This also implies that you can check two `List`s for equality via `==` (which would be not be
  28 possible for ordinary slices). This is precisely because they never represent a "sub-list", only the
  29 complete `List`, which has been hashed and interned.
  30
  31 So pulling it all together, let’s go back to our example above:
  32
  33 ```rust,ignore
  34 struct MyStruct<T>
  35 ```
  36
  37 - There would be an `AdtDef` (and corresponding `DefId`) for `MyStruct`.
  38 - There would be a `TyKind::Param` (and corresponding `DefId`) for `T` (more later).
  39 - There would be a `SubstsRef` containing the list `[GenericArgKind::Type(Ty(T))]`
  40     - The `Ty(T)` here is my shorthand for entire other `ty::Ty` that has `TyKind::Param`, which we
  41       mentioned in the previous point.
  42 - This is one `TyKind::Adt` containing the `AdtDef` of `MyStruct` with the `SubstsRef` above.
  43
  44 Finally, we will quickly mention the
  45 [`Generics`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/struct.Generics.html) type. It
  46 is used to give information about the type parameters of a type.
  47
  48 ### Unsubstituted Generics
  49
  50 So above, recall that in our example the `MyStruct` struct had a generic type `T`. When we are (for
  51 example) type checking functions that use `MyStruct`, we will need to be able to refer to this type
  52 `T` without actually knowing what it is. In general, this is true inside all generic definitions: we
  53 need to be able to work with unknown types. This is done via `TyKind::Param` (which we mentioned in
  54 the example above).
  55
  56 Each `TyKind::Param` contains two things: the name and the index. In general, the index fully
  57 defines the parameter and is used by most of the code. The name is included for debug print-outs.
  58 There are two reasons for this. First, the index is convenient, it allows you to include into the
  59 list of generic arguments when substituting. Second, the index is more robust. For example, you
  60 could in principle have two distinct type parameters that use the same name, e.g. `impl<A> Foo<A> {
  61 fn bar<A>() { .. } }`, although the rules against shadowing make this difficult (but those language
  62 rules could change in the future).
  63
  64 The index of the type parameter is an integer indicating its order in the list of the type
  65 parameters. Moreover, we consider the list to include all of the type parameters from outer scopes.
  66 Consider the following example:
  67
  68 ```rust,ignore
  69 struct Foo<A, B> {
  70   // A would have index 0
  71   // B would have index 1
  72
  73   .. // some fields
  74 }
  75 impl<X, Y> Foo<X, Y> {
  76   fn method<Z>() {
  77     // inside here, X, Y and Z are all in scope
  78     // X has index 0
  79     // Y has index 1
  80     // Z has index 2
  81   }
  82 }
  83 ```
  84
  85 When we are working inside the generic definition, we will use `TyKind::Param` just like any other
  86 `TyKind`; it is just a type after all. However, if we want to use the generic type somewhere, then
  87 we will need to do substitutions.
  88
  89 For example suppose that the `Foo<A, B>` type from the previous example has a field that is a
  90 `Vec<A>`. Observe that `Vec` is also a generic type. We want to tell the compiler that the type
  91 parameter of `Vec` should be replaced with the `A` type parameter of `Foo<A, B>`. We do that with
  92 substitutions:
  93
  94 ```rust,ignore
  95 struct Foo<A, B> { // Adt(Foo, &[Param(0), Param(1)])
  96   x: Vec<A>, // Adt(Vec, &[Param(0)])
  97   ..
  98 }
  99
 100 fn bar(foo: Foo<u32, f32>) { // Adt(Foo, &[u32, f32])
 101   let y = foo.x; // Vec<Param(0)> => Vec<u32>
 102 }
 103 ```
 104
 105 This example has a few different substitutions:
 106
 107 - In the definition of `Foo`, in the type of the field `x`, we replace `Vec`'s type parameter with
 108   `Param(0)`, the first parameter of `Foo<A, B>`, so that the type of `x` is `Vec<A>`.
 109 - In the function `bar`, we specify that we want a `Foo<u32, f32>`. This means that we will
 110   substitute `Param(0)` and `Param(1)` with `u32` and `f32`.
 111 - In the body of `bar`, we access `foo.x`, which has type `Vec<Param(0)>`, but `Param(0)` has been
 112   substituted for `u32`, so `foo.x` has type `Vec<u32>`.
 113
 114 Let’s look a bit more closely at that last substitution to see why we use indexes. If we want to
 115 find the type of `foo.x`, we can get generic type of `x`, which is `Vec<Param(0)>`. Now we can take
 116 the index `0` and use it to find the right type substitution: looking at `Foo`'s `SubstsRef`, we
 117 have the list `[u32, f32]` , since we want to replace index `0`, we take the 0-th index of this
 118 list, which is `u32`. Voila!
 119
 120 You may have a couple of followup questions…
 121
 122  **`type_of`** How do we get the “generic type of `x`"? You can get the type of pretty much anything
 123  with the   `tcx.type_of(def_id)` query. In this case, we would pass the `DefId` of the field `x`.
 124  The `type_of` query always returns the definition with the generics that are in scope of the
 125  definition. For example, `tcx.type_of(def_id_of_my_struct)` would return the “self-view” of
 126  `MyStruct`: `Adt(Foo, &[Param(0), Param(1)])`.
 127
 128 **`subst`** How do we actually do the substitutions? There is a function for that too! You use
 129 [`subst`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/subst/struct.EarlyBinder.html#method.subst) to
 130 replace a `SubstsRef` with another list of types.
 131
 132 [Here is an example of actually using `subst` in the compiler][substex].  The exact details are not
 133 too important, but in this piece of code, we happen to be converting from the `rustc_hir::Ty` to
 134 a real `ty::Ty`. You can see that we first get some substitutions (`substs`).  Then we call
 135 `type_of` to get a type and call `ty.subst(substs)` to get a new version of `ty` with
 136 the substitutions made.
 137
 138 [substex]: https://github.com/rust-lang/rust/blob/0940040c0486a536be4f8685c7dd9a078f9e87c2/compiler/rustc_hir_analysis/src/astconv/mod.rs#L1231-L1242
 139
 140 **Note on indices:** It is possible for the indices in `Param` to not match with what we expect. For
 141 example, the index could be out of bounds or it could be the index of a lifetime when we were
 142 expecting a type. These sorts of errors would be caught earlier in the compiler when translating
 143 from a `rustc_hir::Ty` to a `ty::Ty`. If they occur later, that is a compiler bug.
 144
 145