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
29import copy
30
31
32class TestConfiguration(object):
33    def __init__(self, version, architecture, build_type):
34        self.version = version
35        self.architecture = architecture
36        self.build_type = build_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']
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>" %
51                self.__dict__)
52
53    def __repr__(self):
54        return "TestConfig(version='%(version)s', architecture='%(architecture)s', build_type='%(build_type)s')" % self.__dict__
55
56    def __hash__(self):
57        return hash(self.version + self.architecture + self.build_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
67class SpecifierSorter(object):
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        self.add_macros(macros)
78
79    def add_specifier(self, category, specifier):
80        self._specifier_to_category[specifier] = category
81
82    def add_macros(self, macros):
83        if not macros:
84            return
85        # Assume well-formed macros.
86        for macro, specifier_list in macros.items():
87            self.add_specifier(self.category_for_specifier(specifier_list[0]), macro)
88
89    @classmethod
90    def category_priority(cls, category):
91        return TestConfiguration.category_order().index(category)
92
93    def specifier_priority(self, specifier):
94        return self.category_priority(self._specifier_to_category[specifier])
95
96    def category_for_specifier(self, specifier):
97        return self._specifier_to_category.get(specifier)
98
99    def sort_specifiers(self, specifiers):
100        category_slots = map(lambda x: [], TestConfiguration.category_order())
101        for specifier in specifiers:
102            category_slots[self.specifier_priority(specifier)].append(specifier)
103
104        def sort_and_return(result, specifier_list):
105            specifier_list.sort()
106            return result + specifier_list
107
108        return reduce(sort_and_return, category_slots, [])
109
110
111class TestConfigurationConverter(object):
112    def __init__(self, all_test_configurations, configuration_macros=None):
113        self._all_test_configurations = all_test_configurations
114        self._configuration_macros = configuration_macros or {}
115        self._specifier_to_configuration_set = {}
116        self._specifier_sorter = SpecifierSorter()
117        self._collapsing_sets_by_size = {}
118        self._junk_specifier_combinations = {}
119        self._collapsing_sets_by_category = {}
120        matching_sets_by_category = {}
121        for configuration in all_test_configurations:
122            for category, specifier in configuration.items():
123                self._specifier_to_configuration_set.setdefault(specifier, set()).add(configuration)
124                self._specifier_sorter.add_specifier(category, specifier)
125                self._collapsing_sets_by_category.setdefault(category, set()).add(specifier)
126                # FIXME: This seems extra-awful.
127                for cat2, spec2 in configuration.items():
128                    if category == cat2:
129                        continue
130                    matching_sets_by_category.setdefault(specifier, {}).setdefault(cat2, set()).add(spec2)
131        for collapsing_set in self._collapsing_sets_by_category.values():
132            self._collapsing_sets_by_size.setdefault(len(collapsing_set), set()).add(frozenset(collapsing_set))
133
134        for specifier, sets_by_category in matching_sets_by_category.items():
135            for category, set_by_category in sets_by_category.items():
136                if len(set_by_category) == 1 and self._specifier_sorter.category_priority(category) > self._specifier_sorter.specifier_priority(specifier):
137                    self._junk_specifier_combinations[specifier] = set_by_category
138
139        self._specifier_sorter.add_macros(configuration_macros)
140
141    def specifier_sorter(self):
142        return self._specifier_sorter
143
144    def _expand_macros(self, specifier):
145        expanded_specifiers = self._configuration_macros.get(specifier)
146        return expanded_specifiers or [specifier]
147
148    def to_config_set(self, specifier_set, error_list=None):
149        """Convert a list of specifiers into a set of TestConfiguration instances."""
150        if len(specifier_set) == 0:
151            return copy.copy(self._all_test_configurations)
152
153        matching_sets = {}
154
155        for specifier in specifier_set:
156            for expanded_specifier in self._expand_macros(specifier):
157                configurations = self._specifier_to_configuration_set.get(expanded_specifier)
158                if not configurations:
159                    if error_list is not None:
160                        error_list.append("Unrecognized specifier '" + expanded_specifier + "'")
161                    return set()
162                category = self._specifier_sorter.category_for_specifier(expanded_specifier)
163                matching_sets.setdefault(category, set()).update(configurations)
164
165        return reduce(set.intersection, matching_sets.values())
166
167    @classmethod
168    def collapse_macros(cls, macros_dict, specifiers_list):
169        for macro_specifier, macro in macros_dict.items():
170            if len(macro) == 1:
171                continue
172
173            for combination in cls.combinations(specifiers_list, len(macro)):
174                if cls.symmetric_difference(combination) == set(macro):
175                    for item in combination:
176                        specifiers_list.remove(item)
177                    new_specifier_set = cls.intersect_combination(combination)
178                    new_specifier_set.add(macro_specifier)
179                    specifiers_list.append(frozenset(new_specifier_set))
180
181        def collapse_individual_specifier_set(macro_specifier, macro):
182            specifiers_to_remove = []
183            specifiers_to_add = []
184            for specifier_set in specifiers_list:
185                macro_set = set(macro)
186                if macro_set.intersection(specifier_set) == macro_set:
187                    specifiers_to_remove.append(specifier_set)
188                    specifiers_to_add.append(frozenset((set(specifier_set) - macro_set) | set([macro_specifier])))
189            for specifier in specifiers_to_remove:
190                specifiers_list.remove(specifier)
191            for specifier in specifiers_to_add:
192                specifiers_list.append(specifier)
193
194        for macro_specifier, macro in macros_dict.items():
195            collapse_individual_specifier_set(macro_specifier, macro)
196
197    # FIXME: itertools.combinations in buggy in Python 2.6.1 (the version that ships on SL).
198    # It seems to be okay in 2.6.5 or later; until then, this is the implementation given
199    # in http://docs.python.org/library/itertools.html (from 2.7).
200    @staticmethod
201    def combinations(iterable, r):
202        # combinations('ABCD', 2) --> AB AC AD BC BD CD
203        # combinations(range(4), 3) --> 012 013 023 123
204        pool = tuple(iterable)
205        n = len(pool)
206        if r > n:
207            return
208        indices = range(r)
209        yield tuple(pool[i] for i in indices)
210        while True:
211            for i in reversed(range(r)):
212                if indices[i] != i + n - r:
213                    break
214            else:
215                return
216            indices[i] += 1  # pylint: disable=W0631
217            for j in range(i + 1, r):  # pylint: disable=W0631
218                indices[j] = indices[j - 1] + 1
219            yield tuple(pool[i] for i in indices)
220
221    @classmethod
222    def intersect_combination(cls, combination):
223        return reduce(set.intersection, [set(specifiers) for specifiers in combination])
224
225    @classmethod
226    def symmetric_difference(cls, iterable):
227        union = set()
228        intersection = iterable[0]
229        for item in iterable:
230            union = union | item
231            intersection = intersection.intersection(item)
232        return union - intersection
233
234    def to_specifiers_list(self, test_configuration_set):
235        """Convert a set of TestConfiguration instances into one or more list of specifiers."""
236        # Easy out: if the set is all configurations, the specifier is empty.
237        if len(test_configuration_set) == len(self._all_test_configurations):
238            return [[]]
239
240        # 1) Build a list of specifier sets, discarding specifiers that don't add value.
241        specifiers_list = []
242        for config in test_configuration_set:
243            values = set(config.values())
244            for specifier, junk_specifier_set in self._junk_specifier_combinations.items():
245                if specifier in values:
246                    values -= junk_specifier_set
247            specifiers_list.append(frozenset(values))
248
249        def try_collapsing(size, collapsing_sets):
250            if len(specifiers_list) < size:
251                return False
252            for combination in self.combinations(specifiers_list, size):
253                if self.symmetric_difference(combination) in collapsing_sets:
254                    for item in combination:
255                        specifiers_list.remove(item)
256                    specifiers_list.append(frozenset(self.intersect_combination(combination)))
257                    return True
258            return False
259
260        # 2) Collapse specifier sets with common specifiers:
261        #   (xp, release), (xp, debug) --> (xp, x86)
262        for size, collapsing_sets in self._collapsing_sets_by_size.items():
263            while try_collapsing(size, collapsing_sets):
264                pass
265
266        def try_abbreviating(collapsing_sets):
267            if len(specifiers_list) < 2:
268                return False
269            for combination in self.combinations(specifiers_list, 2):
270                for collapsing_set in collapsing_sets:
271                    diff = self.symmetric_difference(combination)
272                    if diff <= collapsing_set:
273                        common = self.intersect_combination(combination)
274                        for item in combination:
275                            specifiers_list.remove(item)
276                        specifiers_list.append(frozenset(common | diff))
277                        return True
278            return False
279
280        # 3) Abbreviate specifier sets by combining specifiers across categories.
281        #   (xp, release), (win7, release) --> (xp, win7, release)
282        while try_abbreviating(self._collapsing_sets_by_size.values()):
283            pass
284
285
286        # 4) Substitute specifier subsets that match macros witin each set:
287        #   (xp, win7, release) -> (win, release)
288        self.collapse_macros(self._configuration_macros, specifiers_list)
289
290        macro_keys = set(self._configuration_macros.keys())
291
292        # 5) Collapsing macros may have created combinations the can now be abbreviated.
293        #   (xp, release), (linux, x86, release), (linux, x86_64, release) --> (xp, release), (linux, release) --> (xp, linux, release)
294        while try_abbreviating([self._collapsing_sets_by_category['version'] | macro_keys]):
295            pass
296
297        # 6) Remove cases where we have collapsed but have all macros.
298        #   (android, win, mac, linux, release) --> (release)
299        specifiers_to_remove = []
300        for specifier_set in specifiers_list:
301            if macro_keys <= specifier_set:
302                specifiers_to_remove.append(specifier_set)
303
304        for specifier_set in specifiers_to_remove:
305            specifiers_list.remove(specifier_set)
306            specifiers_list.append(frozenset(specifier_set - macro_keys))
307
308        return specifiers_list
309