src/librustc/middle/typeck/check/method/doc.rs

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