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

[Stephen Leake]

Stephen Leake <address@hidden> writes:

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

This is now partly implemented.

All other existing tests are passing, except those that relied on
die-die-die for content/drop conflicts:

  2 (imp)_merge((patch_foo_a),_(delete_foo_))     FAIL (line 18)
267 merge((drop_a),_(rename_a_b,_patch_b))        FAIL (line 22)
268 merge((patch_a),_(drop_a))                    FAIL (line 21)
269 merge((patch_a),_(drop_a,_add_a))             FAIL (line 29)

These now report content/drop conflicts. I'm not clear what to do with
these tests.

>
> 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 step (merging E and F to produce G) gives two conflicts:

     conflict duplicate_name
    left_type "added file"
    left_name "checkout.sh"
 left_file_id [dd6805ae36432d6edcbdff6ea578ea981ffa2144]
   right_type "added file"
   right_name "checkout.sh"
right_file_id [7b4836e9931cf1a3adfc8c432a3e407b2fef84e9]

     conflict content_drop
   right_type "file"
   right_name "checkout.sh"
right_file_id [7b4836e9931cf1a3adfc8c432a3e407b2fef84e9]

The duplicate_name conflict is the same one that Abe attempted to
resolve by dropping node 1; this just shows that dropping is _not_ a
good way to resolve duplicate name conflicts.

This time, the duplicate_name conflict is resolved by suturing nodes 1
and 2 into node 4. Then rev E is just a change to a sutured node,
which would normally not be a conflict. But since a conflict is
reported here, it is resolved by specifying 'resolved_suture'.


> 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

At the moment, this is a duplicate name conflict; nodes 3 and 4 are
both named 'checkout.sh'; the ancestry is not fully searched. So it
requires a suture.

However, there are other situations in which a more complete search of
ancestry is required. Consider suturing several files together on one
side of a merge (these would have to be user sutures, not conflict
resolution sutures):

  A1a  A2b  A3c  A4d
    \  /      \  /   \   \    \    \
     B5e       B6f  C1g  C2h  C3i  C4j
       \       /    /    /    /    /
        \     /    /    /    /    /
         \   /    /    /    /    /
          D7k    /    /    /    /
            \   /    /    /    /
              E7?

If the scalars for nodes 1, 2, 3, 4 on the right are not changed from their
ancestor values on the left, this should be a clean merge, resulting
in E7k. On the other hand, if any scalars have changed, there should
be conflicts, which would be resolved by suturing. Determining that
means searching all uncommon ancestors of E for sutures, which can
grow without bound in a long-running separate branch. But if we assume
sutures are rare, perhaps that's ok.

A separate issue is how to do the sutures; the order may matter. I
think the simplest approach here is for the merge to fail, and require
the user to suture the right side in the same way the left was
sutured, before doing the final merge. Then it is the same as merging
G, D above.

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

I'll work on this next.

-- 
-- Stephe