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

Bram Cohen wrote:

> The new codeville merge code I linked to recently contains code for doing
> implicit undo on a single binary value (whether a line is included or
> not). I *think* that approach can be generalized to scalar values by
> running it over a tree multiple times for each value which has ever
> occured, with the two values set to a/not a, b/not b, etc. If there's only
> one value which should be present, it's set to that value, if there are
> multiple ones, you have a conflict. I *think* it's impossible to have no
> values set, but that's an open conjecture.

Here's an example. Let's take one problematic case:

  a
 / \
d   b
 \ / \
  b   c

Now we have to run over this in four cases: a/not a, b/not b, c/not c, and
d/not d. I'll use # to indicate 'not'. Here are the four cases:

  a
 / \
#   #
 \ / \
  #   #

Clearly a loses.

  #
 / \
#   b
 \ / \
  b   #

In this case the lower b was a clean merge, because the upper # had
already gotten overridden by the upper b. Therefore the lower b loses to
the override effect of the lower right #, so the overall result is # and b
loses.

  #
 / \
#   #
 \ / \
  #   c

Obviously c wins.

  #
 / \
d   #
 \ / \
  #   #

And clearly d loses.

Hopefully that clarifies the notion of doing a multi-valued merge as a set
of binary merges.

By the way, the merge code is at http://bitconjurer.org/merge.py and the
part which does two-valued merges is LivingStatus. Probably the easiest
way to understand my proposal is to simply read the code for it. (You can
ignore the rest of that file other than LivingStatus for now.)

The neat trick with merging binary values is that you can never have a
conflict - if one side changes then it wins, if both side changes you have
a coincidental merge, but there's no such concept as having parallel
changes to two different values.

-Bram