[darcs-users] Delta Debugging

Kenneth Knowles kknowles at berkeley.edu
Mon May 24 16:34:44 UTC 2004

On Mon, May 24, 2004 at 08:10:02AM -0400, David Roundy wrote:
> 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
> system.

I left this out, but there are optimizations inherent in the algorithm where you
can leave some patches applied.  I implemented the ddmin algorithm instead of
the dd+ because it has more of these opportunities.  There are a lot of
domain-specific optimization suggestions in the papers, and things like whether
patches commute will really reduce the search space.

However, this is never going to "fast" as you can imagine.  (I've never used
trackdown, but I assume it is kind of a linear search of the same space).

Oh, and in a previous post I said the worst-case was O(n log n) but I must have
been thinking of something else.  If every single change is required to cause
the failure, it takes O(n^2) tests, but that is a reall pathological case; if
there is just one failure-inducing change then it is O(log n).

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

The papers are quite general, and the test you use can just return
"indeterminate" when this occurs.  The type of the algorithm is

ddmin :: (List a -> Maybe Bool) -> List a -> List a

And returning "Nothing" from the test function would be the thing to do when a
compile fails.

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

Excellent, this should be fun.


More information about the darcs-users mailing list