Generalised bisection

[Ealdwulf Wuffinga <ealdwulf@googlemail.com>]

[whoops, mail server does not like html. trying again...]

Hi,

I have developed a generalised bisection algorithm, for the case where
a bug is intermittent. The code may be found at
git://github.com/Ealdwulf/bbchop.git. It should be considered
experimental.

This should cover the use cases requested by Ingo
(http://article.gmane.org/gmane.comp.version-control.git/108565) and
John  (http://article.gmane.org/gmane.comp.version-control.git/112280),
although it does not work in the same way as your proposed solutions -
it is intended to be more general, working when the bug is not
almost-deterministic. It is based on Bayesian Search Theory
(http://en.wikipedia.org/wiki/Bayesian_search_theory, although that
description is a bit simplistic) which is usually used to find
submarines, or people lost on mountains.

To try it out, you need python and mpmath (from
http://code.google.com/p/mpmath/ or your distribution).
Once your have obtained the source, you can immediately run BBChop/source/bbchop
which is the main driver program.

It is not currently integrated into git, although doing so should only
involve minor scriptery.

The simplest way to try it out to is run it in manual mode:


>   bbchop -l 10 -c 0.9

This means, search in a linear history of 10 revisions, numbered 0 to
9, until bbchop thinks it has found
the faulty location with probability at least 0.9. It will start
asking questions:

] Most likely location is 0 (probability 0.100000).
] Please test at location 3.
] Target detected at 3? Y/N/S(kip)

Eventually the search will terminate and BBChop will print out its
conclusion, with evidence, eg:

] Search complete.  Most likely location is 3 (probability 0.919614).
] Number of tests at 3: 3 of which 1 detected
] Number of tests at parents of 3:
]         At 2, 5 of which 0 detected

More information canbe found in the readme file.

Feel free to reply with any comments, questions, etc. If anyone tries
it out on a real bug, please let me know how it goes.

regards,

Ealdwulf