[patch] weave merge conflict scope improvement

[Martin Pool]

This patch improves detection of conflict regions in weave merge.
The particular case which is improved is demonstrated by the new test
case test_sync_on_deletion.  

The current code incorrectly merges them to

            start context
<<<<<<< 
            a's replacement line 2
=======
            b replaces
            both lines
>>>>>>> 
            end context

The change is in how we handle lines which were present in a base
revision, but now deleted in both new versions.  These changes are
agreed-upon and shouldn't cause a conflict in themselves, but we don't
know precisely where in the new text they used to be, so we cannot use
them to delimit regions of disagreement.

Thanks to David Allouche for helping find this.

-- 
Martin
-------------- next part --------------
=== modified file 'a/bzrlib/tests/test_weave.py'
--- a/bzrlib/tests/test_weave.py	
+++ b/bzrlib/tests/test_weave.py	
@@ -780,6 +780,141 @@
                      ['aaa', 'ddd', 'ccc'],
                      ['aaa', 'ccc'],
                      ['<<<<<<<< ', 'aaa', '=======', '>>>>>>> ', 'ccc'])
+
+    def _test_merge_from_strings(self, base, a, b, expected):
+        w = Weave()
+        w.add_lines('text0', [], base.splitlines(True))
+        w.add_lines('text1', ['text0'], a.splitlines(True))
+        w.add_lines('text2', ['text0'], b.splitlines(True))
+        self.log('merge plan:')
+        p = list(w.plan_merge('text1', 'text2'))
+        for state, line in p:
+            if line:
+                self.log('%12s | %s' % (state, line[:-1]))
+        self.log('merge result:')
+        result_text = ''.join(w.weave_merge(p))
+        self.log(result_text)
+        self.assertEqualDiff(result_text, expected)
+
+    def test_deletion_extended(self):
+        """One side deletes, the other deletes more.
+        """
+        base = """\
+            line 1
+            line 2
+            line 3
+            """
+        a = """\
+            line 1
+            line 2
+            """
+        b = """\
+            line 1
+            """
+        result = """\
+            line 1
+            """
+        self._test_merge_from_strings(base, a, b, result)
+
+    def test_deletion_overlap(self):
+        """Delete overlapping regions with no other conflict.
+
+        Arguably it'd be better to treat these as agreement, rather than 
+        conflict, but for now conflict is safer.
+        """
+        base = """\
+            start context
+            int a() {}
+            int b() {}
+            int c() {}
+            end context
+            """
+        a = """\
+            start context
+            int a() {}
+            end context
+            """
+        b = """\
+            start context
+            int c() {}
+            end context
+            """
+        result = """\
+            start context
+<<<<<<< 
+            int a() {}
+=======
+            int c() {}
+>>>>>>> 
+            end context
+            """
+        self._test_merge_from_strings(base, a, b, result)
+
+    def test_agreement_deletion(self):
+        """Agree to delete some lines, without conflicts."""
+        base = """\
+            start context
+            base line 1
+            base line 2
+            end context
+            """
+        a = """\
+            start context
+            base line 1
+            end context
+            """
+        b = """\
+            start context
+            base line 1
+            end context
+            """
+        result = """\
+            start context
+            base line 1
+            end context
+            """
+        self._test_merge_from_strings(base, a, b, result)
+
+    def test_sync_on_deletion(self):
+        """Specific case of merge where we can synchronize incorrectly.
+        
+        A previous version of the weave merge concluded that the two versions
+        agreed on deleting line 2, and this could be a synchronization point.
+        Line 1 was then considered in isolation, and thought to be deleted on 
+        both sides.
+
+        It's better to consider the whole thing as a disagreement region.
+        """
+        base = """\
+            start context
+            base line 1
+            base line 2
+            end context
+            """
+        a = """\
+            start context
+            base line 1
+            a's replacement line 2
+            end context
+            """
+        b = """\
+            start context
+            b replaces
+            both lines
+            end context
+            """
+        result = """\
+            start context
+<<<<<<< 
+            base line 1
+            a's replacement line 2
+=======
+            b replaces
+            both lines
+>>>>>>> 
+            end context
+            """
+        self._test_merge_from_strings(base, a, b, result)
 
 
 class JoinWeavesTests(TestBase):
@@ -974,7 +1109,7 @@
         w2.join(w1) # extract 3b to add txt1 
 
 
-class TestNeedsRweave(TestCase):
+class TestNeedsReweave(TestCase):
     """Internal corner cases for when reweave is needed."""
 
     def test_compatible_parents(self):
@@ -990,5 +1125,3 @@
         self.assertFalse(w1._compatible_parents(set(), set([1])))
         self.assertFalse(w1._compatible_parents(my_parents, set([1, 2, 3, 4])))
         self.assertFalse(w1._compatible_parents(my_parents, set([4])))
-        
-

=== modified file 'a/bzrlib/versionedfile.py'
--- a/bzrlib/versionedfile.py	
+++ b/bzrlib/versionedfile.py	
@@ -448,8 +448,12 @@
         # 
         # TODO: Show some version information (e.g. author, date) on 
         # conflicted regions.
+        
+        # We previously considered either 'unchanged' or 'killed-both' lines
+        # to be possible places to resynchronize.  However, assuming agreement
+        # on killed-both lines may be too agressive. -- mbp 20060324
         for state, line in plan:
-            if state == 'unchanged' or state == 'killed-both':
+            if state == 'unchanged':
                 # resync and flush queued conflicts changes if any
                 if not lines_a and not lines_b:
                     pass

=== modified file 'a/bzrlib/weave.py'
--- a/bzrlib/weave.py	
+++ b/bzrlib/weave.py	
@@ -66,6 +66,7 @@
 # be done fairly efficiently because the sequence numbers constrain
 # the possible relationships.
 
+# FIXME: the conflict markers should be *7* characters
 
 from copy import copy
 from cStringIO import StringIO

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: Digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060324/05ff5cfa/attachment.pgp