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