[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:

A1:	addfile ./foo

A2:	hunk ./foo 1
	+ hello

B:	addfile ./foo

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 


More information about the darcs-users mailing list