How does Rust choose which trait implementation to use when multiple apply for a given type?

help
1

I have, for example, this trait:

pub trait DynamicSize {
    fn size(&self) -> usize;
}

It has an implementation for Vec<T>, which simply sums up the dynamic sizes:

impl<T: DynamicSize> DynamicSize for Vec<T> {
    fn size(&self) -> usize {
        self.iter().map(DynamicSize::size).sum()
    }
}

Now, I create some struct implementing From:

struct Test<T>(Vec<T>);

impl<T: DynamicSize> From<T> for Test<T> {
    fn from(data: T) -> Self {
        Self(vec![data])
    }
}

But, crucially, I also have an implementation for specifically Vec:

impl<T: DynamicSize> From<Vec<T>> for Test<T> {
    fn from(data: Vec<T>) -> Self {
        Self(data)
    }
}

(disregard the fact the trait is not actually used in the functions, I simplified the code)

Given a vec![1, 2, 3], it can either

  • Interpret Vec as implementing DynamicSize and call the first implementation (resulting with Test([[1, 2, 3]]))
  • Interpret Vec as matching the second implementation (resulting with Test([1, 2, 3]))

The question is how does the compiler know which trait implementation to choose?

2

Because the two trait implementations are disjoint, which one is chosen depends on type inference. Type inference in Rust isn't monodirectional, and can flow "backwards" where constraints on the returned value are used in trait selection.

The first implementation provides <Test<T> as From<T>>::from(T) -> Test<T>, and the latter provides <Test<T> as From<Vec<T>>>::from(Vec<T>) -> Test<T>. When you write Test::<T>::from, it could be either function, and which is used depends on whether you provide T or Vec<T> as an argument. When you write Test::<_>::from, whether you get Test<T> or Test<Vec<T>> depends on how you use the result value, and if you don't constrain the value to one or the other, you will get an error.

4 Likes
3

I always suggest people to change the mental model of the type checker from a calculator (i.e. given some input, calculate some output) to an equation solver (i.e. given some constraints with unknown types, solve the equation, only succeeds if the solution is unique, fails if no solution or multiple solution)

take OP's problem as an example, suppose we have already defined impl DynamicSize for String {...}, given this code snippet:

let v = vec!["hello".to_string(), "world".to_string()];
let test = Test::<String>::from(v);

first statement is trivially solvable and v has the type Vec<String; in the second statement, this function <Test<String> as From>::from() must have the type Vec<String> -> Test<String>. and we can see this type can be satisfied by this impl block:

in this impl block, the function from() has the type Vec<T> -> Test<T>, substitue String for T we get what we wanted.

on the other hand, the other impl block:

the from() function has the type T -> Test<T>, which is unsolvable given our target equation.

the following code snippet is left as an excercise. playground link here

let v = vec!["hello".to_string(), "world".to_string()];

// compile error: need annotation;
// multiple `impl`s satisfying `Test<_>: From<Vec<String>>` found
let test: Test<_> = v.into();

// ok, choose `impl From<Vec<T>> for Test<T>`
let test: Test<String> = v.into();

// ok, choose `impl From<T> for Test<T>`
let test: Test<Vec<String>> = v.into();

EDIT:

the last one can also omit the String:

let test: Test<Vec<_>> = v.into();
5 Likes