Type inference do not take bounds from impl into account

In the example below I get the following error.

error[E0284]: type annotations required: cannot resolve `<_ as Stream>::Item == char`
  --> src/main.rs:60:49
   |
60 |     let _: (char, &str) = satisfy(|c| c != 'a').map(|c| c).parse("").unwrap();
   |                                                 ^^^
   |
   = note: required because of the requirements on the impl of `Parser<_>` for `Satisfy<[closure@src/main.rs:60:35: 60:47]>`

Perhaps this is intended but I couldn't find anything stating that, feel free to close if that is the case.

#[derive(Clone)]
pub struct Satisfy<P> {
    predicate: P,
}

trait Stream {
    type Item;
}

impl<I, P> Parser<I> for Satisfy<P>
where
    I: Stream,
    P: FnMut(I::Item) -> bool,
{
    type Output = I::Item;
}

pub fn satisfy<P, C>(predicate: P) -> Satisfy<P>
where
    P: FnMut(C) -> bool,
{
    Satisfy { predicate }
}

pub struct Map<P, F>(P, F);
impl<I, B, P, F> Parser<I> for Map<P, F>
where
    I: Stream,
    P: Parser<I>,
    F: FnMut(P::Output) -> B,
{
    type Output = B;
}

impl<'a> Stream for &'a str {
    type Item = char;
}

pub trait Parser<Input>
where
    Input: Stream,
{
    type Output;

    fn parse(&mut self, input: Input) -> Result<(Self::Output, Input), ()> {
        unimplemented!()
    }

    fn map<F, B>(self, f: F) -> Map<Self, F>
    where
        F: FnMut(Self::Output) -> B,
        Self: Sized,
    {
        Map(self, f)
    }
}

fn main() {
    let _: (char, &str) = satisfy(|c| c != 'a').map(|c| c).parse("").unwrap();
}

1. I believe this is legitimately ambiguous code. You get a somewhat clearer explanation if you qualify the map call:

      |
   59 |     <_ as Parser<_>>::map(satisfy(|c| c != 'a'), |c| c)
      |                  ^ cannot infer type for `_`
   

   There is no way for it to pick an unambiguous I for the impl<I, P> Parser<I> for Satisfy<P>. It could pick any I that satisfies <I as Stream>::Item == char (which is what you saw in the original error).

   David Tolnay at 2018-01-21 08:06:10

2. @dtolnay Hmm you are right. I guess the actual thing I want here is to be able to call methods such as map, which do not refer to the type parameters of the trait. That might not be solvable without higher ranked trait bounds though :/.

   Markus Westerlind at 2018-01-24 18:40:16

3. I have the same issue, but I think this is not ambiguous

   struct Qux;
   struct Map<T, F>(T, F);
   
   trait Foo {
       fn map<F>(self, f: F) -> Map<Self, F> where Self: Sized, Map<Self, F>: Foo {
           Map(self, f)
       }
   }
   trait Bar: Foo {
       fn bar(&self) {}
   }
   
   impl Foo for Qux {}
   impl Bar for Qux {}
   
   impl<T, F> Foo for Map<T, F> where F: FnOnce() {}
   impl<T, F> Bar for Map<T, F> where F: FnMut() {}
   
   fn main() {
       fn id<F>(f: F) -> F { f }
       
       Qux.map(id(||())).bar();
       // Qux.map(||()).bar(); // doesn't work
   }
   

   playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0303c8f3ddd73801e5fb0f83d7e570d7

   If you un-comment out the last line in main, this program fails to compile. It seems to be that it doesn't infer that the closure || () could in fact implement FnMut(), so it doesn't implement it.

   Mine looks like another version of #26085

   RustyYato at 2019-04-25 05:15:10