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


More information about the darcs-users mailing list