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