Generics in Rust: murky waters of implementing foreign traits on foreign types
Tags: rust, generics, numeric, beginners
Published: 2024-06-04 03:11:12

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](https://doc.rust-lang.org/book/ch10-02-traits.html) 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](https://doc.rust-lang.org/book/ch10-02-traits.html)? 

## 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](https://doc.rust-lang.org/book/ch10-02-traits.html).

Looking into the [`nalgebra` source code](https://github.com/dimforge/nalgebra/blob/dev/src/base/ops.rs), 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](https://rust-lang.github.io/rfcs/) (RFC stands for Request For Comments). 
[RFC 2451](https://rust-lang.github.io/rfcs/2451-re-rebalancing-coherence.html) 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](https://rust-lang.github.io/rfcs/2451-re-rebalancing-coherence.html) 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<T> ForeignTrait<LocalType<T>, T> for ForeignType is valid, but impl<T> ForeignTrait<T, LocalType<T>> 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](https://dev.to/iprosk/generics-in-rust-visualizing-bezier-curves-in-a-jupyter-notebook-part-3-565n)

```
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](https://doc.rust-lang.org/error_codes/E0210.html).

## Summary

We can implement foreign traits on foreign types in Rust with caveats. However, this behavior is not in [The Rust Book](https://doc.rust-lang.org/book/ch10-02-traits.html) yet, and is communicated mostly through [E0210](https://doc.rust-lang.org/error_codes/E0210.html) and [RFCs](https://rust-lang.github.io/rfcs/2451-re-rebalancing-coherence.html). Pure generics do not work, which, according to [RFC 2451](https://rust-lang.github.io/rfcs/2451-re-rebalancing-coherence.html), looks like a technical difficulty that may be revised in the future.