Overloading an operator with both a type and a reference

user_17753604 0
Viewed 158

The following MWE trying to define all possible multiplications of a container type (containing an abstract multiplicable type) and its references with a float causes the rust compiler to choke up with an evaluation overflow. Based on the message, somehow in the second impl it cannot decide what impl to call if the fourth one is defined. Any idea how to fix it? How to constrain a generic impl to not apply to reference types?

use std::ops::*;

struct A<T> {
    v : T
}

impl<T> Mul<f64> for A<T> where T : Mul<f64> {
    type Output = A<<T as Mul<f64>>::Output>;
    fn mul(self, w : f64) -> Self::Output { A{ v : self.v * w} }
}

impl<T> Mul<A<T>> for f64 where f64 : Mul<T> {
    type Output = A<<f64 as Mul<T>>::Output>;
    fn mul(self, x : A<T>) -> Self::Output { A{ v : self * x.v} }
}

impl<'a, T> Mul<f64> for &'a A<T> where &'a T : Mul<f64> {
    type Output = A<<&'a T as Mul<f64>>::Output>;
    fn mul(self, w : f64) -> Self::Output { A{ v : &(self.v) * w} }
}

// If you remove this
impl<'b, T> Mul<&'b A<T>> for f64 where f64 : Mul<&'b T> {
    type Output = A<<f64 as Mul<&'b T>>::Output>;
    fn mul(self, x : &'b A<T>) -> Self::Output { A { v : self * &(x.v) } }
}

fn main() {
    let t = A{v : 1.0};
    let b = 3.0*&t; // ... and this, then it compiles.
    let c = &t*3.0;
}

If I add type annotations in the impls, the problem just moves to the application in main. The code can be made to compile if an explicit version of mul is always selected, but that is not practical in daily use:

use std::ops::*;

struct A<T>  {
    v : T
}

impl<T> Mul<f64> for A<T> where T : Mul<f64> {
    type Output = A<<T as Mul<f64>>::Output>;
    fn mul(self, w : f64) -> Self::Output { A{ v : <T as Mul<f64>>::mul(self.v, w) } }
}

impl<T> Mul<A<T>> for f64 where f64 : Mul<T> {
    type Output = A<<f64 as Mul<T>>::Output>;
    fn mul(self, x : A<T>) -> Self::Output { A{ v : <f64 as Mul<T>>::mul(self, x.v) } }
}

impl<'a, T> Mul<f64> for &'a A<T> where &'a T : Mul<f64> {
    type Output = A<<&'a T as Mul<f64>>::Output>;
    fn mul(self, w : f64) -> Self::Output { A{ v : <&'a T as Mul<f64>>::mul(&(self.v), w)} }
}

impl<'b, T> Mul<&'b A<T>> for f64 where f64 : Mul<&'b T> { 
    type Output = A<<f64 as Mul<&'b T>>::Output>;
    fn mul(self, x : &'b A<T>) -> Self::Output { A { v : <f64 as Mul<&'b T>>::mul(self, &(x.v)) } }
}

fn main() {
    let t : A<f64> = A{v : 1.0};
    let _a = <f64 as Mul<&A<f64>>>::mul(3.0, &t); // This explicit typing works
    let _b = 3.0*(&t); //  If you remove this, then it compiles.
    let _c = &t*3.0;
}

The error in this version (for the _b-line at the end) is

error[E0275]: overflow evaluating the requirement `f64: std::ops::Mul<&A<_>>`

So it seems as if the compiler was looking for arbitrary Mul<&A<_> instead of Mul<&A<f64>>, which it very well should know from that it needs based on the type annotations of t and even without the explicit annotations.

rust overloading traits
2 Answers

As mentioned in the comments, this is a compiler bug with very little movement to fix it. In the end I came up with a few workarounds that do not require changing architecture, just adding a few hacks. They're both based on a “nesting level counting multiplication trait”. For brevity I only include f64 * &A<T>; for version 2 &A<T> * f64, f64 * A<T>, and A<T>*64 are unchanged from the original question, as they do not require the level-counting workaround. For version 1 the extra level type parameter of A should be handled in those as well.

Version 2

This version is very non-invasive with regard to code that should work without the compiler bug. It only implements a “shadow” variant of the original (multiplication) function that counts nesting levels at the type system level.

use std::ops::*;

// Our nested data structure
struct A<T> {
    v : T
}

// Nesting level counting structs and traits
struct L0 {}
struct Succ<L> { _prev : L }
trait Nested { type Level; }

// Primitives like f64 are at nesting level zero
impl Nested for f64 { type Level = L0; }
// A<T> always increases nesting level
impl<T> Nested for A<T> where T : Nested { type Level=Succ<T::Level>; }

// Nested multiplication trait. Default implementation is standard multiplication.
trait NestedMul<T, L> : Mul<T>  + Sized {
    fn nested_mul(self, a : T) -> Self::Output { self * a}
}
// Auto-implement it at level 0
impl<'b,S,T> NestedMul<&'b T,L0> for S where T : Nested<Level=L0>, S : Mul<&'b T> + Sized {}

// Special implementation of NestedMul for A, bypassing Mul
impl<'b, T : Nested> NestedMul<&'b A<T>, Succ<T::Level>> for f64 where f64 : NestedMul<&'b T, T::Level> {
    fn nested_mul(self, a : &'b A<T>) -> Self::Output {  A { v : self.nested_mul(&(a.v))  } }
}

// The “interface” : when A is multiplied in plain code, we pass to level-counting nested
// multiplication to avoid compiler overflow. 
//
// Version 1: this would be for all nesting structures. Not allowed by Rust as it involves
// no local structs. Similarly f64 has to be hard-coded here / this whole impl macro-generated
// when generalising to other types.
//
//impl<'b, T : Nested> Mul<&'b T> for f64 where f64 : NestedMul<T, T::Level>  { 
//    type Output=<f64 as Mul<&'b T>>::Output;
//    fn mul(self, a : &'b A<T>) -> Self::Output { self.nested_mul(a) }
//}
//
// Version 2: specifically for A<T>. A minor optimisation as bypasses one level of
// nested_mul:
impl<'b, T : Nested> Mul<&'b A<T>> for f64 where f64 : NestedMul<&'b T, T::Level> { 
   type Output=A<<f64 as Mul<&'b T>>::Output>;
   fn mul(self, a : &'b A<T>) -> Self::Output {  A { v : self.nested_mul(&(a.v)) } }
 }

fn main() {
    let t : A<A<f64>> = A{ v : A{v : 1.0 } };
    let _b = 3.0*&t;
}

Version 1

The first version used PhantomData and a type parameter addition to the nesting structure A, so is a bit more invasive. Since type inference in main is not completely automatic using basic struct constructors, a little bit more work would be needed to write constructors for which inference works.

use std::ops::*;
use std::marker::PhantomData;

// Define type-level integers
struct L0 {}
struct Succ<L> { _prev : L }
type L1 = Succ<L0>;
type L2 = Succ<L1>;

// Our nested data structure that includes the nesting level.
struct A<T,L> {
    v : T,
    lev : PhantomData<L>
}

// Nested multiplication trait. Default implementation is standard multiplication.
trait NestedMul<T, L> : Mul<T>  + Sized {
    fn nested_mul(self, a : T) -> Self::Output { self * a }
}

// Implement it for f64 using defaults.
impl<'b,T> NestedMul<T, L0> for f64 where f64 : Mul<T> { }

// Special implementation of NestedMul for A, bypassing Mul
impl<'b,L,T> NestedMul<&'b A<T,Succ<L>>,Succ<L>> for f64 where f64 : NestedMul<&'b T, L> {
    fn nested_mul(self, a : &'b A<T,Succ<L>>) -> Self::Output {
        A { v : self.nested_mul(&(a.v)), lev : PhantomData  }
    }
}

// The “interface” : when A is multiplied in plain code, we pass to level-counting nested
// multiplication to avoid compiler overflow. 
impl<'b, T, L> Mul<&'b A<T, Succ<L>>> for f64 where f64 : NestedMul<&'b T, L> { 
    type Output=A<<f64 as Mul<&'b T>>::Output, Succ<L>>;
    fn mul(self, a : &'b A<T,Succ<L>>) -> Self::Output {
        A { v : self.nested_mul(&(a.v)), lev : PhantomData }
    }
}

fn main() {
    let t : A<A<f64,L1>,L2> = A{ v : A{v : 1.0, lev : PhantomData }, lev : PhantomData };
    let _b = 3.0*&t;
}
user_177536040

This seems to be a limitation of the Rust language itself. You may refer to the popular https://github.com/rust-ndarray/ndarray library and see how it deals with the problem. Its ArrayBase needs to be able to + - * / with another ArrayBase object using either reference or type. IMHO if I remember correctly, they do not have a good way to do so yet.

user_46199580
Related