Introduce SpecifierSorter, a thing that knows how specifiers should be ordered.
[WebKit.git] / Tools / Scripts / webkitpy / layout_tests / models / test_configuration.py
1 # Copyright (C) 2011 Google Inc. All rights reserved.
2 #
3 # Redistribution and use in source and binary forms, with or without
4 # modification, are permitted provided that the following conditions are
5 # met:
6 #
7 #     * Redistributions of source code must retain the above copyright
8 # notice, this list of conditions and the following disclaimer.
9 #     * Redistributions in binary form must reproduce the above
10 # copyright notice, this list of conditions and the following disclaimer
11 # in the documentation and/or other materials provided with the
12 # distribution.
13 #     * Neither the Google name nor the names of its
14 # contributors may be used to endorse or promote products derived from
15 # this software without specific prior written permission.
16 #
17 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 """Representation of a layout test configuration."""
29
30
31 class TestConfiguration(object):
32     def __init__(self, port=None, version=None, architecture=None, build_type=None, graphics_type=None):
33         self.version = version or port.version()
34         self.architecture = architecture or port.architecture()
35         self.build_type = build_type or port.options.configuration.lower()
36         self.graphics_type = graphics_type or port.graphics_type()
37
38     @classmethod
39     def category_order(cls):
40         """The most common human-readable order in which the configuration properties are listed."""
41         return ['version', 'architecture', 'build_type', 'graphics_type']
42
43     def items(self):
44         return self.__dict__.items()
45
46     def keys(self):
47         return self.__dict__.keys()
48
49     def __str__(self):
50         return ("<%(version)s, %(architecture)s, %(build_type)s, %(graphics_type)s>" %
51                 self.__dict__)
52
53     def __repr__(self):
54         return "TestConfig(version='%(version)s', architecture='%(architecture)s', build_type='%(build_type)s', graphics_type='%(graphics_type)s')" % self.__dict__
55
56     def __hash__(self):
57         return hash(self.version + self.architecture + self.build_type + self.graphics_type)
58
59     def __eq__(self, other):
60         return self.__hash__() == other.__hash__()
61
62     def values(self):
63         """Returns the configuration values of this instance as a tuple."""
64         return self.__dict__.values()
65
66
67 class SpecifierSorter:
68     def __init__(self, all_test_configurations=None, macros=None):
69         self._specifier_to_category = {}
70
71         if not all_test_configurations:
72             return
73         for test_configuration in all_test_configurations:
74             for category, specifier in test_configuration.items():
75                 self.add_specifier(category, specifier)
76
77         if not macros:
78             return
79         # Assume well-formed macros.
80         for macro, specifier_list in macros.items():
81             self.add_specifier(self.category_for_specifier(specifier_list[0]), macro)
82
83     def add_specifier(self, category, specifier):
84         self._specifier_to_category[specifier] = category
85
86     @classmethod
87     def category_priority(cls, category):
88         return TestConfiguration.category_order().index(category)
89
90     def specifier_priority(self, specifier):
91         return self.category_priority(self._specifier_to_category[specifier])
92
93     def category_for_specifier(self, specifier):
94         return self._specifier_to_category.get(specifier)
95
96     def sort_specifiers(self, specifiers):
97         category_slots = map(lambda x: [], TestConfiguration.category_order())
98         for specifier in specifiers:
99             category_slots[self.specifier_priority(specifier)].append(specifier)
100
101         def sort_and_return(result, specifier_list):
102             specifier_list.sort()
103             return result + specifier_list
104
105         return reduce(sort_and_return, category_slots, [])
106
107
108 class TestConfigurationConverter:
109     def __init__(self, all_test_configurations, configuration_macros=None):
110         self._all_test_configurations = all_test_configurations
111         self._configuration_macros = configuration_macros or {}
112         self._specifier_to_configuration_set = {}
113         self._specifier_sorter = SpecifierSorter()
114         self._collapsing_sets_by_size = {}
115         self._junk_specifier_combinations = {}
116         collapsing_sets_by_category = {}
117         matching_sets_by_category = {}
118         for configuration in all_test_configurations:
119             for category, specifier in configuration.items():
120                 self._specifier_to_configuration_set.setdefault(specifier, set()).add(configuration)
121                 self._specifier_sorter.add_specifier(category, specifier)
122                 collapsing_sets_by_category.setdefault(category, set()).add(specifier)
123                 # FIXME: This seems extra-awful.
124                 for cat2, spec2 in configuration.items():
125                     if category == cat2:
126                         continue
127                     matching_sets_by_category.setdefault(specifier, {}).setdefault(cat2, set()).add(spec2)
128         for collapsing_set in collapsing_sets_by_category.values():
129             self._collapsing_sets_by_size.setdefault(len(collapsing_set), set()).add(frozenset(collapsing_set))
130
131         for specifier, sets_by_category in matching_sets_by_category.items():
132             for category, set_by_category in sets_by_category.items():
133                 if len(set_by_category) == 1 and self._specifier_sorter.category_priority(category) > self._specifier_sorter.specifier_priority(specifier):
134                     self._junk_specifier_combinations[specifier] = set_by_category
135
136     def _expand_macros(self, specifier):
137         expanded_specifiers = self._configuration_macros.get(specifier)
138         return expanded_specifiers or [specifier]
139
140     def to_config_set(self, specifier_set, error_list=None):
141         """Convert a list of specifiers into a set of TestConfiguration instances."""
142         if len(specifier_set) == 0:
143             return self._all_test_configurations
144
145         matching_sets = {}
146
147         for specifier in specifier_set:
148             for expanded_specifier in self._expand_macros(specifier):
149                 configurations = self._specifier_to_configuration_set.get(expanded_specifier)
150                 if not configurations:
151                     if error_list is not None:
152                         error_list.append("Unrecognized modifier '" + expanded_specifier + "'")
153                     return set()
154                 category = self._specifier_sorter.category_for_specifier(expanded_specifier)
155                 matching_sets.setdefault(category, set()).update(configurations)
156
157         return reduce(set.intersection, matching_sets.values())
158
159     @classmethod
160     def collapse_macros(cls, macros_dict, specifiers_list):
161         for i in range(len(specifiers_list)):
162             for macro_specifier, macro in macros_dict.items():
163                 specifiers_set = set(specifiers_list[i])
164                 macro_set = set(macro)
165                 if specifiers_set >= macro_set:
166                     specifiers_list[i] = frozenset((specifiers_set - macro_set) | set([macro_specifier]))
167
168     def to_specifiers_list(self, test_configuration_set):
169         """Convert a set of TestConfiguration instances into one or more list of specifiers."""
170
171         # Easy out: if the set is all configurations, the modifier is empty.
172         if len(test_configuration_set) == len(self._all_test_configurations):
173             return []
174
175         # 1) Build a list of specifier sets, discarding specifiers that don't add value.
176         specifiers_list = []
177         for config in test_configuration_set:
178             values = set(config.values())
179             for specifier, junk_specifier_set in self._junk_specifier_combinations.items():
180                 if specifier in values:
181                     values -= junk_specifier_set
182             specifiers_list.append(frozenset(values))
183
184         # FIXME: Replace with iteritools.combinations when we obsolete Python 2.5.
185         def combinations(iterable, r):
186             """This function is borrowed verbatim from http://docs.python.org/library/itertools.html#itertools.combinations."""
187             pool = tuple(iterable)
188             n = len(pool)
189             if r > n:
190                 return
191             indices = range(r)
192             yield tuple(pool[i] for i in indices)
193             while True:
194                 for i in reversed(range(r)):
195                     if indices[i] != i + n - r:
196                         break
197                 else:
198                     return
199                 indices[i] += 1
200                 for j in range(i + 1, r):
201                     indices[j] = indices[j - 1] + 1
202                 yield tuple(pool[i] for i in indices)
203
204         def intersect_combination(combination):
205             return reduce(set.intersection, [set(specifiers) for specifiers in combination])
206
207         def symmetric_difference(iterable):
208             return reduce(lambda x, y: x ^ y, iterable)
209
210         def try_collapsing(size, collapsing_sets):
211             if len(specifiers_list) < size:
212                 return False
213             for combination in combinations(specifiers_list, size):
214                 if symmetric_difference(combination) in collapsing_sets:
215                     for item in combination:
216                         specifiers_list.remove(item)
217                     specifiers_list.append(frozenset(intersect_combination(combination)))
218                     return True
219             return False
220
221         # 2) Collapse specifier sets with common specifiers:
222         #   (xp, release, gpu), (xp, release, cpu) --> (xp, x86, release)
223         for size, collapsing_sets in self._collapsing_sets_by_size.items():
224             while try_collapsing(size, collapsing_sets):
225                 pass
226
227         def try_abbreviating():
228             if len(specifiers_list) < 2:
229                 return False
230             for combination in combinations(specifiers_list, 2):
231                 for collapsing_set in collapsing_sets:
232                     diff = symmetric_difference(combination)
233                     if diff <= collapsing_set:
234                         common = intersect_combination(combination)
235                         for item in combination:
236                             specifiers_list.remove(item)
237                         specifiers_list.append(frozenset(common | diff))
238                         return True
239             return False
240
241         # 3) Abbreviate specifier sets by combining specifiers across categories.
242         #   (xp, release), (win7, release) --> (xp, win7, release)
243         while try_abbreviating():
244             pass
245
246         # 4) Substitute specifier subsets that match macros witin each set:
247         #   (xp, vista, win7, release) -> (win, release)
248         self.collapse_macros(self._configuration_macros, specifiers_list)
249
250         return specifiers_list