[darcs-devel] darcs patch: Rewrite gcau, and add explanatory comment from David

David Roundy droundy at abridgegame.org
Sun Aug 28 04:10:46 PDT 2005


On Sun, Aug 28, 2005 at 12:03:33AM +0100, Ian Lynagh wrote:
> 
> Hi David,
> 
> How does this look?

It looks good to me.

> Also, I'm a bit confused; it's not necessarily true that the
> (fst $ last ps1) == (fst $ last ps2) test be when the lengths are equal,
> right? So we might miss it due to our length equalising if we are
> unlucky?

Right, I think the length-equalizing heuristic only works reliably if the
number of patches between tags exceeds the number of patches that could be
pulled/pushed/applied.  This is a very common case, but is certainly not
always true.

> Perhaps we should really be checking lasts each time we take a
> new patch set against all lasts on the other side we have seen?

Yes, that would make sense.  Unless you're likely to work that out soon,
I'd like to get this change into stable as soon as possible, since even the
current algorithm almost always works properly (or at least, properly
enough).

> And possibly biasing the search towards the non-network or less-partial
> repo (although partialness isn't a total order, I don't think)?

Right.  Even better would be to put in proper handling of partial
repositories--if we checked in gcau itself whether patches are available we
could dynamically adjust our algorithm to handle the two-partial-repository
case elegantly (i.e. if we run off the end of one partial repository, we'd
look deeper on the other side, and if there's a solution we could I think
be guaranteed to find it).  I think we'd just have to look at the "last"
patches occasionally to see if they're Nothing.

A slightly harder problem is patch bundles, which are different from true
partial repositories.  A partial repository has the entire inventory, but a
patch bundle doesn't.  But in the case of patch bundles, we're almost
always okay, because if the patch bundle was created with a push to the
repository we're applying to, gcau will always (?) work all right by
construction.

> Hmm, just realised my gcau_simple (cr ps1 ++ concat ps1s) (cr ps2)
> (and symmetric) case will be missing opportunities to do the test but
> aborting sending at this point is too much hassle  :-)

Ah, I see now.  I read the email and didn't understand this comment, then
read the code and didn't see this problem, but now it makes sense.  Yes,
using "f" again in those cases would definitely be good, as this situation
actually will happen, since patch bundles are always a single sequence, and
in that case we do need to keep looking for the tag that the patch bundle
starts with.

Do you want to amend this patch, or add another? In either case, I think
this can go into darcs-unstable now, and I'll pull it soon into
darcs-stable.
-- 
David Roundy
http://www.darcs.net




More information about the darcs-devel mailing list