Impl search fails in case of generalized trait inheritance

[rntz]

The following program fails to compile:

trait Foo { fn foo(&self, x: &Self); }
trait Bar<A: Foo> { fn bar(&self) -> A; }

struct Wrap<T>(T);

impl<A, B: Bar<A>> Wrap<B> {
    fn test(&self, x: &A) {
        (*self).bar().foo(x);
    }
}

fn main() {}

With the following error:

implsearch.rs:8:8: 8:22 error: failed to find an implementation of trait Foo for A
implsearch.rs:8         (*self).bar().foo(x);
                        ^~~~~~~~~~~~~~

Given that B: Bar<A>, we know A: Foo because of the definition of the trait Bar. This can be seen as a generalized case of trait inheritance (trait B inheriting from A lets us know that if X:B, then X:A, because X:B requires X:A; similarly, B:Bar<A> requires A:Foo, so we know A:Foo). Indeed, in Haskell there is no distinction between the two forms of inheritance:

{-# LANGUAGE MultiParamTypeClasses #-}
class Foo b where foo :: b -> b -> ()
class Foo b => Bar a b where bar :: a -> b

test :: Bar a b => a -> b -> ()
test x y = foo (bar x) y

The order of arguments to Bar could be switched and the program above would still be valid.

[huonw]

cc @nikomatsakis

[nikomatsakis]

file under #5527 -- it is a good point.

[steveklabnik]

The error for this sample is now

hello.rs:8:29: 8:34 error: type `Wrap<B>` does not implement any method in scope named `bar`
hello.rs:8                     (*self).bar().foo(x);
                                       ^~~~~
error: aborting due to previous error

[steveklabnik]

Triage: same error, but with extra message:

hello.rs:11:29: 11:34 error: type `Wrap<B>` does not implement any method in scope named `bar`
hello.rs:11                     (*self).bar().foo(x);
                                        ^~~~~
hello.rs:11:34: 11:34 help: methods from traits can only be called if the trait is implemented and in scope; the following trait defines a method `bar`, perhaps you need to implement it:
hello.rs:11:34: 11:34 help: candidate #1: `Bar`
hello.rs:11:41: 11:41 help: methods from traits can only be called if the trait is implemented and in scope; the following trait defines a method `foo`, perhaps you need to implement it:
hello.rs:11:41: 11:41 help: candidate #1: `Foo`

Also, you need the old impl check here:

#![feature(old_impl_check)]

trait Foo { fn foo(&self, x: &Self); }
trait Bar<A: Foo> { fn bar(&self) -> A; }

struct Wrap<T>(T);

#[old_impl_check]
impl<A, B: Bar<A>> Wrap<B> {
        fn test(&self, x: &A) {
                    (*self).bar().foo(x);
                        }
}

fn main() {}

[apasel422]

Even without the old impl check, this example no longer makes sense, because it uses the old unary tuple dereferencing syntax. Today, the compiler is correct that type Wrap<B> does not implement any method in scope named bar, because the type of (*self) is Wrap<B>. That line should now read self.0.bar().foo(x). Updating the trait to use an associated type:

trait Foo {
    fn foo(&self, x: &Self);
}

trait Bar {
    type A: Foo;
    fn bar(&self) -> Self::A;
}

struct Wrap<T>(T);

impl<B: Bar> Wrap<B> {
    fn test(&self, x: &B::A) {
        self.0.bar().foo(x);
    }
}

fn main() {}

compiles successfully. I think this issue can be closed.

[talchas]

Well this still fails, and seems like morally still at least somewhat similar.

trait Foo { fn foo(&self, x: &Self); }
trait Bar<A: Foo> { fn bar(&self) -> A; }
struct Wrap<T>(T);

fn test<A, B: Bar<A>>(wrap: Wrap<B>, x: &A) {
    wrap.0.bar().foo(x);
}

fn main() {}

[arielb1]

This is intentional - non-supertrait bounds are not elaborated.

[nikomatsakis]

Closing as a duplicate of #20671, which has a better explanation.