Re: The new Codeville merge algorithm

Nathaniel Smith wrote:

> Some useful context for this may be two recent messages on
> monotone-devel, where I lay out the known flaws in 3-way merge, and
> why I no longer believe it is an acceptable approach to merging in any
> but very restricted cases:
>   http://article.gmane.org/gmane.comp.version-control.monotone.devel/3256
>   http://article.gmane.org/gmane.comp.version-control.monotone.devel/3264
> Full thread:
>   http://thread.gmane.org/gmane.comp.version-control.monotone.devel/3240

A somewhat tangential point has to do with how files are identified.
Codeville simply has file and directory identifiers, and there's a (name,
parent) property of files which gets versioned with a single 'last
modified' stamp. Not having these seems to be aggravating your three way
merge problems.

A note about the whole rename thing - that information is still going to
be tracked with an old-school last modified stamp in the new Codeville
merge algorithm, but the behavior of that stamp may change a bit. The
problem comes when you have a coincidental match. This is a conflict as
far as history is concerned, but can't be escalated to the user, because
they can only fix it one way. The obvious way to fix this is to just pick
one. (That's how coincidental matches in code are handled - that will
probably get special cased). While reasonable, that approach would
sometimes give incorrect conflicts in this case -

P
|\
| \
A  A
| /|
|/ |
A  P
 \ |
  \|
   ?

What we're doing instead (and this may be a very small win, coincidental
matches on renames are a rare case) is that there's a list of ancestors in
the last modified, and if there's a coincidental match they get glommed
together. Another version is considered to beat the list if it contains
*anything* from within the list. This can cause an ambiguous clean merge
in the following case:

    P
   /\
  /  \
 /    \
A      B
|\    /|
| |  | |
B  \/  A
|  /\  |
| |  | |
|/    \|
B      A
 \    /
  \  /
   \/
    ?

In this case we present this as an ambiguous clean conflict to the user.
Picking an ancestor arbitrarily would pick A a quarter of the time, B a
quarter of the time, a regular conflict a quarter of the time, and an
ambiguous clean conflict a quarted of the time. That doesn't seem like
good behavior either. The most seeming coherent algorithm for this case
would be to use a list and require that an alternate name have *all* of
the last modifieds in its history to win. That would cause a lot of
seemingly unnecessary merges in the first example case above though.

-Bram