Generics in Rust: murky waters of implementing foreign traits on foreign types

This post is about what bothered me for a while in generic Rust before I could clarify what's going on (sort of), namely, implementing foreign trait on foreign types, especially, in the context of Rust's way of "operator overloading".

We can't do it, or can we?

First, there is no mystery, right? The Rust Book is pretty clear on this matter.

But we can’t implement external traits on external types. For example, we can’t implement the Display trait on Vec<T> within our aggregator crate, because Display and Vec<T> are both defined in the standard library and aren’t local to our aggregator crate. This restriction is part of a property called coherence, and more specifically the orphan rule, so named because the parent type is not present.

So if we try to write something like this in the Playground:

impl From<usize> for f64 {
    // -- snippet --
}

the compiler immediately reminds us about this orphan rule

error[E0117]: only traits defined in the current crate can be implemented for primitive types

Nice and clear! Now, if we replace these lines with generics, the compiler error is different (and in a "slight" logical contradiction with the first error message), which hint that something is not so simple as advertised

impl<T, U> From<T> for U {
    // -- snippet --
}

error[E0210]: type parameter `U` must be used as the type parameter for some local type (e.g., `MyStruct<U>`)

When we look into a detailed explanation of error[E0210], we find our intuition was right:

When implementing a foreign trait for a foreign type, the trait must have one or more type parameters. A type local to your crate must appear before any use of any type parameters.

So we can do it in Rust, can't we? But what about The Book?

How can nalgebra do it?

Looking into reputable library crates such nalgebra also raises questions. Let's try, for example:

use nalgebra::Vector3;

fn main() {
   let v = Vector3::new(1.0, 2.0, 3.0);
   println!("{:?}", v * 3.0);
   println!("{:?}", 3.0 * v);
}

It compiles and produces what's expected, and everything look alight. But how is that possible?

The first expression is, of course, pretty standard: v * 3.0 requires implementing std::ops::Mul<f64> trait with Output = Vector3 on Vector3. However, 3.0 * v requires std::ops::Mul<Vector3> on the build-in type f64, which is nothing but implementing a foreign trait on a foreign type in direct violation of the The Book.

Looking into the nalgebra source code, we find that the first expression is implemented using generics

macro_rules! componentwise_scalarop_impl(
    ($Trait: ident, $method: ident, $bound: ident;
     $TraitAssign: ident, $method_assign: ident) => {
        impl<T, R: Dim, C: Dim, S> $Trait<T> for Matrix<T, R, C, S>
            where T: Scalar + $bound,
                  S: Storage<T, R, C>,
                  DefaultAllocator: Allocator<T, R, C> {
                //
                // -- snippet --
                //
            }
        }  
    }
);

The macro declaration is not so important in this case. More important is that right-multiplication by a scalar is generic, and all metavariables in the macro pattern simply bind to identifies.

Left multiplication by a scalar is completely different. It is not generic, macro pattern matcher binds to types with repletion patterns

macro_rules! left_scalar_mul_impl(
    ($($T: ty),* $(,)*) => {$(
        impl<R: Dim, C: Dim, S: Storage<$T, R, C>> Mul<Matrix<$T, R, C, S>> for $T
            // -- snippet --
    )*}
);

left_scalar_mul_impl!(u8, u16, u32, u64, usize, i8, i16, i32, i64, isize, f32, f64);

The last line explicitly instantiates implementations for built-in types.

So why is it different?

We can do what we can't

Finally, I found the answer in the RFC Book (RFC stands for Request For Comments).
RFC 2451 from 2018-05-30 that starts with the following lines:

For better or worse, we allow implementing foreign traits for foreign types.

That's it! That's the answer.

Then it becomes more interesting:

This change isn’t something that would end up in a guide, and is mostly communicated through error messages. The most common one seen is E0210. The text of that error will be changed to approximate the following:

Then follows the details of E0210 that I have already mentioned above. Together with RFC 2451 it clarifies a little bit when we can implement foreign traits for foreign types and when we cannon. One more details from these documents:

When implementing a foreign trait for a foreign type, the trait must have one or more type parameters. A type local to your crate must appear before any use of any type parameters. This means that impl ForeignTrait, T> for ForeignType is valid, but impl ForeignTrait> for ForeignType is not.

This works in the following example for left-scalar multiplication from my little library of generic Bezier curves that I used for illustration in previous posts

impl<T, const N: usize> Mul<Bernstein<T, f64, {N}>> for f64 where
            T: Copy + Mul<f64, Output = T>,
            [(); N]:
{
    // -- snippet --
}

In this example a foreign trait std::ops::Mul<T> specialized on a local generic type Bernstein<T, U, N> is implemented for a foreign type f64 similar to example above with left_scalar_mul_impl from nalgebra crate. Purely generic variant of this implementation

impl<T, U, const N: usize> Mul<Bernstein<T, U, {N}>> for U where
            T: Copy + Mul<U, Output = T>,
            U: Copy,
            [(); N]:
{
    type Output = Bernstein<T, U, {N}>;

    fn mul(self, rhs: Bernstein<T, U, {N}>) -> Self::Output {
        // -- snippet --
    }
}

gives already familiar compiler error E0210.

Summary

We can implement foreign traits on foreign types in Rust with caveats. However, this behavior is not in The Rust Book yet, and is communicated mostly through E0210 and RFCs. Pure generics do not work, which, according to RFC 2451, looks like a technical difficulty that may be revised in the future.