Bisection (software engineering)

Code 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.

Overview

The code bisection method is a divide and conquer algorithm that tries to minimize the effort to find a specific change set.

It depends on the having access to the code history which is usually preserved by revision control in a code repository.

The Bisection Method

Code Bisection Algorithm

Since code history has the structure of an acyclic directed graph which can be topologically sorted it is possible split up a search space, test for the behavior in question and depending on the result reducing the search space further for a next iteration step.

Algorithmic complexity

Code bisection as a divide and conquer algorithm is in LSPACE having an algorithmic complexity of $O(\log _{2}N)$ with $N$ denoting the number of revisions in the search space.

Desirable Repository Properties

For code bisection it is desirable that each revision in the search space can be compiled and tested independently.

Support by Revision Control Systems

Revision control systems like Git or Mercurial directly support ^[1]^[2] code bisection.

Other revision control systems like [[Bazaar_(software)|Bazaar] or Subversion support it indirectly employing plugins^[3] or external scripts^[4].

References

[1] ttp://www.kernel.org/pub/software/scm/git/docs/v1.7.10/git-bisect.html

[2] ttp://www.selenic.com/mercurial/hg.1.html#bisect

[3] ttp://doc.bazaar.canonical.com/plugins/en/bisect-plugin.html

[4] ttp://search.cpan.org/dist/App-SVN-Bisect/bin/svn-bisect

[1]

[2]

[3]

[4]