Implement effective overload set algorithm

Implement effective overload set algorithm

To implement the overload resolution algorithm, I'm going to first
implement basic algorithms from the spec (*without* changing
generated code), then incrementally switch existing interfaces to
the proper algorithm (changing the generated code).

This implements the "effective overload set" algorithm:
http://heycam.github.io/webidl/#dfn-effective-overload-set

The code isn't very Pythonic, but it's directly from the spec.

Next will be 'distinguishing index'.

R=haraken
BUG=293561
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=173625

[Nils Barth (inactive), 2014-05-07 09:12:47]

First algorithm.

https://codereview.chromium.org/274503003/diff/1/Source/bindings/scripts/v8_i...
File Source/bindings/scripts/v8_interface.py (right):

https://codereview.chromium.org/274503003/diff/1/Source/bindings/scripts/v8_i...
Source/bindings/scripts/v8_interface.py:2: # coding=utf-8
This is so we can directly copy-paste text from the spec, without needing to
ASCIIify it.

[Jens Widell, 2014-05-07 11:37:26]

Non-owner LGMT.

Easy enough to read after just having read the corresponding section in the
specification, which of course is nice.

Out of curiosity: what is the plan regarding handling of variadic overloads?
Will you implement a "complete" overload mechanism first without it, and then
add that later?

[haraken, 2014-05-07 11:37:55]

Thanks for working on this! No one has succeeded in implementing (even
understanding) the overloaded algorithm.

LGTM.

[jsbell, 2014-05-07 16:51:19]

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
File Source/bindings/scripts/v8_interface.py (right):

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:368: E.g., f(optional long x) is listed
as f() and f(long), or more formally
Nit: can you rephrase this in the form of "An effective overload set is ...."
and "Given input ... this outputs ..." ?

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:369: (f, [], []) and (f, [long],
[optional]).
maybe write optional:boolean ?

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:376: An additional argument N (argument
count) is needed when overloading
I believe this is going to be the trickiest part of the spec to implement, since
N is determined at runtime not compile time.

I agree that the approach in this CL is a great direction to pursue. Long term a
very different approach may be needed (e.g. something crazy like implementing
bindings themselves in JS so the overload can be dynamic and JITted), but since
variadics are already custom bindings, this approach makes sense.

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:432: # 8. If n > 0 and all arguments of
X are optional, then add to S the
Is there a spec bug here?

If all arguments of X are optional then i == 0 in last iteration of the previous
loop, and <X, (), ()> will already have been added to the set.

[jsbell, 2014-05-07 17:07:15]

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
File Source/bindings/scripts/v8_interface.py (right):

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:432: # 8. If n > 0 and all arguments of
X are optional, then add to S the
On 2014/05/07 16:51:19, jsbell wrote:
> Is there a spec bug here?
> 
> If all arguments of X are optional then i == 0 in last iteration of the
previous
> loop, and <X, (), ()> will already have been added to the set.

Yeah, I filed https://www.w3.org/Bugs/Public/show_bug.cgi?id=25590

Step 7 in the spec should probably be i > 0.

[Nils Barth (inactive), 2014-05-08 05:29:54]

On 2014/05/07 11:37:26, Jens Lindström wrote:
> Out of curiosity: what is the plan regarding handling of variadic overloads?
> Will you implement a "complete" overload mechanism first without it, and then
> add that later?

Yup, that's the plan!

I'm implementing the Web IDL standard algorithm to cover all existing overloads;
this is necessary before we can start adding features, since it involves
completely
rewriting the overload resolution, and can't be done very incrementally.

Once that's done, then we can start adding features and removing custom bindings
for
existing overloads.

I've opened a bug for adding variadic overloads, as (per Joshua) that may be
quite involved, but can be done later.
IDL: overloading for variadic methods
https://code.google.com/p/chromium/issues/detail?id=371246

[Nils Barth (inactive), 2014-05-08 05:51:07]

Thanks, revised!

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
File Source/bindings/scripts/v8_interface.py (right):

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:368: E.g., f(optional long x) is listed
as f() and f(long), or more formally
On 2014/05/07 16:51:19, jsbell wrote:
> Nit: can you rephrase this in the form of "An effective overload set is ...."
> and "Given input ... this outputs ..." ?

Done: more formal, and fuller example.

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:369: (f, [], []) and (f, [long],
[optional]).
On 2014/05/07 16:51:19, jsbell wrote:
> maybe write optional:boolean ?

Clarified in prose, esp. since variadic makes this trickier.

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:376: An additional argument N (argument
count) is needed when overloading
On 2014/05/07 16:51:19, jsbell wrote:
> I believe this is going to be the trickiest part of the spec to implement,
since
> N is determined at runtime not compile time.
> 
> I agree that the approach in this CL is a great direction to pursue. Long term
a
> very different approach may be needed (e.g. something crazy like implementing
> bindings themselves in JS so the overload can be dynamic and JITted), but
since
> variadics are already custom bindings, this approach makes sense.

Got it, thanks!

As this is a substantial separate (followup) project, I've opened a bug for it:
IDL: overloading for variadic methods
https://code.google.com/p/chromium/issues/detail?id=371246

For now I'll implement to cover all existing cases, and once that is done, we
can add new features incrementally, removing custom bindings on the way.

(Hopefully won't need to do a revolutionary change, but may be necessary; should
be easier if we get Blink-in-JavaScript!)

https://codereview.chromium.org/274503003/diff/20001/Source/bindings/scripts/...
Source/bindings/scripts/v8_interface.py:432: # 8. If n > 0 and all arguments of
X are optional, then add to S the
On 2014/05/07 17:07:16, jsbell wrote:
> On 2014/05/07 16:51:19, jsbell wrote:
> > Is there a spec bug here?
> > 
> > If all arguments of X are optional then i == 0 in last iteration of the
> previous
> > loop, and <X, (), ()> will already have been added to the set.
> 
> Yeah, I filed https://www.w3.org/Bugs/Public/show_bug.cgi?id=25590
> 
> Step 7 in the spec should probably be i > 0.

Good catch, thanks!
We don't want *that* level of bug-for-bug conformance ;)
For now I've changed it to i > 0, as that seems the best resolution.

[Nils Barth (inactive), 2014-05-08 08:08:57]

The CQ bit was checked by nbarth@chromium.org

[commit-bot: I haz the power, 2014-05-08 08:09:37]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/nbarth@chromium.org/274503003/40001

[commit-bot: I haz the power, 2014-05-08 09:30:34]

Change committed as 173625