Bisection is a method used in software development to identify change sets that result in a specific behavior change. It is mostly employed for finding the patch that introduced a bug. Another application area is finding the patch that indirectly fixed a bug.
Contents
Overview
Code bisection has the goal of minimizing the effort to find a specific change set.
It employs a divide and conquer algorithm that depends on having access to the code history which is usually preserved by revision control in a code repository.
Code bisection algorithm
Code history has the structure of a directed acyclic graph which can be topologically sorted. This makes it possible to use a divide and conquer search algorithm which:
Algorithmic complexity
Bisection is in LSPACE having an algorithmic complexity of
Desirable repository properties
For code bisection it is desirable that each revision in the search space can be built and tested independently.
Support by revision control systems
Revision control systems like Git or Mercurial directly support code bisection.
Other revision control systems like Bazaar or Subversion support it indirectly employing plugins or external scripts.