Apply code review changes and fix a bug when clearing dependencies.

4 files changed, 80 insertions, 54 deletions

diff --git a/morph b/morph
index 413944db..729b4323 100755
--- a/morph
+++ b/morph
@@ -199,7 +199,6 @@ class Morph(cliapp.Application):
 
             # compute a build order from the graph
             blobs, order = graph.build_order()
-            sort_func = (lambda x,y : cmp(str(x), str(y)))
             self.output.write('build order:\n')
             for group in order:
                 self.output.write('  group:\n')
diff --git a/morphlib/blobs.py b/morphlib/blobs.py
index 70cd1f90..6ddcaf0c 100644
--- a/morphlib/blobs.py
+++ b/morphlib/blobs.py
@@ -16,15 +16,18 @@
 
 class Blob(object):
 
-    def __init__(self, parent, morph):
-        self.parent = parent
+    def __init__(self, morph):
+        self.parents = []
         self.morph = morph
-        self.dependencies = set()
-        self.dependents = set()
+        self.dependencies = []
+        self.dependents = []
+
+    def add_parent(self, parent):
+        self.parents.append(parent)
 
     def add_dependency(self, other):
-        self.dependencies.add(other)
-        other.dependents.add(self)
+        self.dependencies.append(other)
+        other.dependents.append(self)
 
     def remove_dependency(self, other):
         self.dependencies.remove(other)
diff --git a/morphlib/builddependencygraph.py b/morphlib/builddependencygraph.py
index 8fc85c20..9623a4f0 100644
--- a/morphlib/builddependencygraph.py
+++ b/morphlib/builddependencygraph.py
@@ -22,39 +22,46 @@ import morphlib
 
 class BuildDependencyGraph(object): # pragma: no cover
 
-    '''This class constructs a build dependency graph from an input morphology
-       and provides ways to traverse this graph. It also provides a method to
-       transform the dependency graph into groups of items that are independent
-       and can be built in parallel.'''
+    '''This class constructs a build dependency graph from an input morphology.
+
+    Given a chunk, stratum or system morphology, this class constructs a build
+    dependency graph and provides ways to traverse it. It also provides a 
+    method to transform the dependency graph into groups of items that are 
+    independent and can be built in parallel.
+    
+    '''
     
     def __init__(self, loader, morph):
         self.loader = loader
         self.morph = morph
         self.blobs = set()
 
-    def create_blob(self, morph, parent=None):
-        '''Creates a blob from a morphology. The optional parent is used to
-           associate chunks with their containing stratum.'''
+    def create_blob(self, morph):
+        '''Creates a blob from a morphology.'''
 
         if morph.kind == 'stratum':
-            return morphlib.blobs.Stratum(parent, morph)
+            return morphlib.blobs.Stratum(morph)
         elif morph.kind == 'chunk':
-            return morphlib.blobs.Chunk(parent, morph)
+            return morphlib.blobs.Chunk(morph)
         else:
-            return morphlib.blobs.System(parent, morph)
+            return morphlib.blobs.System(morph)
 
     def resolve(self):
-        '''Constructs the dependency graph by resolving dependencies
-           recursively.'''
+        '''Constructs the graph by resolving dependencies recursively.'''
 
         self.cached_blobs = {}
         self._resolve_strata()
         self._resolve_chunks()
 
     def build_order(self):
-        '''Computes a topological sorting of the dependency graph and
-           generates a deque of groups, each of which contains a set
-           of items that are independent and can be built in parallel.'''
+        '''Returns a queue of build groups in a valid order.
+        
+        This function computes a topological sorting of the dependency graph
+        and generates a deque of groups, each of which contains a set of items
+        that are independent and can be built in parallel. The items in each
+        group are guaranteed to depend only on items in previous groups.
+        
+        '''
 
         sorting = self._compute_topological_sorting()
         groups = collections.deque()
@@ -79,22 +86,29 @@ class BuildDependencyGraph(object): # pragma: no cover
         # return the set of blobs and the build groups
         return set(self.blobs), groups
 
-    def _get_blob(self, info, parent=None):
+    def _get_blob(self, info):
         '''Takes a (repo, ref, filename) tuple and looks up the blob for it.
-           It loads the corresponding morphology and blob on-demand if it is
-           not cached yet.'''
+
+        Loads the corresponding morphology and blob on-demand if it is
+        not cached yet.
+           
+        '''
 
         blob = self.cached_blobs.get(info, None)
         if not blob:
             morphology = self.loader.load(info[0], info[1], info[2])
-            blob = self.create_blob(morphology, parent)
+            blob = self.create_blob(morphology)
             self.cached_blobs[info] = blob
         return blob
 
     def _resolve_strata(self):
-        '''This method recursively generates a dependency graph of strata
-           for the input morphology using breadth-first search. It loads
-           morphologies and blobs on demand.'''
+        '''Generates a dependency graph of strata recursively.
+
+        It starts with the input morphology and attempts to resolve all its
+        build dependencies recursively using breadth-first search. Morphologies
+        and blobs are loaded from disk on demand.
+           
+        '''
 
         if self.morph.kind == 'stratum':
             # turn the morphology into a stratum object
@@ -134,9 +148,13 @@ class BuildDependencyGraph(object): # pragma: no cover
                                     % stratum)
 
     def _resolve_chunks(self):
-        '''Starting with a dependency graph of strata, this method fills the
-           graph with all contained chunks and creates dependencies where 
-           appropriate. Chunk morphologies and blobs are loaded on demand.'''
+        '''Resolves all chunks of the strata and inserts them into the graph.
+        
+        Starting with a dependency graph of strata, this method fills the
+        graph with all contained chunks and creates dependencies where 
+        appropriate. Chunk morphologies and blobs are loaded on demand.
+        
+        '''
 
         if self.morph.kind == 'chunk':
             blob = self.create_blob(self.morph)
@@ -167,7 +185,8 @@ class BuildDependencyGraph(object): # pragma: no cover
             info = (repo, ref, filename)
 
             # load the chunk on demand
-            chunk = self._get_blob(info, stratum)
+            chunk = self._get_blob(info)
+            chunk.add_parent(stratum)
 
             # store (name -> chunk) association to avoid loading the chunk twice
             name_to_chunk[source['name']] = chunk
@@ -210,20 +229,26 @@ class BuildDependencyGraph(object): # pragma: no cover
                 chunk.add_dependency(dependency)
 
         # clear the dependencies of the stratum
-        stratum.dependencies = set()
+        for dependency in set(stratum.dependencies):
+            stratum.remove_dependency(dependency)
 
         # make the stratum depend on all its chunks
         for chunk in stratum_chunks:
             stratum.add_dependency(chunk)
 
     def _compute_topological_sorting(self):
-        '''Computes a topological sorting of the dependency graph. A topological
-           sorting basically is the result of a series of breadth-first searches
-           starting at each leaf node (blobs with no dependencies). Blobs are
-           added to the sorting as soon as all their dependencies have been
-           added (which means that by then, all dependencies are satisfied).
-
-           http://en.wikipedia.org/wiki/Topological_sorting.'''
+        '''Computes a topological sorting of the dependency graph. 
+        
+        A topological sorting basically is the result of a series of
+        breadth-first searches starting at each leaf node (blobs with no
+        dependencies). Blobs 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 blobs to sets of satisfied dependencies. this is to detect when
         # we can actually add blobs to the BFS queue. rather than dropping
diff --git a/morphlib/builder.py b/morphlib/builder.py
index 222e884c..ff5fc3f6 100644
--- a/morphlib/builder.py
+++ b/morphlib/builder.py
@@ -90,7 +90,7 @@ class BlobBuilder(object):
         # if not all build items are in the cache, rebuild the blob
         if not all(os.path.isfile(builds[name]) for name in builds):
             with self.build_watch('overall-build'):
-                built_items += self.do_build()
+                self.do_build()
 
         # check again, fail if not all build items were actually built
         if not all(os.path.isfile(builds[name]) for name in builds):
@@ -99,11 +99,13 @@ class BlobBuilder(object):
 
         # install all build items to the staging area
         for name, filename in builds.items():
-            self.msg('Using cached %s %s at %s' % (self.blob.morph.kind,
-                                                   name, filename))
+            self.msg('Fetching cached %s %s from %s' %
+                     (self.blob.morph.kind, name, filename))
             self.install_chunk(name, filename)
             self.dump_memory_profile('after installing chunk')
 
+            built_items.append((name, filename))
+
         return built_items
 
     def filename(self, name):
@@ -217,7 +219,7 @@ class ChunkBuilder(BlobBuilder):
             'FAKEROOTKEY',
             'FAKED_MODE',
             'FAKEROOT_FD_BASE',
-        ], None)
+        ])
         for name in copied_vars:
             copied_vars[name] = self.ex.env.get(name, None)
 
@@ -523,11 +525,8 @@ class Builder(object):
 
         # second pass: build group by group, item after item
         ret = []
-        while len(build_order) > 0:
-            group = build_order.popleft()
-            while len(group) > 0:
-                blob = group.pop()
-
+        for group in build_order:
+            for blob in group:
                 self.msg('Building %s' % blob)
                 self.indent_more()
 
@@ -546,12 +545,12 @@ class Builder(object):
 
                 built_items = builders[blob].build()
                 
-                if blob.parent:
+                for parent in blob.parents:
                     for item, filename in built_items:
-                        self.msg('Marking %s to be staged for %s' %
-                                 (item, blob.parent))
+                        self.msg('Marking %s to be staged for %s'
+                                 % (item, parent))
 
-                    parent_builder = builders[blob.parent]
+                    parent_builder = builders[parent]
                     parent_builder.stage_items += built_items
 
                 self.indent_less()