Constraints on supertraits associated types are ignored

[14427]

The following code:

trait Foo {
    type T;
}

trait Bar {
    fn bar(&self);
}

trait Quux: Foo where Self::T: Bar {
    fn quux(&self) -> Self::T;
}

struct Baz<X> {
    x: X,
}

impl<X: Quux> Baz<X> {
    fn baz(&self) {
        self.x.quux().bar()
    }
}

fails to compile, with the error message

the trait Bar is not implemented for the type <X as Foo>::T [E0277]

As it is impossible for the return type of quux() to not return a type that implements Bar, I think this is a bug in the compiler.

[SSheldon]

Related to #20671?

[frangio]

Here's another, although less general example of this bug:

use std::path::Path;
use std::convert::AsRef;
use std::iter::Peekable;
use std::env;

trait PathIterator: Iterator where <Self as Iterator>::Item : AsRef<Path> {}

impl<I: ?Sized, T: AsRef<Path>> PathIterator for I
    where I: Iterator<Item = T> {}

struct A<I: PathIterator> {
    paths: Peekable<I>,
}

impl<I: PathIterator> A<I> {
    fn next_path(&self) -> Option<&Path> {
        self.paths.peek().map(|p| p.as_ref())
    }
}

fn main() { }

<anon>:17:37: 17:45 error: type `&<I as core::iter::Iterator>::Item` does not implement any method in scope named `as_ref`
<anon>:17         self.paths.peek().map(|p| p.as_ref())
                                              ^~~~~~~~
error: aborting due to previous error

[paholg]

I believe this is the issue that I'm having, and it depends on whether you are implementing a trait with a member function or not. In addition to the compiler not correctly figuring out type constraints, it takes much longer to compile when given type constraints with a where clause.

Consider the following two implementations of addition over Peano numbers using Rust's type system:

First, using std::ops::Add: http://is.gd/7tO1cK

Then, using a custom trait for addition, AddPeano, that has only an associated type and no member functions: http://is.gd/byhqSn

The key difference is here:

Using AddPeano:

impl<Lhs: Peano + AddPeano<Rhs>, Rhs: Peano> AddPeano<Rhs> for Succ<Lhs> {
    type Output = Succ<<Lhs as AddPeano<Rhs>>::Output>;
}

Using std::ops::Add:

impl<Lhs: Peano + Add<Rhs>, Rhs: Peano> Add<Rhs> for Succ<Lhs> where <Lhs as Add<Rhs>>::Output: Peano {
    type Output = Succ<<Lhs as Add<Rhs>>::Output>;
    fn add(self, rhs: Rhs) -> Self::Output { unreachable!() }
}

without the where clause, the compiler gives the error

error: the trait `Peano` is not implemented for the type `<Lhs as core::ops::Add<Rhs>>::Output`

In main() for both of those examples, the Add traits are used for successive doubling until the number 32 is reached. Using AddPeano, playpen finishes in moments, whereas using Add it triggers playpen's timeout and fails to compile.

I have had similar results locally ... even using up 8 GB of ram in the case of the std::ops version while the version without a function would compile virtually instantly.

[arielb1]

Predicates on Self's associated types aren't supertrait predicates and are not elaborated - you need to add the where-clauses explicitly (e.g. where <I as Iterator>::Item : AsRef<Path> in @frangio-s case).

@paholg
That is a different issue. Trait selection is undecidable in general, and therefore can take arbitrarily long time on some cases. I think we should be able to handle this case quickly through - you may want to open a (separate) issue for that.

[paholg]

Okay, will do.

Thanks, @arielb1.

[soltanmm]

There's a workaround for the first example:

trait Foo {
    type T;
}

trait Bar {
    fn bar(&self);
}

trait QuuxMyT {
    type MyT: Bar;
}

trait Quux: QuuxMyT + Foo<T=<Self as QuuxMyT>::MyT> {
    fn quux(&self) -> Self::T;
}

struct Baz<X> {
    x: X,
}

impl<X: Quux> Baz<X> {
    fn baz(&self) {
        self.x.quux().bar()
    }
}

Basically, use the fact that bounds on associated types are always assumed (elaborated? the relevant RFC said 'assume') by moving the bound to a helper trait's associated type, then force the identity relation on that helper trait's associated type and the relevant associated type of the supertrait.