Introduce the "show-dependencies" command and BuildDependencyGraph.

The "show-dependencies" command takes a series of build tuples and dumps
the resulting dependency graph (including strata and chunks at the
moment) to the standard output. It also dumps the resulting build order
which is a list of groups. These groups indicate which chunks and strata
can be built in parallel and are not dependent on each other.

6 files changed, 315 insertions, 8 deletions

diff --git a/morphlib/__init__.py b/morphlib/__init__.py
index 9787846e..35939c45 100644
--- a/morphlib/__init__.py
+++ b/morphlib/__init__.py
@@ -1,4 +1,4 @@
-# Copyright (C) 2011  Codethink Limited
+# Copyright (C) 2011-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
@@ -21,6 +21,7 @@ __version__ = '0.0'
 
 
 import bins
+import builddependencygraph
 import builder
 import cachedir
 import execute
diff --git a/morphlib/builddependencygraph.py b/morphlib/builddependencygraph.py
new file mode 100644
index 00000000..146cdc54
--- /dev/null
+++ b/morphlib/builddependencygraph.py
@@ -0,0 +1,291 @@
+# 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 copy
+import os
+
+import morphlib
+
+
+class Node(object):
+
+    '''Node in the dependency graph.'''
+
+    def __init__(self, morphology):
+        self.morphology = morphology
+        self.dependents = []
+        self.dependencies = []
+
+    def add_dependency(self, other):
+        if other not in self.dependencies:
+            self.dependencies.append(other)
+        if self not in other.dependents:
+            other.dependents.append(self)
+
+    def remove_dependency(self, other):
+        if other in self.dependencies:
+            self.dependencies.remove(other)
+        if self in other.dependents:
+            other.dependents.remove(self)
+
+    def depends_on(self, other):
+        return other in self.dependencies
+
+    def __str__(self):
+        return '%s (%s)' % (self.morphology.name, self.morphology.kind)
+
+    def __deepcopy__(self, memo):
+        return Node(self.morphology)
+
+
+class NodeList(list):
+
+    def __deepcopy__(self, memo):
+        nodes = NodeList()
+        
+        old_to_new = {}
+        
+        for node in self:
+            node_copy = copy.deepcopy(node)
+            old_to_new[node] = node_copy
+            nodes.append(node_copy)
+
+        for node in self:
+            node_copy = old_to_new[node]
+            for dep in node.dependencies:
+                dep_copy = old_to_new[dep]
+                node_copy.add_dependency(dep_copy)
+
+        return nodes
+
+
+class BuildDependencyGraph(object):
+    
+    def __init__(self, loader, morphology):
+        self.loader = loader
+        self.morphology = morphology
+        self.nodes = None
+
+    def add(self, morphology):
+        node = Node(morphology)
+        if node not in self.nodes:
+            self.nodes.append(node)
+
+    def resolve(self):
+        self.cached_morphologies = {}
+        self._resolve_strata()
+        self._resolve_chunks()
+
+    def build_order(self):
+        sorting = self._compute_topological_sorting()
+
+        #print
+        #print 'sorting: %s' % [str(x) for x in sorting]
+        #print
+
+        groups = []
+        group_nodes = {}
+
+        group = []
+        groups.append(group)
+
+        for node in sorting:
+            create_group = False
+            for dep in node.dependencies:
+                if dep in group:
+                    create_group = True
+
+            if create_group:
+                group = []
+                groups.append(group)
+
+            group.append(node)
+
+        morphology_groups = []
+        for group in groups:
+            morphology_group = []
+            for node in group:
+                morphology_group.append(node.morphology)
+            morphology_groups.append(morphology_group)
+
+        return morphology_groups
+
+    def _resolve_strata(self):
+        self.nodes = NodeList()
+
+        if self.morphology.kind == 'stratum':
+            root = Node(self.morphology)
+            self.nodes.append(root)
+
+            queue = collections.deque()
+            queue.append(root)
+            while len(queue) > 0:
+                node = queue.popleft()
+
+                if not node.morphology.build_depends:
+                    continue
+                
+                if isinstance(node.morphology.build_depends, list):
+                    for other_name in node.morphology.build_depends:
+                        # prepare a tuple for loading the morphology
+                        repo = node.morphology.repo
+                        ref = node.morphology.ref
+                        filename = '%s.morph' % other_name
+                        info = (repo, ref, filename)
+
+                        # look up or create a node for the morphology
+                        other_node = self.cached_morphologies.get(info, None)
+                        if not other_node:
+                            #print other_name
+                            morphology = self.loader.load(repo, ref, filename)
+                            other_node = Node(morphology)
+
+                            # cache the node for this morphology
+                            self.cached_morphologies[info] = other_node
+
+                        # add the morphology node to the graph
+                        node.add_dependency(other_node)
+                        self.nodes.append(other_node)
+                        queue.append(other_node)
+                else:
+                    raise Exception('%s  uses an invalid "build-depends" format' % 
+                                    os.path.basename(stratum_node.morphology.filename))
+
+        #print 'strata: %s' % [str(x) for x in self.nodes]
+
+    def _resolve_chunks(self):
+        strata_nodes = list(self.nodes)
+        for stratum_node in strata_nodes:
+            self._resolve_stratum_chunks(stratum_node)
+
+    def _morphology_node(self, repo, ref, filename):
+        info = (repo, ref, filename)
+        
+        if info in self.cached_morphologies:
+            return self.cached_morphologies[info]
+        else:
+            morphology = self.loader.load(repo, ref, filename)
+            node = Node(morphology)
+            self.nodes.append(node)
+            self.cached_morphologies[info] = node
+            return node
+
+    def _resolve_stratum_chunks(self, stratum_node):
+        stratum_chunk_nodes = []
+        chunk_lookup = {}
+
+        # second, create nodes for all chunks in the stratum
+        for i in xrange(0, len(stratum_node.morphology.sources)):
+            source = stratum_node.morphology.sources[i]
+
+            # construct the build tuple
+            repo = source['repo']
+            ref = source['ref']
+            filename = '%s.morph' % (source['morph']
+                                     if 'morph' in source
+                                     else source['name'])
+
+            chunk_node = self._morphology_node(repo, ref, filename)
+
+            chunk_lookup[source['name']] = chunk_node
+
+            stratum_chunk_nodes.append(chunk_node)
+
+            # read the build-depends information
+            build_depends = (source['build-depends']
+                             if 'build-depends' in source
+                             else None)
+
+            # turn build-depends into proper dependencies in the graph
+            if build_depends is None:
+                for j in xrange(0, i):
+                    chunk_node.add_dependency(stratum_chunk_nodes[j])
+            elif isinstance(build_depends, list):
+                for depname in build_depends:
+                    if depname in chunk_lookup:
+                        depnode = chunk_lookup[depname]
+                        chunk_node.add_dependency(depnode)
+                    else:
+                        raise Exception('%s: source "%s" references "%s" '
+                                        'before it is defined' % 
+                                        (os.path.basename(stratum_node.morphology.filename),
+                                         source['name'],
+                                         depname))
+            else:
+                raise Exception('%s: source "%s" uses an invalid '
+                                '"build-depends" format' % 
+                                (os.path.basename(stratum_node.morphology.filename),
+                                 source['name']))
+
+        # make the chunk nodes in this stratum depend on all strata
+        # that need to be built first
+        for chunk_node in stratum_chunk_nodes:
+            for stratum_dep in stratum_node.dependencies:
+                chunk_node.add_dependency(stratum_dep)
+
+        # clear the dependencies of the stratum
+        stratum_node.dependencies = []
+
+        # make the stratum node depend on all its chunk nodes
+        for chunk_node in stratum_chunk_nodes:
+            stratum_node.add_dependency(chunk_node)
+
+    def _compute_topological_sorting(self):
+        nodes = copy.deepcopy(self.nodes)
+
+        original_node = {}
+        for node in self.nodes:
+            for node_copy in nodes:
+                if node.morphology == node_copy.morphology:
+                    original_node[node_copy] = node
+
+        #print 'compute topological sorting:'
+        #print '  nodes: %s' % [str(x) for x in nodes]
+
+        sorting = []
+        leafs = collections.deque()
+        
+        for node in nodes:
+            if len(node.dependencies) is 0:
+                leafs.append(node)
+
+        #print '  leafs: %s' % [str(x) for x in leafs]
+
+        while len(leafs) > 0:
+            leaf = leafs.popleft()
+            sorting.append(leaf)
+
+            #print '  visit %s' % leaf
+
+            #print '  visit %s' % leaf
+
+            for parent in list(leaf.dependents):
+                #print '    parent %s' % parent
+                #print '    parent %s dependencies: %s' % (parent, [str(x) for x in parent.dependencies])
+                parent.remove_dependency(leaf)
+                #print '    parent %s dependencies: %s' % (parent, [str(x) for x in parent.dependencies])
+                if len(parent.dependencies) == 0:
+                    #print '    add %s' % parent
+                    leafs.append(parent)
+
+        #print [str(node) for node in sorting]
+        if len(sorting) < len(nodes):
+            raise Exception('Cyclic dependencies found in the dependency '
+                            'graph of "%s"' % self.morphology)
+
+        #return sorting
+        return [original_node[node] for node in sorting]
diff --git a/morphlib/builder.py b/morphlib/builder.py
index 69f896a8..88a46633 100644
--- a/morphlib/builder.py
+++ b/morphlib/builder.py
@@ -481,11 +481,8 @@ class Builder(object):
         self.dump_memory_profile('at start of build method')
         self.indent_more()
         self.msg('build %s|%s|%s' % (repo, ref, filename))
-        base_url = self.settings['git-base-url']
-        if not base_url.endswith('/'):
-            base_url += '/'
-        repo = urlparse.urljoin(base_url, repo)
         morph = self.morph_loader.load(repo, ref, filename)
+        repo = morph.repo
         self.dump_memory_profile('after getting morph from git')
 
         if morph.kind == 'chunk':
diff --git a/morphlib/morphology.py b/morphlib/morphology.py
index 0dcb03f7..9059e9b9 100644
--- a/morphlib/morphology.py
+++ b/morphlib/morphology.py
@@ -22,7 +22,10 @@ class Morphology(object):
 
     '''Represent a morphology: description of how to build binaries.'''
     
-    def __init__(self, fp, baseurl=None):
+    def __init__(self, repo, ref, fp, baseurl=None):
+        self.repo = repo
+        self.ref = ref
+
         self._fp = fp
         self._baseurl = baseurl or ''
         self._load()
@@ -58,7 +61,7 @@ class Morphology(object):
 
     @property
     def build_depends(self):
-        return self._dict.get('build-depends', [])
+        return self._dict.get('build-depends', None)
 
     @property
     def build_system(self):
diff --git a/morphlib/morphology_tests.py b/morphlib/morphology_tests.py
index 0119ebc6..cac80798 100644
--- a/morphlib/morphology_tests.py
+++ b/morphlib/morphology_tests.py
@@ -32,6 +32,7 @@ class MorphologyTests(unittest.TestCase):
 
     def test_accepts_valid_chunk_morphology(self):
         morph = morphlib.morphology.Morphology(
+                          'repo', 'ref',
                           MockFile('''
                             {
                                 "name": "hello",
@@ -57,6 +58,10 @@ class MorphologyTests(unittest.TestCase):
                                     ]
                                 }
                             }'''))
+
+        self.assertEqual(morph.repo, 'repo')
+        self.assertEqual(morph.ref, 'ref')
+        self.assertEqual(morph.filename, 'mockfile')
         self.assertEqual(morph.name, 'hello')
         self.assertEqual(morph.kind, 'chunk')
         self.assertEqual(morph.description, 'desc')
@@ -77,6 +82,7 @@ class MorphologyTests(unittest.TestCase):
 
     def test_build_system_defaults_to_None(self):
         morph = morphlib.morphology.Morphology(
+                          'repo', 'ref',
                           MockFile('''
                             {
                                 "name": "hello",
@@ -86,6 +92,7 @@ class MorphologyTests(unittest.TestCase):
 
     def test_max_jobs_defaults_to_None(self):
         morph = morphlib.morphology.Morphology(
+                          'repo', 'ref',
                           MockFile('''
                             {
                                 "name": "hello",
@@ -95,6 +102,7 @@ class MorphologyTests(unittest.TestCase):
 
     def test_accepts_valid_stratum_morphology(self):
         morph = morphlib.morphology.Morphology(
+                          'repo', 'ref',
                           MockFile('''
                             {
                                 "name": "hello",
@@ -121,6 +129,7 @@ class MorphologyTests(unittest.TestCase):
 
     def test_accepts_valid_system_morphology(self):
         morph = morphlib.morphology.Morphology(
+                          'repo', 'ref',
                           MockFile('''
                             {
                                 "name": "hello",
@@ -145,6 +154,7 @@ class StratumRepoTests(unittest.TestCase):
 
     def stratum(self, repo):
         return morphlib.morphology.Morphology(
+                          'repo', 'ref',
                           MockFile('''
                             {
                                 "name": "hello",
diff --git a/morphlib/morphologyloader.py b/morphlib/morphologyloader.py
index 0a1f6513..a227214f 100644
--- a/morphlib/morphologyloader.py
+++ b/morphlib/morphologyloader.py
@@ -30,6 +30,11 @@ class MorphologyLoader(object):
         self.morphologies = {}
 
     def load(self, repo, ref, filename):
+        base_url = self.settings['git-base-url']
+        if not base_url.endswith('/'):
+            base_url += '/'
+        repo = urlparse.urljoin(base_url, repo)
+
         key = (repo, ref, filename)
         
         if key in self.morphologies:
@@ -47,6 +52,6 @@ class MorphologyLoader(object):
         scheme, netlock, path, params, query, frag = urlparse.urlparse(repo)
         f = StringIO.StringIO(morph_text)
         f.name = os.path.join(path, filename)
-        morph = morphlib.morphology.Morphology(f,
+        morph = morphlib.morphology.Morphology(repo, ref, f,
                                                self.settings['git-base-url'])
         return morph