1 # Copyright (C) 2013 Google Inc. All rights reserved.
3 # Redistribution and use in source and binary forms, with or without
4 # modification, are permitted provided that the following conditions are
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
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.
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.
36 from webkitpy.common.system.executive import Executive
37 from webkitpy.common.system.filesystem import FileSystem
38 from webkitpy.common.webkit_finder import WebKitFinder
40 _log = logging.getLogger(__name__)
44 def __init__(self, tests):
48 return len(self.tests)
51 class Bisector(object):
53 def __init__(self, tests, is_debug):
54 self.executive = Executive()
56 self.expected_failure = tests[-1]
57 self.is_debug = is_debug
58 self.webkit_finder = WebKitFinder(FileSystem())
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
66 if not self.test_fails(self.tests):
67 _log.error('%s does not fail' % self.expected_failure)
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():
75 self.split_largest_bucket()
77 self.verify_non_flaky()
80 def test_fails_in_isolation(self):
81 return self.test_bucket_list_fails([Bucket([self.expected_failure])])
83 def verify_non_flaky(self):
84 print 'Verifying the failure is not flaky by running 10 times.'
86 for i in range(0, 10):
87 if self.test_bucket_list_fails(self.buckets):
89 print 'Failed %d/10 times' % count_failures
91 def print_progress(self):
93 for bucket in self.buckets:
94 count += len(bucket.tests)
95 print '%d tests left, %d buckets' % (count, len(self.buckets))
97 def print_result(self):
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))
105 for bucket in self.buckets:
106 if bucket.size() > 1:
110 def split_largest_bucket(self):
114 for bucket in self.buckets:
115 if bucket.size() > largest_size:
116 largest_index = index
117 largest_size = bucket.size()
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:])
125 buckets_before = self.buckets[:largest_index]
126 buckets_after = self.buckets[largest_index + 1:]
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
134 new_buckets = buckets_before + [first_half] + buckets_after
135 if self.test_bucket_list_fails(new_buckets):
136 self.buckets = new_buckets
139 self.buckets = buckets_before + [first_half, second_half] + buckets_after
141 def test_bucket_list_fails(self, buckets):
143 for bucket in buckets:
144 tests += bucket.tests
145 return self.test_fails(tests)
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():
158 logging.basicConfig()
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)
165 tests = open(options.test_list).read().strip().split('\n')
166 bisector = Bisector(tests, is_debug=options.debug)
167 return bisector.bisect()
169 if __name__ == '__main__':
170 sys.exit(main(sys.argv[1:]))