# Arithmetic operators on references and trait constraints

#1

Hi,

in my toy project I’m experimenting with an abstraction over different bignum implementations. These typically implement arithmetic operations on references to avoid unnecessary clones. Unfortunately my attempts seem to lead to infinite recursions in the type system. Here is an example for such an attempt:

``````trait BigNum
where
for<'a1, 'a2> &'a1 Self: std::ops::Add<&'a2 Self, Output = Self>,
{
}

struct BigNumWrapper<T> {
x: T,
}

impl<'a1, 'a2, T> std::ops::Add<&'a2 BigNumWrapper<T>> for &'a1 BigNumWrapper<T>
where
&'a1 T: std::ops::Add<&'a2 T, Output = T>,
{
type Output = BigNumWrapper<T>;

fn add(self, other: &'a2 BigNumWrapper<T>) -> Self::Output {
BigNumWrapper {
x: &self.x + &other.x,
}
}
}

impl<T: BigNum> BigNum for BigNumWrapper<T> {}``````

This leads to the following error:

``````error[E0275]: overflow evaluating the requirement `<&_ as std::ops::Add<&_>>::Output`
``````

Playground

Note that this does not seem to be caused by the obvious recursion in the last impl. Introducing a copy `BigNum2` of `BigNum` and replacing the constraint in the last impl by `T: BigNum2` gives the same error.

Also the analogous code using values instead of references compiles just fine: Playground

I’d be very grateful if somebody could shed some light on what the problem is here.

Update: Even though this concrete error can be fixed by repeating the constraint on `&'a1 Self` (see the discussion below), the same infinite recursion keeps popping up when actually trying to use the `BigNumWrapper`, in particular in the context of type inference. I therefore did not find this approach viable. Instead I am now implementing the arithmetic operators via a macro for the concrete types `T` that I want to wrap. The code can be found here in case anyone is interested.

#2

It seems like the problem is it can’t pinpoint what the `Output = T` type is (i.e. the `T`) in the `Add` constraint of `BigNumWrapper`'s `Add` impl. The `Add` constraint on `T` is defined in terms of adding two `&T`, but these are different types (from type system perspective) than `T` itself. So it keeps recursing trying to see if `BigNumWrapper` satisfies the `BigNum` constraint.

In the value case, there’s a single type `T` used, and all constraints are defined in terms of it. No mixing of `&T` and `T` and the compiler doesn’t keep chasing the `Output = T` type to resolve it.

Not sure if that’s “scientific” enough of an explanation or even if it’s right .

#3

I’ve also investigated this some more and apparently the constraint on `&'a1 Self` used in the `BigNum` trait does not really work the way I expected.

The following simplified example illustrates what I mean.

The following code compiles just fine, as expected:

``````trait ByVal
where
for<'a> Self: std::ops::Add<&'a Self, Output = Self>
{
}

fn by_val<T: ByVal>(x: T, y: T) -> T {
x + &y
}``````

But the analoguous code

``````trait ByRef
where
for<'a> &'a Self: std::ops::Add<&'a Self, Output = Self>
{
}

fn by_ref<T: ByRef>(x: T, y: T) -> T {
&x + &y
}``````

produces the following error:

``````error[E0277]: the trait bound `for<'a> &'a T: std::ops::Add` is not satisfied
``````

The code only works after (redundantly?) repeating the trait constraint on the `by_ref` function:

``````trait ByRef
where
for<'a> &'a Self: std::ops::Add<&'a Self, Output = Self>
{
}

fn by_ref<T: ByRef>(x: T, y: T) -> T
where
for<'a> &'a T: std::ops::Add<&'a T, Output = T>
{
&x + &y
}``````

This also helps with my original code. If I replace the last line

``impl<T: BigNum> BigNum for BigNumWrapper<T> {}``

with

``````impl<T: BigNum> BigNum for BigNumWrapper<T>
where
for<'a1, 'a2> &'a1 T: std::ops::Add<&'a2 T, Output = T>
{}``````

the code no longer into the recursion and compiles just fine.

I really don’t understand why I have to repeat the constraint when it should already be implied by the definition of the `BigNum` trait (resp. by the definition of the `ByRef` trait in the simplified example).

#4

https://github.com/rust-lang/rfcs/blob/master/text/2089-implied-bounds.md aims at eliminating the need to repeat bounds.

#5

Ok, thank you, that explains it.

So apparently bounds for the type itself do not need to be repeated, that’s why the `ByVal` case works.

The `ByRef` case on the other hand is closer to the

``````trait Foo<U> where U: Eq { }
``````

example from the RFC in that it contains a bound on a different type (`&Self` instead of `Self`). And in this case the constraint on the different type currently needs to be repeated everywhere. Good to know, that makes it a lot less mysterious.