[darcs-devel] Clarification about mergers

[David Roundy]

On Wed, May 11, 2005 at 04:21:27PM +0200, Juliusz Chroboczek wrote:
> Any chance you could explain what's the story behind 0.0, 0.1 and 0.9
> mergers?

Sure.  Originally, I thought that when there was a conflict I could come up
with a "default resolution", which would be uniquely defined, and would
usually correspond to what the user wants.  I hardly remember merger 0.1,
but relatively early on, I realized that this would be hard.  I now believe
that it's impossible, unless you severely limit the expressive power of
your patches--possibly to the point of forbidding renames.

The merger version flag was to indicate which resolution was used in the
merge.  Merger 0.9 was the best I got to, but it didn't result in a unique
resolution, so it had a tendancy to lead to conflicts.  At that stage I
went went back to what was originally a debugging version, merger 0.0,
which has the result of simply not applying any of the patches involved in
the conflict.  I now believe that this is (except perhaps in certain simple
corner cases) the only unique resolution of conflicts.

You can now remove merger 0.9 patches from a repository with darcs optimize
--modernize.

However, I still wanted some sort of marking, and one of the results of the
"smart resolution" work was to mark up conflict for the user.  When I
switched to using merger 0.0, I needed a way to mark up the conflict in the
working directory, and that's done essentially by converting the merger
0.0s to merger 0.9s (although there's also some commutation work involved).

> And if you have time, if you could explain conflictors to the unwashed
> mashes, the unwashed mashes would wash.  Or something.

Conflictors are a new way of representing what merger 0.0 ought to be.
They should be more efficient and simpler, and much easier to debug.
Consider two branches, one has patches ABCDE, and the other has patch X,
which conflicts with all the above (leftmost patch applied first).  With
mergers--which I'll represent as (A,B), you'd get a merge which looks
something like like

ABCDE(E,(D,(C,(B,(A,X)))))

where the last is a highly nested merger.  The conflictor (using an older
and more simple notation--we've been getting more sophisticated over on
darcs-conflicts) would look more like

ABCDE[ABCDE,X]

In this simple case, the two schemes look similar, but if we reordered the
patches so that the X came first (as must always be possible), the merger
picture would be very scary.

X(X,A)((A,X),B)((B,(A,X)),C)((C,(B,(A,X))),D)(D,(C,(B,(A,X))),E)

where there is a plenty of ambiguity regarding how the nested mergers will
show up--there are many equivalent ways of writing any given patch--and
it's not easy to enumerate all the equivalent representations, either.

In conflictors, this would be

X[X,A][X,AB][X,ABC][X,ABCD][X,ABCDE]

There still are equivalent representations, if ABCDE can commute with each
other at all, but it's very easy to enumerate the possible representations.

There are trickinesses that show up when you have different combinations of
patches only some of which conflict, or if you are handling a merge of
three parallel conflicting patches (or sequences of patches), which require
more thought, and that's what we're working out over on darcs-conflicts.

When this is done, we'll want a new framework for handling the marking of
conflicts, which should have features that have been discussed on
darcs-users, like keeping track of what conflicts are left unresolved in
your working directory, and avoiding conflicts with conflict markers.
-- 
David Roundy
http://www.darcs.net