[darcs-users] Delta Debugging

Kenneth Knowles kknowles at berkeley.edu
Mon May 24 06:20:45 UTC 2004

On Sun, May 23, 2004 at 10:59:32PM -0700, Samuel A. Falvo II wrote:
> It sounds to me that if one follows the process of test-driven 
> development, this whole thing becomes unnecessary.  Am I missing 
> something?

I'll reply to this below, but it strongly depends on the quality of your tests.
Even with perfect tests, it could possible identify the minimal set of changes
that break it for another users' system.
> > 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:

> I'm sorry, the above sentence doesn't parse for me.  Can you re-state?

Basically, each use of Delta-Debugging needs its own implementation.  Darcs
provides most of that implementation for the use in source management.  Sorry
about the poor phrasing.

> Would this system be able to handle the case where, for example, I make 
> sweeping changes to several sources files, all at once, then check the 
> whole she-bang into the repo?  Or, would I have to make a very tiny 
> change, check-in, change more, check-in again, etc?

The basic answer is yes.  Better detail is in the papers, and they are short,
sweet, and better phrased than my emails.

The user of DD decides how to split the overall change into pieces, and also how
to test the product of the change - these are the values upon which the
algorithm is parameterized.  To be useful, I think the changes should be much
smaller than those we can manage by hand.

In the paper, they demonstrate find a bug in GCC 2.95.2 by defining a change as
each additional character in the C input file, and the test is whether GCC has
an internal error or not.  Another case is each line of HTML passed to mozilla,
and the test is whether mozilla can print it.

What I'm proposing is that the division be as fine a granularity as darcs can
automate - such as each change in a patch (hunk, addfile, etc) being considered
one change - and the test be whatever test darcs has installed.  This means that
if you code for a while and then run the test, it'll not just say "test failed"
but, if you are patient, tell you a minimal set of lines that cause the failure.


More information about the darcs-users mailing list