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

[William Uther]

On 07/05/2008, at 1:21 PM, Matthew Nicholson wrote:

> William Uther wrote:
>
> > 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.
>
> Reversal involves making two new node id's each with the sutured  
> node as a parent.

Not sure what you mean by 'parent' here.  If you mean 'parent' in the  
revision parent sense, then that is confused - we're talking about  
files, not revisions.  If you mean 'parent' in the union-find  
algorithm sense then what you describe will not achieve a split - both  
new node id's would end up having the same 'set' according to the  
algorithm and you have achieved nothing but a slight slowdown.

The only way I can imagine making a 'split' is the simple one of  
making a new file with the current contents - think 'copy'.  Hrm, I  
guess you could make it symmetric and create two new ids (kinda like  
two copies and a drop), but I'm not sure that is an advance.

> History is preserved and the files are split again.  This of course  
> is roughly equivalent to the copy/split operation I have seen  
> floating around.

This is a tricky problem.  e.g.

   a   b
    \ / \
     c   d
     |\ /|
     | e |
     |   |
     f   |
      \ /
       g

Lower case letters are revisions, not files.

a and b each create a file 'foo'.  I'll refer to them as fooa and foob.
c sutures the two foos together - making fooc.
d edits foob.
e merges the changes made in d to foob into fooc.
f splits fooc into ??
g merges d and f.  What happens to the changes to foob in rev d?  Are  
they dropped?  Are they merged into both child nodes of fooc?  Only  
one child node, and if so, which?

No imagine another child revision of a that makes changes to fooa.  It  
then gets merged with rev g.  What happens now?

This is what I mean when I say that history is lost.  Once node-ids  
get merged, they're forever merged.  You could introduce a copy  
operation that made a new node-id.  In that situation, any merges from  
before the join will get merged into the merged node, and the copied  
node is just like a new file.  I cannot see a way to separate out  
changes rooted in rev a from changes rooted in rev b and have them  
merge into the correct files after a 'split'.  AFAIK the union-find  
algorithm is one-way.  It isn't a union-find-separate algorithm.

> > 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.
>
> This is very similar to what I was thinking when the "atomic drop  
> two add one" idea was first presented.  This is basically a  
> combination of your options i and iii, although with pure option 3  
> you don't need the graveyard.

You still need a structure very like a graveyard, but it doesn't store  
a resurrection bit.  I guess you're right in that it doesn't need to  
be stored for deleted nodes, and hence you don't get the 'monotonic  
roster size growth' problem.

Cheers,

Will        :-}