Why is an explicit dereference required in (*x).into(), but not in x.my_into()?

Question

After reading method-call expressions, dereference operator, method lookup, and auto-dereferencing, I thought I had a pretty good understanding of the subject; but then I encountered a situation in which I expected auto-dereferencing to happen, when in fact it didn't happen.

The example is as follows.

#[derive(Clone, Copy, Debug)]
struct Foo();

impl Into<&'static str> for Foo {
    fn into(self) -> &'static str {
        "<Foo as Into>::into"
    }
}

fn vec_into<F: Copy + Into<T>, T>(slice: &[F]) -> Vec<T> {
    slice.iter().map(|x| (*x).into()).collect()
}

fn main() {
    let array = [Foo(), Foo(), Foo()];
    let vec = vec_into::<_, &'static str>(&array);
    println!("{:?}", vec);
}

The code above works, but I thought that the explicit dereferencing (*x).into() in the function vec_into wasn't needed. My reasoning is that, since x: &Foo, then x.into() would try to find methods accepting type &Foo, &&Foo, &mut &Foo, Foo, &Foo, &mut Foo.

This is because there is the chain of dereferencing &Foo → Foo, and for each U in this chain we insert also &U and &mut U.

My intuition is confirmed by the fact that the following code also works, without any explicit dereference.

#[derive(Clone, Copy, Debug)]
struct Foo();

trait MyInto<T> {
    fn my_into(self) -> T;
}

impl MyInto<&'static str> for Foo {
    fn my_into(self) -> &'static str {
        "<Foo as MyInto>::my_into"
    }
}

fn vec_my_into<F: Copy + MyInto<T>, T>(slice: &[F]) -> Vec<T> {
    slice.iter().map(|x| x.my_into()).collect()
}

fn main() {
    let array = [Foo(), Foo(), Foo()];
    let my_vec = vec_my_into(&array);
    println!("{:?}", my_vec);
}

Here x: &Foo is implicitly dereferenced in order to call the method <Foo as MyInto<&'static str>>::my_into.

A smaller example

Given the above definitions of Foo and MyInto, the code

let result: &str = (&Foo()).my_into()

works, but

let result: &str = (&Foo()).into()

fails to compile with the error

error[E0277]: the trait bound `&str: std::convert::From<&Foo>` is not satisfied
  --> src/bin/into.rs:34:33
   |
34 |     let result: &str = (&Foo()).into();
   |                                 ^^^^ the trait `std::convert::From<&Foo>` is not implemented for `&str`
   |
   = note: required because of the requirements on the impl of `std::convert::Into<&str>` for `&Foo`

Answer 1

Rust performs method lookup exatly as you describe, and it immediately finds a candidate for .into() – the blanket implementation

impl<T, U> Into<U> for T
where
    U: From<T>,
{
    fn into(self) -> U {
        U::from(self)
    }
}

This implementation fulfils all the requirements for candidate methods – it is visible, in scope and defined for type &Foo, since it is defined for any type T. Once the compiler has picked this candidate, it notices that the trait bounds on U are not satisfied, and issues the error you see.

The situation for MyInto is completely different, because you don't provide a blanket implementation based on From. If you do, you will get the same error.

It could be argued that the compiler should skip the blanket implementation if the trait bounds are not satisfied, and move on with the list of candidate types until it finds a better fit. The language specification is actually not completely clear on that point, but from the error we see it is clear what the compiler actually does.

Answer 2

Interestingly enough, after inspecting the compiler output, it would appear that the Into implementation actually just calls a method of the trait From. What it's looking for is std::collections::From<&Foo> for &str. Therefore, if we implement that trait, the compiler will indeed find our function, and execute it.

Using the following declarations:

#[derive(Clone, Copy, Debug)]
struct Foo();

impl std::convert::From<&Foo> for &str {
    fn from(f: &Foo) -> &'static str {
        "A &str"// This could be replaced with an actual implementation
    }
}

Your code works as you wanted:

let result: &str = (&Foo()).into();// No compiler errors.

The original code you wanted does work, and it isn't actually hard to implement.