Parameterized traits can't be implemented for arbitrary types even if their parameters are "local"

[netvl]

This program fails to compile:

use std::ops::Add;

struct BigFloat;

impl Add<BigFloat> for f64 {
    type Output = BigFloat;

    fn add(self, rhs: BigFloat) -> BigFloat {
        BigFloat
    }
}

fn main() {}

The error:

test7.rs:5:1: 11:2 error: the type `f64` does not reference any types defined in this crate; only traits defined in the current crate can be implemented for arbitrary types [E0117]
test7.rs:5 impl Add<BigFloat> for f64 {
test7.rs:6     type Output = BigFloat;
test7.rs:7 
test7.rs:8     fn add(self, rhs: BigFloat) -> BigFloat {
test7.rs:9         BigFloat
test7.rs:10     }
            ...
error: aborting due to previous error

I would expect that this should work because Add's parameter is "local" type. Associated types and multidispatch RFC agrees with me.

reddit discussion

[japaric]

cc @aturon @nikomatsakis

[huonw]

It turns out the rules from that RFC weren't quite good enough, unfortunately. #19470

[nikomatsakis]

For the moment, at least, this error is expected. We may revise the rules in the future and plan to (at least) write up a good description of how we arrived at the current rules.

[renato-zannon]

(re-post from reddit, since this didn't get much attention there, and I think it might be a potential solution to allow overriding binops on both sides)

From the new rules , it sounds like the design for the operators should be changed to contain both the LHS and RHS on the Self type if we want to allow overloading on both sides.

Could we do something like this?

on libcore:

trait Add {
    type Output;
    fn add(self) -> <Self as Add>::Output;
}

on user libraries:

struct BigFloat;

impl Add for (f64, BigFloat) {
    type Output = BigFloat;

    fn add(self) -> BigFloat {
        BigFloat
    }
}

impl Add for (BigFloat, f64) {
    type Output = BigFloat;

    fn add(self) -> BigFloat {
        BigFloat
    }
}

And then, make a + b desugar to (a, b).add()

[nikomatsakis]

Plausibly, but it carries limitations as well. For example, one cannot do this:

impl<T:Iterable<Item=U>,U> Add for (T, MyVec<U>)

Perhaps it's a worthy trade-off though.

We don't necessarily have to change the trait itself so much as add a way for Add to opt in to considering the RHS part of the "self input" (for purposes of orphan check) vs an "auxiliary input". We would however have to do that before 1.0 or it would be backwards incompatible.

@nikomatsakis I think the following would work for both cases with the current rules. There's more boilerplate but that shouldn't be a too big of a deal. It could be simplified with equality constraints.

pub mod tag {
    pub enum Add {}
    pub enum Mul {}
}

trait OpSelf { type LHS; type RHS; }
impl<LHS, RHS> OpSelf for (LHS, RHS) { type LHS = LHS; type RHS = RHS; }

trait Op<Tag, LHS, RHS>: OpSelf<LHS = LHS, RHS = RHS> { type Out; }

trait Add<LHS, RHS>: Op<tag::Add, LHS, RHS> {
    fn add(self) -> <Self as Op<tag::Add, LHS, RHS>>::Out;
}

struct BigFloat;
impl Op<tag::Add, f64, BigFloat> for (f64, BigFloat) { type Out = BigFloat; }
impl Add<f64, BigFloat> for (f64, BigFloat) {
    fn add(self) -> BigFloat { BigFloat }
}

impl Op<tag::Add, BigFloat, f64> for (BigFloat, f64) { type Out = BigFloat; }
impl Add<BigFloat, f64> for (BigFloat, f64) {
    fn add(self) -> BigFloat { BigFloat }
}

struct MyVec<U>;
impl<U, T: Iterator<Item = U>> Op<tag::Add, T, MyVec<U>> for (T, MyVec<U>) { type Out = MyVec<U>; }
impl<U, T: Iterator<Item = U>> Add<T, MyVec<U>> for (T, MyVec<U>) {
    fn add(self) -> MyVec<U> { unimplemented!() }
}

[rrichardson]

I think I am seeing a symptom of this with this code: http://is.gd/WbOmdE
Please let me know if this is not the case (also I'm sure there are other issues with this code)

use std::ops::Shl;

pub trait Subscriber {
    type Input;
}

pub trait Publisher<'a> {
    type Output;
}

pub trait Processor<'a> : Subscriber + Publisher<'a> { }

impl<'a, P> Processor<'a> for P
where P : Subscriber + Publisher<'a> { }


impl<'a, PR, PB> Shl<Box<PR>> for Box<PB>
where PR : Processor<'a, Input=<PB as Publisher<'a>>::Output>,
      PB : Publisher<'a, Output=<PR as Processor<'a>>::Input>
{
    type Output = Box<Publisher<'a, Output=<PR as Processor<'a>>::Output> + 'a>;

    fn shl(self, rhs: Box<PR>) -> Box<<Self as Shl<Box<PR>>>::Output> {
        rhs as Box<PB>
    }
}


fn main() {}

[nikomatsakis]

@rrichardson none of the proposed rules allow for that example that you just gave. The problem is that there are no local types in the impl -- just Box<PR> and Box<PB>. Now, because PR and PB implement the Processor and Publisher traits, you could argue that they are local, but it's not really true. Those traits can be implemented for any types, and moreover could be implemented by downstream crates. @aturon and I went through a lot of examples like that and basically concluded that it's super hard to use traits to "divvy up" the impl space like that. It seems to create a hard requirement that for every impl we check every other existing impl for coherence violations, at minimum, which seems like a bad O(n^2) requirement to impose (though in practice it'd likely be optimizable in most common cases to not require a true O(n^2) check).