This document is for future maintainers of the binary search/bisection tools. Authors: * Original Tool: asharif@, llozano@, cmtice@ * Updates after May 2016: cburden@ * chromeos-toolchain@ The following are good reference materials on how the tool works: * Ahmad's original presentation: https://goto.google.com/zxdfyi * Bisection tool update design doc: https://goto.google.com/zcwei * Bisection tool webpage: https://goto.google.com/ruwpyi * Compiler wrapper webpage: https://goto.google.com/xossn TESTING: All unit tests live under the ./test directory. However, these tests specifically test binary_search_state.py, binary_search_perforce.py, bisect.py. These unit tests will not test the specific logic for ChromeOS/Android bisection. To test the ChromeOS/Android bisectors, use the common/hash_test.sh test. This is a simple test case that just checks the hashes of files on your file system. This means you won't have to find a specific compiler error for the bisector to triage in order to test each bisector. TODO: The bisection tool (I believe) is in a fairly good state. So these are mostly wishlist items and things that could use some improvement. 1. Get rid of binary_search_perforce.py. This file is mostly legacy code and the majority of it isn't even used to bisect object files. The file was originally intended to bisect CLs, and binary_search_state.py just reused the binary searching logic from it. Maybe just extract the binary searching logic from binary_search_perforce.py and put it in its own module in cros_utils? 2. Cleanup unit tests in ./test. These tests are a little hacked together, and are all under one test suite. Maybe consider organizing them across multiple directories. 3. Create a "checkout setup" system for bisection. Currently if you want to bisect, you have to run scripts/edit sources in this repo. Ideally these scripts would be static, and if you wanted to bisect/make changes you would "checkout" or copy all the scripts to a working directory and have a unique working directory for each bisection. Credits to Luis for this idea =) 4. Make all scripts relative to each other. Currently all scripts enforce the idea that their cwd will be ./binary_search_tool/. But it would be less confusing to have each script relative to each other. There's quite a few stackoverflow topics on how to do this best, but each one has some sort of downside or flaw. 5. Overall modularize code more, especially in binary_search_state.py DESIGN EXPLANATIONS: Some of the design decisions are a bit difficult to understand from just reading the code unfortunately. I will attempt to clear up the major offenders of this: 1. common.py's argument dictionary: binary_search_state.py and bisect.py both have to have near identical arguments in order to support argument overriding in bisect.py. However they do have to be slightly different. Mainly, bisect.py needs to have no default values for arguments (so it can determine what's being overriden). In order to reduce huge amounts of code duplication for the argument building, we put argument building in common.py. That way both modules can reference the arguments, and they can have different configurations across both. 2. Compiler wrapper: The compiler wrapper is called before all compiler calls. It exists to trick whatever build system (make, emerge, etc.) into thinking our bisection is just a normal build, when really we're doing some tricks. The biggest benefit the compiler wrapper gives is: knowing for sure which files are actually generated by the compiler during bisection setup, and potentially being able to skip compilations while triaging (speeding up the triaging process significantly). 3. The weird options for the --verify, --verbose, --file_args, etc. arguments: Some of the arguments for the bisection tool have a weird set of options for the AddArgument method (nargs, const, default, StrToBool). This is so we can make argument overriding workable. These options allow the following functionality for a boolean argument (using --prune as an example): * --prune (prune set to True) * (prune set to False) * --prune=True (prune set to True) * --prune=False (prune set to False) The first two are easy to implement (action='store_true'), but the last two are why the extra weird arguments are required. Now, why would we want the last two? Imagine if the Android bisector set --prune=True as a default argument. With just the first two options above it would be impossible for the user to override prune and set it to False. So the user needs the --prune=False option. See the argparse documentation for more details. 4. General binary searching logic/pruning logic: binary_search_state.py will enumerate all items into a list. The binary search will find the *first* bad item (starting with lowest index). Everything to the left of the "current" index is switched to good, everything to right of the "current" index is switched to bad. Once a bad item is found, it's put at the very end of the list. If prune is set, the tool will continuing searching until all bad items are found (instead of stopping after the first one). If the tool finds the same item twice, that means no more bad items exist. This is because the item was found, said item was put at the end of the list, and it was found again. Because the binary search logic finds the bad item with the lowest index, this means nothing in between the start of the list and the end of the list is bad (thus no more bad items remain).