Type inference for for loops

[flodiebold]

Now that basic support for associated types is implemented, we should be able to
implement type inference for for loops. E.g. here:

let v = Vec::new();
v.push("foo");
for x in v {
    x;
}

hovering x should say &str (and hence we should get completions for x., etc...).

rustc implements for loops by desugaring to a loop.
We could do the same (once we support resolving associated type paths), but I
feel it'd be simpler to implement type inference for them directly (at least for
now).

Basically the only thing we have to do is introduce a type variable for the type
of the loop variable, and make sure that this variable equals the projection of
the IntoIterator::Item associated type of the iteratee. E.g. let's say we have

let v = Vec::new();
for x in v {}

So at the point we're looking at the for loop, we've already inferred that v
is of type Vec<?0> (where ?0 is an inference variable). We then introduce a
new inference variable ?1 for the type of x and need to 'remember' the
relationship <Vec<?0> as IntoIterator>::Item = ?1. (In this case we could just
immediately resolve the projection, but in general that may not always be
possible.) The type inference process keeps such relationships as
'obligations' that it then regularly tries to resolve to gain further information. Currently
we only have Implements obligations, so we need to add Projection
obligations that say 'this associated type projection equals this other type'. The variant is actually already there, just commented out because we didn't need it so far :)

So, the basic steps to implement this are:

1. Add a test for for loop inference to ty/tests.rs
2. Add the Projection variant to Obligation
3. Handle these obligations during obligation resolution.
   This should work very similar to the existing code for Implements, except
   it needs to call the normalize query instead of implements.
4. When looking at a for loop, introduce a type variable for the pattern (where it currently just uses
   Ty::Unknown), and register a Projection obligation that the projection of
   ::std::iter::IntoIterator::Item for iterable_ty should equal the new type
   variable. Note that IntoIterator isn't a lang item, since rustc just uses a
   desugaring, so we need to somehow resolve the absolute path to get the trait.
5. See whether the test passes.

I think that's it? The test might be a bit awkward because it needs to define
the IntoIterator trait at the right absolute path, and in general having to
hardcode the path is a bit weird (but no different than what rustc does, I
think).

Here's a Zulip stream for questions about this.

[zbelial]

I'd like to tackle this issue if no one is solving it.

[flodiebold]

No one is so far, go ahead!

[flodiebold]

Note, this is implemented, but it's not working yet correctly because Chalk seems to get confused by the impl<T> IntoIterator for T where T: Iterator blanket implementation, so I'll leave this open until we find a solution for that.

[zbelial]

It's great that we have a (partial) implementation, and sorry that I have not solved this issue until now. I was working on this but I need to gain more knowledge about RA and rust, so it took me too much time to get a solution.
Congrats.

[flodiebold]

The bug with the IntoIterator implementation has actually been fixed in Chalk by now, and this is usually working.