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