HRTB: Generic matrix struct and type inference issues


#1

Hello all,

Figured this would be the best place to ask for help with some slightly esoteric Rust programming.

A little while ago, I attempted to create a generic small-matrix struct with the typical linear algebra operations, multiplications, etc. I also didn’t want it to contain just primitive types, so I followed these instructions and used higher ranked trait bounds to make it work with references to both primitive types and any other type implementing Add. To this end, I created the following structs and functions:

#[derive(Debug,Clone,PartialEq,Eq)]
pub struct Mat2x2<T>
{
    m: [T; 4],
}

impl<'a, 'b, T> ops::Mul<&'b Mat2x2<T>> for &'a Mat2x2<T>
    where T: Clone + ops::Add<Output = T>,
for<'c> &'c T: Clone + ops::Mul<Output = T>
{
    type Output = Mat2x2<T>;

    fn mul(self, rhs: &'b Mat2x2<T>) -> Self::Output
    {
        let m = &self.m;
        let n = &rhs.m;
        Mat2x2 { m: [
            &m[0]*&n[0] + &m[1]*&n[2], &m[0]*&n[1] + &m[1]*&n[3],
            &m[2]*&n[0] + &m[3]*&n[2], &m[2]*&n[1] + &m[3]*&n[3]
        ]}
    }
}

fn main()
{
    let a = Mat2x2 { m: [1, 0, 0, 1] };
    let b = Mat2x2 { m: [1, 0, 0, 1] };
    let c = &a * &b;
    assert_eq!(a, c);
}

And this works fine on its own, but when I introduce some other function that also uses higher ranked trait bounds and type-inference, things get a bit weird:

#![recursion_limit="10"]
use std::ops;

#[derive(Debug,Clone,PartialEq,Eq)]
pub struct Mat2x2<T>
{
    m: [T; 4],
}

fn testing<T>() -> T
    where T: Clone + From<u64>,
for<'a> &'a T: ops::Mul<Output = T>
{
    let a: T = From::from(0);
    let b: T = From::from(1);
    let d: T = &a * &b;
    d
}

impl<'a, 'b, T> ops::Mul<&'b Mat2x2<T>> for &'a Mat2x2<T>
    where T: Clone + ops::Add<Output = T>,
for<'c> &'c T: Clone + ops::Mul<Output = T>
{
    type Output = Mat2x2<T>;

    fn mul(self, rhs: &'b Mat2x2<T>) -> Self::Output
    {
        let m = &self.m;
        let n = &rhs.m;
        Mat2x2 { m: [
            &m[0]*&n[0] + &m[1]*&n[2], &m[0]*&n[1] + &m[1]*&n[3],
            &m[2]*&n[0] + &m[3]*&n[2], &m[2]*&n[1] + &m[3]*&n[3]
        ]}
    }
}

fn main()
{
    let a = Mat2x2 { m: [1, 0, 0, 1] };
    let b = Mat2x2 { m: [1, 0, 0, 1] };
    let c = &a * &b;
    assert_eq!(a, c);

    let res: u64 = testing::<_>();
    let ans: u64 = 55;
    assert_eq!(res, ans);
}

This will refuse to compile with the error:

error[E0275]: overflow evaluating the requirement `<_ as std::ops::Add>::Output`
  --> src/lib.rs:44:20
   |
44 |     let res: u64 = testing::<_>();
   |                    ^^^^^^^^^^^^
   |
   = help: consider adding a `#![recursion_limit="10"]` attribute to your crate
   = note: required because of the requirements on the impl of `std::ops::Mul` for `&'c Mat2x2<_>`
   = note: required because of the requirements on the impl of `std::ops::Mul` for `&'c Mat2x2<Mat2x2<_>>`
   = note: required because of the requirements on the impl of `std::ops::Mul` for `&'c Mat2x2<Mat2x2<Mat2x2<_>>>`
   = note: required because of the requirements on the impl of `std::ops::Mul` for `&'c Mat2x2<Mat2x2<Mat2x2<Mat2x2<_>>>>`
   = note: required because of the requirements on the impl of `for<'a> std::ops::Mul` for `&'a Mat2x2<Mat2x2<Mat2x2<Mat2x2<Mat2x2<_>>>>>`
   = note: required by `testing`

(I explicitly set the recursion depth rather low to reduce the amount of output).

If I understand this correctly, Rust is unable to deduce the type T for testing, and is for some reason trying all possible nestings of Mat2x2 to figure it out and the process of doing that runs afoul of the generic recursion depth limit.

As far as I can tell, this happens because Mat2x2 implements Mul and requires T to also implement it, enabling this kind of recursion. So what I’m wondering is this: Is this working as intended? And if so, is there any way to work around it?

It is possible to explicitly set the type for testing, but that essentially means that type inference gets disabled when using this kind of structures, which is a bit of a shame.


#2

I think this is a known issue, where inference hits infinite recursion while trying to decide if a type is applicable. The fact that the bound uses T and &T makes it not terminate as it keeps oscillating between the two trying to figure out the precise type.

I think you’ll need to stick with explicit type param in this case.


#3

Hmm, I’m not sure if the T and &T is what’s causing it. It’s possible to
drop some ergonomics in the mul function by only using &T bounds:

impl<'a, 'b, T> ops::Mul<&'b Mat2x2<T>> for &'a Mat2x2<T>                                                                                                                                                         
21     where for<'c> &'c T: Clone + ops::Mul<Output = T> + ops::Add<Output = T>,                                                                                                                                     
22 {                                                                                                                                                                                                                 
23     type Output = Mat2x2<T>;                                                                                                                                                                                      
24                                                                                                                                                                                                                   
25     fn mul(self, rhs: &'b Mat2x2<T>) -> Self::Output                                                                                                                                                              
26     {                                                                                                                                                                                                             
27         let m = &self.m;                                                                                                                                                                                          
28         let n = &rhs.m;                                                                                                                                                                                           
29         Mat2x2 { m: [                                                                                                                                                                                             
30             &(&m[0]*&n[0]) + &(&m[1]*&n[2]), &(&m[0]*&n[1]) + &(&m[1]*&n[3]),                                                                                                                                     
31             &(&m[2]*&n[0]) + &(&m[3]*&n[2]), &(&m[2]*&n[1]) + &(&m[3]*&n[3])                                                                                                                                      
32         ]}                                                                                                                                                                                                        
33     }                                                                                                                                                                                                             
34 }         

This still causes the same infinite recursion as before.


#4

In my own utils where I’ve run into this, I had success working around this by removing all bounds of the form for<'c> &'c T: Add<U> or T: for<&'b> Add<&'b U> and just writing all bounds as involving T by value, cloning as necessary. In your latest example I would write T: Clone + etc.

(&'c T: Clone is trivially true, anyways)


To be clear, I dont’t use &'a T: Add<&'b U> either. I exclusively use T: Add<U>. (with a frowney face in the comments, where applicable)


To be even clearer, the above is only referring to my where bounds. You can still impl Add for borrowed types:

impl<'a, 'b, A, B, C> Add<&'b Mat<B>> for &'a Mat<A>
where A: Clone, B: Clone, A: Add<B, Output=C>
{ ... }

#5

But your bounds are still using T and &T. Namely, the associated type Output is bound in terms of T. Trait resolution and unification will need to solve for that type, and it hits this infinite recursion. I’m honestly not sure if it’s a bug or not - my hunch is that it is, but there may be some a good reason for why it’s like this and perhaps the error could be better.

Maybe @nikomatsakis, @arielb1, or @eddyb could shed some light (not sure how often they visit this forum vs the internals one). Alternatively, @Xaldew, you can file a github issue and hopefully someone will clarify what exactly is the issue.


#6

Ah, you’re right of course. I forgot to consider the right hand side of the bounds. anyways, i did go ahead and post this as an issue github, available here:

https://github.com/rust-lang/rust/issues/46637

Hopefully someone should be able to clarify things and perhaps at least improve the error message.


#7

This is all true, but I believe that by using references I could remove most the clone calls from the code and also cut down on the amount of clones that have to be created. Consider for instance a matrix of BigInts with thousands of digits, you don’t really want to clone those unnecessarily.


#8

Yes, you could… if it didn’t cause rustc to poop its pants. But as things stand, to the best of my knowledge, you currently have no choice. (I would be thrilled to be proven otherwise.)

All I can say is that I hope you don’t personally need to support BigInts right now, and that, if you do need to support them, then you need to design something specifically for that alone. (or to accept the performance hit of the Clones)

If you want, you can make some trait

pub trait DumbClone: Clone { }

impl<T: Clone> DumbClone for T { }

that you can use in your bounds whenever you really ought to be able to support references, to make it easier to grep around for what to fix when such becomes possible in a future version of rust.