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

On Sat, Aug 06, 2005 at 11:15:03PM -0700, Nathaniel Smith wrote:
> (One horrible idea I had, suitable for scaring small children who are
> interested in merge algorithms: since it seem like trees may actually
> be _easier_ to merge than text, by passing to the representation
> of nodes-and-pointers-to-parents and then applying a nice scalar merge
> algorithm, why not apply the same trick to the linear ordering
> structure that makes up text?  Model each line as a (text, pointer to
> preceding line) pair, and merge on those.
> 
> The horrible thing about this is that it allows for arbitrary
> _movement_ of text.  Fun!)

Damn, you're forcing my hand on this one. I've already run an idea of how to
support restricted moves by Bram and he didn't poke any holes in it.

As Bram already pointed out, resolution becomes more difficult with arbitrary
moves. You have only specific a way of representing the location of a line
which can be versioned itself. The other big problem I'm aware of is figuring
out when a conflict occurs. Remember that in textual merging conflicts are
using guesswork (ok, every merge method uses guesswork since we can't read
users minds to determine intent) based on context. What constitutes context
in this case is really unclear, it will have to involve the historical ones
as well as current when doing merges.

Now for my idea for handling a restricted set of line moves. Start with
precise codeville merge, which appears to be reasonably complete but still
needs some field testing for sanities sake. As has been pointed out, one of
the problems with pcdv merge is the imposed global ordering. There is an
obvious partial ordering which can be done (which is not to say that it's
easy to implement, just that the idea is obvious) which is nice because it
gives a few less conflicts in a few places.

As I've been thinking about partial ordering in the past, it largely didn't
seem worth the effort involved for the cases it can handle cleanly. However,
a new case occurred to me. What if we define the partial ordering on the
entire tree instead of just a single file? Lines within different files
will not be ordered relative to each other. At least, not until someone
moves data between them.

With this scheme, we have a consistent and fixed context despite supporting
data moving between different files. Resolution is made easier since it has
an ordering within which to work, as well.

Supporting moves between files is quite useful in that a lot of refactoring
makes use of this. Someone doing major plumbing work off on a branch would
be saved a lot of pain in merging. You could also attempt to generalize
the partial ordering to support arbitrary moves, although that should really
wait until we understand what's involved in the more modest proposal.

Ross