Home | History | Annotate | Download | only in models
      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 
     29 import copy
     30 
     31 
     32 class 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 
     67 class 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 
    111 class 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