What are Rust's exact auto-dereferencing rules?

Question

I'm learning/experimenting with Rust, and in all the elegance that I find in this language, there is one peculiarity that baffles me and seems totally out of place.

Rust automatically dereferences pointers when making method calls. I made some tests to determine the exact behaviour:

struct X { val: i32 }
impl std::ops::Deref for X {
    type Target = i32;
    fn deref(&self) -> &i32 { &self.val }
}

trait M { fn m(self); }
impl M for i32   { fn m(self) { println!("i32::m()");  } }
impl M for X     { fn m(self) { println!("X::m()");    } }
impl M for &X    { fn m(self) { println!("&X::m()");   } }
impl M for &&X   { fn m(self) { println!("&&X::m()");  } }
impl M for &&&X  { fn m(self) { println!("&&&X::m()"); } }

trait RefM { fn refm(&self); }
impl RefM for i32  { fn refm(&self) { println!("i32::refm()");  } }
impl RefM for X    { fn refm(&self) { println!("X::refm()");    } }
impl RefM for &X   { fn refm(&self) { println!("&X::refm()");   } }
impl RefM for &&X  { fn refm(&self) { println!("&&X::refm()");  } }
impl RefM for &&&X { fn refm(&self) { println!("&&&X::refm()"); } }


struct Y { val: i32 }
impl std::ops::Deref for Y {
    type Target = i32;
    fn deref(&self) -> &i32 { &self.val }
}

struct Z { val: Y }
impl std::ops::Deref for Z {
    type Target = Y;
    fn deref(&self) -> &Y { &self.val }
}


#[derive(Clone, Copy)]
struct A;

impl M for    A { fn m(self) { println!("A::m()");    } }
impl M for &&&A { fn m(self) { println!("&&&A::m()"); } }

impl RefM for    A { fn refm(&self) { println!("A::refm()");    } }
impl RefM for &&&A { fn refm(&self) { println!("&&&A::refm()"); } }


fn main() {
    // I'll use @ to denote left side of the dot operator
    (*X{val:42}).m();        // i32::m()    , Self == @
    X{val:42}.m();           // X::m()      , Self == @
    (&X{val:42}).m();        // &X::m()     , Self == @
    (&&X{val:42}).m();       // &&X::m()    , Self == @
    (&&&X{val:42}).m();      // &&&X:m()    , Self == @
    (&&&&X{val:42}).m();     // &&&X::m()   , Self == *@
    (&&&&&X{val:42}).m();    // &&&X::m()   , Self == **@
    println!("-------------------------");

    (*X{val:42}).refm();     // i32::refm() , Self == @
    X{val:42}.refm();        // X::refm()   , Self == @
    (&X{val:42}).refm();     // X::refm()   , Self == *@
    (&&X{val:42}).refm();    // &X::refm()  , Self == *@
    (&&&X{val:42}).refm();   // &&X::refm() , Self == *@
    (&&&&X{val:42}).refm();  // &&&X::refm(), Self == *@
    (&&&&&X{val:42}).refm(); // &&&X::refm(), Self == **@
    println!("-------------------------");

    Y{val:42}.refm();        // i32::refm() , Self == *@
    Z{val:Y{val:42}}.refm(); // i32::refm() , Self == **@
    println!("-------------------------");

    A.m();                   // A::m()      , Self == @
    // without the Copy trait, (&A).m() would be a compilation error:
    // cannot move out of borrowed content
    (&A).m();                // A::m()      , Self == *@
    (&&A).m();               // &&&A::m()   , Self == &@
    (&&&A).m();              // &&&A::m()   , Self == @
    A.refm();                // A::refm()   , Self == @
    (&A).refm();             // A::refm()   , Self == *@
    (&&A).refm();            // A::refm()   , Self == **@
    (&&&A).refm();           // &&&A::refm(), Self == @
}

(Playground)

So, it seems that, more or less:

• The compiler will insert as many dereference operators as necessary to invoke a method.
• The compiler, when resolving methods declared using &self (call-by-reference):
  • First tries calling for a single dereference of self
  • Then tries calling for the exact type of self
  • Then, tries inserting as many dereference operators as necessary for a match
• Methods declared using self (call-by-value) for type T behave as if they were declared using &self (call-by-reference) for type &T and called on the reference to whatever is on the left side of the dot operator.
• The above rules are first tried with raw built-in dereferencing, and if there's no match, the overload with Deref trait is used.

What are the exact auto-dereferencing rules? Can anyone give any formal rationale for such a design decision?

Solution 1

Your pseudo-code is pretty much correct. For this example, suppose we had a method call foo.bar() where foo: T. I'm going to use the fully qualified syntax (FQS) to be unambiguous about what type the method is being called with, e.g. A::bar(foo) or A::bar(&***foo). I'm just going to write a pile of random capital letters, each one is just some arbitrary type/trait, except T is always the type of the original variable foo that the method is called on.

The core of the algorithm is:

• For each "dereference step" U (that is, set U = T and then U = *T, ...)
  1. if there's a method bar where the receiver type (the type of self in the method) matches U exactly , use it (a "by value method")
  2. otherwise, add one auto-ref (take & or &mut of the receiver), and, if some method's receiver matches &U, use it (an "autorefd method")

Notably, everything considers the "receiver type" of the method, not the Self type of the trait, i.e. impl ... for Foo { fn method(&self) {} } thinks about &Foo when matching the method, and fn method2(&mut self) would think about &mut Foo when matching.

It is an error if there's ever multiple trait methods valid in the inner steps (that is, there can be only be zero or one trait methods valid in each of 1. or 2., but there can be one valid for each: the one from 1 will be taken first), and inherent methods take precedence over trait ones. It's also an error if we get to the end of the loop without finding anything that matches. It is also an error to have recursive Deref implementations, which make the loop infinite (they'll hit the "recursion limit").

These rules seem to do-what-I-mean in most circumstances, although having the ability to write the unambiguous FQS form is very useful in some edge cases, and for sensible error messages for macro-generated code.

Only one auto-reference is added because

• if there was no bound, things get bad/slow, since every type can have an arbitrary number of references taken
• taking one reference &foo retains a strong connection to foo (it is the address of foo itself), but taking more starts to lose it: &&foo is the address of some temporary variable on the stack that stores &foo.

Examples

Suppose we have a call foo.refm(), if foo has type:

• X, then we start with U = X, refm has receiver type &..., so step 1 doesn't match, taking an auto-ref gives us &X, and this does match (with Self = X), so the call is RefM::refm(&foo)
• &X, starts with U = &X, which matches &self in the first step (with Self = X), and so the call is RefM::refm(foo)
• &&&&&X, this doesn't match either step (the trait isn't implemented for &&&&X or &&&&&X), so we dereference once to get U = &&&&X, which matches 1 (with Self = &&&X) and the call is RefM::refm(*foo)
• Z, doesn't match either step so it is dereferenced once, to get Y, which also doesn't match, so it's dereferenced again, to get X, which doesn't match 1, but does match after autorefing, so the call is RefM::refm(&**foo).
• &&A, the 1. doesn't match and neither does 2. since the trait is not implemented for &A (for 1) or &&A (for 2), so it is dereferenced to &A, which matches 1., with Self = A

Suppose we have foo.m(), and that A isn't Copy, if foo has type:

• A, then U = A matches self directly so the call is M::m(foo) with Self = A
• &A, then 1. doesn't match, and neither does 2. (neither &A nor &&A implement the trait), so it is dereferenced to A, which does match, but M::m(*foo) requires taking A by value and hence moving out of foo, hence the error.
• &&A, 1. doesn't match, but autorefing gives &&&A, which does match, so the call is M::m(&foo) with Self = &&&A.

(This answer is based on the code, and is reasonably close to the (slightly outdated) README. Niko Matsakis, the main author of this part of the compiler/language, also glanced over this answer.)

Solution 2

The Rust reference has a chapter about the method call expression. I copied the most important part below. Reminder: we are talking about an expression recv.m(), where recv is called "receiver expression" below.

The first step is to build a list of candidate receiver types. Obtain these by repeatedly dereferencing the receiver expression's type, adding each type encountered to the list, then finally attempting an unsized coercion at the end, and adding the result type if that is successful. Then, for each candidate T, add &T and &mut T to the list immediately after T.

For instance, if the receiver has type Box<[i32;2]>, then the candidate types will be Box<[i32;2]>, &Box<[i32;2]>, &mut Box<[i32;2]>, [i32; 2] (by dereferencing), &[i32; 2], &mut [i32; 2], [i32] (by unsized coercion), &[i32], and finally &mut [i32].

Then, for each candidate type T, search for a visible method with a receiver of that type in the following places:

1. T's inherent methods (methods implemented directly on T [¹]).
2. Any of the methods provided by a visible trait implemented by T. [...]

(Note about [¹]: I actually think this phrasing is wrong. I've opened an issue. Let's just ignore that sentence in the parenthesis.)

---

Let's go through a few examples from your code in detail! For your examples, we can ignore the part about "unsized coercion" and "inherent methods".

(*X{val:42}).m(): the receiver expression's type is i32. We perform these steps:

• Creating list of candidate receiver types:
  • i32 cannot be dereferenced, so we are already done with step 1. List: [i32]
  • Next, we add &i32 and &mut i32. List: [i32, &i32, &mut i32]
• Searching for methods for each candidate receiver type:
  • We find <i32 as M>::m which has the receiver type i32. So we are already done.

So far so easy. Now let's pick a more difficult example: (&&A).m(). The receiver expression's type is &&A. We perform these steps:

• Creating list of candidate receiver types:
  • &&A can be dereferenced to &A, so we add that to the list. &A can be dereferenced again, so we also add A to the list. A cannot be dereferenced, so we stop. List: [&&A, &A, A]
  • Next, for each type T in the list, we add &T and &mut T immediately after T. List: [&&A, &&&A, &mut &&A, &A, &&A, &mut &A, A, &A, &mut A]
• Searching for methods for each candidate receiver type:
  • There is no method with receiver type &&A, so we go to the next type in the list.
  • We find the method <&&&A as M>::m which indeed has the receiver type &&&A. So we are done.

---

Here are the candidate receiver lists for all of your examples. The type that is enclosed in ⟪x⟫ is the one that "won", i.e. the first type for which a fitting method could be found. Also remember that the first type in the list is always the receiver expression's type. Lastly, I formatted the list in lines of three, but that's just formatting: this list is a flat list.

• (*X{val:42}).m() → <i32 as M>::m

  [⟪i32⟫, &i32, &mut i32]
  

• X{val:42}.m() → <X as M>::m

  [⟪X⟫, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&X{val:42}).m() → <&X as M>::m

  [⟪&X⟫, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&&X{val:42}).m() → <&&X as M>::m

  [⟪&&X⟫, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&&&X{val:42}).m() → <&&&X as M>::m

  [⟪&&&X⟫, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&&&&X{val:42}).m() → <&&&X as M>::m

  [&&&&X, &&&&&X, &mut &&&&X, 
   ⟪&&&X⟫, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&&&&&X{val:42}).m() → <&&&X as M>::m

  [&&&&&X, &&&&&&X, &mut &&&&&X, 
   &&&&X, &&&&&X, &mut &&&&X, 
   ⟪&&&X⟫, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (*X{val:42}).refm() → <i32 as RefM>::refm

  [i32, ⟪&i32⟫, &mut i32]
  

• X{val:42}.refm() → <X as RefM>::refm

  [X, ⟪&X⟫, &mut X, 
   i32, &i32, &mut i32]
  

• (&X{val:42}).refm() → <X as RefM>::refm

  [⟪&X⟫, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&&X{val:42}).refm() → <&X as RefM>::refm

  [⟪&&X⟫, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&&&X{val:42}).refm() → <&&X as RefM>::refm

  [⟪&&&X⟫, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&&&&X{val:42}).refm() → <&&&X as RefM>::refm

  [⟪&&&&X⟫, &&&&&X, &mut &&&&X, 
   &&&X, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• (&&&&&X{val:42}).refm() → <&&&X as RefM>::refm

  [&&&&&X, &&&&&&X, &mut &&&&&X, 
   ⟪&&&&X⟫, &&&&&X, &mut &&&&X, 
   &&&X, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]
  

• Y{val:42}.refm() → <i32 as RefM>::refm

  [Y, &Y, &mut Y,
   i32, ⟪&i32⟫, &mut i32]
  

• Z{val:Y{val:42}}.refm() → <i32 as RefM>::refm

  [Z, &Z, &mut Z,
   Y, &Y, &mut Y,
   i32, ⟪&i32⟫, &mut i32]
  

• A.m() → <A as M>::m

  [⟪A⟫, &A, &mut A]
  

• (&A).m() → <A as M>::m

  [&A, &&A, &mut &A,
   ⟪A⟫, &A, &mut A]
  

• (&&A).m() → <&&&A as M>::m

  [&&A, ⟪&&&A⟫, &mut &&A,
   &A, &&A, &mut &A,
   A, &A, &mut A]
  

• (&&&A).m() → <&&&A as M>::m

  [⟪&&&A⟫, &&&&A, &mut &&&A,
   &&A, &&&A, &mut &&A,
   &A, &&A, &mut &A,
   A, &A, &mut A]
  

• A.refm() → <A as RefM>::refm

  [A, ⟪&A⟫, &mut A]
  

• (&A).refm() → <A as RefM>::refm

  [⟪&A⟫, &&A, &mut &A,
   A, &A, &mut A]
  

• (&&A).refm() → <A as RefM>::refm

  [&&A, &&&A, &mut &&A,
   ⟪&A⟫, &&A, &mut &A,
   A, &A, &mut A]
  

• (&&&A).refm() → <&&&A as RefM>::refm

  [&&&A, ⟪&&&&A⟫, &mut &&&A,
   &&A, &&&A, &mut &&A,
   &A, &&A, &mut &A,
   A, &A, &mut A]
  

Comments

[Shepmaster]

I've cross-posted this to the Rust subreddit in the hopes of getting some good answers!

[user2665887]

For extra fun try to repeat the experiment in generics and compare the results.

[Lii]

This answer seems exhaustive and detailed but I think it lacks a short and accessible summery of the rules. One such summery is given in this comment by Shepmaster: "It [the deref algorithm] will deref as many times as possible (&&String -> &String -> String -> str) and then reference at max once (str -> &str)".

[Lii]

(I don't know how accurate and complete that explanation is myself.)

[Lii]

In what cases do auto dereferencing occur? Is it used only for the receiver expression for method call? For field accesses also? Assignment right-hand sides? Left-hand sides? Function parameters? Return value expressions?

[SamB]

Note: Currently, the nomicon has a TODO note to steal information from this answer and write it up in static.rust-lang.org/doc/master/nomicon/dot-operator.html

[haslersn]

Is coercion (A) tried before this or (B) tried after this or (C) tried in every step of this algorithm or (D) something else?

[Xiao-Feng Li]

@haslersn Auto deref is part of coercion, which includes auto-deref, auto-unsize, auto-ref, etc. See the implementation code here: github.com/rust-lang/rust/blob/…. Auto-unsize is applied after one or more auto-derefs, and auto-ref is after other adjustments. So per you specific question, (C) tried in every step is the answer.

[Joseph Garvin]

Notably this coercion does not appear to happen for comparison operators like >, inconsistent with named function calls.