Rev 3100: Add a failing test demonstrating a history-shortcut problem without walking off the graph in http://bzr.arbash-meinel.com/branches/bzr/0.93-dev/graph_update
John Arbash Meinel
john at arbash-meinel.com
Wed Dec 12 15:21:06 GMT 2007
At http://bzr.arbash-meinel.com/branches/bzr/0.93-dev/graph_update
------------------------------------------------------------
revno: 3100
revision-id:john at arbash-meinel.com-20071212152039-asn1cpp5l2nin0sf
parent: john at arbash-meinel.com-20071209021647-pk4jiyy05x7o9e4m
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_update
timestamp: Wed 2007-12-12 09:20:39 -0600
message:
Add a failing test demonstrating a history-shortcut problem without walking off the graph
modified:
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
-------------- next part --------------
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2007-12-08 16:29:28 +0000
+++ b/bzrlib/tests/test_graph.py 2007-12-12 15:20:39 +0000
@@ -161,6 +161,39 @@
'd':['c'], 'e':['c'], 'f':['a', 'd'],
'g':['a', 'e']}
+# Complex shortcut
+# This has a failure mode in that a shortcut will find some nodes in common,
+# but the common searcher won't have time to find that one branche is actually
+# in common. The extra nodes at the beginning are because we want to avoid
+# walking off the graph. Specifically, node G should be considered common, but
+# is likely to be seen by M long before the common searcher finds it.
+#
+# NULL_REVISION
+# |
+# a
+# |
+# b
+# |
+# c
+# |
+# d
+# |\
+# e f
+# | |\
+# | g h
+# |/| |
+# i j |
+# | | |
+# | k |
+# | | |
+# | l |
+# |/|/
+# m n
+complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
+ 'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
+ 'i':['e', 'g'], 'j':['g'], 'k':['j'],
+ 'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
+
# Shortcut with extra root
# We have a long history shortcut, and an extra root, which is why we can't
# stop searchers based on seeing NULL_REVISION
@@ -388,6 +421,11 @@
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
graph.find_difference('f', 'g'))
+ def test_graph_difference_complex_shortcut(self):
+ graph = self.make_graph(complex_shortcut)
+ self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
+ graph.find_difference('m', 'n'))
+
def test_graph_difference_shortcut_extra_root(self):
graph = self.make_graph(shortcut_extra_root)
self.assertEqual((set(['e']), set(['f', 'g'])),
More information about the bazaar-commits
mailing list