[Monotone-devel] Re: test mail

[graydon hoare]

address@hidden wrote:

> Is there more details on the merging algorithm that the faq refers too ?

hm, not an awful lot outside of reading the code (diff_patch.cc, 
patch_set.cc, and cert.cc). those are pretty dense, so I can give a 
rundown here:

1 - given 2 unmerged leaves in the manifest ancestry graph, work out
    which "common ancestor" to merge them via. this is more subtle than
    it sounds. at the moment this is done by computing the dominators
    and ancestor sets of both leaves using some iterative bitsets, and
    picking the first ancestor of A which is a dominator of B, or
    vice-versa, whichever happens first.

2 - compute the change sets which occurred along the edges from parent
    -> A and parent -> B. call these edges "left" and "right". this is
    also more subtle than it sounds because we need to look at all the
    rename certs which happen to show up along the edges and concatenate
    the rename history implied by them, to catch things which are not
    trivial renames (same file id removed from one path and added to
    another in the same changeset)

3 - perform setwise conflict detection on the change sets. for each
    delta, delete, add or move, check that there are no conflicting
    deletes, deltas, adds or moves. split move+edit changes into a move
    followed by an edit on the target. if any irreconcilable changes
    happen here, fail. otherwise collect a merged set of tree layout
    changes and deltas-to-be-merged. at some point in the future I'd
    like to put a hook for calling a tree-layout-conflict resolver
    from the user. they're infrequent, but when they happen right now
    we just fail.

4 - merge the deltas. this involves dropping down to the file level and
    computing an edit list for each file on the left and right edges,
    line-wise, then converting the edit lists to vectors of extents
    which map coordinates from the ancestor into left and right
    coordinates, normalizing the extent vectors, and merging them.
    this aims to do exactly the same thing "diff3 --merge" does. if
    it fails, this *does* call a lua hook to get the user to help,
    which typically calls ediff (or my current preference xxdiff).

these steps have seen quite a bit of churn over the past 8 months, so 
there's actually a certain amount of dead code in there right now. I 
mean to clean it up someday, but it's been quite a task merely finding 
algorithms which seemed to do the right thing. tromey keeps finding 
testcases which break my existing algorithms :)

the goal of all this is a "whole-tree" 3-way merge against the last 
"natural" state of affairs common to both trees. this differs somewhat 
from the arch approach (concatenate 2 history logs in one of two 
dominating orders) or the darcs approach (commute history elements until 
each edge has the same partial order). I'm not going to claim any one is 
generically "best", but I think monotone's style feels reasonably smooth 
in practise.

-graydon