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 errno
  39 import imp
  40 import math
  41 import optparse
  42 import os
  43 import re
  44 import shlex
  45 import shutil
  46 import subprocess
  47 import sys
  48 import threading
  49 import time
  50
  51 import bisect_utils
  52
  53
  54 # The additional repositories that might need to be bisected.
  55 # If the repository has any dependant repositories (such as skia/src needs
  56 # skia/include and skia/gyp to be updated), specify them in the 'depends'
  57 # so that they're synced appropriately.
  58 # Format is:
  59 # src: path to the working directory.
  60 # recurse: True if this repositry will get bisected.
  61 # depends: A list of other repositories that are actually part of the same
  62 #   repository in svn.
  63 # svn: Needed for git workflow to resolve hashes to svn revisions.
  64 DEPOT_DEPS_NAME = {
  65   'webkit' : {
  66     "src" : "src/third_party/WebKit",
  67     "recurse" : True,
  68     "depends" : None
  69   },
  70   'v8' : {
  71     "src" : "src/v8",
  72     "recurse" : True,
  73     "depends" : None,
  74     "build_with": 'v8_bleeding_edge'
  75   },
  76   'v8_bleeding_edge' : {
  77     "src" : "src/v8_bleeding_edge",
  78     "recurse" : False,
  79     "depends" : None,
  80     "svn": "https://v8.googlecode.com/svn/branches/bleeding_edge"
  81   },
  82   'skia/src' : {
  83     "src" : "src/third_party/skia/src",
  84     "recurse" : True,
  85     "svn" : "http://skia.googlecode.com/svn/trunk/src",
  86     "depends" : ['skia/include', 'skia/gyp']
  87   },
  88   'skia/include' : {
  89     "src" : "src/third_party/skia/include",
  90     "recurse" : False,
  91     "svn" : "http://skia.googlecode.com/svn/trunk/include",
  92     "depends" : None
  93   },
  94   'skia/gyp' : {
  95     "src" : "src/third_party/skia/gyp",
  96     "recurse" : False,
  97     "svn" : "http://skia.googlecode.com/svn/trunk/gyp",
  98     "depends" : None
  99   }
 100 }
 101
 102 DEPOT_NAMES = DEPOT_DEPS_NAME.keys()
 103
 104
 105
 106 def CalculateTruncatedMean(data_set, truncate_percent):
 107   """Calculates the truncated mean of a set of values.
 108
 109   Args:
 110     data_set: Set of values to use in calculation.
 111     truncate_percent: The % from the upper/lower portions of the data set to
 112         discard, expressed as a value in [0, 1].
 113
 114   Returns:
 115     The truncated mean as a float.
 116   """
 117   if len(data_set) > 2:
 118     data_set = sorted(data_set)
 119
 120     discard_num_float = len(data_set) * truncate_percent
 121     discard_num_int = int(math.floor(discard_num_float))
 122     kept_weight = len(data_set) - discard_num_float * 2
 123
 124     data_set = data_set[discard_num_int:len(data_set)-discard_num_int]
 125
 126     weight_left = 1.0 - (discard_num_float - discard_num_int)
 127
 128     if weight_left < 1:
 129       # If the % to discard leaves a fractional portion, need to weight those
 130       # values.
 131       unweighted_vals = data_set[1:len(data_set)-1]
 132       weighted_vals = [data_set[0], data_set[len(data_set)-1]]
 133       weighted_vals = [w * weight_left for w in weighted_vals]
 134       data_set = weighted_vals + unweighted_vals
 135   else:
 136     kept_weight = len(data_set)
 137
 138   truncated_mean = reduce(lambda x, y: float(x) + float(y),
 139                           data_set) / kept_weight
 140
 141   return truncated_mean
 142
 143
 144 def CalculateStandardDeviation(v):
 145   mean = CalculateTruncatedMean(v, 0.0)
 146
 147   variances = [float(x) - mean for x in v]
 148   variances = [x * x for x in variances]
 149   variance = reduce(lambda x, y: float(x) + float(y), variances) / (len(v) - 1)
 150   std_dev = math.sqrt(variance)
 151
 152   return std_dev
 153
 154
 155 def IsStringFloat(string_to_check):
 156   """Checks whether or not the given string can be converted to a floating
 157   point number.
 158
 159   Args:
 160     string_to_check: Input string to check if it can be converted to a float.
 161
 162   Returns:
 163     True if the string can be converted to a float.
 164   """
 165   try:
 166     float(string_to_check)
 167
 168     return True
 169   except ValueError:
 170     return False
 171
 172
 173 def IsStringInt(string_to_check):
 174   """Checks whether or not the given string can be converted to a integer.
 175
 176   Args:
 177     string_to_check: Input string to check if it can be converted to an int.
 178
 179   Returns:
 180     True if the string can be converted to an int.
 181   """
 182   try:
 183     int(string_to_check)
 184
 185     return True
 186   except ValueError:
 187     return False
 188
 189
 190 def IsWindows():
 191   """Checks whether or not the script is running on Windows.
 192
 193   Returns:
 194     True if running on Windows.
 195   """
 196   return os.name == 'nt'
 197
 198
 199 def RunProcess(command, print_output=False):
 200   """Run an arbitrary command, returning its output and return code.
 201
 202   Args:
 203     command: A list containing the command and args to execute.
 204     print_output: Optional parameter to write output to stdout as it's
 205         being collected.
 206
 207   Returns:
 208     A tuple of the output and return code.
 209   """
 210   if print_output:
 211     print 'Running: [%s]' % ' '.join(command)
 212
 213   # On Windows, use shell=True to get PATH interpretation.
 214   shell = IsWindows()
 215   proc = subprocess.Popen(command,
 216                           shell=shell,
 217                           stdout=subprocess.PIPE,
 218                           stderr=subprocess.PIPE,
 219                           bufsize=0)
 220
 221   out = ['']
 222   def ReadOutputWhileProcessRuns(stdout, print_output, out):
 223     while True:
 224       line = stdout.readline()
 225       out[0] += line
 226       if line == '':
 227         break
 228       if print_output:
 229         sys.stdout.write(line)
 230
 231   thread = threading.Thread(target=ReadOutputWhileProcessRuns,
 232                             args=(proc.stdout, print_output, out))
 233   thread.start()
 234   proc.wait()
 235   thread.join()
 236
 237   return (out[0], proc.returncode)
 238
 239
 240 def RunGit(command):
 241   """Run a git subcommand, returning its output and return code.
 242
 243   Args:
 244     command: A list containing the args to git.
 245
 246   Returns:
 247     A tuple of the output and return code.
 248   """
 249   command = ['git'] + command
 250
 251   return RunProcess(command)
 252
 253
 254 def BuildWithMake(threads, targets, print_output):
 255   cmd = ['make', 'BUILDTYPE=Release', '-j%d' % threads] + targets
 256
 257   (output, return_code) = RunProcess(cmd, print_output)
 258
 259   return not return_code
 260
 261
 262 def BuildWithNinja(threads, targets, print_output):
 263   cmd = ['ninja', '-C', os.path.join('out', 'Release'),
 264       '-j%d' % threads] + targets
 265
 266   (output, return_code) = RunProcess(cmd, print_output)
 267
 268   return not return_code
 269
 270
 271 def BuildWithVisualStudio(targets, print_output):
 272   path_to_devenv = os.path.abspath(
 273       os.path.join(os.environ['VS100COMNTOOLS'], '..', 'IDE', 'devenv.com'))
 274   path_to_sln = os.path.join(os.getcwd(), 'chrome', 'chrome.sln')
 275   cmd = [path_to_devenv, '/build', 'Release', path_to_sln]
 276
 277   for t in targets:
 278     cmd.extend(['/Project', t])
 279
 280   (output, return_code) = RunProcess(cmd, print_output)
 281
 282   return not return_code
 283
 284
 285 class SourceControl(object):
 286   """SourceControl is an abstraction over the underlying source control
 287   system used for chromium. For now only git is supported, but in the
 288   future, the svn workflow could be added as well."""
 289   def __init__(self):
 290     super(SourceControl, self).__init__()
 291
 292   def SyncToRevisionWithGClient(self, revision):
 293     """Uses gclient to sync to the specified revision.
 294
 295     ie. gclient sync --revision <revision>
 296
 297     Args:
 298       revision: The git SHA1 or svn CL (depending on workflow).
 299
 300     Returns:
 301       The return code of the call.
 302     """
 303     return bisect_utils.RunGClient(['sync', '--revision',
 304         revision, '--verbose'])
 305
 306
 307 class GitSourceControl(SourceControl):
 308   """GitSourceControl is used to query the underlying source control. """
 309   def __init__(self):
 310     super(GitSourceControl, self).__init__()
 311
 312   def IsGit(self):
 313     return True
 314
 315   def GetRevisionList(self, revision_range_end, revision_range_start):
 316     """Retrieves a list of revisions between |revision_range_start| and
 317     |revision_range_end|.
 318
 319     Args:
 320       revision_range_end: The SHA1 for the end of the range.
 321       revision_range_start: The SHA1 for the beginning of the range.
 322
 323     Returns:
 324       A list of the revisions between |revision_range_start| and
 325       |revision_range_end| (inclusive).
 326     """
 327     revision_range = '%s..%s' % (revision_range_start, revision_range_end)
 328     cmd = ['log', '--format=%H', '-10000', '--first-parent', revision_range]
 329     (log_output, return_code) = RunGit(cmd)
 330
 331     assert not return_code, 'An error occurred while running'\
 332                             ' "git %s"' % ' '.join(cmd)
 333
 334     revision_hash_list = log_output.split()
 335     revision_hash_list.append(revision_range_start)
 336
 337     return revision_hash_list
 338
 339   def SyncToRevision(self, revision, use_gclient=True):
 340     """Syncs to the specified revision.
 341
 342     Args:
 343       revision: The revision to sync to.
 344       use_gclient: Specifies whether or not we should sync using gclient or
 345         just use source control directly.
 346
 347     Returns:
 348       True if successful.
 349     """
 350
 351     if use_gclient:
 352       results = self.SyncToRevisionWithGClient(revision)
 353     else:
 354       results = RunGit(['checkout', revision])[1]
 355
 356     return not results
 357
 358   def ResolveToRevision(self, revision_to_check, depot, search):
 359     """If an SVN revision is supplied, try to resolve it to a git SHA1.
 360
 361     Args:
 362       revision_to_check: The user supplied revision string that may need to be
 363         resolved to a git SHA1.
 364       depot: The depot the revision_to_check is from.
 365       search: The number of changelists to try if the first fails to resolve
 366         to a git hash. If the value is negative, the function will search
 367         backwards chronologically, otherwise it will search forward.
 368
 369     Returns:
 370       A string containing a git SHA1 hash, otherwise None.
 371     """
 372     if not IsStringInt(revision_to_check):
 373       return revision_to_check
 374
 375     depot_svn = 'svn://svn.chromium.org/chrome/trunk/src'
 376
 377     if depot != 'src':
 378       depot_svn = DEPOT_DEPS_NAME[depot]['svn']
 379
 380     svn_revision = int(revision_to_check)
 381     git_revision = None
 382
 383     if search > 0:
 384       search_range = xrange(svn_revision, svn_revision + search, 1)
 385     else:
 386       search_range = xrange(svn_revision, svn_revision + search, -1)
 387
 388     for i in search_range:
 389       svn_pattern = 'git-svn-id: %s@%d' % (depot_svn, i)
 390       cmd = ['log', '--format=%H', '-1', '--grep', svn_pattern, 'origin/master']
 391
 392       (log_output, return_code) = RunGit(cmd)
 393
 394       assert not return_code, 'An error occurred while running'\
 395                               ' "git %s"' % ' '.join(cmd)
 396
 397       if not return_code:
 398         log_output = log_output.strip()
 399
 400         if log_output:
 401           git_revision = log_output
 402
 403           break
 404
 405     return git_revision
 406
 407   def IsInProperBranch(self):
 408     """Confirms they're in the master branch for performing the bisection.
 409     This is needed or gclient will fail to sync properly.
 410
 411     Returns:
 412       True if the current branch on src is 'master'
 413     """
 414     cmd = ['rev-parse', '--abbrev-ref', 'HEAD']
 415     (log_output, return_code) = RunGit(cmd)
 416
 417     assert not return_code, 'An error occurred while running'\
 418                             ' "git %s"' % ' '.join(cmd)
 419
 420     log_output = log_output.strip()
 421
 422     return log_output == "master"
 423
 424   def SVNFindRev(self, revision):
 425     """Maps directly to the 'git svn find-rev' command.
 426
 427     Args:
 428       revision: The git SHA1 to use.
 429
 430     Returns:
 431       An integer changelist #, otherwise None.
 432     """
 433
 434     cmd = ['svn', 'find-rev', revision]
 435
 436     (output, return_code) = RunGit(cmd)
 437
 438     assert not return_code, 'An error occurred while running'\
 439                             ' "git %s"' % ' '.join(cmd)
 440
 441     svn_revision = output.strip()
 442
 443     if IsStringInt(svn_revision):
 444       return int(svn_revision)
 445
 446     return None
 447
 448   def QueryRevisionInfo(self, revision):
 449     """Gathers information on a particular revision, such as author's name,
 450     email, subject, and date.
 451
 452     Args:
 453       revision: Revision you want to gather information on.
 454     Returns:
 455       A dict in the following format:
 456       {
 457         'author': %s,
 458         'email': %s,
 459         'date': %s,
 460         'subject': %s,
 461       }
 462     """
 463     commit_info = {}
 464
 465     formats = ['%cN', '%cE', '%s', '%cD']
 466     targets = ['author', 'email', 'subject', 'date']
 467
 468     for i in xrange(len(formats)):
 469       cmd = ['log', '--format=%s' % formats[i], '-1', revision]
 470       (output, return_code) = RunGit(cmd)
 471       commit_info[targets[i]] = output.rstrip()
 472
 473       assert not return_code, 'An error occurred while running'\
 474                               ' "git %s"' % ' '.join(cmd)
 475
 476     return commit_info
 477
 478   def CheckoutFileAtRevision(self, file_name, revision):
 479     """Performs a checkout on a file at the given revision.
 480
 481     Returns:
 482       True if successful.
 483     """
 484     return not RunGit(['checkout', revision, file_name])[1]
 485
 486   def RevertFileToHead(self, file_name):
 487     """Unstages a file and returns it to HEAD.
 488
 489     Returns:
 490       True if successful.
 491     """
 492     # Reset doesn't seem to return 0 on success.
 493     RunGit(['reset', 'HEAD', bisect_utils.FILE_DEPS_GIT])
 494
 495     return not RunGit(['checkout', bisect_utils.FILE_DEPS_GIT])[1]
 496
 497 class BisectPerformanceMetrics(object):
 498   """BisectPerformanceMetrics performs a bisection against a list of range
 499   of revisions to narrow down where performance regressions may have
 500   occurred."""
 501
 502   def __init__(self, source_control, opts):
 503     super(BisectPerformanceMetrics, self).__init__()
 504
 505     self.opts = opts
 506     self.source_control = source_control
 507     self.src_cwd = os.getcwd()
 508     self.depot_cwd = {}
 509     self.cleanup_commands = []
 510
 511     # This always starts true since the script grabs latest first.
 512     self.was_blink = True
 513
 514     for d in DEPOT_NAMES:
 515       # The working directory of each depot is just the path to the depot, but
 516       # since we're already in 'src', we can skip that part.
 517
 518       self.depot_cwd[d] = self.src_cwd + DEPOT_DEPS_NAME[d]['src'][3:]
 519
 520   def PerformCleanup(self):
 521     """Performs cleanup when script is finished."""
 522     os.chdir(self.src_cwd)
 523     for c in self.cleanup_commands:
 524       if c[0] == 'mv':
 525         shutil.move(c[1], c[2])
 526       else:
 527         assert False, 'Invalid cleanup command.'
 528
 529   def GetRevisionList(self, bad_revision, good_revision):
 530     """Retrieves a list of all the commits between the bad revision and
 531     last known good revision."""
 532
 533     revision_work_list = self.source_control.GetRevisionList(bad_revision,
 534                                                              good_revision)
 535
 536     return revision_work_list
 537
 538   def Get3rdPartyRevisionsFromCurrentRevision(self):
 539     """Parses the DEPS file to determine WebKit/v8/etc... versions.
 540
 541     Returns:
 542       A dict in the format {depot:revision} if successful, otherwise None.
 543     """
 544
 545     cwd = os.getcwd()
 546     os.chdir(self.src_cwd)
 547
 548     locals = {'Var': lambda _: locals["vars"][_],
 549               'From': lambda *args: None}
 550     execfile(bisect_utils.FILE_DEPS_GIT, {}, locals)
 551
 552     os.chdir(cwd)
 553
 554     results = {}
 555
 556     rxp = re.compile(".git@(?P<revision>[a-fA-F0-9]+)")
 557
 558     for d in DEPOT_NAMES:
 559       if DEPOT_DEPS_NAME[d]['recurse']:
 560         if locals['deps'].has_key(DEPOT_DEPS_NAME[d]['src']):
 561           re_results = rxp.search(locals['deps'][DEPOT_DEPS_NAME[d]['src']])
 562
 563           if re_results:
 564             results[d] = re_results.group('revision')
 565           else:
 566             return None
 567         else:
 568           return None
 569
 570     return results
 571
 572   def BuildCurrentRevision(self):
 573     """Builds chrome and performance_ui_tests on the current revision.
 574
 575     Returns:
 576       True if the build was successful.
 577     """
 578     if self.opts.debug_ignore_build:
 579       return True
 580
 581     targets = ['chrome', 'performance_ui_tests']
 582     threads = 16
 583     if self.opts.use_goma:
 584       threads = 300
 585
 586     cwd = os.getcwd()
 587     os.chdir(self.src_cwd)
 588
 589     if self.opts.build_preference == 'make':
 590       build_success = BuildWithMake(threads, targets,
 591           self.opts.output_buildbot_annotations)
 592     elif self.opts.build_preference == 'ninja':
 593       if IsWindows():
 594         targets = [t + '.exe' for t in targets]
 595       build_success = BuildWithNinja(threads, targets,
 596           self.opts.output_buildbot_annotations)
 597     elif self.opts.build_preference == 'msvs':
 598       assert IsWindows(), 'msvs is only supported on Windows.'
 599       build_success = BuildWithVisualStudio(targets,
 600           self.opts.output_buildbot_annotations)
 601     else:
 602       assert False, 'No build system defined.'
 603
 604     os.chdir(cwd)
 605
 606     return build_success
 607
 608   def RunGClientHooks(self):
 609     """Runs gclient with runhooks command.
 610
 611     Returns:
 612       True if gclient reports no errors.
 613     """
 614
 615     if self.opts.debug_ignore_build:
 616       return True
 617
 618     return not bisect_utils.RunGClient(['runhooks'])
 619
 620   def ParseMetricValuesFromOutput(self, metric, text):
 621     """Parses output from performance_ui_tests and retrieves the results for
 622     a given metric.
 623
 624     Args:
 625       metric: The metric as a list of [<trace>, <value>] strings.
 626       text: The text to parse the metric values from.
 627
 628     Returns:
 629       A list of floating point numbers found.
 630     """
 631     # Format is: RESULT <graph>: <trace>= <value> <units>
 632     metric_formatted = re.escape('RESULT %s: %s=' % (metric[0], metric[1]))
 633
 634     text_lines = text.split('\n')
 635     values_list = []
 636
 637     for current_line in text_lines:
 638       # Parse the output from the performance test for the metric we're
 639       # interested in.
 640       metric_re = metric_formatted +\
 641                   "(\s)*(?P<values>[0-9]+(\.[0-9]*)?)"
 642       metric_re = re.compile(metric_re)
 643       regex_results = metric_re.search(current_line)
 644
 645       if not regex_results is None:
 646         values_list += [regex_results.group('values')]
 647       else:
 648         metric_re = metric_formatted +\
 649                     "(\s)*\[(\s)*(?P<values>[0-9,.]+)\]"
 650         metric_re = re.compile(metric_re)
 651         regex_results = metric_re.search(current_line)
 652
 653         if not regex_results is None:
 654           metric_values = regex_results.group('values')
 655
 656           values_list += metric_values.split(',')
 657
 658     values_list = [float(v) for v in values_list if IsStringFloat(v)]
 659
 660     # If the metric is times/t, we need to sum the timings in order to get
 661     # similar regression results as the try-bots.
 662
 663     if metric == ['times', 't']:
 664       if values_list:
 665         values_list = [reduce(lambda x, y: float(x) + float(y), values_list)]
 666
 667     return values_list
 668
 669   def RunPerformanceTestAndParseResults(self, command_to_run, metric):
 670     """Runs a performance test on the current revision by executing the
 671     'command_to_run' and parses the results.
 672
 673     Args:
 674       command_to_run: The command to be run to execute the performance test.
 675       metric: The metric to parse out from the results of the performance test.
 676
 677     Returns:
 678       On success, it will return a tuple of the average value of the metric,
 679       and a success code of 0.
 680     """
 681
 682     if self.opts.debug_ignore_perf_test:
 683       return ({'mean': 0.0, 'std_dev': 0.0}, 0)
 684
 685     if IsWindows():
 686       command_to_run = command_to_run.replace('/', r'\\')
 687
 688     args = shlex.split(command_to_run)
 689
 690     cwd = os.getcwd()
 691     os.chdir(self.src_cwd)
 692
 693     start_time = time.time()
 694
 695     metric_values = []
 696     for i in xrange(self.opts.repeat_test_count):
 697       # Can ignore the return code since if the tests fail, it won't return 0.
 698       (output, return_code) = RunProcess(args,
 699           self.opts.output_buildbot_annotations)
 700
 701       metric_values += self.ParseMetricValuesFromOutput(metric, output)
 702
 703       elapsed_minutes = (time.time() - start_time) / 60.0
 704
 705       if elapsed_minutes >= self.opts.repeat_test_max_time or not metric_values:
 706         break
 707
 708     os.chdir(cwd)
 709
 710     # Need to get the average value if there were multiple values.
 711     if metric_values:
 712       truncated_mean = CalculateTruncatedMean(metric_values,
 713           self.opts.truncate_percent)
 714       standard_dev = CalculateStandardDeviation(metric_values)
 715
 716       values = {
 717         'mean': truncated_mean,
 718         'std_dev': standard_dev,
 719       }
 720
 721       print 'Results of performance test: %12f %12f' % (
 722           truncated_mean, standard_dev)
 723       print
 724       return (values, 0)
 725     else:
 726       return ('Invalid metric specified, or no values returned from '
 727           'performance test.', -1)
 728
 729   def FindAllRevisionsToSync(self, revision, depot):
 730     """Finds all dependant revisions and depots that need to be synced for a
 731     given revision. This is only useful in the git workflow, as an svn depot
 732     may be split into multiple mirrors.
 733
 734     ie. skia is broken up into 3 git mirrors over skia/src, skia/gyp, and
 735     skia/include. To sync skia/src properly, one has to find the proper
 736     revisions in skia/gyp and skia/include.
 737
 738     Args:
 739       revision: The revision to sync to.
 740       depot: The depot in use at the moment (probably skia).
 741
 742     Returns:
 743       A list of [depot, revision] pairs that need to be synced.
 744     """
 745     revisions_to_sync = [[depot, revision]]
 746
 747     use_gclient = (depot == 'chromium')
 748
 749     # Some SVN depots were split into multiple git depots, so we need to
 750     # figure out for each mirror which git revision to grab. There's no
 751     # guarantee that the SVN revision will exist for each of the dependant
 752     # depots, so we have to grep the git logs and grab the next earlier one.
 753     if not use_gclient and\
 754        DEPOT_DEPS_NAME[depot]['depends'] and\
 755        self.source_control.IsGit():
 756       svn_rev = self.source_control.SVNFindRev(revision)
 757
 758       for d in DEPOT_DEPS_NAME[depot]['depends']:
 759         self.ChangeToDepotWorkingDirectory(d)
 760
 761         dependant_rev = self.source_control.ResolveToRevision(svn_rev, d, -1000)
 762
 763         if dependant_rev:
 764           revisions_to_sync.append([d, dependant_rev])
 765
 766       num_resolved = len(revisions_to_sync)
 767       num_needed = len(DEPOT_DEPS_NAME[depot]['depends'])
 768
 769       self.ChangeToDepotWorkingDirectory(depot)
 770
 771       if not ((num_resolved - 1) == num_needed):
 772         return None
 773
 774     return revisions_to_sync
 775
 776   def PerformPreBuildCleanup(self):
 777     """Performs necessary cleanup between runs."""
 778     print 'Cleaning up between runs.'
 779     print
 780
 781     # Having these pyc files around between runs can confuse the
 782     # perf tests and cause them to crash.
 783     for (path, dir, files) in os.walk(os.getcwd()):
 784       for cur_file in files:
 785         if cur_file.endswith('.pyc'):
 786           path_to_file = os.path.join(path, cur_file)
 787           os.remove(path_to_file)
 788
 789   def PerformWebkitDirectoryCleanup(self, revision):
 790     """If the script is switching between Blink and WebKit during bisect,
 791     its faster to just delete the directory rather than leave it up to git
 792     to sync.
 793
 794     Returns:
 795       True if successful.
 796     """
 797     if not self.source_control.CheckoutFileAtRevision(
 798         bisect_utils.FILE_DEPS_GIT, revision):
 799       return False
 800
 801     cwd = os.getcwd()
 802     os.chdir(self.src_cwd)
 803
 804     is_blink = bisect_utils.IsDepsFileBlink()
 805
 806     os.chdir(cwd)
 807
 808     if not self.source_control.RevertFileToHead(
 809         bisect_utils.FILE_DEPS_GIT):
 810       return False
 811
 812     if self.was_blink != is_blink:
 813       self.was_blink = is_blink
 814       return bisect_utils.RemoveThirdPartyWebkitDirectory()
 815     return True
 816
 817   def PerformPreSyncCleanup(self, revision, depot):
 818     """Performs any necessary cleanup before syncing.
 819
 820     Returns:
 821       True if successful.
 822     """
 823     if depot == 'chromium':
 824       return self.PerformWebkitDirectoryCleanup(revision)
 825     return True
 826
 827   def SyncBuildAndRunRevision(self, revision, depot, command_to_run, metric):
 828     """Performs a full sync/build/run of the specified revision.
 829
 830     Args:
 831       revision: The revision to sync to.
 832       depot: The depot that's being used at the moment (src, webkit, etc.)
 833       command_to_run: The command to execute the performance test.
 834       metric: The performance metric being tested.
 835
 836     Returns:
 837       On success, a tuple containing the results of the performance test.
 838       Otherwise, a tuple with the error message.
 839     """
 840     use_gclient = (depot == 'chromium')
 841
 842     revisions_to_sync = self.FindAllRevisionsToSync(revision, depot)
 843
 844     if not revisions_to_sync:
 845       return ('Failed to resolve dependant depots.', 1)
 846
 847     if not self.PerformPreSyncCleanup(revision, depot):
 848       return ('Failed to perform pre-sync cleanup.', 1)
 849
 850     success = True
 851
 852     if not self.opts.debug_ignore_sync:
 853       for r in revisions_to_sync:
 854         self.ChangeToDepotWorkingDirectory(r[0])
 855
 856         if use_gclient:
 857           self.PerformPreBuildCleanup()
 858
 859         if not self.source_control.SyncToRevision(r[1], use_gclient):
 860           success = False
 861
 862           break
 863
 864     if success:
 865       if not(use_gclient):
 866         success = self.RunGClientHooks()
 867
 868       if success:
 869         if self.BuildCurrentRevision():
 870           results = self.RunPerformanceTestAndParseResults(command_to_run,
 871                                                            metric)
 872
 873           if results[1] == 0 and use_gclient:
 874             external_revisions = self.Get3rdPartyRevisionsFromCurrentRevision()
 875
 876             if external_revisions:
 877               return (results[0], results[1], external_revisions)
 878             else:
 879               return ('Failed to parse DEPS file for external revisions.', 1)
 880           else:
 881             return results
 882         else:
 883           return ('Failed to build revision: [%s]' % (str(revision, )), 1)
 884       else:
 885         return ('Failed to run [gclient runhooks].', 1)
 886     else:
 887       return ('Failed to sync revision: [%s]' % (str(revision, )), 1)
 888
 889   def CheckIfRunPassed(self, current_value, known_good_value, known_bad_value):
 890     """Given known good and bad values, decide if the current_value passed
 891     or failed.
 892
 893     Args:
 894       current_value: The value of the metric being checked.
 895       known_bad_value: The reference value for a "failed" run.
 896       known_good_value: The reference value for a "passed" run.
 897
 898     Returns:
 899       True if the current_value is closer to the known_good_value than the
 900       known_bad_value.
 901     """
 902     dist_to_good_value = abs(current_value['mean'] - known_good_value['mean'])
 903     dist_to_bad_value = abs(current_value['mean'] - known_bad_value['mean'])
 904
 905     return dist_to_good_value < dist_to_bad_value
 906
 907   def ChangeToDepotWorkingDirectory(self, depot_name):
 908     """Given a depot, changes to the appropriate working directory.
 909
 910     Args:
 911       depot_name: The name of the depot (see DEPOT_NAMES).
 912     """
 913     if depot_name == 'chromium':
 914       os.chdir(self.src_cwd)
 915     elif depot_name in DEPOT_NAMES:
 916       os.chdir(self.depot_cwd[depot_name])
 917     else:
 918       assert False, 'Unknown depot [ %s ] encountered. Possibly a new one'\
 919                     ' was added without proper support?' %\
 920                     (depot_name,)
 921
 922   def PrepareToBisectOnDepot(self,
 923                              current_depot,
 924                              end_revision,
 925                              start_revision):
 926     """Changes to the appropriate directory and gathers a list of revisions
 927     to bisect between |start_revision| and |end_revision|.
 928
 929     Args:
 930       current_depot: The depot we want to bisect.
 931       end_revision: End of the revision range.
 932       start_revision: Start of the revision range.
 933
 934     Returns:
 935       A list containing the revisions between |start_revision| and
 936       |end_revision| inclusive.
 937     """
 938     # Change into working directory of external library to run
 939     # subsequent commands.
 940     old_cwd = os.getcwd()
 941     os.chdir(self.depot_cwd[current_depot])
 942
 943     # V8 (and possibly others) is merged in periodically. Bisecting
 944     # this directory directly won't give much good info.
 945     if DEPOT_DEPS_NAME[current_depot].has_key('build_with'):
 946       new_depot = DEPOT_DEPS_NAME[current_depot]['build_with']
 947
 948       svn_start_revision = self.source_control.SVNFindRev(start_revision)
 949       svn_end_revision = self.source_control.SVNFindRev(end_revision)
 950       os.chdir(self.depot_cwd[new_depot])
 951
 952       start_revision = self.source_control.ResolveToRevision(
 953           svn_start_revision, new_depot, -1000)
 954       end_revision = self.source_control.ResolveToRevision(
 955           svn_end_revision, new_depot, -1000)
 956
 957       old_name = DEPOT_DEPS_NAME[current_depot]['src'][4:]
 958       new_name = DEPOT_DEPS_NAME[new_depot]['src'][4:]
 959
 960       os.chdir(self.src_cwd)
 961
 962       shutil.move(old_name, old_name + '.bak')
 963       shutil.move(new_name, old_name)
 964       os.chdir(self.depot_cwd[current_depot])
 965
 966       self.cleanup_commands.append(['mv', old_name, new_name])
 967       self.cleanup_commands.append(['mv', old_name + '.bak', old_name])
 968
 969       os.chdir(self.depot_cwd[current_depot])
 970
 971     depot_revision_list = self.GetRevisionList(end_revision, start_revision)
 972
 973     os.chdir(old_cwd)
 974
 975     return depot_revision_list
 976
 977   def GatherReferenceValues(self, good_rev, bad_rev, cmd, metric):
 978     """Gathers reference values by running the performance tests on the
 979     known good and bad revisions.
 980
 981     Args:
 982       good_rev: The last known good revision where the performance regression
 983         has not occurred yet.
 984       bad_rev: A revision where the performance regression has already occurred.
 985       cmd: The command to execute the performance test.
 986       metric: The metric being tested for regression.
 987
 988     Returns:
 989       A tuple with the results of building and running each revision.
 990     """
 991     bad_run_results = self.SyncBuildAndRunRevision(bad_rev,
 992                                                    'chromium',
 993                                                    cmd,
 994                                                    metric)
 995
 996     good_run_results = None
 997
 998     if not bad_run_results[1]:
 999       good_run_results = self.SyncBuildAndRunRevision(good_rev,
1000                                                       'chromium',
1001                                                       cmd,
1002                                                       metric)
1003
1004     return (bad_run_results, good_run_results)
1005
1006   def AddRevisionsIntoRevisionData(self, revisions, depot, sort, revision_data):
1007     """Adds new revisions to the revision_data dict and initializes them.
1008
1009     Args:
1010       revisions: List of revisions to add.
1011       depot: Depot that's currently in use (src, webkit, etc...)
1012       sort: Sorting key for displaying revisions.
1013       revision_data: A dict to add the new revisions into. Existing revisions
1014         will have their sort keys offset.
1015     """
1016
1017     num_depot_revisions = len(revisions)
1018
1019     for k, v in revision_data.iteritems():
1020       if v['sort'] > sort:
1021         v['sort'] += num_depot_revisions
1022
1023     for i in xrange(num_depot_revisions):
1024       r = revisions[i]
1025
1026       revision_data[r] = {'revision' : r,
1027                           'depot' : depot,
1028                           'value' : None,
1029                           'passed' : '?',
1030                           'sort' : i + sort + 1}
1031
1032   def PrintRevisionsToBisectMessage(self, revision_list, depot):
1033     if self.opts.output_buildbot_annotations:
1034       step_name = 'Bisection Range: [%s - %s]' % (
1035           revision_list[len(revision_list)-1], revision_list[0])
1036       bisect_utils.OutputAnnotationStepStart(step_name)
1037
1038     print
1039     print 'Revisions to bisect on [%s]:' % depot
1040     for revision_id in revision_list:
1041       print '  -> %s' % (revision_id, )
1042     print
1043
1044     if self.opts.output_buildbot_annotations:
1045       bisect_utils.OutputAnnotationStepClosed()
1046
1047   def Run(self, command_to_run, bad_revision_in, good_revision_in, metric):
1048     """Given known good and bad revisions, run a binary search on all
1049     intermediate revisions to determine the CL where the performance regression
1050     occurred.
1051
1052     Args:
1053         command_to_run: Specify the command to execute the performance test.
1054         good_revision: Number/tag of the known good revision.
1055         bad_revision: Number/tag of the known bad revision.
1056         metric: The performance metric to monitor.
1057
1058     Returns:
1059         A dict with 2 members, 'revision_data' and 'error'. On success,
1060         'revision_data' will contain a dict mapping revision ids to
1061         data about that revision. Each piece of revision data consists of a
1062         dict with the following keys:
1063
1064         'passed': Represents whether the performance test was successful at
1065             that revision. Possible values include: 1 (passed), 0 (failed),
1066             '?' (skipped), 'F' (build failed).
1067         'depot': The depot that this revision is from (ie. WebKit)
1068         'external': If the revision is a 'src' revision, 'external' contains
1069             the revisions of each of the external libraries.
1070         'sort': A sort value for sorting the dict in order of commits.
1071
1072         For example:
1073         {
1074           'error':None,
1075           'revision_data':
1076           {
1077             'CL #1':
1078             {
1079               'passed':False,
1080               'depot':'chromium',
1081               'external':None,
1082               'sort':0
1083             }
1084           }
1085         }
1086
1087         If an error occurred, the 'error' field will contain the message and
1088         'revision_data' will be empty.
1089     """
1090
1091     results = {'revision_data' : {},
1092                'error' : None}
1093
1094     # If they passed SVN CL's, etc... we can try match them to git SHA1's.
1095     bad_revision = self.source_control.ResolveToRevision(bad_revision_in,
1096                                                          'src', 100)
1097     good_revision = self.source_control.ResolveToRevision(good_revision_in,
1098                                                           'src', -100)
1099
1100     if bad_revision is None:
1101       results['error'] = 'Could\'t resolve [%s] to SHA1.' % (bad_revision_in,)
1102       return results
1103
1104     if good_revision is None:
1105       results['error'] = 'Could\'t resolve [%s] to SHA1.' % (good_revision_in,)
1106       return results
1107
1108     if self.opts.output_buildbot_annotations:
1109       bisect_utils.OutputAnnotationStepStart('Gathering Revisions')
1110
1111     print 'Gathering revision range for bisection.'
1112
1113     # Retrieve a list of revisions to do bisection on.
1114     src_revision_list = self.GetRevisionList(bad_revision, good_revision)
1115
1116     if self.opts.output_buildbot_annotations:
1117       bisect_utils.OutputAnnotationStepClosed()
1118
1119     if src_revision_list:
1120       # revision_data will store information about a revision such as the
1121       # depot it came from, the webkit/V8 revision at that time,
1122       # performance timing, build state, etc...
1123       revision_data = results['revision_data']
1124
1125       # revision_list is the list we're binary searching through at the moment.
1126       revision_list = []
1127
1128       sort_key_ids = 0
1129
1130       for current_revision_id in src_revision_list:
1131         sort_key_ids += 1
1132
1133         revision_data[current_revision_id] = {'value' : None,
1134                                               'passed' : '?',
1135                                               'depot' : 'chromium',
1136                                               'external' : None,
1137                                               'sort' : sort_key_ids}
1138         revision_list.append(current_revision_id)
1139
1140       min_revision = 0
1141       max_revision = len(revision_list) - 1
1142
1143       self.PrintRevisionsToBisectMessage(revision_list, 'src')
1144
1145       if self.opts.output_buildbot_annotations:
1146         bisect_utils.OutputAnnotationStepStart('Gathering Reference Values')
1147
1148       print 'Gathering reference values for bisection.'
1149
1150       # Perform the performance tests on the good and bad revisions, to get
1151       # reference values.
1152       (bad_results, good_results) = self.GatherReferenceValues(good_revision,
1153                                                                bad_revision,
1154                                                                command_to_run,
1155                                                                metric)
1156
1157       if self.opts.output_buildbot_annotations:
1158         bisect_utils.OutputAnnotationStepClosed()
1159
1160       if bad_results[1]:
1161         results['error'] = bad_results[0]
1162         return results
1163
1164       if good_results[1]:
1165         results['error'] = good_results[0]
1166         return results
1167
1168
1169       # We need these reference values to determine if later runs should be
1170       # classified as pass or fail.
1171       known_bad_value = bad_results[0]
1172       known_good_value = good_results[0]
1173
1174       # Can just mark the good and bad revisions explicitly here since we
1175       # already know the results.
1176       bad_revision_data = revision_data[revision_list[0]]
1177       bad_revision_data['external'] = bad_results[2]
1178       bad_revision_data['passed'] = 0
1179       bad_revision_data['value'] = known_bad_value
1180
1181       good_revision_data = revision_data[revision_list[max_revision]]
1182       good_revision_data['external'] = good_results[2]
1183       good_revision_data['passed'] = 1
1184       good_revision_data['value'] = known_good_value
1185
1186       while True:
1187         if not revision_list:
1188           break
1189
1190         min_revision_data = revision_data[revision_list[min_revision]]
1191         max_revision_data = revision_data[revision_list[max_revision]]
1192
1193         if max_revision - min_revision <= 1:
1194           if min_revision_data['passed'] == '?':
1195             next_revision_index = min_revision
1196           elif max_revision_data['passed'] == '?':
1197             next_revision_index = max_revision
1198           elif min_revision_data['depot'] == 'chromium':
1199             # If there were changes to any of the external libraries we track,
1200             # should bisect the changes there as well.
1201             external_depot = None
1202
1203             for current_depot in DEPOT_NAMES:
1204               if DEPOT_DEPS_NAME[current_depot]["recurse"]:
1205                 if min_revision_data['external'][current_depot] !=\
1206                    max_revision_data['external'][current_depot]:
1207                   external_depot = current_depot
1208
1209                   break
1210
1211             # If there was no change in any of the external depots, the search
1212             # is over.
1213             if not external_depot:
1214               break
1215
1216             earliest_revision = max_revision_data['external'][current_depot]
1217             latest_revision = min_revision_data['external'][current_depot]
1218
1219             new_revision_list = self.PrepareToBisectOnDepot(external_depot,
1220                                                             latest_revision,
1221                                                             earliest_revision)
1222
1223             if not new_revision_list:
1224               results['error'] = 'An error occurred attempting to retrieve'\
1225                                  ' revision range: [%s..%s]' %\
1226                                  (depot_rev_range[1], depot_rev_range[0])
1227               return results
1228
1229             self.AddRevisionsIntoRevisionData(new_revision_list,
1230                                               external_depot,
1231                                               min_revision_data['sort'],
1232                                               revision_data)
1233
1234             # Reset the bisection and perform it on the newly inserted
1235             # changelists.
1236             revision_list = new_revision_list
1237             min_revision = 0
1238             max_revision = len(revision_list) - 1
1239             sort_key_ids += len(revision_list)
1240
1241             print 'Regression in metric:%s appears to be the result of changes'\
1242                   ' in [%s].' % (metric, current_depot)
1243
1244             self.PrintRevisionsToBisectMessage(revision_list, external_depot)
1245
1246             continue
1247           else:
1248             break
1249         else:
1250           next_revision_index = int((max_revision - min_revision) / 2) +\
1251                                 min_revision
1252
1253         next_revision_id = revision_list[next_revision_index]
1254         next_revision_data = revision_data[next_revision_id]
1255         next_revision_depot = next_revision_data['depot']
1256
1257         self.ChangeToDepotWorkingDirectory(next_revision_depot)
1258
1259         if self.opts.output_buildbot_annotations:
1260           step_name = 'Working on [%s]' % next_revision_id
1261           bisect_utils.OutputAnnotationStepStart(step_name)
1262
1263         print 'Working on revision: [%s]' % next_revision_id
1264
1265         run_results = self.SyncBuildAndRunRevision(next_revision_id,
1266                                                    next_revision_depot,
1267                                                    command_to_run,
1268                                                    metric)
1269
1270         if self.opts.output_buildbot_annotations:
1271           bisect_utils.OutputAnnotationStepClosed()
1272
1273         # If the build is successful, check whether or not the metric
1274         # had regressed.
1275         if not run_results[1]:
1276           if next_revision_depot == 'chromium':
1277             next_revision_data['external'] = run_results[2]
1278
1279           passed_regression = self.CheckIfRunPassed(run_results[0],
1280                                                     known_good_value,
1281                                                     known_bad_value)
1282
1283           next_revision_data['passed'] = passed_regression
1284           next_revision_data['value'] = run_results[0]
1285
1286           if passed_regression:
1287             max_revision = next_revision_index
1288           else:
1289             min_revision = next_revision_index
1290         else:
1291           next_revision_data['passed'] = 'F'
1292
1293           # If the build is broken, remove it and redo search.
1294           revision_list.pop(next_revision_index)
1295
1296           max_revision -= 1
1297     else:
1298       # Weren't able to sync and retrieve the revision range.
1299       results['error'] = 'An error occurred attempting to retrieve revision '\
1300                          'range: [%s..%s]' % (good_revision, bad_revision)
1301
1302     return results
1303
1304   def FormatAndPrintResults(self, bisect_results):
1305     """Prints the results from a bisection run in a readable format.
1306
1307     Args
1308       bisect_results: The results from a bisection test run.
1309     """
1310     revision_data = bisect_results['revision_data']
1311     revision_data_sorted = sorted(revision_data.iteritems(),
1312                                   key = lambda x: x[1]['sort'])
1313
1314     if self.opts.output_buildbot_annotations:
1315       bisect_utils.OutputAnnotationStepStart('Results')
1316
1317     print
1318     print 'Full results of bisection:'
1319     for current_id, current_data  in revision_data_sorted:
1320       build_status = current_data['passed']
1321
1322       if type(build_status) is bool:
1323         build_status = int(build_status)
1324
1325       print '  %8s  %s  %s' % (current_data['depot'], current_id, build_status)
1326     print
1327
1328     print
1329     print 'Tested commits:'
1330     for current_id, current_data in revision_data_sorted:
1331       if current_data['value']:
1332         print '  %8s  %s  %12f %12f' % (
1333             current_data['depot'], current_id,
1334             current_data['value']['mean'], current_data['value']['std_dev'])
1335     print
1336
1337     # Find range where it possibly broke.
1338     first_working_revision = None
1339     last_broken_revision = None
1340
1341     for k, v in revision_data_sorted:
1342       if v['passed'] == 1:
1343         if not first_working_revision:
1344           first_working_revision = k
1345
1346       if not v['passed']:
1347         last_broken_revision = k
1348
1349     if last_broken_revision != None and first_working_revision != None:
1350       print 'Results: Regression may have occurred in range:'
1351       print '  -> First Bad Revision: [%s] [%s]' %\
1352             (last_broken_revision,
1353             revision_data[last_broken_revision]['depot'])
1354       print '  -> Last Good Revision: [%s] [%s]' %\
1355             (first_working_revision,
1356             revision_data[first_working_revision]['depot'])
1357
1358       cwd = os.getcwd()
1359       self.ChangeToDepotWorkingDirectory(
1360           revision_data[last_broken_revision]['depot'])
1361       info = self.source_control.QueryRevisionInfo(last_broken_revision)
1362
1363       print
1364       print 'Commit  : %s' % last_broken_revision
1365       print 'Author  : %s' % info['author']
1366       print 'Email   : %s' % info['email']
1367       print 'Date    : %s' % info['date']
1368       print 'Subject : %s' % info['subject']
1369       print
1370       os.chdir(cwd)
1371
1372       # Give a warning if the values were very close together
1373       good_std_dev = revision_data[first_working_revision]['value']['std_dev']
1374       good_mean = revision_data[first_working_revision]['value']['mean']
1375       bad_mean = revision_data[last_broken_revision]['value']['mean']
1376
1377       # A standard deviation of 0 could indicate either insufficient runs
1378       # or a test that consistently returns the same value.
1379       if good_std_dev > 0:
1380         deviations = math.fabs(bad_mean - good_mean) / good_std_dev
1381
1382         if deviations < 1.5:
1383           print 'Warning: Regression was less than 1.5 standard deviations '\
1384                 'from "good" value. Results may not be accurate.'
1385           print
1386       elif self.opts.repeat_test_count == 1:
1387         print 'Warning: Tests were only set to run once. This may be '\
1388               'insufficient to get meaningful results.'
1389         print
1390
1391       # Check for any other possible regression ranges
1392       prev_revision_data = revision_data_sorted[0][1]
1393       prev_revision_id = revision_data_sorted[0][0]
1394       possible_regressions = []
1395       for current_id, current_data in revision_data_sorted:
1396         if current_data['value']:
1397           prev_mean = prev_revision_data['value']['mean']
1398           cur_mean = current_data['value']['mean']
1399
1400           if good_std_dev:
1401             deviations = math.fabs(prev_mean - cur_mean) / good_std_dev
1402           else:
1403             deviations = None
1404
1405           if good_mean:
1406             percent_change = (prev_mean - cur_mean) / good_mean
1407
1408             # If the "good" valuse are supposed to be higher than the "bad"
1409             # values (ie. scores), flip the sign of the percent change so that
1410             # a positive value always represents a regression.
1411             if bad_mean < good_mean:
1412               percent_change *= -1.0
1413           else:
1414             percent_change = None
1415
1416           if deviations >= 1.5 or percent_change > 0.01:
1417             if current_id != first_working_revision:
1418               possible_regressions.append(
1419                   [current_id, prev_revision_id, percent_change, deviations])
1420           prev_revision_data = current_data
1421           prev_revision_id = current_id
1422
1423       if possible_regressions:
1424         print
1425         print 'Other regressions may have occurred:'
1426         print
1427         for p in possible_regressions:
1428           current_id = p[0]
1429           percent_change = p[2]
1430           deviations = p[3]
1431           current_data = revision_data[current_id]
1432           previous_id = p[1]
1433           previous_data = revision_data[previous_id]
1434
1435           if deviations is None:
1436             deviations = 'N/A'
1437           else:
1438             deviations = '%.2f' % deviations
1439
1440           if percent_change is None:
1441             percent_change = 0
1442
1443           print '  %8s  %s  [%.2f%%, %s x std.dev]' % (
1444               previous_data['depot'], previous_id, 100 * percent_change,
1445               deviations)
1446           print '  %8s  %s' % (
1447               current_data['depot'], current_id)
1448           print
1449
1450     if self.opts.output_buildbot_annotations:
1451       bisect_utils.OutputAnnotationStepClosed()
1452
1453
1454 def DetermineAndCreateSourceControl():
1455   """Attempts to determine the underlying source control workflow and returns
1456   a SourceControl object.
1457
1458   Returns:
1459     An instance of a SourceControl object, or None if the current workflow
1460     is unsupported.
1461   """
1462
1463   (output, return_code) = RunGit(['rev-parse', '--is-inside-work-tree'])
1464
1465   if output.strip() == 'true':
1466     return GitSourceControl()
1467
1468   return None
1469
1470
1471 def SetNinjaBuildSystemDefault():
1472   """Makes ninja the default build system to be used by
1473   the bisection script."""
1474   gyp_var = os.getenv('GYP_GENERATORS')
1475
1476   if not gyp_var or not 'ninja' in gyp_var:
1477     if gyp_var:
1478       os.environ['GYP_GENERATORS'] = gyp_var + ',ninja'
1479     else:
1480       os.environ['GYP_GENERATORS'] = 'ninja'
1481
1482     if IsWindows():
1483       os.environ['GYP_DEFINES'] = 'component=shared_library '\
1484           'incremental_chrome_dll=1 disable_nacl=1 fastbuild=1 '\
1485           'chromium_win_pch=0'
1486
1487
1488 def SetMakeBuildSystemDefault():
1489   """Makes make the default build system to be used by
1490   the bisection script."""
1491   os.environ['GYP_GENERATORS'] = 'make'
1492
1493
1494 def CheckPlatformSupported(opts):
1495   """Checks that this platform and build system are supported.
1496
1497   Args:
1498     opts: The options parsed from the command line.
1499
1500   Returns:
1501     True if the platform and build system are supported.
1502   """
1503   # Haven't tested the script out on any other platforms yet.
1504   supported = ['posix', 'nt']
1505   if not os.name in supported:
1506     print "Sorry, this platform isn't supported yet."
1507     print
1508     return False
1509
1510   if IsWindows():
1511     if not opts.build_preference:
1512       opts.build_preference = 'msvs'
1513
1514     if opts.build_preference == 'msvs':
1515       if not os.getenv('VS100COMNTOOLS'):
1516         print 'Error: Path to visual studio could not be determined.'
1517         print
1518         return False
1519     elif opts.build_preference == 'ninja':
1520       SetNinjaBuildSystemDefault()
1521     else:
1522       assert False, 'Error: %s build not supported' % opts.build_preference
1523   else:
1524     if not opts.build_preference:
1525       if 'ninja' in os.getenv('GYP_GENERATORS'):
1526         opts.build_preference = 'ninja'
1527       else:
1528         opts.build_preference = 'make'
1529
1530     if opts.build_preference == 'ninja':
1531       SetNinjaBuildSystemDefault()
1532     elif opts.build_preference == 'make':
1533       SetMakeBuildSystemDefault()
1534     elif opts.build_preference != 'make':
1535       assert False, 'Error: %s build not supported' % opts.build_preference
1536
1537   bisect_utils.RunGClient(['runhooks'])
1538
1539   return True
1540
1541
1542 def RmTreeAndMkDir(path_to_dir):
1543   """Removes the directory tree specified, and then creates an empty
1544   directory in the same location.
1545
1546   Args:
1547     path_to_dir: Path to the directory tree.
1548
1549   Returns:
1550     True if successful, False if an error occurred.
1551   """
1552   try:
1553     if os.path.exists(path_to_dir):
1554       shutil.rmtree(path_to_dir)
1555   except OSError, e:
1556     if e.errno != errno.ENOENT:
1557       return False
1558
1559   try:
1560     os.makedirs(path_to_dir)
1561   except OSError, e:
1562     if e.errno != errno.EEXIST:
1563       return False
1564
1565   return True
1566
1567
1568 def RemoveBuildFiles():
1569   """Removes build files from previous runs."""
1570   if RmTreeAndMkDir(os.path.join('out', 'Release')):
1571     if RmTreeAndMkDir(os.path.join('build', 'Release')):
1572       return True
1573   return False
1574
1575
1576 def main():
1577
1578   usage = ('%prog [options] [-- chromium-options]\n'
1579            'Perform binary search on revision history to find a minimal '
1580            'range of revisions where a peformance metric regressed.\n')
1581
1582   parser = optparse.OptionParser(usage=usage)
1583
1584   parser.add_option('-c', '--command',
1585                     type='str',
1586                     help='A command to execute your performance test at' +
1587                     ' each point in the bisection.')
1588   parser.add_option('-b', '--bad_revision',
1589                     type='str',
1590                     help='A bad revision to start bisection. ' +
1591                     'Must be later than good revision. May be either a git' +
1592                     ' or svn revision.')
1593   parser.add_option('-g', '--good_revision',
1594                     type='str',
1595                     help='A revision to start bisection where performance' +
1596                     ' test is known to pass. Must be earlier than the ' +
1597                     'bad revision. May be either a git or svn revision.')
1598   parser.add_option('-m', '--metric',
1599                     type='str',
1600                     help='The desired metric to bisect on. For example ' +
1601                     '"vm_rss_final_b/vm_rss_f_b"')
1602   parser.add_option('-w', '--working_directory',
1603                     type='str',
1604                     help='Path to the working directory where the script will '
1605                     'do an initial checkout of the chromium depot. The '
1606                     'files will be placed in a subdirectory "bisect" under '
1607                     'working_directory and that will be used to perform the '
1608                     'bisection. This parameter is optional, if it is not '
1609                     'supplied, the script will work from the current depot.')
1610   parser.add_option('-r', '--repeat_test_count',
1611                     type='int',
1612                     default=20,
1613                     help='The number of times to repeat the performance test. '
1614                     'Values will be clamped to range [1, 100]. '
1615                     'Default value is 20.')
1616   parser.add_option('--repeat_test_max_time',
1617                     type='int',
1618                     default=20,
1619                     help='The maximum time (in minutes) to take running the '
1620                     'performance tests. The script will run the performance '
1621                     'tests according to --repeat_test_count, so long as it '
1622                     'doesn\'t exceed --repeat_test_max_time. Values will be '
1623                     'clamped to range [1, 60].'
1624                     'Default value is 20.')
1625   parser.add_option('-t', '--truncate_percent',
1626                     type='int',
1627                     default=25,
1628                     help='The highest/lowest % are discarded to form a '
1629                     'truncated mean. Values will be clamped to range [0, 25]. '
1630                     'Default value is 25 (highest/lowest 25% will be '
1631                     'discarded).')
1632   parser.add_option('--build_preference',
1633                     type='choice',
1634                     choices=['msvs', 'ninja', 'make'],
1635                     help='The preferred build system to use. On linux/mac '
1636                     'the options are make/ninja. On Windows, the options '
1637                     'are msvs/ninja.')
1638   parser.add_option('--use_goma',
1639                     action="store_true",
1640                     help='Add a bunch of extra threads for goma.')
1641   parser.add_option('--output_buildbot_annotations',
1642                     action="store_true",
1643                     help='Add extra annotation output for buildbot.')
1644   parser.add_option('--debug_ignore_build',
1645                     action="store_true",
1646                     help='DEBUG: Don\'t perform builds.')
1647   parser.add_option('--debug_ignore_sync',
1648                     action="store_true",
1649                     help='DEBUG: Don\'t perform syncs.')
1650   parser.add_option('--debug_ignore_perf_test',
1651                     action="store_true",
1652                     help='DEBUG: Don\'t perform performance tests.')
1653   (opts, args) = parser.parse_args()
1654
1655   if not opts.command:
1656     print 'Error: missing required parameter: --command'
1657     print
1658     parser.print_help()
1659     return 1
1660
1661   if not opts.good_revision:
1662     print 'Error: missing required parameter: --good_revision'
1663     print
1664     parser.print_help()
1665     return 1
1666
1667   if not opts.bad_revision:
1668     print 'Error: missing required parameter: --bad_revision'
1669     print
1670     parser.print_help()
1671     return 1
1672
1673   if not opts.metric:
1674     print 'Error: missing required parameter: --metric'
1675     print
1676     parser.print_help()
1677     return 1
1678
1679   opts.repeat_test_count = min(max(opts.repeat_test_count, 1), 100)
1680   opts.repeat_test_max_time = min(max(opts.repeat_test_max_time, 1), 60)
1681   opts.truncate_percent = min(max(opts.truncate_percent, 0), 25)
1682   opts.truncate_percent = opts.truncate_percent / 100.0
1683
1684   metric_values = opts.metric.split('/')
1685   if len(metric_values) != 2:
1686     print "Invalid metric specified: [%s]" % (opts.metric,)
1687     print
1688     return 1
1689
1690   if opts.working_directory:
1691     if bisect_utils.CreateBisectDirectoryAndSetupDepot(opts):
1692       return 1
1693
1694     os.chdir(os.path.join(os.getcwd(), 'src'))
1695
1696     if not RemoveBuildFiles():
1697       print "Something went wrong removing the build files."
1698       print
1699       return 1
1700
1701   if not CheckPlatformSupported(opts):
1702     return 1
1703
1704   # Check what source control method they're using. Only support git workflow
1705   # at the moment.
1706   source_control = DetermineAndCreateSourceControl()
1707
1708   if not source_control:
1709     print "Sorry, only the git workflow is supported at the moment."
1710     print
1711     return 1
1712
1713   # gClient sync seems to fail if you're not in master branch.
1714   if not source_control.IsInProperBranch() and not opts.debug_ignore_sync:
1715     print "You must switch to master branch to run bisection."
1716     print
1717     return 1
1718
1719   bisect_test = BisectPerformanceMetrics(source_control, opts)
1720   try:
1721     bisect_results = bisect_test.Run(opts.command,
1722                                      opts.bad_revision,
1723                                      opts.good_revision,
1724                                      metric_values)
1725     if not(bisect_results['error']):
1726       bisect_test.FormatAndPrintResults(bisect_results)
1727   finally:
1728     bisect_test.PerformCleanup()
1729
1730   if not(bisect_results['error']):
1731     return 0
1732   else:
1733     print 'Error: ' + bisect_results['error']
1734     print
1735     return 1
1736
1737 if __name__ == '__main__':
1738   sys.exit(main())