Stop computing the old build ordering

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])