This is an automated email from the ASF dual-hosted git repository. tvb pushed a commit to branch except_intersections in repository https://gitbox.apache.org/repos/asf/buildstream.git
commit 0bec3b6828d89c014ba3072173e472237a84d91f Author: Tristan Maat <[email protected]> AuthorDate: Tue Nov 7 18:06:41 2017 +0000 _pipeline.py: Adjust remove_elements to work on the 'intersection' --- buildstream/_pipeline.py | 80 +++++++++++++++++++++++++++++------------------- 1 file changed, 48 insertions(+), 32 deletions(-) diff --git a/buildstream/_pipeline.py b/buildstream/_pipeline.py index f89ad2d..de916f4 100644 --- a/buildstream/_pipeline.py +++ b/buildstream/_pipeline.py @@ -25,6 +25,7 @@ import stat import shlex import shutil import tarfile +import itertools from operator import itemgetter from tempfile import TemporaryDirectory from pluginbase import PluginBase @@ -236,6 +237,8 @@ class Pipeline(): # ordering for optimal build plans def plan(self): build_plan = Planner().plan(self.targets) + self.remove_elements(build_plan) + for element in build_plan: yield element @@ -710,48 +713,61 @@ class Pipeline(): # # Internal function # - # Returns all elements to be removed from the given list of - # elements when the given removed elements and their unique - # dependencies are removed. + # Return what we are left with after the intersection between + # excepted and target elements and their unique dependencies is + # gone. # # Args: - # elements (list of elements): The graph to sever elements from. - # removed (list of strings): Names of the elements to remove. - def remove_elements(self, tree, removed): + # elements (list of elements): The list to remove elements from. + def remove_elements(self, elements): + targeted = list(self.dependencies(Scope.ALL)) + + visited = [] - if removed is None: - removed = [] + def find_intersection(element): + if element in visited: + return + visited.append(element) - to_remove = set() - tree = list(tree) + # Intersection elements are those that are also in + # 'targeted', as long as we don't recurse into them. + if element in targeted: + yield element + else: + for dep in element.dependencies(Scope.ALL, recurse=False): + yield from find_intersection(dep) - # Find all elements that might need to be removed. - def search_tree(element_name): - for element in tree: - if element.name == element_name: - return element - return None + # Build a list of 'intersection' elements, i.e. the set of + # elements that lie on the border closest to excepted elements + # between excepted and target elements. + intersection = list(itertools.chain.from_iterable( + find_intersection(element) for element in self.exceptions + )) - for element_name in removed: - element = search_tree(element_name) - if element is None: - raise PipelineError("No element named {} in the loaded pipeline".format(element_name)) + # Now use this set of elements to traverse the targeted + # elements, except 'intersection' elements and their unique + # dependencies. + visited = [] - to_remove.update(element.dependencies(Scope.ALL)) + def traverse(element): + if element in visited or element in intersection: + return + visited.append(element) - old_to_remove = set() - while old_to_remove != to_remove: - old_to_remove = to_remove + for dep in element.dependencies(Scope.ALL, recurse=False): + traverse(dep) - # Of these, find all elements that are not a dependency of - # elements still in use. - for element in tree: - if element.name not in removed and element not in to_remove: - to_remove = to_remove.difference(element.dependencies(Scope.ALL, recurse=False)) + for element in self.targets: + traverse(element) - to_remove = to_remove.union([e for e in tree if e.name in removed]) + # That looks like a lot, but overall we only traverse (part + # of) the graph twice. This could be reduced to once if we + # kept track of parent elements, but is probably not + # significant. - return [element for element in tree if element not in to_remove] + # Ensure that we return elements in the same order they were + # in before. + return [element for element in elements if element in visited] def validate_workspace_index(self, source_index): sources = list(self.targets[0].sources()) @@ -787,7 +803,7 @@ class Pipeline(): elements = list(self.dependencies(scope)) - return self.remove_elements(elements, except_) + return self.remove_elements(elements) # source_bundle() #
