[darcs-users] Delta Debugging

[Kenneth Knowles]

On Mon, May 24, 2004 at 07:41:12PM -0400, Andrew Pimlott wrote:
> On Mon, May 24, 2004 at 03:59:01PM -0700, Kenneth Knowles wrote:
> > 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!
> 
> Actually, I don't think it's that bad (if I understand what you mean),
> because ddmin will still be able to eliminate the "in between" subsets
> that don't prevent the failure.  That's the first thing I tried when
> looking for a pathological case.  It took me a few tries to find the
> example I gave.

Oh, you are right - I was thinking that everything from 1 to 2 would have an
inconsistent repository.  I guess the key thing about the "1 3 4 2" example is
that you have a "palidrome" of breaking and fixing the build process, where any
of the fixes applied without its respective breaking creates an inconsistent
repository.  (I know this is a sufficient condition, but I'm not sure if it is
necessary)

1 3 4 5 6 7 8 9 2
-----------------
1 3 4 5 6         ?
          7 8 9 2 ?
1 3               ?
    4 5 6         P
          7 8     P
1 3       7 8 9 2 F
-------------------
1 3               ?
          7 8     P
              9 2 ?
-------------------
1 3           9 2 F
1 3               ?
              9 2 ?

1, 3, 9, 2 (assuming that 9 is the fix to 3, like 4 used to be)


With a palindrome:
1 2 3 4 4* 3* 2* 1*
-------------------
1 2 3 4             ?
        4* 3* 2* 1* ?
1 2
    3 4
        4* 3*
              2* 1*
1 2     4* 3* 2* 1* ?
1 2 3 4       2* 1* ?
1 2 3 4 4* 3*       ?

... etc ...

So that's not so bad.  Thanks for the great test cases for my implementation,
too.

Kenn