C++ overload resolution in bindings layer

Source/bindings/dart/scripts/dart_interface.py

Index: Source/bindings/dart/scripts/dart_interface.py
diff --git a/Source/bindings/dart/scripts/dart_interface.py b/Source/bindings/dart/scripts/dart_interface.py
index ba0e721bcc103c49a1a60f43b7b58025edf6dc35..bac92a95a4cbae64187c7a7aceba0f577ab39dc6 100644
--- a/Source/bindings/dart/scripts/dart_interface.py
+++ b/Source/bindings/dart/scripts/dart_interface.py
@@ -1,4 +1,5 @@
 # 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
@@ -32,6 +33,8 @@ Design doc: http://www.chromium.org/developers/design-documents/idl-compiler
 """
 
 from collections import defaultdict
+import itertools
+from operator import itemgetter
 
 import idl_types
 from idl_types import IdlType, inherits_interface, IdlArrayOrSequenceType, IdlArrayType
@@ -397,21 +400,6 @@ def _suppress_extended_attributes(extended_attributes):
     return False
 
 
-def add_native_entries(interface, constructors, is_custom):
-    for constructor in constructors:
-        types = None
-        if not is_custom:
-            types = [arg['preprocessed_type']
-                     for arg in constructor['arguments']]
-        argument_names = [arg['name'] for arg in constructor['arguments']]
-        native_entry = \
-            DartUtilities.generate_native_entry(interface.name, constructor,
-                                                None, 'Constructor', None,
-                                                argument_names, types)
-        constructor.update({'native_entry': native_entry})
-
-
-# TODO(terry): Rename generate_interface - interface_context
 def generate_interface(interface):
     includes.clear()
     includes.update(INTERFACE_CPP_INCLUDES)
@@ -539,7 +527,8 @@ def generate_interface(interface):
                     # (currently needed for Perl compatibility)
                     # Handle named constructors separately
                     if constructor.name == 'Constructor']
-    generate_constructor_overloads(constructors)
+    if len(constructors) > 1:
+        template_contents['constructor_overloads'] = overloads_context(constructors)
 
     # [CustomConstructor]
     custom_constructors = [generate_custom_constructor(interface, constructor)
@@ -624,7 +613,7 @@ def generate_interface(interface):
                    not _suppress_method(interface.name, method.name) and
                    not _suppress_extended_attributes(method.extended_attributes) and
                    not 'DartSuppress' in method.extended_attributes)]
-    generate_overloads(methods)
+    compute_method_overloads_context(methods)
     for method in methods:
         method['do_generate_method_configuration'] = (
             method['do_not_check_signature'] and
@@ -699,23 +688,12 @@ def generate_constant(constant):
     }
 
 
-################################################################################
-# Overloads
-################################################################################
-
-def generate_method_native_entry(interface, method, count, optional_index, kind):
-    types = None
-    if not method['is_custom']:
-        types = [arg['preprocessed_type'] for arg in method['arguments'][0:count]]
-    if method['is_call_with_script_arguments']:
-        types.append("object")
+def generate_method_native_entry(interface, method, count, kind):
     argument_names = [arg['name'] for arg in method['arguments'][0:count]]
     name = method.get('name')
     native_entry = \
         DartUtilities.generate_native_entry(interface.name, method,
-                                            name, kind,
-                                            optional_index,
-                                            argument_names, types)
+                                            name, kind, argument_names)
     return native_entry
 
 
@@ -724,178 +702,505 @@ def generate_method_native_entries(interface, methods, kind):
         native_entries = []
         required_arg_count = method['number_of_required_arguments']
         arg_count = method['number_of_arguments']
-        if required_arg_count != arg_count:
-            for x in range(required_arg_count, arg_count + 1):
-                # This is really silly, but is here for now just to match up
-                # the existing name generation in the old dart:html scripts
-                index = arg_count - x + 1
-                native_entry = \
-                    generate_method_native_entry(interface, method, x, index, kind)
-                native_entries.append(native_entry)
-        else:
-            # Eventually, we should probably always generate an unindexed
-            # native entry, to handle cases like
-            # addEventListener in which we suppress the optionality,
-            # and in general to make us more robust against optional changes
+        for x in range(required_arg_count, arg_count + 1):
             native_entry = \
-                generate_method_native_entry(interface, method, arg_count, None, kind)
+                generate_method_native_entry(interface, method, x, kind)
             native_entries.append(native_entry)
 
         method.update({'native_entries': native_entries})
 
-def generate_overloads(methods):
-    generate_overloads_by_type(methods, is_static=False)  # Regular methods
-    generate_overloads_by_type(methods, is_static=True)
 
+################################################################################
+# Overloads
+################################################################################
+
+def compute_method_overloads_context(methods):

[terry, 2014/10/21 21:26:11]

methods => method_contexts ?

We use method(s) as both context(s) and method(s) which seems confusing.  I've
tried to change other mechanisms to context when context is used and vice versa.
 I can also do that after this checkin when I cleanup dart_interface w/
v8_interface.

[Leaf, 2014/10/22 16:31:19]

Kind of trying to minimize text changes vs v8 to make porting changes easier,
but don't mind if we want to change this.

On 2014/10/21 21:26:11, terry wrote:

+    # Regular methods
+    compute_method_overloads_context_by_type([method for method in methods
+                                              if not method['is_static']])
+    # Static methods
+    compute_method_overloads_context_by_type([method for method in methods
+                                              if method['is_static']])
 
-def generate_overloads_by_type(methods, is_static):
-    # Generates |overloads| template values and modifies |methods| in place;
-    # |is_static| flag used (instead of partitioning list in 2) because need to
-    # iterate over original list of methods to modify in place
-    method_counts = defaultdict(lambda: 0)
-    for method in methods:
-        if method['is_static'] != is_static:
-            continue
-        name = method['name']
-        # FIXME(vsm): We don't seem to capture optional param
-        # overloads here.
-        method_counts[name] += 1
 
-    # Filter to only methods that are actually overloaded
-    overloaded_method_counts = dict((name, count)
-                                    for name, count in method_counts.iteritems()
-                                    if count > 1)
+def compute_method_overloads_context_by_type(methods):
+    """Computes |method.overload*| template values.
 
+    Called separately for static and non-static (regular) methods,
+    as these are overloaded separately.
+    Modifies |method| in place for |method| in |methods|.
+    Doesn't change the |methods| list itself (only the values, i.e. individual
+    methods), so ok to treat these separately.
+    """
     # Add overload information only to overloaded methods, so template code can
     # easily verify if a function is overloaded
-    method_overloads = defaultdict(list)
-    for method in methods:
-        name = method['name']
-        if (method['is_static'] != is_static or
-            name not in overloaded_method_counts):
-            continue
-        # Overload index includes self, so first append, then compute index
-        method_overloads[name].append(method)
-        method.update({
-            'overload_index': len(method_overloads[name]),
-            'overload_resolution_expression': overload_resolution_expression(method),
-        })
-        # FIXME(vsm): Looks like we only handle optional parameters if
-        # the method is already overloaded. For a non-overloaded method
-        # with optional parameters, we never get here.
-
-    # Resolution function is generated after last overloaded function;
-    # package necessary information into |method.overloads| for that method.
-    for method in methods:
-        if (method['is_static'] != is_static or
-            'overload_index' not in method):
-            continue
-        name = method['name']
-        if method['overload_index'] != overloaded_method_counts[name]:
-            continue
-        overloads = method_overloads[name]
-        minimum_number_of_required_arguments = min(
-            overload['number_of_required_arguments']
-            for overload in overloads)
-        method['overloads'] = {
-            'has_exception_state': bool(minimum_number_of_required_arguments),
-            'methods': overloads,
-            'minimum_number_of_required_arguments': minimum_number_of_required_arguments,
-            'name': name,
-        }
+    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(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(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):
+        method['overload_index'] = index
+
+    effective_overloads_by_length = effective_overload_set_by_length(overloads)
+    lengths = [length for length, _ in effective_overloads_by_length]
+    name = overloads[0].get('name', '<constructor>')
+
+    # Check and fail if all overloads with the shortest acceptable arguments
+    # list are runtime enabled, since we would otherwise set 'length' on the
+    # function object to an incorrect value when none of those overloads were
+    # actually enabled at runtime. The exception is if all overloads are
+    # controlled by the same runtime enabled feature, in which case there would
+    # be no function object at all if it is not enabled.
+    shortest_overloads = effective_overloads_by_length[0][1]
+    if (all(method.get('runtime_enabled_function')
+            for method, _, _ in shortest_overloads) and
+        not common_value(overloads, 'runtime_enabled_function')):
+        raise ValueError('Function.length of %s depends on runtime enabled features' % name)
+
+    return {
+        'deprecate_all_as': common_value(overloads, 'deprecate_as'),  # [DeprecateAs]
+        'exposed_test_all': common_value(overloads, 'exposed_test'),  # [Exposed]
+        'length_tests_methods': length_tests_methods(effective_overloads_by_length),
+        # 1. Let maxarg be the length of the longest type list of the
+        # entries in S.
+        'maxarg': lengths[-1],
+        'measure_all_as': common_value(overloads, 'measure_as'),  # [MeasureAs]
+        'minarg': lengths[0],
+        'per_context_enabled_function_all': common_value(overloads, 'per_context_enabled_function'),  # [PerContextEnabled]
+        'runtime_enabled_function_all': common_value(overloads, 'runtime_enabled_function'),  # [RuntimeEnabled]
+        '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,
+    }
 
-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.
-    # https://code.google.com/p/chromium/issues/detail?id=293561
+
+def effective_overload_set(F):

[terry, 2014/10/21 21:26:12]

F or f, used f for function in below methods.

[Leaf, 2014/10/22 16:31:19]

I think the odd capitalization and typography in this method are intended to
follow the Web IDL overload resolution text as closely as possible: 
http://heycam.github.io/webidl/#dfn-effective-overload-set .

On 2014/10/21 21:26:12, terry wrote:

+    """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 = []

[terry, 2014/10/21 21:26:12]

capitalized? as well as others

+
+    # 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 vs. required.)
+        o = tuple(argument['is_optional'] 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
+
+    If there is more than one entry in an effective overload set that has a
+    given type list length, then for those entries there must be an index i
+    such that for each pair of entries the types at index i are
+    distinguishable.
+    The lowest such index is termed the distinguishing argument index for the
+    entries of the effective overload set with the given type list length.
+    """
+    # Only applicable “If there is more than one entry”
+    assert len(entries) > 1
+    type_lists = [tuple(idl_type.name for idl_type in entry[1])
+                  for entry in entries]
+    type_list_length = len(type_lists[0])
+    # Only applicable for entries that “[have] a given type list length”
+    assert all(len(type_list) == type_list_length for type_list in type_lists)
+    name = entries[0][0].get('name', 'Constructor')  # for error reporting
+
+    # The spec defines the distinguishing argument index by conditions it must
+    # satisfy, but does not give an algorithm.
     #
-    # 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.
-    # FIXME: Once fixed, check IDLs, as usually want methods with primitive
-    # types to appear first (style-wise).
+    # We compute the distinguishing argument index by first computing the
+    # minimum index where not all types are the same, and then checking that
+    # all types in this position are distinguishable (and the optionality lists
+    # up to this point are identical), since "minimum index where not all types
+    # are the same" is a *necessary* condition, and more direct to check than
+    # distinguishability.
+    types_by_index = (set(types) for types in zip(*type_lists))
+    try:
+        # “In addition, for each index j, where j is less than the
+        #  distinguishing argument index for a given type list length, the types
+        #  at index j in all of the entries’ type lists must be the same”
+        index = next(i for i, types in enumerate(types_by_index)
+                     if len(types) > 1)
+    except StopIteration:
+        raise ValueError('No distinguishing index found for %s, length %s:\n'
+                         'All entries have the same type list:\n'
+                         '%s' % (name, type_list_length, type_lists[0]))
+    # Check optionality
+    # “and the booleans in the corresponding list indicating argument
+    #  optionality must be the same.”
+    # FIXME: spec typo: optionality value is no longer a boolean
+    # https://www.w3.org/Bugs/Public/show_bug.cgi?id=25628
+    initial_optionality_lists = set(entry[2][:index] for entry in entries)
+    if len(initial_optionality_lists) > 1:
+        raise ValueError(
+            'Invalid optionality lists for %s, length %s:\n'
+            'Optionality lists differ below distinguishing argument index %s:\n'
+            '%s'
+            % (name, type_list_length, index, set(initial_optionality_lists)))
+
+    # Check distinguishability
+    # http://heycam.github.io/webidl/#dfn-distinguishable
+    # Use names to check for distinct types, since objects are distinct
+    # FIXME: check distinguishability more precisely, for validation
+    distinguishing_argument_type_names = [type_list[index]
+                                          for type_list in type_lists]
+    if (len(set(distinguishing_argument_type_names)) !=
+        len(distinguishing_argument_type_names)):
+        raise ValueError('Types in distinguishing argument are not distinct:\n'
+                         '%s' % distinguishing_argument_type_names)
+
+    return index
+
+
+def length_tests_methods(effective_overloads_by_length):
+    """Returns sorted list of resolution tests and associated methods, by length.
+
+    This builds the main data structure for the overload resolution loop.
+    For a given argument length, bindings test argument at distinguishing
+    argument index, in order given by spec: if it is compatible with
+    (optionality or) type required by an overloaded method, resolve to that
+    method.
+
+    Returns:
+        [(length, [(test, method)])]
+    """
+    return [(length, list(resolution_tests_methods(effective_overloads)))
+            for length, effective_overloads in effective_overloads_by_length]
+
+
+DART_CHECK_TYPE = {
+    'ArrayBufferView': 'Dart_IsTypedData({cpp_value})',
+    'ArrayBuffer': 'Dart_IsByteBuffer({cpp_value})',
+    'Uint8Array': 'DartUtilities::isUint8Array({cpp_value})',
+    'Uint8ClampedArray': 'DartUtilities::isUint8ClampedArray({cpp_value})',
+}
+
+
+def resolution_tests_methods(effective_overloads):
+    """Yields resolution test and associated method, in resolution order, for effective overloads of a given length.

[terry, 2014/10/21 21:26:11]

linebreak?

+
+    This is the heart of the resolution algorithm.
+    http://heycam.github.io/webidl/#dfn-overload-resolution-algorithm
+
+    Note that a given method can be listed multiple times, with different tests!
+    This is to handle implicit type conversion.
+
+    Returns:
+        [(test, method)]
+    """
+    methods = [effective_overload[0]
+               for effective_overload in effective_overloads]
+    if len(methods) == 1:
+        # If only one method with a given length, no test needed
+        yield 'true', methods[0]
+        return
+
+    # 6. If there is more than one entry in S, then set d to be the
+    # distinguishing argument index for the entries of S.
+    index = distinguishing_argument_index(effective_overloads)
+    # (7-9 are for handling |undefined| values for optional arguments before
+    # the distinguishing argument (as “missing”), so you can specify only some
+    # optional arguments. We don’t support this, so we skip these steps.)
+    # 10. If i = d, then:
+    # (d is the distinguishing argument index)
+    # 1. Let V be argi.
+    #     Note: This is the argument that will be used to resolve which
+    #           overload is selected.
+    cpp_value = 'Dart_GetNativeArgument(args, %s + argOffset)' % index
+
+    # Extract argument and IDL type to simplify accessing these in each loop.
+    arguments = [method['arguments'][index] for method in methods]
+    arguments_methods = zip(arguments, methods)
+    idl_types = [argument['idl_type_object'] for argument in arguments]
+    idl_types_methods = zip(idl_types, methods)
+
+    # We can’t do a single loop through all methods or simply sort them, because
+    # a method may be listed in multiple steps of the resolution algorithm, and
+    # which test to apply differs depending on the step.
     #
-    # Properly:
-    # 1. Compute effective overload set.
-    # 2. First check type list length.
-    # 3. If multiple entries for given length, compute distinguishing argument
-    #    index and have check for that type.
-    arguments = method['arguments']
-    overload_checks = [overload_check_expression(method, index)
-                       # check *omitting* optional arguments at |index| and up:
-                       # index 0 => argument_count 0 (no arguments)
-                       # index 1 => argument_count 1 (index 0 argument only)
-                       for index, argument in enumerate(arguments)
-                       if argument['is_optional']]
-    # FIXME: this is wrong if a method has optional arguments and a variadic
-    # one, though there are not yet any examples of this
-    if not method['is_variadic']:
-        # Includes all optional arguments (len = last index + 1)
-        overload_checks.append(overload_check_expression(method, len(arguments)))
-    return ' || '.join('(%s)' % check for check in overload_checks)
-
-
-def overload_check_expression(method, argument_count):
-    overload_checks = ['info.Length() == %s' % argument_count]
-    arguments = method['arguments'][:argument_count]
-    overload_checks.extend(overload_check_argument(index, argument)
-                           for index, argument in
-                           enumerate(arguments))
-    return ' && '.join('(%s)' % check for check in overload_checks if check)
-
-
-def overload_check_argument(index, argument):
-    def null_or_optional_check():
-        # If undefined is passed for an optional argument, the argument should
-        # be treated as missing; otherwise undefined is not allowed.
-
-        # FIXME(vsm): We need Dart specific checks here.
-        if idl_type.is_nullable:
-            if argument['is_optional']:
-                return 'isUndefinedOrNull(%s)'
-            return '%s->IsNull()'
-        if argument['is_optional']:
-            return '%s->IsUndefined()'
-        return None
+    # Instead, we need to go through all methods at each step, either finding
+    # first match (if only one test is allowed) or filtering to matches (if
+    # multiple tests are allowed), and generating an appropriate tests.
 
-    cpp_value = 'info[%s]' % index
-    idl_type = argument['idl_type_object']
-    # FIXME(vsm): We need Dart specific checks for the rest of this method.
-    # FIXME: proper type checking, sharing code with attributes and methods
-    # FIXME(terry): DartStrictTypeChecking no longer supported; TypeChecking is
-    #               new extended attribute.
-    if idl_type.name == 'String' and argument['is_strict_type_checking']:
-        return ' || '.join(['isUndefinedOrNull(%s)' % cpp_value,
-                            '%s->IsString()' % cpp_value,
-                            '%s->IsObject()' % cpp_value])
-    if idl_type.native_array_element_type:
-        return '%s->IsArray()' % cpp_value
-    if idl_type.is_callback_interface:
-        return ' || '.join(['%s->IsNull()' % cpp_value,
-                            '%s->IsFunction()' % cpp_value])
-    if idl_type.is_wrapper_type:
-        type_check = 'V8{idl_type}::hasInstance({cpp_value}, info.GetIsolate())'.format(idl_type=idl_type.base_type, cpp_value=cpp_value)
-        if idl_type.is_nullable:
-            type_check = ' || '.join(['%s->IsNull()' % cpp_value, type_check])
-        return type_check
-    if idl_type.is_interface_type:
-        # Non-wrapper types are just objects: we don't distinguish type
-        # We only allow undefined for non-wrapper types (notably Dictionary),
-        # as we need it for optional Dictionary arguments, but we don't want to
-        # change behavior of existing bindings for other types.
-        type_check = '%s->IsObject()' % cpp_value
-        added_check_template = null_or_optional_check()
-        if added_check_template:
-            type_check = ' || '.join([added_check_template % cpp_value,
-                                      type_check])
-        return type_check
+    # 2. If V is undefined, and there is an entry in S whose list of
+    # optionality values has “optional” at index i, then remove from S all
+    # other entries.
+    try:
+        method = next(method for argument, method in arguments_methods
+                      if argument['is_optional'])
+        test = 'Dart_IsNull(%s)' % cpp_value
+        yield test, method
+    except StopIteration:
+        pass
+
+    # 3. Otherwise: if V is null or undefined, and there is an entry in S that
+    # has one of the following types at position i of its type list,
+    # • a nullable type
+    try:
+        method = next(method for idl_type, method in idl_types_methods
+                      if idl_type.is_nullable)
+        test = 'Dart_IsNull(%s)' % cpp_value
+        yield test, method
+    except StopIteration:
+        pass
+
+    # 4. Otherwise: if V is a platform object – but not a platform array
+    # object – and there is an entry in S that has one of the following
+    # types at position i of its type list,
+    # • an interface type that V implements
+    # (Unlike most of these tests, this can return multiple methods, since we
+    #  test if it implements an interface. Thus we need a for loop, not a next.)
+    # (We distinguish wrapper types from built-in interface types.)
+    for idl_type, method in ((idl_type, method)
+                             for idl_type, method in idl_types_methods
+                             if idl_type.is_wrapper_type):
+        fmtstr = 'Dart{idl_type}::hasInstance({cpp_value})'
+        if idl_type.base_type in DART_CHECK_TYPE:
+            fmtstr = DART_CHECK_TYPE[idl_type.base_type]
+        test = fmtstr.format(idl_type=idl_type.base_type, cpp_value=cpp_value)
+        yield test, method
+
+    # 8. Otherwise: if V is any kind of object except for a native Date object,
+    # a native RegExp object, and there is an entry in S that has one of the
+    # following types at position i of its type list,
+    # • an array type
+    # • a sequence type
+    # ...
+    # • a dictionary
+    try:
+        # FIXME: IDL dictionary not implemented, so use Blink Dictionary
+        # http://crbug.com/321462
+        idl_type, method = next((idl_type, method)
+                                for idl_type, method in idl_types_methods
+                                if (idl_type.native_array_element_type or
+                                    idl_type.name == 'Dictionary'))
+        if idl_type.native_array_element_type:
+            # (We test for Array instead of generic Object to type-check.)
+            # FIXME: test for Object during resolution, then have type check for
+            # Array in overloaded method: http://crbug.com/262383
+            test = 'Dart_IsList(%s)' % cpp_value
+        else:
+            # FIXME: should be '{1}->IsObject() && !{1}->IsDate() && !{1}->IsRegExp()'.format(cpp_value)
+            # FIXME: the IsDate and IsRegExp checks can be skipped if we've
+            # already generated tests for them.
+            test = 'Dart_IsInstance(%s)' % cpp_value
+        yield test, method
+    except StopIteration:
+        pass
+
+    # (Check for exact type matches before performing automatic type conversion;
+    # only needed if distinguishing between primitive types.)
+    if len([idl_type.is_primitive_type for idl_type in idl_types]) > 1:
+        # (Only needed if match in step 11, otherwise redundant.)
+        if any(idl_type.is_string_type or idl_type.is_enum
+               for idl_type in idl_types):
+            # 10. Otherwise: if V is a Number value, and there is an entry in S
+            # that has one of the following types at position i of its type
+            # list,
+            # • a numeric type
+            try:
+                method = next(method for idl_type, method in idl_types_methods
+                              if idl_type.is_numeric_type)
+                test = 'Dart_IsNumber(%s)' % cpp_value
+                yield test, method
+            except StopIteration:
+                pass
+
+    # (Perform automatic type conversion, in order. If any of these match,
+    # that’s the end, and no other tests are needed.) To keep this code simple,
+    # we rely on the C++ compiler's dead code elimination to deal with the
+    # redundancy if both cases below trigger.
+
+    # 11. Otherwise: if there is an entry in S that has one of the following
+    # types at position i of its type list,
+    # • DOMString
+    # • ByteString
+    # • ScalarValueString [a DOMString typedef, per definition.]
+    # • an enumeration type
+    try:
+        method = next(method for idl_type, method in idl_types_methods
+                      if idl_type.is_string_type or idl_type.is_enum)
+        yield 'true', method
+    except StopIteration:
+        pass
+
+    # 12. Otherwise: if there is an entry in S that has one of the following
+    # types at position i of its type list,
+    # • a numeric type
+    try:
+        method = next(method for idl_type, method in idl_types_methods
+                      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
 
 
+def common_key(dicts, key):
+    """Returns common presence of a key across an iterable of dicts, or None.
+
+    True if all dicts have the key, False if none of the dicts have the key,
+    and None if some but not all dicts have the key.
+    """
+    return common(dicts, lambda d: key in d)
+
+
+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
 ################################################################################
@@ -950,17 +1255,6 @@ def generate_constructor(interface, constructor):
     }
 
 
-def generate_constructor_overloads(constructors):
-    if len(constructors) <= 1:
-        return
-    for overload_index, constructor in enumerate(constructors):
-        constructor.update({
-            'overload_index': overload_index + 1,
-            'overload_resolution_expression':
-                overload_resolution_expression(constructor),
-        })
-
-
 # [NamedConstructor]
 def generate_named_constructor(interface):
     extended_attributes = interface.extended_attributes