Implement effective overload set algorithm

Source/bindings/scripts/v8_interface.py

 # Copyright (C) 2013 Google Inc. All rights reserved.
+# coding=utf-8
 #
 # Redistribution and use in source and binary forms, with or without
 # modification, are permitted provided that the following conditions are
 # met:
 #
 #     * Redistributions of source code must retain the above copyright
 # notice, this list of conditions and the following disclaimer.
 #     * Redistributions in binary form must reproduce the above
 # copyright notice, this list of conditions and the following disclaimer
 # in the documentation and/or other materials provided with the
@@ skipping 317 matching lines @@
 
     # Group by name (generally will be defined together, but not necessarily)
     overloaded_methods.sort(key=itemgetter('name'))
     method_overloads = dict(
         (name, list(methods_iterator)) for name, methods_iterator in
         itertools.groupby(overloaded_methods, itemgetter('name')))
 
     # Add overload information only to overloaded methods, so template code can
     # easily verify if a function is overloaded
     for name, overloads in method_overloads.iteritems():
+        effective_overload_set(overloads)  # to test, compute but discard result
         for index, method in enumerate(overloads, 1):
             method.update({
                 'overload_index': index,
                 'overload_resolution_expression':
                     overload_resolution_expression(method),
             })
 
         # Resolution function is generated after last overloaded function;
         # package necessary information into |method.overloads| for that method.
         minimum_number_of_required_arguments = min(
             method['number_of_required_arguments'] for method in overloads)
         overloads[-1]['overloads'] = {
             'has_exception_state': bool(minimum_number_of_required_arguments),
             'methods': overloads,
             'minimum_number_of_required_arguments': minimum_number_of_required_arguments,
             'name': name,
             'measure_all_as': common_value(overloads, 'measure_as'),  # [MeasureAs]
             'deprecate_all_as': common_value(overloads, 'deprecate_as'),  # [DeprecateAs]
         }
 
 
+def effective_overload_set(F):
+    """Returns the effective overload set of an overloaded function.
+
+    An effective overload set is the set of overloaded functions + signatures
+    (type list of arguments, with optional and variadic arguments included or
+    not), and is used in the overload resolution algorithm.
+
+    For example, given input [f1(optional long x), f2(DOMString s)], the output
+    is informally [f1(), f1(long), f2(DOMString)], and formally
+    [(f1, [], []), (f1, [long], [optional]), (f2, [DOMString], [required])].
+
+    Currently the optionality list is a list of |is_optional| booleans (True
+    means optional, False means required); to support variadics this needs to
+    be tri-valued as required, optional, or variadic.
+
+    Formally:
+    An effective overload set represents the allowable invocations for a
+    particular operation, constructor (specified with [Constructor] or
+    [NamedConstructor]), legacy caller or callback function.
+
+    An additional argument N (argument count) is needed when overloading
+    variadics, but we don't use that currently.
+
+    Spec: http://heycam.github.io/webidl/#dfn-effective-overload-set
+
+    Formally the input and output lists are sets, but methods are stored
+    internally as dicts, which can't be stored in a set because they are not
+    hashable, so we use lists instead.
+
+    Arguments:
+        F: list of overloads for a given callable name.
+
+    Returns:
+        S: list of tuples of the form <callable, type list, optionality list>.
+    """
+    # Code closely follows the algorithm in the spec, for clarity and
+    # correctness, and hence is not very Pythonic.
+
+    # 1. Initialize S to ∅.
+    # (We use a list because we can't use a set, as noted above.)
+    S = []
+
+    # 2. Let F be a set with elements as follows, according to the kind of
+    # effective overload set:
+    # (Passed as argument, nothing to do.)
+
+    # 3. & 4. (maxarg, m) are only needed for variadics, not used.
+
+    # 5. For each operation, extended attribute or callback function X in F:
+    for X in F:  # X is the "callable", F is the overloads.
+        arguments = X['arguments']
+        # 1. Let n be the number of arguments X is declared to take.
+        n = len(arguments)
+        # 2. Let t0..n−1 be a list of types, where ti is the type of X’s
+        # argument at index i.
+        t = [argument['idl_type'] for argument in arguments]  # type list
+        # 3. Let o0..n−1 be a list of optionality values, where oi is “variadic”
+        # if X’s argument at index i is a final, variadic argument, “optional”
+        # if the argument is optional, and “required” otherwise.
+        # (We're just using a boolean for optional vs. required.)
+        o = [argument['is_optional'] for argument in arguments]  # optionality list
+        # 4. Add to S the tuple <X, t0..n−1, o0..n−1>.
+        S.append((X, t, o))
+        # 5. If X is declared to be variadic, then:
+        # (Not used, so not implemented.)
+        # 6. Initialize i to n−1.
+        i = n - 1
+        # 7. While i ≥ 0:
+        # Spec bug (fencepost error); should be “While i > 0:”
+        # https://www.w3.org/Bugs/Public/show_bug.cgi?id=25590
+        while i > 0:
+            # 1. If argument i of X is not optional, then break this loop.
+            if not o[i]:
+                break
+            # 2. Otherwise, add to S the tuple <X, t0..i−1, o0..i−1>.
+            S.append((X, t[:i], o[:i]))
+            # 3. Set i to i−1.
+            i = i - 1
+        # 8. If n > 0 and all arguments of X are optional, then add to S the
+        # tuple <X, (), ()> (where “()” represents the empty list).
+        if n > 0 and all(oi for oi in o):
+            S.append((X, [], []))
+    # 6. The effective overload set is S.
+    return S
+
+
 def overload_resolution_expression(method):
     # Expression is an OR of ANDs: each term in the OR corresponds to a
     # possible argument count for a given method, with type checks.
     # FIXME: Blink's overload resolution algorithm is incorrect, per:
     # Implement WebIDL overload resolution algorithm.  http://crbug.com/293561
     #
     # Currently if distinguishing non-primitive type from primitive type,
     # (e.g., sequence<DOMString> from DOMString or Dictionary from double)
     # the method with a non-primitive type argument must appear *first* in the
     # IDL file, since we're not adding a check to primitive types.
@@ skipping 367 matching lines @@
         deleter = next(
             method
             for method in interface.operations
             if ('deleter' in method.specials and
                 len(method.arguments) == 1 and
                 str(method.arguments[0].idl_type) == 'DOMString'))
     except StopIteration:
         return None
 
     return property_deleter(deleter)