Possible bug in trait bounds evaluation

[fizyk20]

I'm encountering infinite recursion in trait bounds evaluation while trying to compile the following code: https://gist.github.com/anonymous/409eb6a2da7fdceafc45 (unfortunately, I haven't been able to compress it more, since I have no idea what exactly is the combination of factors that triggers the error).

The error and backtrace: https://gist.github.com/fizyk20/a4f644c920f00177d52e

Increasing the recursion limit doesn't help, hence my description of the issue as an infinite recursion.

There are a few aspects of the issue that puzzle me:

• commenting either this line or this impl causes the error to disappear. The line multiplies Tensor by a f32, the impl regards Tensor * Tensor.
• This impl causes the same problem, but switching impl<T, U> Mul<Tensor<T, U>> for Vector<T> to impl<T, U> Mul<Vector<T>> for Tensor<T, U> causes the problem to go away (with no changes to the bounds).

I'm aware that the code is long and I haven't provided much information - that's mostly because I have no idea where else to look for any clues. If there is something I can do to make this issue easier to analyze, please tell me and I'll do it.

I'll also mention that I have build the debug version of rustc 1.4.0 to check the debug logs, but I have no idea what to look for. If something from the debug logs is needed, I can also generate it (provided I know what to generate).

If this is not a bug, but just me doing something stupid, I'd also love to hear what I'm doing wrong.

I'd greatly appreciate any help or hint on how to debug this issue further :)

Update: I have just found that changing

let result: Vector<Test2> = vector1 * 5.0;

to

let result: Vector<Test2> = <Vector<Test2> as Mul<f64>>::mul(vector1, 5.0);

makes the code work. The same can be done to get multiplying vectors to work (click). I hope this will help.

Update 2: This doesn't work, either:

let result: Vector<Test2> = Vector::<Test2>::mul(vector1, 5.0);

This leads me to believe that something goes wrong when the compiler tries to choose the appropriate Mul implementation. Somehow this causes it to evaluate bounds for types it was never supposed to choose and overflow. I'm still not sure if this is a bug, but maybe there is a way to improve the algorithm :)

[huonw]

Here's a more reduced version:

use std::marker::PhantomData;
use std::ops::{Add, Mul};
struct B0;
struct B1;
struct UTerm;
struct UInt<U, B> {
    _marker: PhantomData<(U, B)>,
}
impl Add for UTerm
{
    type Output = UTerm;
    fn add(self, _: UTerm) -> Self {
    }
}
impl<U, B> Add<UInt<U,B>> for UTerm {
    type Output = UInt<U, B>;
    fn add(self, _: UInt<U, B>) -> Self::Output {}
}

impl<Ul, Ur> Add<UInt<Ur, B0>> for UInt<Ul, B0>
    where Ul: Add<Ur>
{
    type Output = UInt<<Ul as Add<Ur>>::Output, B0>;
    fn add(self, _: UInt<Ur, B0>) -> Self::Output {}
}

impl<Ul, Ur> Add<UInt<Ur, B1>> for UInt<Ul, B0>
    where Ul: Add<Ur>
{
    type Output = UInt<<Ul as Add<Ur>>::Output, B1> ;
    fn add(self, _: UInt<Ur, B1>) -> Self::Output {
    }
}

trait Pow<Rhs> { type Output; }
impl<U,B> Mul<UInt<U,B>> for UTerm
{
    type Output = UTerm;
    fn mul(self, _: UInt<U, B>) -> Self {
    }
}

impl<Ul, B, Ur> Mul<UInt<Ur, B>> for UInt<Ul, B0>
    where Ul: Mul<UInt<Ur, B>>
{
    type Output = UInt<<Ul as Mul<UInt<Ur, B>>>::Output, B0>;
    fn mul(self, _: UInt<Ur, B>) -> Self::Output {}
}

impl<Ul, B, Ur> Mul<UInt<Ur, B>> for UInt<Ul, B1>
    where Ul: Mul<UInt<Ur, B>>, UInt<<Ul as Mul<UInt<Ur, B>>>::Output, B0>:Add<UInt<Ur,B>>
{
    type Output = <UInt<<Ul as Mul<UInt<Ur, B>>>::Output, B0> as Add<UInt<Ur, B>>>::Output;
    fn mul(self, _: UInt<Ur, B>) -> Self::Output {}
}

type U1 = UInt<UTerm, B1>;
type U2 = UInt<U1, B0>;
trait PrivatePow<Y, N> { type Output; }
impl<X,N> Pow<N> for X where X: PrivatePow<U1, N>
{
    type Output = <X as PrivatePow<U1, N>>::Output;
}

impl<Y, U, B, X> PrivatePow<Y, UInt<UInt<U, B>, B1>> for X
    where X: Mul + Mul<Y>,
         <X as Mul>::Output: PrivatePow<<X as Mul<Y>>::Output, UInt<U, B>>
{
    type Output = <<X as Mul>::Output as PrivatePow<<X as Mul<Y>>::Output, UInt<U, B>>>::Output;
}

trait Variance { type Rank; }

trait CoordinateSystem {
    type Dimension;
}

type Power<T, U> =<T as Pow<U>>::Output;
struct Tensor<T, U> {
    x: (T, U)
}
impl<T, U> Tensor<T, U>
    where T: CoordinateSystem,
          U: Variance,
          T::Dimension: Pow<U::Rank> {
    fn new() {}
}

type Vector<T> = Tensor<T, ()>;
struct Test2;
impl CoordinateSystem for Test2 {
    type Dimension = U2;
}

fn main() {
    Vector::<Test2>::new
}

(Reduced with creduce, plus a few manual tweaks.)

[fizyk20]

Great, thanks a lot! I've never heard of creduce, but after seeing this I'm pretty sure it involves a lot of black magic ;)

I've noticed an interesting thing here: Variance is never implemented for any type, and Vector::<Test2>::new would require that () is Variance.

I guess that means that the error happens before this is resolved. The trouble-causing part is the requirement T::Dimension: Pow<U::Rank> and indeed commenting it out causes the compiler to notice that no new is implemented for Vector<Test2>.

[brson]

Infinite recursion is caught end reported now:

error[E0275]: overflow evaluating the requirement `<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0> as std::ops::Mul<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UInt<UTerm, B1>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>, B0>>>::Output`
  --> <anon>:96:5
   |
96 |     Vector::<Test2>::new
   |     ^^^^^^^^^^^^^^^^^^^^
   |

[nikomatsakis]

This looks legitimate to me, though I don't exactly see why it's occurring. But this is exactly the kind of overflow (a type of ever-increasing size) that the recursion counter is meant to detect.