[darcs-devel] Re: [darcs-users] On merging

[David Roundy]

On Wed, Dec 08, 2004 at 08:53:46PM +1000, Anthony Towns wrote:
> David Roundy wrote:
> >I'll answer the meat of your email later, but the exciting news is that
> >this morning as I lay in bed (well, actually on the floor, since I sleep on
> >the floor...) I think I solved the merge problem. [...]
> 
> >I still have to work out the details, but so far (I've filled a page of
> >large scribbles) it looks promising, both in terms of improving the speed
> >dramatically, and in terms of simplicity of code and algorithm.  Basically
> >the idea is to deal with sets of "unravelled" sequences rather than binary
> >recersive mergers, which eliminates the whole "unwind" step, and makes
> >understanding what is done much easier (since the unwind is what is so
> >confusing).  I don't expect I'm being comprehensible right now.  I still
> >need to work out the commutation with non-conflicting patches, but that
> >should be pretty much a straightforward excecise.  [...]
> 
> Any chance of an update on this? :)

There are a few more complexities that I had anticipated.  I hadn't yet
considered the case where there are three conflicting sequences of patches
but in an asymmetric way.  I still think that it'll work, but need a week
or so to work out the algorithms.  I've been meaning to work on this, but
just haven't had time.  :(

My hope is to work on this while I'm home for Christmas.  I think I'll
announce that I'm leaving darcs-users for a few weeks and just stop
responding to emails there.  I'll still read -devel, and still apply
patches, but hopefully I'll do no coding, except what may be required by
the conflict code.

The basic idea is to store the two conflicting sequences of patches, so if
(leftmost patch being first) I have two conflicting sequences:

ABC

abc

then the merge would result in (rotated 90 degrees)

A
B
C
[ABC
 a]
[ABC
 ab]
[ABC
 abc]

where the things in brackets are the new patch type tentatively named
"conflictors".

This is the easy case.  The question is what happens when I merge the above
with a sequence

123

where 1 and 2 don't conflict with ABC or a, but do conflict with bc.  I'm
not sure how this would work out.  I just need to sit down for a few hours
a few days in a row working out commutations, and I think it'll become
clear.

It hasn't helped that the sun is coming up really late nowadays, which
results in me waking up really late.  :(
-- 
David Roundy
http://www.darcs.net