Add the new BuildGraph class including tests.

This class takes a source pool and computes a valid build order for
the sources in this pool, if possible.

4 files changed, 1044 insertions, 0 deletions

diff --git a/morphlib/__init__.py b/morphlib/__init__.py
index c588e191..6b0e955b 100644
--- a/morphlib/__init__.py
+++ b/morphlib/__init__.py
@@ -21,6 +21,7 @@ import bins
 import blobs
 import buildcontroller
 import builddependencygraph
+import buildgraph
 import buildsystem
 import buildworker
 import builder
diff --git a/morphlib/buildgraph.py b/morphlib/buildgraph.py
new file mode 100644
index 00000000..d95e7bc1
--- /dev/null
+++ b/morphlib/buildgraph.py
@@ -0,0 +1,208 @@
+# 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 MutualDependencyError(cliapp.AppException):
+
+    def __init__(self, a, b):
+        cliapp.AppException.__init__(
+                self, 'Cyclic dependency between %s and %s detected' % (a, b))
+
+
+class CyclicDependencyChainError(cliapp.AppException):
+
+    def __init__(self):
+        cliapp.AppException.__init__(
+                self, 'Cyclic dependency detected somewhere')
+
+
+class DependencyOrderError(cliapp.AppException):
+
+    def __init__(self, stratum, chunk, dependency_name):
+        cliapp.AppException.__init__(
+                self, 'In stratum %s, chunk %s references its dependency %s '
+                'before it is defined' % (stratum, chunk, dependency_name))
+
+
+class DependencyFormatError(cliapp.AppException):
+
+    def __init__(self, stratum, chunk):
+        cliapp.AppException.__init__(
+                self, 'In stratum %s, chunk %s uses an invalid '
+                'build-depends format' % (stratum, chunk))
+
+
+class BuildGraph(object):
+
+    def compute_build_order(self, source_pool):
+        self._realise_dependencies(source_pool)
+        sorting = self._compute_topological_sorting(source_pool)
+        groups = self._create_build_groups(sorting)
+        return groups
+
+    def _realise_dependencies(self, source_pool):
+        queue = collections.deque(source_pool)
+        while queue:
+            source = queue.popleft()
+
+            if source.morphology['kind'] == 'system':
+                self._realise_system_dependencies(source, queue, source_pool)
+            elif source.morphology['kind'] == 'stratum':
+                self._realise_stratum_dependencies(source, queue, source_pool)
+
+    def _realise_system_dependencies(self, system, queue, source_pool):
+        for stratum_name in system.morphology['strata']:
+            stratum = source_pool.lookup(
+                    system.repo,
+                    system.original_ref,
+                    '%s.morph' % stratum_name)
+            
+            system.add_dependency(stratum)
+            queue.append(stratum)
+
+    def _realise_stratum_dependencies(self, stratum, queue, source_pool):
+        strata = []
+
+        if stratum.morphology['build-depends']:
+            for stratum_name in stratum.morphology['build-depends']:
+                other_stratum = source_pool.lookup(
+                        stratum.repo,
+                        stratum.original_ref,
+                        '%s.morph' % stratum_name)
+                strata.append(other_stratum)
+
+                if other_stratum.depends_on(stratum):
+                    raise MutualDependencyError(stratum, other_stratum)
+
+                stratum.add_dependency(other_stratum)
+                queue.append(other_stratum)
+
+        chunks = []
+        processed_chunks = []
+        name_to_processed_chunk = {}
+
+        for info in stratum.morphology['sources']:
+            chunk = source_pool.lookup(
+                    info['repo'],
+                    info['ref'],
+                    '%s.morph' % info['morph'])
+            chunks.append(chunk)
+
+            stratum.add_dependency(chunk)
+
+            for other_stratum in strata:
+                chunk.add_dependency(other_stratum)
+
+            build_depends = info.get('build-depends', None)
+
+            if build_depends is None:
+                for earlier_chunk in processed_chunks:
+                    if earlier_chunk.depends_on(chunk):
+                        raise MutualDependencyError(chunk, earlier_chunk)
+                    chunk.add_dependency(earlier_chunk)
+            elif isinstance(build_depends, list):
+                for name in build_depends:
+                    other_chunk = name_to_processed_chunk.get(name, None)
+                    if other_chunk:
+                        chunk.add_dependency(other_chunk)
+                    else:
+                        raise DependencyOrderError(stratum, info['name'], name)
+            else:
+                raise DependencyFormatError(stratum, info['name'])
+            processed_chunks.append(chunk)
+            name_to_processed_chunk[info['name']] = chunk
+
+    def _compute_topological_sorting(self, source_pool):
+        '''Computes a topological sorting of the build graph. 
+        
+        A topological sorting basically is the result of a series of
+        breadth-first searches starting at each leaf node (sources with no
+        dependencies). Sources are added to the sorting as soon as all their
+        dependencies have been added (which means that by then, all
+        dependencies are satisfied).
+
+        For more information, see
+        http://en.wikipedia.org/wiki/Topological_sorting.
+        
+        '''
+
+        # map sources to sets of satisfied dependencies. this is to detect when
+        # we can actually add sources to the BFS queue. rather than dropping
+        # links between nodes, like most topological sorting algorithms do,
+        # we simply remember all satisfied dependencies and check if all
+        # of them are met repeatedly
+        satisfied_dependencies = {}
+
+        # create an empty sorting
+        sorting = collections.deque()
+
+        # create a set of leafs to start the DFS from
+        leafs = collections.deque()
+        for source in source_pool:
+            satisfied_dependencies[source] = set()
+            if len(source.dependencies) == 0:
+                leafs.append(source)
+
+        while len(leafs) > 0:
+            # fetch a leaf source from the DFS queue
+            source = leafs.popleft()
+
+            # add it to the sorting
+            sorting.append(source)
+
+            # mark this dependency as resolved
+            for dependent in source.dependents:
+                satisfied_dependencies[dependent].add(source)
+
+                # add the dependent blob as a leaf if all
+                # its dependencies have been resolved
+                has = len(satisfied_dependencies[dependent])
+                needs = len(dependent.dependencies)
+                if has == needs:
+                    leafs.append(dependent)
+
+        # if not all dependencies were resolved on the way, we
+        # have found at least one cyclic dependency
+        if len(sorting) < len(source_pool):
+            raise CyclicDependencyChainError()
+
+        return sorting
+
+    def _create_build_groups(self, sorting):
+        groups = collections.deque()
+
+        if sorting:
+            # create the first group
+            group = []
+            groups.append(group)
+
+            # traverse the build graph in topological order
+            for source in sorting:
+                # add the current item to the current group, or a new group
+                # if one of its dependencies is in the current one
+                create_group = False
+                for dependency in source.dependencies:
+                    if dependency in group:
+                        create_group = True
+                if create_group:
+                    group = []
+                    groups.append(group)
+                group.append(source)
+
+        return groups
diff --git a/morphlib/buildgraph_tests.py b/morphlib/buildgraph_tests.py
new file mode 100644
index 00000000..8ab32f78
--- /dev/null
+++ b/morphlib/buildgraph_tests.py
@@ -0,0 +1,833 @@
+# 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 collections
+import unittest
+
+import morphlib.buildgraph
+import morphlib.source
+
+
+class BuildGraphTests(unittest.TestCase):
+
+    def setUp(self):
+        self.graph = morphlib.buildgraph.BuildGraph()
+
+    def test_create_empty_build_order_for_empty_pool(self):
+        pool = morphlib.sourcepool.SourcePool()
+        order = self.graph.compute_build_order(pool)
+        self.assertEqual(order, collections.deque())
+
+    def test_build_order_with_a_single_chunk(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "foo",
+                    "kind": "chunk",
+                    "artifacts": {
+                        "foo-runtime": [ "usr/bin" ],
+                        "foo-devel":   [ "usr/lib" ]
+                    }
+                }
+                ''')
+        source = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'foo.morph')
+        pool.add(source)
+        
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+                [source]
+        ])
+        self.assertEqual(order, desired_order)
+
+    def test_build_order_with_a_single_empty_stratum(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "foo",
+                    "kind": "stratum"
+                }
+                ''')
+        source = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'foo.morph')
+        pool.add(source)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+                [source]
+        ])
+        self.assertEqual(order, desired_order)
+
+    def test_build_order_with_a_single_empty_system(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "foo",
+                    "kind": "system"
+                }
+                ''')
+        source = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'foo.morph')
+        pool.add(source)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+                [source]
+        ])
+        self.assertEqual(order, desired_order)
+
+    def test_build_order_with_a_one_chunk_stratum(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "stratum",
+                    "kind": "stratum",
+                    "sources": [
+                        {
+                            "name": "chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        }
+                    ]
+                }
+                ''')
+        stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'stratum.morph')
+        pool.add(stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "chunk",
+                    "kind": "chunk",
+                    "artifacts": {
+                        "foo-runtime": [ "usr/bin" ],
+                        "foo-devel":   [ "usr/lib" ]
+                    }
+                }
+                ''')
+        chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'chunk.morph')
+        pool.add(chunk)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+            [chunk],
+            [stratum]
+        ])
+        self.assertEqual(order, desired_order)
+
+        self.assertEqual(stratum.dependencies, [chunk])
+
+    def test_build_order_with_a_one_chunk_artifact_stratum(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "stratum",
+                    "kind": "stratum",
+                    "sources": [
+                        {
+                            "name": "chunk-runtime",
+                            "morph": "chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        }
+                    ]
+                }
+                ''')
+        stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'stratum.morph')
+        pool.add(stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "chunk",
+                    "kind": "chunk",
+                    "artifacts": {
+                        "foo-runtime": [ "usr/bin" ],
+                        "foo-devel":   [ "usr/lib" ]
+                    }
+                }
+                ''')
+        chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'chunk.morph')
+        pool.add(chunk)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+            [chunk],
+            [stratum]
+        ])
+        self.assertEqual(order, desired_order)
+
+        self.assertEqual(stratum.dependencies, [chunk])
+
+    def test_build_order_with_stratum_and_implicit_dependencies(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "stratum",
+                    "kind": "stratum",
+                    "sources": [
+                        {
+                            "name": "first-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        },
+                        {
+                            "name": "second-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        },
+                        {
+                            "name": "third-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        }
+                    ]
+                }
+                ''')
+        stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'stratum.morph')
+        pool.add(stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        first_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-chunk.morph')
+        pool.add(first_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        second_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-chunk.morph')
+        pool.add(second_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "third-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        third_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'third-chunk.morph')
+        pool.add(third_chunk)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+            [first_chunk],
+            [second_chunk],
+            [third_chunk],
+            [stratum]
+        ])
+        self.assertEqual(order, desired_order)
+
+        self.assertEqual(first_chunk.dependencies, [])
+        self.assertEqual(second_chunk.dependencies, [first_chunk])
+        self.assertEqual(third_chunk.dependencies, [first_chunk, second_chunk])
+        self.assertEqual(stratum.dependencies,
+                         [first_chunk, second_chunk, third_chunk])
+
+    def test_build_order_with_explicit_dependencies(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "stratum",
+                    "kind": "stratum",
+                    "sources": [
+                        {
+                            "name": "first-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref",
+                            "build-depends": []
+                        },
+                        {
+                            "name": "second-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref",
+                            "build-depends": []
+                        },
+                        {
+                            "name": "third-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref",
+                            "build-depends": [
+                                "first-chunk",
+                                "second-chunk"
+                            ]
+                        }
+                    ]
+                }
+                ''')
+        stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'stratum.morph')
+        pool.add(stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        first_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-chunk.morph')
+        pool.add(first_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        second_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-chunk.morph')
+        pool.add(second_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "third-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        third_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'third-chunk.morph')
+        pool.add(third_chunk)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+            [first_chunk, second_chunk],
+            [third_chunk],
+            [stratum]
+        ])
+        self.assertEqual(order, desired_order)
+
+        self.assertEqual(first_chunk.dependencies, [])
+        self.assertEqual(second_chunk.dependencies, [])
+        self.assertEqual(third_chunk.dependencies, [first_chunk, second_chunk])
+        self.assertEqual(stratum.dependencies,
+                         [first_chunk, second_chunk, third_chunk])
+
+    def test_build_order_with_stratum_dependencies(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-stratum",
+                    "kind": "stratum"
+                }
+                ''')
+        first_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-stratum.morph')
+        pool.add(first_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-stratum",
+                    "kind": "stratum",
+                    "build-depends": [
+                        "first-stratum"
+                    ]
+                }
+                ''')
+        second_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-stratum.morph')
+        pool.add(second_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "third-stratum",
+                    "kind": "stratum",
+                    "build-depends": [
+                        "second-stratum"
+                    ]
+                }
+                ''')
+        third_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'third-stratum.morph')
+        pool.add(third_stratum)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+            [first_stratum],
+            [second_stratum],
+            [third_stratum]
+        ])
+        self.assertEqual(order, desired_order)
+
+        self.assertEqual(first_stratum.dependencies, [])
+        self.assertEqual(second_stratum.dependencies, [first_stratum])
+        self.assertEqual(third_stratum.dependencies, [second_stratum])
+
+    def test_build_order_with_stratum_and_chunk_dependencies(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-stratum",
+                    "kind": "stratum"
+                }
+                ''')
+        first_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-stratum.morph')
+        pool.add(first_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-stratum",
+                    "kind": "stratum",
+                    "build-depends": [
+                        "first-stratum"
+                    ],
+                    "sources": [
+                        {
+                            "name": "first-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        },
+                        {
+                            "name": "second-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        }
+                    ]
+                }
+                ''')
+        second_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-stratum.morph')
+        pool.add(second_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        first_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-chunk.morph')
+        pool.add(first_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        second_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-chunk.morph')
+        pool.add(second_chunk)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+            [first_stratum],
+            [first_chunk],
+            [second_chunk],
+            [second_stratum]
+        ])
+        self.assertEqual(order, desired_order)
+
+        self.assertEqual(first_stratum.dependencies, [])
+        self.assertEqual(first_chunk.dependencies, [first_stratum])
+        self.assertEqual(second_chunk.dependencies,
+                         [first_stratum, first_chunk])
+        self.assertEqual(second_stratum.dependencies,
+                         [first_stratum, first_chunk, second_chunk])
+
+    def test_build_order_with_a_system_and_two_strata(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-stratum",
+                    "kind": "stratum"
+                }
+                ''')
+        first_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-stratum.morph')
+        pool.add(first_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-stratum",
+                    "kind": "stratum"
+                }
+                ''')
+        second_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-stratum.morph')
+        pool.add(second_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "system",
+                    "kind": "system",
+                    "strata": [
+                        "first-stratum",
+                        "second-stratum"
+                    ]
+                }
+                ''')
+        system = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'system.morph')
+        pool.add(system)
+
+        order = self.graph.compute_build_order(pool)
+        desired_order = collections.deque([
+            [first_stratum, second_stratum],
+            [system]
+        ])
+        self.assertEqual(order, desired_order)
+
+        self.assertEqual(first_stratum.dependencies, [])
+        self.assertEqual(second_stratum.dependencies, [])
+        self.assertEqual(system.dependencies, [first_stratum, second_stratum])
+
+    def test_detection_of_mutual_dependency_between_two_strata(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-stratum",
+                    "kind": "stratum",
+                    "build-depends": [
+                        "second-stratum"
+                    ]
+                }
+                ''')
+        first_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-stratum.morph')
+        pool.add(first_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-stratum",
+                    "kind": "stratum",
+                    "build-depends": [
+                        "first-stratum"
+                    ]
+                }
+                ''')
+        second_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-stratum.morph')
+        pool.add(second_stratum)
+
+        self.assertRaises(morphlib.buildgraph.MutualDependencyError,
+                          self.graph.compute_build_order, pool)
+
+    def test_detection_of_mutual_dependency_between_consecutive_chunks(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-stratum",
+                    "kind": "stratum",
+                    "sources": [
+                        {
+                            "name": "first-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        },
+                        {
+                            "name": "second-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        }
+                    ]
+                }
+                ''')
+        first_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-stratum.morph')
+        pool.add(first_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-stratum",
+                    "kind": "stratum",
+                    "build-depends": [
+                        "first-stratum"
+                    ],
+                    "sources": [
+                        {
+                            "name": "second-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        },
+                        {
+                            "name": "first-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        }
+                    ]
+                }
+                ''')
+        second_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-stratum.morph')
+        pool.add(second_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        first_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-chunk.morph')
+        pool.add(first_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        second_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-chunk.morph')
+        pool.add(second_chunk)
+
+        self.assertRaises(morphlib.buildgraph.MutualDependencyError,
+                          self.graph.compute_build_order, pool)
+
+    def test_detection_of_cyclic_chunk_dependency_chain(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-stratum",
+                    "kind": "stratum",
+                    "sources": [
+                        {
+                            "name": "first-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        },
+                        {
+                            "name": "second-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref",
+                            "build-depends": [
+                                "first-chunk"
+                            ]
+                        },
+                        {
+                            "name": "third-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref",
+                            "build-depends": [
+                                "second-chunk"
+                            ]
+                        }
+                    ]
+                }
+                ''')
+        first_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-stratum.morph')
+        pool.add(first_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-stratum",
+                    "kind": "stratum",
+                    "build-depends": [
+                        "first-stratum"
+                    ],
+                    "sources": [
+                        {
+                            "name": "third-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        },
+                        {
+                            "name": "first-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        }
+                    ]
+                }
+                ''')
+        second_stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-stratum.morph')
+        pool.add(second_stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        first_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-chunk.morph')
+        pool.add(first_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        second_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-chunk.morph')
+        pool.add(second_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "third-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        second_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'third-chunk.morph')
+        pool.add(second_chunk)
+
+        self.assertRaises(morphlib.buildgraph.CyclicDependencyChainError,
+                          self.graph.compute_build_order, pool)
+
+    def test_detection_of_chunk_dependencies_in_invalid_order(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "stratum",
+                    "kind": "stratum",
+                    "sources": [
+                        {
+                            "name": "first-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref",
+                            "build-depends": [
+                                "second-chunk"
+                            ]
+                        },
+                        {
+                            "name": "second-chunk",
+                            "repo": "repo",
+                            "ref": "original/ref"
+                        }
+                    ]
+                }
+                ''')
+        stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'stratum.morph')
+        pool.add(stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "first-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        first_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'first-chunk.morph')
+        pool.add(first_chunk)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "second-chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        second_chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'second-chunk.morph')
+        pool.add(second_chunk)
+
+        self.assertRaises(morphlib.buildgraph.DependencyOrderError,
+                          self.graph.compute_build_order, pool)
+
+    def test_detection_of_invalid_build_depends_format(self):
+        pool = morphlib.sourcepool.SourcePool()
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "stratum",
+                    "kind": "stratum",
+                    "sources": [
+                        {
+                            "name": "chunk",
+                            "repo": "repo",
+                            "ref": "original/ref",
+                            "build-depends": "whatever"
+                        }
+                    ]
+                }
+                ''')
+        stratum = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'stratum.morph')
+        pool.add(stratum)
+
+        morph = morphlib.morph2.Morphology(
+                '''
+                {
+                    "name": "chunk",
+                    "kind": "chunk"
+                }
+                ''')
+        chunk = morphlib.source.Source(
+                'repo', 'original/ref', 'sha1', morph, 'chunk.morph')
+        pool.add(chunk)
+
+        self.assertRaises(morphlib.buildgraph.DependencyFormatError,
+                          self.graph.compute_build_order, pool)
diff --git a/morphlib/source.py b/morphlib/source.py
index cfcd320b..4e36e189 100644
--- a/morphlib/source.py
+++ b/morphlib/source.py
@@ -56,3 +56,5 @@ class Source(object):
         '''Do we depend on ``source``?'''
         return source in self.dependencies
 
+    def __str__(self): # pragma: no cover
+        return '%s|%s|%s' % (self.repo, self.sha1, self.filename)