[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Monotone-devel] resolving name conflicts; file suturing vs drop
From: |
William Uther |
Subject: |
Re: [Monotone-devel] resolving name conflicts; file suturing vs drop |
Date: |
Wed, 7 May 2008 14:10:03 +1000 |
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 :-}
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, (continued)
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Derek Scherger, 2008/05/09
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Thomas Moschny, 2008/05/10
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Justin Patrin, 2008/05/06
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Markus Schiltknecht, 2008/05/07
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, William Uther, 2008/05/06
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Matthew Nicholson, 2008/05/06
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop,
William Uther <=
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Matthew Nicholson, 2008/05/07
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Stephen Leake, 2008/05/07
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, William Uther, 2008/05/07
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Markus Schiltknecht, 2008/05/07
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, William Uther, 2008/05/07
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Markus Schiltknecht, 2008/05/07
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Stephen Leake, 2008/05/07
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Markus Schiltknecht, 2008/05/07
Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Thomas Moschny, 2008/05/08