[WebAgentsAPI]: Split overload set functions into their own module.

third_party/WebKit/Source/bindings/scripts/v8_interface.py

Index: third_party/WebKit/Source/bindings/scripts/v8_interface.py
diff --git a/third_party/WebKit/Source/bindings/scripts/v8_interface.py b/third_party/WebKit/Source/bindings/scripts/v8_interface.py
index 2b66480acc6855cbde17c41731ad46e5cb3703d1..04863262089804a78817898eafeefa93c7f59e6d 100644
--- a/third_party/WebKit/Source/bindings/scripts/v8_interface.py
+++ b/third_party/WebKit/Source/bindings/scripts/v8_interface.py
@@ -33,13 +33,13 @@
 
 Design doc: http://www.chromium.org/developers/design-documents/idl-compiler
 """
-
-from collections import defaultdict
-import itertools
-from operator import itemgetter, or_
+from operator import or_
 
 from idl_definitions import IdlOperation, IdlArgument
 from idl_types import IdlType, inherits_interface
+from overload_set_algorithm import effective_overload_set_by_length
+from overload_set_algorithm import method_overloads_by_name
+
 import v8_attributes
 from v8_globals import includes
 import v8_methods
@@ -745,18 +745,6 @@ def compute_method_overloads_context_by_type(interface, methods):
         overloads[-1]['overloads']['name'] = name
 
 
-def method_overloads_by_name(methods):
-    """Returns generator of overloaded methods by name: [name, [method]]"""
-    # Filter to only methods that are actually overloaded
-    method_counts = Counter(method['name'] for method in methods)
-    overloaded_method_names = set(name
-                                  for name, count in method_counts.iteritems()
-                                  if count > 1)
-    overloaded_methods = [method for method in methods
-                          if method['name'] in overloaded_method_names]
-
-    # Group by name (generally will be defined together, but not necessarily)
-    return sort_and_groupby(overloaded_methods, itemgetter('name'))
 
 
 def overloads_context(interface, overloads):
@@ -878,104 +866,6 @@ def overloads_context(interface, overloads):
     }
 
 
-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.
-        # (“type list”)
-        t = tuple(argument['idl_type_object'] for argument in arguments)
-        # 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.
-        # (“optionality list”)
-        # (We’re just using a boolean for optional/variadic vs. required.)
-        o = tuple(argument['is_optional'] or argument['is_variadic']
-                  for argument in arguments)
-        # 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 effective_overload_set_by_length(overloads):
-    def type_list_length(entry):
-        # Entries in the effective overload set are 3-tuples:
-        # (callable, type list, optionality list)
-        return len(entry[1])
-
-    effective_overloads = effective_overload_set(overloads)
-    return list(sort_and_groupby(effective_overloads, type_list_length))
-
 
 def distinguishing_argument_index(entries):
     """Returns the distinguishing argument index for a sequence of entries.
@@ -1256,14 +1146,6 @@ def resolution_tests_methods(effective_overloads):
 # Utility functions
 ################################################################################
 
-def Counter(iterable):
-    # Once using Python 2.7, using collections.Counter
-    counter = defaultdict(lambda: 0)
-    for item in iterable:
-        counter[item] += 1
-    return counter
-
-
 def common(dicts, f):
     """Returns common result of f across an iterable of dicts, or None.
 
@@ -1294,12 +1176,6 @@ def common_value(dicts, key):
     return common(dicts, lambda d: d.get(key))
 
 
-def sort_and_groupby(l, key=None):
-    """Returns a generator of (key, list), sorting and grouping list by key."""
-    l.sort(key=key)
-    return ((k, list(g)) for k, g in itertools.groupby(l, key))
-
-
 ################################################################################
 # Constructors
 ################################################################################