Merge lp:~jameinel/bzr/2.0rc2-419241-merge-sort into lp:bzr/2.0

[John A Meinel]

[John A Meinel (jameinel)]

This fixes a bug in KnownGraph.merge_sort() when there is a ghost as a mainline parent.

The old code didn't notice because we always pruned ghosts when passing in the parent_map, but it seems nicer to have merge_sort handle them directly. (Means fewer calls to _strip_NULL_ghosts :).

This is part of a critical regression right now for stuff like 'bzr log' on branches with mainline ghosts.

The second (more critical) part is coming soon.

(The code is built on the 2.0 release branch so it can be merged there primarily.)

[Vincent Ladeuil (vila)]

review: Approve

=== modified file 'NEWS'
--- NEWS	2009-08-26 12:54:21 +0000
+++ NEWS	2009-08-26 16:35:14 +0000
@@ -6,6 +6,17 @@
 .. contents:: List of Releases
    :depth: 1
 
+bzr 2.0rc2
+##########
+
+Bug Fixes
+*********
+
+* Fix a potential segmentation fault when doing 'log' of a branch that had
+  ghosts in its mainline. (evaluating None as a tuple is bad.)
+  (John Arbash Meinel, #419241)
+
+
 bzr 2.0rc1
 ##########
 

=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- bzrlib/_known_graph_pyx.pyx	2009-08-18 21:41:08 +0000
+++ bzrlib/_known_graph_pyx.pyx	2009-08-26 16:35:14 +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'
--- bzrlib/tests/test__known_graph.py	2009-08-18 21:41:08 +0000
+++ bzrlib/tests/test__known_graph.py	2009-08-26 16:35:14 +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'
--- bzrlib/tsort.py	2009-08-19 16:23:39 +0000
+++ bzrlib/tsort.py	2009-08-26 16:35:14 +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]