Re: [Monotone-devel] Re: 3-way merge considered harmful

[Nathaniel Smith]

On Sun, May 01, 2005 at 06:51:54PM +0200, Florian Weimer wrote:
> * Nathaniel Smith:
> 
> > Fortunately, it seems like codeville-merge is a viable replacement
> > here (it can be applied to both content merges and tree rearrangement
> > merges), and with some recent improvements that Bram and some other
> > people (including me) have been playing with, it may (I'm not sure
> > yet) be strictly more powerful than 3-way merge.
> 
> Is there some formal model of codeville-merge which one could check?

We're working on figuring out whether it has some formal properties,
actually, like "equivalent to 3-way merge in the cases where 3-way
merge is the right thing to do", "clean merges are order invariant",
etc.

> I should admit that I believe in what could be called a pessmistic
> theory of merging.  Say you have two trees T_1, T_2 (with their
> respective histories), some merge operator M, and a tree invariant I
> such that both I(T_1) and I(T_2) hold.  What you really want is that
> M(T_1, T_2) either fails, or yields a merged tree T_12 such that
> I(T_12) holds.  Obviously, this is impossible unless I is known to M
> and is explicitly checked by M (for example, it might be test case).

Choosing a good I is non-obvious, unfortunately :-).

> Now back to your example.  Source files contain lots of redunancy.
> Often, it's possible to make a particular change in different ways,
> and with truly distributed development, this isn't entirely unlikely
> to happen.  The redundancy means that the changes won't necessarily
> conflict in the sense of codeville-merge, and you still end up with
> the same situation you described (a zombie changeset which is
> resurrected from the dead).

Yes, it's possible for two people to make redundant changes.  This is
one reason why it's impossible define a merge algorithm that works for
all the various I's one might like.  Given that, then, the
responsibility of a merge algorithm is to fail in ways that make
sense, so the user can have some conceptual model of what the system
is doing and how to correct for its failings.

So, for instance, nobody is surprised that, if we write two patches
that have the "same purpose", if they modify two different files then
they will be merged together cleanly, and someone will have to clean
up by hand.  This is pretty different from the zombie changeset case,
though; here someone's already done some work by hand, and now here
comes the VCS silently undoing that work.  Not so cool.

> In other worse, unless codeville-merge needs comparable resources to
> the current approach, it might not be worth it.  I also fear that it
> introduces spurious conflicts when several developers apply the same
> diff to their development lines.

Codeville-merge probably will need more resources, at least at first
(there are a lot of optimizations that can be done, but the first pass
won't have them...).  OTOH, there are a lot of practical benefits to
codeville-merge, even aside from the terrible edge cases above; cf.
the discussion that spawned this thread, about spurious conflicts.
We're talking about trading off computer time versus human time; the
conversion rate there is pretty steep -- you don't have to save much
human time for this to be worth it :-).

-- Nathaniel

-- 
.i dei jitfa fanmo xatra