Understanding a Trait Selection Bug

Recently, I ran into rust-lang/issues/#24066 and spent some time analysing the underlying trait selection mechanism. In this blog post, I’ll briefly explain why this bug prevents the following snippet from compiling.

fn add<T>() where
    u32: std::ops::Add<T, Output = T>
{
    let _ = 1_u32 + 1_u32; // error[E0308]: mismatched types
}

Inside the compiler, the rustc_hir_typeck crate handles lookup of methods for binary operations. When it encounters the expression 1_u32 + 1_u32, it does something peculiar: instead of directly looking up for a method that adds an u32 to another u32, it searches for a method that can add an u32 to a type inference variable $0. This allows the compiler to either borrow or take ownership of the value on the RHS of the binary expression based on the available methods¹.

The request “find a method to add an u32 with the type inference variable $0” is handled by the rustc_trait_selection crate, which selects an appropriate method from a collection of candidates. Here, traits specified in the where clause are given a higher precedence over other candidates². I believe this heuristic is followed as the programmer is expected to specify only the necessary traits in the where clause.

Thus, for the expression 1_u32 + 1_u32, a method which adds an u32 and a type variable T is chosen because it’s mentioned in the where clause and T unifies with the type inference variable $0. This attempts to unify the u32 on the RHS with type variable T, resulting in a type mismatch error.

Guess, this is an other instance where a compiler leans towards soundness over completeness.