[darcs-users] darcs patch: Rewrite "darcs trackdown" help.

[Jason Dagit]

On Mon, Oct 5, 2009 at 3:23 AM, Eric Kow <kowey at darcs.net> wrote:

> On Sat, Oct 03, 2009 at 18:32:32 +1000, Trent W.Buck wrote:
> > Sat Oct  3 18:23:08 EST 2009  Trent W. Buck <trentbuck at gmail.com>
> >   * Rewrite "darcs trackdown" help.
>
> I think my first comment may be grounds for some amendments.
> Could you have a look?
>
> I'll take this opportunity to mention
>  http://bugs.darcs.net/issue1208
>
> which asks for darcs trackdown --bisect
> David mentioned Delta Debugging, which sounds interesting, but we need
> somebody to give a more concrete idea on how this would fit into Darcs.
>

Crash course in Delta Debugging for the curious:

Clever people have realized that much of debugging relies on trial and error
and doing bisection searches between two configurations.  This area is
broadly known as Algorithmic Debugging.  Delta Debugging is a particular
form of AD.  I read a research paper about Delta Debugging several years ago
and I think it's actually a quite interesting approach.

The researchers implemented their tool so that C programs could be debugged
automatically.  Their test case was GCC itself.  At the time, GCC was about
230k lines of code.  They looked through the bug tracker for GCC, found a
bug which had a reproducible test case and a very similar input which did
not trigger the bug.  They also made sure that the bug had a proper fix so
they could evaluate their algorithm's ability to identify the problem spot.
The researchers then let their tool run on GCC for several days unattended.
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.

The first, and maybe the second, lines were not the bug itself.  I think it
was the third highest ranked line of code that was actually present in the
diff for the bug fix.

I believe this is a link to the paper I read:
http://www.st.cs.uni-saarland.de/papers/fse2002/

Now, on to other commentary:

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.

I think it would be interesting if we tracked the various orders of a
repositories patch sequence over its lifetime.  I think that is roughly the
order you want to do the trackdown in, assuming a linear trackdown.

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

Thanks,
Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20091005/7d89a1bf/attachment.htm>