[Monotone-devel] Introduction; multihead merge heuristic

[Zack Weinberg]

Hello folks,

I'm the mysterious fourth SoC student who hasn't said anything up to
now (because classes only ended two weeks ago and then I had to move).
I'm doing workspace merge and other merge- and approval-related
projects as they come up.

Nathaniel suggested I start by implementing a simple heuristic for the
order in which to merge branch heads, when there's more than two: do
pairs with newer LCAs first.  Here's an example.

          oo
         /  \
        xx  ce
       /  \
      cx  xe

(Imagine that that's one file, and the label at each point in the tree
shows the content of the file at that point, except that the two
letters are on separate lines.)  Currently monotone does the merges in
no particular order; the heuristic says merge "cx" and "xe" first.
You can see that this merge goes cleanly if you do it in that order,
but produces a conflict if you do it any other way.

This example is contrived, but the heuristic should help with real
cases where you have just a little divergence at the tip of one
sub-branch, plus another, rather longer-lived sub-branch with more
changes on it.  You wouldn't want to have to merge all the changes
from the long sub-branch twice.

The code (it was quite short and easy to write) is available from
venge.net in branch net.venge.monotone.multihead.  I'd appreciate
review particularly of:

1) Whether I screwed up in any way with the STL data structures in
cmd_merging.cc.  I'm used to C and having to do all the memory
management myself, or else to Python and not having to worry about it
at all.

2) The heuristic falls back to the old way of doing things for many
cases, such as

  a
 /|\
bcd

and

a b
|X|
c d

-- advice on how to extend it for these and other more elaborate cases
would be welcome.

3) More test cases - currently there is only one, and it's pretty primitive.

Thanks,
zw

p.s. Anyone know how to persuade gmail to use a monospace font for
messages and composition windows?  There is no obvious setting for
this.