method dispatcher doesn't handle generic implementations properly

[thestinger]

With this example:

pub trait Iterator<A> {
    fn next(&mut self) -> Option<A>;
}

pub trait IteratorUtil<A> {
    fn map<'r, B>(self, f: &'r fn(A) -> B) -> MapIterator<'r, A, B, Self>;
}

impl<A, T: Iterator<A>> IteratorUtil<A> for T {
    fn map<'r, B>(self, f: &'r fn(A) -> B) -> MapIterator<'r, A, B, T> {
        MapIterator{iter: self, f: f}
    }
}

pub struct MapIterator<'self, A, B, T> {
    priv iter: T,
    priv f: &'self fn(A) -> B
}

fn main() {
    let x = Some(5);
    x.map(|x| x.to_str());
}

Option doesn't implement Iterator, but the following error happens:

foo.rs:22:4: 22:26 error: failed to find an implementation of trait Iterator<<V4>> for <V5>
foo.rs:22     x.map(|x| x.to_str());
              ^~~~~~~~~~~~~~~~~~~~~~

[gifnksm]

This issue is similar to #3429 in the sense that the compiler cannot select the proper implementation.
The problem of #3429 is that the implementation for generic type T conflicts with the other 's implementation.

[alexcrichton]

Nominating for backwards-compatible, and failing that, feature-complete.

[graydon]

declined for milestone, this feels like just-a-bug of some sort, probably #3429

[Blei]

Yes, this is the same bug as #3429. The underlying issue in both of them is that the initial filtering of relevant methods is not precise enough, i.e. that it treats impls such as the following as being applicable to each type, regardless whether it implements Bar or not:

trait Foo {
    fn foo(&self);
}

trait Bar {
    fn bar(&self);
}

impl <T: Bar> Foo for T {
    fn foo(&self) { self.bar(); }
}

(This filtering currently happens in librustc/middle/typeck/check/method.rs in the method is_relevant)

In this issue, this causes a surprising error for a type that is not connected to the relevant traits at all, in issue #3429, this causes a conflict of multiple methods, even though only one of them should be applicable.

[thestinger]

@graydon: I think this should have the backwards compatible milestone because it will mean renaming a bunch of methods like transform -> map due to the current workarounds. By itself, it's not a backwards compatibility issue but the standard library makes it one.