[darcs-devel] Requirements for merging

[Anthony Towns]

David Roundy wrote:
> On Sun, Dec 12 2004 at 02:51:04PM +1000, Anthony Towns wrote:
>>[...]
>>Do those sound reasonable? I'm trying to go from darcs-agnostic first 
>>principle's sort of approach. Should there be more, or is there a better 
>>way of describing them?
> Yes.

Sweet :)

(Assuming the "Yes" is to the "reasonable?" not the "is there a better 
way?" :)

>>darcs gets (b) mostly right -- it's fine for conflicting hunks, and 
>>conflicting addfile/moves, but breaks down for conflicting 
>>addfile/addfiles. Having pretty GUI tools like Bitkeeper does would be 
>>even better, of course.
>>darcs gets (c) completely right for non-conflicting merges, but 
>>completely wrong for conflicting merges.
> Sounds about right.  Both (b) and (c) can be fixed without affecting
> backwards-compatibility, since they're both a case of marking conflicts
> and/or auto-resolving conflicts, both of which processes involve the
> creation of a new patch (within the darcs framework), so there are no
> backwards compatibility issues.

I've thought about this for a little while now, but I don't see how this 
can be right. For (b), sure: you can replace all the discarded changes 
into the working directory without touching the stuff in _darcs. You can 
make that as whacky and personalised as you like, and it won't ever make 
any difference to anyone else. [0]

I don't see how you can possibly solve (c) with just a new patch though. 
The problem is you've got a conflict between A and B, and you want to 
pull in a patch A' which depends on A. But once you've got "M(B,A); A; 
R", there's no patch C you can add that'll make that happen without a 
conflict [1]. (Assuming A and B are atomic patches of course, and that 
A' conflicts with M(B,A)) And while you could change the way 
merging/commutation works so that you don't generate a M(A',M(B,A)) 
patch in future, that'll then mean people who're using old versions of 
darcs will get a different result when doing the same thing (which 
breaks (a), and is unacceptable afaics?).

I thought that maybe you might mean "creation of a new patch /type/", 
but surely that would create backwards compatibility issues?

So, I'm a bit lost. :(

I'm kind of enamoured of the idea of creating a new patch type that can 
be used as a marker for smarter merger/commutation behaviour, but it'd 
be way cooler of you could solve (c) without breaking backwards compat 
at all. I just don't see how...

On the upside, I seem to have written a patch parser in "parsec" that 
comes pretty close to working; which almost means having a formal 
grammar for darcs patches. Yay :)

I have this horrible feeling that in trying to grok patch theory, I'm 
going to end up completely reimplementing darcs, but, oh well... :)

Cheers,
aj

[0] The only reason to break compatibility for (b), would be if you had,
     say, conflicting addfiles, each with a bunch of dependent hunks,
     then you could create some new patch type that doesn't delete the
     files, so that the resolution patch would only need to do some
     "move" patches, rather than including the entire contents of both
     files. But that's an optimisation issue more than a functionality
     issue.

[1] Proof: R1 = A,R. R2 = B,R. R1' = X,A,R.
     R3 = Push R2 -> R1 = M(A,B),A,R
     R3' = Push R1' -> R3 = M(M(A,B),X),M(A,B),A,R

     R4 = C,M(A,B),A,R where C is a "resolving" patch, such that:
     R4' = Push R1' -> R4 = X',C,M(A,B),A,R
     and X' doesn't create a conflict.

     The darcs distributive property gives us:

     R4' = Push R4 -> R3' = C',M(M(A,B),X),M(A,B),A,R

     So C',M(M(A,B),X) commutes to X',C. By assumption, X' doesn't create
     a conflict, but we see that X' and C commute to create at least one
     patch with a conflict. Therefore C must be a "merger" or "regrem"
     patch, since non-Merger patches never commute to create a merger.

     Hrm, actually, I'm stuck. A possible value for C ought to be
     M(A,B)^-1, or maybe M(M(B,A),B^-1), which should be the same
     thing. That's not a very useful value, but I can't think how to
     eliminate any others without going through Patch.lhs exhaustively.
     :(

     Still, while trying to do this, I managed to see what unwinds were
     all about, so that's cool!

     (Although, following true_unwind down is scary. Easy to see how
     these things get slow and painful. What's the bet I end up
     reimplementing that while I'm trying to understand how the existing
     things works? :)