Rev 4532: Found a bug in the pure-python KnownGraph code. in http://bazaar.launchpad.net/~jameinel/bzr/1.17-rework-annotate

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.17-rework-annotate

------------------------------------------------------------
revno: 4532
revision-id: john at arbash-meinel.com-20090708205810-mq7e81jnpccob2qa
parent: john at arbash-meinel.com-20090708170903-nea7ru9bh2hdtf1w
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.17-rework-annotate
timestamp: Wed 2009-07-08 15:58:10 -0500
message:
  Found a bug in the pure-python KnownGraph code.
  
  If a tail is reached directly, we were failing to add it to the possible
  tails set. (Uncommon in real-world, but happening in the test suite.)
  Just switching the code back to not pre-computing the tail list, same
  as we do for the pyrex version.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py	2009-06-19 17:40:59 +0000
+++ b/bzrlib/_known_graph_py.py	2009-07-08 20:58:10 +0000
@@ -63,18 +63,12 @@
         - ghosts will have a parent_keys = None,
         - all nodes found will also have .child_keys populated with all known
           child_keys,
-        - self._tails will list all the nodes without parents.
         """
-        tails = self._tails = set()
         nodes = self._nodes
         for key, parent_keys in parent_map.iteritems():
             if key in nodes:
                 node = nodes[key]
                 node.parent_keys = parent_keys
-                if parent_keys:
-                    # This node has been added before being seen in parent_map
-                    # (see below)
-                    tails.remove(node)
             else:
                 node = _KnownGraphNode(key, parent_keys)
                 nodes[key] = node
@@ -84,17 +78,18 @@
                 except KeyError:
                     parent_node = _KnownGraphNode(parent_key, None)
                     nodes[parent_key] = parent_node
-                    # Potentially a tail, if we're wrong we'll remove it later
-                    # (see above)
-                    tails.add(parent_node)
                 parent_node.child_keys.append(key)
 
+    def _find_tails(self):
+        return [node for node in self._nodes.itervalues()
+                if not node.parent_keys]
+
     def _find_gdfo(self):
         nodes = self._nodes
         known_parent_gdfos = {}
         pending = []
 
-        for node in self._tails:
+        for node in self._find_tails():
             node.gdfo = 1
             pending.append(node)
 
@@ -144,9 +139,6 @@
             # No or only one candidate
             return frozenset(candidate_nodes)
         heads_key = frozenset(candidate_nodes)
-        if heads_key != frozenset(keys):
-            # Mention duplicates
-            note('%s != %s', heads_key, frozenset(keys))
         # Do we have a cached result ?
         try:
             heads = self._known_heads[heads_key]

=== modified file 'bzrlib/tests/test__known_graph.py'
--- a/bzrlib/tests/test__known_graph.py	2009-06-23 19:39:42 +0000
+++ b/bzrlib/tests/test__known_graph.py	2009-07-08 20:58:10 +0000
@@ -63,6 +63,16 @@
 CompiledKnownGraphFeature = _CompiledKnownGraphFeature()
 
 
+#  a
+#  |\
+#  b |
+#  | |
+#  c |
+#   \|
+#    d
+alt_merge = {'a': [], 'b': ['a'], 'c': ['b'], 'd': ['a', 'c']}
+
+
 class TestKnownGraph(tests.TestCase):
 
     module = None # Set by load_tests
@@ -203,6 +213,10 @@
         self.assertEqual(set(['w', 'q']), graph.heads(['w', 's', 'q']))
         self.assertEqual(set(['z']), graph.heads(['s', 'z']))
 
+    def test_heads_alt_merge(self):
+        graph = self.make_known_graph(alt_merge)
+        self.assertEqual(set(['c']), graph.heads(['a', 'c']))
+
     def test_heads_with_ghost(self):
         graph = self.make_known_graph(test_graph.with_ghost)
         self.assertEqual(set(['e', 'g']), graph.heads(['e', 'g']))