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

[Nathaniel Smith]

On Mon, May 02, 2005 at 12:25:08PM +0200, Richard Levitte - VMS Whacker wrote:
> 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...

Err... so you propose that it's okay if we have a merge algorithm that
sometimes simply reverses people's changes, with no warning or reason,
because hey, they might have been a bad change?

I think we will have trouble selling that to users. :-)

> 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.

Trying to code tree rearrangement conflicts as textual conflicts
doesn't work; I spent a few weeks trying, when we were trying to
figure out how to do tree rearrangement in the first place.  You can
conflict on moves that have the same source, or you can conflict on
moves that have the same destination, but you can't detect both at
once... (and good luck with directories!)

I'm pretty sure the right UI to tree rearrangement conflicts is
merge-via-working-dir.

> 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.

This doesn't address the problem.  Everything you say here, we
effectively do; we do track renames, adds, report conflicts then they
conflict, etc.  The problem is that with a 3-way merge, there was no
way for monotone to even detect that those two files were actually the
same file.  It really was correct that relative to A, the changes
along the two edges were "add foo" and "add bar".  Changing how we
represent such merges won't help us, if we don't come up with a better
way to detect the problems in the first place.

-- Nathaniel

-- 
"...All of this suggests that if we wished to find a modern-day model
for British and American speech of the late eighteenth century, we could
probably do no better than Yosemite Sam."