[darcs-users] Delta Debugging

Kenneth Knowles kknowles at berkeley.edu
Mon May 24 22:59:01 UTC 2004

On Mon, May 24, 2004 at 05:28:36PM -0400, Andrew Pimlott wrote:
> Ok, I took a look at those papers, and from what I can tell, they aren't
> very promising for trying to break patches into sub-patches.  The
> problem as I said is that most combinations of sub-patches will be
> broken, ie they will give an indeterminate result.  Take this example,
> which I don't think is too contrived:  We have 8 sub-patches.  1, 2, 3
> (sub-patch set a) go together, as do 1, 2, 4, 5, 7 (sub-patch set b).
> sub-patch set b works, sub-patch set a has a bug, and the code only
> builds if the sub-patch sets are either entirely present or absent.  I
> don't think that any variant of their algorithm will identify patch-set
> a as the minimal test case.  Instead, they will give the full set of
> sub-patches.

This doesn't compute for me, because sub-patch set b will not build by your
criteria - you must either add 3 or remove 1 and 2.  So the minimal set of
patches that even builds is [1, 2, 3, 4, 5, 6, 7].  However, your example below
indicates clearly that things which break the build cause problems.

I'm going to start at the patch level, in any event.
> Here is an example, which I tested with the DD.py implementation:  Say
> patch 1 breaks the build, then patch 2 fixes it but introduces the
> target bug, then patch 3 breaks the build, then patch 4 fixes it.  If
> the patches stay in order, ddmin will find the test case (1, 2).  If
> patch 2 is moved to the end, ddmin will find (1, 2, 3, 4).

I see what you mean (just did it myself, and left the transcript below for the
reading pleasure of the list).  It would be even worse if there were 100
sub-patches and consistency only existed when the first and last were both
applied.  Yikes!

It definitely cries out for enough meta-information to group (1, 2) as a single
patch, and likewise (3, 4).  Relevant suggestions from the papers include this
intelligent grouping of patches that imply one another, and also predicting test
outcomes using this information, so the unresolved tests don't have to be
carried out.  I'm not sure how to go about getting this information, other than
hoping it can be inferred from darcs meta-data sometimes.

It seems that in terms of having a consistent repository, patch 2 doesn't
actually commute with 3 and 4, since the repo remains inconsistent.  Good
repository discipline would have you unrecord patch 1 and re-record it with
patch 2, but I certainly have no illusions about that issue :-)


1 3 4 2
1 3     ?
    4 2 ?
1       ?
  3     ?
    4   ?
      2 ?
  3 4 2 ?
1   4 2 ?
1 3   2 ?
  3 4 2 ?

1 3 4 2 F

More information about the darcs-users mailing list