Build items as late as possible in the build order.

At the moment this is done by creating a reverse topological sorting
starting with the artifacts that depend on nothing else. Artifacts
are then added to build groups as late as possible.

Fix show-dependencies test output for the new build order generation.

2 files changed, 40 insertions, 39 deletions

diff --git a/morphlib/buildorder.py b/morphlib/buildorder.py
index d07dab50..7e15814f 100644
--- a/morphlib/buildorder.py
+++ b/morphlib/buildorder.py
@@ -31,31 +31,30 @@ class BuildOrder:
         self.artifacts = artifacts
 
         if artifacts:
-            sorting = self._compute_topological_sorting(artifacts)
+            sorting = self._compute_reverse_topological_sorting(artifacts)
             self.groups = self._create_build_groups(sorting)
         else:
             self.groups = []
 
-    def _compute_topological_sorting(self, artifacts):
-        '''Computes a topological sorting of the build graph. 
+    def _compute_reverse_topological_sorting(self, artifacts):
+        '''Computes a reverse topological sorting of the build graph. 
         
-        A topological sorting basically is the result of a series of
+        A reverse topological sorting basically is the result of a series of
         breadth-first searches starting at each leaf node (artifacts with no
-        dependencies). Artifacts are added to the sorting as soon as all their
-        dependencies have been added (which means that by then, all
-        dependencies are satisfied).
+        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 dependencies. this is to detect
+        # 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 dependencies and
+        # algorithms do, we simply remember all satisfied dependents and
         # check if all of them are met repeatedly
-        satisfied_dependencies = {}
+        satisfied_dependents = {}
 
         # create an empty sorting
         sorting = collections.deque()
@@ -63,8 +62,8 @@ class BuildOrder:
         # create a set of leafs to start the DFS from
         leafs = collections.deque()
         for artifact in artifacts:
-            satisfied_dependencies[artifact] = set()
-            if len(artifact.dependencies) == 0:
+            satisfied_dependents[artifact] = set()
+            if len(artifact.dependents) == 0:
                 leafs.append(artifact)
 
         while len(leafs) > 0:
@@ -75,15 +74,15 @@ class BuildOrder:
             sorting.append(artifact)
 
             # mark this dependency as resolved in dependent artifacts
-            for dependent in artifact.dependents:
-                satisfied_dependencies[dependent].add(artifact)
+            for dependency in artifact.dependencies:
+                satisfied_dependents[dependency].add(artifact)
 
                 # add the dependent blob as a leaf if all
-                # its dependencies have been resolved
-                has = len(satisfied_dependencies[dependent])
-                needs = len(dependent.dependencies)
+                # its dependents have been resolved
+                has = len(satisfied_dependents[dependency])
+                needs = len(dependency.dependents)
                 if has == needs:
-                    leafs.append(dependent)
+                    leafs.append(dependency)
 
         # if not all dependencies were resolved on the way, we
         # have found at least one cyclic dependency
@@ -96,21 +95,23 @@ class BuildOrder:
         groups = collections.deque()
 
         if sorting:
-            # create the first group
+            # create the last 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)
+            # 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/tests/show-dependencies.stdout b/tests/show-dependencies.stdout
index 7efd76ca..3938e266 100644
--- a/tests/show-dependencies.stdout
+++ b/tests/show-dependencies.stdout
@@ -98,30 +98,30 @@ dependency graph for test-repo|master|xfce-core.morph:
     -> test-repo|master|xfconf.morph|xfconf
 build order for test-repo|master|xfce-core.morph:
   group:
+    test-repo|master|glib.morph|glib
     test-repo|master|freetype.morph|freetype
     test-repo|master|fontconfig.morph|fontconfig
-    test-repo|master|cairo.morph|cairo
-    test-repo|master|glib.morph|glib
-    test-repo|master|dbus.morph|dbus
   group:
-    test-repo|master|pango.morph|pango
+    test-repo|master|cairo.morph|cairo
     test-repo|master|gdk-pixbuf.morph|gdk-pixbuf
-    test-repo|master|dbus-glib.morph|dbus-glib
+    test-repo|master|pango.morph|pango
+    test-repo|master|dbus.morph|dbus
   group:
     test-repo|master|gtk.morph|gtk
+    test-repo|master|dbus-glib.morph|dbus-glib
   group:
     test-repo|master|gtk-stack.morph|gtk-stack
   group:
     test-repo|master|libxfce4util.morph|libxfce4util
-    test-repo|master|tumbler.morph|tumbler
   group:
     test-repo|master|xfconf.morph|xfconf
-    test-repo|master|exo.morph|exo
-    test-repo|master|garcon.morph|garcon
   group:
+    test-repo|master|exo.morph|exo
     test-repo|master|libxfce4ui.morph|libxfce4ui
+    test-repo|master|garcon.morph|garcon
   group:
     test-repo|master|thunar.morph|thunar
+    test-repo|master|tumbler.morph|tumbler
     test-repo|master|xfce4-panel.morph|xfce4-panel
     test-repo|master|xfce4-settings.morph|xfce4-settings
     test-repo|master|xfce4-session.morph|xfce4-session