[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 10:37:16 +1000 |
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 :-}
- Re: [Monotone-devel] resolving name conflicts; code style, (continued)
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Markus Schiltknecht, 2008/05/09
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Stephen Leake, 2008/05/09
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, William Uther, 2008/05/09
- Re: [Monotone-devel] resolving name conflicts; file suturing vs drop, Markus Schiltknecht, 2008/05/09
- 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 <=
- 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, 2008/05/07
- 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