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

third_party/WebKit/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
@@ skipping 15 matching lines @@
 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 # pylint: disable=relative-import
 
 """Generate template values for an interface.
 
 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
 import v8_types
 import v8_utilities
 from v8_utilities import (cpp_name_or_partial, cpp_name, has_extended_attribute_value,
                           runtime_enabled_feature_name, is_legacy_interface_type_checking)
 
 
 INTERFACE_H_INCLUDES = frozenset([
@@ skipping 685 matching lines @@
     """
     # Add overload information only to overloaded methods, so template code can
     # easily verify if a function is overloaded
     for name, overloads in method_overloads_by_name(methods):
         # Resolution function is generated after last overloaded function;
         # package necessary information into |method.overloads| for that method.
         overloads[-1]['overloads'] = overloads_context(interface, overloads)
         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):
     """Returns |overloads| template values for a single name.
 
     Sets |method.overload_index| in place for |method| in |overloads|
     and returns dict of overall overload template values.
     """
     assert len(overloads) > 1  # only apply to overloaded names
     for index, method in enumerate(overloads, 1):
@@ skipping 101 matching lines @@
         'valid_arities': (lengths
                           # Only need to report valid arities if there is a gap in the
                           # sequence of possible lengths, otherwise invalid length means
                           # "not enough arguments".
                           if lengths[-1] - lengths[0] != len(lengths) - 1 else None),
         'visible': has_overload_visible,
         'has_partial_overloads': has_partial_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.
 
     Entries are elements of the effective overload set with the same number
     of arguments (formally, same type list length), each a 3-tuple of the form
     (callable, type list, optionality list).
 
     Spec: http://heycam.github.io/webidl/#dfn-distinguishing-argument-index
 
@@ skipping 260 matching lines @@
                       if idl_type.is_numeric_type)
         yield 'true', method
     except StopIteration:
         pass
 
 
 ################################################################################
 # 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.
 
     Call f for each dict and return its result if the same across all dicts.
     """
     values = (f(d) for d in dicts)
     first_value = next(values)
     if all(value == first_value for value in values):
         return first_value
     return None
@@ skipping 10 matching lines @@
 
 def common_value(dicts, key):
     """Returns common value of a key across an iterable of dicts, or None.
 
     Auxiliary function for overloads, so can consolidate an extended attribute
     that appears with the same value on all items in an overload set.
     """
     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
 ################################################################################
 
 # [Constructor]
 def constructor_context(interface, constructor):
     # [RaisesException=Constructor]
     is_constructor_raises_exception = \
         interface.extended_attributes.get('RaisesException') == 'Constructor'
 
@@ skipping 171 matching lines @@
     extended_attributes = deleter.extended_attributes
     is_call_with_script_state = v8_utilities.has_extended_attribute_value(deleter, 'CallWith', 'ScriptState')
     is_ce_reactions = 'CEReactions' in extended_attributes
     return {
         'is_call_with_script_state': is_call_with_script_state,
         'is_ce_reactions': is_ce_reactions,
         'is_custom': 'Custom' in extended_attributes,
         'is_raises_exception': 'RaisesException' in extended_attributes,
         'name': cpp_name(deleter),
     }