[prev in list] [next in list] [prev in thread] [next in thread] 

List:       darcs-conflicts
Subject:    [darcs-conflicts] three-way merge
From:       David Roundy <droundy () home ! abridgegame ! org>
Date:       2005-05-07 13:17:35
Message-ID: 20050507131731.GA19664 () abridgegame ! org
[Download RAW message or body]

Yesterday I implemented a three-way merge algorithm in the conflictors
code, and I wanted to write it up before I go on to track down the bug in
three-way merges of the existing merger code that I found this morning.

The code is pretty straightforward (for conflictor commutation code), and
pretty limited right now.  In the process of writing it, I found a number
of bugs in the conflictor code, which were based on a misunderstanding of
what all_head_permutations actually does, which was a Good Thing.

So with no further ado, the commute_multiway function you can check out in
the darcs-conflicts repository handles a simple three-way conflict, and
nothing more.  For that reason the code is moderately simple (although it
still took me quite a while to write), and is moderately easy to test.  It
handles the case of A+B+C where all three patches mutually conflict.

We could do the merge in more than one order, so we could (for example)
have the following two parallel sequences

A[A;,B]
A[A;,C]

In which case we'd want to find

[A;,B] + [A;,C]

or any merge you could get by permuting A, B and C.

I decided that the final result should be

A+B+C => A [A;,B] [A[A;,B];,C]

Once this choice is made (basically, I decided that the patch X in [_;_,X]
must not itself be a conflictor), the rest is patch algebra.  In this case,
we know that

[A;,B][A[A;,B];,C] <-> [A;,C][A[A;,C];,B]

by the properties of a merge.  We can then use the "merge" or "juggle"
property to show that

[A[A;,B];,C]inv([A[A;,C];,B]) <-> inv([A;,C])[A;,B]

and of course we have the results of inverting both sides of these
commutes.

Then the job comes down to recognizing these scenarios and doing the right
thing.  The trick will be figuring out how to deal with more complex
scenarios, where we've got potentially long sequences of patches inside the
conflictor.

The code I wrote wasn't *entirely* on the assumption of a purely three-way
conflictor, since I did use some instances of head_patches, etc, which
should generalize to longer lists, but it's entirely untested on anything
else.  Hopefully we can figure out an algorithm that'll in a
straightforward manner deal with all the special cases, without writing
special-case code.

Of to debug mergers... (grrr!!!)
-- 
David Roundy
http://www.darcs.net

_______________________________________________
darcs-conflicts mailing list
darcs-conflicts@darcs.net
http://www.abridgegame.org/cgi-bin/mailman/listinfo/darcs-conflicts
[prev in list] [next in list] [prev in thread] [next in thread]