--- a/test/test_packager.py	Thu May 22 19:13:12 2008 +0000
+++ b/test/test_packager.py	Fri May 23 16:11:22 2008 +0000
@@ -14,7 +14,8 @@
 from treepkg.run import call
 from treepkg.cmdexpand import cmdexpand
 from treepkg.util import writefile
-from treepkg.packager import PackagerGroup, import_packager_module
+from treepkg.packager import PackagerGroup, import_packager_module, \
+     CyclicDependencyError
 import treepkg.subversion as subversion
 import treepkg
 
@@ -411,3 +412,61 @@
 
         self.assertEquals(module.PackageTrack.revision_packager_cls,
                           module.RevisionPackager)
+
+
+class PackageTrackWithDependencies(treepkg.packager.PackageTrack):
+
+    def __init__(self, name, handle_dependencies, requires, provides):
+        defaults = dict(base_dir="/home/builder/tracks/" + name,
+                        svn_url="svn://example.com",
+                        root_cmd=["false"],
+                        pbuilderrc="/home/builder/pbuilderrc",
+                        deb_email="treepkg@example.com", deb_fullname="treepkg",
+                        handle_dependencies=handle_dependencies)
+        super(PackageTrackWithDependencies,
+              self).__init__(name, **defaults)
+        self.dependencies = (set(requires.split()), set(provides.split()))
+
+    def determine_dependencies(self):
+        pass
+
+
+class TestPackageDependencies(unittest.TestCase):
+
+    def test_track_order(self):
+        P = PackageTrackWithDependencies
+        tracks = [P("library", True, "base-dev", "library library-dev"),
+                  P("other", False, "cdbs base-dev", "other"),
+                  P("base", True, "", "base base-dev"),
+                  P("program", True, "library-dev libc", "program program-doc"),
+                  ]
+        group = PackagerGroup(tracks, 3600)
+        sorted_tracks = group.get_package_tracks()
+        track_indices = dict([(track.name, index) for index, track in
+                              enumerate(sorted_tracks)])
+        def check_order(track1, track2):
+            self.failUnless(track_indices[track1] < track_indices[track2])
+
+        check_order("base", "library")
+        check_order("library", "program")
+        check_order("base", "program")
+
+        # sanity check whether other is still there.  It doesn't matter
+        # where
+        self.failUnless("other" in track_indices)
+
+    def test_track_order_cycle(self):
+        P = PackageTrackWithDependencies
+        tracks = [P("library", True, "base-dev", "library library-dev"),
+                  P("cycle", True, "program", "cycle"),
+                  P("other", False, "cdbs base-dev", "other"),
+                  P("base", True, "cycle", "base base-dev"),
+                  P("program", True, "library-dev libc", "program program-doc"),
+                  ]
+        try:
+            group = PackagerGroup(tracks, 3600)
+            sorted_tracks = group.get_package_tracks()
+        except CyclicDependencyError, exc:
+            pass
+        else:
+            self.fail("PackagerGroup did not detect cyclic dependencies")

--- a/treepkg/packager.py	Thu May 22 19:13:12 2008 +0000
+++ b/treepkg/packager.py	Fri May 23 16:11:22 2008 +0000
@@ -19,6 +19,7 @@
 import subversion
 import run
 import status
+import debian
 from cmdexpand import cmdexpand
 from builder import PBuilder
 
@@ -277,7 +278,7 @@
 
     def __init__(self, name, base_dir, svn_url, root_cmd, pbuilderrc, deb_email,
                  deb_fullname, packager_class="treepkg.packager",
-                 debrevision_prefix="treepkg"):
+                 debrevision_prefix="treepkg", handle_dependencies=False):
         self.name = name
         self.base_dir = base_dir
         self.svn_url = svn_url
@@ -285,6 +286,8 @@
         self.deb_email = deb_email
         self.deb_fullname = deb_fullname
         self.debrevision_prefix = debrevision_prefix
+        self.handle_dependencies = handle_dependencies
+        self.dependencies = None
         self.pkg_dir_template = "%(revision)d-%(increment)d"
         self.pkg_dir_regex \
                    = re.compile(r"(?P<revision>[0-9]+)-(?P<increment>[0-9]+)$")
@@ -302,6 +305,33 @@
             print ("TODO: the debian directory %s still has to be created"
                    % (self.debian_dir,))
 
+    def determine_dependencies(self):
+        if self.dependencies is not None:
+            return
+
+        requires = ()
+        provides = ()
+        if self.handle_dependencies:
+            control = debian.DebianControlFile(os.path.join(self.debian_dir,
+                                                            "control"))
+            requires = control.build_depends
+            provides = (pkg[0] for pkg in control.packages)
+        self.dependencies = (set(requires), set(provides))
+        logging.debug("Track %s: build depends: %s", self.name,
+                      " ".join(self.dependencies[0]))
+        logging.debug("Track %s: provides: %s", self.name,
+                      " ".join(self.dependencies[1]))
+
+    def dependencies_required(self):
+        """Returns a list of required packages"""
+        self.determine_dependencies()
+        return self.dependencies[0]
+
+    def dependencies_provided(self):
+        """Returns a list of provided packages"""
+        self.determine_dependencies()
+        return self.dependencies[1]
+
     def pkg_dir_for_revision(self, revision, increment):
         return os.path.join(self.pkg_dir,
                             self.pkg_dir_template % locals())
@@ -432,6 +462,16 @@
     return module.PackageTrack(**kw)
 
 
+class CyclicDependencyError(Exception):
+
+    """Exception thrown when a cycle is detected in the track dependencies"""
+
+    def __init__(self, tracks):
+        Exception.__init__(self,
+                           "Cyclic dependencies between" " tracks (%s)"
+                           % ", ".join([track.name for track in tracks]))
+
+
 class PackagerGroup(object):
 
     def __init__(self, package_tracks, check_interval, revision=None,
@@ -441,6 +481,47 @@
         self.revision = revision
         self.instructions_file = instructions_file
         self.instructions_file_removed = False
+        self.sort_tracks()
+
+    def sort_tracks(self):
+        """Sorts tracks for dependency handling"""
+        todo = self.package_tracks[:]
+        sorted = []
+        seen = set()
+
+        # dependencies that can be solved by one of the tracks
+        known = set()
+        for track in todo:
+            known |= track.dependencies_provided()
+
+        while todo:
+            todo_again = []
+            for track in todo:
+                if not track.handle_dependencies:
+                    sorted.append(track)
+                    continue
+
+                unmet = (track.dependencies_required() & known) - seen
+                if unmet:
+                    todo_again.append(track)
+                else:
+                    sorted.append(track)
+                    seen |= track.dependencies_provided()
+            if todo_again == todo:
+                raise CyclicDependencyError(todo)
+            todo = todo_again
+
+        self.package_tracks = sorted
+        self.needed_binaries = set()
+        for track in self.package_tracks:
+            self.needed_binaries |= track.dependencies_required()
+        self.needed_binaries &= known
+
+        logging.info("sorted track order: %s",
+                     " ".join(track.name for track in sorted))
+        logging.info("binary packages needed as build dependencies: %s",
+                     " ".join(self.needed_binaries))
+
 
     def run(self):
         """Runs the packager group indefinitely"""
@@ -469,19 +550,53 @@
     def check_package_tracks(self):
         logging.info("Checking package tracks")
         self.clear_instruction()
-        for track in self.package_tracks:
-            try:
-                packager = track.package_if_updated(revision=self.revision)
-                if packager:
-                    packager.package()
-                if self.should_stop():
-                    logging.info("Received stop instruction.  Stopping.")
-                    return True
-            except:
-                logging.exception("An error occurred while"
-                                  " checking packager track %r", track.name)
+        repeat = True
+        while repeat:
+            repeat = False
+            for track in self.package_tracks:
+                try:
+                    packager = track.package_if_updated(revision=self.revision)
+                    if packager:
+                        packager.package()
+                        repeat = self.install_dependencies(track, packager)
+                    if self.should_stop():
+                        logging.info("Received stop instruction.  Stopping.")
+                        return True
+                except:
+                    logging.exception("An error occurred while"
+                                      " checking packager track %r", track.name)
+                if repeat:
+                    logging.info("Built binaries needed by other tracks."
+                                 " Starting over to ensure all dependencies"
+                                 " are met")
+                    break
+
         logging.info("Checked all package tracks")
 
+
+    def install_dependencies(self, track, packager):
+        """Add the binaries built by packager to the builder, if necessary.
+        It is necessary if any track depends on the packages.  The
+        method simply installs all binary files built by the packger
+        instead of only those which are immediately required by a track.
+        This is done because tracks usually depend directly only on the
+        -dev packages which usually require another binary package built
+        at the same time.
+        """
+        if (track.handle_dependencies
+            and track.dependencies_provided() & self.needed_binaries):
+            # FIXME: this basically assumes that all tracks use the same
+            # builder.  This is true for now, but it is possible to
+            # configure treepkg with different builders for different
+            # tracks and we really should be installing the newly built
+            # binaries into the builder of the tracks which depends on
+            # them
+            binaries = packager.list_binary_files()
+            track.builder.add_binaries_to_extra_pkg(binaries)
+            return True
+        return False
+
+
     def get_package_tracks(self):
         return self.package_tracks