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

[William Uther]

On 06/05/2008, at 5:58 PM, Markus Schiltknecht wrote:

> Hi,
>
> William Uther wrote:
> > I can't see an easy way to implement this without a graveyard.  If  
> > you're
> > going to implement a graveyard, then I'd get rid of DieDieDie merge  
> > first.
>
> Hm.. I don't see what file resurrection has to do with suturing. Of  
> course, resurrection would help the user to revert from erroneously  
> sutured files. But that's the point of it.

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.

> > You could then implement the 'drop one side' approximation to a  
> > suture, and
> > know that DieDieDie merge wont kill you.
>
> To be symmetric, suturing will have to drop both source files and  
> create a new destination node. Only that way you can resurrect any  
> of the two files later on, for example.
>
> 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.

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

  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.

Option ii) is much messier, but much easier to implement.  Hrm.  Maybe  
not.  Maybe you could do both quick and dirty...

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

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.

Well, it is more food for thought anyway.

> > Once you have a graveyard, appending information to dead nodes,  
> > such as
> > "this node was merged into this other node" would make future  
> > merges easier.
>
> Hm.. maybe you need to outline your graveyard concept a little  
> better. Last I've heard about file resurrection, we should simply  
> add a boolean flag for alive or dead. That hardly carries any extra  
> information, but could be merged the same as other attributes.

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.

I don't know how to merge "replacement" node-ids.  Merging of the  
'parent' node-id for a disjoint sets data structure is easy - it is  
the union operation in "union-find".

Cheers,

Will       :-}