Rev 3521: Fall back to more complete ancestry when we encounter an edge case that doesn't work with simple LCA searching. in http://bzr.arbash-meinel.com/branches/bzr/1.6-dev/merge3_per_file

[John Arbash Meinel]

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

------------------------------------------------------------
revno: 3521
revision-id: john at arbash-meinel.com-20080626234053-jxkl4wuu79b81e98
parent: john at arbash-meinel.com-20080626150300-247h9y65fipn7487
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: merge3_per_file
timestamp: Thu 2008-06-26 18:40:53 -0500
message:
  Fall back to more complete ancestry when we encounter an edge case that doesn't work with simple LCA searching.
-------------- next part --------------
=== modified file 'bzrlib/merge.py'
--- a/bzrlib/merge.py	2008-06-26 15:03:00 +0000
+++ b/bzrlib/merge.py	2008-06-26 23:40:53 +0000
@@ -1583,20 +1583,35 @@
             elif len(next_lcas) == 1:
                 parent_map[next_lcas.pop()] = ()
                 break
+            elif len(next_lcas) > 2:
+                # Fall back to grabbing all of the ancestry for this entry
+                warning('Found more than to Least Common Ancestors'
+                        ' falling back to full ancestry. For %s',
+                        self.vf)
+                cur_lcas = next_lcas
+                while len(cur_lcas) > 1:
+                    cur_lcas = self.graph.find_lca(*cur_lcas)
+                if not cur_lcas:
+                    mutter('no common ancestor, using NULL')
+                    unique_lca = NULL_REVISION
+                else:
+                    unique_lca = cur_lcas.pop()
+
+                parent_map.update(self._find_unique_parents(next_lcas,
+                                                            unique_lca))
+                break
             cur_ancestors = next_lcas
+
         return parent_map
 
-    def _find_all_ancestors(self):
-        try:
-            unique_lca = self.graph.find_unique_lca(self.a_rev, self.b_rev)
-        except errors.NoCommonAncestor:
-            unique_lca = NULL_REVISION
-        interesting = self.graph.find_unique_ancestors(self.a_rev, [unique_lca])
-        interesting.update(self.graph.find_unique_ancestors(self.b_rev,
-                                                            [unique_lca]))
+    def _find_unique_parents(self, tip_revisions, base_revision):
+        interesting = set()
+        for tip in tip_revisions:
+            interesting.update(
+                self.graph.find_unique_ancestors(tip, [base_revision]))
         parent_map = self.graph.get_parent_map(interesting)
-        interesting.add(unique_lca)
-        parent_map[unique_lca] = ()
+        interesting.add(base_revision)
+        parent_map[base_revision] = ()
         culled_parent_map = {}
         for rev_id, parent_ids in parent_map.iteritems():
             real_parent_ids = [p_id for p_id in parent_ids
@@ -1604,6 +1619,13 @@
             culled_parent_map[rev_id] = real_parent_ids
         return culled_parent_map
 
+    def _find_all_ancestors(self):
+        try:
+            unique_lca = self.graph.find_unique_lca(self.a_rev, self.b_rev)
+        except errors.NoCommonAncestor:
+            unique_lca = NULL_REVISION
+        return self._find_unique_parents((self.a_rev, self.b_rev), unique_lca)
+
     def _get_interesting_texts(self, parent_map):
         all_revision_ids = set(parent_map)