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

[Markus Schiltknecht]

Hi,

William Uther wrote:
> Superficially, suturing and resurrection have nothing to do with each 
> other.  However, if you implement suturing using drop, and you still 
> have DieDieDie merge, then suturing is a VERY dangerous operation.  
> Suturing (as I currently understand it - based on drop) would be so 
> dangerous with DieDieDie merge that I would oppose implementing it.

I fully agree.

> > I'm thinking of suturing as an atomic "delete two, add one" operation.
>
> I can see two options for suturing here:
>
>   i) Keep it symmetric as a "delete two, add one" operation.  In this 
> case you need to implement some form of "merge through suture" ability.  
> e.g.  Imagine the following:
>
>        o
>       / \
>      a   b
>     / \ / \
>    c   d   e
>     \  |  /
>      \ | /
>        f
>
> o is our original revision.
> In a and b, two people independently introduced new files with the same 
> name and purpose.
> In revision d, the files introduced in a and b were sutured together.
> In c and e, the files introduced in a and b were each independently edited.
> In f we're trying to merge everything together again.

Well, f currently has 3 ancestor, but your example applies anyway, yes.

> Note that merging c and d, or d and e would require merging "through the 
> drop".

Correct. That would involve handling multiple node id's.

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.

>   ii) Pick one side and drop that side.  This still requires a "merge 
> through suture" function, but that function can be more like 'pluck' in 
> that you just move the patch from the dead node-id and re-apply to the 
> live node-id.  Eventually all instances of the dead node-id would 
> disappear.

Huh? I think that makes no real difference. Whether you 'reuse' one of 
the node ids and special case merges from the other one or just special 
case everything... you still have to solve the above problem somehow 
(maybe with some sort of pluck). And the required amount of code is 
probably the same.

> 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.

> This third option would avoid the drops entirely.  It has the problem 
> that I don't know how to reverse it.  i.e. if you merge two node-ids 
> then you could never tease them apart again.  Hrm.  You could just 
> introduce a new node-id with the current contents, but you'd have lost 
> some of the details in the history.

Hm.. I didn't read into disjoint sets, but again, I doubt it makes any 
difference to the content merging problem, where we have no usable 
common ancestor.

> At the moment dropped node-ids are gone.  Introducing a graveyard means 
> keeping all node-ids around.  The standard thought for resurrection is 
> to keep them around with an 'isLive' boolean attached to them that can 
> be mark-merged.  But once you're keeping around all the node-ids, it 
> wouldn't be hard to keep around more information.  That extra 
> information could be the "replacement" node-id for node ids that were 
> dropped as part of a suture.  The extra information could be the 
> 'parent' node-id from a disjoint sets data structure.

Yes, that extra is certainly needed somewhere. Either on the drop, or on 
the add side. (i.e. dropped due to suturing into foo, or created from 
suturing from bar and baz)

Regards

Markus