Re: [Monotone-devel] Mark merge for existence

[William Uther]

On 15/11/2007, at 7:49 PM, Markus Schiltknecht wrote:

> Hey William,
>
> William Uther wrote:
> >  As a first step I'd like to make a version of monotone that  
> > remembers the new 'existence' marks when the file exists (i.e. add  
> > existence marks to the current code without trying to remember them  
> > when a file is deleted - no it wont change anything, but it is a  
> > necessary step).
>
> "The" new existence marks? Did I miss something here?

Er, sorry.  I edited down a longer email.  "the" should have been  
deleted.

> Are you sure, that's the solution to the die die die merge problem?  
> I'd rather add an (async) copy command

Ok...

> (which does not track merges). And try to get merging right for it.

Um, if it does not track merges, how do you "get merging right"?

I can see how not tracking merges at all might work: simply introduce  
a new node and a simple pointer so that when you track history the  
logs continue from the new node to the old one (I assume this is what  
your diagram was showing).

I have no objections to that at all. (And you could add that as well  
as what I'm suggesting.)

However, if you try to modify it to get merging working then I think  
you travel down the path to Operational Transformation (OT) style  
merging (See also DARCS).  This could work well, and I think would  
make for interesting text merge capabilities too, but is a huge amount  
of work to add it and get it right.

> William Uther wrote:
> >  cmd_merging.cc : CMD(merge)
> >  cmd_merging.cc : merge_two()
> >  merge.cc : interactive_merge_and_store()   # loads the left &  
> > right rosters and marks from db
> >  roster_merge.cc : roster_merge()         merge.cc :  
> > store_roster_merge_result()
> >                                           database.cc :  
> > database::put_revision()
> >                                           database.cc :  
> > put_roster_for_revision()
> >                                           roster.cc :  
> > make_roster_for_revision()
> >                                           roster.cc :  
> > make_roster_for_merge()
> >                                           roster.cc :  
> > mark_merge_roster()  # much happens here
> >                                           roster.cc :   
> > mark_unmerged_node()  and  mark_merged_node()
> >  It seems that roster_merge() does the main merge, but then  
> > mark_merge_roster() does a lot of very similar work to build up the  
> > new marking map just before it is actually written to the db.  This  
> > seems a little convoluted.  Is there some reason for this I'm  
> > missing, or is it just... historical?
>
> Uh.. AFAICT  mark_merged_node() and mark_unmerged_node() act on a  
> single node, while mark_merge_roster() works on a roster... seems an  
> absolutely legal separation.

Yep - I see that distinction.  It was more the distinction between  
roster_merge() and mark_merge_roster() that was confusing me.  I think  
I get it, but it seems like a strange design, and I was wondering  
about the reason for the split.

Why couldn't you build the new roster in roster_merge() rather than  
sorta-building it and then having a bunch of very similar code in  
mark_merge_roster()?

> You've read and understand *-merge? Best sources here [1].

Yup.  Although I tend to use the docs here: http://revctrl.org/ 
MarkMerge :)

BTW, if you're interested in OT theory (which is the sort of thing you  
might want to make your merge work for copies), look here: http://revctrl.org/OperationalTransformation

> Can you expand on you concept of 'existince marks'?

Nothing complex.  I just want to use mark-merge for existence.  When a  
user explicitly adds or un-deletes a file, it is marked because there  
is a user driven existence change.  When a user deletes a file, it is  
marked because there is a user driven existence change.  When two revs  
are merged, for each node you use mark merge to decide the value of  
the existence bool.  If true then the node exists in the merged  
revision.  If false then the node is deleted in the merged revision.   
If conflicted then you ask the user to resolve things (delete or un- 
delete on either side as appropriate) and merge again.

At the moment this is a little tricky because we only keep marks for  
nodes which currently exist.  This is good for storage size - it  
doesn't grow without bound.  This is bad for mark-merge - you need  
those marks to do the merge.

I think I know how we can efficiently reconstruct those marks during  
the merge.  If the node exists on both sides then there isn't a  
problem - the marks exist on both sides.  If the node doesn't exist on  
either side then there isn't a problem - the node wont exist in the  
children and you don't need the marks.  If the node only exists on one  
side then you need to reconstruct the marks on the side that doesn't  
have them.  I think I know how to do that relatively efficiently -  
find the latest cut (in the graph-theoretic sense) in the common  
ancestors where the marks exist in each revision that makes up the  
cut, and reconstruct the marks from there.  (And I've found a  
wonderful method to find that cut efficiently, but this margin is too  
small to contain it.)

At this stage I just want to modify mtn so that it is keeping  
existence marks when the node exists.  They will end up being trivial  
marks at the moment - the revision where the node was born will be the  
only marked revision for existence.  But I can add things  
incrementally from there...

Be well,

Will         :-}