How does Rust go “from” here “into” there

I have heard a lot of (mostly) good things about the Rust programming language. Recently, I decided to give it a try and learn Rust basics myself.

When learning something, I am always curious how things work inside. It is no different this time; I keep stumbling upon the question: But how does it work? I decided that this time I will start blogging about my findings.

One of features that caught my attention is dependency between From and Into traits. The documentation says:

One should always prefer implementing From over Into because implementing From automatically provides one with an implementation of Into thanks to the blanket implementation in the standard library.

It means that when we will implement From trait the into() method invocation will magically work:

struct A(i32);

struct B(i32);

impl From<A> for B {
    fn from(value: A) -> B {
        B(value.0)
    }
}

fn main() {
    let a = A(1);
    let b: B = a.into();
    assert_eq!(1, b.0)
}

Where does the into method come from? The answer is in source code of Rust std library (removed macros and comments for readability):

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

It is blanket implementation indeed - converts one generic type into another generic type. But how does compiler know what trait to use when it sees into call? My struct does not implement any Traits nor is it bound to them in any way.

The answer lies within compiler's trait resolution algorithm. When the compiler looks for what method implementation to use, it first collects candidates (candidate assembly). The compiler searches for impls/where-clauses/etc that might possibly be used to satisfy the obligation (the term "obligation" is a trait reference that compiler is trying to resolve). As part of this process, it is checking if instantiation of a generic trait will satisfy obligation (see collect_trait_impls function in src/librustdoc/passes/collect_trait_impls.rs). Once compiler collects all candidates it then attempts to resolve ambiguities. If it can successfully resolve ambiguities, it verifies the candidate can be used with specified types. And voila! That's how from become into.

Sources:

1. The Rust book
2. Rust std library documentation
3. Rust dev guide
4. rustc source code