Infinite recursion compilation error on a type that is not recursive


#1

I’m a scientific programmer exploring Rust’s potential to provide a superior interface and structure for scientific libraries. I have found that it is pretty easy to trigger infinite recursion in the compiler on generic types that look pretty clearly (to me anyway) to not be recursive. I posted the following example on Stackoverflow, and someone else pointed out a similar one.

extern crate num;

use std::ops::Mul;
use num::traits::Float;
use num::traits::Zero;

trait Matrix<E: Float> {}

struct DenseMatrix<E: Float> {
    n: usize,
    m: usize,
    elements: Vec<E>,
}

impl<E: Float> Matrix<E> for DenseMatrix<E> {}

impl<'a, 'b, E: Float + Zero> Mul<&'b DenseMatrix<E>> for &'a DenseMatrix<E>
    where &'a E: Mul<&'b E, Output=E>,
          E: Zero
{
    type Output = DenseMatrix<E>;
    fn mul(self, rhs: &'b DenseMatrix<E>) -> Self::Output { unimplemented!() }
}

fn multiply<'a, E: Float, T: Matrix<E>>(x: &'a T) -> T
    where &'a T: Mul<&'a T, Output=T> { unimplemented!() }

fn main() {
    let matrix = multiply(&DenseMatrix { n: 2, m: 2, elements: vec![1.0, 2.0, 3.0, 4.0] });
}
error[E0275]: overflow evaluating the requirement `<&_ as std::ops::Mul<&_>>::Output`
  --> src\main.rs:32:18
   |
32 |     let matrix = multiply(&DenseMatrix { n: 2, m: 2, elements: vec![1.0, 2.0, 3.0, 4.0] });
   |                  ^^^^^^^^
   |
   = help: consider adding a `#![recursion_limit="128"]` attribute to your crate
   = note: required because of the requirements on the impl of `std::ops::Mul<&DenseMatrix<_>>` for `&DenseMatrix<_>`
   = note: required because of the requirements on the impl of `std::ops::Mul<&DenseMatrix<DenseMatrix<_>>>` for `&DenseMatrix<DenseMatrix<_>>`
   = note: required because of the requirements on the impl of `std::ops::Mul<&DenseMatrix<DenseMatrix<DenseMatrix<_>>>>` for `&DenseMatrix<DenseMatrix<DenseMatrix<_>>>`
   = note: required because of the requirements on the impl of `std::ops::Mul<&DenseMatrix<DenseMatrix<DenseMatrix<DenseMatrix<_>>>>>` for `&DenseMatrix<DenseMatrix<DenseMatrix<DenseMatrix<_>>>>`
...

This behavior makes it hard to implement generic traits on generic containers. This doesn’t appear to be fundamental limitation of the type system, but I don’t know what unintended consequences might be for changing this. The compiler should be able to conclude that &DenseMatrix<DenseMatrix<_>> is a dead end because DenseMatrix<_> does not satisfy E: Float for any value of _, yet it persists. Or perhaps more importantly, &DenseMatrix {...} does not satisfy &DenseMatrix<DenseMatrix<_>> for any value of _.

Am I using Rust wrong? Is this a known limitation? Is this a desired limitation (to avoid something worse)?


Why Rust fails hard at scientific computing