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

List:       darcs-conflicts
Subject:    Re: [darcs-conflicts] a simple (possibly naive) approach to merge
From:       Marnix Klooster <marnix.klooster () gmail ! com>
Date:       2005-09-14 16:04:43
Message-ID: 43284A1B.10908 () gmail ! com
[Download RAW message or body]

Hi Zooko,

You wrote to darcs-conflicts:

>Honestly, I do not yet understand the formalisms that you guys are working
>with, so my suggestion might be naive.  However:
>
>It seems to me that good handling of merge conflicts might be as per the
>following example.  Suppose there is a file with five lines, which I will
>denote "ABCDE".  Suppose there is a patch P1 which changes the 3rd line from
>"C" to "X", and a different patch P2 which changes the 3rd line from "C" to
>"Y".
>
>Then if there is a repo which contains both patches, the file in that repo
>should look like:
>
>A
>B
>v v v v v v v
>X
>*************
>Y
>^ ^ ^ ^ ^ ^ ^
>D
>E
>
>
>This darcs already does.  Now the simple approach that I'm thinking about is
>that this is considered to be a clean merge -- no user intervention is
>required.  Obviously for usability reasons the user wants to be informed about
>the presence of these, but from a patch theory perspective, this is just a
>normal merge with the following caveat:
>
>Any subsequent patch which touches one of the "v", "*", or "^" marker depends
>upon both P1 and P2, while any patch which touches only the X line depends
>solely on patch P1, and any patch which touches only the Y line depends solely
>on patch P2.
>
>
>It appears to me that this is simple to understand and to implement, and that
>it has desirable consequences, such as:
>
>If I have a merge conflict like the one shown above in my repo, and then I pull
>a patch from someone who had the same conflict and who then resolved it (by
>editing her file, removing the marker lines, and rewriting the X/Y lines to her
>liking), then I will have her resolution patch (which depends on both P1 and
>P2) and no remaining evidence of conflict in my repo.
>  
>

I've been thinking along these lines as well.  In any case, the formal 
goal that David is working towards, is to make sure that every merge has 
one single well-defined result, so that whoever puts the same patches 
into a repository, always gets exactly the same tree.

The basic idea of the darcs-conflicts work has been to let the merges of 
two conflicting patches have no effect.  For example, if P1 and P2 both 
modify the first line of a file, then having both patches in your repo 
means that that line remains unmodified.  (And there should of course be 
some way to find out that these patches were 'ignored' because of a 
conflict.)

Your idea, if I understand it correctly, is instead to let the result be 
conflict markers in the file.

I've been briefly thinking about that some time ago.  There are of 
course difficulties.  For example, you need to make sure that the parts 
that conflict are always in the same order, to guarantee a unique 
result.  (Or you need to specify an equivalence relation on trees: two 
repos with the same patches are unique modulo conflict order.)  And you 
need probably also the 'original' part of the file, before the 
modification.  (Suppose one patch deletes line A, and the other replaces 
it by B.  Then I'd like to see A, empty, and B in the resulting file.)  
And you need to do something with directory conflicts: what if one patch 
renames file K to L, and another creates a file L, and a third one 
deletes file K?  What will then be the names of the resulting files?  
Something else: if one patch modifies lines 5-15, and the other lines 
10-20, and a third 13-22, how should the conflict markers be placed?

So there are lots of details.  But it's definitely doable, in my view.  
It just takes time and patience.

And I agree your remark in another recent e-mail:

>It is my belief that
>no merge algorithm should be widely used by software engineers unless it can be
>widely understood by software engineers, and darcs patch theory currently fails
>that test.
>

W.r.t. merging, this implies that we need to have some spec that details 
exactly what the result of a merge is, so that we can verify it, and 
implement it in different pieces of software and get the same result.

Which means formalism, I'm afraid.

Groetjes,
 <><
Marnix

_______________________________________________
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]