First pass on tool to bisect across range of revisions to help narrow down where a regression in a …

tools/bisect-perf-regression.py

Index: tools/bisect-perf-regression.py
diff --git a/tools/bisect-perf-regression.py b/tools/bisect-perf-regression.py
new file mode 100755
index 0000000000000000000000000000000000000000..8f126df091df9b1eebd311614fc9a98d74be5068
--- /dev/null
+++ b/tools/bisect-perf-regression.py
@@ -0,0 +1,860 @@
+#!/usr/bin/env python
+# Copyright (c) 2013 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+"""Performance Test Bisect Tool
+
+This script bisects a series of changelists using binary search. It starts at
+a bad revision where a performance metric has regressed, and asks for a last
+known-good revision. It will then binary search across this revision range by
+syncing, building, and running a performance test. If the change is
+suspected to occur as a result of WebKit/Skia/V8 changes, the script will
+further bisect changes to those depots and attempt to narrow down the revision
+range.

[tonyg, 2013/01/29 18:49:33]

An example usage like you have in the CL description would be great here.

[shatch, 2013/01/30 03:23:02]

Done.

+"""
+
+DEPOT_WEBKIT = 'webkit'
+DEPOT_SKIA = 'skia'
+DEPOT_V8 = 'v8'
+DEPOT_NAMES = [DEPOT_WEBKIT, DEPOT_SKIA, DEPOT_V8]

[tonyg, 2013/01/29 18:49:33]

I'd recommend killing this variable and just inlining DEPOT_DEPS_NAME.keys()

[shatch, 2013/01/30 03:23:02]

Done.

+DEPOT_DEPS_NAME = { DEPOT_WEBKIT : "src/third_party/WebKit",
+                    DEPOT_SKIA : 'src/third_party/skia/src',
+                    DEPOT_V8 : 'src/v8' }
+
+DEPOT_PATHS_FROM_SRC = { DEPOT_WEBKIT : '/third_party/WebKit',

[shatch, 2013/01/29 02:22:09]

Are these the right depots?

[tonyg, 2013/01/29 18:49:33]

yep

[tony, 2013/01/29 20:10:36]

Skia uses third_party/skia/{src,include,gyp}. Don't we need to sync all of these
together?

[shatch, 2013/01/30 03:23:02]

Are these all the same depot? They seem to be 3 different .git files. I'm a bit
unclear as to how to sync them together.

[tony, 2013/01/30 18:13:29]

They're all from the same skia svn repo.  I'm not sure what the correct way to
sync the git repos are.  Maybe szager knows how the git hashes are produced from
the svn revision.

[shatch, 2013/01/30 19:50:29]

Will follow up with him.

On 2013/01/30 18:13:29, tony wrote:

[szager1, 2013/01/31 01:51:27]

I think you need to treat skia/include, skia/gyp, and skia/src separately.  In
both DEPS and .DEPS.git, they are treated as three separate checkouts, even
though they all come from the same svn repo.

+                         DEPOT_SKIA : '/third_party/skia/src',
+                         DEPOT_V8 : '/v8' }
+
+FILE_DEPS_GIT = '.DEPS.git'
+
+SUPPORTED_OS_TYPES = ['posix']
+
+ERROR_MESSAGE_OS_NOT_SUPPORTED = "Sorry, this platform isn't supported yet."

[tonyg, 2013/01/29 18:49:33]

I have a weak preference to just inline all these messages. I think it would
make the code a little bit easier to follow. Especially for the ones with
formatting strings in them.

[shatch, 2013/01/30 03:23:02]

Done.

+
+ERROR_MESSAGE_SVN_UNSUPPORTED = "Sorry, only the git workflow is supported"\
+                                " at the moment."
+
+ERROR_MESSAGE_GCLIENT_NOT_FOUND = "An error occurred trying to read .gclient"\
+                                  " file. Check that you are running the tool"\
+                                  " from $chromium/src"
+
+ERROR_MESSAGE_IMPORT_GCLIENT = "An error occurred while importing .gclient"\
+                               " file."
+
+ERROR_MISSING_PARAMETER = 'Error: missing required parameter:'
+ERROR_MISSING_COMMAND = ERROR_MISSING_PARAMETER + ' --command'
+ERROR_MISSING_GOOD_REVISION = ERROR_MISSING_PARAMETER + ' --good_revision'
+ERROR_MISSING_BAD_REVISION = ERROR_MISSING_PARAMETER + ' --bad_revision'
+ERROR_MISSING_METRIC = ERROR_MISSING_PARAMETER + ' --metric'
+
+ERROR_RETRIEVE_REVISION_RANGE = 'An error occurred attempting to retrieve'\
+                                ' revision range: [%s..%s]'
+ERROR_RETRIEVE_REVISION = 'An error occurred attempting to retrieve revision:'\
+                          '[%s]'
+
+ERROR_PERF_TEST_NO_VALUES = 'No values returned from performance test.'
+ERROR_PERF_TEST_FAILED_RUN = 'Failed to run performance test.'
+
+ERROR_FAILED_DEPS_PARSE = 'Failed to parse DEPS file for WebKit revision.'
+ERROR_FAILED_BUILD = 'Failed to build revision: [%s]'
+ERROR_FAILED_GCLIENT_RUNHOOKS = 'Failed to run [gclient runhooks].'
+ERROR_FAILED_SYNC = 'Failed to sync revision: [%s]'
+ERROR_INCORRECT_BRANCH = "You must switch to master branch to run bisection."
+
+MESSAGE_REGRESSION_DEPOT_METRIC = 'Regression in metric:%s appears to be the'\
+                                   ' result of changes in [%s].'
+MESSAGE_BISECT_DEPOT = 'Revisions to bisect on [%s]:'
+MESSAGE_BISECT_SRC ='Revisions to bisect on chromium/src:'
+MESSAGE_GATHERING_REFERENCE = 'Gathering reference values for bisection.'
+MESSAGE_GATHERING_REVISIONS = 'Gathering revision range for bisection.'
+MESSAGE_WORK_ON_REVISION = 'Working on revision: [%s]'
+
+
+###############################################################################
+
+import re
+import os
+import imp
+import sys
+import shlex
+import optparse
+import subprocess

[tonyg, 2013/01/29 18:49:33]

Please put the imports above the constants

[shatch, 2013/01/30 03:23:02]

Done.

+
+
+
+GLOBAL_BISECT_OPTIONS = {'build' : False,

[tonyg, 2013/01/29 18:49:33]

This global is begging to be refactored as a class instead. Is there a clean way
to work that out?

[shatch, 2013/01/30 03:23:02]

Done.

+                         'sync' : False,
+                         'perf' : False,
+                         'goma' : False}
+
+def SetGlobalGomaFlag(flag):
+  """Sets global flag for using goma with builds."""
+  global GLOBAL_BISECT_OPTIONS
+
+  GLOBAL_BISECT_OPTIONS['goma'] = flag
+
+
+def IsGlobalGomaFlagEnabled():
+  global GLOBAL_BISECT_OPTIONS
+
+  return GLOBAL_BISECT_OPTIONS['goma']
+
+
+def SetDebugIgnoreFlags(build_flag, sync_flag, perf_flag):
+  """Sets global flags for ignoring builds, syncs, and perf tests."""
+  global GLOBAL_BISECT_OPTIONS
+
+  GLOBAL_BISECT_OPTIONS['build'] = build_flag
+  GLOBAL_BISECT_OPTIONS['sync'] = sync_flag
+  GLOBAL_BISECT_OPTIONS['perf'] = perf_flag
+
+
+def IsDebugIgnoreBuildEnabled():
+  """Returns whether build commands are being ignored."""
+  global GLOBAL_BISECT_OPTIONS
+
+  return GLOBAL_BISECT_OPTIONS['build']
+
+
+def IsDebugIgnoreSyncEnabled():
+  """Returns whether sync commands are being ignored."""
+  global GLOBAL_BISECT_OPTIONS
+
+  return GLOBAL_BISECT_OPTIONS['sync']
+
+
+def IsDebugIgnorePerfTestEnabled():
+  """Returns whether performance test commands are being ignored."""
+  global GLOBAL_BISECT_OPTIONS
+
+  return GLOBAL_BISECT_OPTIONS['perf']
+
+
+def IsStringFloat(string_to_check):
+  """Checks whether or not the given string can be converted to a floating

[tonyg, 2013/01/29 18:49:33]

Check out the style guide's section about function level comments:
http://google-styleguide.googlecode.com/svn/trunk/pyguide.html#Comments

[shatch, 2013/01/30 03:23:02]

Done.

+  point number."""
+  try:
+    float(string_to_check)
+
+    result = True
+  except ValueError:
+    result = False
+
+  return result

[tonyg, 2013/01/29 18:49:33]

Here and below, I'd eliminate the result variable and just inline the return
statements.

[shatch, 2013/01/30 03:23:02]

Done.

+
+
+def IsStringInt(string_to_check):
+  """Checks whether or not the given string can be converted to a integer."""
+  try:
+    int(string_to_check)
+
+    result = True
+  except ValueError:
+    result = False
+
+  return result
+
+
+def RunProcess(command):
+  """Run an arbitrary command, returning its output and return code."""
+  # On Windows, use shell=True to get PATH interpretation.
+  shell = (os.name == 'nt')

[tonyg, 2013/01/29 18:49:33]

I've always seen sys.platform == 'win32'. Is this equivalent?

[shatch, 2013/01/30 03:23:02]

Honestly I just grabbed this function from another py file, there were variants
of it in a few different places.

[tonyg, 2013/01/30 18:26:28]

It is fine to leave as-is then. This script will probably need some work the
first time it is used on windows anyway.

+  proc = subprocess.Popen(command,
+                          shell=shell,
+                          stdout=subprocess.PIPE,
+                          stderr=subprocess.PIPE)
+  out = proc.communicate()[0]
+
+  return (out, proc.returncode)
+
+
+class SourceControl(object):

[shatch, 2013/01/29 02:22:09]

Will we ever extend this to the svn workflow? If not, I probably didn't need to
do this.

[tonyg, 2013/01/29 18:49:33]

Probably not, but it is fine to have this abstraction.

+  """SourceControl is an abstraction over the underlying source control
+  system used for chromium. For now only git is supported, but in the
+  future, the svn workflow could be added as well."""
+  def __init__(self):
+    super(SourceControl, self).__init__()
+
+  def SyncToRevisionWithGClient(self, revision):
+    """Uses gclient to sync to the specified revision."""
+    args = ['gclient', 'sync', '--revision', revision]
+
+    return RunProcess(args)
+
+
+class GitSourceControl(SourceControl):
+  """GitSourceControl is used to query the underlying source control. """
+  def __init__(self):
+    super(GitSourceControl, self).__init__()
+
+  def RunGit(self, command):
+    """Run a git subcommand, returning its output and return code."""
+    command = ['git'] + command
+
+    return RunProcess(command)
+
+  def GetRevisionList(self, revision_range_end, revision_range_start):
+    """Retrieves a list of revisions between the bad revision and last known
+    good revision."""

[tonyg, 2013/01/29 18:49:33]

This comment assumes it is between the bad and good revision, but it is really
just between |revision_range_start| and |revision_range_end|

[shatch, 2013/01/30 03:23:02]

Done.

+    revision_range = '%s..%s' % (revision_range_start, revision_range_end)
+    (log_output, return_code) = self.RunGit(['log',

[tonyg, 2013/01/29 18:49:33]

Should we add an:
assert not return_code

Comment applies to other places where return_code is unused as well.

[shatch, 2013/01/30 03:23:02]

Done.

+                                             '--format=%H',
+                                             '-10000',
+                                             '--first-parent',
+                                             revision_range])
+
+    revision_hash_list = log_output.split()
+    revision_hash_list.append(revision_range_start)
+
+    return revision_hash_list
+
+  def SyncToRevision(self, revision, use_gclient=True):
+    """Syncs to the specified revision."""
+
+    if IsDebugIgnoreSyncEnabled():
+      return True
+
+    if use_gclient:
+      results = self.SyncToRevisionWithGClient(revision)
+    else:
+      results = self.RunGit(['checkout', revision])

[shatch, 2013/01/29 02:22:09]

At the moment, I update the third party libs (WebKit, Skia, V8) by going into
their directories and calling "git checkout <revision>", but I'm not clear if
this will cause any issues. Is there a way of doing this through gclient?

[tonyg, 2013/01/29 18:49:33]

No, that seems right.

+
+    return results[1] == 0
+
+  def ResolveToRevision(self, revision_to_check):

[tonyg, 2013/01/29 18:49:33]

Recommend naming this ResolveSvnToGitRevision()

[shatch, 2013/01/30 03:23:02]

Wasn't sure if I should refer to specific workflows since there is the
abstraction over top.

+    """If the user supplied an SVN revision, try to resolve it to a
+    git SHA1."""
+    if not(IsStringInt(revision_to_check)):

[tonyg, 2013/01/29 18:49:33]

if not IsStringInt(revision_to_check):

[shatch, 2013/01/30 03:23:02]

Done.

+      return revision_to_check
+
+    svn_pattern = 'SVN changes up to revision ' + revision_to_check
+
+    (log_output, return_code) = self.RunGit(['log',
+                                             '--format=%H',
+                                             '-1',
+                                             '--grep',
+                                             svn_pattern,
+                                             'origin/master'])
+
+    revision_hash_list = log_output.split()
+
+    if len(revision_hash_list):
+      return revision_hash_list[0]
+
+    return None
+
+  def IsInProperBranch(self):

[shatch, 2013/01/29 02:22:09]

I found that gclient sync --revision failed after repeated syncs if I wasn't in
the master branch.

[tonyg, 2013/01/29 18:49:33]

Why not name this IsInMasterBranch()

[shatch, 2013/01/30 03:23:02]

My thought was as part of the abstraction, I shouldn't refer to specific
workflows. If I were to add svn later, I wasn't sure if "master" branch was
relevant there.

+    """Confirms they're in the master branch for performing the bisection.
+    This is needed or gclient will fail to sync properly."""
+    (log_output, return_code) = self.RunGit(['rev-parse',
+                                             '--abbrev-ref',
+                                             'HEAD'])
+
+    log_output = log_output.strip()
+
+    return log_output == "master"
+
+
+
+class BisectPerformanceMetrics(object):
+  """BisectPerformanceMetrics performs a bisection against a list of range
+  of revisions to narrow down where performance regressions may have
+  occurred."""
+
+  def __init__(self, source_control):
+    super(BisectPerformanceMetrics, self).__init__()
+
+    self.source_control = source_control
+    self.src_cwd = os.getcwd()
+    self.depot_cwd = {}
+
+    for d in DEPOT_NAMES:
+      self.depot_cwd[d] = self.src_cwd + DEPOT_PATHS_FROM_SRC[d]

[tonyg, 2013/01/29 18:49:33]

You could eliminate the DEPOT_PATHS_FROM_SRC constant and just inline:
DEPOT_DEPS_NAME[d][3:]

[shatch, 2013/01/30 03:23:02]

Done.

+
+  def GetRevisionList(self, bad_revision, good_revision):
+    """Retrieves a list of all the commits between the bad revision and
+    last known good revision."""
+
+    revision_work_list = self.source_control.GetRevisionList(bad_revision,
+                                                             good_revision)
+
+    return revision_work_list
+
+  def Get3rdPartyRevisionsFromCurrentRevision(self):
+    """Parses the DEPS file to determine WebKit/skia/v8/etc... versions."""
+
+    cwd = os.getcwd()
+    os.chdir(self.src_cwd)
+
+    locals = {'Var': lambda _: locals["vars"][_],
+              'From': lambda *args: None}
+    execfile(FILE_DEPS_GIT, {}, locals)
+
+    os.chdir(cwd)
+
+    results = {}
+
+    rxp = ".git@(?P<revision>[a-zA-Z0-9]+)"
+    rxp = re.compile(rxp)

[tonyg, 2013/01/29 18:49:33]

Just inline the re.compile() call on the line above?

Also, would be nice to have a descriptive variable name.

[shatch, 2013/01/30 03:23:02]

Done.

+
+    for d in DEPOT_NAMES:
+      if locals['deps'].has_key(DEPOT_DEPS_NAME[d]):
+        re_results = rxp.search(locals['deps'][DEPOT_DEPS_NAME[d]])
+
+        if re_results:
+          results[d] = re_results.group('revision')
+        else:
+          return None
+      else:
+        return None
+
+    return results
+
+  def BuildCurrentRevision(self):
+    """Builds chrome and the performance_uit_tests suite on the current

[tonyg, 2013/01/29 18:49:33]

s/uit/ui/

[shatch, 2013/01/30 03:23:02]

Done.

+    revision."""
+
+    if IsDebugIgnoreBuildEnabled():
+      return True
+
+    gyp_var = os.getenv('GYP_GENERATORS')
+
+    num_threads = 16
+
+    if IsGlobalGomaFlagEnabled():
+      num_threads = 200
+
+    if gyp_var != None and 'ninja' in gyp_var:

[shatch, 2013/01/29 02:22:09]

Wasn't sure if I needed to do a check for this, but my build failed initially
since I had ninja set up on my laptop.

[tonyg, 2013/01/29 18:49:33]

looks good

+      args = ['ninja',
+              '-C',
+              'out/Release',
+              '-j%d' % num_threads,
+              'chrome',
+              'performance_ui_tests']
+    else:
+      args = ['make',
+              'BUILDTYPE=Release',

[tonyg, 2013/01/29 18:49:33]

Doesn't this have to go before the make command?  Did you test the non-ninja
path?

[shatch, 2013/01/30 03:23:02]

It seemed legit, got it from the linux build instructions page:
https://code.google.com/p/chromium/wiki/LinuxBuildInstructions#Release_mode

Used the ninja path on my laptop and make on my desktop.

[tonyg, 2013/01/30 18:26:28]

OK, sorry I was unfamiliar with that syntax

+              '-j%d' % num_threads,
+              'chrome',
+              'performance_ui_tests']
+
+    cwd = os.getcwd()
+    os.chdir(self.src_cwd)
+
+    (output, return_code) = RunProcess(args)
+
+    os.chdir(cwd)
+
+    #print('build exited with: %d' % (return_code))

[tonyg, 2013/01/29 18:49:33]

Remove this, or perhaps better yet import logging and make this a
logging.debug() line.

[shatch, 2013/01/30 03:23:02]

Done.

+    return return_code == 0
+
+  def RunGClientHooks(self):
+    """Runs gclient with runhooks command."""
+
+    if IsDebugIgnoreBuildEnabled():
+      return True
+
+    results = RunProcess(['gclient', 'runhooks'])
+
+    return results[1] == 0

[tonyg, 2013/01/29 18:49:33]

return not results[1]

http://google-styleguide.googlecode.com/svn/trunk/pyguide.html#True/False_eva...

[shatch, 2013/01/30 03:23:02]

Done.

+
+  def ParseMetricValuesFromOutput(self, metric, text):
+    """Parses output from performance_ui_tests and retrieves the results for
+    a given metric."""
+    # Format is: RESULT <graph>: <trace>= <value> <units>
+    metric_formatted = 'RESULT %s: %s=' % (metric[0], metric[1])
+
+    text_lines = text.split('\n')
+    values_list = []
+
+    for current_line in text_lines:
+      # Parse the output from the performance test for the metric we're
+      # interested in.
+      metric_re = metric_formatted +\
+                  "(\s)*(?P<values>[0-9]+(\.[0-9]*)?)"
+      metric_re = re.compile(metric_re)
+      regex_results = metric_re.search(current_line)
+
+      if not regex_results is None:
+        values_list += [regex_results.group('values')]
+      else:
+        metric_re = metric_formatted +\
+                    "(\s)*\[(\s)*(?P<values>[0-9,.]+)\]"

[tonyg, 2013/01/29 18:49:33]

These aren't always a list of values in []. Sometimes it is just a bare number.
See GraphingLogProcessor here:
https://code.google.com/searchframe#OAMlx_jo-ck/tools/build/scripts/slave/pro...

[shatch, 2013/01/30 03:23:02]

Won't the first search cover that case?

[tonyg, 2013/01/30 18:26:28]

Oh, I follow now. Thanks.

+        metric_re = re.compile(metric_re)
+        regex_results = metric_re.search(current_line)
+
+        if not regex_results is None:
+          metric_values = regex_results.group('values')
+
+          values_list += metric_values.split(',')
+
+    return [float(v) for v in values_list if IsStringFloat(v)]
+
+  def RunPerformanceTestAndParseResults(self, command_to_run, metric):
+    """Runs a performance test on the current revision and parses
+    the results."""
+
+    if IsDebugIgnorePerfTestEnabled():
+      return (0.0, 0)
+
+    args = shlex.split(command_to_run)
+
+    cwd = os.getcwd()
+    os.chdir(self.src_cwd)
+
+    (output, return_code) = RunProcess(args)
+
+    os.chdir(cwd)
+
+    metric_values = self.ParseMetricValuesFromOutput(metric, output)
+
+    # Need to get the average value if there were multiple values.
+    if len(metric_values) > 0:

[tonyg, 2013/01/29 18:49:33]

if metric_values:

[shatch, 2013/01/30 03:23:02]

Done.

+      average_metric_value = reduce(lambda x, y: float(x) + float(y),
+                                    metric_values) / len(metric_values)
+
+      return (average_metric_value, 0)
+    else:
+      return (ERROR_PERF_TEST_NO_VALUES, -1)
+
+  def SyncBuildAndRunRevision(self, revision, depot, command_to_run, metric):
+    """Performs a full sync/build/run of the specified revision."""
+    use_gclient = (depot == 'chromium')
+
+    if self.source_control.SyncToRevision(revision, use_gclient):
+      success = True
+      if not(use_gclient):
+        success = self.RunGClientHooks()
+
+      if success:
+        if self.BuildCurrentRevision():
+          results = self.RunPerformanceTestAndParseResults(command_to_run,
+                                                           metric)
+
+          if results[1] == 0 and use_gclient:
+            external_revisions = self.Get3rdPartyRevisionsFromCurrentRevision()
+
+            if external_revisions:
+              return (results[0], results[1], external_revisions)
+            else:
+              return (ERROR_FAILED_DEPS_PARSE, 1)
+          else:
+            return results
+        else:
+          return (ERROR_FAILED_BUILD % (str(revision, )), 1)
+      else:
+        return (ERROR_FAILED_GCLIENT_RUNHOOKS, 1)
+    else:
+      return (ERROR_FAILED_SYNC % (str(revision, )), 1)
+
+  def CheckIfRunPassed(self, current_value, known_good_value, known_bad_value):
+    """Given known good and bad values, decide if the current_value passed
+    or failed."""
+    dist_to_good_value = abs(current_value - known_good_value)
+    dist_to_bad_value = abs(current_value - known_bad_value)
+
+    return dist_to_good_value < dist_to_bad_value
+
+  def Run(self, command_to_run, bad_revision_in, good_revision_in, metric):

[tonyg, 2013/01/29 18:49:33]

This method is a bit unruly, is there a ways to factor out some helpers? Perhaps
the comments are a good indicator of logical parts to break out.

+    """Given known good and bad revisions, run a binary search on all
+    intermediate revisions to determine the CL where the performance regression
+    occurred.
+
+    @param command_to_run Specify the command to execute the performance test.

[tonyg, 2013/01/29 18:49:33]

See http://google-styleguide.googlecode.com/svn/trunk/pyguide.html#Comments

[shatch, 2013/01/30 03:23:02]

Done.

+    @param good_revision Number/tag of the known good revision.
+    @param bad_revision Number/tag of the known bad revision.
+    @param metric The performance metric to monitor.
+    """
+
+    results = {'revision_data' : {},
+               'error' : None}
+
+    # If they passed SVN CL's, etc... we can try match them to git SHA1's.
+    bad_revision = self.source_control.ResolveToRevision(bad_revision_in)
+    good_revision = self.source_control.ResolveToRevision(good_revision_in)
+
+    if bad_revision is None:
+      results['error'] = 'Could\'t resolve [%s] to SHA1.'%(bad_revision_in,)

[tonyg, 2013/01/29 18:49:33]

Space around % here and below.

[shatch, 2013/01/30 03:23:02]

Done.

+      return results
+
+    if good_revision is None:
+      results['error'] = 'Could\'t resolve [%s] to SHA1.'%(good_revision_in,)
+      return results
+
+    print MESSAGE_GATHERING_REVISIONS
+
+    # Retrieve a list of revisions to do bisection on.
+    src_revision_list = self.GetRevisionList(bad_revision, good_revision)
+
+    if src_revision_list:
+      # revision_data will store information about a revision such as the
+      # depot it came from, the webkit/skia/V8 revision at that time,
+      # performance timing, build state, etc...
+      revision_data = results['revision_data']
+
+      # revision_list is the list we're binary searching through at the moment.
+      revision_list = []
+
+      sort_key_ids = 0
+
+      for current_revision_id in src_revision_list:
+        sort_key_ids += 1
+
+        revision_data[current_revision_id] = {'value' : None,
+                                              'passed' : '?',
+                                              'depot' : 'chromium',
+                                              'external' : None,
+                                              'sort' : sort_key_ids}
+        revision_list.append(current_revision_id)
+
+      min_revision = 0
+      max_revision = len(revision_list) - 1
+
+      print
+      print MESSAGE_BISECT_SRC
+      for revision_id in revision_list:
+        print('  -> %s' % (revision_id, ))
+      print
+
+      print MESSAGE_GATHERING_REFERENCE
+
+      # Perform the performance tests on the good and bad revisions, to get
+      # reference values.
+      # todo: tidy this up
+      bad_revision_run_results = self.SyncBuildAndRunRevision(bad_revision,
+                                                              'chromium',
+                                                              command_to_run,
+                                                              metric)
+
+      if bad_revision_run_results[1] != 0:

[tonyg, 2013/01/29 18:49:33]

if bad_revision_run_results[1]:
 here and below.

[shatch, 2013/01/30 03:23:02]

Done.

+        results['error'] = bad_revision_run_results[0]
+        return results
+
+      good_revision_run_results = self.SyncBuildAndRunRevision(good_revision,
+                                                              'chromium',
+                                                              command_to_run,

[tonyg, 2013/01/29 18:49:33]

indentation

[shatch, 2013/01/30 03:23:02]

Done.

+                                                              metric)
+
+      if good_revision_run_results[1] != 0:
+        results['error'] = good_revision_run_results[0]
+        return results
+
+      # We need these reference values to determine if later runs should be
+      # classified as pass or fail.
+      known_bad_value = bad_revision_run_results[0]
+      known_good_value = good_revision_run_results[0]
+
+      # Can just mark the good and bad revisions explicitly here since we
+      # already know the results.
+      bad_revision_data = revision_data[revision_list[0]]
+      bad_revision_data['external'] = bad_revision_run_results[2]
+      bad_revision_data['passed'] = 0
+      bad_revision_data['value'] = known_bad_value
+
+      good_revision_data = revision_data[revision_list[max_revision]]
+      good_revision_data['external'] = good_revision_run_results[2]
+      good_revision_data['passed'] = 1
+      good_revision_data['value'] = known_good_value
+
+      while True:
+        min_revision_data = revision_data[revision_list[min_revision]]
+        max_revision_data = revision_data[revision_list[max_revision]]
+
+        if max_revision - min_revision <= 1:
+          if min_revision_data['passed'] == '?':
+            next_revision_index = min_revision
+          elif max_revision_data['passed'] == '?':
+            next_revision_index = max_revision
+          elif min_revision_data['depot'] == 'chromium':
+            # If there were changes to any of the external libraries we track,
+            # should bisect the changes there as well..
+            external_changed = False
+
+            for current_depot in DEPOT_NAMES:
+              if min_revision_data['external'][current_depot] !=\
+                 max_revision_data['external'][current_depot]:
+                # Change into working directory of external library to run
+                # subsequent commands.
+                old_cwd = os.getcwd()
+
+                os.chdir(self.depot_cwd[current_depot])
+                depot_rev_range = [min_revision_data['external'][current_depot],
+                                   max_revision_data['external'][current_depot]]
+                depot_revision_list = self.GetRevisionList(depot_rev_range[1],
+                                                           depot_rev_range[0])
+                os.chdir(old_cwd)
+
+                if depot_revision_list == None:
+                  results['error'] = ERROR_RETRIEVE_REVISION_RANGE %\
+                                     (depot_rev_range[1],
+                                      depot_rev_range[0])
+                  return results
+
+                # Add the new revisions
+                num_depot_revisions = len(depot_revision_list)
+                old_sort_key = min_revision_data['sort']
+                sort_key_ids += num_depot_revisions
+
+                for k, v in revision_data.iteritems():
+                  if v['sort'] > old_sort_key:
+                    v['sort'] += num_depot_revisions
+
+                for i in xrange(num_depot_revisions):
+                  r = depot_revision_list[i]
+
+                  revision_data[r] = {'revision' : r,
+                                      'depot' : current_depot,
+                                      'value' : None,
+                                      'passed' : '?',
+                                      'sort' : i + old_sort_key + 1}
+
+                revision_list = depot_revision_list
+
+                print MESSAGE_REGRESSION_DEPOT_METRIC % (metric, current_depot)
+                print
+                print MESSAGE_BISECT_DEPOT % (current_depot, )
+                for r in revision_list:
+                  print '  -> %s' % (r, )
+                print
+
+                # Reset the bisection and perform it on the webkit changelists.
+                min_revision = 0
+                max_revision = len(revision_list) - 1
+
+                # One of the external libraries changed, so we'll loop around
+                # and binary search through the new changelists.
+                external_changed = True
+
+                break
+
+            if external_changed:
+              continue
+            else:
+              break
+          else:
+            break

[tonyg, 2013/01/29 18:49:33]

This part is really hard to read. I'm hoping factoring out some helper methods
will help, but if not, maybe some brief comments here would.

+        else:
+          next_revision_index = int((max_revision - min_revision) / 2) +\
+                                min_revision
+
+        next_revision_id = revision_list[next_revision_index]
+        next_revision_data = revision_data[next_revision_id]
+        next_revision_depot = next_revision_data['depot']
+
+
+        # Change current working directory depending on what we're building.
+        if next_revision_depot == 'chromium':
+          os.chdir(self.src_cwd)
+        elif next_revision_depot in DEPOT_NAMES:
+          os.chdir(self.depot_cwd[next_revision_depot])
+        else:
+          assert False

[tonyg, 2013/01/29 18:49:33]

assert False, 'some description'

[shatch, 2013/01/30 03:23:02]

Done.

+
+        print MESSAGE_WORK_ON_REVISION % next_revision_id
+
+        run_results = self.SyncBuildAndRunRevision(next_revision_id,
+                                                   next_revision_depot,
+                                                   command_to_run,
+                                                   metric)
+
+        # If the build is successful, check whether or not the metric
+        # had regressed.
+        if run_results[1] == 0:
+          if next_revision_depot == 'chromium':
+            next_revision_data['external'] = run_results[2]
+
+          passed_regression = self.CheckIfRunPassed(run_results[0],
+                                                    known_good_value,
+                                                    known_bad_value)
+
+          next_revision_data['passed'] = passed_regression
+          next_revision_data['value'] = run_results[0]
+
+          if passed_regression:
+            max_revision = next_revision_index
+          else:
+            min_revision = next_revision_index
+        else:
+          next_revision_data['passed'] = 'F'
+
+          # If the build is broken, remove it and redo search.
+          revision_list.pop(next_revision_index)
+
+          max_revision -= 1
+    else:
+      # Weren't able to sync and retrieve the revision range.
+      results['error'] = ERROR_RETRIEVE_REVISION_RANGE % (good_revision,
+                                                          bad_revision)
+
+    return results
+
+
+def ParseGClientForSourceControl():
+  """Parses the .gclient file to determine source control method."""
+  try:
+    deps_file = imp.load_source('gclient', '../.gclient')

[shatch, 2013/01/29 02:22:09]

Is this an accurate way of checking their source control?

[tonyg, 2013/01/29 18:49:33]

Not sure. Maybe check the message returned by "svn status" or "git status"?

[shatch, 2013/01/30 03:23:02]

Done.

+
+    if deps_file.solutions[0].has_key('deps_file'):
+      if deps_file.solutions[0]['deps_file'] == '.DEPS.git':
+        source_control = GitSourceControl()
+
+        return (source_control, None)
+      else:
+        return (None, ERROR_MESSAGE_SVN_UNSUPPORTED)
+    else:
+      return (None, ERROR_MESSAGE_SVN_UNSUPPORTED)
+  except ImportError:
+    return (None, ERROR_MESSAGE_IMPORT_GCLIENT)
+  except IOError:
+    return (None, ERROR_MESSAGE_GCLIENT_NOT_FOUND)
+
+
+def main():
+
+  usage = ('%prog [options] [-- chromium-options]\n'
+           'Perform binary search on revision history to find a minimal '
+           'range of revisions where a peformance metric regressed.\n')
+
+  parser = optparse.OptionParser(usage=usage)
+
+  parser.add_option('-c', '--command',
+                    type = 'str',

[tonyg, 2013/01/29 18:49:33]

Google python style is to omit spaces around the "=" when passing args by
keyword. See:
http://google-styleguide.googlecode.com/svn/trunk/pyguide.html?showone=Whites...

[shatch, 2013/01/30 03:23:02]

Done.

+                    help = 'A command to execute your performance test at' +
+                    ' each point in the bisection.')
+  parser.add_option('-b', '--bad_revision',
+                    type = 'str',
+                    help = 'A bad revision to start bisection. ' +
+                    'Must be later than good revision. ')
+  parser.add_option('-g', '--good_revision',
+                    type = 'str',
+                    help = 'A revision to start bisection where performance' +
+                    ' test is known to pass. Must be earlier than the ' +
+                    'bad revision.')
+  parser.add_option('-m', '--metric',
+                    type = 'str',
+                    help = 'The desired metric to bisect on.')
+  parser.add_option('--use_goma',
+                    action = "store_true",
+                    help = 'Add a bunch of extra threads for goma.')
+  parser.add_option('--debug_ignore_build',
+                    action = "store_true",
+                    help = 'DEBUG: Don\'t perform builds.')
+  parser.add_option('--debug_ignore_sync',
+                    action = "store_true",
+                    help = 'DEBUG: Don\'t perform syncs.')
+  parser.add_option('--debug_ignore_perf_test',
+                    action = "store_true",
+                    help = 'DEBUG: Don\'t perform performance tests.')
+  (opts, args) = parser.parse_args()
+
+  if opts.command is None:

[tonyg, 2013/01/29 18:49:33]

if not opts.command:

[shatch, 2013/01/30 03:23:02]

Done.

+    print ERROR_MISSING_COMMAND
+    print
+    parser.print_help()
+    return 1
+
+  if opts.good_revision is None:
+    print ERROR_MISSING_GOOD_REVISION
+    print
+    parser.print_help()
+    return 1
+
+  if opts.bad_revision is None:
+    print ERROR_MISSING_BAD_REVISION
+    print
+    parser.print_help()
+    return 1
+
+  if opts.metric is None:
+    print ERROR_MISSING_METRIC
+    print
+    parser.print_help()
+    return 1
+
+  # Haven't tested the script out on any other platforms yet.
+  if not os.name in SUPPORTED_OS_TYPES:
+    print ERROR_MESSAGE_OS_NOT_SUPPORTED
+    print
+    return 1
+
+
+  SetDebugIgnoreFlags(opts.debug_ignore_build,
+                      opts.debug_ignore_sync,
+                      opts.debug_ignore_perf_test)
+
+  SetGlobalGomaFlag(opts.use_goma)
+
+  # Check what source control method they're using. Only support git workflow
+  # at the moment.
+  (source_control, error_message) = ParseGClientForSourceControl()
+
+  if source_control == None:
+    print error_message
+    print
+    return 1
+
+  # gClient sync seems to fail if you're not in master branch.
+  if not(source_control.IsInProperBranch()):

[tonyg, 2013/01/29 18:49:33]

if not source_control.IsInProperBranch():

[shatch, 2013/01/30 03:23:02]

Done.

+    print ERROR_INCORRECT_BRANCH
+    print
+    return 1
+
+  metric_values = opts.metric.split('/')
+  if len(metric_values) < 2:
+    metric_values.append('')
+
+  bisect_test = BisectPerformanceMetrics(source_control)
+  bisect_results = bisect_test.Run(opts.command,
+                                   opts.bad_revision,
+                                   opts.good_revision,
+                                   metric_values)
+
+  if not(bisect_results['error']):
+    revision_data = bisect_results['revision_data']
+    revision_data_sorted = sorted(revision_data.iteritems(),
+                                  key = lambda x: x[1]['sort'])
+
+    print
+    print 'Full results of bisection:'
+    for k, v in revision_data_sorted:
+      b = v['passed']
+      f = v['value']

[tonyg, 2013/01/29 18:49:33]

Recommend some more descriptive variable names here.

[shatch, 2013/01/30 03:23:02]

Done.

+
+      if type(b) is bool:
+        b = int(b)
+
+      if f is None:
+        f = ''
+
+      print('  %8s  %s  %s %6s' % (v['depot'], k, b, f))
+    print
+
+    # Find range where it possibly broke.
+    first_working_revision = None
+    last_broken_revision = None
+
+    for k, v in revision_data_sorted:
+      if v['passed'] == True:
+        if first_working_revision is None:
+          first_working_revision = k
+
+      if v['passed'] == False:
+        last_broken_revision = k
+
+    if last_broken_revision != None and first_working_revision != None:
+      print 'Results: Regression was detected as a result of changes on:'
+      print '  -> First Bad Revision: [%s] [%s]' %\
+            (last_broken_revision,
+            revision_data[last_broken_revision]['depot'])
+      print '  -> Last Good Revision: [%s] [%s]' %\
+            (first_working_revision,
+            revision_data[first_working_revision]['depot'])
+    return 0
+  else:
+    print 'Error: ' + bisect_results['error']
+    print
+    return 1
+
+if __name__ == '__main__':
+  sys.exit(main())