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.

10 files changed, 835 insertions, 8 deletions

diff --git a/morph b/morph
index f557baa9..360b9a7f 100755
--- a/morph
+++ b/morph
@@ -25,6 +25,7 @@ import logging
 import os
 import shutil
 import tempfile
+import urlparse
 
 import morphlib
 
@@ -149,6 +150,46 @@ class Morph(cliapp.Application):
                 self.msg('not testing %s %s (not a system)' %
                          (morph.kind, morph.name))
 
+    def cmd_show_dependencies(self, args):
+        '''Dumps the dependency tree of all input morphologies.'''
+
+        while len(args) >= 3:
+            # read the build tuple from the command line
+            repo, ref, filename = args[:3]
+            args = args[3:]
+
+            # resolve the URL to the repository
+            base_url = self.settings['git-base-url']
+            if not base_url.endswith('/'):
+                base_url += '/'
+            repo = urlparse.urljoin(base_url, repo)
+
+            # load the morphology corresponding to the build tuple
+            loader = morphlib.morphologyloader.MorphologyLoader(self.settings)
+            morphology = loader.load(repo, ref, filename)
+
+            # create a dependency graph for the morphology
+            graph = \
+                morphlib.builddependencygraph.BuildDependencyGraph(loader,
+                                                                   morphology)
+            graph.resolve()
+
+            # print the graph
+            self.output.write('dependency tree:\n')
+            for node in graph.nodes:
+                self.output.write('  %s\n' % node)
+                for dep in node.dependencies:
+                    self.output.write('    -> %s\n' % dep)
+
+            # compute a build order from the graph
+            order = graph.build_order()
+            self.output.write('build order:\n')
+            for group in order:
+                self.output.write('  group:\n')
+                for morphology in group:
+                    self.output.write('    %s (%s)\n' % (morphology.name,
+                                                         morphology.kind))
+
     def msg(self, msg):
         '''Show a message to the user about what is going on.'''
         logging.debug(msg)
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
diff --git a/tests/show-dependencies.script b/tests/show-dependencies.script
new file mode 100755
index 00000000..da651379
--- /dev/null
+++ b/tests/show-dependencies.script
@@ -0,0 +1,33 @@
+#!/bin/sh
+#
+# Test a basic distributed build of two depending strata
+# with a couple of chunks in them.
+#
+# 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.
+
+set -e
+
+cache="$DATADIR/show-dependencies-cache"
+log="$DATADIR/show-dependencies-morph.log"
+
+./morph show-dependencies                           \
+    test-repo master xfce-core.morph                \
+    --no-default-configs                            \
+    --git-base-url="file://$DATADIR"                \
+    --cachedir="$cache"                             \
+    --keep-path                                     \
+    --no-distcc                                     \
+    --log="$log"
diff --git a/tests/show-dependencies.setup b/tests/show-dependencies.setup
new file mode 100755
index 00000000..6aaad793
--- /dev/null
+++ b/tests/show-dependencies.setup
@@ -0,0 +1,314 @@
+#!/bin/sh
+#
+# 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.
+
+set -e
+
+# Create a repository
+repo="$DATADIR/test-repo"
+mkdir "$repo"
+cd "$repo"
+git init --quiet
+
+# Add a single source file to simulate compiling
+cat <<EOF > hello.c
+#include <stdio.h>
+int main(void)
+{
+    puts("hello, world");
+    return 0;
+}
+EOF
+git add hello.c
+
+# Define a couple of chunk morphologies for the GTK stack
+gtkcomponents=(freetype fontconfig cairo pango glib gdk-pixbuf gtk dbus-glib dbus)
+for component in "${gtkcomponents[@]}"
+do
+    cat <<EOF > $component.morph
+{
+    "name": "$component",
+    "kind": "chunk",
+    "build-commands": [
+        "gcc -o hello hello.c"
+    ],
+    "install-commands": [
+        "install -d \\"\$DESTDIR\\"/etc",
+        "install -d \\"\$DESTDIR\\"/bin",
+        "install hello \\"\$DESTDIR\\"/bin/$component"
+    ]
+}
+EOF
+    git add $component.morph
+done
+git commit --quiet -m "add .c source file and GTK chunk morphologies"
+
+# Define a stratum for the GTK stack
+cat <<EOF > gtk-stack.morph
+{
+  "name": "gtk-stack",
+  "kind": "stratum",
+  "build-depends": [
+  ],
+  "sources": [
+    {
+      "name": "freetype",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+      ]
+    },
+    {
+      "name": "fontconfig",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+      ]
+    },
+    {
+      "name": "cairo",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+      ]
+    },
+    {
+      "name": "pango",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "freetype",
+        "fontconfig"
+      ]
+    },
+    {
+      "name": "glib",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+      ]
+    },
+    {
+      "name": "gdk-pixbuf",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "glib"
+      ]
+    },
+    {
+      "name": "gtk",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "cairo",
+        "gdk-pixbuf",
+        "glib",
+        "pango"
+      ]
+    },
+    {
+      "name": "dbus",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+      ]
+    },
+    {
+      "name": "dbus-glib",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "dbus",
+        "glib"
+      ]
+    }
+  ]
+}
+EOF
+git add gtk-stack.morph
+git commit --quiet -m "add gtk-stack.morph stratum"
+
+# Add a single source file to simulate compiling
+cat <<EOF > hello.c
+#include <stdio.h>
+int main(void)
+{
+    puts("hello, world");
+    return 0;
+}
+EOF
+git add hello.c
+
+# Define a couple of chunk morphologies for the GTK stack
+xfcecomponents=(xfce4-dev-tools libxfce4util libxfce4ui exo xfconf garcon thunar tumbler xfce4-panel xfce4-settings xfce4-session xfwm4 xfdesktop xfce4-appfinder gtk-xfce-engine)
+for component in "${xfcecomponents[@]}"
+do
+    cat <<EOF > $component.morph
+{
+    "name": "$component",
+    "kind": "chunk",
+    "build-commands": [
+        "gcc -o hello hello.c"
+    ],
+    "install-commands": [
+        "install -d \\"\$DESTDIR\\"/etc",
+        "install -d \\"\$DESTDIR\\"/bin",
+        "install hello \\"\$DESTDIR\\"/bin/$component"
+    ]
+}
+EOF
+    git add $component.morph
+done
+git commit --quiet -m "add .c source file and GTK chunk morphologies"
+
+# Define a stratum for the Xfce core
+cat <<EOF > xfce-core.morph
+{
+  "name": "xfce-core",
+  "kind": "stratum",
+  "build-depends": [
+    "gtk-stack"
+  ],
+  "sources": [
+    {
+      "name": "libxfce4util",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+      ]
+    },
+    {
+      "name": "xfconf",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4util"
+      ]
+    },
+    {
+      "name": "libxfce4ui",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "xfconf"
+      ]
+    },
+    {
+      "name": "exo",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4util"
+      ]
+    },
+    {
+      "name": "garcon",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4util"
+      ]
+    },
+    {
+      "name": "thunar",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4ui",
+        "exo"
+      ]
+    },
+    {
+      "name": "tumbler",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+      ]
+    },
+    {
+      "name": "xfce4-panel",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4ui",
+        "exo",
+        "garcon"
+      ]
+    },
+    {
+      "name": "xfce4-settings",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4ui",
+        "exo",
+        "xfconf"
+      ]
+    },
+    {
+      "name": "xfce4-session",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4ui",
+        "exo",
+        "xfconf"
+      ]
+    },
+    {
+      "name": "xfwm4",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4ui",
+        "xfconf"
+      ]
+    },
+    {
+      "name": "xfdesktop",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4ui",
+        "xfconf"
+      ]
+    },
+    {
+      "name": "xfce4-appfinder",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4ui",
+        "garcon",
+        "xfconf"
+      ]
+    },
+    {
+      "name": "gtk-xfce-engine",
+      "repo": "test-repo",
+      "ref": "master",
+      "build-depends": [
+        "libxfce4ui",
+        "garcon",
+        "xfconf"
+      ]
+    }
+  ]
+}
+EOF
+git add xfce-core.morph
+git commit --quiet -m "add xfce-core.morph stratum"
diff --git a/tests/show-dependencies.stdout b/tests/show-dependencies.stdout
new file mode 100644
index 00000000..6f0096e2
--- /dev/null
+++ b/tests/show-dependencies.stdout
@@ -0,0 +1,132 @@
+dependency tree:
+  xfce-core (stratum)
+    -> libxfce4util (chunk)
+    -> xfconf (chunk)
+    -> libxfce4ui (chunk)
+    -> exo (chunk)
+    -> garcon (chunk)
+    -> thunar (chunk)
+    -> tumbler (chunk)
+    -> xfce4-panel (chunk)
+    -> xfce4-settings (chunk)
+    -> xfce4-session (chunk)
+    -> xfwm4 (chunk)
+    -> xfdesktop (chunk)
+    -> xfce4-appfinder (chunk)
+    -> gtk-xfce-engine (chunk)
+  gtk-stack (stratum)
+    -> freetype (chunk)
+    -> fontconfig (chunk)
+    -> cairo (chunk)
+    -> pango (chunk)
+    -> glib (chunk)
+    -> gdk-pixbuf (chunk)
+    -> gtk (chunk)
+    -> dbus (chunk)
+    -> dbus-glib (chunk)
+  libxfce4util (chunk)
+    -> gtk-stack (stratum)
+  xfconf (chunk)
+    -> libxfce4util (chunk)
+    -> gtk-stack (stratum)
+  libxfce4ui (chunk)
+    -> xfconf (chunk)
+    -> gtk-stack (stratum)
+  exo (chunk)
+    -> libxfce4util (chunk)
+    -> gtk-stack (stratum)
+  garcon (chunk)
+    -> libxfce4util (chunk)
+    -> gtk-stack (stratum)
+  thunar (chunk)
+    -> libxfce4ui (chunk)
+    -> exo (chunk)
+    -> gtk-stack (stratum)
+  tumbler (chunk)
+    -> gtk-stack (stratum)
+  xfce4-panel (chunk)
+    -> libxfce4ui (chunk)
+    -> exo (chunk)
+    -> garcon (chunk)
+    -> gtk-stack (stratum)
+  xfce4-settings (chunk)
+    -> libxfce4ui (chunk)
+    -> exo (chunk)
+    -> xfconf (chunk)
+    -> gtk-stack (stratum)
+  xfce4-session (chunk)
+    -> libxfce4ui (chunk)
+    -> exo (chunk)
+    -> xfconf (chunk)
+    -> gtk-stack (stratum)
+  xfwm4 (chunk)
+    -> libxfce4ui (chunk)
+    -> xfconf (chunk)
+    -> gtk-stack (stratum)
+  xfdesktop (chunk)
+    -> libxfce4ui (chunk)
+    -> xfconf (chunk)
+    -> gtk-stack (stratum)
+  xfce4-appfinder (chunk)
+    -> libxfce4ui (chunk)
+    -> garcon (chunk)
+    -> xfconf (chunk)
+    -> gtk-stack (stratum)
+  gtk-xfce-engine (chunk)
+    -> libxfce4ui (chunk)
+    -> garcon (chunk)
+    -> xfconf (chunk)
+    -> gtk-stack (stratum)
+  freetype (chunk)
+  fontconfig (chunk)
+  cairo (chunk)
+  pango (chunk)
+    -> freetype (chunk)
+    -> fontconfig (chunk)
+  glib (chunk)
+  gdk-pixbuf (chunk)
+    -> glib (chunk)
+  gtk (chunk)
+    -> cairo (chunk)
+    -> gdk-pixbuf (chunk)
+    -> glib (chunk)
+    -> pango (chunk)
+  dbus (chunk)
+  dbus-glib (chunk)
+    -> dbus (chunk)
+    -> glib (chunk)
+build order:
+  group:
+    freetype (chunk)
+    fontconfig (chunk)
+    cairo (chunk)
+    glib (chunk)
+    dbus (chunk)
+  group:
+    pango (chunk)
+    gdk-pixbuf (chunk)
+    dbus-glib (chunk)
+  group:
+    gtk (chunk)
+  group:
+    gtk-stack (stratum)
+  group:
+    libxfce4util (chunk)
+    tumbler (chunk)
+  group:
+    xfconf (chunk)
+    exo (chunk)
+    garcon (chunk)
+  group:
+    libxfce4ui (chunk)
+  group:
+    thunar (chunk)
+    xfce4-panel (chunk)
+    xfce4-settings (chunk)
+    xfce4-session (chunk)
+    xfwm4 (chunk)
+    xfdesktop (chunk)
+    xfce4-appfinder (chunk)
+    gtk-xfce-engine (chunk)
+  group:
+    xfce-core (stratum)