Conflicting between `impl <T: Base> T: Ext` and `impl B: Ext`

[gifnksm]

Minimized test case

(taken from bstrie's comment below)

fn main() {
    let x = X;
    x.foobar();
}

trait Foo {
    fn foobar(&self);
}

trait Bar {
    fn foobar(&self);
}

trait FooBase {}

trait BarBase {}

impl<T: FooBase> Foo for T {
    fn foobar(&self) {}
}

impl<T: BarBase> Bar for T {
    fn foobar(&self) {}
}

struct X;

impl FooBase for X {}

Original bug report follows

I tried implementing of a trait Eq for a generic type T: OrdEx, but rustc says conflicting between impl <T: OrdEx> T: Eq and impl Cmp: Eq.

extcmp.rs:

use cmp::{Eq, Ord};

enum Cmp { Lt, Eq, Gt }

trait OrdEx {
    pure fn cmp(&&other: self) -> Cmp;
}

impl Cmp : Eq {
    pure fn eq(&&other: Cmp) -> bool {
        match (self, other) {
          (Lt, Lt) | (Gt, Gt) | (Eq, Eq) => true,
          _ => false
        }
    }
    pure fn ne(&&other: Cmp) -> bool { !self.eq(other) }
}

impl<T: OrdEx> T : Eq {
    pure fn eq(&&other: T) -> bool { match self.cmp(other) { Eq => true, _ => false } }
    pure fn ne(&&other: T) -> bool { !self.eq(other) }
}

impl<T: OrdEx> T : Ord {
    pure fn lt(&&other: T) -> bool { match self.cmp(other) { Lt      => true, _ => false} }
    pure fn le(&&other: T) -> bool { match self.cmp(other) { Lt | Eq => true, _ => false} }
    pure fn ge(&&other: T) -> bool { match self.cmp(other) { Eq | Gt => true, _ => false} }
    pure fn gt(&&other: T) -> bool { match self.cmp(other) { Gt      => true, _ => false} }
}

fn main() {
}

$ rustc extcmp.rs
extcmp.rs:19:0: 22:1 error: conflicting implementations for a trait
extcmp.rs:19 impl<T: OrdEx> T : Eq {
extcmp.rs:20     pure fn eq(&&other: T) -> bool { match self.cmp(other) { Eq => true, _ => false } }
extcmp.rs:21     pure fn ne(&&other: T) -> bool { !self.eq(other) }
extcmp.rs:22 }
extcmp.rs:9:0: 17:1 note: note conflicting implementation here
extcmp.rs:9 impl Cmp : Eq {
extcmp.rs:10     pure fn eq(&&other: Cmp) -> bool {
extcmp.rs:11         match (self, other) {
extcmp.rs:12           (Lt, Lt) | (Gt, Gt) | (Eq, Eq) => true,
extcmp.rs:13           _ => false
extcmp.rs:14         }
             ...
extcmp.rs:16:40: 16:47 error: multiple applicable methods in scope
extcmp.rs:16     pure fn ne(&&other: Cmp) -> bool { !self.eq(other) }
                                                     ^~~~~~~
extcmp.rs:10:4: 15:5 note: candidate #1 is `__extensions__::eq`
extcmp.rs:10     pure fn eq(&&other: Cmp) -> bool {
extcmp.rs:11         match (self, other) {
extcmp.rs:12           (Lt, Lt) | (Gt, Gt) | (Eq, Eq) => true,
extcmp.rs:13           _ => false
extcmp.rs:14         }
extcmp.rs:15     }
extcmp.rs:20:4: 20:87 note: candidate #2 is `__extensions__::eq`
extcmp.rs:20     pure fn eq(&&other: T) -> bool { match self.cmp(other) { Eq => true, _ => false } }
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
error: aborting due to 2 previous errors

[Dretch]

I have run into this issue too. I think the problem is that rust allows you to use generics to declare multiple impls of a trait for the same type - but typeclass coherence says this shouldn't be allowed.

[nikomatsakis]

In general, support for impls for type parameters is sketchy. It's unclear if such constructs should be allowed at all (though they are unquestionably useful). But if we do decide to allow them, it's clear that we have to beef up our algorithms to deal with the complexities that they introduce. In this case, the bug is because coherence doesn't "go further" to check that all the bounds on the type parameters are met when deciding whether two implementations overlap. This is somewhat tricky---it would basically have to conclude that an implementation on all implements of Foo does not conflict with an implementation on the type A because the type A does not implement Foo. This check is only reasonable, of course, due to coherence itself.

[catamorphism]

Nominated for maturity milestone 1 (well-defined), since there's a question as to whether the code should be allowed.

[graydon]

accepted for well-defined milestone

[graydon]

sub-bug of #5527

[bstrie]

Here's an updated, minimized, self-contained test case:

fn main() {
    let x = X;
    x.foobar();
}

trait Foo {
    fn foobar(&self);
}

trait Bar {
    fn foobar(&self);
}

trait FooBase {}

trait BarBase {}

impl<T: FooBase> Foo for T {
    fn foobar(&self) {}
}

impl<T: BarBase> Bar for T {
    fn foobar(&self) {}
}

struct X;

impl FooBase for X {}

Output:

con.rs:3:4: 3:15 error: multiple applicable methods in scope
con.rs:3     x.foobar();
             ^~~~~~~~~~~
con.rs:23:4: 23:23 note: candidate #1 is `__extensions__::foobar`
con.rs:23     fn foobar(&self) {}
              ^~~~~~~~~~~~~~~~~~~
con.rs:19:4: 19:23 note: candidate #2 is `__extensions__::foobar`
con.rs:19     fn foobar(&self) {}
              ^~~~~~~~~~~~~~~~~~~
con.rs:3:4: 3:15 error: failed to find an implementation of trait BarBase for X
con.rs:3     x.foobar();
             ^~~~~~~~~~~

To clarify, the strangeness here is that even though the type X doesn't implement BarBase (this is even noted in the error message), the impl of Bar for all types T: BarBase conflicts with the impl of FooBase on X.

[pnkfelix]

visited for triage email 2013-07-22.

still a problem.

[pnkfelix]

While investigating the test case posted by bstrie, I noticed this variant of the test has a different error message (but its cause may stem from the same origin). This test's goal was to break the main method into separate functions with type signatures to see if I could force rustc to notice the X -> FooBase -> Foo path.

fn g<F:Foo>(f:&F) {
    f.foobar();
}

fn f<FB:FooBase>(fb:&FB) {
    g(fb);
}

fn main() {
    let x = X;
    f(&x);
}
struct X;
impl FooBase for X {}

trait Foo { fn foobar(&self); }

trait Bar { fn foobar(&self); }

trait FooBase {}
trait BarBase {}

impl<T: FooBase> Foo for T {
    fn foobar(&self) {}
}

impl<T: BarBase> Bar for T {
    fn foobar(&self) {}
}

error message:

% rustc /tmp/rusttmp/baz.rs
/tmp/rusttmp/baz.rs:6:4: 6:5 error: failed to find an implementation of trait Foo for T
/tmp/rusttmp/baz.rs:6     g(fb);
                          ^

[huonw]

@pnkfelix it looks like 906264b fixed that testcase there. (The testcase from the bug occurs still after that merge.)

[pnkfelix]

@huonw oh sorry, I indeed was using rustc from 8a7b636 2013-07-10

[DaGenix]

I hit upon a similar behavior, I think, with the following code:

trait T1 { }

trait T2 { }

struct S1;

impl T1 for S1 { }

impl <S: T2> T1 for S { }

fn main() {}