Type inference with a..b is not as good as with range(a, b)

[japaric]

STR

fn main() {
    (0..8).map(|i| i == 1u64).collect::<Vec<_>>();
    //~^ error: the type of this value must be known in this context
    (0..8).map(|i| 1u64 == i).collect::<Vec<_>>();
    //~^ error: type mismatch resolving `<core::ops::Range<i32> as core::iter::Iterator>::Item == u64`
    range(0, 8).map(|i| i == 1u64).collect::<Vec<_>>();  // OK
    range(0, 8).map(|i| 1u64 == i).collect::<Vec<_>>();  // OK
}

Version

rustc 1.0.0-nightly (458a6a2f6 2015-01-25 21:20:37 +0000)

cc @nick29581

[japaric]

@nikomatsakis I think you have a PR that improves type inference in some cases where closures are involved (?), do you know if by chance that fixes this as well?

[japaric]

This is not closure specific:

let _: Vec<u8> = (0..10).collect();
//~^ error: type mismatch resolving `<core::ops::Range<i32> as core::iter::Iterator>::Item == u8`
let _: Vec<u8> = range(0, 10).collect();  // OK

[edwardw]

This must be duo to #20189. It seems to enforce the numeric fallback rule a bit too eagerly.

[edwardw]

Another example from IRC is that

for x in 0..10 { println!("{}", x); }

type checked while

for x in 0..10 { println!("{}", x % 2); }

didn't. Rather interesting.

[bluss]

edwardw, not just that, type inference regressed slightly at the time of the range stabilization PR.

[ghost]

also related #21595

[edwardw]

Have a partial fix by deferring numeric fallback, but it seems to hit #20297 now.

[nikomatsakis]

OK, so I spent some time digging into this. I don't think that deferring numeric fallback is necessarily the solution. @edwardw sorry if I kept disappearing on IRC, I had to put my head down and study the log to see what was happening.

So what seems to happen is that we correctly come up with the constraint:

1. <Range<_#0i> as Iterator>::Item == u8

However, we are unable to make the connection between u8 and _#0i. The reason is that the new ::ops::Range has separate impls for each of the numeric types, whereas the old Range had only impl for a type A:Int. When we process the projections, we first try to resolve Range<_#0i> as Iterator (without considering the output type Item), and we get ambiguity, because there are many impls that could apply.

Unfortunately this all seems a bit right to me. Basically we're trying to infer the type of the range from the output type, which is the reverse direction inference is supposed to go.

When we used a blanket impl, we were able to resolve this because there was only one impl for Range. Probably the best fix is to go back to that, actually, but this is an interesting quandry. I'll have to think about it a bit.

[nikomatsakis]

To be clear, the example I was digging into was let xs: Vec<u8> = (0..10).collect()

[nikomatsakis]

Also, to put it another way: having a single blanket impl allows us to draw the connection that when you iterate over Range<T>, you get Item=T. With the current setup of many distinct impls, that is not known to be true.

[nikomatsakis]

After some discussion with @aturon on RFC, I just wanted to clarify a few things (I myself was a touch confused too).

1. Changing the impl is probably the easiest way to fix this in the short term.
2. However, to some extent, this limitation is an artifact of how trait matching is implemented. That is, we intentionally do not take output bindings into account when selecting traits. However, it doesn't have to be this way, but it'd take some work to massage the trait matching infrastructure, since impl selection doesn't presently have access to output binding information, that'd have to be propagated inward. It might be interesting to try and address this in a more wholistic way (i.e., something that accounts for the full set of facts that are registered).
3. In particular, the important constraint that we MUST maintain is that, during trans, given the input types, we can derive the output type. But it's permissible for us to use the output type to derive the input type during type checking, since once inference is done, we then have the input types to supply during trans so that we can rederive the output.

[edwardw]

The fix is very simple then. Thanks @nikomatsakis for helping diagnose the problem and pointing to the right direction.