diff -u -r --exclude=_darcs dw/setup.cfg autodeps/setup.cfg
--- dw/setup.cfg	2008-05-15 15:31:42.000000000 -0700
+++ autodeps/setup.cfg	2008-06-27 11:35:40.000000000 -0700
@@ -1,3 +1,6 @@
 [egg_info]
 tag_build = .dev
 tag_svn_revision = 1
+
+[easy_install]
+zip_ok = False
diff -u -r --exclude=_darcs dw/setup.py autodeps/setup.py
--- dw/setup.py	2008-05-15 15:32:13.000000000 -0700
+++ autodeps/setup.py	2008-06-27 11:39:26.000000000 -0700
@@ -1,5 +1,3 @@
-#!/usr/bin/env python
-
 import setuptools
 from setuptools import setup
 
diff -u -r --exclude=_darcs dw/stdeb/command/sdist_dsc.py autodeps/stdeb/command/sdist_dsc.py
--- dw/stdeb/command/sdist_dsc.py	2008-05-21 06:33:07.000000000 -0700
+++ autodeps/stdeb/command/sdist_dsc.py	2008-06-27 11:35:40.000000000 -0700
@@ -80,6 +80,10 @@
         if self.extra_cfg_file is not None:
             cfg_files.append(self.extra_cfg_file)
 
+        try:
+            install_requires = open(os.path.join(egg_info_dirname,'requires.txt'),'rU').read()
+        except EnvironmentError:
+            install_requires = ()
         debinfo = DebianInfo(
             cfg_files=cfg_files,
             module_name = module_name,
@@ -93,6 +97,8 @@
             long_description = self.distribution.get_long_description(),
             patch_file = self.patch_file,
             patch_level = self.patch_level,
+            install_requires = install_requires,
+            setup_requires = (), # XXX How do we get the setup_requires?
         )
         if debinfo.patch_file != '' and self.patch_already_applied:
             raise RuntimeError('A patch was already applied, but another '
diff -u -r --exclude=_darcs dw/stdeb/util.py autodeps/stdeb/util.py
--- dw/stdeb/util.py	2008-05-21 06:33:07.000000000 -0700
+++ autodeps/stdeb/util.py	2008-06-27 11:39:00.000000000 -0700
@@ -1,11 +1,12 @@
 #
 # This module contains most of the code of stdeb.
 #
-import sys, os, shutil, sets, select
+import re, sys, os, shutil, sets, select
 import ConfigParser
 import subprocess
 import tempfile
 import stdeb
+import pkg_resources
 from stdeb import log, __version__ as __stdeb_version__
 
 __all__ = ['DebianInfo','build_dsc','expand_tarball','expand_zip',
@@ -13,6 +14,15 @@
            'apply_patch','repack_tarball_with_debianized_dirname',
            'expand_sdist_file']
 
+import exceptions
+class CalledProcessError(exceptions.Exception): pass
+
+def check_call(*popenargs, **kwargs):
+    retcode = subprocess.call(*popenargs, **kwargs)
+    if retcode == 0:
+        return
+    raise CalledProcessError(retcode)
+
 stdeb_cmdline_opts = [
     ('dist-dir=', 'd',
      "directory to put final built distributions in (default='deb_dist')"),
@@ -48,7 +58,7 @@
 def process_command(args, cwd=None):
     if not isinstance(args, (list, tuple)):
         raise RuntimeError, "args passed must be in a list"
-    subprocess.check_call(args, cwd=cwd)
+    check_call(args, cwd=cwd)
 
 def recursive_hardlink(src,dst):
     dst = os.path.abspath(dst)
@@ -111,6 +121,80 @@
     result = cmd.stdout.read().strip()
     return result
 
+def get_deb_depends_from_setuptools_requires(requirements):
+    depends = [] # This will be the return value from this function.
+
+    requirements = list(pkg_resources.parse_requirements(requirements))
+    if not requirements:
+        return depends
+
+    # Ask apt-file for any packages which have a .egg-info file by these names.
+    # Note that apt-file appears to think that some packages e.g. setuptools itself have "foo.egg-info/BLAH" files but not a "foo.egg-info" directory.
+    
+    egginfore="((%s)(?:-[^/]+)?(?:-py[0-9]\.[0-9.]+)?\.egg-info)" % '|'.join(req.project_name for req in requirements)
+
+    args = ["apt-file", "search", "--ignore-case", "--regexp", egginfore]
+    try:
+        cmd = subprocess.Popen(args, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE, universal_newlines=True)
+    except Exception, le:
+        log.error('ERROR running: %s', ' '.join(args))
+        raise RuntimeError('exception %s from subprocess %s' % (le,args)) 
+    returncode = cmd.wait()
+    if returncode:
+        log.error('ERROR running: %s', ' '.join(args))
+        raise RuntimeError('returncode %d from subprocess %s' % (returncode, args))
+
+    inlines = cmd.stdout.readlines()
+
+    dd = {} # {pydistname: {pydist: set(debpackagename)}}
+    E=re.compile(egginfore, re.I)
+    D=re.compile("^([^:]*):", re.I)
+    eggsndebs = set()
+    for l in inlines:
+        if l:
+            emo = E.search(l)
+            assert emo, l
+            dmo = D.search(l)
+            assert dmo, l
+            eggsndebs.add((emo.group(1), dmo.group(1)))
+            
+    for (egginfo, debname) in eggsndebs:
+        pydist = pkg_resources.Distribution.from_filename(egginfo)
+        try:
+            dd.setdefault(pydist.project_name.lower(), {}).setdefault(pydist, set()).add(debname)
+        except ValueError, le:
+            log.warn("I got an error parsing a .egg-info file named \"%s\" from Debian package \"%s\" as a pkg_resources Distribution: %s" % (egginfo, debname, le,))
+            pass
+
+    # Now for each requirement, see if a Debian package satisfies it.
+    ops = {'<':'<<','>':'>>','==':'=','<=':'<=','>=':'>='}
+    for req in requirements:
+        reqname = req.project_name.lower()
+        gooddebs = set()
+        for pydist, debs in dd.get(reqname, {}).iteritems():
+            if pydist in req:
+                # log.info("I found Debian packages \"%s\" which provides Python package \"%s\", version \"%s\", which satisfies our version requirements: \"%s\"" % (', '.join(debs), req.project_name, ver, req))
+                gooddebs |= (debs)
+            else:
+                log.info("I found Debian packages \"%s\" which provides Python package \"%s\", version \"%s\", which does not satisfy our version requirements: \"%s\" -- ignoring." % (', '.join(debs), req.project_name, ver, req))
+        if not gooddebs:
+            log.warn("I found no Debian package which provides the required Python package \"%s\" with version requirements \"%s\".  Guessing blindly that the name \"python-%s\" will be it, and that the Python package version number requirements will apply to the Debian package." % (req.project_name, req.specs, reqname))
+            gooddebs.add("python-" + reqname)
+        elif len(gooddebs) == 1:
+            log.info("I found a Debian package which provides the require Python package.  Python package: \"%s\", Debian package: \"%s\";  adding Depends specifications for the following version(s): \"%s\"" % (req.project_name, tuple(gooddebs)[0], req.specs))
+        else:
+            log.warn("I found multiple Debian packages which provide the Python distribution required.  I'm listing them all as alternates.  Candidate debs which claim to provide the Python package \"%s\" are: \"%s\"" % (req.project_name, ', '.join(gooddebs),))
+
+        alts = []
+        for deb in gooddebs:
+            for spec in req.specs:
+                # Here we blithely assume that the Debian package versions are enough like the Python package versions that the requirement can be ported straight over...
+                alts.append("%s (%s %s)" % (deb, ops[spec[0]], spec[1]))
+
+        depends.append(' | '.join(alts))
+
+    return depends
+
 def make_tarball(tarball_fname,directory,cwd=None):
     "create a tarball from a directory"
     if tarball_fname.endswith('.gz'): opts = 'czf'
@@ -278,6 +362,8 @@
                  long_description=NotGiven,
                  patch_file=None,
                  patch_level=None,
+                 install_requires=None,
+                 setup_requires=None,
                  ):
         if cfg_files is NotGiven: raise ValueError("cfg_files must be supplied")
         if module_name is NotGiven: raise ValueError("module_name must be supplied")
@@ -337,7 +423,9 @@
             self.pycentral_showversions=current
 
 
-        build_deps = ['python-setuptools (>= 0.6b3-1)']
+        build_deps = ['python-setuptools (>= 0.6b3)']
+        build_deps.extend(get_deb_depends_from_setuptools_requires(setup_requires))
+
         depends = []
 
         depends.append('${python:Depends}')
@@ -386,6 +474,7 @@
             self.copy_files_lines += '\n\tcp %s %s'%(mime_desktop_file,dest_file)
 
         depends.extend(parse_vals(cfg,module_name,'Depends') )
+        depends.extend(get_deb_depends_from_setuptools_requires(install_requires))
         self.depends = ', '.join(depends)
 
         self.description = description