Hi,
William Uther wrote:
o
/ \
a b
/ \ / \
c d e
\ | /
\ | /
f
Let's check for merging c and d: common ancestors are: o and a,
clearly, a is lower, so that's the LCA. Doing a 3-way merge with that
should work just fine. Say that merges into g.
If we then merge d and e, we have b as common ancestor, and merge into h.
Now we have g and h left and want to merge those. If you forget about
node ids, and pretend this would be a simple scalar merge, we'd have
to merge with o as the common ancestor, right? So this probably poses
problems for us, because o doesn't carry our file.
Couldn't d be the common ancestor in that case? You want an ancestor
close to the revs being merged, not closer to the root of the DAG, right?
Uh... you are right, cool. I've been overly cautious...
The set of common ancestors of h and g is: o, a, b and d. And d clearly
is a descendant of all other common ancestors.
So that means, there is no 'content merge problem' for suturing, right?
In general it seems that you're going to get one of a few cases:
i) The rev with the suture is an ancestor, of both sides, in which
case you have at least one common ancestor.
ii) The rev with the suture is an ancestor of only one side, but in
that case there should still be a common ancestor.
iii) You haven't sutured - in which case you will get non-content
conflicts, same as now.
iv) You have sutured, but you're trying to merge two revs neither of
which has the suture rev as an ancestor. Not sure what should happen
here, but I'd be happy if this failed - you must merge in the suture
node first. This could be treated the same as iii), no?
Ahhh. There may be a third option here. Use a disjoint sets (aka
union-find) algorithm on node-ids.
http://en.wikipedia.org/wiki/Disjoint-set_data_structure
In this option, each node-id would have a pointer to a 'parent'
node-id. If the parent is null then you use the node-id itself.
Otherwise you keep following parent ids until you get to the final id
of a node. You then merge as normal... (have to think about how to
find a 'common ancestor' for three-way merge).
Again, same problem as above: there is no usable common ancestor for
the merge.
Well, I think this might not be a problem. You just end up using the
suture node as a common ancestor.
Correct, AFAICT now.
Regards
Markus
_______________________________________________
Monotone-devel mailing list
Monotone-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/monotone-devel
