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