Rev 2392: Basic graph delta support functional, using a new graph get_heads method. in file:///home/robertc/source/baz/netsim/

Robert Collins robertc at robertcollins.net
Sun Apr 1 08:13:25 BST 2007


At file:///home/robertc/source/baz/netsim/

------------------------------------------------------------
revno: 2392
revision-id: robertc at robertcollins.net-20070401071322-2wi0ecpdtf0jrjm0
parent: robertc at robertcollins.net-20070401063117-71od8scu0te38npy
committer: Robert Collins <robertc at robertcollins.net>
branch nick: netsim
timestamp: Sun 2007-04-01 17:13:22 +1000
message:
  Basic graph delta support functional, using a new graph get_heads method.
modified:
  bzrlib/graph.py                graph.py-20050905070950-b47dce53236c5e48
  bzrlib/tests/test_graph.py     testgraph.py-20050905070950-42e6c958106610fd
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2007-04-01 06:31:17 +0000
+++ b/bzrlib/graph.py	2007-04-01 07:13:22 +0000
@@ -169,14 +169,29 @@
         """Return a dictionary of graph node:child_node:distance entries."""
         return dict(self._graph_descendants.items())
 
+    def get_heads(self):
+        """Determine the heads of the graph."""
+        return set([node for node, descendants in
+            self._graph_descendants.items() if not descendants])
+
 
 class GraphDelta(object):
     """A delta between two DAG's. 
 
     Currently this requires that the from DAG be a supergraph of the to DAG.
     This restriction may be lifted in the future.
+
+    Public attributes: 
+    heads: A list of heads that the subgraph should start from. An empty list
+        means start from the heads of the from graph when applying the delta.
+    cut_from: A list of nodes to cut out of the output. An empty list means
+        cut nothing.
     """
 
+    def __init__(self):
+        self.heads = set()
+        self.cut_from = set()
+
     def __eq__(self, other):
         return isinstance(other, GraphDelta) and self.__dict__ == other.__dict__
 
@@ -185,14 +200,60 @@
         
         :return: A new graph derived from from_ and this delta.
         """
-        return Graph()
+        result = Graph()
+        if self.heads:
+            pending = set(self.heads)
+        else:
+            pending = set(from_.get_heads())
+        cut_from = set(self.cut_from) # in case its a list
+        ancestors = from_.get_ancestors()
+        while pending:
+            node = pending.pop()
+            if node not in cut_from:
+                result.add_node(node, ancestors[node])
+        return result
 
     @classmethod
     def _changes_from(cls, from_, to):
         """Construct a delta from from_ to to."""
         result = GraphDelta()
-        from_nodes = set(from_.get_ancestors())
+        ancestors = from_.get_ancestors()
         to_nodes = set(to.get_ancestors())
-        if to_nodes.difference(from_nodes):
+        if to_nodes.difference(ancestors):
             raise errors.NotSubGraph(from_, to)
+        result.heads = to.get_heads()
+        # if the heads list is equal to the from_ heads list, 
+        # omit it. XXX: this special casing may be a pointless
+        # optimisation.
+        if result.heads == from_.get_heads():
+            result.heads = set([])
+         
+        # start walking from all the nodes in to.
+        # when we hit a node not in to, add it to cut_from.
+        # when we hit a node in to, remove it from heads.
+        # discount ghosts in parent lists.
+        # special case, symmetrical with the apply_to use of the 
+        # source graph heads when the to graph is empty:
+        # we use the source graph heads as the cut list giving
+        # an instant empty graph.
+        if not to_nodes:
+            result.cut_from = from_.get_heads()
+            return result
+        pending = set(result.heads)
+        while pending:
+            node = pending.pop()
+            node_parents = ancestors[node]
+            for parent in node_parents:
+                if parent in from_.ghosts:
+                    continue
+                if parent not in to_nodes:
+                    result.cut_from.add(parent)
+                    continue
+                if parent in result.heads:
+                    result.heads.remove(parent)
+                pending.add(parent)
+        # remove heads that 
         return result
+
+    def __repr__(self):
+        return "GraphDelta heads=%r, cut_from=%r" % (self.heads, self.cut_from)

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2007-04-01 06:31:17 +0000
+++ b/bzrlib/tests/test_graph.py	2007-04-01 07:13:22 +0000
@@ -80,6 +80,33 @@
         self.assertEqual({'ghost': {'rev1': 1}, 'rev1': {}},
                          graph.get_descendants())
 
+    def test_get_heads(self):
+        # graph objects allow querying for their heads. 
+        # test empty graph, a partitioned graph, and a graph
+        # with a unmerged branch
+        # empty
+        graph = Graph()
+        self.assertEqual(set(), graph.get_heads())
+        # simple
+        graph.add_node('A', [])
+        self.assertEqual(set(['A']), graph.get_heads())
+        graph.add_node('B', ['A'])
+        self.assertEqual(set(['B']), graph.get_heads())
+        # simple, partitioned
+        graph.add_node('C', [])
+        self.assertEqual(set(['B', 'C']), graph.get_heads())
+        graph.add_node('D', ['C'])
+        self.assertEqual(set(['B', 'D']), graph.get_heads())
+        # joined up parititons
+        graph.add_node('E', ['D', 'B'])
+        self.assertEqual(set(['E']), graph.get_heads())
+        # unmerged branch
+        graph.add_node('F', ['B'])
+        self.assertEqual(set(['E', 'F']), graph.get_heads())
+        # and merge it
+        graph.add_node('G', ['E', 'F'])
+        self.assertEqual(set(['G']), graph.get_heads())
+
 
 class TestGraphDelta(TestCase):
 
@@ -112,4 +139,15 @@
         graph_from.add_node('A', [])
         graph_to = Graph()
         result = GraphDelta()
+        # keeping the implied heads lets the graph-to-build be maintained
+        # outside the core routine; this is cleaner I think for now.
+        result.cut_from = set(['A'])
+        self.check_delta(result, graph_from, graph_to)
+
+    def testSmallIdentityGraph(self):
+        graph_from = Graph()
+        graph_from.add_node('A', [])
+        graph_to = Graph()
+        graph_to.add_node('A', [])
+        result = GraphDelta()
         self.check_delta(result, graph_from, graph_to)



More information about the bazaar-commits mailing list