# Copyright 2020 The Chromium OS Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

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,
run_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 run_bisect.py both have to have near identical
     arguments in order to support argument overriding in run_bisect.py. However
     they do have to be slightly different. Mainly, run_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)
       * <not given> (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).