Rev 3527: Add the ability to prune extra tails from the parent_map. in http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/weave_merge

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/weave_merge

------------------------------------------------------------
revno: 3527
revision-id: john at arbash-meinel.com-20080713003042-ak1b725ck5vmpbmi
parent: john at arbash-meinel.com-20080712180630-5hc93d3s2vff9olo
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: weave_merge
timestamp: Sat 2008-07-12 19:30:42 -0500
message:
  Add the ability to prune extra tails from the parent_map.
  
  Now we can get the right answer without having to add extra history.
-------------- next part --------------
=== modified file 'bzrlib/merge.py'
--- a/bzrlib/merge.py	2008-07-12 18:06:30 +0000
+++ b/bzrlib/merge.py	2008-07-13 00:30:42 +0000
@@ -1493,6 +1493,9 @@
             parent_map[base_key] = ()
         culled_parent_map, child_map, tails = self._remove_external_references(
             parent_map)
+        # Remove all the tails but base_key
+        tails.remove(base_key)
+        self._prune_tails(culled_parent_map, child_map, tails)
         return culled_parent_map
 
     @staticmethod
@@ -1524,8 +1527,30 @@
             filtered_parent_map[key] = culled_parent_keys
         return filtered_parent_map, child_map, tails
 
-    def _prune_tails(self, parent_map, tails_to_remove, child_map):
-        """Remove tails from the parent map."""
+    @staticmethod
+    def _prune_tails(parent_map, child_map, tails_to_remove):
+        """Remove tails from the parent map.
+        
+        This will remove the supplied revisions until no more children have 0
+        parents.
+
+        :param parent_map: A dict of {child: [parents]}, this dictionary will
+            be modified in place.
+        :param tails_to_remove: A list of tips that should be removed,
+            this list will be consumed
+        :param child_map: The reverse dict of parent_map ({parent: [children]})
+            this dict will be modified
+        :return: None, parent_map will be modified in place.
+        """
+        while tails_to_remove:
+            next = tails_to_remove.pop()
+            parent_map.pop(next)
+            children = child_map.pop(next)
+            for child in children:
+                child_parents = parent_map[child]
+                child_parents.remove(next)
+                if len(child_parents) == 0:
+                    tails_to_remove.append(child)
 
     def _get_interesting_texts(self, parent_map):
         """Return a dict of texts we are interested in.

=== modified file 'bzrlib/tests/test_merge.py'
--- a/bzrlib/tests/test_merge.py	2008-07-12 18:06:30 +0000
+++ b/bzrlib/tests/test_merge.py	2008-07-13 00:30:42 +0000
@@ -632,20 +632,12 @@
         # Merge G & H but supersede an old line in B
         self.add_rev('root', 'J', ['H', 'Q', 'G'], 'DaJbCcF')
         plan = self.plan_merge_vf.plan_merge('I', 'J')
-        # This has a slight incorrect value, as it considers the lines in A to
-        # be 'killed-base', because they show up as new in both B and C, and
-        # then E has to resolve which ones are the 'real' ones.
-        # However, I believe this is okay as the important lines will all
-        # derive from E.
         self.assertEqual([
                           ('unchanged', 'D\n'),
                           ('unchanged', 'a\n'),
                           ('killed-b', 'B\n'),
                           ('new-b', 'J\n'),
                           ('unchanged', 'b\n'),
-                          ('killed-base', 'c\n'), # Not technically correct
-                          ('killed-base', 'a\n'), # as they came from A
-                          ('killed-base', 'b\n'), # but the final text is right
                           ('unchanged', 'C\n'),
                           ('unchanged', 'c\n'),
                           ('unchanged', 'F\n')],
@@ -812,6 +804,38 @@
             [3, 4],
             {1: [3], 2: [3, 4], 3: [5], 4: []})
 
+    def assertPruneTails(self, pruned_map, tails, parent_map):
+        child_map = {}
+        for key, parent_keys in parent_map.iteritems():
+            child_map.setdefault(key, [])
+            for pkey in parent_keys:
+                child_map.setdefault(pkey, []).append(key)
+        _PlanMerge._prune_tails(parent_map, child_map, tails)
+        self.assertEqual(pruned_map, parent_map)
+
+    def test__prune_tails(self):
+        # Nothing requested to prune
+        self.assertPruneTails({1: [], 2: [], 3: []}, [],
+                              {1: [], 2: [], 3: []})
+        # Prune a single entry
+        self.assertPruneTails({1: [], 3: []}, [2],
+                              {1: [], 2: [], 3: []})
+        # Prune a chain
+        self.assertPruneTails({1: []}, [3],
+                              {1: [], 2: [3], 3: []})
+        # Prune a chain with a diamond
+        self.assertPruneTails({1: []}, [5],
+                              {1: [], 2: [3, 4], 3: [5], 4: [5], 5: []})
+        # Prune a partial chain
+        self.assertPruneTails({1: [6], 6:[]}, [5],
+                              {1: [2, 6], 2: [3, 4], 3: [5], 4: [5], 5: [],
+                               6: []})
+        # Prune a chain with multiple tips, that pulls out intermediates
+        self.assertPruneTails({1:[3], 3:[]}, [4, 5],
+                              {1: [2, 3], 2: [4, 5], 3: [], 4:[], 5:[]})
+        self.assertPruneTails({1:[3], 3:[]}, [5, 4],
+                              {1: [2, 3], 2: [4, 5], 3: [], 4:[], 5:[]})
+
     def test_subtract_plans(self):
         old_plan = [
         ('unchanged', 'a\n'),