OLD | NEW |
(Empty) | |
| 1 # Copyright 2017 The Chromium Authors. All rights reserved. |
| 2 # coding=utf-8 |
| 3 # Use of this source code is governed by a BSD-style license that can be |
| 4 # found in the LICENSE file. |
| 5 |
| 6 from collections import Counter |
| 7 import itertools |
| 8 from operator import itemgetter |
| 9 |
| 10 |
| 11 def sort_and_groupby(list_to_sort, key=None): |
| 12 """Returns a generator of (key, list), sorting and grouping list by key.""" |
| 13 list_to_sort.sort(key=key) |
| 14 return ((k, list(g)) for k, g in itertools.groupby(list_to_sort, key)) |
| 15 |
| 16 |
| 17 def effective_overload_set(F): # pylint: disable=invalid-name |
| 18 """Returns the effective overload set of an overloaded function. |
| 19 |
| 20 An effective overload set is the set of overloaded functions + signatures |
| 21 (type list of arguments, with optional and variadic arguments included or |
| 22 not), and is used in the overload resolution algorithm. |
| 23 |
| 24 For example, given input [f1(optional long x), f2(DOMString s)], the output |
| 25 is informally [f1(), f1(long), f2(DOMString)], and formally |
| 26 [(f1, [], []), (f1, [long], [optional]), (f2, [DOMString], [required])]. |
| 27 |
| 28 Currently the optionality list is a list of |is_optional| booleans (True |
| 29 means optional, False means required); to support variadics this needs to |
| 30 be tri-valued as required, optional, or variadic. |
| 31 |
| 32 Formally: |
| 33 An effective overload set represents the allowable invocations for a |
| 34 particular operation, constructor (specified with [Constructor] or |
| 35 [NamedConstructor]), legacy caller or callback function. |
| 36 |
| 37 An additional argument N (argument count) is needed when overloading |
| 38 variadics, but we don't use that currently. |
| 39 |
| 40 Spec: http://heycam.github.io/webidl/#dfn-effective-overload-set |
| 41 |
| 42 Formally the input and output lists are sets, but methods are stored |
| 43 internally as dicts, which can't be stored in a set because they are not |
| 44 hashable, so we use lists instead. |
| 45 |
| 46 Arguments: |
| 47 F: list of overloads for a given callable name. |
| 48 |
| 49 Returns: |
| 50 S: list of tuples of the form (callable, type list, optionality list). |
| 51 """ |
| 52 # Code closely follows the algorithm in the spec, for clarity and |
| 53 # correctness, and hence is not very Pythonic. |
| 54 |
| 55 # 1. Initialize S to ∅. |
| 56 # (We use a list because we can't use a set, as noted above.) |
| 57 S = [] # pylint: disable=invalid-name |
| 58 |
| 59 # 2. Let F be a set with elements as follows, according to the kind of |
| 60 # effective overload set: |
| 61 # (Passed as argument, nothing to do.) |
| 62 |
| 63 # 3. & 4. (maxarg, m) are only needed for variadics, not used. |
| 64 |
| 65 # 5. For each operation, extended attribute or callback function X in F: |
| 66 for X in F: # X is the "callable". pylint: disable=invalid-name |
| 67 arguments = X['arguments'] # pylint: disable=invalid-name |
| 68 # 1. Let n be the number of arguments X is declared to take. |
| 69 n = len(arguments) # pylint: disable=invalid-name |
| 70 # 2. Let t0..n−1 be a list of types, where ti is the type of X’s |
| 71 # argument at index i. |
| 72 # (“type list”) |
| 73 t = tuple(argument['idl_type_object'] # pylint: disable=invalid-name |
| 74 for argument in arguments) |
| 75 # 3. Let o0..n−1 be a list of optionality values, where oi is “variadic” |
| 76 # if X’s argument at index i is a final, variadic argument, “optional” |
| 77 # if the argument is optional, and “required” otherwise. |
| 78 # (“optionality list”) |
| 79 # (We’re just using a boolean for optional/variadic vs. required.) |
| 80 o = tuple(argument['is_optional'] # pylint: disable=invalid-name |
| 81 or argument['is_variadic'] for argument in arguments) |
| 82 # 4. Add to S the tuple <X, t0..n−1, o0..n−1>. |
| 83 S.append((X, t, o)) |
| 84 # 5. If X is declared to be variadic, then: |
| 85 # (Not used, so not implemented.) |
| 86 # 6. Initialize i to n−1. |
| 87 i = n - 1 |
| 88 # 7. While i ≥ 0: |
| 89 # Spec bug (fencepost error); should be “While i > 0:” |
| 90 # https://www.w3.org/Bugs/Public/show_bug.cgi?id=25590 |
| 91 while i > 0: |
| 92 # 1. If argument i of X is not optional, then break this loop. |
| 93 if not o[i]: |
| 94 break |
| 95 # 2. Otherwise, add to S the tuple <X, t0..i−1, o0..i−1>. |
| 96 S.append((X, t[:i], o[:i])) |
| 97 # 3. Set i to i−1. |
| 98 i = i - 1 |
| 99 # 8. If n > 0 and all arguments of X are optional, then add to S the |
| 100 # tuple <X, (), ()> (where “()” represents the empty list). |
| 101 if n > 0 and all(oi for oi in o): |
| 102 S.append((X, [], [])) |
| 103 # 6. The effective overload set is S. |
| 104 return S |
| 105 |
| 106 |
| 107 def effective_overload_set_by_length(overloads): |
| 108 def type_list_length(entry): |
| 109 # Entries in the effective overload set are 3-tuples: |
| 110 # (callable, type list, optionality list) |
| 111 return len(entry[1]) |
| 112 |
| 113 effective_overloads = effective_overload_set(overloads) |
| 114 return list(sort_and_groupby(effective_overloads, type_list_length)) |
| 115 |
| 116 |
| 117 def method_overloads_by_name(methods): |
| 118 """Returns generator of overloaded methods by name: [name, [method]]""" |
| 119 # Filter to only methods that are actually overloaded |
| 120 method_counts = Counter(method['name'] for method in methods) |
| 121 overloaded_method_names = set(name |
| 122 for name, count in method_counts.iteritems() |
| 123 if count > 1) |
| 124 overloaded_methods = [method for method in methods |
| 125 if method['name'] in overloaded_method_names] |
| 126 |
| 127 # Group by name (generally will be defined together, but not necessarily) |
| 128 return sort_and_groupby(overloaded_methods, itemgetter('name')) |
OLD | NEW |