Rev 2: Basic client-server graph mockup working. in file:///home/robertc/source/baz/plugins/netsim/trunk/
Robert Collins
robertc at robertcollins.net
Tue Apr 3 09:12:31 BST 2007
At file:///home/robertc/source/baz/plugins/netsim/trunk/
------------------------------------------------------------
revno: 2
revision-id: robertc at robertcollins.net-20070403081230-avzbku11jiowfzzj
parent: robertc at robertcollins.net-20070401222920-b8macm2o7934egao
committer: Robert Collins <robertc at robertcollins.net>
branch nick: trunk
timestamp: Tue 2007-04-03 18:12:30 +1000
message:
Basic client-server graph mockup working.
modified:
NEWS news-20070401222807-st2hllnh0o1674h2-2
missing.py missing.py-20070401222807-st2hllnh0o1674h2-6
tests/test_missing.py test_missing.py-20070401222807-st2hllnh0o1674h2-10
=== modified file 'NEWS'
--- a/NEWS 2007-04-01 22:29:20 +0000
+++ b/NEWS 2007-04-03 08:12:30 +0000
@@ -2,3 +2,4 @@
INTERNALS:
+ * Get a mockup of client-server graph missing logic working.
=== modified file 'missing.py'
--- a/missing.py 2007-04-01 22:29:20 +0000
+++ b/missing.py 2007-04-03 08:12:30 +0000
@@ -15,17 +15,94 @@
# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
#
-from bzrlib.graph import GraphDelta
+from bzrlib.graph import Graph, GraphDelta, NthNodeSelector
from bzrlib.revision import NULL_REVISION
"""Missing revision algorithms."""
-def server_step(wanted_heads=[], repository=None):
- """Step through the server portion of missing node selection."""
+def determine_diff_urls(cu, su):
+ import bzrlib.branch
+ cb = bzrlib.branch.Branch.open(cu)
+ sb = bzrlib.branch.Branch.open(su)
+ cb.lock_read()
+ cg = cb.repository.get_revision_graph(cb.last_revision()) # limited to the branch graph
+ # for testing of the algorithm; should not limit to use shared repository facilities.
+ result = server_step(wanted_heads=[sb.last_revision()], repository=sb.repository)
+ results = [result]
+ iteration = 0
+ send_length=len(sb.last_revision())
+ while result[0] != 'missing':
+ got_length = len(''.join(result[1].heads)) + len(''.join(result[1].cut_from)) + len(''.join(result[2].heads)) + len(''.join(result[2].cut_from)) + len(''.join(result[3]))
+ print iteration, 'sent=', send_length, 'recieved=', got_length
+ iteration += 1
+ present = [cg.__contains__(node) for node in result[3]]
+ send_length=got_length - len(''.join(result[3])) + (len(result[3])+1)/8 + len(sb.last_revision())
+ result = server_step(wanted_heads=[sb.last_revision()], repository=sb.repository,
+ remove_present_delta=result[1], absent_delta=result[2], present=present)
+ results.append(result)
+ got_length = len(''.join(result[1].heads)) + len(''.join(result[1].cut_from))
+ print iteration, 'sent=', send_length, 'recieved=', got_length
+ cb.unlock()
+ return result, results
+
+
+def server_step(wanted_heads=[], repository=None, limit=300, remove_present_delta=None, absent_delta=None, present=None):
+ """Step through the server portion of missing node selection.
+
+ :param wanted_heads: The heads of the graph the client is interested in.
+ e.g. the last_revision of the branch being pulled.
+ :param repository: The repository to get graph data from.
+ :param limit: A parameter to the NodeSelector to set the total count of
+ returned nodes.
+ :param remove_present_delta: A GraphDelta which will remove the known
+ present nodes from the full search graph.
+ :param absent_delta: A GraphDelta which will remove the known absent nodes
+ from the missing-or-unknown search graph.
+ """
+ # TODO: having proved the concept this needs a rewrite to be a single pass
+ # algorithm rather than using multiple temporary graphs.
assert repository is not None
for pos, head in enumerate(wanted_heads):
if head is None:
wanted_heads[pos] = NULL_REVISION
full_graph = repository.get_revision_graph_with_ghosts(wanted_heads)
- if not len(full_graph.get_ancestors()):
- return 'missing', GraphDelta()
+ if remove_present_delta:
+ assert absent_delta
+ assert present
+ missing_or_unknown_graph = remove_present_delta.apply_to(full_graph)
+ unknown_graph = absent_delta.apply_to(missing_or_unknown_graph)
+ # inferral:
+ last_nodes = zip(NthNodeSelector(limit).select(unknown_graph), present)
+ # now we have recreated the prior state we can apply new deltas
+ # to reduce the graphs
+ # firstly, remove more known-present nodes by making a delta.
+ present_nodes = [node[0] for node in last_nodes if node[1]]
+ new_remove_present_delta = GraphDelta()
+ new_remove_present_delta.cut_from = set(present_nodes)
+ # apply this to both the missing_or_unknown_graph and unknown_graph
+ # graphs
+ missing_or_unknown_graph = \
+ new_remove_present_delta.apply_to(missing_or_unknown_graph)
+ unknown_graph = new_remove_present_delta.apply_to(unknown_graph)
+ # now remove nodes from the unknown graph which are marked absent
+ absent_nodes = [node[0] for node in last_nodes if not node[1]]
+ # mutate in place behind the scenes, as the delta interface isn't
+ # able to pithily describe this operation yet.
+ pending = set(absent_nodes)
+ done = set()
+ while pending:
+ node = pending.pop()
+ done.add(node)
+ descendants = unknown_graph.get_descendants().pop(node)
+ unknown_graph._graph_ancestors.pop(node)
+ pending.update(set(descendants).difference(done))
+ else:
+ missing_or_unknown_graph = full_graph
+ unknown_graph = full_graph
+ if not len(unknown_graph.get_ancestors()):
+ # with no unknowns, missing_or_unknown_graph == missing_graph.
+ return 'missing', missing_or_unknown_graph.changes_from(full_graph)
+ nodes = NthNodeSelector(limit).select(unknown_graph)
+ missing_unknown_delta = missing_or_unknown_graph.changes_from(full_graph)
+ unknown_delta = unknown_graph.changes_from(missing_or_unknown_graph)
+ return 'unknown', missing_unknown_delta, unknown_delta, nodes
=== modified file 'tests/test_missing.py'
--- a/tests/test_missing.py 2007-04-01 22:29:20 +0000
+++ b/tests/test_missing.py 2007-04-03 08:12:30 +0000
@@ -31,6 +31,42 @@
# client has nothing to send except the branch tip
result = server_step(wanted_heads=[server_tree.last_revision()],
repository=server_tree.branch.repository)
- # and the process should be finished now
+ # and the process should be finished now - everything is missing
expected_result = ('missing', GraphDelta())
self.assertEqual(expected_result, result)
+
+ def test_graph_size_under_selection_count(self):
+ # the entire graph should be returned for the first lookup.
+ server_tree = self.make_branch_and_tree('server')
+ rev1id = server_tree.commit('first post')
+ # client has nothing to send except the branch tip
+ result = server_step(wanted_heads=[server_tree.last_revision()],
+ repository=server_tree.branch.repository, limit=1)
+ # we should get back an unknown result
+ # with remove_present_delta of nothing, and absent delta of nothing
+ remove_present_delta = GraphDelta()
+ absent_delta = GraphDelta()
+ expected_selection = [rev1id]
+ expected_result = ('unknown', remove_present_delta, absent_delta,
+ expected_selection)
+ self.assertEqual(expected_result, result)
+ # now we send back our lookup result: Lets claim that we have rev1id
+ new_result = server_step(wanted_heads=[server_tree.last_revision()],
+ repository=server_tree.branch.repository,
+ limit=1, remove_present_delta=result[1], absent_delta=result[2],
+ present=[True])
+ # we should get back a final result with a selected empty graph
+ missing_delta = GraphDelta()
+ missing_delta.cut_from = set([rev1id])
+ expected_result = ('missing', missing_delta)
+ self.assertEqual(expected_result, new_result)
+ # alternatively, we could claim that we dont have rev1id, meaning
+ # we dont have anything.
+ new_result = server_step(wanted_heads=[server_tree.last_revision()],
+ repository=server_tree.branch.repository,
+ limit=1, remove_present_delta=result[1], absent_delta=result[2],
+ present=[False])
+ # we should get back a final result which includes the whole graph
+ missing_delta = GraphDelta()
+ expected_result = ('missing', missing_delta)
+ self.assertEqual(expected_result, new_result)
More information about the bazaar-commits
mailing list