4793bcfa84a4e061a6de78a6aa40b9077dd8d880
[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 TestConfigurationConverter:
68     def __init__(self, all_test_configurations, configuration_macros=None):
69         self._all_test_configurations = all_test_configurations
70         self._configuration_macros = configuration_macros or {}
71         self._specifier_to_configuration_set = {}
72         self._specifier_to_category = {}
73         self._collapsing_sets_by_size = {}
74         self._junk_specifier_combinations = {}
75         collapsing_sets_by_category = {}
76         matching_sets_by_category = {}
77         for configuration in all_test_configurations:
78             for category, specifier in configuration.items():
79                 self._specifier_to_configuration_set.setdefault(specifier, set()).add(configuration)
80                 self._specifier_to_category[specifier] = category
81                 collapsing_sets_by_category.setdefault(category, set()).add(specifier)
82                 # FIXME: This seems extra-awful.
83                 for cat2, spec2 in configuration.items():
84                     if category == cat2:
85                         continue
86                     matching_sets_by_category.setdefault(specifier, {}).setdefault(cat2, set()).add(spec2)
87         for collapsing_set in collapsing_sets_by_category.values():
88             self._collapsing_sets_by_size.setdefault(len(collapsing_set), set()).add(frozenset(collapsing_set))
89
90         def category_priority(category):
91             return TestConfiguration.category_order().index(category)
92
93         def specifier_priority(specifier):
94             return category_priority(self._specifier_to_category[specifier])
95
96         for specifier, sets_by_category in matching_sets_by_category.items():
97             for category, set_by_category in sets_by_category.items():
98                 if len(set_by_category) == 1 and category_priority(category) > specifier_priority(specifier):
99                     self._junk_specifier_combinations[specifier] = set_by_category
100
101     def _expand_macros(self, specifier):
102         expanded_specifiers = self._configuration_macros.get(specifier)
103         return expanded_specifiers or [specifier]
104
105     def to_config_set(self, specifier_set, error_list=None):
106         """Convert a list of specifiers into a set of TestConfiguration instances."""
107         if len(specifier_set) == 0:
108             return self._all_test_configurations
109
110         matching_sets = {}
111
112         for specifier in specifier_set:
113             for expanded_specifier in self._expand_macros(specifier):
114                 configurations = self._specifier_to_configuration_set.get(expanded_specifier)
115                 if not configurations:
116                     if error_list is not None:
117                         error_list.append("Unrecognized modifier '" + expanded_specifier + "'")
118                     return set()
119                 category = self._specifier_to_category[expanded_specifier]
120                 matching_sets.setdefault(category, set()).update(configurations)
121
122         return reduce(set.intersection, matching_sets.values())
123
124     @classmethod
125     def collapse_macros(cls, macros_dict, specifiers_list):
126         for i in range(len(specifiers_list)):
127             for macro_specifier, macro in macros_dict.items():
128                 specifiers_set = set(specifiers_list[i])
129                 macro_set = set(macro)
130                 if specifiers_set >= macro_set:
131                     specifiers_list[i] = frozenset((specifiers_set - macro_set) | set([macro_specifier]))
132
133     def to_specifiers_list(self, test_configuration_set):
134         """Convert a set of TestConfiguration instances into one or more list of specifiers."""
135
136         # Easy out: if the set is all configurations, the modifier is empty.
137         if len(test_configuration_set) == len(self._all_test_configurations):
138             return []
139
140         # 1) Build a list of specifier sets, discarding specifiers that don't add value.
141         specifiers_list = []
142         for config in test_configuration_set:
143             values = set(config.values())
144             for specifier, junk_specifier_set in self._junk_specifier_combinations.items():
145                 if specifier in values:
146                     values -= junk_specifier_set
147             specifiers_list.append(frozenset(values))
148
149         # FIXME: Replace with iteritools.combinations when we obsolete Python 2.5.
150         def combinations(iterable, r):
151             """This function is borrowed verbatim from http://docs.python.org/library/itertools.html#itertools.combinations."""
152             pool = tuple(iterable)
153             n = len(pool)
154             if r > n:
155                 return
156             indices = range(r)
157             yield tuple(pool[i] for i in indices)
158             while True:
159                 for i in reversed(range(r)):
160                     if indices[i] != i + n - r:
161                         break
162                 else:
163                     return
164                 indices[i] += 1
165                 for j in range(i + 1, r):
166                     indices[j] = indices[j - 1] + 1
167                 yield tuple(pool[i] for i in indices)
168
169         def intersect_combination(combination):
170             return reduce(set.intersection, [set(specifiers) for specifiers in combination])
171
172         def symmetric_difference(iterable):
173             return reduce(lambda x, y: x ^ y, iterable)
174
175         def try_collapsing(size, collapsing_sets):
176             if len(specifiers_list) < size:
177                 return False
178             for combination in combinations(specifiers_list, size):
179                 if symmetric_difference(combination) in collapsing_sets:
180                     for item in combination:
181                         specifiers_list.remove(item)
182                     specifiers_list.append(frozenset(intersect_combination(combination)))
183                     return True
184             return False
185
186         # 2) Collapse specifier sets with common specifiers:
187         #   (xp, release, gpu), (xp, release, cpu) --> (xp, x86, release)
188         for size, collapsing_sets in self._collapsing_sets_by_size.items():
189             while try_collapsing(size, collapsing_sets):
190                 pass
191
192         def try_abbreviating():
193             if len(specifiers_list) < 2:
194                 return False
195             for combination in combinations(specifiers_list, 2):
196                 for collapsing_set in collapsing_sets:
197                     diff = symmetric_difference(combination)
198                     if diff <= collapsing_set:
199                         common = intersect_combination(combination)
200                         for item in combination:
201                             specifiers_list.remove(item)
202                         specifiers_list.append(frozenset(common | diff))
203                         return True
204             return False
205
206         # 3) Abbreviate specifier sets by combining specifiers across categories.
207         #   (xp, release), (win7, release) --> (xp, win7, release)
208         while try_abbreviating():
209             pass
210
211         # 4) Substitute specifier subsets that match macros witin each set:
212         #   (xp, vista, win7, release) -> (win, release)
213         self.collapse_macros(self._configuration_macros, specifiers_list)
214
215         return specifiers_list