Improve inference for conditional dispatch

[nikomatsakis]

In the comments on PR #17669, @japaric raised this example:

use std::vec::MoveItems;

trait IntoIter<I> {
    fn into_iter_(self) -> I;
}

impl<T, I: Iterator<T>> IntoIter<I> for I {
    fn into_iter_(self) -> I {
        self
    }
}

impl<T> IntoIter<MoveItems<T>> for Vec<T> {
    fn into_iter_(self) -> MoveItems<T> {
        self.into_iter()
    }
}

fn into_iter<I, S: IntoIter<I>>(iterable: S) -> I {
    iterable.into_iter_()
}

fn main() {
    let v = vec![0u8, 1, 2];

    // WORKS OK
    let i: MoveItems<u8> = into_iter(v); 

    // FAILS TO INFER
    let i = into_iter(v);
}

This comment describes why inference fails: #17669 (comment)

It's plausible we could infer a result here. More concretely, it would mean changing the logic in evaluate_stack to not be so eager to declare a trait-reference ambiguous it it contains an unbound variable. However, we have to be careful:

• This rule affects coherence. After all, an impl like impl IntoIter<Vec<u8>> for Vec<u8> would be a coherence violation.
• This rule also affects an infinite loop problem we had where a rule like impl<T:Eq> Eq for Vec<T>, when matching against an inference variable $0, would unify and yield a subconstraint $1 : Eq for some fresh variable $1, which would then unify with Vec<$2> and repeat into a horrible cycle. This rule was what evades that cycle and made the whole patch work.

So I'm not 100% sure this can be fixed, but I suspect it could if we made the rule more subtle.

[steveklabnik]

MoveItems is now gone, so I'm not sure what code sample constructs this.

[nikomatsakis]

I think I'm going to close this. There are certainly improvements to be made but I think the pressing need for this particular example is past.

[bombless]

cc me