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

Bram Cohen wrote:

>
>     a
>    /|
>   / |
>  b  |
>  |  |
>  c  b
>
> If you're convergent, the answer is c. If you aren't, you get a conflict.

I just realized why the scalar case seems to be different from the lines
in files case. With lines in files we're currently treating each line as
completely independent of the others, and as a result there are only two
values - present and not present. Therefore in the situation above we
probably have a, not present, b, present, and c, once again not present.
Since we only have two states we can't differentiate between a 'change'
and a 'revert'. If the deletion is part of a revert, then the add should
win. If it's part of a 'change', then the change should win.

Perhaps this is a good argument in favor of Nathan's suggestion of using
the preceding line information when doing merges. I'm no big fan of moving
lines, but there's an edge case which 3-way gets right and pcdv currently
gets wrong which could be fixed with that technique, and it would allow
one to tell if two lines appear next to each other which had in the past,
in which case everything which appeared between them was 'reverted',
otherwise it was 'changed'. It also might allow for the
both-ancestors-different-from-descendant case to not be treated as a
special kind of conflict, and even allow it to not be a conflict when it
shouldn't be. I think that case shouldn't be a conflict in the case of a
scalar, and the reason why it can be for pcdv is that pcdv is currently
ignoring too much information.

Of course, versioning preceding line information introduces a whole bunch
of new problems. But it's a promising road map which would have no wacky
special cased edge cases at the end. And for the time being we can
hopefully work out thoroughly how to version a scalar. I'm mostly
convinced now that convergence is a good idea, and thoroughly convinced
that implicit undo is a good idea, and I'm fairly sure that they can be
made to work together.

So now we have this rather involved mathematical problem of defining,
deriving, and proving correctness of a scalar merge algorithm which
supports both implicit undo and convergence. Should make a good paper :-)

-Bram