Rev 4653: Support when the left-hand parent is a ghost. in http://bazaar.launchpad.net/~jameinel/bzr/2.0rc2-419241-merge-sort-lefthand-ghost

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/2.0rc2-419241-merge-sort-lefthand-ghost

------------------------------------------------------------
revno: 4653
revision-id: john at arbash-meinel.com-20090826151153-uj942xu3cdzm61ld
parent: pqm at pqm.ubuntu.com-20090826124958-pwu4xwec4nyn01nn
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.0rc2-419241-merge-sort-lefthand-ghost
timestamp: Wed 2009-08-26 10:11:53 -0500
message:
  Support when the left-hand parent is a ghost.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-08-18 21:41:08 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-08-26 15:11:53 +0000
@@ -443,7 +443,8 @@
         self.completed = 0
 
     def __repr__(self):
-        return '%s(depth:%s rev:%s,%s,%s first:%s seen:%s)' % (self.__class__.__name__,
+        return '%s(%s depth:%s rev:%s,%s,%s first:%s seen:%s)' % (
+            self.__class__.__name__, self.key,
             self.merge_depth,
             self._revno_first, self._revno_second, self._revno_last,
             self.is_first_child, self.seen_by_child)
@@ -497,7 +498,6 @@
         if (tip_key is not None and tip_key != NULL_REVISION
             and tip_key != (NULL_REVISION,)):
             node = self.graph._nodes[tip_key]
-            self._get_ms_node(node)
             self._push_node(node, 0)
 
     cdef _MergeSortNode _get_ms_node(self, _KnownGraphNode node):
@@ -518,10 +518,17 @@
 
         ms_node = self._get_ms_node(node)
         ms_node.merge_depth = merge_depth
+        if node.parents is None:
+            raise RuntimeError('ghost nodes should not be pushed'
+                               ' onto the stack: %s' % (node,))
         if PyTuple_GET_SIZE(node.parents) > 0:
             parent_node = _get_parent(node.parents, 0)
             ms_node.left_parent = parent_node
-            ms_node.left_pending_parent = parent_node
+            if parent_node.parents is None: # left-hand ghost
+                ms_node.left_pending_parent = None
+                ms_node.left_parent = None
+            else:
+                ms_node.left_pending_parent = parent_node
         if PyTuple_GET_SIZE(node.parents) > 1:
             ms_node.pending_parents = []
             for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):

=== modified file 'bzrlib/tests/test__known_graph.py'
--- a/bzrlib/tests/test__known_graph.py	2009-08-18 21:41:08 +0000
+++ b/bzrlib/tests/test__known_graph.py	2009-08-26 15:11:53 +0000
@@ -731,6 +731,20 @@
              ('A', 0, (1,), True),
             ])
 
+    def test_lefthand_ghost(self):
+        # ghost
+        #  |
+        #  A
+        #  |
+        #  B
+        self.assertSortAndIterate(
+            {'A': ['ghost'],
+             'B': ['A'],
+            }, 'B',
+            [('B', 0, (2,), False),
+             ('A', 0, (1,), True),
+            ])
+
     def test_graph_cycle(self):
         # merge_sort should fail with a simple error when a graph cycle is
         # encountered.

=== modified file 'bzrlib/tsort.py'
--- a/bzrlib/tsort.py	2009-08-19 16:23:39 +0000
+++ b/bzrlib/tsort.py	2009-08-26 15:11:53 +0000
@@ -459,9 +459,15 @@
             left_subtree_pushed_stack_append(False)
             pending_parents_stack_append(list(parents))
             # as we push it, check if it is the first child
+            parent_info = None
             if parents:
                 # node has parents, assign from the left most parent.
-                parent_info = revnos[parents[0]]
+                try:
+                    parent_info = revnos[parents[0]]
+                except KeyError:
+                    # Left-hand parent is a ghost, consider it not to exist
+                    pass
+            if parent_info is not None:
                 first_child = parent_info[1]
                 parent_info[1] = False
             else:
@@ -495,9 +501,15 @@
             pending_parents_stack_pop()
 
             parents = original_graph[node_name]
+            parent_revno = None
             if parents:
                 # node has parents, assign from the left most parent.
-                parent_revno = revnos[parents[0]][0]
+                try:
+                    parent_revno = revnos[parents[0]][0]
+                except KeyError:
+                    # left-hand parent is a ghost, treat it as not existing
+                    pass
+            if parent_revno is not None:
                 if not first_child:
                     # not the first child, make a new branch
                     base_revno = parent_revno[0]
@@ -628,10 +640,15 @@
         self._left_subtree_pushed_stack.append(False)
         self._pending_parents_stack.append(list(parents))
         # as we push it, figure out if this is the first child
-        parents = self._original_graph[node_name]
+        parent_info = None
         if parents:
             # node has parents, assign from the left most parent.
-            parent_info = self._revnos[parents[0]]
+            try:
+                parent_info = self._revnos[parents[0]]
+            except KeyError:
+                # Left-hand parent is a ghost, consider it not to exist
+                pass
+        if parent_info is not None:
             first_child = parent_info[1]
             parent_info[1] = False
         else:
@@ -655,9 +672,15 @@
         self._pending_parents_stack.pop()
 
         parents = self._original_graph[node_name]
+        parent_revno = None
         if parents:
             # node has parents, assign from the left most parent.
-            parent_revno = self._revnos[parents[0]][0]
+            try:
+                parent_revno = self._revnos[parents[0]][0]
+            except KeyError:
+                # left-hand parent is a ghost, treat it as not existing
+                pass
+        if parent_revno is not None:
             if not first_child:
                 # not the first child, make a new branch
                 base_revno = parent_revno[0]