[darcs-users] delta-debugging and trackdown --bisect

Eric Kow kowey at darcs.net
Tue Oct 6 08:20:56 UTC 2009

Thanks for this, Jason,

It's occurred to me that we would be much more likely to make progress
if we gave ourselves "permission" to implement bisect instead of the
much cooler Delta Debugging approach (due to my lack of understanding, I
can only presume it's cooler).

So I've split the ticket:
 * http://bugs.darcs.net/issue1208 - trackdown --bisect
   A very *easy* bug that would catch us up nicely
 * http://bugs.darcs.net/issue1638 - trackdown with delta debugging

On Mon, Oct 05, 2009 at 20:48:35 -0700, Jason Dagit wrote:
> In the end their algorithm found approximately 10 places in the code
> (meaning, lines in various files) where it thought the bug was likely to be
> located.

Presumably here Darcs would merely be finding the set of patches which
are likely to trigger the bug.

> I think one of trickiest tasks with trackdown is that sometimes the
> intermediate versions may be correct from the perspective of patch theory
> and being a consistent repository, but the actual state of the pristine may
> not make sense in terms of some other semantics such as the semantics of the
> programming languages used.  In other words, some versions may be valid,
> non-corrupt, repositories but may not compile.  Also, dealing with changes
> surrounding a conflict may be tricky.  Also, the search space may be
> absolutely huge when you consider all the permutations of the patch
> sequence.

Do we really care about order?

> I think these are the concrete ideas that Eric needs someone to think about.

So my difficulty is that, crash course notwithstanding, I still don't really
know what Delta Debugging is other than it being a generalisation of bisect so
I don't know superficially yet concretely what a revision control system like
Darcs is supposed to do.  For example, does it need to care what's in your
repository, or can it (like trackdown) just rely on tests passing and failing?
Is it really just a clever way of pulling and unpulling patches until we find
the minimal set that passes the test and the minimal set that fails?

I suppose I ought to just go away and read the paper for a while.

Quoting the abstract
| We show how the Delta Debugging algorithm isolates the relevant variables and
| values by systematically narrowing the state difference between a passing run
| and a failing run—by assessing the outcome of altered executions to determine
| wether a change in the program state makes a difference in the test outcome. 

Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
PGP Key ID: 08AC04F9
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20091006/e87e5a62/attachment.pgp>

More information about the darcs-users mailing list