[cdv-devel] Supporting convergence

I've been haggling over the following case, and concluded that it produces
a real problem:

  a
 / \
|   b
|   |
b   a

The problem is that there are two possible things which the user who
changed back to a could mean - either 'pretend that change was never
applied to this branch' or 'that change was a bad idea and should be
forgotten globally'. There is no single right answer, so what you really
want is a conflict.

Since in this case the problem is a collision between the implications of
implicit undo and convergence, I decided to work out how to support
convergence with no implicit undo at all.

It turns out that the answer is quite simple. A scalar is treated as a
bunch of separate binary variables, for each value which has appeared, and
versioned independently (and if an amount other than 1 of them is set to
on you have a conflict). Each of those variable is versioned by giving it
a single numerical value. All variables start with 0. When the variable is
set to on the value changes to 1. When it's set off again the value
changes to 2. From there on each time the variable is changed the value is
incremented by one. When two values are merged together, the greater one
wins.

This technique is very much like how line versioning was done originally,
only back then once a value got to 2 it stayed there permanently, never
increasing to 3. It seems like way to simple a trick to magically do
implicit cherry-pick interpretation, but on paper it seems to work, and
I'll have to test it (a modest alteration to the reference code I posted
before, just rewriting LivingStatus, will do it).

There are limitations to this approach. For one thing, if you cherry-pick
the changes from value 0 to value 5, that will be implicitly interpreted
as a change to value 1. Likewise if you cherry-pick from 0 to 4 that will
not even show up on the radar. And cherry-picking from 4 to 5 onto value 0
will result in 1, when it isn't even very clear what that should do.

Also, this approach doesn't support any implicit undo (duh, that's the
point of this exercise). I'll have to think more about the interactions
with implicit undo and how they should be handled. I don't think it's
terribly controversial to say that the following should merge clean:

  a
 / \
|   b
|   |
c   a

Or maybe it is. I dunno. Perhaps we'll wind up with a system which asks
users if particular hunks are undos or forward rewrites.

These are fairly substantive limitations. They appear intractable to
completely fix using only implicit information. In particular, a
cherry-pick from version 0 to 4 will produce no change in the code
whatsoever, and only affect later merging, so implicit inference clearly
can't support it.

That said, I'm a bit tacken aback at how simple this is. It couldn't be
*that* easy to support magic implicit cherry-picking, after all the time
we've spent haggling with it. The limitations I gave above are unlikely to
show up all that often in practice, and the benefits for a system which
does this are clearly useful, especially for a system like git which has
offline cherry-picks done constantly.

-Bram