Rev 2396: Finish unit tests for creating and applying GraphDelta's, fixing a bug with prefix-deltas, and update the walkthroughts in the server design documentation. in file:///home/robertc/source/baz/netsim/
Robert Collins
robertc at robertcollins.net
Sun Apr 1 11:08:20 BST 2007
At file:///home/robertc/source/baz/netsim/
------------------------------------------------------------
revno: 2396
revision-id: robertc at robertcollins.net-20070401100816-j0298tbd10xjsguv
parent: robertc at robertcollins.net-20070401073652-xhjw2gmfgjsv4tvi
committer: Robert Collins <robertc at robertcollins.net>
branch nick: netsim
timestamp: Sun 2007-04-01 20:08:16 +1000
message:
Finish unit tests for creating and applying GraphDelta's, fixing a bug with prefix-deltas, and update the walkthroughts in the server design documentation.
modified:
bzrlib/graph.py graph.py-20050905070950-b47dce53236c5e48
bzrlib/tests/test_graph.py testgraph.py-20050905070950-42e6c958106610fd
doc/design/server.txt server.txt-20070401020531-rqa7d77i22idnj78-2
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2007-04-01 07:31:18 +0000
+++ b/bzrlib/graph.py 2007-04-01 10:08:16 +0000
@@ -226,7 +226,8 @@
to_nodes = set(to.get_ancestors())
if to_nodes.difference(ancestors):
raise errors.NotSubGraph(from_, to)
- result.heads = to.get_heads()
+ to_heads = to.get_heads()
+ result.heads = to_heads
# if the heads list is equal to the from_ heads list,
# omit it. XXX: this special casing may be a pointless
# optimisation.
@@ -244,7 +245,7 @@
if not to_nodes:
result.cut_from = from_.get_heads()
return result
- pending = set(result.heads)
+ pending = set(to_heads)
while pending:
node = pending.pop()
node_parents = ancestors[node]
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2007-04-01 07:36:52 +0000
+++ b/bzrlib/tests/test_graph.py 2007-04-01 10:08:16 +0000
@@ -169,6 +169,115 @@
result.cut_from = set(['E'])
self.check_delta(result, graph_from, graph_to)
+ def testMiddleSegmentWithMerges(self):
+ # grabbing a delta where the to graph is totally interior and contains embedded merges.
+ graph_from = Graph()
+ graph_from.add_node('A', ['B'])
+ graph_from.add_node('B', ['C', 'D'])
+ graph_from.add_node('C', ['E'])
+ graph_from.add_node('D', ['E'])
+ graph_from.add_node('E', ['F'])
+ graph_from.add_node('F', [])
+ graph_to = Graph()
+ graph_to.add_node('B', ['C', 'D'])
+ graph_to.add_node('C', ['E'])
+ graph_to.add_node('D', ['E'])
+ graph_to.add_node('E', ['F'])
+ result = GraphDelta()
+ result.heads = set(['B'])
+ result.cut_from = set(['F'])
+ self.check_delta(result, graph_from, graph_to)
+
+ def testMiddleSegmentWithMergeStart(self):
+ # grabbing a delta where the to graph is totally interior and contains the start
+ # of a branch in the graph
+ graph_from = Graph()
+ graph_from.add_node('A', ['B'])
+ graph_from.add_node('B', ['C', 'D'])
+ graph_from.add_node('C', ['E'])
+ graph_from.add_node('D', ['E'])
+ graph_from.add_node('E', ['F'])
+ graph_from.add_node('F', [])
+ graph_to = Graph()
+ graph_to.add_node('C', ['E'])
+ graph_to.add_node('D', ['E'])
+ graph_to.add_node('E', ['F'])
+ result = GraphDelta()
+ result.heads = set(['C', 'D'])
+ result.cut_from = set(['F'])
+ self.check_delta(result, graph_from, graph_to)
+
+ def testMiddleSegmentWithMergeEnd(self):
+ # grabbing a delta where the to graph is totally interior and contains the end
+ # of a branch in the graph
+ graph_from = Graph()
+ graph_from.add_node('A', ['B'])
+ graph_from.add_node('B', ['C', 'D'])
+ graph_from.add_node('C', ['E'])
+ graph_from.add_node('D', ['E'])
+ graph_from.add_node('E', ['F'])
+ graph_from.add_node('F', [])
+ graph_to = Graph()
+ graph_to.add_node('B', ['C', 'D'])
+ result = GraphDelta()
+ result.heads = set(['B'])
+ result.cut_from = set(['C', 'D'])
+ self.check_delta(result, graph_from, graph_to)
+
+ def testMiddleSegmentWithPartitionedMerge(self):
+ # grabbing a delta where the to graph is totally interior and contains both
+ # sides of a branch and merge, but not the start or end.
+ graph_from = Graph()
+ graph_from.add_node('A', ['B'])
+ graph_from.add_node('B', ['C', 'D'])
+ graph_from.add_node('C', ['E'])
+ graph_from.add_node('D', ['E'])
+ graph_from.add_node('E', ['F'])
+ graph_from.add_node('F', [])
+ graph_to = Graph()
+ graph_to.add_node('C', ['E'])
+ graph_to.add_node('D', ['E'])
+ result = GraphDelta()
+ result.heads = set(['C', 'D'])
+ result.cut_from = set(['E'])
+ self.check_delta(result, graph_from, graph_to)
+
+ def testMiddleSegmentWithLeftSideMerge(self):
+ # grabbing a delta where the to graph is totally interior and contains the left
+ # side of a branch and merge but not the right side.
+ graph_from = Graph()
+ graph_from.add_node('A', ['B'])
+ graph_from.add_node('B', ['C', 'D'])
+ graph_from.add_node('C', ['E'])
+ graph_from.add_node('D', ['E'])
+ graph_from.add_node('E', ['F'])
+ graph_from.add_node('F', [])
+ graph_to = Graph()
+ graph_to.add_node('C', ['E'])
+ graph_to.add_node('E', ['F'])
+ result = GraphDelta()
+ result.heads = set(['C'])
+ result.cut_from = set(['F'])
+ self.check_delta(result, graph_from, graph_to)
+
+ def testMiddleSegmentWithRightSideMerge(self):
+ # grabbing a delta where the to graph is totally interior and contains the right
+ # side of a branch and merge but not the left side.
+ graph_from = Graph()
+ graph_from.add_node('A', ['B'])
+ graph_from.add_node('B', ['C', 'D'])
+ graph_from.add_node('C', ['E'])
+ graph_from.add_node('D', ['E'])
+ graph_from.add_node('E', ['F'])
+ graph_from.add_node('F', [])
+ graph_to = Graph()
+ graph_to.add_node('D', ['E'])
+ graph_to.add_node('E', ['F'])
+ result = GraphDelta()
+ result.heads = set(['D'])
+ result.cut_from = set(['F'])
+ self.check_delta(result, graph_from, graph_to)
+
def testEndOfGraph(self):
# grabbing a delta from A->B->C->D->E,F to C->D->E,F:
graph_from = Graph()
@@ -205,3 +314,71 @@
result = GraphDelta()
result.heads = set(['D', 'E'])
self.check_delta(result, graph_from, graph_to)
+
+ def testStartOfGraph(self):
+ # grabbing a delta from A->B->C to A->B:
+ graph_from = Graph()
+ graph_from.add_node('A', ['B'])
+ graph_from.add_node('B', ['C'])
+ graph_from.add_node('C', [])
+ graph_to = Graph()
+ graph_to.add_node('A', ['B'])
+ graph_to.add_node('B', ['C'])
+ result = GraphDelta()
+ result.cut_from = set(['C'])
+ self.check_delta(result, graph_from, graph_to)
+
+ def testStartOfGraphMultipleHeads(self):
+ # grabbing a delta which grabs the top of a graph with multiple hedas.
+ graph_from = Graph()
+ graph_from.add_node('A1', ['B1'])
+ graph_from.add_node('A2', ['B2'])
+ graph_from.add_node('B1', ['C'])
+ graph_from.add_node('B2', ['C'])
+ graph_from.add_node('C', [])
+ graph_to = Graph()
+ graph_to.add_node('A1', ['B1'])
+ graph_to.add_node('A2', ['B2'])
+ graph_to.add_node('B1', ['C'])
+ graph_to.add_node('B2', ['C'])
+ result = GraphDelta()
+ result.cut_from = set(['C'])
+ self.check_delta(result, graph_from, graph_to)
+
+ def testStartOfPartitionedGraph(self):
+ # grabbing a delta which grabs the top of a partitioned graph.
+ graph_from = Graph()
+ graph_from.add_node('A1', ['B1'])
+ graph_from.add_node('A2', ['B2'])
+ graph_from.add_node('B1', ['C1'])
+ graph_from.add_node('B2', ['C2'])
+ graph_from.add_node('C1', [])
+ graph_from.add_node('C2', [])
+ graph_to = Graph()
+ graph_to.add_node('A1', ['B1'])
+ graph_to.add_node('A2', ['B2'])
+ graph_to.add_node('B1', ['C1'])
+ graph_to.add_node('B2', ['C2'])
+ result = GraphDelta()
+ result.cut_from = set(['C1', 'C2'])
+ self.check_delta(result, graph_from, graph_to)
+
+ def testOneSideOfPartitionedGraph(self):
+ # grabbing a delta which grabs one side of a partitioned graph.
+ graph_from = Graph()
+ graph_from.add_node('A1', ['B1'])
+ graph_from.add_node('A2', ['B2'])
+ graph_from.add_node('B1', ['C1'])
+ graph_from.add_node('B2', ['C2'])
+ graph_from.add_node('C1', [])
+ graph_from.add_node('C2', [])
+ graph_to = Graph()
+ graph_to.add_node('A1', ['B1'])
+ graph_to.add_node('B1', ['C1'])
+ result = GraphDelta()
+ result.heads = set(['A1'])
+ # we only need to cut at C1 because the heads list removes the other
+ # partition implicitly.
+ result.cut_from = set(['C1'])
+ self.check_delta(result, graph_from, graph_to)
+
=== modified file 'doc/design/server.txt'
--- a/doc/design/server.txt 2007-04-01 06:31:17 +0000
+++ b/doc/design/server.txt 2007-04-01 10:08:16 +0000
@@ -87,12 +87,13 @@
Client message 1:
get_missing()
response:
-delta=(HEADS=[A], STOPS=[])
+unknowns=(HEADS=[], STOPS=[])
sample=(0, [A])
Client message 2:
-get_missing((HEADS=[A], STOPS=[]), (0, [False]))
+get_missing((HEADS=[], STOPS=[]), (0, [False]))
response:
-'complete', delta=(HEADS=[A], STOPS=[])
+'complete', missing=(HEADS=[], STOPS=[])
+
Server Graph: {A:[], B:[A], C:[A], D:[B, C]}
Client Graph: {A:[], B:[A], E:[B]}
@@ -100,17 +101,17 @@
Client message 1:
get_missing
response:
-delta=(HEADS=[E], STOPS=[])
+unknown=(HEADS=[], STOPS=[])
sample=(0, [A, D])
client message 2:
-get_missing((HEADS=[E], STOPS=[]), (0, [True, False]))
+get_missing((HEADS=[], STOPS=[]), (0, [True, False]))
response:
-delta=(HEADS=[B,C], STOPS=[A])
+unknown=(HEADS=[B, C], STOPS=[A])
sample=(0, [B, C])
client message 3:
get_missing((HEADS=[B,C], STOPS=[A]), (0, [True, False]))
response:
-'complete', delta=(HEADS=[C], STOPS=[C])
+'complete', missing=(HEADS=[], STOPS=[B, A])
More information about the bazaar-commits
mailing list