OLD | NEW |
---|---|
(Empty) | |
1 # Copyright 2017 The Chromium Authors. All rights reserved. | |
haraken
2017/02/23 21:38:17
Nit: I'd prefer renaming this file to "overload_re
| |
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 |