diff options
author | Jannis Pohlmann <jannis.pohlmann@codethink.co.uk> | 2012-05-01 15:37:11 +0100 |
---|---|---|
committer | Jannis Pohlmann <jannis.pohlmann@codethink.co.uk> | 2012-05-01 15:21:29 +0000 |
commit | 2e2b8757f8d5dcbfe6ce6f079c22cb61f9972b4b (patch) | |
tree | e3fe5d012002c03b1c6d68bdba0efaa3b3259479 | |
parent | 2d5b60bbbdf1a43d0271f352a0d5f536796002c9 (diff) | |
download | morph-2e2b8757f8d5dcbfe6ce6f079c22cb61f9972b4b.tar.gz |
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.
-rw-r--r-- | morphlib/buildorder.py | 63 | ||||
-rw-r--r-- | tests/show-dependencies.stdout | 16 |
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 |