Rev 4633: Add tests that we detect GraphCycleError in http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted
John Arbash Meinel
john at arbash-meinel.com
Mon Aug 17 17:35:18 BST 2009
At http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted
------------------------------------------------------------
revno: 4633
revision-id: john at arbash-meinel.com-20090817163507-0j9tdamcybwqu8rn
parent: john at arbash-meinel.com-20090817161122-c0fvi0h2az6bo1h9
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Mon 2009-08-17 11:35:07 -0500
message:
Add tests that we detect GraphCycleError
Turned out to be quite important, because otherwise KnownGraph.merge_sort()
ends up in an infinite loop w/ a GraphCycle.
(unlike topo_sort which pretty much just ignores those nodes.)
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py 2009-08-13 21:54:04 +0000
+++ b/bzrlib/_known_graph_py.py 2009-08-17 16:35:07 +0000
@@ -180,10 +180,9 @@
def merge_sort(self, tip_key):
"""Compute the merge sorted graph output."""
- # TODO: merge_sort doesn't handle ghosts (yet), figure out what to do
- # when we want it to.
as_parent_map = dict((node.key, node.parent_keys)
- for node in self._nodes.itervalues())
+ for node in self._nodes.itervalues()
+ if node.parent_keys is not None)
# We intentionally always generate revnos and never force the
# mainline_revisions
return tsort.merge_sort(as_parent_map, tip_key,
=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx 2009-08-17 16:11:22 +0000
+++ b/bzrlib/_known_graph_pyx.pyx 2009-08-17 16:35:07 +0000
@@ -448,13 +448,6 @@
return 0
-# cdef _MergeSortNode _get_ms_node(lst, Py_ssize_t pos):
-# cdef PyObject *temp_node
-#
-# temp_node = PyList_GET_ITEM(lst, pos)
-# return <_MergeSortNode>temp_node
-#
-
cdef class _MergeSorter:
"""This class does the work of computing the merge_sort ordering.
@@ -463,9 +456,9 @@
"""
# Current performance numbers for merge_sort(bzr_dev_parent_map):
- # 310ms tsort.merge_sort()
- # 92ms graph.KnownGraph().merge_sort()
- # 42ms kg.merge_sort()
+ # 302ms tsort.merge_sort()
+ # 91ms graph.KnownGraph().merge_sort()
+ # 41ms kg.merge_sort()
cdef KnownGraph graph
cdef object _depth_first_stack # list
@@ -537,7 +530,6 @@
cdef _MergeSortNode ms_node, ms_parent_node, ms_prev_node
cdef _KnownGraphNode node, parent_node, prev_node
- assert self._last_stack_item >= 0
node = _get_list_node(self._depth_first_stack, self._last_stack_item)
ms_node = <_MergeSortNode>node.extra
self._last_stack_item = self._last_stack_item - 1
@@ -616,6 +608,8 @@
# print ' ', self._scheduled_nodes
last_node = _get_list_node(self._depth_first_stack,
self._last_stack_item)
+ if last_node.gdfo == -1:
+ raise errors.GraphCycleError(self.graph._nodes)
ms_last_node = <_MergeSortNode>last_node.extra
if not ms_last_node.has_pending_parents():
# Processed all parents, pop this node
@@ -653,7 +647,6 @@
## # this indicates a cycle.
## raise errors.GraphCycleError(self._depth_first_stack)
- assert ms_next_node is not None
if next_node is ms_last_node.left_parent:
next_merge_depth = ms_last_node.merge_depth
else:
@@ -674,7 +667,7 @@
# We've set up the basic schedule, now we can continue processing the
# output.
- # TODO: This final loop costs us 41.4ms => 28.3ms (13ms, 30%) on
+ # TODO: This final loop costs us 40.0ms => 28.8ms (11ms, 25%) on
# bzr.dev, to convert the internal Object representation into a
# Tuple representation...
# 2ms is walking the data and computing revno tuples
@@ -689,16 +682,14 @@
ms_node = <_MergeSortNode>node.extra
if ms_node.revno_first == -1:
if ms_node.revno_second != -1:
- raise ValueError('Something wrong with: %s' % (ms_node,))
+ raise RuntimeError('Something wrong with: %s' % (ms_node,))
revno = (ms_node.revno_last,)
else:
revno = (ms_node.revno_first, ms_node.revno_second,
ms_node.revno_last)
- t = (sequence_number, node.key,
- ms_node.merge_depth, revno,
- ms_node.end_of_merge)
- PyList_Append(ordered, t)
- # PyList_Append(ordered, )
+ PyList_Append(ordered, (sequence_number, node.key,
+ ms_node.merge_depth, revno,
+ ms_node.end_of_merge))
# Get rid of the extra stored info
node.extra = None
sequence_number = sequence_number + 1
=== modified file 'bzrlib/tests/test__known_graph.py'
--- a/bzrlib/tests/test__known_graph.py 2009-08-17 15:39:48 +0000
+++ b/bzrlib/tests/test__known_graph.py 2009-08-17 16:35:07 +0000
@@ -708,3 +708,45 @@
(17, 'A', 0, (1,), True),
],
)
+
+ def test_ghost(self):
+ # merge_sort should be able to ignore ghosts
+ # A
+ # |
+ # B ghost
+ # |/
+ # C
+ self.assertSortAndIterate(
+ {'A': [],
+ 'B': ['A'],
+ 'C': ['B', 'ghost'],
+ },
+ 'C',
+ [(0, 'C', 0, (3,), False),
+ (1, 'B', 0, (2,), False),
+ (2, 'A', 0, (1,), True),
+ ])
+
+ def test_graph_cycle(self):
+ # merge_sort should fail with a simple error when a graph cycle is
+ # encountered.
+ #
+ # A
+ # |,-.
+ # B |
+ # | |
+ # C ^
+ # | |
+ # D |
+ # |'-'
+ # E
+ self.assertRaises(errors.GraphCycleError,
+ self.assertSortAndIterate,
+ {'A': [],
+ 'B': ['D'],
+ 'C': ['B'],
+ 'D': ['C'],
+ 'E': ['D'],
+ },
+ 'E',
+ [])
=== modified file 'bzrlib/tsort.py'
--- a/bzrlib/tsort.py 2009-08-17 15:38:52 +0000
+++ b/bzrlib/tsort.py 2009-08-17 16:35:07 +0000
@@ -606,7 +606,11 @@
# current search stack (but not completed or we would
# have hit the continue 4 lines up.
# this indicates a cycle.
- raise errors.GraphCycleError(node_name_stack)
+ if next_node_name in self._original_graph:
+ raise errors.GraphCycleError(node_name_stack)
+ else:
+ # This is just a ghost parent, ignore it
+ continue
next_merge_depth = 0
if is_left_subtree:
# a new child branch from name_stack[-1]
More information about the bazaar-commits
mailing list