[darcs-users] Delta Debugging

Kenneth Knowles kknowles at berkeley.edu
Mon May 24 04:44:28 UTC 2004


Hi all,

I've been doing two things for my own educational entertainment, and they might
combine into something useful (assuming noone else has done this already).

1) I read about Delta Debugging, and implemented a framework for the algorithm
in O'Caml.

2) To learn Haskell better, since I've only perused the docs, I'm porting it to
Haskell.

Here are the two relevant papers I read:

http://www.infosun.fmi.uni-passau.de/st/papers/tr-99-01/
http://www.infosun.fmi.uni-passau.de/st/papers/issta2000/

For those who don't have time to read the papers, the idea is that starting with
the last known working configuration of a program, you apply the changes
gradually until it breaks.  The algorithm is more sophisticated, and finds a
minimal set of changes causing the error.  It is parameterized by the type of
"change" you are applying and the test function.  In the papers, the examples
are very impressive, narrowing bugs in GCC, GDB, and Mozilla down to a couple
lines out of thousands, or even characters.

The biggest drawback of the technique for wide use is that you have to
re-implement for each test and type that you want to evaluate, but for darcs
we've already got this stuff and a big library for manipulating it:

Since we have "darcs trackdown" and also a built in notion of a
test, as well as hunks as a good place to divide patches, it should be pretty
straightforward to implement this.  The part I don't feel comfortable doing
myself is the creation of a temp directory or whatnot to apply patches gradually
and run the test.  I admit that this part is probably more work than the
framework, but is this of interest?

I really think this would be great because when someone says "I just pulled
darcs and now it doesn't work" you can ask for the output of "darcs deltadebug"
or some such, and it is guaranteed to give you a minimal set of hunks to
reproduce the error.

Would this have a chance of making it into darcs?

Kenn






More information about the darcs-users mailing list