# [darcs-users] On merging

Anthony Towns aj at azure.humbug.org.au
Thu Nov 25 16:50:01 UTC 2004

```David Roundy wrote:
> The merge algorithms definitely need
> improvement when there are conflicts.  It's possible that there is no
> efficient solution, which would be very sad, but I'm still optimistic that
> I'll be able to figure out a more efficient way to do things.
>
> The current (inefficient) algorithms came about because originally I was
> overly ambitious, and when my original ideas turned out to be flawed, I
> went with an algorithm (based on the original one) which was safe and
> correct via a simple modification of the old algorithm.  Dealing with merge
> conflicts isn't easy, and for the last year I've been caught up fixing real
> bugs.

I'm trying to rewrite the patch theory in a way that I understand; and
I'm stuck on the merge part again. :-/

I guess the main thing I don't get is why when you have conflicts,
"darcs pull" leaves unrecorded changes (ie, "vvvv", "****", and "^^^^")
in the repo? Having patch X recorded, pulling patch Y that conflicts
with patch X, and then running "darcs revert" and having the resulting
repo not have either X or Y applied (let alone the merger stuff) seems
confusing too.

Oh well. Is it the case that Theorem Two (the "do some commutes and
inversions to work out the merged patch" one) applies except when there
are "conflicts"? Hrm.

Also, the patch theory says: "If either commute fails, this theorem does
not apply." -- I think you can simplify that to just say that the
theorem doesn't apply if P^{-1} and Q don't commute. FWIW, I find it
simpler to say:

P = p inverse
Q = q inverse

p and q both apply to repository r, ie p*r and q*r makes a valid
repository; r = P*p*r = Q*q*r, obviously.

q*r
= q*(P*p*r)
= (q*P)*p*r
= (P'*q')*p*r  (if q, P commute)

X = P' inverse
X*q*r = X*P'*q'*p*r
X*q*r = q'*p*r

Merged patches are X for p, and q' for q

Sorry for being a wimp and leaving in the context rather than just
working on patches against uncollapsed repositories :)

Anyway, that means it'll work as long as the _second_ commute succeeds.
No need for the "either". AFAICS, anyway?

What does "q and P doesn't commute" mean? Unless I'm missing something
it means q depends on P; which is to say q can't be applied until
something from p is undone. Which I think is the same as saying "q and p
conflict". (I really hope that's right, because it's beginning to be
comprehensible :)

Erm.

Okay, now I'm really confused. It seems like "X,MERGE(X,Y)" is the same
as "X,X^{-1}". Ah, it is the same if X and Y don't have mergers
themselves, but it's different if they do have mergers. I guess what
confuses me is the statement:

] The job of a merger is basically to undo the two conflicting patches,
] and then apply some sort of a ``resolution'' of the two instead.

when what it really seems to do is just undo the two conflicting
patches, and leave you to later apply a patch that includes both of them.

Hrm, except surely that doesn't work right? If I've got patches:

A2:	hunk ./foo 1
+ hello

then if I apply A1,B and get a conflict, and then apply A2, I get a
changelog that adds ./foo twice, changes it once, and end up without the
file in my repository at all?

I'm sceptical because I find that behaviour completely batty, which
usually means I'm missing something obvious and enlightening :)

(And I know I'm missing /something/ because I still don't see what
"unwinding" has to do with anything)

I guess I can't go much further with this without getting confident in
hax0ring Patch.lhs so I can do up prototypes :-/ Perl just doesn't seem
the ideal language for playing with commuting conflicting mergers...

Cheers,
aj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 155 bytes
Desc: OpenPGP digital signature
Url : http://lists.osuosl.org/pipermail/darcs-users/attachments/20041126/1c096362/attachment.pgp
```