tools/bisect-perf-regression.py

   1 #!/usr/bin/env python
   2 # Copyright (c) 2013 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 """Performance Test Bisect Tool
   7
   8 This script bisects a series of changelists using binary search. It starts at
   9 a bad revision where a performance metric has regressed, and asks for a last
  10 known-good revision. It will then binary search across this revision range by
  11 syncing, building, and running a performance test. If the change is
  12 suspected to occur as a result of WebKit/V8 changes, the script will
  13 further bisect changes to those depots and attempt to narrow down the revision
  14 range.
  15
  16
  17 An example usage (using svn cl's):
  18
  19 ./tools/bisect-perf-regression.py -c\
  20 "out/Release/performance_ui_tests --gtest_filter=ShutdownTest.SimpleUserQuit"\
  21 -g 168222 -b 168232 -m shutdown/simple-user-quit
  22
  23 Be aware that if you're using the git workflow and specify an svn revision,
  24 the script will attempt to find the git SHA1 where svn changes up to that
  25 revision were merged in.
  26
  27
  28 An example usage (using git hashes):
  29
  30 ./tools/bisect-perf-regression.py -c\
  31 "out/Release/performance_ui_tests --gtest_filter=ShutdownTest.SimpleUserQuit"\
  32 -g 1f6e67861535121c5c819c16a666f2436c207e7b\
  33 -b b732f23b4f81c382db0b23b9035f3dadc7d925bb\
  34 -m shutdown/simple-user-quit
  35
  36 """
  37
  38 import imp
  39 import optparse
  40 import os
  41 import re
  42 import shlex
  43 import subprocess
  44 import sys
  45 import threading
  46
  47 import bisect_utils
  48
  49
  50 # The additional repositories that might need to be bisected.
  51 # If the repository has any dependant repositories (such as skia/src needs
  52 # skia/include and skia/gyp to be updated), specify them in the 'depends'
  53 # so that they're synced appropriately.
  54 # Format is:
  55 # src: path to the working directory.
  56 # recurse: True if this repositry will get bisected.
  57 # depends: A list of other repositories that are actually part of the same
  58 #   repository in svn.
  59 # svn: Needed for git workflow to resolve hashes to svn revisions.
  60 DEPOT_DEPS_NAME = { 'webkit' : {
  61                       "src" : "src/third_party/WebKit",
  62                       "recurse" : True,
  63                       "depends" : None
  64                     },
  65                     'v8' : {
  66                       "src" : "src/v8",
  67                       "recurse" : True,
  68                       "depends" : None
  69                     },
  70                     'skia/src' : {
  71                       "src" : "src/third_party/skia/src",
  72                       "recurse" : True,
  73                       "svn" : "http://skia.googlecode.com/svn/trunk/src",
  74                       "depends" : ['skia/include', 'skia/gyp']
  75                     },
  76                     'skia/include' : {
  77                       "src" : "src/third_party/skia/include",
  78                       "recurse" : False,
  79                       "svn" : "http://skia.googlecode.com/svn/trunk/include",
  80                       "depends" : None
  81                     },
  82                     'skia/gyp' : {
  83                       "src" : "src/third_party/skia/gyp",
  84                       "recurse" : False,
  85                       "svn" : "http://skia.googlecode.com/svn/trunk/gyp",
  86                       "depends" : None
  87                     }
  88                   }
  89
  90 DEPOT_NAMES = DEPOT_DEPS_NAME.keys()
  91
  92 FILE_DEPS_GIT = '.DEPS.git'
  93
  94
  95 def IsStringFloat(string_to_check):
  96   """Checks whether or not the given string can be converted to a floating
  97   point number.
  98
  99   Args:
 100     string_to_check: Input string to check if it can be converted to a float.
 101
 102   Returns:
 103     True if the string can be converted to a float.
 104   """
 105   try:
 106     float(string_to_check)
 107
 108     return True
 109   except ValueError:
 110     return False
 111
 112
 113 def IsStringInt(string_to_check):
 114   """Checks whether or not the given string can be converted to a integer.
 115
 116   Args:
 117     string_to_check: Input string to check if it can be converted to an int.
 118
 119   Returns:
 120     True if the string can be converted to an int.
 121   """
 122   try:
 123     int(string_to_check)
 124
 125     return True
 126   except ValueError:
 127     return False
 128
 129
 130 def RunProcess(command, print_output=False):
 131   """Run an arbitrary command, returning its output and return code.
 132
 133   Args:
 134     command: A list containing the command and args to execute.
 135     print_output: Optional parameter to write output to stdout as it's
 136         being collected.
 137
 138   Returns:
 139     A tuple of the output and return code.
 140   """
 141   # On Windows, use shell=True to get PATH interpretation.
 142   shell = (os.name == 'nt')
 143   proc = subprocess.Popen(command,
 144                           shell=shell,
 145                           stdout=subprocess.PIPE,
 146                           stderr=subprocess.PIPE,
 147                           bufsize=0)
 148
 149   out = ['']
 150   def ReadOutputWhileProcessRuns(stdout, print_output, out):
 151     while True:
 152       line = stdout.readline()
 153       out[0] += line
 154       if line == '':
 155         break
 156       if print_output:
 157         sys.stdout.write(line)
 158
 159   thread = threading.Thread(target=ReadOutputWhileProcessRuns,
 160                             args=(proc.stdout, print_output, out))
 161   thread.start()
 162   proc.wait()
 163   thread.join()
 164
 165   return (out[0], proc.returncode)
 166
 167
 168 def RunGit(command):
 169   """Run a git subcommand, returning its output and return code.
 170
 171   Args:
 172     command: A list containing the args to git.
 173
 174   Returns:
 175     A tuple of the output and return code.
 176   """
 177   command = ['git'] + command
 178
 179   return RunProcess(command)
 180
 181
 182 class SourceControl(object):
 183   """SourceControl is an abstraction over the underlying source control
 184   system used for chromium. For now only git is supported, but in the
 185   future, the svn workflow could be added as well."""
 186   def __init__(self):
 187     super(SourceControl, self).__init__()
 188
 189   def SyncToRevisionWithGClient(self, revision):
 190     """Uses gclient to sync to the specified revision.
 191
 192     ie. gclient sync --revision <revision>
 193
 194     Args:
 195       revision: The git SHA1 or svn CL (depending on workflow).
 196
 197     Returns:
 198       A tuple of the output and return code.
 199     """
 200     args = ['gclient', 'sync', '--revision', revision]
 201
 202     return RunProcess(args)
 203
 204
 205 class GitSourceControl(SourceControl):
 206   """GitSourceControl is used to query the underlying source control. """
 207   def __init__(self):
 208     super(GitSourceControl, self).__init__()
 209
 210   def IsGit(self):
 211     return True
 212
 213   def GetRevisionList(self, revision_range_end, revision_range_start):
 214     """Retrieves a list of revisions between |revision_range_start| and
 215     |revision_range_end|.
 216
 217     Args:
 218       revision_range_end: The SHA1 for the end of the range.
 219       revision_range_start: The SHA1 for the beginning of the range.
 220
 221     Returns:
 222       A list of the revisions between |revision_range_start| and
 223       |revision_range_end| (inclusive).
 224     """
 225     revision_range = '%s..%s' % (revision_range_start, revision_range_end)
 226     cmd = ['log', '--format=%H', '-10000', '--first-parent', revision_range]
 227     (log_output, return_code) = RunGit(cmd)
 228
 229     assert not return_code, 'An error occurred while running'\
 230                             ' "git %s"' % ' '.join(cmd)
 231
 232     revision_hash_list = log_output.split()
 233     revision_hash_list.append(revision_range_start)
 234
 235     return revision_hash_list
 236
 237   def SyncToRevision(self, revision, use_gclient=True):
 238     """Syncs to the specified revision.
 239
 240     Args:
 241       revision: The revision to sync to.
 242       use_gclient: Specifies whether or not we should sync using gclient or
 243         just use source control directly.
 244
 245     Returns:
 246       True if successful.
 247     """
 248
 249     if use_gclient:
 250       results = self.SyncToRevisionWithGClient(revision)
 251     else:
 252       results = RunGit(['checkout', revision])
 253
 254     return not results[1]
 255
 256   def ResolveToRevision(self, revision_to_check, depot, search=1):
 257     """If an SVN revision is supplied, try to resolve it to a git SHA1.
 258
 259     Args:
 260       revision_to_check: The user supplied revision string that may need to be
 261         resolved to a git SHA1.
 262       depot: The depot the revision_to_check is from.
 263       search: The number of changelists to try if the first fails to resolve
 264         to a git hash.
 265
 266     Returns:
 267       A string containing a git SHA1 hash, otherwise None.
 268     """
 269     if not IsStringInt(revision_to_check):
 270       return revision_to_check
 271
 272     depot_svn = 'svn://svn.chromium.org/chrome/trunk/src'
 273
 274     if depot != 'src':
 275       depot_svn = DEPOT_DEPS_NAME[depot]['svn']
 276
 277     svn_revision = int(revision_to_check)
 278     git_revision = None
 279
 280     for i in xrange(svn_revision, svn_revision - search, -1):
 281       svn_pattern = 'git-svn-id: %s@%d' %\
 282                     (depot_svn, i)
 283       cmd = ['log', '--format=%H', '-1', '--grep', svn_pattern, 'origin/master']
 284
 285       (log_output, return_code) = RunGit(cmd)
 286
 287       assert not return_code, 'An error occurred while running'\
 288                               ' "git %s"' % ' '.join(cmd)
 289
 290       if not return_code:
 291         log_output = log_output.strip()
 292
 293         if log_output:
 294           git_revision = log_output
 295
 296           break
 297
 298     return git_revision
 299
 300   def IsInProperBranch(self):
 301     """Confirms they're in the master branch for performing the bisection.
 302     This is needed or gclient will fail to sync properly.
 303
 304     Returns:
 305       True if the current branch on src is 'master'
 306     """
 307     cmd = ['rev-parse', '--abbrev-ref', 'HEAD']
 308     (log_output, return_code) = RunGit(cmd)
 309
 310     assert not return_code, 'An error occurred while running'\
 311                             ' "git %s"' % ' '.join(cmd)
 312
 313     log_output = log_output.strip()
 314
 315     return log_output == "master"
 316
 317   def SVNFindRev(self, revision):
 318     """Maps directly to the 'git svn find-rev' command.
 319
 320     Args:
 321       revision: The git SHA1 to use.
 322
 323     Returns:
 324       An integer changelist #, otherwise None.
 325     """
 326
 327     cmd = ['svn', 'find-rev', revision]
 328
 329     (output, return_code) = RunGit(cmd)
 330
 331     assert not return_code, 'An error occurred while running'\
 332                             ' "git %s"' % ' '.join(cmd)
 333
 334     svn_revision = output.strip()
 335
 336     if IsStringInt(svn_revision):
 337       return int(svn_revision)
 338
 339     return None
 340
 341   def QueryRevisionInfo(self, revision):
 342     """Gathers information on a particular revision, such as author's name,
 343     email, subject, and date.
 344
 345     Args:
 346       revision: Revision you want to gather information on.
 347     Returns:
 348       A dict in the following format:
 349       {
 350         'author': %s,
 351         'email': %s,
 352         'date': %s,
 353         'subject': %s,
 354       }
 355     """
 356     commit_info = {}
 357
 358     formats = ['%cN', '%cE', '%s', '%cD']
 359     targets = ['author', 'email', 'subject', 'date']
 360
 361     for i in xrange(len(formats)):
 362       cmd = ['log', '--format=%s' % formats[i], '-1', revision]
 363       (output, return_code) = RunGit(cmd)
 364       commit_info[targets[i]] = output.rstrip()
 365
 366       assert not return_code, 'An error occurred while running'\
 367                               ' "git %s"' % ' '.join(cmd)
 368
 369     return commit_info
 370
 371
 372 class BisectPerformanceMetrics(object):
 373   """BisectPerformanceMetrics performs a bisection against a list of range
 374   of revisions to narrow down where performance regressions may have
 375   occurred."""
 376
 377   def __init__(self, source_control, opts):
 378     super(BisectPerformanceMetrics, self).__init__()
 379
 380     self.opts = opts
 381     self.source_control = source_control
 382     self.src_cwd = os.getcwd()
 383     self.depot_cwd = {}
 384
 385     for d in DEPOT_NAMES:
 386       # The working directory of each depot is just the path to the depot, but
 387       # since we're already in 'src', we can skip that part.
 388
 389       self.depot_cwd[d] = self.src_cwd + DEPOT_DEPS_NAME[d]['src'][3:]
 390
 391   def GetRevisionList(self, bad_revision, good_revision):
 392     """Retrieves a list of all the commits between the bad revision and
 393     last known good revision."""
 394
 395     revision_work_list = self.source_control.GetRevisionList(bad_revision,
 396                                                              good_revision)
 397
 398     return revision_work_list
 399
 400   def Get3rdPartyRevisionsFromCurrentRevision(self):
 401     """Parses the DEPS file to determine WebKit/v8/etc... versions.
 402
 403     Returns:
 404       A dict in the format {depot:revision} if successful, otherwise None.
 405     """
 406
 407     cwd = os.getcwd()
 408     os.chdir(self.src_cwd)
 409
 410     locals = {'Var': lambda _: locals["vars"][_],
 411               'From': lambda *args: None}
 412     execfile(FILE_DEPS_GIT, {}, locals)
 413
 414     os.chdir(cwd)
 415
 416     results = {}
 417
 418     rxp = re.compile(".git@(?P<revision>[a-fA-F0-9]+)")
 419
 420     for d in DEPOT_NAMES:
 421       if DEPOT_DEPS_NAME[d]['recurse']:
 422         if locals['deps'].has_key(DEPOT_DEPS_NAME[d]['src']):
 423           re_results = rxp.search(locals['deps'][DEPOT_DEPS_NAME[d]['src']])
 424
 425           if re_results:
 426             results[d] = re_results.group('revision')
 427           else:
 428             return None
 429         else:
 430           return None
 431
 432     return results
 433
 434   def BuildCurrentRevision(self):
 435     """Builds chrome and performance_ui_tests on the current revision.
 436
 437     Returns:
 438       True if the build was successful.
 439     """
 440
 441     if self.opts.debug_ignore_build:
 442       return True
 443
 444     gyp_var = os.getenv('GYP_GENERATORS')
 445
 446     num_threads = 16
 447
 448     if self.opts.use_goma:
 449       num_threads = 100
 450
 451     if gyp_var != None and 'ninja' in gyp_var:
 452       args = ['ninja',
 453               '-C',
 454               'out/Release',
 455               '-j%d' % num_threads,
 456               'chrome',
 457               'performance_ui_tests']
 458     else:
 459       args = ['make',
 460               'BUILDTYPE=Release',
 461               '-j%d' % num_threads,
 462               'chrome',
 463               'performance_ui_tests']
 464
 465     cwd = os.getcwd()
 466     os.chdir(self.src_cwd)
 467
 468     (output, return_code) = RunProcess(args,
 469         self.opts.output_buildbot_annotations)
 470
 471     os.chdir(cwd)
 472
 473     return not return_code
 474
 475   def RunGClientHooks(self):
 476     """Runs gclient with runhooks command.
 477
 478     Returns:
 479       True if gclient reports no errors.
 480     """
 481
 482     if self.opts.debug_ignore_build:
 483       return True
 484
 485     results = RunProcess(['gclient', 'runhooks'])
 486
 487     return not results[1]
 488
 489   def ParseMetricValuesFromOutput(self, metric, text):
 490     """Parses output from performance_ui_tests and retrieves the results for
 491     a given metric.
 492
 493     Args:
 494       metric: The metric as a list of [<trace>, <value>] strings.
 495       text: The text to parse the metric values from.
 496
 497     Returns:
 498       A dict of lists of floating point numbers found.
 499
 500       {
 501         'list_name':[values]
 502       }
 503     """
 504     # Format is: RESULT <graph>: <trace>= <value> <units>
 505     metric_formatted = 'RESULT %s: %s=' % (metric[0], metric[1])
 506
 507     text_lines = text.split('\n')
 508     values_list = []
 509
 510     for current_line in text_lines:
 511       # Parse the output from the performance test for the metric we're
 512       # interested in.
 513       metric_re = metric_formatted +\
 514                   "(\s)*(?P<values>[0-9]+(\.[0-9]*)?)"
 515       metric_re = re.compile(metric_re)
 516       regex_results = metric_re.search(current_line)
 517
 518       if not regex_results is None:
 519         values_list += [regex_results.group('values')]
 520       else:
 521         metric_re = metric_formatted +\
 522                     "(\s)*\[(\s)*(?P<values>[0-9,.]+)\]"
 523         metric_re = re.compile(metric_re)
 524         regex_results = metric_re.search(current_line)
 525
 526         if not regex_results is None:
 527           metric_values = regex_results.group('values')
 528
 529           values_list += metric_values.split(',')
 530
 531     values_list = [float(v) for v in values_list if IsStringFloat(v)]
 532     values_dict = {}
 533
 534     # If the metric is times/t, we need to group the timings by page or the
 535     # results aren't very useful.
 536     # Will make the assumption that if pages are supplied, and the metric
 537     # is "times/t", that the results needs to be grouped.
 538     metric_re = "Pages:(\s)*\[(\s)*(?P<values>[a-zA-Z0-9-_,.]+)\]"
 539     metric_re = re.compile(metric_re)
 540
 541     regex_results = metric_re.search(text)
 542     page_names = []
 543
 544     if regex_results:
 545       page_names = regex_results.group('values')
 546       page_names = page_names.split(',')
 547
 548     if not metric == ['times', 't'] or not page_names:
 549       values_dict['%s: %s' % (metric[0], metric[1])] = values_list
 550     else:
 551       if not (len(values_list) % len(page_names)):
 552         values_dict = dict([(k, []) for k in page_names])
 553
 554         # In the case of times/t, values_list is an array of times in the
 555         # order of page_names, repeated X number of times.
 556         # ie.
 557         # page_names = ['www.chromium.org', 'dev.chromium.org']
 558         # values_list = [1, 2, 1, 2, 1, 2]
 559         num_pages = len(page_names)
 560
 561         for i in xrange(len(values_list)):
 562           page_index = i % num_pages
 563
 564           values_dict[page_names[page_index]].append(values_list[i])
 565
 566     return values_dict
 567
 568   def RunPerformanceTestAndParseResults(self, command_to_run, metric):
 569     """Runs a performance test on the current revision by executing the
 570     'command_to_run' and parses the results.
 571
 572     Args:
 573       command_to_run: The command to be run to execute the performance test.
 574       metric: The metric to parse out from the results of the performance test.
 575
 576     Returns:
 577       On success, it will return a tuple of the average value of the metric,
 578       and a success code of 0.
 579     """
 580
 581     if self.opts.debug_ignore_perf_test:
 582       return ({'debug' : 0.0}, 0)
 583
 584     args = shlex.split(command_to_run)
 585
 586     cwd = os.getcwd()
 587     os.chdir(self.src_cwd)
 588
 589     # Can ignore the return code since if the tests fail, it won't return 0.
 590     (output, return_code) = RunProcess(args,
 591         self.opts.output_buildbot_annotations)
 592
 593     os.chdir(cwd)
 594
 595     metric_values = self.ParseMetricValuesFromOutput(metric, output)
 596
 597     # Need to get the average value if there were multiple values.
 598     if metric_values:
 599       for k, v in metric_values.iteritems():
 600         average_metric_value = reduce(lambda x, y: float(x) + float(y),
 601                                       v) / len(v)
 602
 603         metric_values[k] = average_metric_value
 604
 605       return (metric_values, 0)
 606     else:
 607       return ('No values returned from performance test.', -1)
 608
 609   def FindAllRevisionsToSync(self, revision, depot):
 610     """Finds all dependant revisions and depots that need to be synced for a
 611     given revision. This is only useful in the git workflow, as an svn depot
 612     may be split into multiple mirrors.
 613
 614     ie. skia is broken up into 3 git mirrors over skia/src, skia/gyp, and
 615     skia/include. To sync skia/src properly, one has to find the proper
 616     revisions in skia/gyp and skia/include.
 617
 618     Args:
 619       revision: The revision to sync to.
 620       depot: The depot in use at the moment (probably skia).
 621
 622     Returns:
 623       A list of [depot, revision] pairs that need to be synced.
 624     """
 625     revisions_to_sync = [[depot, revision]]
 626
 627     use_gclient = (depot == 'chromium')
 628
 629     # Some SVN depots were split into multiple git depots, so we need to
 630     # figure out for each mirror which git revision to grab. There's no
 631     # guarantee that the SVN revision will exist for each of the dependant
 632     # depots, so we have to grep the git logs and grab the next earlier one.
 633     if not use_gclient and\
 634        DEPOT_DEPS_NAME[depot]['depends'] and\
 635        self.source_control.IsGit():
 636       svn_rev = self.source_control.SVNFindRev(revision)
 637
 638       for d in DEPOT_DEPS_NAME[depot]['depends']:
 639         self.ChangeToDepotWorkingDirectory(d)
 640
 641         dependant_rev = self.source_control.ResolveToRevision(svn_rev, d, 1000)
 642
 643         if dependant_rev:
 644           revisions_to_sync.append([d, dependant_rev])
 645
 646       num_resolved = len(revisions_to_sync)
 647       num_needed = len(DEPOT_DEPS_NAME[depot]['depends'])
 648
 649       self.ChangeToDepotWorkingDirectory(depot)
 650
 651       if not ((num_resolved - 1) == num_needed):
 652         return None
 653
 654     return revisions_to_sync
 655
 656   def SyncBuildAndRunRevision(self, revision, depot, command_to_run, metric):
 657     """Performs a full sync/build/run of the specified revision.
 658
 659     Args:
 660       revision: The revision to sync to.
 661       depot: The depot that's being used at the moment (src, webkit, etc.)
 662       command_to_run: The command to execute the performance test.
 663       metric: The performance metric being tested.
 664
 665     Returns:
 666       On success, a tuple containing the results of the performance test.
 667       Otherwise, a tuple with the error message.
 668     """
 669     use_gclient = (depot == 'chromium')
 670
 671     revisions_to_sync = self.FindAllRevisionsToSync(revision, depot)
 672
 673     if not revisions_to_sync:
 674       return ('Failed to resolve dependant depots.', 1)
 675
 676     success = True
 677
 678     if not self.opts.debug_ignore_sync:
 679       for r in revisions_to_sync:
 680         self.ChangeToDepotWorkingDirectory(r[0])
 681
 682         if not self.source_control.SyncToRevision(r[1], use_gclient):
 683           success = False
 684
 685           break
 686
 687     if success:
 688       if not(use_gclient):
 689         success = self.RunGClientHooks()
 690
 691       if success:
 692         if self.BuildCurrentRevision():
 693           results = self.RunPerformanceTestAndParseResults(command_to_run,
 694                                                            metric)
 695
 696           if results[1] == 0 and use_gclient:
 697             external_revisions = self.Get3rdPartyRevisionsFromCurrentRevision()
 698
 699             if external_revisions:
 700               return (results[0], results[1], external_revisions)
 701             else:
 702               return ('Failed to parse DEPS file for external revisions.', 1)
 703           else:
 704             return results
 705         else:
 706           return ('Failed to build revision: [%s]' % (str(revision, )), 1)
 707       else:
 708         return ('Failed to run [gclient runhooks].', 1)
 709     else:
 710       return ('Failed to sync revision: [%s]' % (str(revision, )), 1)
 711
 712   def CheckIfRunPassed(self, current_value, known_good_value, known_bad_value):
 713     """Given known good and bad values, decide if the current_value passed
 714     or failed.
 715
 716     Args:
 717       current_value: The value of the metric being checked.
 718       known_bad_value: The reference value for a "failed" run.
 719       known_good_value: The reference value for a "passed" run.
 720
 721     Returns:
 722       True if the current_value is closer to the known_good_value than the
 723       known_bad_value.
 724     """
 725     passes = 0
 726     fails = 0
 727
 728     for k in current_value.keys():
 729       dist_to_good_value = abs(current_value[k] - known_good_value[k])
 730       dist_to_bad_value = abs(current_value[k] - known_bad_value[k])
 731
 732       if dist_to_good_value < dist_to_bad_value:
 733         passes += 1
 734       else:
 735         fails += 1
 736
 737     return passes > fails
 738
 739   def ChangeToDepotWorkingDirectory(self, depot_name):
 740     """Given a depot, changes to the appropriate working directory.
 741
 742     Args:
 743       depot_name: The name of the depot (see DEPOT_NAMES).
 744     """
 745     if depot_name == 'chromium':
 746       os.chdir(self.src_cwd)
 747     elif depot_name in DEPOT_NAMES:
 748       os.chdir(self.depot_cwd[depot_name])
 749     else:
 750       assert False, 'Unknown depot [ %s ] encountered. Possibly a new one'\
 751                     ' was added without proper support?' %\
 752                     (depot_name,)
 753
 754   def PrepareToBisectOnDepot(self,
 755                              current_depot,
 756                              end_revision,
 757                              start_revision):
 758     """Changes to the appropriate directory and gathers a list of revisions
 759     to bisect between |start_revision| and |end_revision|.
 760
 761     Args:
 762       current_depot: The depot we want to bisect.
 763       end_revision: End of the revision range.
 764       start_revision: Start of the revision range.
 765
 766     Returns:
 767       A list containing the revisions between |start_revision| and
 768       |end_revision| inclusive.
 769     """
 770     # Change into working directory of external library to run
 771     # subsequent commands.
 772     old_cwd = os.getcwd()
 773     os.chdir(self.depot_cwd[current_depot])
 774
 775     depot_revision_list = self.GetRevisionList(end_revision, start_revision)
 776
 777     os.chdir(old_cwd)
 778
 779     return depot_revision_list
 780
 781   def GatherReferenceValues(self, good_rev, bad_rev, cmd, metric):
 782     """Gathers reference values by running the performance tests on the
 783     known good and bad revisions.
 784
 785     Args:
 786       good_rev: The last known good revision where the performance regression
 787         has not occurred yet.
 788       bad_rev: A revision where the performance regression has already occurred.
 789       cmd: The command to execute the performance test.
 790       metric: The metric being tested for regression.
 791
 792     Returns:
 793       A tuple with the results of building and running each revision.
 794     """
 795     bad_run_results = self.SyncBuildAndRunRevision(bad_rev,
 796                                                    'chromium',
 797                                                    cmd,
 798                                                    metric)
 799
 800     good_run_results = None
 801
 802     if not bad_run_results[1]:
 803       good_run_results = self.SyncBuildAndRunRevision(good_rev,
 804                                                       'chromium',
 805                                                       cmd,
 806                                                       metric)
 807
 808     return (bad_run_results, good_run_results)
 809
 810   def AddRevisionsIntoRevisionData(self, revisions, depot, sort, revision_data):
 811     """Adds new revisions to the revision_data dict and initializes them.
 812
 813     Args:
 814       revisions: List of revisions to add.
 815       depot: Depot that's currently in use (src, webkit, etc...)
 816       sort: Sorting key for displaying revisions.
 817       revision_data: A dict to add the new revisions into. Existing revisions
 818         will have their sort keys offset.
 819     """
 820
 821     num_depot_revisions = len(revisions)
 822
 823     for k, v in revision_data.iteritems():
 824       if v['sort'] > sort:
 825         v['sort'] += num_depot_revisions
 826
 827     for i in xrange(num_depot_revisions):
 828       r = revisions[i]
 829
 830       revision_data[r] = {'revision' : r,
 831                           'depot' : depot,
 832                           'value' : None,
 833                           'passed' : '?',
 834                           'sort' : i + sort + 1}
 835
 836   def PrintRevisionsToBisectMessage(self, revision_list, depot):
 837     if self.opts.output_buildbot_annotations:
 838       step_name = 'Bisection Range: [%s - %s]' % (
 839           revision_list[len(revision_list)-1], revision_list[0])
 840       bisect_utils.OutputAnnotationStepStart(step_name)
 841
 842     print
 843     print 'Revisions to bisect on [%s]:' % depot
 844     for revision_id in revision_list:
 845       print '  -> %s' % (revision_id, )
 846     print
 847
 848     if self.opts.output_buildbot_annotations:
 849       bisect_utils.OutputAnnotationStepClosed()
 850
 851   def Run(self, command_to_run, bad_revision_in, good_revision_in, metric):
 852     """Given known good and bad revisions, run a binary search on all
 853     intermediate revisions to determine the CL where the performance regression
 854     occurred.
 855
 856     Args:
 857         command_to_run: Specify the command to execute the performance test.
 858         good_revision: Number/tag of the known good revision.
 859         bad_revision: Number/tag of the known bad revision.
 860         metric: The performance metric to monitor.
 861
 862     Returns:
 863         A dict with 2 members, 'revision_data' and 'error'. On success,
 864         'revision_data' will contain a dict mapping revision ids to
 865         data about that revision. Each piece of revision data consists of a
 866         dict with the following keys:
 867
 868         'passed': Represents whether the performance test was successful at
 869             that revision. Possible values include: 1 (passed), 0 (failed),
 870             '?' (skipped), 'F' (build failed).
 871         'depot': The depot that this revision is from (ie. WebKit)
 872         'external': If the revision is a 'src' revision, 'external' contains
 873             the revisions of each of the external libraries.
 874         'sort': A sort value for sorting the dict in order of commits.
 875
 876         For example:
 877         {
 878           'error':None,
 879           'revision_data':
 880           {
 881             'CL #1':
 882             {
 883               'passed':False,
 884               'depot':'chromium',
 885               'external':None,
 886               'sort':0
 887             }
 888           }
 889         }
 890
 891         If an error occurred, the 'error' field will contain the message and
 892         'revision_data' will be empty.
 893     """
 894
 895     results = {'revision_data' : {},
 896                'error' : None}
 897
 898     # If they passed SVN CL's, etc... we can try match them to git SHA1's.
 899     bad_revision = self.source_control.ResolveToRevision(bad_revision_in,
 900                                                          'src')
 901     good_revision = self.source_control.ResolveToRevision(good_revision_in,
 902                                                           'src')
 903
 904     if bad_revision is None:
 905       results['error'] = 'Could\'t resolve [%s] to SHA1.' % (bad_revision_in,)
 906       return results
 907
 908     if good_revision is None:
 909       results['error'] = 'Could\'t resolve [%s] to SHA1.' % (good_revision_in,)
 910       return results
 911
 912     if self.opts.output_buildbot_annotations:
 913       bisect_utils.OutputAnnotationStepStart('Gathering Revisions')
 914
 915     print 'Gathering revision range for bisection.'
 916
 917     # Retrieve a list of revisions to do bisection on.
 918     src_revision_list = self.GetRevisionList(bad_revision, good_revision)
 919
 920     if self.opts.output_buildbot_annotations:
 921       bisect_utils.OutputAnnotationStepClosed()
 922
 923     if src_revision_list:
 924       # revision_data will store information about a revision such as the
 925       # depot it came from, the webkit/V8 revision at that time,
 926       # performance timing, build state, etc...
 927       revision_data = results['revision_data']
 928
 929       # revision_list is the list we're binary searching through at the moment.
 930       revision_list = []
 931
 932       sort_key_ids = 0
 933
 934       for current_revision_id in src_revision_list:
 935         sort_key_ids += 1
 936
 937         revision_data[current_revision_id] = {'value' : None,
 938                                               'passed' : '?',
 939                                               'depot' : 'chromium',
 940                                               'external' : None,
 941                                               'sort' : sort_key_ids}
 942         revision_list.append(current_revision_id)
 943
 944       min_revision = 0
 945       max_revision = len(revision_list) - 1
 946
 947       self.PrintRevisionsToBisectMessage(revision_list, 'src')
 948
 949       if self.opts.output_buildbot_annotations:
 950         bisect_utils.OutputAnnotationStepStart('Gathering Reference Values')
 951
 952       print 'Gathering reference values for bisection.'
 953
 954       # Perform the performance tests on the good and bad revisions, to get
 955       # reference values.
 956       (bad_results, good_results) = self.GatherReferenceValues(good_revision,
 957                                                                bad_revision,
 958                                                                command_to_run,
 959                                                                metric)
 960
 961       if self.opts.output_buildbot_annotations:
 962         bisect_utils.OutputAnnotationStepClosed()
 963
 964       if bad_results[1]:
 965         results['error'] = bad_results[0]
 966         return results
 967
 968       if good_results[1]:
 969         results['error'] = good_results[0]
 970         return results
 971
 972
 973       # We need these reference values to determine if later runs should be
 974       # classified as pass or fail.
 975       known_bad_value = bad_results[0]
 976       known_good_value = good_results[0]
 977
 978       # Can just mark the good and bad revisions explicitly here since we
 979       # already know the results.
 980       bad_revision_data = revision_data[revision_list[0]]
 981       bad_revision_data['external'] = bad_results[2]
 982       bad_revision_data['passed'] = 0
 983       bad_revision_data['value'] = known_bad_value
 984
 985       good_revision_data = revision_data[revision_list[max_revision]]
 986       good_revision_data['external'] = good_results[2]
 987       good_revision_data['passed'] = 1
 988       good_revision_data['value'] = known_good_value
 989
 990       while True:
 991         if not revision_list:
 992           break
 993
 994         min_revision_data = revision_data[revision_list[min_revision]]
 995         max_revision_data = revision_data[revision_list[max_revision]]
 996
 997         if max_revision - min_revision <= 1:
 998           if min_revision_data['passed'] == '?':
 999             next_revision_index = min_revision
1000           elif max_revision_data['passed'] == '?':
1001             next_revision_index = max_revision
1002           elif min_revision_data['depot'] == 'chromium':
1003             # If there were changes to any of the external libraries we track,
1004             # should bisect the changes there as well.
1005             external_depot = None
1006
1007             for current_depot in DEPOT_NAMES:
1008               if DEPOT_DEPS_NAME[current_depot]["recurse"]:
1009                 if min_revision_data['external'][current_depot] !=\
1010                    max_revision_data['external'][current_depot]:
1011                   external_depot = current_depot
1012
1013                   break
1014
1015             # If there was no change in any of the external depots, the search
1016             # is over.
1017             if not external_depot:
1018               break
1019
1020             earliest_revision = max_revision_data['external'][current_depot]
1021             latest_revision = min_revision_data['external'][current_depot]
1022
1023             new_revision_list = self.PrepareToBisectOnDepot(external_depot,
1024                                                             latest_revision,
1025                                                             earliest_revision)
1026
1027             if not new_revision_list:
1028               results['error'] = 'An error occurred attempting to retrieve'\
1029                                  ' revision range: [%s..%s]' %\
1030                                  (depot_rev_range[1], depot_rev_range[0])
1031               return results
1032
1033             self.AddRevisionsIntoRevisionData(new_revision_list,
1034                                               external_depot,
1035                                               min_revision_data['sort'],
1036                                               revision_data)
1037
1038             # Reset the bisection and perform it on the newly inserted
1039             # changelists.
1040             revision_list = new_revision_list
1041             min_revision = 0
1042             max_revision = len(revision_list) - 1
1043             sort_key_ids += len(revision_list)
1044
1045             print 'Regression in metric:%s appears to be the result of changes'\
1046                   ' in [%s].' % (metric, current_depot)
1047
1048             self.PrintRevisionsToBisectMessage(revision_list, external_depot)
1049
1050             continue
1051           else:
1052             break
1053         else:
1054           next_revision_index = int((max_revision - min_revision) / 2) +\
1055                                 min_revision
1056
1057         next_revision_id = revision_list[next_revision_index]
1058         next_revision_data = revision_data[next_revision_id]
1059         next_revision_depot = next_revision_data['depot']
1060
1061         self.ChangeToDepotWorkingDirectory(next_revision_depot)
1062
1063         if self.opts.output_buildbot_annotations:
1064           step_name = 'Working on [%s]' % next_revision_id
1065           bisect_utils.OutputAnnotationStepStart(step_name)
1066
1067         print 'Working on revision: [%s]' % next_revision_id
1068
1069         run_results = self.SyncBuildAndRunRevision(next_revision_id,
1070                                                    next_revision_depot,
1071                                                    command_to_run,
1072                                                    metric)
1073
1074         if self.opts.output_buildbot_annotations:
1075           bisect_utils.OutputAnnotationStepClosed()
1076
1077         # If the build is successful, check whether or not the metric
1078         # had regressed.
1079         if not run_results[1]:
1080           if next_revision_depot == 'chromium':
1081             next_revision_data['external'] = run_results[2]
1082
1083           passed_regression = self.CheckIfRunPassed(run_results[0],
1084                                                     known_good_value,
1085                                                     known_bad_value)
1086
1087           next_revision_data['passed'] = passed_regression
1088           next_revision_data['value'] = run_results[0]
1089
1090           if passed_regression:
1091             max_revision = next_revision_index
1092           else:
1093             min_revision = next_revision_index
1094         else:
1095           next_revision_data['passed'] = 'F'
1096
1097           # If the build is broken, remove it and redo search.
1098           revision_list.pop(next_revision_index)
1099
1100           max_revision -= 1
1101     else:
1102       # Weren't able to sync and retrieve the revision range.
1103       results['error'] = 'An error occurred attempting to retrieve revision '\
1104                          'range: [%s..%s]' % (good_revision, bad_revision)
1105
1106     return results
1107
1108   def FormatAndPrintResults(self, bisect_results):
1109     """Prints the results from a bisection run in a readable format.
1110
1111     Args
1112       bisect_results: The results from a bisection test run.
1113     """
1114     revision_data = bisect_results['revision_data']
1115     revision_data_sorted = sorted(revision_data.iteritems(),
1116                                   key = lambda x: x[1]['sort'])
1117
1118     if self.opts.output_buildbot_annotations:
1119       bisect_utils.OutputAnnotationStepStart('Results')
1120
1121     print
1122     print 'Full results of bisection:'
1123     for current_id, current_data  in revision_data_sorted:
1124       build_status = current_data['passed']
1125
1126       if type(build_status) is bool:
1127         build_status = int(build_status)
1128
1129       print '  %8s  %s  %s' % (current_data['depot'], current_id, build_status)
1130     print
1131
1132     # Find range where it possibly broke.
1133     first_working_revision = None
1134     last_broken_revision = None
1135
1136     for k, v in revision_data_sorted:
1137       if v['passed'] == 1:
1138         if not first_working_revision:
1139           first_working_revision = k
1140
1141       if not v['passed']:
1142         last_broken_revision = k
1143
1144     if last_broken_revision != None and first_working_revision != None:
1145       print 'Results: Regression may have occurred in range:'
1146       print '  -> First Bad Revision: [%s] [%s]' %\
1147             (last_broken_revision,
1148             revision_data[last_broken_revision]['depot'])
1149       print '  -> Last Good Revision: [%s] [%s]' %\
1150             (first_working_revision,
1151             revision_data[first_working_revision]['depot'])
1152
1153       cwd = os.getcwd()
1154       self.ChangeToDepotWorkingDirectory(
1155           revision_data[last_broken_revision]['depot'])
1156       info = self.source_control.QueryRevisionInfo(last_broken_revision)
1157
1158       print
1159       print 'Commit  : %s' % last_broken_revision
1160       print 'Author  : %s' % info['author']
1161       print 'Email   : %s' % info['email']
1162       print 'Date    : %s' % info['date']
1163       print 'Subject : %s' % info['subject']
1164       print
1165       os.chdir(cwd)
1166
1167     if self.opts.output_buildbot_annotations:
1168       bisect_utils.OutputAnnotationStepClosed()
1169
1170
1171 def DetermineAndCreateSourceControl():
1172   """Attempts to determine the underlying source control workflow and returns
1173   a SourceControl object.
1174
1175   Returns:
1176     An instance of a SourceControl object, or None if the current workflow
1177     is unsupported.
1178   """
1179
1180   (output, return_code) = RunGit(['rev-parse', '--is-inside-work-tree'])
1181
1182   if output.strip() == 'true':
1183     return GitSourceControl()
1184
1185   return None
1186
1187
1188 def main():
1189
1190   usage = ('%prog [options] [-- chromium-options]\n'
1191            'Perform binary search on revision history to find a minimal '
1192            'range of revisions where a peformance metric regressed.\n')
1193
1194   parser = optparse.OptionParser(usage=usage)
1195
1196   parser.add_option('-c', '--command',
1197                     type='str',
1198                     help='A command to execute your performance test at' +
1199                     ' each point in the bisection.')
1200   parser.add_option('-b', '--bad_revision',
1201                     type='str',
1202                     help='A bad revision to start bisection. ' +
1203                     'Must be later than good revision. May be either a git' +
1204                     ' or svn revision.')
1205   parser.add_option('-g', '--good_revision',
1206                     type='str',
1207                     help='A revision to start bisection where performance' +
1208                     ' test is known to pass. Must be earlier than the ' +
1209                     'bad revision. May be either a git or svn revision.')
1210   parser.add_option('-m', '--metric',
1211                     type='str',
1212                     help='The desired metric to bisect on. For example ' +
1213                     '"vm_rss_final_b/vm_rss_f_b"')
1214   parser.add_option('-w', '--working_directory',
1215                     type='str',
1216                     help='Path to the working directory where the script will '
1217                     'do an initial checkout of the chromium depot. The '
1218                     'files will be placed in a subdirectory "bisect" under '
1219                     'working_directory and that will be used to perform the '
1220                     'bisection. This parameter is optional, if it is not '
1221                     'supplied, the script will work from the current depot.')
1222   parser.add_option('--use_goma',
1223                     action="store_true",
1224                     help='Add a bunch of extra threads for goma.')
1225   parser.add_option('--output_buildbot_annotations',
1226                     action="store_true",
1227                     help='Add extra annotation output for buildbot.')
1228   parser.add_option('--debug_ignore_build',
1229                     action="store_true",
1230                     help='DEBUG: Don\'t perform builds.')
1231   parser.add_option('--debug_ignore_sync',
1232                     action="store_true",
1233                     help='DEBUG: Don\'t perform syncs.')
1234   parser.add_option('--debug_ignore_perf_test',
1235                     action="store_true",
1236                     help='DEBUG: Don\'t perform performance tests.')
1237   (opts, args) = parser.parse_args()
1238
1239   if not opts.command:
1240     print 'Error: missing required parameter: --command'
1241     print
1242     parser.print_help()
1243     return 1
1244
1245   if not opts.good_revision:
1246     print 'Error: missing required parameter: --good_revision'
1247     print
1248     parser.print_help()
1249     return 1
1250
1251   if not opts.bad_revision:
1252     print 'Error: missing required parameter: --bad_revision'
1253     print
1254     parser.print_help()
1255     return 1
1256
1257   if not opts.metric:
1258     print 'Error: missing required parameter: --metric'
1259     print
1260     parser.print_help()
1261     return 1
1262
1263   # Haven't tested the script out on any other platforms yet.
1264   if not os.name in ['posix']:
1265     print "Sorry, this platform isn't supported yet."
1266     print
1267     return 1
1268
1269   metric_values = opts.metric.split('/')
1270   if len(metric_values) != 2:
1271     print "Invalid metric specified: [%s]" % (opts.metric,)
1272     print
1273     return 1
1274
1275   if opts.working_directory:
1276     if bisect_utils.CreateBisectDirectoryAndSetupDepot(opts):
1277       return 1
1278
1279     os.chdir(os.path.join(os.getcwd(), 'src'))
1280
1281   # Check what source control method they're using. Only support git workflow
1282   # at the moment.
1283   source_control = DetermineAndCreateSourceControl()
1284
1285   if not source_control:
1286     print "Sorry, only the git workflow is supported at the moment."
1287     print
1288     return 1
1289
1290   # gClient sync seems to fail if you're not in master branch.
1291   if not source_control.IsInProperBranch() and not opts.debug_ignore_sync:
1292     print "You must switch to master branch to run bisection."
1293     print
1294     return 1
1295
1296   bisect_test = BisectPerformanceMetrics(source_control, opts)
1297   bisect_results = bisect_test.Run(opts.command,
1298                                    opts.bad_revision,
1299                                    opts.good_revision,
1300                                    metric_values)
1301
1302   if not(bisect_results['error']):
1303     bisect_test.FormatAndPrintResults(bisect_results)
1304     return 0
1305   else:
1306     print 'Error: ' + bisect_results['error']
1307     print
1308     return 1
1309
1310 if __name__ == '__main__':
1311   sys.exit(main())