[darcs-users] On merging

David Roundy droundy at abridgegame.org
Sat Nov 27 14:55:05 UTC 2004

On Sat, Nov 27, 2004 at 01:57:03PM +1000, Anthony Towns wrote:
> Anthony Towns wrote:
> >So applying X, inv(X), then Y isn't the same as just applying Y if X and 
> >Y conflict. Surely /that/ has to be a bug? Please? :)
> I wonder if this would be more appropriate for a darcs-theory list, or if
> I should be using my blog, or darcs-devel, or something, but anyway...

Perhaps darcs-devel, but probably -users is fine, since quite a few users
are interested in the theory behind darcs.

> So, here's my theory: if merge always works, commutation can always work
> too.

This was the idea I tried out recently and found not to work.  It would be
a very nice system, except that you'd have to deal with patch commutation
sometimes creating "conflicts", which would be annoying.  The trouble is
that it can't be done in a consistent and useful manner.

Currently, we have the sad state that sometimes

ABB^-1 <-> B'B'^-1A' where A' differs from A.

This happens when there are mergers involved, and it is a rather annoying

(I have my notes from working on this still sitting on my desk, so I'll
summarize the results here.  Unfortunately, I neglected to number the
pages, so it's a but confusing trying to follow the logic.)

The problem is that if you assume a result for a normally non-commuting

AB <-> X(A,B)Y(A,B)

where X and Y are unknown functions, one can show (by considering the
commutation of B^-1A^-1) that

Y(A,B) == X(A^-1,B^-1)^-1

After a few more steps (a page or two of my large writing) involving the
assumption that commuting a patch A by BB^-1 doesn't change it, and that
there is a unique result to a given merge operation, you can show that

X(A,B^-1) == X(B^-1,A)

which doesn't make any sense.  This means that the assumptions were
incompatible.  :(

> My hypothesis: having commutes work like that would be horrible, 
> confusing and bad, therefore having merges work like that must be 
> horrible, confusing and bad too!

The difference is that until resolved, a repository with conflicts in it is
by definiteion in a horrible, confusing, bad state...

> I wonder if you could make darcs still be useful if you forbade pulling 
> conflicting patches in the same way you can't commute dependant patches; 
> then you could only pull something that did an "addfile ./foo" if you'd 
> already mv'ed your ./foo out of the way, eg. The trick would come in 
> dealing with pulling something that did "addfile ./foo; ........; 
> rmfile/mv ./foo". Although maybe it'd be best just to disallow that too; 
> unless it was "bundled up" into a single patch that you'd deal with 
> atomically. Dealing with hunk-conflicts would obviously need thought 
> (and automation) too.

This would definitely be very bad.  Conflicts are very easy to create, and
"pre-fixing" the conflicts as you suggest isn't possible unless you do
something funky with the commutation rules.

I think the real solution to the merge conflict issue is two-fold.  We need
to keep track of merge conflicts in some more coherent manner than we
currently do, so that you don't see conflicts with conflict markers.  This
means maintaining something like pending which indicates which conflicts
are currently marked.  Then we need to make the UI display and handle
conflicts more nicely.  And of course, improving the conflict marking to
include dealing with problems such as the commonly-quoted "two files with
the same name" problem.
David Roundy http://www.darcs.net
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.osuosl.org/pipermail/darcs-users/attachments/20041127/ef2fb01f/attachment.pgp 

More information about the darcs-users mailing list