Autoref priority rules

[QuietMisdreavus]

This is a port of rust-lang/rust#26007.

The following is actually a comment on that thread, describing the rules in question:

I've never commented on this bug it seems. These rules are indeed intentional and yes they are the result of an interplay between autoderef rules and prioritization. The algorithm is that we first arrange a series of steps which correspond to increasing amounts of deref operations. We will try these steps in order and stop at the first step for which we find methods. Within a given step, we will give inherent methods priority over trait methods.

This ordering is the result of a lot of experimentation and making changes to it will definitely cause massive breakage. Before 1.0, I did spend some time experimenting with different "cleaner" strategies, but abandoned it because they broke a lot of code and by and large made things work less well (i.e., more explicit * and &).

The exact algorithm:

• Assemble list of types found by repeatedly deref'ing, with the addition of a single "unsize" step.
  • Example: if receiver is Box<Vec<T>>, we would produce:
    • Box<Vec>
    • Vec (deref)
    • [T] (unsize)
• Iterate down that list, and for each type X:
  • Try with receiver of X (no adjustments), then &X (one autoref), then &mut X (one autoref-mut):
    • Search for inherent methods defined on the given type (X, &X, or &mut X)
    • If none found, search for extension methods

I am certainly not saying that this procedure is ideal, but we definitely can't cavalierly change it, and it has some nice properties. For example, if you have an &self method in an impl defined on T, that is equivalent in resolution order to a fn(self) method defined in an impl for &T.

An example of a change I tried to make which did not work was to search for impls defined directly on the type X and then apply the autoref by looking at how the method was defined. This seems cleaner, but it interacted quite poorly with Clone, since with the new rules, if you invoke clone() on an &T type, it would invoke the (no-op) impl of Clone for &T instead of invoking the Clone impl for T (which is what you want, and what we do today). That is, today, if the receiver has type &T, we will search for methods whose receivers are &T first -- and this matches the impl of Clone for T, since clone() is an &self method (whereas the impl of Clone for &T would match when we search for &&T).

So basically I think we have to document these rules but I wouldn't want to change them without careful consideration.

The issue mainly becomes phrasing this for the reference and finding the proper location for it.