Why is it necessary to add redundant trait bounds even though my trait uses those same traits as bounds?

Question

I have been trying to code a trait which requires a type to implement Add (and further down the line other operations for vector spaces) with itself as well as among its references. The following is a small example, illustrating the problem I ran into:

use std::ops::Add;

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

impl<'a, 'b, T: Copy + Add> Add<&'a MyVec<T>> for &'b MyVec<T> {
    type Output = MyVec<T::Output>;
    fn add(self, other: &'a MyVec<T>) -> Self::Output {
        /* ... */
    }
}
impl<'a, T: Copy + Add> Add<MyVec<T>> for &'a MyVec<T> {
    /* ... */
}
impl<'a, T: Copy + Add> Add<&'a MyVec<T>> for MyVec<T> {
    /* ... */
}
impl<T: Copy + Add> Add<MyVec<T>> for MyVec<T> {
    /* ... */
}

trait Addable: Add<Self, Output = Self>
where
    Self: Sized,
    for<'a> &'a Self: Add<Self, Output = Self>,
    for<'b> Self: Add<&'b Self, Output = Self>,
    for<'a, 'b> &'a Self: Add<&'b Self, Output = Self>,
{
}

impl<T: Copy + Add<Output = T>> Addable for MyVec<T> {}

fn add_stuff<'a, 'b, T: Addable>(x: &'a T, y: &'b T) -> T {
    x + y
}

fn main() {
    let v = MyVec(vec![1, 2, 3]);
    let w = MyVec(vec![2, 4, 6]);
    println!("{:?}", add_stuff(&v, &w));
}

I use the newtype pattern to create an alias of Vec so I can implement a foreign trait (Add) on a foreign struct (Vec).
I implement Add for MyVec and its references. The associated type Output is always the (unreferenced) MyVec. The latter three impls are implemented in terms of the first.
Addable is the central trait that I want to demo. Things that are addable should allow themselves and their references to be added with the result being Self. Particularly, in add_stuff I want the expression x + y + x to be valid where x + y gives a non-ref which can be added with x (which has not been moved out of, because it's a ref) to produce another non-ref.
I don't get any complaints from the compiler regarding the implementation of the Addable trait on MyVec. Specifically, the compiler seems to recognize that the above impls satisfy the bounds in the where clause.

However, I get the following compiler errors:

error[E0277]: the trait bound `for<'a> &'a T: std::ops::Add<T>` is not satisfied
  --> src/main.rs:33:1
   |
33 | / fn add_stuff<'a, 'b, T: Addable>(x: &'a T, y: &'b T) -> T {
34 | |     x + y
35 | | }
   | |_^ no implementation for `&'a T + T`
   |
   = help: the trait `for<'a> std::ops::Add<T>` is not implemented for `&'a T`
   = help: consider adding a `where for<'a> &'a T: std::ops::Add<T>` bound
   = note: required by `Addable`

error[E0277]: the trait bound `for<'a, 'b> &'a T: std::ops::Add<&'b T>` is not satisfied
  --> src/main.rs:33:1
   |
33 | / fn add_stuff<'a, 'b, T: Addable>(x: &'a T, y: &'b T) -> T {
34 | |     x + y
35 | | }
   | |_^ no implementation for `&'a T + &'b T`
   |
   = help: the trait `for<'a, 'b> std::ops::Add<&'b T>` is not implemented for `&'a T`
   = help: consider adding a `where for<'a, 'b> &'a T: std::ops::Add<&'b T>` bound
   = note: required by `Addable`

This can be fixed by amending the add_stuff function with a where clause as suggested by the compiler:

where
    for<'c, 'd> &'c T: Add<&'d T, Output = T>,
    for<'c> &'c T: Add<T, Output = T>,

I do not understand why this is necessary. I thought by specifying a bound in the definition of the trait I could rely on that bound being met for any type that implements that trait? Having to add these where clauses every time sort of defies the whole point of my Addable trait.

Googling brought up this GitHub issue which I don't understand fully but which might be related? That would suggest this is indeed a bug in Rust (which hasn't been fixed for a very long time).

Sebastian Redl Sebastian Redl · Accepted Answer · 2018-03-22T19:38:47

You've hit a shortcoming of the Rust compiler as it currently is. RFC 2089 proposed to make it work as you expect, and was accepted in December 2017.

However, as of today, the feature isn't implemented. The tracking issue for the implementation hasn't seen much activity yet, so it appears implementation hasn't even started. It appears that some fundamental improvements to the compiler's trait bound handling are necessary before this particular feature can be efficiently implemented (search keyword: chalk).

Why is it necessary to add redundant trait bounds even though my trait uses those same traits as bounds?

1 Answers