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.

1 files changed, 291 insertions, 0 deletions

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]