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 math
  47 import optparse
  48 import os
  49 import pipes
  50 import re
  51 import shlex
  52 import shutil
  53 import subprocess
  54 import sys
  55 import tempfile
  56 import threading
  57 import urllib
  58 from distutils.version import LooseVersion
  59 from xml.etree import ElementTree
  60 import zipfile
  61
  62
  63 class PathContext(object):
  64   """A PathContext is used to carry the information used to construct URLs and
  65   paths when dealing with the storage server and archives."""
  66   def __init__(self, base_url, platform, good_revision, bad_revision,
  67                is_official, is_aura):
  68     super(PathContext, self).__init__()
  69     # Store off the input parameters.
  70     self.base_url = base_url
  71     self.platform = platform  # What's passed in to the '-a/--archive' option.
  72     self.good_revision = good_revision
  73     self.bad_revision = bad_revision
  74     self.is_official = is_official
  75     self.is_aura = is_aura
  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, dir):
 291   """Unzip |filename| to directory |dir|."""
 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(dir):
 298     os.mkdir(dir)
 299   os.chdir(dir)
 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       dir = os.path.dirname(name)
 308       if not os.path.isdir(dir):
 309         os.makedirs(dir)
 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 and context.platform.startswith('linux'):
 367     testargs.append('--no-sandbox')
 368
 369   runcommand = []
 370   for token in shlex.split(command):
 371     if token == "%a":
 372       runcommand.extend(testargs)
 373     else:
 374       runcommand.append( \
 375           token.replace('%p', context.GetLaunchPath()) \
 376                .replace('%s', ' '.join(testargs)))
 377
 378   for i in range(0, num_runs):
 379     subproc = subprocess.Popen(runcommand,
 380                                bufsize=-1,
 381                                stdout=subprocess.PIPE,
 382                                stderr=subprocess.PIPE)
 383     (stdout, stderr) = subproc.communicate()
 384
 385   os.chdir(cwd)
 386   try:
 387     shutil.rmtree(tempdir, True)
 388   except Exception, e:
 389     pass
 390
 391   return (subproc.returncode, stdout, stderr)
 392
 393
 394 def AskIsGoodBuild(rev, official_builds, status, stdout, stderr):
 395   """Ask the user whether build |rev| is good or bad."""
 396   # Loop until we get a response that we can parse.
 397   while True:
 398     response = raw_input('Revision %s is ' \
 399                          '[(g)ood/(b)ad/(r)etry/(u)nknown/(q)uit]: ' %
 400                          str(rev))
 401     if response and response in ('g', 'b', 'r', 'u'):
 402       return response
 403     if response and response == 'q':
 404       raise SystemExit()
 405
 406
 407 class DownloadJob(object):
 408   """DownloadJob represents a task to download a given Chromium revision."""
 409   def __init__(self, context, name, rev, zipfile):
 410     super(DownloadJob, self).__init__()
 411     # Store off the input parameters.
 412     self.context = context
 413     self.name = name
 414     self.rev = rev
 415     self.zipfile = zipfile
 416     self.quit_event = threading.Event()
 417     self.progress_event = threading.Event()
 418
 419   def Start(self):
 420     """Starts the download."""
 421     fetchargs = (self.context,
 422                  self.rev,
 423                  self.zipfile,
 424                  self.quit_event,
 425                  self.progress_event)
 426     self.thread = threading.Thread(target=FetchRevision,
 427                                    name=self.name,
 428                                    args=fetchargs)
 429     self.thread.start()
 430
 431   def Stop(self):
 432     """Stops the download which must have been started previously."""
 433     self.quit_event.set()
 434     self.thread.join()
 435     os.unlink(self.zipfile)
 436
 437   def WaitFor(self):
 438     """Prints a message and waits for the download to complete. The download
 439     must have been started previously."""
 440     print "Downloading revision %s..." % str(self.rev)
 441     self.progress_event.set()  # Display progress of download.
 442     self.thread.join()
 443
 444
 445 def Bisect(base_url,
 446            platform,
 447            official_builds,
 448            is_aura,
 449            good_rev=0,
 450            bad_rev=0,
 451            num_runs=1,
 452            command="%p %a",
 453            try_args=(),
 454            profile=None,
 455            evaluate=AskIsGoodBuild):
 456   """Given known good and known bad revisions, run a binary search on all
 457   archived revisions to determine the last known good revision.
 458
 459   @param platform Which build to download/run ('mac', 'win', 'linux64', etc.).
 460   @param official_builds Specify build type (Chromium or Official build).
 461   @param good_rev Number/tag of the known good revision.
 462   @param bad_rev Number/tag of the known bad revision.
 463   @param num_runs Number of times to run each build for asking good/bad.
 464   @param try_args A tuple of arguments to pass to the test application.
 465   @param profile The name of the user profile to run with.
 466   @param evaluate A function which returns 'g' if the argument build is good,
 467                   'b' if it's bad or 'u' if unknown.
 468
 469   Threading is used to fetch Chromium revisions in the background, speeding up
 470   the user's experience. For example, suppose the bounds of the search are
 471   good_rev=0, bad_rev=100. The first revision to be checked is 50. Depending on
 472   whether revision 50 is good or bad, the next revision to check will be either
 473   25 or 75. So, while revision 50 is being checked, the script will download
 474   revisions 25 and 75 in the background. Once the good/bad verdict on rev 50 is
 475   known:
 476
 477     - If rev 50 is good, the download of rev 25 is cancelled, and the next test
 478       is run on rev 75.
 479
 480     - If rev 50 is bad, the download of rev 75 is cancelled, and the next test
 481       is run on rev 25.
 482   """
 483
 484   if not profile:
 485     profile = 'profile'
 486
 487   context = PathContext(base_url, platform, good_rev, bad_rev,
 488                         official_builds, is_aura)
 489   cwd = os.getcwd()
 490
 491   print "Downloading list of known revisions..."
 492   _GetDownloadPath = lambda rev: os.path.join(cwd,
 493       '%s-%s' % (str(rev), context.archive_name))
 494   if official_builds:
 495     revlist = context.GetOfficialBuildsList()
 496   else:
 497     revlist = context.GetRevList()
 498
 499   # Get a list of revisions to bisect across.
 500   if len(revlist) < 2:  # Don't have enough builds to bisect.
 501     msg = 'We don\'t have enough builds to bisect. revlist: %s' % revlist
 502     raise RuntimeError(msg)
 503
 504   # Figure out our bookends and first pivot point; fetch the pivot revision.
 505   minrev = 0
 506   maxrev = len(revlist) - 1
 507   pivot = maxrev / 2
 508   rev = revlist[pivot]
 509   zipfile = _GetDownloadPath(rev)
 510   fetch = DownloadJob(context, 'initial_fetch', rev, zipfile)
 511   fetch.Start()
 512   fetch.WaitFor()
 513
 514   # Binary search time!
 515   while fetch and fetch.zipfile and maxrev - minrev > 1:
 516     if bad_rev < good_rev:
 517       min_str, max_str = "bad", "good"
 518     else:
 519       min_str, max_str = "good", "bad"
 520     print 'Bisecting range [%s (%s), %s (%s)].' % (revlist[minrev], min_str, \
 521                                                    revlist[maxrev], max_str)
 522
 523     # Pre-fetch next two possible pivots
 524     #   - down_pivot is the next revision to check if the current revision turns
 525     #     out to be bad.
 526     #   - up_pivot is the next revision to check if the current revision turns
 527     #     out to be good.
 528     down_pivot = int((pivot - minrev) / 2) + minrev
 529     down_fetch = None
 530     if down_pivot != pivot and down_pivot != minrev:
 531       down_rev = revlist[down_pivot]
 532       down_fetch = DownloadJob(context, 'down_fetch', down_rev,
 533                                _GetDownloadPath(down_rev))
 534       down_fetch.Start()
 535
 536     up_pivot = int((maxrev - pivot) / 2) + pivot
 537     up_fetch = None
 538     if up_pivot != pivot and up_pivot != maxrev:
 539       up_rev = revlist[up_pivot]
 540       up_fetch = DownloadJob(context, 'up_fetch', up_rev,
 541                              _GetDownloadPath(up_rev))
 542       up_fetch.Start()
 543
 544     # Run test on the pivot revision.
 545     status = None
 546     stdout = None
 547     stderr = None
 548     try:
 549       (status, stdout, stderr) = RunRevision(context,
 550                                              rev,
 551                                              fetch.zipfile,
 552                                              profile,
 553                                              num_runs,
 554                                              command,
 555                                              try_args)
 556     except Exception, e:
 557       print >>sys.stderr, e
 558
 559     # Call the evaluate function to see if the current revision is good or bad.
 560     # On that basis, kill one of the background downloads and complete the
 561     # other, as described in the comments above.
 562     try:
 563       answer = evaluate(rev, official_builds, status, stdout, stderr)
 564       if answer == 'g' and good_rev < bad_rev or \
 565           answer == 'b' and bad_rev < good_rev:
 566         fetch.Stop()
 567         minrev = pivot
 568         if down_fetch:
 569           down_fetch.Stop()  # Kill the download of the older revision.
 570           fetch = None
 571         if up_fetch:
 572           up_fetch.WaitFor()
 573           pivot = up_pivot
 574           fetch = up_fetch
 575       elif answer == 'b' and good_rev < bad_rev or \
 576           answer == 'g' and bad_rev < good_rev:
 577         fetch.Stop()
 578         maxrev = pivot
 579         if up_fetch:
 580           up_fetch.Stop()  # Kill the download of the newer revision.
 581           fetch = None
 582         if down_fetch:
 583           down_fetch.WaitFor()
 584           pivot = down_pivot
 585           fetch = down_fetch
 586       elif answer == 'r':
 587         pass  # Retry requires no changes.
 588       elif answer == 'u':
 589         # Nuke the revision from the revlist and choose a new pivot.
 590         fetch.Stop()
 591         revlist.pop(pivot)
 592         maxrev -= 1  # Assumes maxrev >= pivot.
 593
 594         if maxrev - minrev > 1:
 595           # Alternate between using down_pivot or up_pivot for the new pivot
 596           # point, without affecting the range. Do this instead of setting the
 597           # pivot to the midpoint of the new range because adjacent revisions
 598           # are likely affected by the same issue that caused the (u)nknown
 599           # response.
 600           if up_fetch and down_fetch:
 601             fetch = [up_fetch, down_fetch][len(revlist) % 2]
 602           elif up_fetch:
 603             fetch = up_fetch
 604           else:
 605             fetch = down_fetch
 606           fetch.WaitFor()
 607           if fetch == up_fetch:
 608             pivot = up_pivot - 1  # Subtracts 1 because revlist was resized.
 609           else:
 610             pivot = down_pivot
 611           zipfile = fetch.zipfile
 612
 613         if down_fetch and fetch != down_fetch:
 614           down_fetch.Stop()
 615         if up_fetch and fetch != up_fetch:
 616           up_fetch.Stop()
 617       else:
 618         assert False, "Unexpected return value from evaluate(): " + answer
 619     except SystemExit:
 620       print "Cleaning up..."
 621       for f in [_GetDownloadPath(revlist[down_pivot]),
 622                 _GetDownloadPath(revlist[up_pivot])]:
 623         try:
 624           os.unlink(f)
 625         except OSError:
 626           pass
 627       sys.exit(0)
 628
 629     rev = revlist[pivot]
 630
 631   return (revlist[minrev], revlist[maxrev])
 632
 633
 634 def GetBlinkDEPSRevisionForChromiumRevision(rev):
 635   """Returns the blink revision that was in REVISIONS file at
 636   chromium revision |rev|."""
 637   # . doesn't match newlines without re.DOTALL, so this is safe.
 638   blink_re = re.compile(r'webkit_revision\D*(\d+)')
 639   url = urllib.urlopen(DEPS_FILE % rev)
 640   m = blink_re.search(url.read())
 641   url.close()
 642   if m:
 643     return int(m.group(1))
 644   else:
 645     raise Exception('Could not get Blink revision for Chromium rev %d'
 646                     % rev)
 647
 648
 649 def GetBlinkRevisionForChromiumRevision(self, rev):
 650   """Returns the blink revision that was in REVISIONS file at
 651   chromium revision |rev|."""
 652   file_url = "%s/%s%d/REVISIONS" % (self.base_url,
 653                                     self._listing_platform_dir, rev)
 654   url = urllib.urlopen(file_url)
 655   data = json.loads(url.read())
 656   url.close()
 657   if 'webkit_revision' in data:
 658     return data['webkit_revision']
 659   else:
 660     raise Exception('Could not get blink revision for cr rev %d' % rev)
 661
 662 def FixChromiumRevForBlink(revisions_final, revisions, self, rev):
 663   """Returns the chromium revision that has the correct blink revision
 664   for blink bisect, DEPS and REVISIONS file might not match since
 665   blink snapshots point to tip of tree blink.
 666   Note: The revisions_final variable might get modified to include
 667   additional revisions."""
 668
 669   blink_deps_rev = GetBlinkDEPSRevisionForChromiumRevision(rev)
 670
 671   while (GetBlinkRevisionForChromiumRevision(self, rev) > blink_deps_rev):
 672     idx = revisions.index(rev)
 673     if idx > 0:
 674       rev = revisions[idx-1]
 675       if rev not in revisions_final:
 676         revisions_final.insert(0, rev)
 677
 678   revisions_final.sort()
 679   return rev
 680
 681 def GetChromiumRevision(url):
 682   """Returns the chromium revision read from given URL."""
 683   try:
 684     # Location of the latest build revision number
 685     return int(urllib.urlopen(url).read())
 686   except Exception, e:
 687     print('Could not determine latest revision. This could be bad...')
 688     return 999999999
 689
 690
 691 def main():
 692   usage = ('%prog [options] [-- chromium-options]\n'
 693            'Perform binary search on the snapshot builds to find a minimal\n'
 694            'range of revisions where a behavior change happened. The\n'
 695            'behaviors are described as "good" and "bad".\n'
 696            'It is NOT assumed that the behavior of the later revision is\n'
 697            'the bad one.\n'
 698            '\n'
 699            'Revision numbers should use\n'
 700            '  Official versions (e.g. 1.0.1000.0) for official builds. (-o)\n'
 701            '  SVN revisions (e.g. 123456) for chromium builds, from trunk.\n'
 702            '    Use base_trunk_revision from http://omahaproxy.appspot.com/\n'
 703            '    for earlier revs.\n'
 704            '    Chrome\'s about: build number and omahaproxy branch_revision\n'
 705            '    are incorrect, they are from branches.\n'
 706            '\n'
 707            'Tip: add "-- --no-first-run" to bypass the first run prompts.')
 708   parser = optparse.OptionParser(usage=usage)
 709   # Strangely, the default help output doesn't include the choice list.
 710   choices = ['mac', 'win', 'linux', 'linux64', 'linux-arm']
 711             # linux-chromiumos lacks a continuous archive http://crbug.com/78158
 712   parser.add_option('-a', '--archive',
 713                     choices = choices,
 714                     help = 'The buildbot archive to bisect [%s].' %
 715                            '|'.join(choices))
 716   parser.add_option('-o', action="store_true", dest='official_builds',
 717                     help = 'Bisect across official ' +
 718                     'Chrome builds (internal only) instead of ' +
 719                     'Chromium archives.')
 720   parser.add_option('-b', '--bad', type = 'str',
 721                     help = 'A bad revision to start bisection. ' +
 722                     'May be earlier or later than the good revision. ' +
 723                     'Default is HEAD.')
 724   parser.add_option('-g', '--good', type = 'str',
 725                     help = 'A good revision to start bisection. ' +
 726                     'May be earlier or later than the bad revision. ' +
 727                     'Default is 0.')
 728   parser.add_option('-p', '--profile', '--user-data-dir', type = 'str',
 729                     help = 'Profile to use; this will not reset every run. ' +
 730                     'Defaults to a clean profile.', default = 'profile')
 731   parser.add_option('-t', '--times', type = 'int',
 732                     help = 'Number of times to run each build before asking ' +
 733                     'if it\'s good or bad. Temporary profiles are reused.',
 734                     default = 1)
 735   parser.add_option('-c', '--command', type = 'str',
 736                     help = 'Command to execute. %p and %a refer to Chrome ' +
 737                     'executable and specified extra arguments respectively. ' +
 738                     'Use %s to specify all extra arguments as one string. ' +
 739                     'Defaults to "%p %a". Note that any extra paths ' +
 740                     'specified should be absolute.',
 741                     default = '%p %a');
 742   parser.add_option('-l', '--blink', action='store_true',
 743                     help = 'Use Blink bisect instead of Chromium. ')
 744   parser.add_option('--aura',
 745                     dest='aura',
 746                     action='store_true',
 747                     default=False,
 748                     help='Allow the script to bisect aura builds')
 749
 750   (opts, args) = parser.parse_args()
 751
 752   if opts.archive is None:
 753     print 'Error: missing required parameter: --archive'
 754     print
 755     parser.print_help()
 756     return 1
 757
 758   if opts.aura:
 759     if opts.archive != 'win' or not opts.official_builds:
 760       print 'Error: Aura is supported only on Windows platform '\
 761             'and official builds.'
 762       return 1
 763
 764   if opts.blink:
 765     base_url = WEBKIT_BASE_URL
 766   else:
 767     base_url = CHROMIUM_BASE_URL
 768
 769   # Create the context. Initialize 0 for the revisions as they are set below.
 770   context = PathContext(base_url, opts.archive, 0, 0,
 771                         opts.official_builds, opts.aura)
 772   # Pick a starting point, try to get HEAD for this.
 773   if opts.bad:
 774     bad_rev = opts.bad
 775   else:
 776     bad_rev = '999.0.0.0'
 777     if not opts.official_builds:
 778       bad_rev = GetChromiumRevision(context.GetLastChangeURL())
 779
 780   # Find out when we were good.
 781   if opts.good:
 782     good_rev = opts.good
 783   else:
 784     good_rev = '0.0.0.0' if opts.official_builds else 0
 785
 786   if opts.official_builds:
 787     good_rev = LooseVersion(good_rev)
 788     bad_rev = LooseVersion(bad_rev)
 789   else:
 790     good_rev = int(good_rev)
 791     bad_rev = int(bad_rev)
 792
 793   if opts.times < 1:
 794     print('Number of times to run (%d) must be greater than or equal to 1.' %
 795           opts.times)
 796     parser.print_help()
 797     return 1
 798
 799   (min_chromium_rev, max_chromium_rev) = Bisect(
 800       base_url, opts.archive, opts.official_builds, opts.aura, good_rev,
 801       bad_rev, opts.times, opts.command, args, opts.profile)
 802
 803   # Get corresponding blink revisions.
 804   try:
 805     min_blink_rev = GetBlinkRevisionForChromiumRevision(context,
 806                                                         min_chromium_rev)
 807     max_blink_rev = GetBlinkRevisionForChromiumRevision(context,
 808                                                         max_chromium_rev)
 809   except Exception, e:
 810     # Silently ignore the failure.
 811     min_blink_rev, max_blink_rev = 0, 0
 812
 813   if opts.blink:
 814     # We're done. Let the user know the results in an official manner.
 815     if good_rev > bad_rev:
 816       print DONE_MESSAGE_GOOD_MAX % (str(min_blink_rev), str(max_blink_rev))
 817     else:
 818       print DONE_MESSAGE_GOOD_MIN % (str(min_blink_rev), str(max_blink_rev))
 819
 820     print 'BLINK CHANGELOG URL:'
 821     print '  ' + BLINK_CHANGELOG_URL % (max_blink_rev, min_blink_rev)
 822
 823   else:
 824     # We're done. Let the user know the results in an official manner.
 825     if good_rev > bad_rev:
 826       print DONE_MESSAGE_GOOD_MAX % (str(min_chromium_rev),
 827                                      str(max_chromium_rev))
 828     else:
 829       print DONE_MESSAGE_GOOD_MIN % (str(min_chromium_rev),
 830                                      str(max_chromium_rev))
 831     if min_blink_rev != max_blink_rev:
 832       print ("NOTE: There is a Blink roll in the range, "
 833              "you might also want to do a Blink bisect.")
 834
 835     print 'CHANGELOG URL:'
 836     if opts.official_builds:
 837       print OFFICIAL_CHANGELOG_URL % (min_chromium_rev, max_chromium_rev)
 838     else:
 839       print '  ' + CHANGELOG_URL % (min_chromium_rev, max_chromium_rev)
 840
 841 if __name__ == '__main__':
 842   sys.exit(main())