[darcs-users] darcs trackdown

[David Roundy]

On Tue, Oct 04, 2005 at 08:19:20PM -0700, John Meacham wrote:
> this reminds me. I tried using trackdown recently, and one of the first
> patches it unpulled was the one that sets up the test case :(

Generally it's best to have the test case external to the repository
(i.e. call it with an absolute path).  Otherwise you run into precisely the
problem you describe.

> it seems a much better algorithm would be to iterate through the patches
> and test the whole repo without just that patch. (and any that depend on
> it), I find that very commonly, it gets past a point where it unpulls
> something that is actually needed and the whole trackdown fails back to
> stage one.

Indeed, the algorithm used by trackdown is quite stupid.  There are a
couple of papers referenced in the following email

http://www.abridgegame.org/pipermail/darcs-users/2004-May/002006.html

which describe algorithms to do what trackdown *ought* to do.  I'd suggest
that implementing something like those (or at least reading them carefully)
would be a good idea.

> I would be willing to do the coding, but don't know much about darcs
> internals (but know haskell quite well). 

I'm sure you'll catch on fine...  It shouldn't be too hard, but you'd need
to handle some moderately tricky commutation business.

> looking at the trackdown code, it appears to just get a list of patches,
> and applys the inverse of each one in order running the test case each
> time.
>
> it seems like it would be simple to invert a patch, apply it, test, then
> apply the original patch and then invert the next, test it, reapply the patch
> and so forth...  the only thing I am not sure about is how to "follow
> through" to get at all the dependencies of a patch so they can be
> temporarily undone too, and when it is a group of patches, how do I
> invert and apply the whole group? 
> 
> does this sound like it would work? does it seem like a good idea? any
> pointers?

The trick would be to do the commutation so that you could properly
apply/unapply the patches with the right context.  If only we had our
GADT-based context-checking types in place, you'd be a lot safer.  The
trouble is that if you get the commutation wrong, your code will often work
for most test cases you try, only to fail on some relatively rare case.

I'd recommend using PatchChoices to handle the dependencies for you.
PatchChoices holds a sequence of patches and you can tell it which patches
you want and which you don't want, and ask it for the patches you want,
properly commuted.  This is easier (and safer) than doing the commutation
yourself.  It also allows you to just view the patches as a set, which
should allow you to code at a higher level.  The tricky bit (where you have
to think a bit "low-level" is that for trackdown we *really* don't want to
touch files that aren't modified, so that if "make" is part of the test it
won't have to recompile more than is absolutely necesary.

Take a look at the functions exported from PatchChoices.lhs, and ask
(perhaps on darcs-devel) if it's not clear.  You'd want to use
patch_choices_tps to generate your PatchChoices, so you'd have a set of
TaggedPatches with which to manipulate it.  For examples of using
PatchChoices you could look at PatchSelect or Record (which passes a
PatchChoices to PatchSelect).

I think if you rewrite TrackDown using PatchChoices, it ought to make it
simpler to implement alternate trackdown algorithms even if you didn't
implement the fancy ones in the paper.
-- 
David Roundy
http://www.darcs.net