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