Hi,
William Uther wrote:
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.
I fully agree.
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.
Well, f currently has 3 ancestor, but your example applies anyway, yes.
Note that merging c and d, or d and e would require merging "through the
drop".
Correct. That would involve handling multiple node id's.
Let's check for merging c and d: common ancestors are: o and a, clearly,
a is lower, so that's the LCA. Doing a 3-way merge with that should work
just fine. Say that merges into g.
If we then merge d and e, we have b as common ancestor, and merge into h.
Now we have g and h left and want to merge those. If you forget about
node ids, and pretend this would be a simple scalar merge, we'd have to
merge with o as the common ancestor, right? So this probably poses
problems for us, because o doesn't carry our file.
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.
Huh? I think that makes no real difference. Whether you 'reuse' one of
the node ids and special case merges from the other one or just special
case everything... you still have to solve the above problem somehow
(maybe with some sort of pluck). And the required amount of code is
probably the same.
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).
Again, same problem as above: there is no usable common ancestor for the
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.
Hm.. I didn't read into disjoint sets, but again, I doubt it makes any
difference to the content merging problem, where we have no usable
common ancestor.
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.
Yes, that extra is certainly needed somewhere. Either on the drop, or on
the add side. (i.e. dropped due to suturing into foo, or created from
suturing from bar and baz)
Regards
Markus
_______________________________________________
Monotone-devel mailing list
[email protected]
http://lists.nongnu.org/mailman/listinfo/monotone-devel
