Add programmatic interface

tools/bisect-builds.py

 #!/usr/bin/python
 # Copyright (c) 2011 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """Snapshot Build Bisect Tool
 
 This script bisects a snapshot archive using binary search. It starts at
 a bad revision (it will try to guess HEAD) and asks for a last known-good
 revision. It will then binary search across this revision range by downloading,
 unzipping, and opening Chromium for you. After testing the specific revision,
 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'
 
 # Changelogs URL.
 CHANGELOG_URL = 'http://build.chromium.org/f/chromium/' \
                 'perf/dashboard/ui/changelog.html?url=/trunk/src&range=%d:%d'
 
 ###############################################################################
 
 import math
 import optparse
 import os
 import pipes
 import re
 import shutil
 import sys
 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
   paths when dealing with the storage server and archives."""
   def __init__(self, platform, good_revision, bad_revision):
     super(PathContext, self).__init__()
     # Store off the input parameters.
     self.platform = platform  # What's passed in to the '-a/--archive' option.
     self.good_revision = good_revision
     self.bad_revision = bad_revision
 
     # The name of the ZIP file in a revision directory on the server.
     self.archive_name = None
 
     # Set some internal members:
     #   _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/'
       self.archive_name = 'chrome-mac.zip'
       self._archive_extract_dir = 'chrome-mac'
       self._binary_name = 'Chromium.app/Contents/MacOS/Chromium'
     elif self.platform == 'win':
       self._listing_platform_dir = 'Win/'
       self.archive_name = 'chrome-win32.zip'
       self._archive_extract_dir = 'chrome-win32'
       self._binary_name = 'chrome.exe'
     else:
       raise Exception("Invalid platform")
 
   def GetListingURL(self, marker=None):
     """Returns the URL for a directory listing, with an optional marker."""
     marker_param = ''
     if marker:
       marker_param = '&marker=' + str(marker)
     return BASE_URL + '/?delimiter=/&prefix=' + self._listing_platform_dir + \
         marker_param
 
   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."""
     return BASE_URL + '/' + self._listing_platform_dir + 'LAST_CHANGE'
 
   def GetLaunchPath(self):
     """Returns a relative path (presumably from the archive extraction location)
     that is used to run the executable."""
     return os.path.join(self._archive_extract_dir, self._binary_name)
 
 
 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)
     os.chdir(dir)
     # Extract files.
     for info in zf.infolist():
       name = info.filename
       if name.endswith('/'):  # dir
         if not os.path.isdir(name):
           os.makedirs(name)
@@ skipping 39 matching lines @@
     is_truncated = document.find(namespace + 'IsTruncated')
     if is_truncated is not None and is_truncated.text.lower() == 'true':
       next_marker = document.find(namespace + 'NextMarker').text
 
     # Get a list of all the revisions.
     all_prefixes = document.findall(namespace + 'CommonPrefixes/' +
                                     namespace + 'Prefix')
     # 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.
   (revisions, next_marker) = _FetchAndParse(context.GetListingURL())
   # If the result list was truncated, refetch with the next marker. Do this
   # until an entire directory listing is done.
   while next_marker:
     (new_revisions, next_marker) = _FetchAndParse(
         context.GetListingURL(next_marker))
     revisions.extend(new_revisions)
 
   return revisions
 
 
 def GetRevList(context):
   """Gets the list of revision numbers between |good_revision| and
   |bad_revision| of the |context|."""
   # Download the revlist and filter for just the range between good and bad.
   rev_range = range(context.good_revision, context.bad_revision)
   revlist = map(int, ParseDirectoryIndex(context))
   revlist = filter(lambda r: r in rev_range, revlist)
   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.
+  def ReportHook(blocknum, blocksize, totalsize):
+    if quit_event and quit_event.is_set():
+      raise RuntimeError("Aborting download of revision %d" % rev)
+
+  download_url = context.GetDownloadURL(rev)
+
+  try:
+    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
+
+  # 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)
 
-  # 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)
-
-  # Unzip the file.
-  print 'Unzipping ...'
-  UnzipFilenameToDir(context.archive_name, os.curdir)
-
-  # 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'
            'Perform binary search on the snapshot builds.\n'
            '\n'
            'Tip: add "-- --no-first-run" to bypass the first run prompts.')
   parser = optparse.OptionParser(usage=usage)
   # Strangely, the default help output doesn't include the choice list.
   choices = ['mac', 'win', 'linux', 'linux64']
             # linux-chromiumos lacks a continuous archive http://crbug.com/78158
@@ skipping 18 matching lines @@
 
   if opts.bad and opts.good and (opts.good > opts.bad):
     print ('The good revision (%d) must precede the bad revision (%d).\n' %
            (opts.good, opts.bad))
     parser.print_help()
     return 1
 
   # 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())
       latest = int(nh.read())
       nh.close()
       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
+  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
 
-  # 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]
-
-  # 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())