Tools/Scripts/bisect-builds

#!/usr/bin/env python3

# Copyright (C) 2017, 2020 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.

# A webkitpy import needs to go first for autoinstaller to work with subsequent imports.
from webkitpy.common.memoized import memoized
from webkitpy.common.system.systemhost import SystemHost
from webkitpy.common.version_name_map import VersionNameMap

from webkitcorepy.string_utils import pluralize

import argparse
import bisect
import json
import math
import os
import shutil
import subprocess
import sys
import tempfile
import urllib


REST_API_URL = 'https://q1tzqfy48e.execute-api.us-west-2.amazonaws.com/v2_2/'
REST_API_ARCHIVE_ENDPOINT = 'archives/'
REST_API_MINIFIED_ARCHIVE_ENDPOINT = 'minified-archives/'
REST_API_PLATFORM_ENDPOINT = 'platforms'
REST_API_MINIFIED_PLATFORM_ENDPOINT = 'minified-platforms'


class QueueDescriptor(object):
    def __init__(self, descriptor_string):
        self.platform_name = None
        self.version = None
        self.architectures = set()
        self.configuration = None

        if descriptor_string.startswith('mac-'):
            platform_name_end_index = descriptor_string.find('-')
            version_start_index = platform_name_end_index + 1
            version_end_index = descriptor_string.find('-', version_start_index)
            self.platform_name = descriptor_string[:platform_name_end_index]
            if version_end_index == -1:
                self.version = descriptor_string[version_start_index:]
                return
            self.version = descriptor_string[version_start_index:version_end_index]
            architectures_and_configuration = descriptor_string[version_end_index + 1:]
        elif descriptor_string.startswith('ios-simulator-'):
            platform_name_end_index = descriptor_string.find('-', descriptor_string.find('-') + 1)
            version_start_index = platform_name_end_index + 1
            version_end_index = descriptor_string.find('-', version_start_index)
            self.platform_name = descriptor_string[:platform_name_end_index]
            if version_end_index == -1:
                self.version = descriptor_string[version_start_index:]
                return
            self.version = descriptor_string[version_start_index:version_end_index]
            architectures_and_configuration = descriptor_string[version_end_index + 1:]
        else:
            platform_name_end_index = descriptor_string.find('-')
            if platform_name_end_index == -1:
                self.platform_name = descriptor_string
                return
            self.platform_name = descriptor_string[:platform_name_end_index]
            architectures_and_configuration = descriptor_string[platform_name_end_index + 1:]
        architectures_end_index = architectures_and_configuration.find('-')
        if architectures_end_index == -1:
            self.architectures = set(architectures_and_configuration.split(' '))
            return
        configuration_start_index = architectures_end_index + 1
        self.architectures = set(architectures_and_configuration[:architectures_end_index].split(' '))
        self.configuration = architectures_and_configuration[configuration_start_index:]

    def pretty_string(self):
        result = self.platform_name
        if self.version:
            result += '-' + self.version
        result += ' (' + ' '.join(self.architectures)
        result += ', ' + self.configuration + ')'
        return result


def trac_link(start_revision, end_revision):
    if start_revision + 1 == end_revision:
        return 'https://trac.webkit.org/r{}'.format(end_revision)
    else:
        return 'https://trac.webkit.org/log/trunk/?mode=follow_copy&rev={}&stop_rev={}'.format(end_revision, start_revision + 1)


def bisect_builds(revision_list, start_index, end_index, options):
    index_to_test = pick_next_build(revision_list, start_index, end_index)
    if index_to_test is None:
        print('\nWorks: r{}'.format(revision_list[start_index]))
        print('Fails: r{}'.format(revision_list[end_index]))
        print(trac_link(revision_list[start_index], revision_list[end_index]))
        exit(0)

    archive_count = end_index - start_index - 1
    print('Bisecting between r{} and r{}, {} in the range.'.format(revision_list[start_index], revision_list[end_index], pluralize(archive_count, 'archive')))
    reproduces = test_revision(options, revision_list[index_to_test])

    if reproduces:
        bisect_builds(revision_list, start_index, index_to_test, options)
    else:
        bisect_builds(revision_list, index_to_test, end_index, options)


# download-built-product and built-product-archive implicitly use WebKitBuild directory for downloaded archive.
# FIXME: Modifying the WebKitBuild directory makes no sense here, find a way to use a temporary directory for the archive.
def download_archive(options, revision):
    api_url = get_api_archive_url(options)
    s3_url = get_s3_location_for_revision(api_url, revision)
    print('Downloading r{}: {}'.format(revision, s3_url))
    command = ['python', '../CISupport/download-built-product', '--{}'.format(options.configuration), '--platform', options.platform, s3_url]
    subprocess.check_call(command)


def extract_archive(options):
    command = ['python', '../CISupport/built-product-archive', '--{}'.format(options.configuration), '--platform', options.platform, 'extract']
    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_archive_url(options, last_evaluated_key=None):
    if options.full:
        base_url = urllib.parse.urljoin(REST_API_URL, REST_API_ARCHIVE_ENDPOINT)
    else:
        base_url = urllib.parse.urljoin(REST_API_URL, REST_API_MINIFIED_ARCHIVE_ENDPOINT)

    api_url = urllib.parse.urljoin(base_url, urllib.parse.quote(options.queue))
    if last_evaluated_key:
        querystring = urllib.parse.quote(json.dumps(last_evaluated_key))
        api_url += '?ExclusiveStartKey=' + querystring

    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 available 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(item['revision']['N']) for item in revisions_dict['revisions']['Items']]
    return sorted(revisions)


def get_s3_location_for_revision(url, revision):
    url = '/'.join([url, str(revision)])
    r = urllib.request.urlopen(url)
    data = json.load(r)

    for archive in data['archive']:
        s3_url = archive['s3_url']
    return s3_url


def host_platform_name():
    platform = SystemHost().platform
    version_name = VersionNameMap.strip_name_formatting(platform.os_version_name())
    if version_name is None:
        return platform.os_name
    return platform.os_name + '-' + version_name


def parse_args(args):
    helptext = 'bisect-builds helps pinpoint regressions to specific code changes. It does this by bisecting across archives produced by build.webkit.org. Full and "minified" archives are available. Minified archives are significantly smaller, as they have been stripped of dSYMs and other non-essential components.'
    parser = argparse.ArgumentParser(description=helptext)
    parser.add_argument('-c', '--configuration', default='release', help='the configuration to query [release | debug]')
    parser.add_argument('-a', '--architecture', help='the architecture to query, e.g. x86_64, default is no preference')
    parser.add_argument('-p', '--platform', default=host_platform_name(), help='the platform to query, e.g. mac-bigsur, gtk, ios-simulator-14, win, default is current host platform.')
    parser.add_argument('-f', '--full', action='store_true', default=False, help='use full archives containing debug symbols, which 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')
    parser.add_argument('--sanity-check', action='store_true', default=False, help='verify both starting and ending revisions before bisecting')
    parser.add_argument('-l', '--list', action='store_true', default=False, help='display a list of platforms and revisions')
    return parser.parse_args(args)


def pick_next_build(revision_list, start_index, end_index):
    if start_index + 1 >= end_index:
        print('No archives available between r{} and r{}.'.format(revision_list[start_index], revision_list[end_index]))
        return None

    middle_index = (start_index + end_index) / 2
    return int(math.ceil(middle_index))


def prompt_did_reproduce():
    var = 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('Archives will be extracted to {}'.format(temp_dir))
    os.environ['WEBKIT_OUTPUTDIR'] = temp_dir


def test_revision(options, revision):
    download_archive(options, revision)
    extract_archive(options)
    if options.platform.startswith('ios-simulator'):
        command = ['./run-safari', '--iphone-simulator', '--{}'.format(options.configuration)]
    else:
        command = ['./run-minibrowser', '--{}'.format(options.configuration)]

    if command:
        subprocess.call(command, stdout=subprocess.DEVNULL, stderr=subprocess.DEVNULL)
    return prompt_did_reproduce()


def get_platforms(endpoint):
    platform_url = urllib.parse.urljoin(REST_API_URL, endpoint)
    r = urllib.request.urlopen(platform_url)
    data = json.load(r)
    platforms = []
    for platform in data.get('Items'):
        platforms.append(str(platform['identifier']['S']))

    return platforms


@memoized
def minified_platforms():
    return get_platforms(REST_API_MINIFIED_PLATFORM_ENDPOINT)


@memoized
def unminified_platforms():
    return get_platforms(REST_API_PLATFORM_ENDPOINT)


def queue_for(options):
    if options.full:
        platform_list = unminified_platforms()
    else:
        platform_list = minified_platforms()

    descriptor_from_options = QueueDescriptor(options.platform)

    if not descriptor_from_options.architectures:
        if options.architecture:
            descriptor_from_options.architectures = set(options.architecture)
    elif options.architecture is not None and descriptor_from_options.architectures != {options.architecture}:
        return None

    if not descriptor_from_options.configuration:
        if options.configuration:
            descriptor_from_options.configuration = options.configuration
    elif options.configuration is not None and descriptor_from_options.configuration != options.configuration:
        return None

    for platform_name in platform_list:
        available_platform = QueueDescriptor(platform_name)
        if descriptor_from_options.platform_name != available_platform.platform_name:
            continue
        if descriptor_from_options.version and descriptor_from_options.version != available_platform.version:
            continue
        if not descriptor_from_options.architectures.issubset(available_platform.architectures):
            continue
        if descriptor_from_options.configuration and descriptor_from_options.configuration != available_platform.configuration:
            continue
        return platform_name
    return None


def print_platforms(platforms):
    platform_strings = ['    {}'.format(QueueDescriptor(queue_name).pretty_string()) for queue_name in platforms]
    print('\n'.join(sorted(platform_strings)))


def validate_options(options):
    options.queue = queue_for(options)  # Resolve and cache for future use.
    if options.queue is None:
        print('Unsupported platform combination, exiting.')
        if options.full:
            print('Available unminified platforms:')
            print_platforms(unminified_platforms())
        else:
            print('Available minified platforms:')
            print_platforms(minified_platforms())
        exit(1)


def print_list_and_exit(revision_list, options):
    print('Supported minified platforms:')
    print_platforms(minified_platforms())
    print('Supported unminified platforms:')
    print_platforms(unminified_platforms())
    print('{} revisions available for {}:'.format(len(revision_list), options.queue))
    print(revision_list)
    exit(0)


def fetch_revision_list(options, last_evaluated_key=None):
    url = get_api_archive_url(options, last_evaluated_key)
    r = urllib.request.urlopen(url)
    data = json.load(r)
    revision_list = get_sorted_revisions(data)

    if 'LastEvaluatedKey' in data['revisions']:
        last_evaluated_key = data['revisions']['LastEvaluatedKey']
        revision_list += fetch_revision_list(options, last_evaluated_key)

    return revision_list


def 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()

    validate_options(options)
    revision_list = fetch_revision_list(options)

    if options.list:
        print_list_and_exit(revision_list, options)

    if not revision_list:
        print('No archives found for {}.'.format(options.queue))
        exit(1)
    start_index, end_index = get_indices_from_revisions(revision_list, options.start, options.end)

    set_webkit_output_dir(webkit_output_dir)

    # From here forward, use indices instead of revisions.
    try:
        if options.sanity_check:
            if test_revision(options, revision_list[start_index]):
                print('Issue reproduced with the first revision in the range, cannot bisect.')
                exit(1)
            if not test_revision(options, revision_list[end_index]):
                print('Issue did not reproduce with the last revision in the range, cannot bisect.')
                exit(1)

        bisect_builds(revision_list, start_index, end_index, options)
    except KeyboardInterrupt:
        exit(1)
    finally:
        shutil.rmtree(webkit_output_dir, ignore_errors=True)


if __name__ == '__main__':
    main()