Issue 1755 - Overload selection patch - haxe

[issuesbot]

[Google Issue #1755 : https://code.google.com/p/haxe/issues/detail?id=1755] by waneck, at 30/04/2013, 21:27:11 After countless tries to get overload selection working on Haxe, I think I've finally managed to do it.

I'm attaching a minimal patch for review which will allow Haxe to have a proper overload selection algorithm. All selection-related code is self-contained into a codegen.ml module, and I think I could achieve it with minimal changes to typer.ml .

The selection algorithm follows C#'s definition of 'better function member' (http://msdn.microsoft.com/en-us/library/aa691338(v=vs.71).aspx), which seems to fit nicely into Haxe.

I'll write a more detailed email about why we need it for Haxe 3.0, but it boils down to:

• Our current 'first-match' algorithm can easily completely shadow some more specific suggestions (e.g. function (i:Int):Void shadowed by function(f:Float):Void)
• Our current algorithm also doesn't support versioning; Since as long as there's a viable function available, it will accept it, we can't tailor our algorithm throughout Haxe 3.0 without quietly breaking code.
• On the other hand, with an algorithm that can detect ambiguity and throw an error when found, we can later tailor more specific rules which will allow a better overload choice algorithm
• This can potentially allow better typing also for languages like JavaScript

Implementation details: The unify_call_params function remains almost unchanged. The only difference is that even when it finds a matching type, it still goes through until all potential candidates are exhausted. When exhausted, if only one compatible function was found, it is returned; Otherwise, the candidates are passed to Codegen.Overloads.reduce_compatible, which will either take off a candidate completely (if e.g. the person used 'untyped' and types aren't valid, or if the user used a Dynamic type when Dynamics aren't expected), or rate it following the above definition of a 'better function member'.

• Problem: The algorithm still can't handle overloads with constrained type parameters. I've started working on it, it isn't too hard to support it, but I figured that it would be best to keep the patch nice and clean for now. Anyway, this is one of the advantages of this, is that we can later support constrained types without this being a breaking change.

Thank you!

[issuesbot]

[comment from waneck, published at 30/04/2013, 21:52:32] Quick update: I was following C#'s algorithm too literally, and if a Dynamic-typed object was passed to the overloaded function, it would outright reject it as a valid function (as it hurts the 'implicit conversion' rule - being a downcast) I've realized it doesn't make much sense for Haxe, so I've changed it. Anyway, unrelated types being passed with 'untyped' still will be rejected by the overload selection algorithm I'll start to write test cases for all of that

[issuesbot]

[comment from si...@haxe.org, published at 01/05/2013, 07:32:24] Well, you know my reservations about unify_call_params modifications and I don't want it to end up like type_access (word is you have to study it in a French mountain monastery for a year before you find enlightenment).

I wonder if we could find a better separation here, e.g. introduce a new function unify_field_call which can handle all the fancy overload stuff on platforms that need it and which calls a clean version of unify_call_params.

Other than that the patch looks fine to me, although I didn't check the Codegen part thoroughly. Is all this properly unit tested?

[issuesbot]

[comment from waneck, published at 01/05/2013, 13:40:02] hahaha. I can even hear a zen master telling me that "You don't change the code. You must let the code change you first"

Thank you for your comments, I've tried some times to find a better separation. Actually the first version of this had the selection algorithm completely separated from unify_call_params. But I had some problems coming from this:

• I had to get the expression types in order to be able to rate the functions. This meant I had to run type_expr once, with 'with_expr' as Value, which gave me type inferencing problems
• unify_call_params already receives the function arguments' type, which has its type constraints already added. So we can't modify a single place (unify_call_params), we'd have instead to modify every single call site of the function, which turn up to be a quite big change
• I had to replicate the arguments selection code. It's not so bad, but still, means that any change would have to be made to two places instead of one.

It seems to me that unify_call_params could really use some cleaning up. But this, in my point of view, would really involve a change to its signature, which we can maybe do after Haxe 3.0's release? I'll be happy to help.

I'm working on the unit tests right now. I'll attach a new diff with them added asap

[issuesbot]

[comment from waneck, published at 03/05/2013, 04:53:23] I'm attaching the overloads diff, with unit tests. When making the unit tests, I fixed some bugs on gencommon/gencs/genjava regarding overloads, type parameters and right overload selection. Also, I've realized that C# will always try to find a matching type that is declared in the current class. (see http://blogs.msdn.com/b/ericlippert/archive/2007/09/04/future-breaking-changes-part-three.aspx ). The parlay is good about it, but in practice, I think it's a little strange that you can't select a best match, even if it's overriden. So I've forced C# to choose what Haxe chooses from the algorithm discussed above.

Also, in making the tests, I've changed some things from last time:

• I've realized that if optional arguments are involved, we must first choose the function that has the least amount of unfilled (meaning that the user didn't explicitly use it) optional arguments. This is because a function that has optional arguments can always be explicitly chosen by padding their optionals with nulls; The opposite isn't true.
• Null<> types with coreType abstracts will have a slightly different behavior from their followed counterparts: They count as an extra implicit conversion when converting from their underlying types, and they count as one least implicit conversion when converting from Dynamic (e.g. if you pass a Dynamic, and there's a Null and a Int options, it will choose a Null; if you pass an Int, it will choose the Int overload)
• Abstracts are now handled correctly, since they can have more than one from/to depth
• Using won't have its behaviour altered by @ :overloads (unit tested)

As a side-note, for now this overload selection is running for all platforms, though I think the only other relevant platform it will influence is JS. I'll update this with an exhaustive test for all JQuery's API, and I think it would be a nice idea to have one central overload resolution algorithm. To be clear, I don't mean to support pf_overload on JS - overloads will still be declared with @ :overload(function() {}), but with our improved selection algorithm

Thank you!

[issuesbot]

[comment from si...@haxe.org, published at 03/05/2013, 07:38:53] If this is Google Patch Greenlight then I suppose you get my vote since you're fulfilling the unit test stipulations.

However, I'm not so sure about the "central overload resolution algorithm" idea. If we are talking externs we'd have to follow the rules (and quirks) of the target platforms.

[issuesbot]

[comment from waneck, published at 03/05/2013, 12:59:41] Thanks, Simon! Nicolas, does the patch look ok to you? Point taken about the central overload algorithm! For now, I will make sure it will follow the older algorithm.

However, as I see it, the only platform difference from JavaScript is that overloads aren't inherited (and in the current patch, this is already respected). Granted, JavaScript's type limitations will force the overloads to be much simpler - and so simpler that probably we won't ever have an ambiguous argument. In this way, the only argument I have, other than it would be a more unified approach to overload resolution, is that code like this would be supported:

@ :overload(function(a:Int,b:String):Float{}) @ :overload(function(a:String,b:Dynamic):{ a:String, b:Dynamic } {}) function weirdExample(a:Dynamic, b:Dynamic):Dynamic

{
    if (Std.is(a, Int) && Std.is(b, String))
    return a + Std.parseFloat(b);
    else if (Std.is(a, String))
    return { a: a, b:b };
    return null;
}

For now, using this function for typing would only result in the Dynamic->Dynamic->Dynamic being called.

I know at least one library that uses this kind of feature: https://github.com/jdonaldson/promhx/blob/049beed94b7151e4e3b78dd84d12c105204160ee/src/promhx/Promise.hx#L70 . Also, I think it would be nice to be able to have a reliable overload behaviour so it can be used e.g. for macro typing hacks (e.g. call Context.typeof with MyExternNonExistantClass.doOverload() to map a type) . I've got some still unreleased code that uses this kind of hack so it doesn't need to have its own typer, and still map a Haxe type to a macroe'd DSL-specific type

[issuesbot]

[comment from waneck, published at 03/05/2013, 13:27:40] s/hack/trick

[issuesbot]

[comment from ncanna...@gmail.com, published at 04/05/2013, 14:50:59] I had a quick look but couldn't fully review the patch since it's a Git patch while I use the Haxe SVN repo. Could you quickly post a SVN compatible .patch?

[issuesbot]

[comment from waneck, published at 04/05/2013, 17:57:37] Hi, sorry for taking so long to answer. I stumbled at Issue #1769 and was trying to track it down, thinking there was a problem with the patch. Can you try this diff? Thanks!

[issuesbot]

[comment from ncanna...@gmail.com, published at 05/05/2013, 07:42:43] Ok, the patch is good to apply. I just made some small changes in typer.ml (see attached diff)

[issuesbot]

[comment from waneck, published at 05/05/2013, 09:52:54] This issue was closed by revision 6bd0552f8553d312f55618461523d3db57db6ef8.

[issuesbot]

[comment from andy@onthewings.net, published at 06/05/2013, 01:13:33] I would like to know if there is any plan on supporting java/cs style @ :overload declaration in JS? It is useful for writing JS extern, which:

• each signature can has its own doc string
• able to attach meta data to individual signature (eg. @ :deprecated specific signature)

If there is no such plan, I will simulate it with macros.

[issuesbot]

[comment from si...@haxe.org, published at 06/05/2013, 09:58:28] What are the rules for optional arguments? Should this really not compile?

class Main {
    @:overload(function(s:String, i:Int = 1):Void {})
    static public function test() { }
    static public function main() {
        test("foo"); // Not enough arguments, Function 'test' requires arguments : s, i
    }
}