New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Rewrite how trait-impl matching works in typeck #3742

Closed
nikomatsakis opened this Issue Oct 12, 2012 · 10 comments

Comments

Projects
None yet
7 participants
@nikomatsakis
Contributor

nikomatsakis commented Oct 12, 2012

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 #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).

@ghost ghost assigned nikomatsakis Oct 12, 2012

@nikomatsakis

This comment has been minimized.

Show comment
Hide comment
@nikomatsakis

nikomatsakis Oct 12, 2012

Contributor

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
}
Contributor

nikomatsakis commented Oct 12, 2012

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

This comment has been minimized.

Show comment
Hide comment
@nikomatsakis

nikomatsakis Oct 12, 2012

Contributor

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.

Contributor

nikomatsakis commented Oct 12, 2012

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

This comment has been minimized.

Show comment
Hide comment
@nikomatsakis

nikomatsakis Oct 12, 2012

Contributor

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

Contributor

nikomatsakis commented Oct 12, 2012

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

@catamorphism

This comment has been minimized.

Show comment
Hide comment
@catamorphism

catamorphism May 23, 2013

Contributor

Nominating for milestone 5, production-ready

Contributor

catamorphism commented May 23, 2013

Nominating for milestone 5, production-ready

@pnkfelix

This comment has been minimized.

Show comment
Hide comment
@pnkfelix

pnkfelix Jun 27, 2013

Member

punting to later bug triage with niko present

Member

pnkfelix commented Jun 27, 2013

punting to later bug triage with niko present

@graydon

This comment has been minimized.

Show comment
Hide comment
@graydon

graydon Jul 11, 2013

Contributor

accepted for well-defined milestone

Contributor

graydon commented Jul 11, 2013

accepted for well-defined milestone

@flaper87

This comment has been minimized.

Show comment
Hide comment
@flaper87

flaper87 Feb 11, 2014

Contributor

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.

Contributor

flaper87 commented Feb 11, 2014

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

This comment has been minimized.

Show comment
Hide comment
@treeman

treeman Aug 25, 2014

Contributor

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

Might be related to #5527?

Contributor

treeman commented Aug 25, 2014

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

Might be related to #5527?

@aturon

This comment has been minimized.

Show comment
Hide comment
@aturon

aturon Sep 18, 2014

Member

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

Member

aturon commented Sep 18, 2014

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

@aturon aturon added the I-nominated label Sep 18, 2014

@pnkfelix

This comment has been minimized.

Show comment
Hide comment
@pnkfelix

pnkfelix Sep 18, 2014

Member

closing as dupe of #5527.

Member

pnkfelix commented Sep 18, 2014

closing as dupe of #5527.

@pnkfelix pnkfelix closed this Sep 18, 2014

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment