Rev 4839: Implement KnownGraph.add_node(), along with tests, for the python version. in http://bazaar.launchpad.net/~jameinel/bzr/2.1.0b4-kg-add-node
John Arbash Meinel
john at arbash-meinel.com
Mon Nov 30 16:57:57 GMT 2009
At http://bazaar.launchpad.net/~jameinel/bzr/2.1.0b4-kg-add-node
------------------------------------------------------------
revno: 4839
revision-id: john at arbash-meinel.com-20091130165755-4hia7he55tjv7180
parent: pqm at pqm.ubuntu.com-20091130114732-azinhhr5xf5rscez
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.1.0b4-kg-add-node
timestamp: Mon 2009-11-30 10:57:55 -0600
message:
Implement KnownGraph.add_node(), along with tests, for the python version.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py 2009-09-07 14:19:05 +0000
+++ b/bzrlib/_known_graph_py.py 2009-11-30 16:57:55 +0000
@@ -17,6 +17,7 @@
"""Implementation of Graph algorithms when we have already loaded everything.
"""
+from collections import deque
from bzrlib import (
errors,
revision,
@@ -132,6 +133,56 @@
# Update known_parent_gdfos for a key we couldn't process
known_parent_gdfos[child_key] = known_gdfo
+ def add_node(self, key, parent_keys):
+ """Add a new node to the graph."""
+ nodes = self._nodes
+ if key in nodes:
+ node = nodes[key]
+ if node.parent_keys is None:
+ node.parent_keys = parent_keys
+ elif parent_keys == node.parent_keys:
+ return # Identical content
+ else:
+ raise ValueError('Parent key mismatch, existing node %s'
+ ' has parents of %s not %s'
+ % (key, node.parent_keys, parent_keys))
+ else:
+ node = _KnownGraphNode(key, parent_keys)
+ nodes[key] = node
+ parent_gdfo = 0
+ for parent_key in parent_keys:
+ try:
+ parent_node = nodes[parent_key]
+ except KeyError:
+ parent_node = _KnownGraphNode(parent_key, None)
+ # Ghosts and roots have gdfo 1
+ parent_node.gdfo = 1
+ nodes[parent_key] = parent_node
+ if parent_gdfo < parent_node.gdfo:
+ parent_gdfo = parent_node.gdfo
+ parent_node.child_keys.append(key)
+ node.gdfo = parent_gdfo + 1
+ # Now fill the gdfo to all children
+ # Note that this loop is slightly inefficient, in that we may visit the
+ # same child (and its decendents) more than once, however, it is
+ # 'efficient' in that we only walk to nodes that would be updated,
+ # rather than all nodes
+ # We use a deque rather than a simple list stack, to go for BFD rather
+ # than DFD. So that if a longer path is possible, we walk it before we
+ # get to the final child
+ pending = deque([node])
+ while pending:
+ node = pending.popleft()
+ next_gdfo = node.gdfo + 1
+ for child_key in node.child_keys:
+ child = nodes[child_key]
+ if child.gdfo < next_gdfo:
+ # This child is being updated, we need to check its
+ # children
+ child.gdfo = next_gdfo
+ pending.append(child)
+
+
def heads(self, keys):
"""Return the heads from amongst keys.
=== modified file 'bzrlib/tests/test__known_graph.py'
--- a/bzrlib/tests/test__known_graph.py 2009-09-07 14:19:05 +0000
+++ b/bzrlib/tests/test__known_graph.py 2009-11-30 16:57:55 +0000
@@ -154,6 +154,66 @@
self.assertGDFO(graph, 'a', 5)
self.assertGDFO(graph, 'c', 5)
+ def test_add_existing_node(self):
+ graph = self.make_known_graph(test_graph.ancestry_1)
+ # Add a node that already exists with identical content
+ # This is a 'no-op'
+ self.assertGDFO(graph, 'rev4', 5)
+ graph.add_node('rev4', ['rev3', 'rev2b'])
+ self.assertGDFO(graph, 'rev4', 5)
+
+ def test_add_node_with_ghost_parent(self):
+ graph = self.make_known_graph(test_graph.ancestry_1)
+ graph.add_node('rev5', ['rev2b', 'revGhost'])
+ self.assertGDFO(graph, 'rev5', 4)
+ self.assertGDFO(graph, 'revGhost', 1)
+
+ def test_add_new_root(self):
+ graph = self.make_known_graph(test_graph.ancestry_1)
+ graph.add_node('rev5', [])
+ self.assertGDFO(graph, 'rev5', 1)
+
+ def test_add_with_all_ghost_parents(self):
+ graph = self.make_known_graph(test_graph.ancestry_1)
+ graph.add_node('rev5', ['ghost'])
+ self.assertGDFO(graph, 'rev5', 2)
+ self.assertGDFO(graph, 'ghost', 1)
+
+ def test_gdfo_after_add_node(self):
+ graph = self.make_known_graph(test_graph.ancestry_1)
+ self.assertEqual([], graph.get_child_keys('rev4'))
+ graph.add_node('rev5', ['rev4'])
+ self.assertEqual(['rev4'], graph.get_parent_keys('rev5'))
+ self.assertEqual(['rev5'], graph.get_child_keys('rev4'))
+ self.assertEqual([], graph.get_child_keys('rev5'))
+ self.assertGDFO(graph, 'rev5', 6)
+ graph.add_node('rev6', ['rev2b'])
+ graph.add_node('rev7', ['rev6'])
+ graph.add_node('rev8', ['rev7', 'rev5'])
+ self.assertGDFO(graph, 'rev5', 6)
+ self.assertGDFO(graph, 'rev6', 4)
+ self.assertGDFO(graph, 'rev7', 5)
+ self.assertGDFO(graph, 'rev8', 7)
+
+ def test_fill_in_ghost(self):
+ graph = self.make_known_graph(test_graph.with_ghost)
+ # Add in a couple nodes and then fill in the 'ghost' so that it should
+ # cause renumbering of children nodes
+ graph.add_node('x', [])
+ graph.add_node('y', ['x'])
+ graph.add_node('z', ['y'])
+ graph.add_node('g', ['z'])
+ self.assertGDFO(graph, 'f', 2)
+ self.assertGDFO(graph, 'e', 3)
+ self.assertGDFO(graph, 'x', 1)
+ self.assertGDFO(graph, 'y', 2)
+ self.assertGDFO(graph, 'z', 3)
+ self.assertGDFO(graph, 'g', 4)
+ self.assertGDFO(graph, 'b', 4)
+ self.assertGDFO(graph, 'd', 5)
+ self.assertGDFO(graph, 'a', 5)
+ self.assertGDFO(graph, 'c', 6)
+
class TestKnownGraphHeads(TestCaseWithKnownGraph):
More information about the bazaar-commits
mailing list