Understanding a Trait Selection Bug
2024-Apr-21
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 (refer to 1) of the value on the RHS of the binary expression based on the available methods1.
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 candidates2. 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.
1 Edit (May 14, 2024)
My understanding is incorrect. The real reason, as pointed by SkiFire13 on Reddit:
Addition always takes ownership of the rhs. It may be a bit confusing because in case the rhs is a reference this means taking ownership of the reference, not the referenced value (because references are values as well!)
The reason the inference variable is used is due to coercions. If you’re trying to sum a
String
with a&String
there’s no impl that applies, so it would normally fail. However&String
coerces to&str
, for which there is an applicable impl. Using an inference variable allows to resolve the type of the rhs to&str
and then check that&String
coerces to&str
, instead of immediately erroring because there’s noimpl Add<&String>
forString
.