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

[Richard Levitte - VMS Whacker]

In message <address@hidden> on Sun, 1 May 2005 00:29:48 -0700, Nathaniel Smith 
<address@hidden> said:

njs> Here's another pathological case for 3-way merge:
njs>    A
njs>    |
njs>    B
njs>   / \
njs>  C   D
njs> Suppose that a file was added on the A->B edge, and then removed again
njs> in B->C, while it was left alone on the B->D edge.  We want to merge
njs> C and D.  Let's assume that for some reason we decide to use A as a
njs> common ancestor.  What will happen?  Our file does not exist in either
njs> A or C, so when comparing A and C 3-way merge will think that nothing
njs> has happened.  Our file _does_ exist in D, though, so when comparing A
njs> and D, 3-way merge will decide that a file has been added.  Therefore,
njs> says 3-way merge, this file should exist in the new merged node.
njs> But, this is obviously wrong; the file was deleted between B and C,
njs> and this delete should have caused a delete of D's copy as well.

I disagree with that conclusion.  It's quite possible the removal of
the file in the B->C edge is a mistake, and that the person leaving it
along in the B->D edge had it right.  Especially in a fairly loose
network of cooperating programmers, disagreements of that kind are
bound to happen (and have happened).  Others might call them "oopses"
rather than disagreements...

njs> When we discovered this a while ago, we sort of scratched our heads,
njs> tossed around some ideas about "per-hunk ancestor selection" and
njs> such, and shrugged and ignored it for a while.  Richard just
njs> discovered a related problem that is harder to ignore.  Take the same
njs> graph as above, and suppose that instead of being deleted in C, our
njs> file was _renamed_ in C.  Now, when we go to merge, the A->C changeset
njs> says file "foo" was added, the A->D changeset says file "bar" was
njs> added, and there is no way to tell that these files are really the
njs> same file, so they are both added.  Now we have a single logical file
njs> that exists twice in the same tree.

Bottom line is, we don't keep a very good track on file movement in
some cases.  Well, actually, we keep good track of file addition, just
not as good track of file deletion or renames...

The most obvious solution would really be to have those file
movements codified during a merge into a file similar to "MT/work",
and which can suffer from conflicts if needed.  That file would be the
first to have to be resolved, and the results from it would be applied
immediately in some way, before any other change is applied.

Doing so would at least make sure we don't end up in these weird
situations with one conceptual file being duplicated into several
physical ones, by keeping god track of what happens with the files.

This constructed "work file" could also be made to have conflicts as
soon as any file movement differs, for good measure.  That would force
the decision between differing file movements back into the hands of
the programmers, and do it in a way that still fits the 3-way merge
model, if I understand it correctly.  The programmer would have to
choose between removing the file (B->C file movement) or keeping it
(B->D lack of file movement) in the first example.  The programmer
would have to choose between renaming the file (B->C) or keep the same
name (B->D) in the second example.

Comments?

Cheers,
Richard

-- 
Richard Levitte                         address@hidden
                                        http://richard.levitte.org/

"When I became a man I put away childish things, including
 the fear of childishness and the desire to be very grown up."
                                                -- C.S. Lewis