src/librustc_typeck/check/method/README.md

   1 # Method lookup
   2
   3 Method lookup can be rather complex due to the interaction of a number
   4 of factors, such as self types, autoderef, trait lookup, etc. This
   5 file provides an overview of the process. More detailed notes are in
   6 the code itself, naturally.
   7
   8 One way to think of method lookup is that we convert an expression of
   9 the form:
  10
  11     receiver.method(...)
  12
  13 into a more explicit UFCS form:
  14
  15     Trait::method(ADJ(receiver), ...) // for a trait call
  16     ReceiverType::method(ADJ(receiver), ...) // for an inherent method call
  17
  18 Here `ADJ` is some kind of adjustment, which is typically a series of
  19 autoderefs and then possibly an autoref (e.g., `&**receiver`). However
  20 we sometimes do other adjustments and coercions along the way, in
  21 particular unsizing (e.g., converting from `[T, ..n]` to `[T]`).
  22
  23 ## The Two Phases
  24
  25 Method lookup is divided into two major phases: probing (`probe.rs`)
  26 and confirmation (`confirm.rs`). The probe phase is when we decide
  27 what method to call and how to adjust the receiver. The confirmation
  28 phase "applies" this selection, updating the side-tables, unifying
  29 type variables, and otherwise doing side-effectful things.
  30
  31 One reason for this division is to be more amenable to caching.  The
  32 probe phase produces a "pick" (`probe::Pick`), which is designed to be
  33 cacheable across method-call sites. Therefore, it does not include
  34 inference variables or other information.
  35
  36 ## Probe phase
  37
  38 The probe phase (`probe.rs`) decides what method is being called and
  39 how to adjust the receiver.
  40
  41 ### Steps
  42
  43 The first thing that the probe phase does is to create a series of
  44 *steps*. This is done by progressively dereferencing the receiver type
  45 until it cannot be deref'd anymore, as well as applying an optional
  46 "unsize" step. So if the receiver has type `Rc<Box<[T; 3]>>`, this
  47 might yield:
  48
  49     Rc<Box<[T; 3]>>
  50     Box<[T; 3]>
  51     [T; 3]
  52     [T]
  53
  54 ### Candidate assembly
  55
  56 We then search along those steps to create a list of *candidates*. A
  57 `Candidate` is a method item that might plausibly be the method being
  58 invoked. For each candidate, we'll derive a "transformed self type"
  59 that takes into account explicit self.
  60
  61 Candidates are grouped into two kinds, inherent and extension.
  62
  63 **Inherent candidates** are those that are derived from the
  64 type of the receiver itself.  So, if you have a receiver of some
  65 nominal type `Foo` (e.g., a struct), any methods defined within an
  66 impl like `impl Foo` are inherent methods.  Nothing needs to be
  67 imported to use an inherent method, they are associated with the type
  68 itself (note that inherent impls can only be defined in the same
  69 module as the type itself).
  70
  71 FIXME: Inherent candidates are not always derived from impls.  If you
  72 have a trait object, such as a value of type `Box<ToString>`, then the
  73 trait methods (`to_string()`, in this case) are inherently associated
  74 with it. Another case is type parameters, in which case the methods of
  75 their bounds are inherent. However, this part of the rules is subject
  76 to change: when DST's "impl Trait for Trait" is complete, trait object
  77 dispatch could be subsumed into trait matching, and the type parameter
  78 behavior should be reconsidered in light of where clauses.
  79
  80 **Extension candidates** are derived from imported traits.  If I have
  81 the trait `ToString` imported, and I call `to_string()` on a value of
  82 type `T`, then we will go off to find out whether there is an impl of
  83 `ToString` for `T`.  These kinds of method calls are called "extension
  84 methods".  They can be defined in any module, not only the one that
  85 defined `T`.  Furthermore, you must import the trait to call such a
  86 method.
  87
  88 So, let's continue our example. Imagine that we were calling a method
  89 `foo` with the receiver `Rc<Box<[T; 3]>>` and there is a trait `Foo`
  90 that defines it with `&self` for the type `Rc<U>` as well as a method
  91 on the type `Box` that defines `Foo` but with `&mut self`. Then we
  92 might have two candidates:
  93
  94     &Rc<Box<[T; 3]>> from the impl of `Foo` for `Rc<U>` where `U=Box<T; 3]>
  95     &mut Box<[T; 3]>> from the inherent impl on `Box<U>` where `U=[T; 3]`
  96
  97 ### Candidate search
  98
  99 Finally, to actually pick the method, we will search down the steps,
 100 trying to match the receiver type against the candidate types. At
 101 each step, we also consider an auto-ref and auto-mut-ref to see whether
 102 that makes any of the candidates match. We pick the first step where
 103 we find a match.
 104
 105 In the case of our example, the first step is `Rc<Box<[T; 3]>>`,
 106 which does not itself match any candidate. But when we autoref it, we
 107 get the type `&Rc<Box<[T; 3]>>` which does match. We would then
 108 recursively consider all where-clauses that appear on the impl: if
 109 those match (or we cannot rule out that they do), then this is the
 110 method we would pick. Otherwise, we would continue down the series of
 111 steps.