Add programmatic interface

tools/bisect-builds.py

Index: tools/bisect-builds.py
diff --git a/tools/bisect-builds.py b/tools/bisect-builds.py
index d9c056904b113b295266d6b2b5716e7eae0a9222..549d4228f86809ad58977ced0af03b012c0c7822 100755
--- a/tools/bisect-builds.py
+++ b/tools/bisect-builds.py
@@ -13,7 +13,7 @@ it will ask you whether it is good or bad before continuing the search.
 """
 
 # The root URL for storage.
-BASE_URL = 'http://commondatastorage.googleapis.com/chromium-browser-continuous'
+BASE_URL = 'http://commondatastorage.googleapis.com/chromium-browser-snapshots'
 
 # URL to the ViewVC commit page.
 BUILD_VIEWVC_URL = 'http://src.chromium.org/viewvc/chrome?view=rev&revision=%d'
@@ -35,6 +35,8 @@ import tempfile
 import urllib
 from xml.etree import ElementTree
 import zipfile
+import subprocess
+import threading

[Evan Martin, 2011/07/14 18:57:52]

I think this list is alphabetized.

[szager, 2011/07/14 19:23:03]

Done.

 
 class PathContext(object):
   """A PathContext is used to carry the information used to construct URLs and
@@ -53,13 +55,13 @@ class PathContext(object):
     #   _listing_platform_dir = Directory that holds revisions. Ends with a '/'.
     #   _archive_extract_dir = Uncompressed directory in the archive_name file.
     #   _binary_name = The name of the executable to run.
-    if self.platform == 'linux' or self.platform == 'linux-64':
+    if self.platform == 'linux' or self.platform == 'linux64':
       self._listing_platform_dir = 'Linux/'
       self.archive_name = 'chrome-linux.zip'
       self._archive_extract_dir = 'chrome-linux'
       self._binary_name = 'chrome'
       # Linux and x64 share all the same path data except for the archive dir.
-      if self.platform == 'linux-64':
+      if self.platform == 'linux64':
         self._listing_platform_dir = 'Linux_x64/'
     elif self.platform == 'mac':
       self._listing_platform_dir = 'Mac/'
@@ -84,8 +86,8 @@ class PathContext(object):
 
   def GetDownloadURL(self, revision):
     """Gets the download URL for a build archive of a specific revision."""
-    return BASE_URL + '/' + self._listing_platform_dir + str(revision) + '/' + \
-        self.archive_name
+    return "%s/%s%d/%s" % (
+        BASE_URL, self._listing_platform_dir, revision, self.archive_name)
 
   def GetLastChangeURL(self):
     """Returns a URL to the LAST_CHANGE file."""
@@ -99,9 +101,11 @@ class PathContext(object):
 
 def UnzipFilenameToDir(filename, dir):
   """Unzip |filename| to directory |dir|."""
+  pushd = os.getcwd()
+  if not os.path.isabs(filename):
+    filename = os.path.join(pushd, filename)
   zf = zipfile.ZipFile(filename)
   # Make base.
-  pushd = os.getcwd()
   try:
     if not os.path.isdir(dir):
       os.mkdir(dir)
@@ -161,7 +165,15 @@ def ParseDirectoryIndex(context):
     # The <Prefix> nodes have content of the form of
     # |_listing_platform_dir/revision/|. Strip off the platform dir and the
     # trailing slash to just have a number.
-    revisions = map(lambda x: x.text[len(prefix):-1], all_prefixes)
+    #revisions = map(lambda x: x.text[len(prefix):-1], all_prefixes)

[Evan Martin, 2011/07/14 18:57:52]

Did you mean to leave in this commented-out code?

[szager, 2011/07/14 19:23:03]

Deleted!

+    revisions = []
+    for pf in all_prefixes:

[Robert Sesek, 2011/07/15 16:27:14]

What's "pf"? |prefix| is fine.

+      revnum = pf.text[len(prefix):-1]
+      try:
+        revnum = int(revnum)
+        revisions.append(revnum)
+      except ValueError:
+        pass
     return (revisions, next_marker)
 
   # Fetch the first list of revisions.
@@ -186,63 +198,164 @@ def GetRevList(context):
   revlist.sort()
   return revlist
 
+def FetchRevision(context, rev, filename, quit_event=None) :
+  """Downloads and unzips revision |rev|"""
 
-def TryRevision(context, rev, profile, args):
-  """Downloads revision |rev|, unzips it, and opens it for the user to test.
-  |profile| is the profile to use."""
-  # Do this in a temp dir so we don't collide with user files.
-  cwd = os.getcwd()
-  tempdir = tempfile.mkdtemp(prefix='bisect_tmp')
-  os.chdir(tempdir)
+  def ReportHook(blocknum, blocksize, totalsize):
+    if quit_event and quit_event.is_set():
+      raise RuntimeError("Aborting download of revision %d" % rev)
 
-  # Download the file.
   download_url = context.GetDownloadURL(rev)
-  def _ReportHook(blocknum, blocksize, totalsize):
-    size = blocknum * blocksize
-    if totalsize == -1:  # Total size not known.
-      progress = "Received %d bytes" % size
-    else:
-      size = min(totalsize, size)
-      progress = "Received %d of %d bytes, %.2f%%" % (
-          size, totalsize, 100.0 * size / totalsize)
-    # Send a \r to let all progress messages use just one line of output.
-    sys.stdout.write("\r" + progress)
-    sys.stdout.flush()
+
   try:
-    print 'Fetching ' + download_url
-    urllib.urlretrieve(download_url, context.archive_name, _ReportHook)
-    print
-  except Exception, e:
-    print('Could not retrieve the download. Sorry.')
-    sys.exit(-1)
+    urllib.urlretrieve(download_url, filename, ReportHook)
+  except RuntimeError, e:
+    pass
+
+def RunRevision(context, revision, zipfile, profile, args) :
+  """Given a zipped revision, unzip it and run the test"""
+
+  print "Trying revision %d..." % revision
 
-  # Unzip the file.
-  print 'Unzipping ...'
-  UnzipFilenameToDir(context.archive_name, os.curdir)
+  # Create a temp directory and unzip the revision into it
+  cwd = os.getcwd()
+  tempdir = tempfile.mkdtemp(prefix='bisect_tmp')
+  UnzipFilenameToDir(zipfile, tempdir)
+  os.chdir(tempdir)
 
-  # Tell the system to open the app.
-  args = ['--user-data-dir=%s' % profile] + args
-  flags = ' '.join(map(pipes.quote, args))
-  cmd = '%s %s' % (context.GetLaunchPath(), flags)
-  print 'Running %s' % cmd
-  os.system(cmd)
+  # Run the test
+  testargs = [context.GetLaunchPath(), '--user-data-dir=%s' % profile] + args
+  subproc = subprocess.Popen(testargs,
+                             bufsize=-1,
+                             stdout=subprocess.PIPE,
+                             stderr=subprocess.PIPE)
+  (stdout, stderr) = subproc.communicate()
 
   os.chdir(cwd)
-  print 'Cleaning temp dir ...'
   try:
     shutil.rmtree(tempdir, True)
   except Exception, e:
     pass
 
+  return (subproc.returncode, stdout, stderr)
 
-def AskIsGoodBuild(rev):
+def ResultIsGood(status, stdout, stderr) :
   """Ask the user whether build |rev| is good or bad."""
   # Loop until we get a response that we can parse.
   while True:
-    response = raw_input('\nBuild %d is [(g)ood/(b)ad]: ' % int(rev))
+    response = raw_input('Build is [(g)ood/(b)ad/(q)uit]: ')
     if response and response in ('g', 'b'):
       return response == 'g'
+    if response and response == 'q':
+      raise SystemExit()
+
+def bisect(platform=None,

[Evan Martin, 2011/07/14 18:57:52]

Capital B on function names.  (Our Python style is weird, I know.)

[szager, 2011/07/14 19:23:03]

Done.

+           profile="",
+           run_args=(),
+           good_rev=0,
+           bad_rev=0,
+           predicate=ResultIsGood):
+  """Given known good and known bad revisions, run a binary search on all
+  archived revisions to determine the last known good revision."""
+
+  context = PathContext(platform, good_rev, bad_rev)
+  cwd = os.getcwd()
+
+  revlist = GetRevList(context)
 
+  # Get a list of revisions to bisect across.
+  if len(revlist) < 2:  # Don't have enough builds to bisect
+    msg = 'We don\'t have enough builds to bisect. revlist: %s' % revlist
+    raise RuntimeError(msg)
+
+  # If we don't have a |good_rev|, set it to be the first revision possible.
+  if good_rev == 0:
+    good_rev = revlist[0]
+
+  # Figure out our bookends and first pivot point; fetch the pivot revision
+  good = 0
+  bad = len(revlist) - 1
+  pivot = bad/2
+  rev = revlist[pivot]
+  zipfile = os.path.join(cwd, '%d-%s' % (rev, context.archive_name))
+  FetchRevision(context, rev, zipfile)
+
+  # Binary search time!
+  while zipfile and bad - good > 1:
+    print "iterating with good=%d bad=%d pivot=%d" % (
+        revlist[good], revlist[bad], revlist[pivot])
+
+    # Pre-fetch next two possible pivots
+    down_pivot = int((pivot - good) / 2) + good
+    down_thread = None
+    if down_pivot != pivot and down_pivot != good :
+      down_rev = revlist[down_pivot]
+      zipfile_base = '%d-%s' % (down_rev, context.archive_name)
+      down_zipfile = os.path.join(cwd, zipfile_base)
+      down_event = threading.Event()
+      fetchargs = (context, down_rev, down_zipfile, down_event)
+      down_thread = threading.Thread(target=FetchRevision,
+                                     name='down_fetch',
+                                     args=fetchargs)
+      down_thread.start()
+
+    up_pivot = int((bad - pivot) / 2) + pivot
+    up_thread = None
+    if up_pivot != pivot and up_pivot != bad :
+      up_rev = revlist[up_pivot]
+      zipfile_base = '%d-%s' % (up_rev, context.archive_name)
+      up_zipfile = os.path.join(cwd, zipfile_base)
+      up_event = threading.Event()
+      fetchargs = (context, up_rev, up_zipfile, up_event)
+      up_thread = threading.Thread(target=FetchRevision,
+                                   name='up_fetch',
+                                   args=fetchargs)
+      up_thread.start()
+
+    # Run test on the pivot revision
+    (status, stdout, stderr) = RunRevision(context,
+                                           rev,
+                                           zipfile,
+                                           profile,
+                                           run_args)
+    os.unlink(zipfile)
+    zipfile = None
+    try:
+      if predicate(status, stdout, stderr) :
+        good = pivot
+        if down_thread :
+          down_event.set()    # Kill the download of older revision
+          down_thread.join()
+          os.unlink(down_zipfile)
+        if up_thread :
+          print "Downloading revision %d..." % up_rev
+          up_thread.join()    # Wait for newer revision to finish downloading
+          pivot = up_pivot
+          zipfile = up_zipfile
+      else :
+        bad = pivot
+        if up_thread :
+          up_event.set()      # Kill download of newer revision
+          up_thread.join()
+          os.unlink(up_zipfile)
+        if down_thread :
+          print "Downloading revision %d..." % down_rev
+          down_thread.join()  # Wait for older revision to finish downloading
+          pivot = down_pivot
+          zipfile = down_zipfile
+    except SystemExit:
+      for f in [down_zipfile, up_zipfile]:
+        try:
+          os.unlink(f)
+        except OSError:
+          pass
+      sys.exit(0)

[Evan Martin, 2011/07/14 18:57:52]

Is this both moving the code and making changes to it?  It'd be easier to review
if you uploaded a change that just moved it, and then a second one that modifies
it.

[szager, 2011/07/14 19:23:03]

I had move the main loop out of main() to enable the programmatic interface; and
I had to reorganize the main loop to enable threading.  I can probably split
those into two changes.

+
+    rev = revlist[pivot]
+
+  return (good, bad)
+
+################################################################################
 
 def main():
   usage = ('%prog [options] [-- chromium-options]\n'
@@ -281,11 +394,7 @@ def main():
   # Create the context. Initialize 0 for the revisions as they are set below.
   context = PathContext(opts.archive, 0, 0)
 
-  # Pick a starting point, try to get HEAD for this.
-  if opts.bad:
-    bad_rev = opts.bad
-  else:
-    bad_rev = 0
+  if not opts.bad :
     try:
       # Location of the latest build revision number
       nh = urllib.urlopen(context.GetLastChangeURL())
@@ -294,71 +403,30 @@ def main():
       bad_rev = raw_input('Bad revision [HEAD:%d]: ' % latest)
       if (bad_rev == ''):
         bad_rev = latest
-      bad_rev = int(bad_rev)
+      opts.bad = int(bad_rev)
     except Exception, e:
       print('Could not determine latest revision. This could be bad...')
-      bad_rev = int(raw_input('Bad revision: '))
+      opts.bad = int(raw_input('Bad revision: '))
 
-  # Find out when we were good.
-  if opts.good:
-    good_rev = opts.good
-  else:
-    good_rev = 0
+  if not opts.good :
     try:
-      good_rev = int(raw_input('Last known good [0]: '))
+      opts.good = int(raw_input('Last known good [0]: '))
     except Exception, e:
       pass
 
-  # Set the input parameters now that they've been validated.
-  context.good_revision = good_rev
-  context.bad_revision = bad_rev
-
-  # Get a list of revisions to bisect across.
-  revlist = GetRevList(context)
-  if len(revlist) < 2:  # Don't have enough builds to bisect
-    print 'We don\'t have enough builds to bisect. revlist: %s' % revlist
-    sys.exit(1)
-
-  # If we don't have a |good_rev|, set it to be the first revision possible.
-  if good_rev == 0:
-    good_rev = revlist[0]
-
-  # These are indexes of |revlist|.
-  good = 0
-  bad = len(revlist) - 1
-  last_known_good_rev = revlist[good]
+  try :
+    (good, bad) = bisect(opts.archive, opts.profile, args, opts.good, opts.bad)
+    # We're done. Let the user know the results in an official manner.
+    print('You are probably looking for build %d.' % bad)
+    clog_url = CHANGELOG_URL % (good, bad)
+    print('CHANGELOG URL: %s' % clog_url)
+    build_url = BUILD_VIEWVC_URL % bad
+    print('Built at revision: %s' % build_url)
+    return 0
+  except Exception, e:
+    print e
+    return 1
 
-  # Binary search time!
-  while good < bad:
-    candidates = revlist[good:bad]
-    num_poss = len(candidates)
-    if num_poss > 10:
-      print('%d candidates. %d tries left.' %
-          (num_poss, round(math.log(num_poss, 2))))
-    else:
-      print('Candidates: %s' % revlist[good:bad])
-
-    # Cut the problem in half...
-    test = int((bad - good) / 2) + good
-    test_rev = revlist[test]
-
-    # Let the user give this rev a spin (in her own profile, if she wants).
-    profile = opts.profile
-    if not profile:
-      profile = 'profile'  # In a temp dir.
-    TryRevision(context, test_rev, profile, args)
-    if AskIsGoodBuild(test_rev):
-      last_known_good_rev = revlist[good]
-      good = test + 1
-    else:
-      bad = test
-
-  # We're done. Let the user know the results in an official manner.
-  print('You are probably looking for build %d.' % revlist[bad])
-  print('CHANGELOG URL:')
-  print(CHANGELOG_URL % (last_known_good_rev, revlist[bad]))
-  print('Built at revision:')
-  print(BUILD_VIEWVC_URL % revlist[bad])
 
 if __name__ == '__main__':
   sys.exit(main())