[darcs-users] Delta Debugging

David Roundy droundy at abridgegame.org
Mon May 24 12:10:02 UTC 2004

On Sun, May 23, 2004 at 09:44:28PM -0700, Kenneth Knowles wrote:
> 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?

Something like this would definitely be great to have in darcs.  This is
basically what I was sort of hoping the trackdown command would evolve
into, but after finding the bug for which I wrote trackdown (it was in a
code at work) I've never really had occasion to use it, so it has sort of

I'd recommend starting by implementing delta debugging at the "recorded
change" level--this is what I would personally find most useful--and just
replace the existing trackdown command, since it ought to be subsumed by
the delta-debugging technique anyways.

Once that is working (which should be a challenge in itself), then
extending to work out which primitive patches are needed could be added as
an option.

One question is whether to use a clean copy for each test.  Trackdown
doesn't do this currently, which is nice because it means you only have to
recompile files that are modified from one version to the next, but could
lead to "interesting" histeresis effects if there are bugs in the build

Another thought is that perhaps we could also add an "--auto-depends"
feature to record, which would use some sort of clever algorithm (related
to delta-debugging, perhaps?) to run a number of tests to see which patches
are required by the being-recorded patch in order to pass the tests.  For
the darcs repo this would probably be prohibitively slow (at least on my
computer), but it would be a cool feature to have.  And actually the repo
I'm using at work has a test suite that currently takes about an hour to
complete... stupid wavelets!

There's also some question (in my mind) as to the most useful set of
changes to tell the user about.  It depends on what tests the user
has--e.g. if the test can distinguish between the desired bug and a compile

I imagine implementing something like

latest_working_version :: FilePath -> (IO ()) -> (IO Bool) -> IO PatchSet

where the first argument is the location of a repository (a PatchSet could
be given instead, but we might want to throw away and reread the patches to
save memory), the second argument is an initialization function, and the
third is the actual test.  This function wouldn't only test versions in the
linear sequence, but would try any combinations of patches that it likes to
try to get a version with the most patches in it that passes the test.

I should read the papers you referenced (but haven't done so and won't have
time today)... I presume they must deal with the issue of distinguishing
between a simple compile error and the bug itself.

So yes, there is interest in implementing such a feature in darcs... :)
David Roundy

More information about the darcs-users mailing list