1# Copyright 2020 The Chromium OS Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5This document is for future maintainers of the binary search/bisection tools.
6
7Authors:
8  * Original Tool: asharif@, llozano@, cmtice@
9  * Updates after May 2016: cburden@
10  * chromeos-toolchain@
11
12The following are good reference materials on how the tool works:
13  * Ahmad's original presentation:
14    https://goto.google.com/zxdfyi
15
16  * Bisection tool update design doc:
17    https://goto.google.com/zcwei
18
19  * Bisection tool webpage:
20    https://goto.google.com/ruwpyi
21
22  * Compiler wrapper webpage:
23    https://goto.google.com/xossn
24
25
26TESTING:
27All unit tests live under the ./test directory. However, these tests
28specifically test binary_search_state.py, binary_search_perforce.py,
29run_bisect.py.
30
31These unit tests will not test the specific logic for ChromeOS/Android
32bisection. To test the ChromeOS/Android bisectors, use the common/hash_test.sh
33test. This is a simple test case that just checks the hashes of files on your
34file system. This means you won't have to find a specific compiler error for
35the bisector to triage in order to test each bisector.
36
37TODO:
38The bisection tool (I believe) is in a fairly good state. So these are mostly
39wishlist items and things that could use some improvement.
40
41  1. Get rid of binary_search_perforce.py. This file is mostly legacy code and
42     the majority of it isn't even used to bisect object files. The file was
43     originally intended to bisect CLs, and binary_search_state.py just reused
44     the binary searching logic from it. Maybe just extract the binary searching
45     logic from binary_search_perforce.py and put it in its own module in
46     cros_utils?
47
48  2. Cleanup unit tests in ./test. These tests are a little hacked together,
49     and are all under one test suite. Maybe consider organizing them across
50     multiple directories.
51
52  3. Create a "checkout setup" system for bisection. Currently if you want to
53     bisect, you have to run scripts/edit sources in this repo. Ideally these
54     scripts would be static, and if you wanted to bisect/make changes you would
55     "checkout" or copy all the scripts to a working directory and have a unique
56     working directory for each bisection. Credits to Luis for this idea =)
57
58  4. Make all scripts relative to each other. Currently all scripts enforce the
59     idea that their cwd will be ./binary_search_tool/. But it would be less
60     confusing to have each script relative to each other. There's quite a few
61     stackoverflow topics on how to do this best, but each one has some sort of
62     downside or flaw.
63
64  5. Overall modularize code more, especially in binary_search_state.py
65
66DESIGN EXPLANATIONS:
67Some of the design decisions are a bit difficult to understand from just reading
68the code unfortunately. I will attempt to clear up the major offenders of this:
69
70  1. common.py's argument dictionary:
71     binary_search_state.py and run_bisect.py both have to have near identical
72     arguments in order to support argument overriding in run_bisect.py. However
73     they do have to be slightly different. Mainly, run_bisect.py needs to have
74     no default values for arguments (so it can determine what's being
75     overriden).
76
77     In order to reduce huge amounts of code duplication for the argument
78     building, we put argument building in common.py. That way both modules
79     can reference the arguments, and they can have different configurations
80     across both.
81
82  2. Compiler wrapper:
83     The compiler wrapper is called before all compiler calls. It exists to
84     trick whatever build system (make, emerge, etc.) into thinking our
85     bisection is just a normal build, when really we're doing some tricks.
86
87     The biggest benefit the compiler wrapper gives is: knowing for sure which
88     files are actually generated by the compiler during bisection setup, and
89     potentially being able to skip compilations while triaging (speeding up the
90     triaging process significantly).
91
92  3. The weird options for the --verify, --verbose, --file_args, etc. arguments:
93     Some of the arguments for the bisection tool have a weird set of options
94     for the AddArgument method (nargs, const, default, StrToBool). This is so
95     we can make argument overriding workable. These options allow the following
96     functionality for a boolean argument (using --prune as an example):
97       * --prune (prune set to True)
98       * <not given> (prune set to False)
99       * --prune=True (prune set to True)
100       * --prune=False (prune set to False)
101
102     The first two are easy to implement (action='store_true'), but the last two
103     are why the extra weird arguments are required. Now, why would we want the
104     last two? Imagine if the Android bisector set --prune=True as a default
105     argument. With just the first two options above it would be impossible for
106     the user to override prune and set it to False. So the user needs the
107     --prune=False option. See the argparse documentation for more details.
108
109  4. General binary searching logic/pruning logic:
110     binary_search_state.py will enumerate all items into a list. The binary
111     search will find the *first* bad item (starting with lowest index).
112     Everything to the left of the "current" index is switched to good,
113     everything to right of the "current" index is switched to bad. Once a bad
114     item is found, it's put at the very end of the list.
115
116     If prune is set, the tool will continuing searching until all bad items are
117     found (instead of stopping after the first one). If the tool finds the same
118     item twice, that means no more bad items exist. This is because the item
119     was found, said item was put at the end of the list, and it was found
120     again. Because the binary search logic finds the bad item with the lowest
121     index, this means nothing in between the start of the list and the end of
122     the list is bad (thus no more bad items remain).
123