Bug in checker for duplicate constraints

[bvssvni]

play.rust-lang.org: http://is.gd/AnPaWL

When the same trait is used more than one time but for different concrete types, it triggers the error for duplicate constraints without being sound.

pub trait Get<T> {
    fn get(&self) -> T;
}

pub struct Foo {
    one: uint,
    two: uint
}

pub struct One(pub uint);
pub struct Two(pub uint);

impl Get<One> for Foo {
    fn get(&self) -> One { One(self.one) }
}

impl Get<Two> for Foo {
    fn get(&self) -> Two { Two(self.two) }
}

// error: trait `Get<Two>` already appears in the list of bounds [E0127]
fn bar<T: Get<One> + Get<Two>>(bar: &T) {
    let One(one) = bar.get();
    println!("{}", one);
    let Two(two) = bar.get();
    println!("{}", two);
}

fn main() {
    let foo = Foo { one: 1, two: 2 };
    // Works:
    let One(one) = foo.get();
    println!("{}", one);
    let Two(two) = foo.get();
    println!("{}", two);
    // Does not work:
    bar(&foo);
}

[eddyb]

cc @nikomatsakis @pcwalton @pnkfelix
Should this be handled by multidispatch?

[sebcrozet]

This is also very limiting for generic maths. For example, something like the following is impossible:

fn two_mult<Scalar, Vector, Matrix>(s: Scalar, v: Vector, m: Matrix) -> (Matrix, Vector)
    where Matrix: Mul<Scalar, Matrix> + Mul<Vector, Vector> {
  (m * s, m * v)
}

because Mul cannot appear twice as a trait bound. I am not sure there is a simple workaround for this operator-overloading limitation.

[nikomatsakis]

These are the current rules. I do think we ought to lift the restriction at some point, but there are subtleties to consider around object types. I've been meaning to write up an RFC exploring the details. Still, seems like a non-1.0 blocker to me.

[bvssvni]

As far as I can tell, it blocks the planned redesign of piston-event and Conrod. There is a workaround, but with bad ergonomics as consequence. Definitely high priority for Piston.

@nikomatsakis I'll write up the RFC, if that is what it takes to speed this up.

[reem]

We'd like this in Iron too, as it plays nicely with Set from rust-modifier, but not as much as it is wanted in Piston.

[bvssvni]

@nikomatsakis So far I have come up with a rule:

For each method in the trait, the concrete types that appears in the method signature must differ at least one place.

For example:

pub trait Foo<T> {
    fn foo(&self); // no places to differ, trait can not have duplicates
}

// must differ in concrete type both by T and U
pub trait Bar<T, U> {
    fn bar1<T>(&mut self, t: &T); // must differ in concrete type by T
    fn bar2<U>(&mut self, u: &U); // must differ in concrete type by U
}

// must differ in concrete type by T or U
pub trait Baz<T, U> {
    fn baz<T, U>(&self, t: &T, u: &U);
}

This is a super set of the current constraint in the compiler.

[nikomatsakis]

@bvssvni sorry, I'm not clear on what this proposed rule is trying to achieve?

[bvssvni]

@nikomatsakis I should have explained this better.

Assume you have a signature fn bar<T: Get<One> + Get<Two>>(bar: &T) like in the example. The rule is distinguish whether Get is a duplicate or not and for which arguments you pass, without knowing the content of the function body. While the rule itself might not be necessary to do method resolving, it is helpful to understand what it means by two trait constraints being duplicates. The rule is to prove that any method call in the function body using the trait is not ambiguous, that any method on the trait constraints can be called.

For example, in fn bar<T: Get<One> + Get<U>, U>(...) the two trait constraints are considered duplicates because one contains a concrete type and the other a generic argument. This seems intuitive, but how do we formally define the difference? Well, traits are used for method resolving, so the way we distinguish them is by detecting whether there is a method we can call on either trait that leads to ambiguity. If there is, then there is a use case where one can be said to be a duplicate of the other.

Depending on which constraint we choose, we will end up with different behavior depending whether it is stricter or looser than this rule. For example, we could require all parameters to be concrete types, in which case it is a stricter rule. With a looser rule, we could only compare the arguments, which might mean some methods can not be resolved, even with type annotation.

pub trait Get<T> {
    fn get(&self) -> Foo; 
}

fn bar<T: Get<One> + Get<Two>>(bar: &T) {
    // there is no way to determine the trait from the method,
    // because both returns type `Foo`.
    let x = bar.get();
    ...
}

My point is, the rule defines precisely how to determine whether two trait constraints are duplicates or not.

[bvssvni]

The recent updates to piston-current makes the workaround decent enough to not block the planned redesign. We can wait after Rust 1.0. I will collect information about this in issues under the piston repo, but will probably not write an RFC, since I don't know enough about the compiler. I learned enough to see this requires non-trivial changes.

Closing this since it is not a bug and would better be discussed elsewhere.