189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org#!/usr/bin/python 289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org# Copyright 2014 Google Inc. 489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org# 589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org# Use of this source code is governed by a BSD-style license that can be 689335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org# found in the LICENSE file. 789335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.orgimport collections 989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.orgimport types 1089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 11ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org# The goal of this class is to store a set of unique items in the order in 12ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org# which they are inserted. This is important for the final makefile, where 13ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org# we want to make sure the image decoders are in a particular order. See 14ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org# images.gyp for more information. 1589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.orgclass OrderedSet(object): 16d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Ordered set of unique items that supports addition and removal. 17d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 18d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Retains the order in which items are inserted. 1989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 2089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 2189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def __init__(self): 22d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org self.__ordered_set = [] 2389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 2489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def add(self, item): 25d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Add item, if it is not already in the set. 26d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 27d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org item is appended to the end if it is not already in the set. 28d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 29d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Args: 30d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org item: The item to add. 3189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 32d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org if item not in self.__ordered_set: 33d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org self.__ordered_set.append(item) 3489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 3589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def __contains__(self, item): 36d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Whether the set contains item. 37d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 38d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Args: 39d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org item: The item to search for in the set. 40d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 41d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Returns: 42d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org bool: Whether the item is in the set. 4389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 44d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org return item in self.__ordered_set 4589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 4689335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def __iter__(self): 47d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Iterator for the set. 4889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 49d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org return self.__ordered_set.__iter__() 5089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 5189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def remove(self, item): 5289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 5389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org Remove item from the set. 54d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 55d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Args: 56d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org item: Item to be removed. 57d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 58d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Raises: 59d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org ValueError if item is not in the set. 6089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 61d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org self.__ordered_set.remove(item) 6289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 6389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def __len__(self): 64d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Number of items in the set. 6589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 66d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org return len(self.__ordered_set) 6789335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 6889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def __getitem__(self, index): 69d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Return item at index. 7089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 71d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org return self.__ordered_set[index] 7289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 73ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org def reset(self): 74d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Reset to empty. 75ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org """ 76d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org self.__ordered_set = [] 77d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 78d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org def set(self, other): 79d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Replace this ordered set with another. 80d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 81d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Args: 82d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org other: OrderedSet to replace this one. After this call, this OrderedSet 83d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org will contain exactly the same elements as other. 84ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org """ 85d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org self.__ordered_set = list(other.__ordered_set) 86ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org 8789335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.orgVAR_NAMES = ['LOCAL_CFLAGS', 8889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 'LOCAL_CPPFLAGS', 8989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 'LOCAL_SRC_FILES', 9089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 'LOCAL_SHARED_LIBRARIES', 9189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 'LOCAL_STATIC_LIBRARIES', 9289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 'LOCAL_C_INCLUDES', 9389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 'LOCAL_EXPORT_C_INCLUDE_DIRS', 94ba0c5ea90d0e6b2e8b20696e54fea13ead6dda93commit-bot@chromium.org 'DEFINES', 95d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 'KNOWN_TARGETS', 96d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org # These are not parsed by gyp, but set manually. 97d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 'LOCAL_MODULE_TAGS', 98d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 'LOCAL_MODULE'] 9989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 10089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.orgclass VarsDict(collections.namedtuple('VarsDict', VAR_NAMES)): 101d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Custom class for storing the arguments to Android.mk variables. 102d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 103d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Can also be treated as a dictionary with fixed keys. 10489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 10589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 10689335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org __slots__ = () 10789335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 10889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def __new__(cls): 10989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org lists = [] 11089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org # TODO (scroggo): Is there a better way add N items? 11189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org for __unused__ in range(len(VAR_NAMES)): 11289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org lists.append(OrderedSet()) 11389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org return tuple.__new__(cls, lists) 11489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 11589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def keys(self): 116d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Return the field names as strings. 11789335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 11889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org return self._fields 11989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 12089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org def __getitem__(self, index): 121d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Return an item, indexed by a number or a string. 12289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 12389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org if type(index) == types.IntType: 12489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org # Treat the index as an array index into a tuple. 12589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org return tuple.__getitem__(self, index) 12689335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org if type(index) == types.StringType: 12789335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org # Treat the index as a key into a dictionary. 12889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org return eval('self.%s' % index) 12989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org return None 13089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 13189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 13289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.orgdef intersect(var_dict_list): 133d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org """Compute intersection of VarsDicts. 134d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 13589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org Find the intersection of a list of VarsDicts and trim each input to its 13689335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org unique entries. 137d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org 138d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Args: 139d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org var_dict_list: list of VarsDicts. WARNING: each VarsDict will be 140d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org modified in place, to remove the common elements! 141d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org Returns: 142d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org VarsDict containing list entries common to all VarsDicts in 143d6656854697b2039fb88a4afd6bc1995bf6dfa02commit-bot@chromium.org var_dict_list 14489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org """ 14589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org intersection = VarsDict() 14689335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org # First VarsDict 14789335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org var_dict_a = var_dict_list[0] 14889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org # The rest. 14989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org other_var_dicts = var_dict_list[1:] 15089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 15189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org for key in var_dict_a.keys(): 15289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org # Copy A's list, so we can continue iterating after modifying the original. 15389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org a_list = list(var_dict_a[key]) 15489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org for item in a_list: 15589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org # If item is in all lists, add to intersection, and remove from all. 15689335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org in_all_lists = True 15789335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org for var_dict in other_var_dicts: 15889335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org if not item in var_dict[key]: 15989335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org in_all_lists = False 16089335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org break 16189335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org if in_all_lists: 16289335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org intersection[key].add(item) 16389335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org for var_dict in var_dict_list: 16489335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org var_dict[key].remove(item) 16589335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org return intersection 16689335631749b29ea92e55ed710f030692aa13297commit-bot@chromium.org 167