[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Monotone-devel] Mark merge for existence
From: |
William Uther |
Subject: |
Re: [Monotone-devel] Mark merge for existence |
Date: |
Thu, 15 Nov 2007 22:42:23 +1100 |
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 :-}
Re: [Monotone-devel] Mark merge for existence, Markus Schiltknecht, 2007/11/15
Re: [Monotone-devel] Mark merge for existence, William Uther, 2007/11/15