I am at the moment just playing with monotone, but
after reading the e-mail below I started to think a little
bit about how to pick an ancestor for merging.
It is quite an interesting problem, and quite tricky because
for me it seems very hard to make precise what properties you
want for a merge ancestor for revisions l and r.
But I think the current algorithme as I understand it can
be improved.
So first lets introduce some concepts:
* The revisions form a DAG (directed acyclic graph) G,
for which the vertices V are the revisions.
* The DAG structure induce a partial ordering on the revision,
defined by:
r <= s iff r = s or there is a path from r to s in the
the revision graph.
* given a set of revisions S (subset of V)
Heads (S) = maximal elements of S for the partial order.
= { s in S | there is no t in S such that t != s and s <= t}
* given a revision r the ancestors are given by
An (r) = { s in V | s <= r }
* given a set of revisions S (subset of V) lets define D vertices
(related to the dominators) by:
D (S) = { s in S | for all x in S : x <= s or s <= x}
In other words, D(S) consists of the vertices that are comparable
to all the other vertices in S.
>From this it seems that:
LCA (l, r) = Heads ( An (l) intersect An (r))
the dominators of r are all the D points of the ancestors of r, or
in other words:
DOM (r) = D (An (r))
So the current algorithme is:
Nathaniel Smith <[EMAIL PROTECTED]> writes:
> To avoid this kind of problem, monotone currently uses the "LCA+DOM",
> or "lcad" ancestor selection algorithm -- it chooses the most recent
> revision that is a common ancestor of both nodes, and a dominator of
> one of them.
LCA+DOM (l, r) = Heads (An (l) intersect Dom (r))
or
Heads (Dom (l) intersect An (r))
> So, let's fix this.
>
> There are some different approaches to doing so:
> -- use a better ancestor selection algorithm:
> -- I'm pretty sure that "if there's a unique LCA, use it;
> otherwise, fall back to LCA+DOM" is a correct algorithm, and
> it should help a lot in the long-lived branches case, where
> propagates are reasonably rare.
This seems more complicated than needed.
I propose
Merge ancestor (l, r) = Heads (D (An (l) intersect An (r)))
Mathematical speaking this has a few advantages:
* Merge ancestor is either empty, or contains exactly one revision,
so it does not need a random choice anymore.
* It coincides with LCA if there is a unique LCA
* in all other cases this ancestor is >= LCA+DOM ancestor
(so it is further from the root of the tree, so closer
to the revisions to be merged).
* Also, the few cases I looked at, it seems that this
merge ancestor algorithm has the advantage that
if you have long lived parallel branches with
a topology that is bad for mergin you can
quite easily fix this by making a strategic merge.
> -- it is probably possible to do much better; I have some
> sketches on how one can calculate some kind of optimal safe
> merge ancestor. They are currently sketches.
I am very interested to hear about them.
> -- implement codeville-merge
I am interested to know how the codeville-merge works, but the codeville
site does not seem to have a lot of documentation of the algorithme ;-(
If the above is too cryptic, please let me know, I am happy to answer
questions, and as mentioned above, I just started thinking about this.
Oh, and if I am talking nonsense, please let me know :-)
Wim Oudshoorn.
_______________________________________________
Monotone-devel mailing list
Monotone-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/monotone-devel
