src/tools/bisect-builds.py

   1 #!/usr/bin/env python
   2 # Copyright (c) 2012 The Chromium Authors. All rights reserved.
   3 # Use of this source code is governed by a BSD-style license that can be
   4 # found in the LICENSE file.
   5
   6 """Snapshot Build Bisect Tool
   7
   8 This script bisects a snapshot archive using binary search. It starts at
   9 a bad revision (it will try to guess HEAD) and asks for a last known-good
  10 revision. It will then binary search across this revision range by downloading,
  11 unzipping, and opening Chromium for you. After testing the specific revision,
  12 it will ask you whether it is good or bad before continuing the search.
  13 """
  14
  15 # The root URL for storage.
  16 CHROMIUM_BASE_URL = 'http://commondatastorage.googleapis.com/chromium-browser-snapshots'
  17 WEBKIT_BASE_URL = 'http://commondatastorage.googleapis.com/chromium-webkit-snapshots'
  18
  19 # The root URL for official builds.
  20 OFFICIAL_BASE_URL = 'http://master.chrome.corp.google.com/official_builds'
  21
  22 # Changelogs URL.
  23 CHANGELOG_URL = 'http://build.chromium.org/f/chromium/' \
  24                 'perf/dashboard/ui/changelog.html?' \
  25                 'url=/trunk/src&range=%d%%3A%d'
  26
  27 # Official Changelogs URL.
  28 OFFICIAL_CHANGELOG_URL = 'http://omahaproxy.appspot.com/'\
  29                          'changelog?old_version=%s&new_version=%s'
  30
  31 # DEPS file URL.
  32 DEPS_FILE = 'http://src.chromium.org/viewvc/chrome/trunk/src/DEPS?revision=%d'
  33 # Blink Changelogs URL.
  34 BLINK_CHANGELOG_URL = 'http://build.chromium.org/f/chromium/' \
  35                       'perf/dashboard/ui/changelog_blink.html?' \
  36                       'url=/trunk&range=%d%%3A%d'
  37
  38 DONE_MESSAGE_GOOD_MIN = 'You are probably looking for a change made after %s ' \
  39                         '(known good), but no later than %s (first known bad).'
  40 DONE_MESSAGE_GOOD_MAX = 'You are probably looking for a change made after %s ' \
  41                         '(known bad), but no later than %s (first known good).'
  42
  43 ###############################################################################
  44
  45 import json
  46 import optparse
  47 import os
  48 import re
  49 import shlex
  50 import shutil
  51 import subprocess
  52 import sys
  53 import tempfile
  54 import threading
  55 import urllib
  56 from distutils.version import LooseVersion
  57 from xml.etree import ElementTree
  58 import zipfile
  59
  60
  61 class PathContext(object):
  62   """A PathContext is used to carry the information used to construct URLs and
  63   paths when dealing with the storage server and archives."""
  64   def __init__(self, base_url, platform, good_revision, bad_revision,
  65                is_official, is_aura, flash_path = None):
  66     super(PathContext, self).__init__()
  67     # Store off the input parameters.
  68     self.base_url = base_url
  69     self.platform = platform  # What's passed in to the '-a/--archive' option.
  70     self.good_revision = good_revision
  71     self.bad_revision = bad_revision
  72     self.is_official = is_official
  73     self.is_aura = is_aura
  74     self.flash_path = flash_path
  75
  76     # The name of the ZIP file in a revision directory on the server.
  77     self.archive_name = None
  78
  79     # Set some internal members:
  80     #   _listing_platform_dir = Directory that holds revisions. Ends with a '/'.
  81     #   _archive_extract_dir = Uncompressed directory in the archive_name file.
  82     #   _binary_name = The name of the executable to run.
  83     if self.platform in ('linux', 'linux64', 'linux-arm'):
  84       self._binary_name = 'chrome'
  85     elif self.platform == 'mac':
  86       self.archive_name = 'chrome-mac.zip'
  87       self._archive_extract_dir = 'chrome-mac'
  88     elif self.platform == 'win':
  89       self.archive_name = 'chrome-win32.zip'
  90       self._archive_extract_dir = 'chrome-win32'
  91       self._binary_name = 'chrome.exe'
  92     else:
  93       raise Exception('Invalid platform: %s' % self.platform)
  94
  95     if is_official:
  96       if self.platform == 'linux':
  97         self._listing_platform_dir = 'precise32bit/'
  98         self.archive_name = 'chrome-precise32bit.zip'
  99         self._archive_extract_dir = 'chrome-precise32bit'
 100       elif self.platform == 'linux64':
 101         self._listing_platform_dir = 'precise64bit/'
 102         self.archive_name = 'chrome-precise64bit.zip'
 103         self._archive_extract_dir = 'chrome-precise64bit'
 104       elif self.platform == 'mac':
 105         self._listing_platform_dir = 'mac/'
 106         self._binary_name = 'Google Chrome.app/Contents/MacOS/Google Chrome'
 107       elif self.platform == 'win':
 108         if self.is_aura:
 109           self._listing_platform_dir = 'win-aura/'
 110         else:
 111           self._listing_platform_dir = 'win/'
 112     else:
 113       if self.platform in ('linux', 'linux64', 'linux-arm'):
 114         self.archive_name = 'chrome-linux.zip'
 115         self._archive_extract_dir = 'chrome-linux'
 116         if self.platform == 'linux':
 117           self._listing_platform_dir = 'Linux/'
 118         elif self.platform == 'linux64':
 119           self._listing_platform_dir = 'Linux_x64/'
 120         elif self.platform == 'linux-arm':
 121           self._listing_platform_dir = 'Linux_ARM_Cross-Compile/'
 122       elif self.platform == 'mac':
 123         self._listing_platform_dir = 'Mac/'
 124         self._binary_name = 'Chromium.app/Contents/MacOS/Chromium'
 125       elif self.platform == 'win':
 126         self._listing_platform_dir = 'Win/'
 127
 128   def GetListingURL(self, marker=None):
 129     """Returns the URL for a directory listing, with an optional marker."""
 130     marker_param = ''
 131     if marker:
 132       marker_param = '&marker=' + str(marker)
 133     return self.base_url + '/?delimiter=/&prefix=' + \
 134         self._listing_platform_dir + marker_param
 135
 136   def GetDownloadURL(self, revision):
 137     """Gets the download URL for a build archive of a specific revision."""
 138     if self.is_official:
 139       return "%s/%s/%s%s" % (
 140           OFFICIAL_BASE_URL, revision, self._listing_platform_dir,
 141           self.archive_name)
 142     else:
 143       return "%s/%s%s/%s" % (self.base_url, self._listing_platform_dir,
 144                              revision, self.archive_name)
 145
 146   def GetLastChangeURL(self):
 147     """Returns a URL to the LAST_CHANGE file."""
 148     return self.base_url + '/' + self._listing_platform_dir + 'LAST_CHANGE'
 149
 150   def GetLaunchPath(self):
 151     """Returns a relative path (presumably from the archive extraction location)
 152     that is used to run the executable."""
 153     return os.path.join(self._archive_extract_dir, self._binary_name)
 154
 155   def IsAuraBuild(self, build):
 156     """Check the given build is Aura."""
 157     return build.split('.')[3] == '1'
 158
 159   def IsASANBuild(self, build):
 160     """Check the given build is ASAN build."""
 161     return build.split('.')[3] == '2'
 162
 163   def ParseDirectoryIndex(self):
 164     """Parses the Google Storage directory listing into a list of revision
 165     numbers."""
 166
 167     def _FetchAndParse(url):
 168       """Fetches a URL and returns a 2-Tuple of ([revisions], next-marker). If
 169       next-marker is not None, then the listing is a partial listing and another
 170       fetch should be performed with next-marker being the marker= GET
 171       parameter."""
 172       handle = urllib.urlopen(url)
 173       document = ElementTree.parse(handle)
 174
 175       # All nodes in the tree are namespaced. Get the root's tag name to extract
 176       # the namespace. Etree does namespaces as |{namespace}tag|.
 177       root_tag = document.getroot().tag
 178       end_ns_pos = root_tag.find('}')
 179       if end_ns_pos == -1:
 180         raise Exception("Could not locate end namespace for directory index")
 181       namespace = root_tag[:end_ns_pos + 1]
 182
 183       # Find the prefix (_listing_platform_dir) and whether or not the list is
 184       # truncated.
 185       prefix_len = len(document.find(namespace + 'Prefix').text)
 186       next_marker = None
 187       is_truncated = document.find(namespace + 'IsTruncated')
 188       if is_truncated is not None and is_truncated.text.lower() == 'true':
 189         next_marker = document.find(namespace + 'NextMarker').text
 190
 191       # Get a list of all the revisions.
 192       all_prefixes = document.findall(namespace + 'CommonPrefixes/' +
 193                                       namespace + 'Prefix')
 194       # The <Prefix> nodes have content of the form of
 195       # |_listing_platform_dir/revision/|. Strip off the platform dir and the
 196       # trailing slash to just have a number.
 197       revisions = []
 198       for prefix in all_prefixes:
 199         revnum = prefix.text[prefix_len:-1]
 200         try:
 201           revnum = int(revnum)
 202           revisions.append(revnum)
 203         except ValueError:
 204           pass
 205       return (revisions, next_marker)
 206
 207     # Fetch the first list of revisions.
 208     (revisions, next_marker) = _FetchAndParse(self.GetListingURL())
 209
 210     # If the result list was truncated, refetch with the next marker. Do this
 211     # until an entire directory listing is done.
 212     while next_marker:
 213       next_url = self.GetListingURL(next_marker)
 214       (new_revisions, next_marker) = _FetchAndParse(next_url)
 215       revisions.extend(new_revisions)
 216     return revisions
 217
 218   def GetRevList(self):
 219     """Gets the list of revision numbers between self.good_revision and
 220     self.bad_revision."""
 221     # Download the revlist and filter for just the range between good and bad.
 222     minrev = min(self.good_revision, self.bad_revision)
 223     maxrev = max(self.good_revision, self.bad_revision)
 224     revlist_all = map(int, self.ParseDirectoryIndex())
 225
 226     revlist = [x for x in revlist_all if x >= int(minrev) and x <= int(maxrev)]
 227     revlist.sort()
 228
 229     # Set good and bad revisions to be legit revisions.
 230     if revlist:
 231       if self.good_revision < self.bad_revision:
 232         self.good_revision = revlist[0]
 233         self.bad_revision = revlist[-1]
 234       else:
 235         self.bad_revision = revlist[0]
 236         self.good_revision = revlist[-1]
 237
 238       # Fix chromium rev so that the deps blink revision matches REVISIONS file.
 239       if self.base_url == WEBKIT_BASE_URL:
 240         revlist_all.sort()
 241         self.good_revision = FixChromiumRevForBlink(revlist,
 242                                                     revlist_all,
 243                                                     self,
 244                                                     self.good_revision)
 245         self.bad_revision = FixChromiumRevForBlink(revlist,
 246                                                    revlist_all,
 247                                                    self,
 248                                                    self.bad_revision)
 249     return revlist
 250
 251   def GetOfficialBuildsList(self):
 252     """Gets the list of official build numbers between self.good_revision and
 253     self.bad_revision."""
 254     # Download the revlist and filter for just the range between good and bad.
 255     minrev = min(self.good_revision, self.bad_revision)
 256     maxrev = max(self.good_revision, self.bad_revision)
 257     handle = urllib.urlopen(OFFICIAL_BASE_URL)
 258     dirindex = handle.read()
 259     handle.close()
 260     build_numbers = re.findall(r'<a href="([0-9][0-9].*)/">', dirindex)
 261     final_list = []
 262     i = 0
 263     parsed_build_numbers = [LooseVersion(x) for x in build_numbers]
 264     for build_number in sorted(parsed_build_numbers):
 265       path = OFFICIAL_BASE_URL + '/' + str(build_number) + '/' + \
 266              self._listing_platform_dir + self.archive_name
 267       i = i + 1
 268       try:
 269         connection = urllib.urlopen(path)
 270         connection.close()
 271         if build_number > maxrev:
 272           break
 273         if build_number >= minrev:
 274           # If we are bisecting Aura, we want to include only builds which
 275           # ends with ".1".
 276           if self.is_aura:
 277             if self.IsAuraBuild(str(build_number)):
 278               final_list.append(str(build_number))
 279           # If we are bisecting only official builds (without --aura),
 280           # we can not include builds which ends with '.1' or '.2' since
 281           # they have different folder hierarchy inside.
 282           elif (not self.IsAuraBuild(str(build_number)) and
 283                 not self.IsASANBuild(str(build_number))):
 284             final_list.append(str(build_number))
 285       except urllib.HTTPError, e:
 286         pass
 287     return final_list
 288
 289 def UnzipFilenameToDir(filename, directory):
 290   """Unzip |filename| to |directory|."""
 291   cwd = os.getcwd()
 292   if not os.path.isabs(filename):
 293     filename = os.path.join(cwd, filename)
 294   zf = zipfile.ZipFile(filename)
 295   # Make base.
 296   if not os.path.isdir(directory):
 297     os.mkdir(directory)
 298   os.chdir(directory)
 299   # Extract files.
 300   for info in zf.infolist():
 301     name = info.filename
 302     if name.endswith('/'):  # dir
 303       if not os.path.isdir(name):
 304         os.makedirs(name)
 305     else:  # file
 306       directory = os.path.dirname(name)
 307       if not os.path.isdir(directory):
 308         os.makedirs(directory)
 309       out = open(name, 'wb')
 310       out.write(zf.read(name))
 311       out.close()
 312     # Set permissions. Permission info in external_attr is shifted 16 bits.
 313     os.chmod(name, info.external_attr >> 16L)
 314   os.chdir(cwd)
 315
 316
 317 def FetchRevision(context, rev, filename, quit_event=None, progress_event=None):
 318   """Downloads and unzips revision |rev|.
 319   @param context A PathContext instance.
 320   @param rev The Chromium revision number/tag to download.
 321   @param filename The destination for the downloaded file.
 322   @param quit_event A threading.Event which will be set by the master thread to
 323                     indicate that the download should be aborted.
 324   @param progress_event A threading.Event which will be set by the master thread
 325                     to indicate that the progress of the download should be
 326                     displayed.
 327   """
 328   def ReportHook(blocknum, blocksize, totalsize):
 329     if quit_event and quit_event.isSet():
 330       raise RuntimeError("Aborting download of revision %s" % str(rev))
 331     if progress_event and progress_event.isSet():
 332       size = blocknum * blocksize
 333       if totalsize == -1:  # Total size not known.
 334         progress = "Received %d bytes" % size
 335       else:
 336         size = min(totalsize, size)
 337         progress = "Received %d of %d bytes, %.2f%%" % (
 338             size, totalsize, 100.0 * size / totalsize)
 339       # Send a \r to let all progress messages use just one line of output.
 340       sys.stdout.write("\r" + progress)
 341       sys.stdout.flush()
 342
 343   download_url = context.GetDownloadURL(rev)
 344   try:
 345     urllib.urlretrieve(download_url, filename, ReportHook)
 346     if progress_event and progress_event.isSet():
 347       print
 348   except RuntimeError, e:
 349     pass
 350
 351
 352 def RunRevision(context, revision, zipfile, profile, num_runs, command, args):
 353   """Given a zipped revision, unzip it and run the test."""
 354   print "Trying revision %s..." % str(revision)
 355
 356   # Create a temp directory and unzip the revision into it.
 357   cwd = os.getcwd()
 358   tempdir = tempfile.mkdtemp(prefix='bisect_tmp')
 359   UnzipFilenameToDir(zipfile, tempdir)
 360   os.chdir(tempdir)
 361
 362   # Run the build as many times as specified.
 363   testargs = ['--user-data-dir=%s' % profile] + args
 364   # The sandbox must be run as root on Official Chrome, so bypass it.
 365   if ((context.is_official or context.flash_path) and
 366       context.platform.startswith('linux')):
 367     testargs.append('--no-sandbox')
 368   if context.flash_path:
 369     testargs.append('--ppapi-flash-path=%s' % context.flash_path)
 370     # We have to pass a large enough Flash version, which currently needs not
 371     # be correct. Instead of requiring the user of the script to figure out and
 372     # pass the correct version we just spoof it.
 373     testargs.append('--ppapi-flash-version=99.9.999.999')
 374
 375   runcommand = []
 376   for token in shlex.split(command):
 377     if token == "%a":
 378       runcommand.extend(testargs)
 379     else:
 380       runcommand.append( \
 381           token.replace('%p', os.path.abspath(context.GetLaunchPath())) \
 382                .replace('%s', ' '.join(testargs)))
 383
 384   results = []
 385   for i in range(0, num_runs):
 386     subproc = subprocess.Popen(runcommand,
 387                                bufsize=-1,
 388                                stdout=subprocess.PIPE,
 389                                stderr=subprocess.PIPE)
 390     (stdout, stderr) = subproc.communicate()
 391     results.append((subproc.returncode, stdout, stderr))
 392
 393   os.chdir(cwd)
 394   try:
 395     shutil.rmtree(tempdir, True)
 396   except Exception, e:
 397     pass
 398
 399   for (returncode, stdout, stderr) in results:
 400     if returncode:
 401       return (returncode, stdout, stderr)
 402   return results[0]
 403
 404
 405 def AskIsGoodBuild(rev, official_builds, status, stdout, stderr):
 406   """Ask the user whether build |rev| is good or bad."""
 407   # Loop until we get a response that we can parse.
 408   while True:
 409     response = raw_input('Revision %s is ' \
 410                          '[(g)ood/(b)ad/(r)etry/(u)nknown/(q)uit]: ' %
 411                          str(rev))
 412     if response and response in ('g', 'b', 'r', 'u'):
 413       return response
 414     if response and response == 'q':
 415       raise SystemExit()
 416
 417
 418 class DownloadJob(object):
 419   """DownloadJob represents a task to download a given Chromium revision."""
 420   def __init__(self, context, name, rev, zipfile):
 421     super(DownloadJob, self).__init__()
 422     # Store off the input parameters.
 423     self.context = context
 424     self.name = name
 425     self.rev = rev
 426     self.zipfile = zipfile
 427     self.quit_event = threading.Event()
 428     self.progress_event = threading.Event()
 429
 430   def Start(self):
 431     """Starts the download."""
 432     fetchargs = (self.context,
 433                  self.rev,
 434                  self.zipfile,
 435                  self.quit_event,
 436                  self.progress_event)
 437     self.thread = threading.Thread(target=FetchRevision,
 438                                    name=self.name,
 439                                    args=fetchargs)
 440     self.thread.start()
 441
 442   def Stop(self):
 443     """Stops the download which must have been started previously."""
 444     self.quit_event.set()
 445     self.thread.join()
 446     os.unlink(self.zipfile)
 447
 448   def WaitFor(self):
 449     """Prints a message and waits for the download to complete. The download
 450     must have been started previously."""
 451     print "Downloading revision %s..." % str(self.rev)
 452     self.progress_event.set()  # Display progress of download.
 453     self.thread.join()
 454
 455
 456 def Bisect(base_url,
 457            platform,
 458            official_builds,
 459            is_aura,
 460            good_rev=0,
 461            bad_rev=0,
 462            num_runs=1,
 463            command="%p %a",
 464            try_args=(),
 465            profile=None,
 466            flash_path=None,
 467            interactive=True,
 468            evaluate=AskIsGoodBuild):
 469   """Given known good and known bad revisions, run a binary search on all
 470   archived revisions to determine the last known good revision.
 471
 472   @param platform Which build to download/run ('mac', 'win', 'linux64', etc.).
 473   @param official_builds Specify build type (Chromium or Official build).
 474   @param good_rev Number/tag of the known good revision.
 475   @param bad_rev Number/tag of the known bad revision.
 476   @param num_runs Number of times to run each build for asking good/bad.
 477   @param try_args A tuple of arguments to pass to the test application.
 478   @param profile The name of the user profile to run with.
 479   @param interactive If it is false, use command exit code for good or bad
 480                      judgment of the argument build.
 481   @param evaluate A function which returns 'g' if the argument build is good,
 482                   'b' if it's bad or 'u' if unknown.
 483
 484   Threading is used to fetch Chromium revisions in the background, speeding up
 485   the user's experience. For example, suppose the bounds of the search are
 486   good_rev=0, bad_rev=100. The first revision to be checked is 50. Depending on
 487   whether revision 50 is good or bad, the next revision to check will be either
 488   25 or 75. So, while revision 50 is being checked, the script will download
 489   revisions 25 and 75 in the background. Once the good/bad verdict on rev 50 is
 490   known:
 491
 492     - If rev 50 is good, the download of rev 25 is cancelled, and the next test
 493       is run on rev 75.
 494
 495     - If rev 50 is bad, the download of rev 75 is cancelled, and the next test
 496       is run on rev 25.
 497   """
 498
 499   if not profile:
 500     profile = 'profile'
 501
 502   context = PathContext(base_url, platform, good_rev, bad_rev,
 503                         official_builds, is_aura, flash_path)
 504   cwd = os.getcwd()
 505
 506   print "Downloading list of known revisions..."
 507   _GetDownloadPath = lambda rev: os.path.join(cwd,
 508       '%s-%s' % (str(rev), context.archive_name))
 509   if official_builds:
 510     revlist = context.GetOfficialBuildsList()
 511   else:
 512     revlist = context.GetRevList()
 513
 514   # Get a list of revisions to bisect across.
 515   if len(revlist) < 2:  # Don't have enough builds to bisect.
 516     msg = 'We don\'t have enough builds to bisect. revlist: %s' % revlist
 517     raise RuntimeError(msg)
 518
 519   # Figure out our bookends and first pivot point; fetch the pivot revision.
 520   minrev = 0
 521   maxrev = len(revlist) - 1
 522   pivot = maxrev / 2
 523   rev = revlist[pivot]
 524   zipfile = _GetDownloadPath(rev)
 525   fetch = DownloadJob(context, 'initial_fetch', rev, zipfile)
 526   fetch.Start()
 527   fetch.WaitFor()
 528
 529   # Binary search time!
 530   while fetch and fetch.zipfile and maxrev - minrev > 1:
 531     if bad_rev < good_rev:
 532       min_str, max_str = "bad", "good"
 533     else:
 534       min_str, max_str = "good", "bad"
 535     print 'Bisecting range [%s (%s), %s (%s)].' % (revlist[minrev], min_str, \
 536                                                    revlist[maxrev], max_str)
 537
 538     # Pre-fetch next two possible pivots
 539     #   - down_pivot is the next revision to check if the current revision turns
 540     #     out to be bad.
 541     #   - up_pivot is the next revision to check if the current revision turns
 542     #     out to be good.
 543     down_pivot = int((pivot - minrev) / 2) + minrev
 544     down_fetch = None
 545     if down_pivot != pivot and down_pivot != minrev:
 546       down_rev = revlist[down_pivot]
 547       down_fetch = DownloadJob(context, 'down_fetch', down_rev,
 548                                _GetDownloadPath(down_rev))
 549       down_fetch.Start()
 550
 551     up_pivot = int((maxrev - pivot) / 2) + pivot
 552     up_fetch = None
 553     if up_pivot != pivot and up_pivot != maxrev:
 554       up_rev = revlist[up_pivot]
 555       up_fetch = DownloadJob(context, 'up_fetch', up_rev,
 556                              _GetDownloadPath(up_rev))
 557       up_fetch.Start()
 558
 559     # Run test on the pivot revision.
 560     status = None
 561     stdout = None
 562     stderr = None
 563     try:
 564       (status, stdout, stderr) = RunRevision(context,
 565                                              rev,
 566                                              fetch.zipfile,
 567                                              profile,
 568                                              num_runs,
 569                                              command,
 570                                              try_args)
 571     except Exception, e:
 572       print >> sys.stderr, e
 573
 574     # Call the evaluate function to see if the current revision is good or bad.
 575     # On that basis, kill one of the background downloads and complete the
 576     # other, as described in the comments above.
 577     try:
 578       if not interactive:
 579         if status:
 580           answer = 'b'
 581           print 'Bad revision: %s' % rev
 582         else:
 583           answer = 'g'
 584           print 'Good revision: %s' % rev
 585       else:
 586         answer = evaluate(rev, official_builds, status, stdout, stderr)
 587       if answer == 'g' and good_rev < bad_rev or \
 588           answer == 'b' and bad_rev < good_rev:
 589         fetch.Stop()
 590         minrev = pivot
 591         if down_fetch:
 592           down_fetch.Stop()  # Kill the download of the older revision.
 593           fetch = None
 594         if up_fetch:
 595           up_fetch.WaitFor()
 596           pivot = up_pivot
 597           fetch = up_fetch
 598       elif answer == 'b' and good_rev < bad_rev or \
 599           answer == 'g' and bad_rev < good_rev:
 600         fetch.Stop()
 601         maxrev = pivot
 602         if up_fetch:
 603           up_fetch.Stop()  # Kill the download of the newer revision.
 604           fetch = None
 605         if down_fetch:
 606           down_fetch.WaitFor()
 607           pivot = down_pivot
 608           fetch = down_fetch
 609       elif answer == 'r':
 610         pass  # Retry requires no changes.
 611       elif answer == 'u':
 612         # Nuke the revision from the revlist and choose a new pivot.
 613         fetch.Stop()
 614         revlist.pop(pivot)
 615         maxrev -= 1  # Assumes maxrev >= pivot.
 616
 617         if maxrev - minrev > 1:
 618           # Alternate between using down_pivot or up_pivot for the new pivot
 619           # point, without affecting the range. Do this instead of setting the
 620           # pivot to the midpoint of the new range because adjacent revisions
 621           # are likely affected by the same issue that caused the (u)nknown
 622           # response.
 623           if up_fetch and down_fetch:
 624             fetch = [up_fetch, down_fetch][len(revlist) % 2]
 625           elif up_fetch:
 626             fetch = up_fetch
 627           else:
 628             fetch = down_fetch
 629           fetch.WaitFor()
 630           if fetch == up_fetch:
 631             pivot = up_pivot - 1  # Subtracts 1 because revlist was resized.
 632           else:
 633             pivot = down_pivot
 634           zipfile = fetch.zipfile
 635
 636         if down_fetch and fetch != down_fetch:
 637           down_fetch.Stop()
 638         if up_fetch and fetch != up_fetch:
 639           up_fetch.Stop()
 640       else:
 641         assert False, "Unexpected return value from evaluate(): " + answer
 642     except SystemExit:
 643       print "Cleaning up..."
 644       for f in [_GetDownloadPath(revlist[down_pivot]),
 645                 _GetDownloadPath(revlist[up_pivot])]:
 646         try:
 647           os.unlink(f)
 648         except OSError:
 649           pass
 650       sys.exit(0)
 651
 652     rev = revlist[pivot]
 653
 654   return (revlist[minrev], revlist[maxrev])
 655
 656
 657 def GetBlinkDEPSRevisionForChromiumRevision(rev):
 658   """Returns the blink revision that was in REVISIONS file at
 659   chromium revision |rev|."""
 660   # . doesn't match newlines without re.DOTALL, so this is safe.
 661   blink_re = re.compile(r'webkit_revision\D*(\d+)')
 662   url = urllib.urlopen(DEPS_FILE % rev)
 663   m = blink_re.search(url.read())
 664   url.close()
 665   if m:
 666     return int(m.group(1))
 667   else:
 668     raise Exception('Could not get Blink revision for Chromium rev %d'
 669                     % rev)
 670
 671
 672 def GetBlinkRevisionForChromiumRevision(self, rev):
 673   """Returns the blink revision that was in REVISIONS file at
 674   chromium revision |rev|."""
 675   file_url = "%s/%s%d/REVISIONS" % (self.base_url,
 676                                     self._listing_platform_dir, rev)
 677   url = urllib.urlopen(file_url)
 678   data = json.loads(url.read())
 679   url.close()
 680   if 'webkit_revision' in data:
 681     return data['webkit_revision']
 682   else:
 683     raise Exception('Could not get blink revision for cr rev %d' % rev)
 684
 685 def FixChromiumRevForBlink(revisions_final, revisions, self, rev):
 686   """Returns the chromium revision that has the correct blink revision
 687   for blink bisect, DEPS and REVISIONS file might not match since
 688   blink snapshots point to tip of tree blink.
 689   Note: The revisions_final variable might get modified to include
 690   additional revisions."""
 691
 692   blink_deps_rev = GetBlinkDEPSRevisionForChromiumRevision(rev)
 693
 694   while (GetBlinkRevisionForChromiumRevision(self, rev) > blink_deps_rev):
 695     idx = revisions.index(rev)
 696     if idx > 0:
 697       rev = revisions[idx-1]
 698       if rev not in revisions_final:
 699         revisions_final.insert(0, rev)
 700
 701   revisions_final.sort()
 702   return rev
 703
 704 def GetChromiumRevision(url):
 705   """Returns the chromium revision read from given URL."""
 706   try:
 707     # Location of the latest build revision number
 708     return int(urllib.urlopen(url).read())
 709   except Exception, e:
 710     print('Could not determine latest revision. This could be bad...')
 711     return 999999999
 712
 713
 714 def main():
 715   usage = ('%prog [options] [-- chromium-options]\n'
 716            'Perform binary search on the snapshot builds to find a minimal\n'
 717            'range of revisions where a behavior change happened. The\n'
 718            'behaviors are described as "good" and "bad".\n'
 719            'It is NOT assumed that the behavior of the later revision is\n'
 720            'the bad one.\n'
 721            '\n'
 722            'Revision numbers should use\n'
 723            '  Official versions (e.g. 1.0.1000.0) for official builds. (-o)\n'
 724            '  SVN revisions (e.g. 123456) for chromium builds, from trunk.\n'
 725            '    Use base_trunk_revision from http://omahaproxy.appspot.com/\n'
 726            '    for earlier revs.\n'
 727            '    Chrome\'s about: build number and omahaproxy branch_revision\n'
 728            '    are incorrect, they are from branches.\n'
 729            '\n'
 730            'Tip: add "-- --no-first-run" to bypass the first run prompts.')
 731   parser = optparse.OptionParser(usage=usage)
 732   # Strangely, the default help output doesn't include the choice list.
 733   choices = ['mac', 'win', 'linux', 'linux64', 'linux-arm']
 734             # linux-chromiumos lacks a continuous archive http://crbug.com/78158
 735   parser.add_option('-a', '--archive',
 736                     choices = choices,
 737                     help = 'The buildbot archive to bisect [%s].' %
 738                            '|'.join(choices))
 739   parser.add_option('-o', action="store_true", dest='official_builds',
 740                     help = 'Bisect across official ' +
 741                     'Chrome builds (internal only) instead of ' +
 742                     'Chromium archives.')
 743   parser.add_option('-b', '--bad', type = 'str',
 744                     help = 'A bad revision to start bisection. ' +
 745                     'May be earlier or later than the good revision. ' +
 746                     'Default is HEAD.')
 747   parser.add_option('-f', '--flash_path', type = 'str',
 748                     help = 'Absolute path to a recent Adobe Pepper Flash ' +
 749                     'binary to be used in this bisection (e.g. ' +
 750                     'on Windows C:\...\pepflashplayer.dll and on Linux ' +
 751                     '/opt/google/chrome/PepperFlash/libpepflashplayer.so).')
 752   parser.add_option('-g', '--good', type = 'str',
 753                     help = 'A good revision to start bisection. ' +
 754                     'May be earlier or later than the bad revision. ' +
 755                     'Default is 0.')
 756   parser.add_option('-p', '--profile', '--user-data-dir', type = 'str',
 757                     help = 'Profile to use; this will not reset every run. ' +
 758                     'Defaults to a clean profile.', default = 'profile')
 759   parser.add_option('-t', '--times', type = 'int',
 760                     help = 'Number of times to run each build before asking ' +
 761                     'if it\'s good or bad. Temporary profiles are reused.',
 762                     default = 1)
 763   parser.add_option('-c', '--command', type = 'str',
 764                     help = 'Command to execute. %p and %a refer to Chrome ' +
 765                     'executable and specified extra arguments respectively. ' +
 766                     'Use %s to specify all extra arguments as one string. ' +
 767                     'Defaults to "%p %a". Note that any extra paths ' +
 768                     'specified should be absolute.',
 769                     default = '%p %a')
 770   parser.add_option('-l', '--blink', action='store_true',
 771                     help = 'Use Blink bisect instead of Chromium. ')
 772   parser.add_option('', '--not-interactive', action='store_true',
 773                     help = 'Use command exit code to tell good/bad revision.',
 774                     default=False)
 775   parser.add_option('--aura',
 776                     dest='aura',
 777                     action='store_true',
 778                     default=False,
 779                     help='Allow the script to bisect aura builds')
 780
 781   (opts, args) = parser.parse_args()
 782
 783   if opts.archive is None:
 784     print 'Error: missing required parameter: --archive'
 785     print
 786     parser.print_help()
 787     return 1
 788
 789   if opts.aura:
 790     if opts.archive != 'win' or not opts.official_builds:
 791       print 'Error: Aura is supported only on Windows platform '\
 792             'and official builds.'
 793       return 1
 794
 795   if opts.blink:
 796     base_url = WEBKIT_BASE_URL
 797   else:
 798     base_url = CHROMIUM_BASE_URL
 799
 800   # Create the context. Initialize 0 for the revisions as they are set below.
 801   context = PathContext(base_url, opts.archive, 0, 0,
 802                         opts.official_builds, opts.aura, None)
 803   # Pick a starting point, try to get HEAD for this.
 804   if opts.bad:
 805     bad_rev = opts.bad
 806   else:
 807     bad_rev = '999.0.0.0'
 808     if not opts.official_builds:
 809       bad_rev = GetChromiumRevision(context.GetLastChangeURL())
 810
 811   # Find out when we were good.
 812   if opts.good:
 813     good_rev = opts.good
 814   else:
 815     good_rev = '0.0.0.0' if opts.official_builds else 0
 816
 817   if opts.flash_path:
 818     flash_path = opts.flash_path
 819     msg = 'Could not find Flash binary at %s' % flash_path
 820     assert os.path.exists(flash_path), msg
 821
 822   if opts.official_builds:
 823     good_rev = LooseVersion(good_rev)
 824     bad_rev = LooseVersion(bad_rev)
 825   else:
 826     good_rev = int(good_rev)
 827     bad_rev = int(bad_rev)
 828
 829   if opts.times < 1:
 830     print('Number of times to run (%d) must be greater than or equal to 1.' %
 831           opts.times)
 832     parser.print_help()
 833     return 1
 834
 835   (min_chromium_rev, max_chromium_rev) = Bisect(
 836       base_url, opts.archive, opts.official_builds, opts.aura, good_rev,
 837       bad_rev, opts.times, opts.command, args, opts.profile, opts.flash_path,
 838       not opts.not_interactive)
 839
 840   # Get corresponding blink revisions.
 841   try:
 842     min_blink_rev = GetBlinkRevisionForChromiumRevision(context,
 843                                                         min_chromium_rev)
 844     max_blink_rev = GetBlinkRevisionForChromiumRevision(context,
 845                                                         max_chromium_rev)
 846   except Exception, e:
 847     # Silently ignore the failure.
 848     min_blink_rev, max_blink_rev = 0, 0
 849
 850   if opts.blink:
 851     # We're done. Let the user know the results in an official manner.
 852     if good_rev > bad_rev:
 853       print DONE_MESSAGE_GOOD_MAX % (str(min_blink_rev), str(max_blink_rev))
 854     else:
 855       print DONE_MESSAGE_GOOD_MIN % (str(min_blink_rev), str(max_blink_rev))
 856
 857     print 'BLINK CHANGELOG URL:'
 858     print '  ' + BLINK_CHANGELOG_URL % (max_blink_rev, min_blink_rev)
 859
 860   else:
 861     # We're done. Let the user know the results in an official manner.
 862     if good_rev > bad_rev:
 863       print DONE_MESSAGE_GOOD_MAX % (str(min_chromium_rev),
 864                                      str(max_chromium_rev))
 865     else:
 866       print DONE_MESSAGE_GOOD_MIN % (str(min_chromium_rev),
 867                                      str(max_chromium_rev))
 868     if min_blink_rev != max_blink_rev:
 869       print ("NOTE: There is a Blink roll in the range, "
 870              "you might also want to do a Blink bisect.")
 871
 872     print 'CHANGELOG URL:'
 873     if opts.official_builds:
 874       print OFFICIAL_CHANGELOG_URL % (min_chromium_rev, max_chromium_rev)
 875     else:
 876       print '  ' + CHANGELOG_URL % (min_chromium_rev, max_chromium_rev)
 877
 878 if __name__ == '__main__':
 879   sys.exit(main())