[darcs-devel] darcs patch: simplify get_common_and_uncommon code, and make it laz...

[David Roundy]

Hi Ian,

Sorry about the delay, somehow I missed your response, and then I was on
vacation and was only reading new emails.

On Tue, Aug 09, 2005 at 02:42:46AM +0100, Ian Lynagh wrote:
> On Sun, Aug 07, 2005 at 09:22:40AM -0400, David Roundy wrote:
> > Hi Ian and others,
> > 
> > I'd appreciate if you'd take a careful look at this patch.  I think I
> > didn't change the behavior of the code (except making it lazier), but this
> > is the sort of code in which one can make changes that work fine until some
> > rare repository comes along and suddenly they cause corruption.
> 
> I'm not sure the behaviour is going to be the same if you have inputs
> like
> 
>     gcau ([[x], [y]], [[z]])
> 
> but if not, probably in ways that don't matter. Before I think it
> through properly can you point me at a description of exactly what it's
> meant to do please? (it would be good to have one as a comment in the
> file, I think).

gcau determines a list of "common" patches and patches unique to each of
the two PatchSets.  The list of "common" patches only needs to include all
patches that are not interspersed with the "unique" patches, but including
more patches in the list of "common" patches doesn't really hurt, except
for efficiency considerations.  Mostly, we want to access as few elements
as possible of the PatchSet list, since those can be expensive (or
unavailable).

PatchSets have the property that if

(fst $ last $ head a) == (fst $ last $ head b)

then (tail a) and (tail b) are identical repositories, and we want to take
advantage of this if possible, to avoid reading too many inventories.  In
the case of --partial repositories or patch bundles, it is crucial that we
don't need to read the whole history, since it isn't available.

> I think it can probably be written more clearly using irrefutable
> patterns. I'd guess the length comparison bit could/should be written
> more symmetrically with a compare, too.

More symmetrically may not be desirable, since we want to touch as few
elements as possible when examining the lists, even if that breaks
symmetry.  But I'm certainly open to clearer implementations...
-- 
David Roundy
http://www.darcs.net