# Copyright 2017 The Chromium Authors. All rights reserved.
# coding=utf-8
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

from collections import Counter
import itertools
from operator import itemgetter


def sort_and_groupby(list_to_sort, key=None):
    """Returns a generator of (key, list), sorting and grouping list by key."""
    list_to_sort.sort(key=key)
    return ((k, list(g)) for k, g in itertools.groupby(list_to_sort, key))


def effective_overload_set(F):  # pylint: disable=invalid-name
    """Returns the effective overload set of an overloaded function.

    An effective overload set is the set of overloaded functions + signatures
    derived from the set F by transforming it into the distinct permutations of
    function invocations possible given the argument types. It is used by the
    overload resolution algorithm.

    For example, given input:
    [
        f1(DOMString a),
        f2(Node a, DOMString b, double... c),
        f3(),
        f4(Event a, DOMString b, optional DOMString c, double... d)
    ]

    The output is:
    [
        (f1, [DOMString], [required]),
        (f2, [Node, DOMString], [required, required]),
        (f2, [Node, DOMString, double], [required, required, variadic]),
        (f2, [Node, DOMString, double, double], [required, required, variadic, variadic]),
        (f3, [], []),
        (f4, [Event, DOMString], [required, required],
        (f4, [Event, DOMString, DOMString], [required, required, optional]),
        (f4, [Event, DOMString, DOMString, double], [required, required, optional, variadic])
    ]

    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, tuple(type list), tuple(optionality list)).
    """
    # Code closely follows the algorithm in the spec, for clarity and
    # correctness, and hence is not very Pythonic.

    # 1. Let S be an ordered set.
    # (We use a list because we can't use a set, as noted above.)
    S = []  # pylint: disable=invalid-name

    # 2. Let F be an ordered set with items as follows, according to the kind of
    # effective overload set:
    # (Passed as argument, nothing to do.)

    # 3. Let maxarg be the maximum number of arguments the operations,
    # constructor extended attributes or callback functions in F are declared
    # to take. For variadic operations and constructor extended attributes,
    # the argument on which the ellipsis appears counts as a single argument.
    # Note: So void f(long x, long... y); is considered to be declared to take
    # two arguments.
    # X is the "callable".
    maxarg = max([len(X['arguments']) for X in F])

    # 4. Let max be max(maxarg, N).
    # Per: https://github.com/heycam/webidl/issues/600.

    # The effective overload set as defined in the Web IDL spec is used at
    # runtime as an input to the overload resolution algorithm. The runtime
    # portion of the overload resolution algorithm includes coercing arguments
    # into the proper type. To perform that coercion, the effective overload set
    # must produce variadic entries in the type list to match the number of
    # arguments supplied for the invocation (N) of the function.

    # Our use of the effective overload set, however, is limited to determining
    # which function overload should handle the invocation. Coercion of
    # arguments is a separate problem making N irrelevant and max always equal
    # to maxarg.

    # 5. For each operation, extended attribute or callback function X in F:
    for X in F:  # pylint: disable=invalid-name
        # 5.1. Let arguments be the list of arguments X is declared to take.
        arguments = X['arguments']  # pylint: disable=invalid-name
        # 5.2. Let n be the size of arguments.
        n = len(arguments)  # pylint: disable=invalid-name
        # 5.3. Let types be a type list.
        # 5.4. Let optionalityValues be an optionality list.
        types, optionality_values = [], []

        # 5.5. For each argument in arguments:
        for argument in arguments:
            # 5.5.1. Append the type of argument to types.
            types.append(argument['idl_type_object'])
            # 5.5.2. Append "variadic" to optionalityValues if argument is a
            # final, variadic argument, "optional" if argument is optional,
            # and "required" otherwise.
            if argument['is_variadic']:
                optionality_values.append('variadic')
            elif argument['is_optional']:
                optionality_values.append('optional')
            else:
                optionality_values.append('required')

        # 5.6. Append the tuple (X, types, optionalityValues) to S.
        S.append((X, tuple(types), tuple(optionality_values)))

        # 5.7. If X is declared to be variadic, then:
        if optionality_values and optionality_values[-1] == 'variadic':
            # 5.7.1. For each i in the range n to max - 1, inclusive:
            for i in range(n, maxarg):
                # 5.7.1.1. Let t be a type list.
                # 5.7.1.2. Let o be an optionality list.
                type_list, optionality_list = [], []
                # 5.7.1.3. For each j in the range 0 to n-1, inclusive:
                for j in range(0, n):
                    # 5.7.1.3.1. Append types[j] to t.
                    type_list.append(types[j])
                    # 5.7.1.3.2. Append optionalityValues[j] to o.
                    optionality_list.append(optionality_values[j])
                # 5.7.1.4. For each j in the range n to i, inclusive:
                for j in range(n, i + 1):
                    # 5.7.1.4.1. Append types[n - 1] to t.
                    type_list.append(types[n - 1])
                    # 5.7.1.4.2. Append "variadic" to o.
                    optionality_list.append('variadic')
                # 5.7.1.5. Append the tuple (X, t, o) to S.
                S.append((X, tuple(type_list), tuple(optionality_list)))
        # 5.8. Let i be n - 1.
        i = n - 1

        # 5.9. While i ≥ 0:
        while i >= 0:
            # 5.9.1. If arguments[i] is not optional (i.e., it is not marked as
            # "optional" and is not a final, variadic argument), then break.
            if optionality_values[i] == 'required':
                break

            # 5.9.2. Let t be a type list.
            # 5.9.3. Let o be an optionality list.
            type_list, optionality_list = [], []
            # 5.9.4. For each j in the range 0 to i-1, inclusive:
            for j in range(0, i):
                # 5.9.4.1. Append types[j] to t.
                type_list.append(types[j])
                # 5.9.4.2. Append optionalityValues[j] to o.
                optionality_list.append(optionality_values[j])
            # 5.9.5. Append the tuple (X, t, o) to S.
            # Note: if i is 0, this means to add to S the tuple (X, « », « »);
            # (where "« »" represents an empty list).
            S.append((X, tuple(type_list), tuple(optionality_list)))
            # 5.9.6. Set i to i−1.
            i = i - 1

    # 6. Return 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 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.items() 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'))