Re: [Monotone-devel] resolving name conflicts; implementation issues

[Stephen Leake]

I'm implementing the suture/merge test case discussed in
http://lists.gnu.org/archive/html/monotone-devel/2008-05/msg00108.html
and following.

We have this revision history graph:

                o
               / \
             A1a  B2b
             /| \ /|
            / |  X |
           /  C / \|
          /   |/  D3d
        E1e  F2b

'o' is the base revision. In 'A' and 'B', Abe and Beth each add a
file with the same name 'checkout.sh'.

in 'D', Beth resolves the duplicate name conflict by suturing. As
implemented in nvm.automate_show_conflicts, "suture" means drop both
parent nodes and create one new one, recording this event in the
marking map and the changeset for the revision.

in 'C', Abe prepares to resolve the duplicate name conflict by
dropping his version; he merges in F, keeping Beth's (Abe hasn't
learned about suture yet).

in 'E', Jim edits Abe's version of checkout.sh.

Then we consider the two possible merge orders for D, E, and F; 
do they produce consistent results?

Merging E, F to G encounters a content/drop conflict. Currently, that
is resolved by die-die-die; Jim's changes are lost. 

I propose to replace that with a new content_drop conflict, which can
be resolved by suture or by ignore_drop; we choose suture in this
case, keeping Jim's content:

                o
               / \
             A1a  B2b
             /| \ /|
            / |  X |
           /  C / \|
          /   |/  D3d
        E1e  F2b
          \  /
           G4e

This conflict is already detected by the code that outputs the warning
about changes being lost; it's easy to replace that by a conflict that
can be resolved with user input.

Then merging G, D to H could be just a content conflict, since the
marking map records that nodes 3 and 4 have ancestor nodes 1 and 2 in
common, and the necessary sutures have already been done:

                o
               / \
             A1a  B2b
             /| \ /|
            / |  X |
           /  C / \|
          /   |/  D3d
        E1e  F2b  /
          \  /   /
           G4e  /
             \ /
             H5e

Or maybe this will require an explicit suture to resolve; I haven't
implemented that step yet. The revision graph as drawn here certainly
says it's a suture. The issue is how it is reported to the user;
perhaps mtn au show_conflicts could output a duplicate name conflict
with a resolution of 'resolved_suture'.

Going back and considering the other merge order; merging D, F to G
gives a suture/drop conflict, resolved in this case by ignore_drop:

                o
               / \
             A1a  B2b
             /| \ /|
            / |  X |
           /  C / \|
          /   |/  D3d
        E1e  F2b  /
               \ / 
               G3d

I have not implemented this conflict yet; currently the merge
succeeds, ignoring the drop. We need to allow the other choice, which
would be to drop the sutured node.

Merging E and G to H is then a content conflict (because the marking
map records the fact that node 1 is an ancestor of node 3), resolved
in this case by keeping Jim's content:

                o
               / \
             A1a  B2b
             /| \ /|
            / |  X |
           /  C / \|
          /   |/  D3d
        E1e  F2b  /
          \    \ / 
           \   G3d
            \  /
             H3e

So implementing content/drop and suture/drop conflicts will allow this
use case to be resolved consistently, no matter which merge order is
chosen.

Comments?

-- 
-- Stephe