Trouble implementing operators for structs that template typenums. Aren't `Add<SomeStruct<P1>>` and `Add<SomeStruct<P2>>` different traits?

The Code:

use typenum::*;
use std::ops::Add;

struct A<T> {}

impl<L: Unsigned> Add<A<L>> for A<L> {
    type Output = i32;
    fn add(self, _rhs: A<L>) -> Self::Output {
        5
    }
}

impl<L: Unsigned> Add<A<Add1<L>>> for A<L> {
    type Output = i32;
    fn add(self, _rhs: A<Add1<L>>) -> Self::Output {
        500
    }
}

fn main() {
    let a1 = A::<P1>{};
    let a2 = A::<P2>{};
    assert_eq!(a1 + a1, 5);
    assert_eq!(a1 + a2, 500);
    assert_eq!(a2 + a2, 5);
}

The Error:

   Compiling playground v0.0.1 (/playground)
error[E0119]: conflicting implementations of trait `Add` for type `A<_>`
  --> src/main.rs:13:1
   |
6  | impl<L: Unsigned> Add<A<L>> for A<L> {
   | ------------------------------------ first implementation here
...
13 | impl<L: Unsigned> Add<A<Add1<L>>> for A<L> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `A<_>`

For more information about this error, try `rustc --explain E0119`.
error: could not compile `playground` (bin "playground") due to 1 previous error

(Playground)

Aren’t Add<SomeStruct<P1>> and Add<SomeStruct<P2>> different traits?

Sure, they are, but your case of P1 = L and P2 = Add1<L> doesn’t seem to rule out overlap in a way that can convince the compiler.

While indeed the (sealed) implementors of Unsigned from typenum never have L and Add1<L> be the same type, that’s “just a convention” that typenum follows. In principle, the compiler

  • cannot tell this property anyways, and
  • would need to account for future-compatibility, so upstream could add new implementors of Unsigned and Add<B1> so that Add1<L> is the same as L for those.

I suppose this is a downside of working with a binary representation of the type-level numbers. If it was a unary system, where each successor was just Successor<Previous> and Successor is a simple struct Successor<T>(T) type constructor, then the compiler could know that Successor<L> and L are never the same.

So, we can work around the limitation though, by using a few more trait implementations…

use typenum::*;
use std::ops::Add;

#[derive(Copy, Clone)]
struct A<T>(T);

impl<L: Unsigned> Add<A<L>> for A<L> {
    type Output = i32;
    fn add(self, _rhs: A<L>) -> Self::Output {
        5
    }
}

// L is the smaller of the two numbers
fn add_successor<L: Unsigned>() -> i32 {
    500
}

impl Add<A<U1>> for A<U0> {
    type Output = i32;
    fn add(self, _rhs: A<U1>) -> Self::Output {
        add_successor::<U0>()
    }
}
impl<L: Unsigned> Add<A<UInt<L, B1>>> for A<UInt<L, B0>> {
    type Output = i32;
    fn add(self, _rhs: A<UInt<L, B1>>) -> Self::Output {
        add_successor::<UInt<L, B0>>()
    }
}
impl<L: Unsigned + Add<B1>> Add<A<UInt<Add1<L>, B0>>> for A<UInt<L, B1>> {
    type Output = i32;
    fn add(self, _rhs: A<UInt<Add1<L>, B0>>) -> Self::Output {
        add_successor::<UInt<L, B1>>()
    }
}

fn main() {
    let a1 = A(U1::new());
    let a2 = A(U2::new());
    assert_eq!(a1 + a1, 5);
    assert_eq!(a1 + a2, 500);
    assert_eq!(a2 + a2, 5);
}

Rust Playground

Thanks! Big help. Feels like most of this should be hidden behind a macro from typenum tbh.

I came up with a second alternative approach. While the first above relied on more fine-grained manual impls (and the fact that the last bit is always different for successors), this one just calculates R - L, and then uses the difference to avoid overlap. This still needs a 2-step process, as Rust’s overlap protection isn’t all that smart, so we use a helper trait and pass it the calculated difference as parameter:

use typenum::*;
use std::ops::Add;
use core::ops::Sub;

#[derive(Copy, Clone)]
struct A<T>(T);

impl<L: Unsigned, R: Unsigned, D> Add<A<R>> for A<L>
where
    R: Sub<L, Output = D>,
    L: AddAWithDiff<D>
{
    type Output = i32;
    fn add(self, _rhs: A<R>) -> Self::Output {
        L::add_impl()
    }
}

trait AddAWithDiff<D> {
    fn add_impl() -> i32;
}

impl<L> AddAWithDiff<U0> for L {
    fn add_impl() -> i32 {
        5
    }
}

impl<L> AddAWithDiff<U1> for L {
    fn add_impl() -> i32 {
        500
    }
}

fn main() {
    let a1 = A(U1::new());
    let a2 = A(U2::new());
    assert_eq!(a1 + a1, 5);
    assert_eq!(a1 + a2, 500);
    assert_eq!(a2 + a2, 5);
}