Rewrite how trait-impl matching works in typeck

[nikomatsakis]

Right now, we have this hokey thing where it walks the tree at the end, but sometimes (to help with inference) does resolution eagerly, and it's all a big mess. Besides being hard to understand and inefficient, this also means that inference often fails where it could succeed. An example is the overloading example I gave in my blog post, where the result type often fails to be inferred (at least according to some folk on IRC, I haven't experimented much with this myself, so I don't have a precise test case).

I want to have it work something like this:

• There is a list in the fn_ctxt of pending type-trait pairs that need to be resolved
• We add new pairs to this list as we do our type check, assigning each pair an index.
  • We can then create a mapping from the expr.id and probably some other stuff to this index so we can uncover the result in trans, this is tied up a bit in Make a.b() always a method call, refactor how methods are represented in the compiler #3446
• When we add a new pair to the list, we can try to eagerly resolve it at that time, which helps with type inference
• Actually, we are free to try and resolve whenever we like, so we can even wait to try and resolve when we encounter types whose structure is not known but needs to be
• At the end, we walk the list and make sure all pairs are resolvable

These pairs more-or-less correspond to Haskell's type contexts. "Eager resolution" is context simplification. The only reason it's reasonable to use pairs is if we decide to enforce overload freedom, as I described in my blog post.

Also, to ensure termination, it may be necessary to add a depth to these pairs, unless we decide to enforce something like Haskell's Paterson or Basic conditions (which I am not sure how I feel about).

[nikomatsakis]

Here is a test case where inference fails:

struct Vec2 {
    x: float,
    y: float
}

// methods we want to export as methods as well as operators
impl Vec2 {
#[inline(always)]
    pure fn vmul(other: float) -> Vec2 {
        Vec2 { x: self.x * other, y: self.y * other }
    }
}

// Right-hand-side operator visitor pattern
trait RhsOfVec2Mul<Result> { pure fn mul_vec2_by(lhs: &Vec2) -> Result; }

// Vec2's implementation of Mul "from the other side" using the above trait
impl<Res, Rhs: RhsOfVec2Mul<Res>> Vec2: Mul<Rhs,Res> {
    pure fn mul(rhs: &Rhs) -> Res { rhs.mul_vec2_by(&self) }
}

// Implementation of 'float as right-hand-side of Vec2::Mul'
impl float: RhsOfVec2Mul<Vec2> {
    pure fn mul_vec2_by(lhs: &Vec2) -> Vec2 { lhs.vmul(self) }
}

// Usage with failing inference
fn main() {
    let a = Vec2 { x: 3f, y: 4f };

    // the following compiles and works properly
    let v1: Vec2 = a * 3f;
    io::println(fmt!("%f %f", v1.x, v1.y));

    // the following compiles but v2 will not be Vec2 yet and
    // using it later will cause an error that the type of v2
    // must be known
    let v2 = a * 3f;
    io::println(fmt!("%f %f", v2.x, v2.y)); // error regarding v2's type
}

[nikomatsakis]

Actually, this example is illustrating a bit of a different bug than I thought it was. Here the bug is that operator overloading doesnt' attempt eager resolution. If you rewrite 'a * 3f' to 'a.mul(3f)' it works fine.

[nikomatsakis]

I still think we should do this refactoring but I am not sure if it it will ultimately make inference work any better =)

[catamorphism]

Nominating for milestone 5, production-ready

[pnkfelix]

punting to later bug triage with niko present

[graydon]

accepted for well-defined milestone

[flaper87]

Triage bump. It still needs to be implemented.

@nikomatsakis mentioned he has a concrete plan for it and he'll write it down later this week.

[treeman]

Triage bump. Is this relevant? I tried and failed to create a test case for it.

Might be related to #5527?

[aturon]

Nominating for removal from "P-backcompat-lang". Should this issue even be open any more?

[pnkfelix]

closing as dupe of #5527.