rustc wrongly reports conflicting trait implementations

[rphmeier]

use std::marker::PhantomData;

trait Foo {
    type Bar: Interface<Self>; // = Default<Self>
}

trait Interface<T: Foo> {}

// default implementation, we never implement Alternate<T> for this.
trait DefaultFoo: Foo<Bar=Default<Self>> {}
struct Default<T: DefaultFoo> {
    _marker: PhantomData<T>,
}
impl<T: DefaultFoo> Interface<T> for Default<T> {}

// alternate implementations must use this trait
// predicate on A: Alternate<T> should preclude Default<T>.
trait Alternate<T: Foo<Bar=Self>> {}
impl<T, A> Interface<T> for A
where T: Foo<Bar=A>, A: Alternate<T> {}

fn main() {}

fails with E0119, although the Self types don't overlap.
Playpen: http://is.gd/vT98nf, fails on Stable, Beta, and Nightly.

[rphmeier]

A variation using associated types does compile: http://is.gd/GPGNj9

[huonw]

triage: I-nominated T-lang

I don't have time to really dig into it, but I suspect the bug here might be that the associated type version does compile (although the two examples are fairly different: the second one only has three traits but the first one has 4?). Rust tries to avoid reasoning about implementations that don't exist, unless it absolutely has to (which is what the #[fundamental] attribute does, see e.g. https://dxr.mozilla.org/rust/rev/c14b615534ebcd5667f594c86d18eebff6afc7cb/src/libcore/marker.rs#60 and https://dxr.mozilla.org/rust/rev/c14b615534ebcd5667f594c86d18eebff6afc7cb/src/libcore/ops.rs#1637), because doing this reasoning is a pretty large backwards compatibility risk.

cc @rust-lang/lang, but especially @nikomatsakis

[aturon]

@huonw is correct.

The particular problem here is that a downstream crate could add an impl of Alternate for Default, as in the following:

struct MyNewType;
impl Foo for MyNewType {
    type Bar = MyNewType;
}
impl Alternate<MyNewType> for MyNewType {}

(I'm not sure if I have the nest of traits quite right here, but hopefully you get the basic idea).

The point is, because downstream crates can impl existing traits if they apply Default to a local type, you can't actually reason as if no such impls could exist.

Some of this kind of thing is described in the rebalancing coherence RFC.

[aturon]

Sorry, to be clear: this is working as intended.

[rphmeier]

@aturon @huonw

Thanks for the explanations, I see now that this is not a bug. In a little more experimentation after filing, I found that only the type parameter for Alternate needed to be made associated in order to compile.

In particular, I had assumed that the orphan rule would provide protection against implementations of Alternate<T> for Default, as both traits were defined in an upstream crate. Am I correct in understanding that generic traits are treated as "trait constructors", where monomorphized versions are considered as members of the crate which specialized them, rather than members of the upstream crate which defined the constructor?

Assuming the above is correct, it would make sense for the associated type version to compile, as the Alternate trait can no longer be instantiated differently within downstream crates.

[aturon]

Am I correct in understanding that generic traits are treated as "trait constructors", where monomorphized versions are considered as members of the crate which specialized them, rather than members of the upstream crate which defined the constructor?

The full story is a bit more complicated than that. You can get the scoop in @nikomatsakis's epic blog post.