Implement type inference for binary operators

[flodiebold]

We need to infer the result types of binary operations, like a + b or a && b. In general, this will involve the following steps:

• we probably want to wait for Introduce hir::Expr #386 to have hir::Expr::BinOp
• add a test in ra_hir/src/ty/tests.rs for the binary operation
• in infer_expr in ty.rs, add the code to infer the type of both operands and then calculate the result type.

One complication is that many operators are overloadable via traits (e.g. Add). To implement these correctly, we would have to be able to do associated type projections (i.e. calculate <T1 as Add<T2>>::Output). Since we're still quite a bit away from doing that, we might hard-code the result types for the primitive operations at least (and maybe it makes sense to guess that the output type is the same as the input type, but that could result in wrong inferences).

Specifically, we've got these groups of binary operations:

• short-circuiting bool operations && and ||: These aren't overloadable and always have result type bool, so the inference is easy
• comparison / equality: ==, < etc.: These are overloadable, but the result type is still always bool, so it's still easy 😄
• assignment: =. This isn't overloadable, and the return type is always () (Ty::unit()). The right side needs to be coercible to the left; we don't have coercion yet, but we can already pass down the type of the left side as the expectation for the right side.
• operation + assignment: +=, *= etc.. Overloadable, but result type is still always ().
• arithmetical and bitwise operations: +, -, |, & etc.. These are overloadable with arbitrary result types, so we can't handle this in general without trait resolution, but we could still handle primitive types.
• ranges .. and ..=: Not overloadable, but we need to find the various Range structs to construct the type.

I'd suggest taking these on one bullet point at a time 😄

[marcusklaas]

I'm working on type inference for binary operations on primitive numbers now.

[flodiebold]

@marcusklaas I've got the refactoring for #386 coming up, which changes a lot of code in type inference... So you're going to get a lot of conflicts if you start now :) I'll rebase and push my branch when #440 is merged, so maybe it'd be a good idea to wait for that.

[marcusklaas]

Sounds good, I'll fix #440 and then wait for your code. Thanks for the heads-up :-)

[flodiebold]

Ok, the PR is #446.

[simonvandel]

What is missing before this can be closed?

[DJMcNab]

Searching for lang items and trait resolution :P. The former probably also requires a better api for handling attributes.