[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Monotone-devel] Re: test mail
From: |
graydon hoare |
Subject: |
[Monotone-devel] Re: test mail |
Date: |
Mon, 02 Feb 2004 17:26:50 -0500 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6b) Gecko/20031205 Thunderbird/0.4 |
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