[darcs-users] Delta Debugging

Kenneth Knowles kknowles at berkeley.edu
Mon May 24 16:20:37 UTC 2004


On Mon, May 24, 2004 at 10:09:53AM -0400, Andrew Pimlott wrote:
> However, I bet
> you'd get 90% of the benefit with just a binary serach, which would work
> with any RCS that has changesets.
> 
> I wouldn't think about breaking up patches.  You'll get a combinatorial
> explosion of sub-patches, most of which will probably be completely
> broken. 

The algorithm is O(n log n) in whatever level you choose to break up, if I
recall; and it already is pretty much a binary search, except it takes into
account the fact that it may take two non-contiguous hunks to cause the error:

c1 c2 c3* c4 c5 c6 c7* c8
 
If the *s are both needed to cause the bug, binary search returns all the
changes, whereas DD returns [c3, c7].

The good news is that (1) We don't have to run the full test for things that don't
build, that's why it uses a tri-valued test (pass, fail, undetermined), and (2)
darcs already has some information about patches that imply each other, which
then don't have to be split.

Kenn




More information about the darcs-users mailing list