Method lookup

Method lookup can be rather complex due to the interaction of a number of factors, such as self types, autoderef, trait lookup, etc. The algorithm is divided into two parts: candidate collection and candidate selection.

Candidate collection

A Candidate is a method item that might plausibly be the method being invoked. Candidates are grouped into two kinds, inherent and extension. Inherent candidates are those that are derived from the type of the receiver itself. So, if you have a receiver of some nominal type Foo (e.g., a struct), any methods defined within an impl like impl Foo are inherent methods. Nothing needs to be imported to use an inherent method, they are associated with the type itself (note that inherent impls can only be defined in the same module as the type itself).

Inherent candidates are not always derived from impls. If you have a trait instance, such as a value of type Box<ToStr>, then the trait methods (to_str(), in this case) are inherently associated with it. Another case is type parameters, in which case the methods of their bounds are inherent.

Extension candidates are derived from imported traits. If I have the trait ToStr imported, and I call to_str() on a value of type T, then we will go off to find out whether there is an impl of ToStr for T. These kinds of method calls are called "extension methods". They can be defined in any module, not only the one that defined T. Furthermore, you must import the trait to call such a method.

For better or worse, we currently give weight to inherent methods over extension methods during candidate selection (below).

Candidate selection

Once we know the set of candidates, we can go off and try to select which one is actually being called. We do this by taking the type of the receiver, let's call it R, and checking whether it matches against the expected receiver type for each of the collected candidates. We first check for inherent candidates and see whether we get exactly one match (zero means keep searching, more than one is an error). If so, we return that as the candidate. Otherwise we search the extension candidates in the same way.

If find no matching candidate at all, we proceed to auto-deref the receiver type and search again. We keep doing that until we cannot auto-deref any longer. At each step, we also check for candidates based on "autoptr", which if the current type is T, checks for &mut T, &const T, and &T receivers. Finally, at the very end, we will also try autoslice, which converts ~[] to &[] (there is no point at trying autoslice earlier, because no autoderefable type is also sliceable).

Why two phases?

You might wonder why we first collect the candidates and then select. Both the inherent candidate collection and the candidate selection proceed by progressively deref'ing the receiver type, after all. The answer is that two phases are needed to elegantly deal with explicit self. After all, if there is an impl for the type Foo, it can define a method with the type Box<self>, which means that it expects a receiver of type Box<Foo>. If we have a receiver of type Box<Foo>, but we waited to search for that impl until we have deref'd the Box away and obtained the type Foo, we would never match this method.