Write a tool to bisect WebKit builds
authorlforschler@apple.com <lforschler@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 10 Aug 2017 18:22:01 +0000 (18:22 +0000)
committerlforschler@apple.com <lforschler@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 10 Aug 2017 18:22:01 +0000 (18:22 +0000)
https://bugs.webkit.org/show_bug.cgi?id=174596

Reviewed by Dean Johnson and Kocsen Chung.

* Scripts/bisect-builds: Added.
(bisect_builds): main bisection algorithm
(download_archive):download an archive from S3 using existing tools
(extract_archive):extract an archive using existing tools
(find_le):Find rightmost value less than or equal to x
(find_ge):Find leftmost item greater than or equal to x
(get_api_url):generate url for the rest api/database
(get_indices_from_revisions):convert revisions to list indexes for bisection
(get_sorted_revisions):retrieve sorted revision list
(get_s3_location_for_revision):calculate the S3 archive storage location
(parse_args):parse command line arguments
(pick_next_build):compute the next build to bisect
(prompt_did_reproduce):prompt user for direction for bisection
(set_webkit_output_dir):set the folder for bisected builds to avoid overwriting engineering build output
(test_archive):Platform specific logic to test downloaded archive
(minified_platforms):return a list of minified platforms in the database
(unminified_platforms):return a list of full platforms in the database
(is_supported_platform):check if platform is supported
(validate_options):validate command line options
(main):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@220534 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Tools/ChangeLog
Tools/Scripts/bisect-builds [new file with mode: 0755]

index df0045315bc13423b6126a9964eeb82f304ac856..f362d4b2b86394fb0b65324ffa573eaf2d8a3302 100644 (file)
@@ -1,3 +1,31 @@
+2017-08-10  Lucas Forschler  <lforschler@apple.com>
+
+        Write a tool to bisect WebKit builds
+        https://bugs.webkit.org/show_bug.cgi?id=174596
+
+        Reviewed by Dean Johnson and Kocsen Chung.
+
+        * Scripts/bisect-builds: Added.
+        (bisect_builds): main bisection algorithm
+        (download_archive):download an archive from S3 using existing tools
+        (extract_archive):extract an archive using existing tools
+        (find_le):Find rightmost value less than or equal to x
+        (find_ge):Find leftmost item greater than or equal to x
+        (get_api_url):generate url for the rest api/database
+        (get_indices_from_revisions):convert revisions to list indexes for bisection
+        (get_sorted_revisions):retrieve sorted revision list
+        (get_s3_location_for_revision):calculate the S3 archive storage location
+        (parse_args):parse command line arguments
+        (pick_next_build):compute the next build to bisect
+        (prompt_did_reproduce):prompt user for direction for bisection
+        (set_webkit_output_dir):set the folder for bisected builds to avoid overwriting engineering build output
+        (test_archive):Platform specific logic to test downloaded archive
+        (minified_platforms):return a list of minified platforms in the database
+        (unminified_platforms):return a list of full platforms in the database
+        (is_supported_platform):check if platform is supported
+        (validate_options):validate command line options
+        (main):
+
 2017-08-10  Lucas Forschler  <lforschler@apple.com>
 
         Remove bisect-builds script.
diff --git a/Tools/Scripts/bisect-builds b/Tools/Scripts/bisect-builds
new file mode 100755 (executable)
index 0000000..373ef30
--- /dev/null
@@ -0,0 +1,726 @@
+#!/usr/bin/env python
+
+# Copyright (C) 2017 Apple Inc. All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+#
+# 1.  Redistributions of source code must retain the above copyright
+#     notice, this list of conditions and the following disclaimer. 
+# 2.  Redistributions in binary form must reproduce the above copyright
+#     notice, this list of conditions and the following disclaimer in the
+#     documentation and/or other materials provided with the distribution. 
+# 3.  Neither the name of Apple Inc. ("Apple") nor the names of
+#     its contributors may be used to endorse or promote products derived
+#     from this software without specific prior written permission. 
+#
+# THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+import argparse
+import bisect
+import math
+import os
+import requests
+import shutil
+import subprocess
+import sys
+import tempfile
+import urlparse
+
+REST_API_URL = 'https://q1tzqfy48e.execute-api.us-west-2.amazonaws.com/v1/'
+REST_API_ENDPOINT = 'archives/'
+REST_API_MINIFIED_ENDPOINT = 'minified-archives/'
+
+
+def bisect_builds(revision_list, start_index, end_index, options):
+    while True:
+        index_to_test = pick_next_build(revision_list, start_index, end_index)
+        if index_to_test == None:
+            print('No more builds to test...')
+            exit(1)
+        download_archive(options, revision_list[index_to_test])
+        extract_archive(options)
+        reproduces = test_archive(options, revision_list[index_to_test])
+
+        if reproduces:          # bisect left
+            index_to_test -= 1  # We can remove this from the end of the list of builds to test
+            bisect_builds(revision_list, start_index, index_to_test, options)
+        if not reproduces:      # bisect right
+            index_to_test += 1  # We can remove this from the start of the list of builds to test
+            bisect_builds(revision_list, index_to_test, end_index, options)
+
+
+def download_archive(options, revision):
+    api_url = get_api_url(options)
+    s3_url = get_s3_location_for_revision(api_url, revision)
+    print('Archive URL: {}'.format(s3_url))
+    command = ['python', '../BuildSlaveSupport/download-built-product', '--{}'.format(options.configuration), '--platform', options.platform, s3_url]
+    print('Downloading revision: {}'.format(revision))
+    subprocess.check_call(command)
+
+
+def extract_archive(options):
+    command = ['python', '../BuildSlaveSupport/built-product-archive', '--platform', options.platform, '--%s' % options.configuration, 'extract']
+    print('Extracting archive: {}'.format(command))
+    subprocess.check_call(command)
+
+
+# ---- bisect helpers from https://docs.python.org/2/library/bisect.html ----
+def find_le(a, x):
+    """Find rightmost value less than or equal to x"""
+    i = bisect.bisect_right(a, x)
+    if i:
+        return i - 1
+    raise ValueError
+
+
+def find_ge(a, x):
+    """Find leftmost item greater than or equal to x"""
+    i = bisect.bisect_left(a, x)
+    if i != len(a):
+        return i
+    raise ValueError
+# ---- end bisect helpers ----
+
+
+def get_api_url(options):
+    if options.full:
+        base_url = urlparse.urljoin(REST_API_URL, REST_API_ENDPOINT)
+    else:
+        base_url = urlparse.urljoin(REST_API_URL, REST_API_MINIFIED_ENDPOINT)
+
+    api_url = urlparse.urljoin(base_url, '-'.join([options.platform, options.architecture, options.configuration]))
+    return api_url
+
+
+def get_indices_from_revisions(revision_list, start_revision, end_revision):
+    if start_revision is None:
+        print('WARNING: No starting revision was given, defaulting to first available for this configuration')
+        start_index = 0
+    else:
+        start_index = find_ge(revision_list, start_revision)
+
+    if end_revision is None:
+        print('WARNING: No ending revision was given, defaulting to last avialable for this configuration')
+        end_index = len(revision_list) - 1
+    else:
+        end_index = find_le(revision_list, end_revision)
+
+    return start_index, end_index
+
+
+def get_sorted_revisions(revisions_dict):
+    revisions = [int(revision['revision']) for revision in revisions_dict['revisions']]
+    return sorted(revisions)
+    
+
+def get_s3_location_for_revision(url, revision):
+    url = '/'.join([url, str(revision)])
+    r = requests.get(url)
+    for archive in r.json()['archive']:
+        s3_url = archive['s3_url']
+    return s3_url
+
+
+def parse_args(args):
+    parser = argparse.ArgumentParser(description='Perform a bisection against existing WebKit archives.')
+    parser.add_argument('-c', '--configuration', default='release', help='The configuration to query [release | debug]')
+    parser.add_argument('-a', '--architecture', default='x86_64', help='The architecture to query [x86_64 | i386]')
+    parser.add_argument('-p', '--platform', default='None', required=True, help='The platform to query [mac-sierra | gtk | ios-simulator | win]')
+    parser.add_argument('-f', '--full', action='store_true', default=False, help='Use full archives containing debug symbols. These are significantly larger files!')
+    parser.add_argument('-s', '--start', default=None, type=int, help='The starting revision to bisect.')
+    parser.add_argument('-e', '--end', default=None, type=int, help='The ending revision to bisect')
+    return parser.parse_args(args)
+
+
+def pick_next_build(revision_list, start_index, end_index):
+    revisions_remaining = (end_index - start_index) + 1
+    print('Found {} revisions in this range to test...'.format(revisions_remaining))
+
+    if start_index >= end_index:
+        print('No archives available between {} and {}'.format(revision_list[end_index], revision_list[start_index]))
+        return None
+
+    middleIndex = (start_index + end_index) / 2
+    return int(math.ceil(middleIndex))
+
+
+def prompt_did_reproduce():
+    var = raw_input('\nDid the error reproduce? [y/n]: ')
+    var = var.lower()
+    if 'y' in var:
+        return True
+    if 'n' in var:
+        return False
+    else:
+        prompt_did_reproduce()
+    
+
+def set_webkit_output_dir(temp_dir):
+    print('Setting environment variable WEBKIT_OUTPUTDIR to {}'.format(temp_dir))
+    os.environ['WEBKIT_OUTPUTDIR'] = temp_dir
+
+
+def test_archive(options, revision):
+    print('Testing revision {}...'.format(revision))
+    command = []
+    if 'mac' in options.platform:
+        command = ['./run-safari']
+    elif 'ios' in options.platform:
+        command = ['./run-safari', '--simulator']
+    else:
+        print('Default test behavior for this platform is not implemented...'.format(options.platform))
+
+    if command:
+        subprocess.call(command)
+    return prompt_did_reproduce()
+    
+
+def minified_platforms():
+    # FIXME: query this dynamically from API
+    return  ['mac-elcapitan', 'mac-sierra']
+
+
+def unminified_platforms():
+    # FIXME: query this dynamically from API
+    return ['gtk', 'ios-simulator-10', 'mac-elcapitan', 'mac-sierra', 'win', 'wpe']
+
+
+def is_supported_platform(options):
+    if options.full:
+        return options.platform in unminified_platforms()
+    return options.platform in minified_platforms()
+
+
+def validate_options(options):
+    if not is_supported_platform(options):
+        print('Unsupported platform: [{}], exiting...'.format(options.platform))
+        if options.full:
+            print('Available Unminified platforms: {}'.format(unminified_platforms()))
+        else:
+            print('Available Minified platforms: {}'.format(minified_platforms()))
+            print('INFO: pass --full to try against full archives')
+        exit(1)
+
+
+def main(options):
+    validate_options(options)
+
+    url = get_api_url(options)
+    r = requests.get(url)
+    revision_list = get_sorted_revisions(r.json())
+    
+    start_index, end_index = get_indices_from_revisions(revision_list, options.start, options.end)
+    print('Bisecting between {} and {}'.format(revision_list[start_index], revision_list[end_index]))
+    
+    # from here forward, use indices instead of revisions
+    bisect_builds(revision_list, start_index, end_index, options)
+
+
+if __name__ == '__main__':
+    options = parse_args(sys.argv[1:])
+    script_path = os.path.abspath(__file__)
+    script_directory = os.path.dirname(script_path)
+    os.chdir(script_directory)
+    webkit_output_dir = tempfile.mkdtemp()
+    set_webkit_output_dir(webkit_output_dir)
+    try:
+        main(options)    
+    except KeyboardInterrupt:
+        exit("Aborting.")
+    finally:
+        shutil.rmtree(webkit_output_dir, ignore_errors=True)
+#!/usr/bin/env python
+
+# Copyright (C) 2017 Apple Inc. All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+#
+# 1.  Redistributions of source code must retain the above copyright
+#     notice, this list of conditions and the following disclaimer. 
+# 2.  Redistributions in binary form must reproduce the above copyright
+#     notice, this list of conditions and the following disclaimer in the
+#     documentation and/or other materials provided with the distribution. 
+# 3.  Neither the name of Apple Inc. ("Apple") nor the names of
+#     its contributors may be used to endorse or promote products derived
+#     from this software without specific prior written permission. 
+#
+# THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+import argparse
+import bisect
+import math
+import os
+import requests
+import shutil
+import subprocess
+import sys
+import tempfile
+import urlparse
+
+REST_API_URL = 'https://q1tzqfy48e.execute-api.us-west-2.amazonaws.com/v1/'
+REST_API_ENDPOINT = 'archives/'
+REST_API_MINIFIED_ENDPOINT = 'minified-archives/'
+
+
+def bisect_builds(revision_list, start_index, end_index, options):
+    while True:
+        index_to_test = pick_next_build(revision_list, start_index, end_index)
+        if index_to_test == None:
+            print('No more builds to test...')
+            exit(1)
+        download_archive(options, revision_list[index_to_test])
+        extract_archive(options)
+        reproduces = test_archive(options, revision_list[index_to_test])
+
+        if reproduces:          # bisect left
+            index_to_test -= 1  # We can remove this from the end of the list of builds to test
+            bisect_builds(revision_list, start_index, index_to_test, options)
+        if not reproduces:      # bisect right
+            index_to_test += 1  # We can remove this from the start of the list of builds to test
+            bisect_builds(revision_list, index_to_test, end_index, options)
+
+
+def download_archive(options, revision):
+    api_url = get_api_url(options)
+    s3_url = get_s3_location_for_revision(api_url, revision)
+    print('Archive URL: {}'.format(s3_url))
+    command = ['python', '../BuildSlaveSupport/download-built-product', '--{}'.format(options.configuration), '--platform', options.platform, s3_url]
+    print('Downloading revision: {}'.format(revision))
+    subprocess.check_call(command)
+
+
+def extract_archive(options):
+    command = ['python', '../BuildSlaveSupport/built-product-archive', '--platform', options.platform, '--%s' % options.configuration, 'extract']
+    print('Extracting archive: {}'.format(command))
+    subprocess.check_call(command)
+
+
+# ---- bisect helpers from https://docs.python.org/2/library/bisect.html ----
+def find_le(a, x):
+    """Find rightmost value less than or equal to x"""
+    i = bisect.bisect_right(a, x)
+    if i:
+        return i - 1
+    raise ValueError
+
+
+def find_ge(a, x):
+    """Find leftmost item greater than or equal to x"""
+    i = bisect.bisect_left(a, x)
+    if i != len(a):
+        return i
+    raise ValueError
+# ---- end bisect helpers ----
+
+
+def get_api_url(options):
+    if options.full:
+        base_url = urlparse.urljoin(REST_API_URL, REST_API_ENDPOINT)
+    else:
+        base_url = urlparse.urljoin(REST_API_URL, REST_API_MINIFIED_ENDPOINT)
+
+    api_url = urlparse.urljoin(base_url, '-'.join([options.platform, options.architecture, options.configuration]))
+    return api_url
+
+
+def get_indices_from_revisions(revision_list, start_revision, end_revision):
+    if start_revision is None:
+        print('WARNING: No starting revision was given, defaulting to first available for this configuration')
+        start_index = 0
+    else:
+        start_index = find_ge(revision_list, start_revision)
+
+    if end_revision is None:
+        print('WARNING: No ending revision was given, defaulting to last avialable for this configuration')
+        end_index = len(revision_list) - 1
+    else:
+        end_index = find_le(revision_list, end_revision)
+
+    return start_index, end_index
+
+
+def get_sorted_revisions(revisions_dict):
+    revisions = [int(revision['revision']) for revision in revisions_dict['revisions']]
+    return sorted(revisions)
+    
+
+def get_s3_location_for_revision(url, revision):
+    url = '/'.join([url, str(revision)])
+    r = requests.get(url)
+    for archive in r.json()['archive']:
+        s3_url = archive['s3_url']
+    return s3_url
+
+
+def parse_args(args):
+    parser = argparse.ArgumentParser(description='Perform a bisection against existing WebKit archives.')
+    parser.add_argument('-c', '--configuration', default='release', help='The configuration to query [release | debug]')
+    parser.add_argument('-a', '--architecture', default='x86_64', help='The architecture to query [x86_64 | i386]')
+    parser.add_argument('-p', '--platform', default='None', required=True, help='The platform to query [mac-sierra | gtk | ios-simulator | win]')
+    parser.add_argument('-f', '--full', action='store_true', default=False, help='Use full archives containing debug symbols. These are significantly larger files!')
+    parser.add_argument('-s', '--start', default=None, type=int, help='The starting revision to bisect.')
+    parser.add_argument('-e', '--end', default=None, type=int, help='The ending revision to bisect')
+    return parser.parse_args(args)
+
+
+def pick_next_build(revision_list, start_index, end_index):
+    revisions_remaining = (end_index - start_index) + 1
+    print('Found {} revisions in this range to test...'.format(revisions_remaining))
+
+    if start_index >= end_index:
+        print('No archives available between {} and {}'.format(revision_list[end_index], revision_list[start_index]))
+        return None
+
+    middleIndex = (start_index + end_index) / 2
+    return int(math.ceil(middleIndex))
+
+
+def prompt_did_reproduce():
+    var = raw_input('\nDid the error reproduce? [y/n]: ')
+    var = var.lower()
+    if 'y' in var:
+        return True
+    if 'n' in var:
+        return False
+    else:
+        prompt_did_reproduce()
+    
+
+def set_webkit_output_dir(temp_dir):
+    print('Setting environment variable WEBKIT_OUTPUTDIR to {}'.format(temp_dir))
+    os.environ['WEBKIT_OUTPUTDIR'] = temp_dir
+
+
+def test_archive(options, revision):
+    print('Testing revision {}...'.format(revision))
+    command = []
+    if 'mac' in options.platform:
+        command = ['./run-safari']
+    elif 'ios' in options.platform:
+        command = ['./run-safari', '--simulator']
+    else:
+        print('Default test behavior for this platform is not implemented...'.format(options.platform))
+
+    if command:
+        subprocess.call(command)
+    return prompt_did_reproduce()
+    
+
+def minified_platforms():
+    # FIXME: query this dynamically from API
+    return  ['mac-elcapitan', 'mac-sierra']
+
+
+def unminified_platforms():
+    # FIXME: query this dynamically from API
+    return ['gtk', 'ios-simulator-10', 'mac-elcapitan', 'mac-sierra', 'win', 'wpe']
+
+
+def is_supported_platform(options):
+    if options.full:
+        return options.platform in unminified_platforms()
+    return options.platform in minified_platforms()
+
+
+def validate_options(options):
+    if not is_supported_platform(options):
+        print('Unsupported platform: [{}], exiting...'.format(options.platform))
+        if options.full:
+            print('Available Unminified platforms: {}'.format(unminified_platforms()))
+        else:
+            print('Available Minified platforms: {}'.format(minified_platforms()))
+            print('INFO: pass --full to try against full archives')
+        exit(1)
+
+
+def main(options):
+    validate_options(options)
+
+    url = get_api_url(options)
+    r = requests.get(url)
+    revision_list = get_sorted_revisions(r.json())
+    
+    start_index, end_index = get_indices_from_revisions(revision_list, options.start, options.end)
+    print('Bisecting between {} and {}'.format(revision_list[start_index], revision_list[end_index]))
+    
+    # from here forward, use indices instead of revisions
+    bisect_builds(revision_list, start_index, end_index, options)
+
+
+if __name__ == '__main__':
+    options = parse_args(sys.argv[1:])
+    script_path = os.path.abspath(__file__)
+    script_directory = os.path.dirname(script_path)
+    os.chdir(script_directory)
+    webkit_output_dir = tempfile.mkdtemp()
+    set_webkit_output_dir(webkit_output_dir)
+    try:
+        main(options)    
+    except KeyboardInterrupt:
+        exit("Aborting.")
+    finally:
+        shutil.rmtree(webkit_output_dir, ignore_errors=True)
+#!/usr/bin/env python
+
+# Copyright (C) 2017 Apple Inc. All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+#
+# 1.  Redistributions of source code must retain the above copyright
+#     notice, this list of conditions and the following disclaimer. 
+# 2.  Redistributions in binary form must reproduce the above copyright
+#     notice, this list of conditions and the following disclaimer in the
+#     documentation and/or other materials provided with the distribution. 
+# 3.  Neither the name of Apple Inc. ("Apple") nor the names of
+#     its contributors may be used to endorse or promote products derived
+#     from this software without specific prior written permission. 
+#
+# THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+# EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+# DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+# DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+import argparse
+import bisect
+import math
+import os
+import requests
+import shutil
+import subprocess
+import sys
+import tempfile
+import urlparse
+
+REST_API_URL = 'https://q1tzqfy48e.execute-api.us-west-2.amazonaws.com/v1/'
+REST_API_ENDPOINT = 'archives/'
+REST_API_MINIFIED_ENDPOINT = 'minified-archives/'
+
+
+def bisect_builds(revision_list, start_index, end_index, options):
+    while True:
+        index_to_test = pick_next_build(revision_list, start_index, end_index)
+        if index_to_test == None:
+            print('No more builds to test...')
+            exit(1)
+        download_archive(options, revision_list[index_to_test])
+        extract_archive(options)
+        reproduces = test_archive(options, revision_list[index_to_test])
+
+        if reproduces:          # bisect left
+            index_to_test -= 1  # We can remove this from the end of the list of builds to test
+            bisect_builds(revision_list, start_index, index_to_test, options)
+        if not reproduces:      # bisect right
+            index_to_test += 1  # We can remove this from the start of the list of builds to test
+            bisect_builds(revision_list, index_to_test, end_index, options)
+
+
+def download_archive(options, revision):
+    api_url = get_api_url(options)
+    s3_url = get_s3_location_for_revision(api_url, revision)
+    print('Archive URL: {}'.format(s3_url))
+    command = ['python', '../BuildSlaveSupport/download-built-product', '--{}'.format(options.configuration), '--platform', options.platform, s3_url]
+    print('Downloading revision: {}'.format(revision))
+    subprocess.check_call(command)
+
+
+def extract_archive(options):
+    command = ['python', '../BuildSlaveSupport/built-product-archive', '--platform', options.platform, '--%s' % options.configuration, 'extract']
+    print('Extracting archive: {}'.format(command))
+    subprocess.check_call(command)
+
+
+# ---- bisect helpers from https://docs.python.org/2/library/bisect.html ----
+def find_le(a, x):
+    """Find rightmost value less than or equal to x"""
+    i = bisect.bisect_right(a, x)
+    if i:
+        return i - 1
+    raise ValueError
+
+
+def find_ge(a, x):
+    """Find leftmost item greater than or equal to x"""
+    i = bisect.bisect_left(a, x)
+    if i != len(a):
+        return i
+    raise ValueError
+# ---- end bisect helpers ----
+
+
+def get_api_url(options):
+    if options.full:
+        base_url = urlparse.urljoin(REST_API_URL, REST_API_ENDPOINT)
+    else:
+        base_url = urlparse.urljoin(REST_API_URL, REST_API_MINIFIED_ENDPOINT)
+
+    api_url = urlparse.urljoin(base_url, '-'.join([options.platform, options.architecture, options.configuration]))
+    return api_url
+
+
+def get_indices_from_revisions(revision_list, start_revision, end_revision):
+    if start_revision is None:
+        print('WARNING: No starting revision was given, defaulting to first available for this configuration')
+        start_index = 0
+    else:
+        start_index = find_ge(revision_list, start_revision)
+
+    if end_revision is None:
+        print('WARNING: No ending revision was given, defaulting to last avialable for this configuration')
+        end_index = len(revision_list) - 1
+    else:
+        end_index = find_le(revision_list, end_revision)
+
+    return start_index, end_index
+
+
+def get_sorted_revisions(revisions_dict):
+    revisions = [int(revision['revision']) for revision in revisions_dict['revisions']]
+    return sorted(revisions)
+    
+
+def get_s3_location_for_revision(url, revision):
+    url = '/'.join([url, str(revision)])
+    r = requests.get(url)
+    for archive in r.json()['archive']:
+        s3_url = archive['s3_url']
+    return s3_url
+
+
+def parse_args(args):
+    parser = argparse.ArgumentParser(description='Perform a bisection against existing WebKit archives.')
+    parser.add_argument('-c', '--configuration', default='release', help='The configuration to query [release | debug]')
+    parser.add_argument('-a', '--architecture', default='x86_64', help='The architecture to query [x86_64 | i386]')
+    parser.add_argument('-p', '--platform', default='None', required=True, help='The platform to query [mac-sierra | gtk | ios-simulator | win]')
+    parser.add_argument('-f', '--full', action='store_true', default=False, help='Use full archives containing debug symbols. These are significantly larger files!')
+    parser.add_argument('-s', '--start', default=None, type=int, help='The starting revision to bisect.')
+    parser.add_argument('-e', '--end', default=None, type=int, help='The ending revision to bisect')
+    return parser.parse_args(args)
+
+
+def pick_next_build(revision_list, start_index, end_index):
+    revisions_remaining = (end_index - start_index) + 1
+    print('Found {} revisions in this range to test...'.format(revisions_remaining))
+
+    if start_index >= end_index:
+        print('No archives available between {} and {}'.format(revision_list[end_index], revision_list[start_index]))
+        return None
+
+    middleIndex = (start_index + end_index) / 2
+    return int(math.ceil(middleIndex))
+
+
+def prompt_did_reproduce():
+    var = raw_input('\nDid the error reproduce? [y/n]: ')
+    var = var.lower()
+    if 'y' in var:
+        return True
+    if 'n' in var:
+        return False
+    else:
+        prompt_did_reproduce()
+    
+
+def set_webkit_output_dir(temp_dir):
+    print('Setting environment variable WEBKIT_OUTPUTDIR to {}'.format(temp_dir))
+    os.environ['WEBKIT_OUTPUTDIR'] = temp_dir
+
+
+def test_archive(options, revision):
+    print('Testing revision {}...'.format(revision))
+    command = []
+    if 'mac' in options.platform:
+        command = ['./run-safari']
+    elif 'ios' in options.platform:
+        command = ['./run-safari', '--simulator']
+    else:
+        print('Default test behavior for this platform is not implemented...'.format(options.platform))
+
+    if command:
+        subprocess.call(command)
+    return prompt_did_reproduce()
+    
+
+def minified_platforms():
+    # FIXME: query this dynamically from API
+    return  ['mac-elcapitan', 'mac-sierra']
+
+
+def unminified_platforms():
+    # FIXME: query this dynamically from API
+    return ['gtk', 'ios-simulator-10', 'mac-elcapitan', 'mac-sierra', 'win', 'wpe']
+
+
+def is_supported_platform(options):
+    if options.full:
+        return options.platform in unminified_platforms()
+    return options.platform in minified_platforms()
+
+
+def validate_options(options):
+    if not is_supported_platform(options):
+        print('Unsupported platform: [{}], exiting...'.format(options.platform))
+        if options.full:
+            print('Available Unminified platforms: {}'.format(unminified_platforms()))
+        else:
+            print('Available Minified platforms: {}'.format(minified_platforms()))
+            print('INFO: pass --full to try against full archives')
+        exit(1)
+
+
+def main(options):
+    validate_options(options)
+
+    url = get_api_url(options)
+    r = requests.get(url)
+    revision_list = get_sorted_revisions(r.json())
+    
+    start_index, end_index = get_indices_from_revisions(revision_list, options.start, options.end)
+    print('Bisecting between {} and {}'.format(revision_list[start_index], revision_list[end_index]))
+    
+    # from here forward, use indices instead of revisions
+    bisect_builds(revision_list, start_index, end_index, options)
+
+
+if __name__ == '__main__':
+    options = parse_args(sys.argv[1:])
+    script_path = os.path.abspath(__file__)
+    script_directory = os.path.dirname(script_path)
+    os.chdir(script_directory)
+    webkit_output_dir = tempfile.mkdtemp()
+    set_webkit_output_dir(webkit_output_dir)
+    try:
+        main(options)    
+    except KeyboardInterrupt:
+        exit("Aborting.")
+    finally:
+        shutil.rmtree(webkit_output_dir, ignore_errors=True)