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

user_11952411 0
Viewed 207

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?

rust generics
1 Answers

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

user_166338430
Related