diff options
-rw-r--r-- | morphlib/__init__.py | 1 | ||||
-rw-r--r-- | morphlib/buildcommand.py | 25 | ||||
-rw-r--r-- | morphlib/buildorder.py | 117 | ||||
-rw-r--r-- | morphlib/buildorder_tests.py | 141 |
4 files changed, 17 insertions, 267 deletions
diff --git a/morphlib/__init__.py b/morphlib/__init__.py index 4446720e..271fa977 100644 --- a/morphlib/__init__.py +++ b/morphlib/__init__.py @@ -48,7 +48,6 @@ import artifactresolver import bins import buildcommand import buildenvironment -import buildorder import buildsystem import builder2 import cachedir diff --git a/morphlib/buildcommand.py b/morphlib/buildcommand.py index c12735bb..34a3e291 100644 --- a/morphlib/buildcommand.py +++ b/morphlib/buildcommand.py @@ -75,12 +75,6 @@ class BuildCommand(object): def get_artifact_object(self, repo_name, ref, filename): '''Create an Artifact object representing the given triplet.''' - order = self._compute_build_order(repo_name, ref, filename) - artifact = order.groups[-1][-1] - return artifact - - def _compute_build_order(self, repo_name, ref, filename): - '''Compute build order for a triplet.''' self.app.status(msg='Figuring out the right build order') self.app.status(msg='Creating source pool', chatty=True) @@ -103,9 +97,9 @@ class BuildCommand(object): artifact.cache_id = self.ckc.get_cache_id(artifact) self.app.status(msg='Computing build order', chatty=True) - order = morphlib.buildorder.BuildOrder(artifacts) + root_artifact = self._find_root_artifact(artifacts) - return order + return root_artifact def _validate_cross_morphology_references(self, srcpool): '''Perform validation across all morphologies involved in the build''' @@ -165,6 +159,21 @@ class BuildCommand(object): other.morphology['kind'], wanted)) + def _find_root_artifact(self, artifacts): + '''Find the root artifact among a set of artifacts in a DAG. + + There can be only one. + + ''' + + maybe = set(artifacts) + for a in artifacts: + for dep in a.dependencies: + if dep in maybe: + maybe.remove(dep) + assert len(maybe) == 1 + return maybe.pop() + def build_in_order(self, artifact): '''Build everything specified in a build order.''' self.app.status(msg='Building according to build ordering', diff --git a/morphlib/buildorder.py b/morphlib/buildorder.py deleted file mode 100644 index 39b53f05..00000000 --- a/morphlib/buildorder.py +++ /dev/null @@ -1,117 +0,0 @@ -# Copyright (C) 2012 Codethink Limited -# -# This program is free software; you can redistribute it and/or modify -# it under the terms of the GNU General Public License as published by -# the Free Software Foundation; version 2 of the License. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License along -# with this program; if not, write to the Free Software Foundation, Inc., -# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - - -import cliapp -import collections - - -class CyclicDependencyChainError(cliapp.AppException): - - def __init__(self): - cliapp.AppException.__init__( - self, 'Cyclic dependency chain detected') - - -class BuildOrder: - - def __init__(self, artifacts): - self.artifacts = artifacts - - if artifacts: - sorting = self._compute_reverse_topological_sorting(artifacts) - self.groups = self._create_build_groups(sorting) - else: - self.groups = [] - - def _compute_reverse_topological_sorting(self, artifacts): - '''Computes a reverse topological sorting of the build graph. - - A reverse topological sorting basically is the result of a series of - breadth-first searches starting at each leaf node (artifacts with no - dependents). Artifacts are added to the sorting as soon as all their - dependents have been added. - - For more information, see - http://en.wikipedia.org/wiki/Topological_sorting. - - ''' - - # map artifacts to sets of satisfied dependents. this is to detect - # when we can actually add artifacts to the BFS queue. rather than - # dropping links between nodes, like most topological sorting - # algorithms do, we simply remember all satisfied dependents and - # check if all of them are met repeatedly - satisfied_dependents = {} - - # create an empty sorting - sorting = collections.deque() - - # create a set of leafs to start the DFS from - leafs = collections.deque() - for artifact in artifacts: - satisfied_dependents[artifact] = set() - if len(artifact.dependents) == 0: - leafs.append(artifact) - - while len(leafs) > 0: - # fetch a leaf artifact from the DFS queue - artifact = leafs.popleft() - - # add it to the sorting - sorting.append(artifact) - - # mark this dependency as resolved in dependent artifacts - for dependency in artifact.dependencies: - satisfied_dependents[dependency].add(artifact) - - # add the dependent blob as a leaf if all - # its dependents have been resolved - has = len(satisfied_dependents[dependency]) - needs = len(dependency.dependents) - if has == needs: - leafs.append(dependency) - - # if not all dependencies were resolved on the way, we - # have found at least one cyclic dependency - if len(sorting) < len(artifacts): - raise CyclicDependencyChainError() - - return sorting - - def _create_build_groups(self, sorting): - groups = collections.deque() - - if sorting: - # create the last group - group = [] - groups.append(group) - - # traverse the build graph in reverse topological order - for artifact in sorting: - # add artifact to a group that comes as late in the build order - # as possible; if the first group contains any dependents, - # add the artifact to a new group at the beginning of the order - for group in groups: - if not any([x in group for x in artifact.dependents]): - group.append(artifact) - break - else: - group = [] - group.append(artifact) - groups.appendleft(group) - break - - return groups diff --git a/morphlib/buildorder_tests.py b/morphlib/buildorder_tests.py deleted file mode 100644 index ab1a7e1c..00000000 --- a/morphlib/buildorder_tests.py +++ /dev/null @@ -1,141 +0,0 @@ -# Copyright (C) 2012 Codethink Limited -# -# This program is free software; you can redistribute it and/or modify -# it under the terms of the GNU General Public License as published by -# the Free Software Foundation; version 2 of the License. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License along -# with this program; if not, write to the Free Software Foundation, Inc., -# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - - -import unittest - -import morphlib - - -class FakeSource(object): - pass - - -class BuildOrderTests(unittest.TestCase): - - def test_empty_list_results_in_no_groups_at_all(self): - order = morphlib.buildorder.BuildOrder([]) - self.assertEqual(len(order.groups), 0) - - def test_list_with_one_artifact_results_in_one_group(self): - chunk = FakeSource() - artifact = morphlib.artifact.Artifact(chunk, 'chunk') - - order = morphlib.buildorder.BuildOrder([artifact]) - - self.assertEqual(len(order.groups), 1) - self.assertEqual(order.groups[0], [artifact]) - - def test_list_with_two_unrelated_artifacts_results_in_one_group(self): - chunk1 = FakeSource() - artifact1 = morphlib.artifact.Artifact(chunk1, 'chunk1') - - chunk2 = FakeSource() - artifact2 = morphlib.artifact.Artifact(chunk2, 'chunk2') - - order = morphlib.buildorder.BuildOrder([artifact1, artifact2]) - - self.assertEqual(len(order.groups), 1) - self.assertEqual(order.groups[0], [artifact1, artifact2]) - - def test_list_with_two_dependent_artifacts_results_in_two_groups(self): - chunk1 = FakeSource() - artifact1 = morphlib.artifact.Artifact(chunk1, 'chunk1') - - chunk2 = FakeSource() - artifact2 = morphlib.artifact.Artifact(chunk2, 'chunk2') - artifact2.add_dependency(artifact1) - - order = morphlib.buildorder.BuildOrder([artifact1, artifact2]) - - self.assertEqual(len(order.groups), 2) - self.assertEqual(order.groups[0], [artifact1]) - self.assertEqual(order.groups[1], [artifact2]) - - def test_chain_of_three_dependent_artifacts_results_in_three_groups(self): - chunk1 = FakeSource() - artifact1 = morphlib.artifact.Artifact(chunk1, 'chunk1') - - chunk2 = FakeSource() - artifact2 = morphlib.artifact.Artifact(chunk2, 'chunk2') - artifact2.add_dependency(artifact1) - - chunk3 = FakeSource() - artifact3 = morphlib.artifact.Artifact(chunk3, 'chunk3') - artifact3.add_dependency(artifact2) - - order = morphlib.buildorder.BuildOrder( - [artifact1, artifact2, artifact3]) - - self.assertEqual(len(order.groups), 3) - self.assertEqual(order.groups[0], [artifact1]) - self.assertEqual(order.groups[1], [artifact2]) - self.assertEqual(order.groups[2], [artifact3]) - - def test_two_artifacts_depending_on_another_results_in_two_groups(self): - chunk1 = FakeSource() - artifact1 = morphlib.artifact.Artifact(chunk1, 'chunk1') - - chunk2 = FakeSource() - artifact2 = morphlib.artifact.Artifact(chunk2, 'chunk2') - artifact2.add_dependency(artifact1) - - chunk3 = FakeSource() - artifact3 = morphlib.artifact.Artifact(chunk3, 'chunk3') - artifact3.add_dependency(artifact1) - - order = morphlib.buildorder.BuildOrder( - [artifact1, artifact2, artifact3]) - - self.assertEqual(len(order.groups), 2) - self.assertEqual(order.groups[0], [artifact1]) - self.assertEqual(order.groups[1], [artifact2, artifact3]) - - def test_one_artifact_depending_on_two_others_results_in_two_groups(self): - chunk1 = FakeSource() - artifact1 = morphlib.artifact.Artifact(chunk1, 'chunk1') - - chunk2 = FakeSource() - artifact2 = morphlib.artifact.Artifact(chunk2, 'chunk2') - - chunk3 = FakeSource() - artifact3 = morphlib.artifact.Artifact(chunk3, 'chunk3') - artifact3.add_dependency(artifact1) - artifact3.add_dependency(artifact2) - - order = morphlib.buildorder.BuildOrder( - [artifact1, artifact2, artifact3]) - - self.assertEqual(len(order.groups), 2) - self.assertEqual(order.groups[0], [artifact1, artifact2]) - self.assertEqual(order.groups[1], [artifact3]) - - def test_detection_of_cyclic_dependency_chain(self): - chunk1 = FakeSource() - artifact1 = morphlib.artifact.Artifact(chunk1, 'chunk1') - - chunk2 = FakeSource() - artifact2 = morphlib.artifact.Artifact(chunk2, 'chunk2') - - chunk3 = FakeSource() - artifact3 = morphlib.artifact.Artifact(chunk3, 'chunk3') - - artifact1.add_dependency(artifact3) - artifact2.add_dependency(artifact1) - artifact3.add_dependency(artifact2) - - self.assertRaises(morphlib.buildorder.CyclicDependencyChainError, - morphlib.buildorder.BuildOrder, - [artifact1, artifact2, artifact3]) |