1 # Copyright (C) 2013 Google Inc. All rights reserved. 2 # 3 # Redistribution and use in source and binary forms, with or without 4 # modification, are permitted provided that the following conditions are 5 # met: 6 # 7 # * Redistributions of source code must retain the above copyright 8 # notice, this list of conditions and the following disclaimer. 9 # * Redistributions in binary form must reproduce the above 10 # copyright notice, this list of conditions and the following disclaimer 11 # in the documentation and/or other materials provided with the 12 # distribution. 13 # * Neither the name of Google Inc. nor the names of its 14 # contributors may be used to endorse or promote products derived from 15 # this software without specific prior written permission. 16 # 17 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 29 import logging 30 import math 31 import optparse 32 import os 33 import subprocess 34 import sys 35 36 from webkitpy.common.system.executive import Executive 37 from webkitpy.common.system.filesystem import FileSystem 38 from webkitpy.common.webkit_finder import WebKitFinder 39 40 _log = logging.getLogger(__name__) 41 42 43 class Bucket(object): 44 def __init__(self, tests): 45 self.tests = tests 46 47 def size(self): 48 return len(self.tests) 49 50 51 class Bisector(object): 52 53 def __init__(self, tests, is_debug): 54 self.executive = Executive() 55 self.tests = tests 56 self.expected_failure = tests[-1] 57 self.is_debug = is_debug 58 self.webkit_finder = WebKitFinder(FileSystem()) 59 60 def bisect(self): 61 if self.test_fails_in_isolation(): 62 self.buckets = [Bucket([self.expected_failure])] 63 print '%s fails when run in isolation.' % self.expected_failure 64 self.print_result() 65 return 0 66 if not self.test_fails(self.tests): 67 _log.error('%s does not fail' % self.expected_failure) 68 return 1 69 # Split the list of test into buckets. Each bucket has at least one test required to cause 70 # the expected failure at the end. Split buckets in half until there are only buckets left 71 # with one item in them. 72 self.buckets = [Bucket(self.tests[:-1]), Bucket([self.expected_failure])] 73 while not self.is_done(): 74 self.print_progress() 75 self.split_largest_bucket() 76 self.print_result() 77 self.verify_non_flaky() 78 return 0 79 80 def test_fails_in_isolation(self): 81 return self.test_bucket_list_fails([Bucket([self.expected_failure])]) 82 83 def verify_non_flaky(self): 84 print 'Verifying the failure is not flaky by running 10 times.' 85 count_failures = 0 86 for i in range(0, 10): 87 if self.test_bucket_list_fails(self.buckets): 88 count_failures += 1 89 print 'Failed %d/10 times' % count_failures 90 91 def print_progress(self): 92 count = 0 93 for bucket in self.buckets: 94 count += len(bucket.tests) 95 print '%d tests left, %d buckets' % (count, len(self.buckets)) 96 97 def print_result(self): 98 tests = [] 99 for bucket in self.buckets: 100 tests += bucket.tests 101 extra_args = ' --debug' if self.is_debug else '' 102 print 'run-webkit-tests%s --child-processes=1 --order=none %s' % (extra_args, " ".join(tests)) 103 104 def is_done(self): 105 for bucket in self.buckets: 106 if bucket.size() > 1: 107 return False 108 return True 109 110 def split_largest_bucket(self): 111 index = 0 112 largest_index = 0 113 largest_size = 0 114 for bucket in self.buckets: 115 if bucket.size() > largest_size: 116 largest_index = index 117 largest_size = bucket.size() 118 index += 1 119 120 bucket_to_split = self.buckets[largest_index] 121 halfway_point = int(largest_size / 2) 122 first_half = Bucket(bucket_to_split.tests[:halfway_point]) 123 second_half = Bucket(bucket_to_split.tests[halfway_point:]) 124 125 buckets_before = self.buckets[:largest_index] 126 buckets_after = self.buckets[largest_index + 1:] 127 128 # Do the second half first because it tends to be faster because the http tests are front-loaded and slow. 129 new_buckets = buckets_before + [second_half] + buckets_after 130 if self.test_bucket_list_fails(new_buckets): 131 self.buckets = new_buckets 132 return 133 134 new_buckets = buckets_before + [first_half] + buckets_after 135 if self.test_bucket_list_fails(new_buckets): 136 self.buckets = new_buckets 137 return 138 139 self.buckets = buckets_before + [first_half, second_half] + buckets_after 140 141 def test_bucket_list_fails(self, buckets): 142 tests = [] 143 for bucket in buckets: 144 tests += bucket.tests 145 return self.test_fails(tests) 146 147 def test_fails(self, tests): 148 extra_args = ['--debug'] if self.is_debug else [] 149 path_to_run_webkit_tests = self.webkit_finder.path_from_webkit_base('Tools', 'Scripts', 'run-webkit-tests') 150 output = self.executive.popen([path_to_run_webkit_tests, '--child-processes', '1', '--order', 'none', '--no-retry', '--no-show-results', '--verbose'] + extra_args + tests, stdout=subprocess.PIPE, stderr=subprocess.PIPE) 151 failure_string = self.expected_failure + ' failed' 152 if failure_string in output.stderr.read(): 153 return True 154 return False 155 156 157 def main(argv): 158 logging.basicConfig() 159 160 option_parser = optparse.OptionParser() 161 option_parser.add_option('--test-list', action='store', help='file that list tests to bisect. The last test in the list is the expected failure.', metavar='FILE'), 162 option_parser.add_option('--debug', action='store_true', default=False, help='whether to use a debug build'), 163 options, args = option_parser.parse_args(argv) 164 165 tests = open(options.test_list).read().strip().split('\n') 166 bisector = Bisector(tests, is_debug=options.debug) 167 return bisector.bisect() 168 169 if __name__ == '__main__': 170 sys.exit(main(sys.argv[1:])) 171