src/doc/rustc-dev-guide/src/traits/associated-types.md

   1 # Equality and associated types
   2
   3 This section covers how the trait system handles equality between
   4 associated types. The full system consists of several moving parts,
   5 which we will introduce one by one:
   6
   7 - Projection and the `Normalize` predicate
   8 - Placeholder associated type projections
   9 - The `ProjectionEq` predicate
  10 - Integration with unification
  11
  12 ## Associated type projection and normalization
  13
  14 When a trait defines an associated type (e.g.,
  15 [the `Item` type in the `IntoIterator` trait][intoiter-item]), that
  16 type can be referenced by the user using an **associated type
  17 projection** like `<Option<u32> as IntoIterator>::Item`.
  18
  19 > Often, people will use the shorthand syntax `T::Item`. Presently, that
  20 > syntax is expanded during ["type collection"](../type-checking.html) into the
  21 > explicit form, though that is something we may want to change in the future.
  22
  23 [intoiter-item]: https://doc.rust-lang.org/nightly/core/iter/trait.IntoIterator.html#associatedtype.Item
  24
  25 <a name="normalize"></a>
  26
  27 In some cases, associated type projections can be **normalized** –
  28 that is, simplified – based on the types given in an impl. So, to
  29 continue with our example, the impl of `IntoIterator` for `Option<T>`
  30 declares (among other things) that `Item = T`:
  31
  32 ```rust,ignore
  33 impl<T> IntoIterator for Option<T> {
  34   type Item = T;
  35   ...
  36 }
  37 ```
  38
  39 This means we can normalize the projection `<Option<u32> as
  40 IntoIterator>::Item` to just `u32`.
  41
  42 In this case, the projection was a "monomorphic" one – that is, it
  43 did not have any type parameters.  Monomorphic projections are special
  44 because they can **always** be fully normalized.
  45
  46 Often, we can normalize other associated type projections as well. For
  47 example, `<Option<?T> as IntoIterator>::Item`, where `?T` is an inference
  48 variable, can be normalized to just `?T`.
  49
  50 In our logic, normalization is defined by a predicate
  51 `Normalize`. The `Normalize` clauses arise only from
  52 impls. For example, the `impl` of `IntoIterator` for `Option<T>` that
  53 we saw above would be lowered to a program clause like so:
  54
  55 ```text
  56 forall<T> {
  57     Normalize(<Option<T> as IntoIterator>::Item -> T) :-
  58         Implemented(Option<T>: IntoIterator)
  59 }
  60 ```
  61
  62 where in this case, the one `Implemented` condition is always true.
  63
  64 > Since we do not permit quantification over traits, this is really more like
  65 > a family of program clauses, one for each associated type.
  66
  67 We could apply that rule to normalize either of the examples that
  68 we've seen so far.
  69
  70 ## Placeholder associated types
  71
  72 Sometimes however we want to work with associated types that cannot be
  73 normalized. For example, consider this function:
  74
  75 ```rust,ignore
  76 fn foo<T: IntoIterator>(...) { ... }
  77 ```
  78
  79 In this context, how would we normalize the type `T::Item`?
  80
  81 Without knowing what `T` is, we can't really do so. To represent this case,
  82 we introduce a type called a **placeholder associated type projection**. This
  83 is written like so: `(IntoIterator::Item)<T>`.
  84
  85 You may note that it looks a lot like a regular type (e.g., `Option<T>`),
  86 except that the "name" of the type is `(IntoIterator::Item)`. This is not an
  87 accident: placeholder associated type projections work just like ordinary
  88 types like `Vec<T>` when it comes to unification. That is, they are only
  89 considered equal if (a) they are both references to the same associated type,
  90 like `IntoIterator::Item` and (b) their type arguments are equal.
  91
  92 Placeholder associated types are never written directly by the user.
  93 They are used internally by the trait system only, as we will see
  94 shortly.
  95
  96 In rustc, they correspond to the `TyKind::UnnormalizedProjectionTy` enum
  97 variant, declared in [`librustc/ty/sty.rs`][sty]. In chalk, we use an
  98 `ApplicationTy` with a name living in a special namespace dedicated to
  99 placeholder associated types (see the `TypeName` enum declared in
 100 [`chalk-ir/src/lib.rs`][chalk_type_name]).
 101
 102 [sty]: https://github.com/rust-lang/rust/blob/master/src/librustc/ty/sty.rs
 103 [chalk_type_name]: https://github.com/rust-lang-nursery/chalk/blob/master/chalk-ir/src/lib.rs
 104
 105 ## Projection equality
 106
 107 So far we have seen two ways to answer the question of "When can we
 108 consider an associated type projection equal to another type?":
 109
 110 - the `Normalize` predicate could be used to transform projections when we
 111   knew which impl applied;
 112 - **placeholder** associated types can be used when we don't. This is also
 113   known as **lazy normalization**.
 114
 115 We now introduce the `ProjectionEq` predicate to bring those two cases
 116 together. The `ProjectionEq` predicate looks like so:
 117
 118 ```text
 119 ProjectionEq(<T as IntoIterator>::Item = U)
 120 ```
 121
 122 and we will see that it can be proven *either* via normalization or
 123 via the placeholder type. As part of lowering an associated type declaration from
 124 some trait, we create two program clauses for `ProjectionEq`:
 125
 126 ```text
 127 forall<T, U> {
 128     ProjectionEq(<T as IntoIterator>::Item = U) :-
 129         Normalize(<T as IntoIterator>::Item -> U)
 130 }
 131
 132 forall<T> {
 133     ProjectionEq(<T as IntoIterator>::Item = (IntoIterator::Item)<T>)
 134 }
 135 ```
 136
 137 These are the only two `ProjectionEq` program clauses we ever make for
 138 any given associated item.
 139
 140 ## Integration with unification
 141
 142 Now we are ready to discuss how associated type equality integrates
 143 with unification. As described in the
 144 [type inference](../type-inference.html) section, unification is
 145 basically a procedure with a signature like this:
 146
 147 ```text
 148 Unify(A, B) = Result<(Subgoals, RegionConstraints), NoSolution>
 149 ```
 150
 151 In other words, we try to unify two things A and B. That procedure
 152 might just fail, in which case we get back `Err(NoSolution)`. This
 153 would happen, for example, if we tried to unify `u32` and `i32`.
 154
 155 The key point is that, on success, unification can also give back to
 156 us a set of subgoals that still remain to be proven. (It can also give
 157 back region constraints, but those are not relevant here).
 158
 159 Whenever unification encounters a non-placeholder associated type
 160 projection P being equated with some other type T, it always succeeds,
 161 but it produces a subgoal `ProjectionEq(P = T)` that is propagated
 162 back up. Thus it falls to the ordinary workings of the trait system
 163 to process that constraint.
 164
 165 > If we unify two projections P1 and P2, then unification produces a
 166 > variable X and asks us to prove that `ProjectionEq(P1 = X)` and
 167 > `ProjectionEq(P2 = X)`. (That used to be needed in an older system to
 168 > prevent cycles; I rather doubt it still is. -nmatsakis)