Re: [Monotone-devel] resolving name conflicts; file suturing vs drop

[Stephen Leake]

Markus Schiltknecht <address@hidden> writes:

> William Uther wrote:
>
>> 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.

This is the same duplicate name conflict that was noticed when merging
a and b to get d. So merging g and h fails with a duplicate name
conflict, and 'merge --resolve_conflicts' lets the user resolve it,
by another suture.

>>   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.

The current recommended resolution (in monotone.info) for duplicate
name conflicts where there should be only one file is to drop one
side.

If we use that approach in this example, we get:

       o
      / \
     a   b
    / \ / \
   c   d   e
    \ / \ /
     g   h
      \ /
       f
o is our original revision.
In a and b, two people independently introduced new files with the
same name and purpose.
In d, the file in a is dropped; content of the file in a and b is merged.
In c and e, the files introduced in a and b were each independently edited.
In g, the file disappears due to DieDieDie.
In h, the files in d and e are merged correctly.
In f, the file disappears due to DieDieDie.

I think this is a realistic use case; in c and e Abe and Beth are
improving checkout.sh, while in d some supervisor has noticed the
duplicated work and sutures them. Then g, h, and f are just Abe and
Beth catching up.

So we do need to do something to record the suture so that DieDieDie
doesn't kill the file later. As people have been saying; I'm just
taking a while to catch up :).

However, I'm not saying we need to get rid of DieDieDie entirely; just
override it when there is a suture in the history.

Assuming we do that by adding information somewhere, and adopt the
definition "suture = drop two, add one", this example becomes:

o is our original revision.
In a and b, two people independently introduced new files with the
same name and purpose.
In d, the files in a and b are dropped, a new merged file is added,
and the suture is recorded to defeat later DieDieDie.
In c and e, the files introduced in a and b were each independently edited.
In g, the files in c and d are merged correctly.
In h, the files in d and e are merged correctly.
In f, the files in g and h are merged correctly.

There is no need for 'pluck' that I can see. But maybe I'm missing
something; maybe the code for "c and d are merged correctly" ends up
looking like the code for 'pluck'?

>> 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)

I need to read the code to see exactly to which type this extra info
could be added. I've started adding the rename resolution to merge
(not checked in yet); that will help me understand the code better.

-- 
-- Stephe