How to implement generics over all types capable of arithmetic operations?

Question

The Number wrapper presents subtraction on its contained type if possible. The Difference struct saves two numbers and their difference (playground):

use std::ops::Sub;

#[derive(Debug)]
struct Number<T>(T); // Doesn't have the Copy marker
// Implements subtraction whenever the contained type does
// Only the case with references implemented for brevity
impl<'a, 'b, T> Sub<&'b Number<T>> for &'a Number<T>
where
    &'a T: Sub<&'b T, Output = T> 
{
    type Output = Number<T>;
    
    fn sub(self, rhs: &'b Number<T>) -> Number<T> {
        Number(&self.0 - &rhs.0)
    }
}

#[derive(Debug)]
struct Difference<T> {
    a: Number<T>,
    b: Number<T>,
    diff: Number<T>,
}
impl<'a, 'b, T: 'b + 'a> Difference<T>
where
    // "Any type for which `Number` implements subtraction"
    &'a Number<T>: Sub<&'b Number<T>, Output = Number<T>>,
{
    fn new(a: Number<T>, b: Number<T>) -> Self {
        let diff = &b - &a;
        Difference { a, b, diff }
    }
}

fn main() {
    println!("{:?}", Difference::new(Number(3), Number(5)));
}

This code doesn't compile for several reasons. Firstly, there's recursion while evaluating the Sub trait bound:

error[E0275]: overflow evaluating the requirement `&BTreeSet<_>: Sub<&BTreeSet<_>>`
  --> src/main.rs:36:22
   |
36 |     println!("{:?}", Difference::new(Number(3), Number(5)));
   |                      ^^^^^^^^^^^^^^^
   |
   = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`playground`)
note: required because of the requirements on the impl of `Sub<&Number<BTreeSet<_>>>` for `&Number<BTreeSet<_>>`
  --> src/main.rs:7:17
   |
7  | impl<'a, 'b, T> Sub<&'b Number<T>> for &'a Number<T>
   |                 ^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^
   = note: 127 redundant requirements hidden
   = note: required because of the requirements on the impl of `Sub` for `&Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<Number<BTreeSet<_>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`

I don't understand that, because as I see it, the compiler should:

• see that Difference::new() is invoked
• extract the T type from its parameters ({integer} in this case)
• check if there is any valid implementation for the bounds of this type:

  `&'a Number<{integer}>: Sub<&'b Number<{integer}>, Output = Number<{integer}>>`
  

• see that impl<'a, 'b, T> Sub<&'b Number<T>> for &'a Number<T> with type Output = Number<T>; is the correct implementation if the bounds on T are satisfied
• see that every {integer} satisfies the &'a T: Sub<&'b T, Output = T> bound

It seems to me, that the compiler instead tries to recursively substitute Number<T> as T, but I don't understand why.

Even after this problem is resolved (or hidden by commenting the println! invocation) a new error is generated:

error[E0597]: `b` does not live long enough
  --> src/main.rs:30:20
   |
24 | impl<'a, 'b, T: 'b + 'a> Difference<T>
   |      -- lifetime `'a` defined here
...
30 |         let diff = &b - &a;
   |                    ^^
   |                    |
   |                    borrowed value does not live long enough
   |                    requires that `b` is borrowed for `'a`
31 |         Difference { a, b, diff }
32 |     }
   |     - `b` dropped here while still borrowed

error[E0597]: `a` does not live long enough
  --> src/main.rs:30:25
   |
24 | impl<'a, 'b, T: 'b + 'a> Difference<T>
   |          -- lifetime `'b` defined here
...
30 |         let diff = &b - &a;
   |                         ^^
   |                         |
   |                         borrowed value does not live long enough
   |                         requires that `a` is borrowed for `'b`
31 |         Difference { a, b, diff }
32 |     }
   |     - `a` dropped here while still borrowed

error[E0505]: cannot move out of `a` because it is borrowed
  --> src/main.rs:31:22
   |
24 | impl<'a, 'b, T: 'b + 'a> Difference<T>
   |          -- lifetime `'b` defined here
...
30 |         let diff = &b - &a;
   |                         --
   |                         |
   |                         borrow of `a` occurs here
   |                         requires that `a` is borrowed for `'b`
31 |         Difference { a, b, diff }
   |                      ^ move out of `a` occurs here

error[E0505]: cannot move out of `b` because it is borrowed
  --> src/main.rs:31:25
   |
24 | impl<'a, 'b, T: 'b + 'a> Difference<T>
   |      -- lifetime `'a` defined here
...
30 |         let diff = &b - &a;
   |                    --
   |                    |
   |                    borrow of `b` occurs here
   |                    requires that `b` is borrowed for `'a`
31 |         Difference { a, b, diff }
   |                         ^ move out of `b` occurs here

The idea is that I borrow a and b for the subtraction and then give them back, so that they can be moved into the returned struct. However, in the bound &'a Number<T>: Sub<&'b Number<T>, Output = Number<T>> I promise that they will be borrowed for the entire duration of the function. I don't want to promise that, but I need some lifetime to be even able to specify the bound, and I don't know how to specify a shorter lifetime.

How would I go about solving these problems?

Answer 1

First of all lets fix that annoying recursive type by specifying the exact type to use

println!("{:?}", Difference::<i32>::new(Number(3), Number(5)));

There type seems to be ambiguous!! (because {integer} isn't a concrete type) To be honest I don't know exactly why it goes though that recursion but it does.

Next the trait bound for ambiguous with how trait bound were you were specifying that &'a Number<T> - &'b Number<T> = &'a+b Number<T> witch isn't the case since you implemented that &'a Number<T> - &'b Number<T> = Number<T>. To fix this I used HRTBs. (To be honest you could probably do it without them but it gets annoying when there are a lot of lifetimes)

for<'a, 'b> &'a Number<T>: Sub<&'b Number<T>, Output = Number<T>>,

Full code

use std::ops::Sub;

#[derive(Debug)]
struct Number<T>(T);

impl<'a, 'b, T> Sub<&'b Number<T>> for &'a Number<T>
where
    &'a T: Sub<&'b T, Output = T> 
{
    type Output = Number<T>;
    
    fn sub(self, rhs: &'b Number<T>) -> Number<T> {
        Number(&self.0 - &rhs.0)
    }
}

#[derive(Debug)]
struct Difference<T> {
    a: Number<T>,
    b: Number<T>,
    diff: Number<T>,
}
impl<T> Difference<T>
where
    // Used [HRTBs](https://doc.rust-lang.org/nomicon/hrtb.html) to define that &a - &b = c works used a single lifetime
    for<'a, 'b> &'a Number<T>: Sub<&'b Number<T>, Output = Number<T>>,
{
    fn new(a: Number<T>, b: Number<T>) -> Self {
        let diff = &b - &a;
        Difference { a, b, diff }
    }
}

fn main() {
    // Defined the type because there are some recursive issues
    // Somehow the type is ambiguous!!! But the error doesn't explain anything
    // It is trying to figure out the type but when exploring all the types it throws a to many recursions error
    println!("{:?}", Difference::<i32>::new(Number(3), Number(5)));
}

EDIT: I just found out that this is really similar to std::num::Wrapping