Re: [Monotone-devel] resolving name conflicts; file suturing vs drop

[Markus Schiltknecht]

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