Arithmetic operators on references and trait constraints

help
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 :slight_smile:.

3

Thanks for your reply.

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. :slight_smile: