ambiguous clean (was Re: [Monotone-devel] Re: [cdv-devel] more merging stuff (bit long...))

[Nathaniel Smith]

On Sun, Aug 07, 2005 at 02:03:19PM -0400, Ross Cohen wrote:
> > Here *(b) is an ancestor of c, *(c) is an ancestor of b; you lose.
> > 
> > It's exactly that I mark the conflict resolutions as changed, that
> > eliminates ambiguous clean merge.
> 
> Merging of the last c and c in this case gives a conflict, just as your
> suggested algorithm does.
> 
> > (ambiguous clean merge is sufficiently annoying that I feel like I'm
> > using too weak a verb there.  "annihilates"?  "obliterates"?
> > 
> > maybe I'm taking this too personally.)
> 
> I think you are. As should already be obvious, I don't consider the negative
> conflict of the ambiguous case to be less valid than the affirmative conflict
> mode which you are attempting to force everything into.

Hmm.  I believe I disagree, on two counts.

The first problem with ambiguous clean merge (or "negative
conflict"?) is that it leads to a particular sort of objectionable
behavior:

    a
   / \
  b   c
  |\ /|
  | X |
  |/ \|
  b   c
  |\ /
  | c   <-- ambiguous clean merge
  | |
  b |
  \ /
   ?    <-- another ambiguous clean merge!

This is quite different from an ordinary conflict, which when resolved
should stay resolved.  In the worst case, this can generate
arbitrarily many spurious conflicts, as people keep working on
branches, making changes completely unrelated to this but repeatedly
resolving anyway, until eventually every revision is a descendent of
the original resolution node.  Unless someone somewhere resolves the
conflict the other way, in which case it starts all over again...

This is an unnecessarily apocalyptic view of it all, but it just
doesn't seem like the sort of property one looks for in a merge
algorithm.

The other reason I dislike ambiguous clean merge is a little more
theoretical.  It's not just this the one misbehavior I describe above;
it's that I fundamentally don't have any way to understand what's
going on.  By the semantics I thought we were ascribing to the
various parts of the merge algorithm, it means "both sides lose" --
and I don't have any way to interpret that.  This makes me distrustful
of the whole thing -- if I can't systematically understand its
behavior, how do I know that it will always behave sensibly?

> In addition, your proofs are nice, they demonstrate we understand the
> behaviour of a very specific case. However, they are about an algorithm which
> gets some common cases wrong. While your objection to designing around a
> bunch of test cases is understandable, the test cases are still a necessary
> condition for acceptance.

Right, of course they are, and I certainly wouldn't suggest anyone use
a merge algorithm based only on proofs!  So far I'm pleasantly
surprised at how well it's held up, though; the "common cases" you
refer to seem to me to be less objectionable than the strange
ambiguous clean cases.  It gives the occasional avoidable conflict,
but resolving the conflict is straightforward.  The basic difference
to traditional cdv-merge is that traditional cdv-merge infers _no_
intention from merges; I prefer conservatively inferring a bit more
than most user's intuitions say...

So, at this moment, I personally consider this to be the best
algorithm for this that we have.

On the other hand, it was partly an exercise in seeing if it was
possible to make something that rigorous at _all_, and has the
simplest possible user model I could think of.  So I definitely agree
there's room for improvement!

-- Nathaniel

-- 
Details are all that matters; God dwells there, and you never get to
see Him if you don't struggle to get them right. -- Stephen Jay Gould