Fixed graph rep to handle multiple heads correctly. I had to change the topkey format so repositories inserted with earlier versions won't work with the new code.
diff --git a/infocalypse/__init__.py b/infocalypse/__init__.py
--- a/infocalypse/__init__.py
+++ b/infocalypse/__init__.py
@@ -125,6 +125,7 @@ Post to freenet group on FMS.
import os
+from binascii import hexlify
from mercurial import commands, util
from infcmds import get_config_info, execute_create, execute_pull, \
@@ -135,13 +136,16 @@ def set_target_version(ui_, repo, opts,
revs = opts.get('rev') or None
if not revs is None:
- if len(revs) > 1:
- raise util.Abort("Only a single -r version is supported. ")
- rev = revs[0]
- ctx = repo[rev] # Fail if we don't have the rev.
- params['TO_VERSION'] = rev
- if ctx != repo['tip']:
- ui_.status(msg_fmt % rev)
+ for rev in revs:
+ repo.changectx(rev) # Fail if we don't have the rev.
+
+ params['TO_VERSIONS'] = tuple(revs)
+ ui_.status(msg_fmt % ' '.join([ver[:12] for ver in revs]))
+ else:
+ # REDFLAG: get rid of default versions arguments?
+ params['TO_VERSIONS'] = tuple([hexlify(head) for head in repo.heads()])
+ #print "set_target_version -- using all head"
+ #print params['TO_VERSIONS']
def infocalypse_create(ui_, repo, **opts):
""" Create a new Infocalypse repository in Freenet. """
@@ -154,7 +158,7 @@ def infocalypse_create(ui_, repo, **opts
return
set_target_version(ui_, repo, opts, params,
- "Only inserting to version: %s\n")
+ "Only inserting to version(s): %s\n")
params['INSERT_URI'] = insert_uri
execute_create(ui_, repo, params, stored_cfg)
@@ -230,7 +234,7 @@ def infocalypse_push(ui_, repo, **opts):
return
set_target_version(ui_, repo, opts, params,
- "Only pushing to version: %s\n")
+ "Only pushing to version(s): %s\n")
params['INSERT_URI'] = insert_uri
#if opts['requesturi'] != '':
# # DOESN'T search the insert uri index.
@@ -260,6 +264,7 @@ AGGRESSIVE_OPT = [('', 'aggressive', Non
NOSEARCH_OPT = [('', 'nosearch', None, 'use USK version in URI'), ]
# Allow mercurial naming convention for command table.
# pylint: disable-msg=C0103
+
cmdtable = {
"fn-pull": (infocalypse_pull,
[('', 'uri', '', 'request URI to pull from'),]
diff --git a/infocalypse/bundlecache.py b/infocalypse/bundlecache.py
--- a/infocalypse/bundlecache.py
+++ b/infocalypse/bundlecache.py
@@ -26,7 +26,10 @@ import random
from mercurial import commands
+from fcpconnection import sha1_hexdigest
+
from graph import FIRST_INDEX, FREENET_BLOCK_LEN, MAX_REDUNDANT_LENGTH
+from graphutil import get_rollup_bounds
def make_temp_file(temp_dir):
""" Make a temporary file name. """
@@ -71,10 +74,17 @@ class BundleCache:
def get_bundle_path(self, index_pair):
""" INTERNAL: Get the full path to a bundle file for the given edge. """
- start_info = self.graph.index_table[index_pair[0]]
- end_info = self.graph.index_table[index_pair[1]]
- return os.path.join(self.base_dir, "_tmp_%s_%s.hg"
- % (start_info[1], end_info[1]))
+ bundle_id = sha1_hexdigest(
+ ''.join(self.graph.index_table[index_pair[0]][0])
+ + '|' # hmmm really needed?
+ +''.join(self.graph.index_table[index_pair[0]][1])
+
+ +''.join(self.graph.index_table[index_pair[1]][0])
+ + '|' # hmmm really needed?
+ +''.join(self.graph.index_table[index_pair[1]][1])
+ )
+
+ return os.path.join(self.base_dir, "_tmp_%s.hg" % bundle_id)
def get_cached_bundle(self, index_pair, out_file):
""" INTERNAL: Copy the cached bundle file for the edge to out_file. """
@@ -110,7 +120,7 @@ class BundleCache:
if raised and os.path.exists(out_file):
os.remove(out_file)
- def make_bundle(self, graph, index_pair, out_file=None):
+ def make_bundle(self, graph, version_table, index_pair, out_file=None):
""" Create an hg bundle file corresponding to the edge in graph. """
#print "INDEX_PAIR:", index_pair
assert not index_pair is None
@@ -125,14 +135,20 @@ class BundleCache:
if out_file is None:
out_file = make_temp_file(self.base_dir)
try:
- start_info = self.graph.index_table[index_pair[0]]
- end_info = self.graph.index_table[index_pair[1]]
+
+ parents, heads = get_rollup_bounds(self.graph, self.repo,
+ index_pair[0] + 1, # INCLUSIVE
+ index_pair[1],
+ version_table)
# Hmmm... ok to suppress mercurial noise here.
self.ui_.pushbuffer()
try:
+ #print 'PARENTS:', list(parents)
+ #print 'HEADS:', list(heads)
commands.bundle(self.ui_, self.repo, out_file,
- None, base=[start_info[1]], rev=[end_info[1]])
+ None, base=list(parents),
+ rev=list(heads))
finally:
self.ui_.popbuffer()
@@ -149,7 +165,8 @@ class BundleCache:
# INTENT: Freenet stores data in 32K blocks. If we can stuff
# extra changes into the bundle file under the block boundry
# we get extra redundancy for free.
- def make_redundant_bundle(self, graph, last_index, out_file=None):
+ def make_redundant_bundle(self, graph, version_table, last_index,
+ out_file=None):
""" Make an hg bundle file including the changes in the edge and
other earlier changes if it is possible to fit them under
the 32K block size boundry. """
@@ -167,6 +184,7 @@ class BundleCache:
pair = (earliest_index, last_index)
#print "PAIR:", pair
bundle = self.make_bundle(graph,
+ version_table,
pair,
out_file)
diff --git a/infocalypse/choose.py b/infocalypse/choose.py
--- a/infocalypse/choose.py
+++ b/infocalypse/choose.py
@@ -21,8 +21,10 @@
import random
-from graph import MAX_PATH_LEN, block_cost, print_list
+from graph import MAX_PATH_LEN, block_cost, print_list, canonical_path_itr, \
+ build_version_table
+from graphutil import get_rollup_bounds
# This is the maximum allowed ratio of allowed path block cost
# to minimum full update block cost.
# It is used in low_block_cost_edges() to determine when a
@@ -167,7 +169,10 @@ def low_block_cost_edges(graph, known_ed
def canonical_path_edges(graph, known_edges, from_index, allowed):
""" INTERNAL: Returns edges containing from_index from canonical paths. """
# Steps from canonical paths
- paths = graph.canonical_paths(graph.latest_index, MAX_PATH_LEN)
+ # REDFLAG: fix, efficiency, bound number of path, add alternate edges
+ #paths = graph.canonical_paths(graph.latest_index, MAX_PATH_LEN)
+ paths = canonical_path_itr(graph, 0, graph.latest_index, MAX_PATH_LEN)
+
second = []
#print "get_update_edges -- after"
for path in paths:
@@ -192,7 +197,6 @@ def canonical_path_edges(graph, known_ed
return second
-
# STEP BACK:
# This function answers two questions:
# 0) What should I request to update as quickly as possible?
@@ -277,3 +281,109 @@ def dump_update_edges(first, second, all
print_list("second choice:", second)
print "---"
+def get_top_key_updates(graph, repo, version_table=None):
+ """ Returns the update tuples needed to build the top key."""
+
+ graph.rep_invariant()
+
+ edges = graph.get_top_key_edges()
+
+ coalesced_edges = []
+ ordinals = {}
+ for edge in edges:
+ assert edge[2] >= 0 and edge[2] < 2
+ assert edge[2] == 0 or (edge[0], edge[1], 0) in edges
+ ordinal = ordinals.get(edge[:2])
+ if ordinal is None:
+ ordinal = 0
+ coalesced_edges.append(edge[:2])
+ ordinals[edge[:2]] = max(ordinal, edge[2])
+
+ if version_table is None:
+ version_table = build_version_table(graph, repo)
+ ret = []
+ for edge in coalesced_edges:
+ parents, latest = get_rollup_bounds(graph, repo,
+ edge[0] + 1, edge[1],
+ version_table)
+
+ length = graph.get_length(edge)
+ assert len(graph.edge_table[edge][1:]) > 0
+
+ #(length, parent_rev, latest_rev, (CHK, ...))
+ update = (length, parents, latest,
+ graph.edge_table[edge][1:],
+ True, True)
+ ret.append(update)
+
+
+ # Stuff additional remote heads into first update.
+ result = get_rollup_bounds(graph,
+ repo,
+ 0,
+ graph.latest_index,
+ version_table)
+
+ for head in ret[0][2]:
+ if not head in result[1]:
+ print "Expected head not in all_heads!", head[:12]
+ assert False
+
+ #top_update = list(ret[0])
+ #top_update[2] = tuple(all_heads)
+ #ret[0] = tuple(top_update)
+
+ ret[0] = list(ret[0])
+ ret[0][2] = tuple(result[1])
+ ret[0] = tuple(ret[0])
+
+ return ret
+
+def build_salting_table(target):
+ """ INTERNAL: Build table used to keep track of metadata salting. """
+ def traverse_candidates(candidate_list, table):
+ """ INTERNAL: Helper function to traverse a single candidate list. """
+ for candidate in candidate_list:
+ if candidate[6]:
+ continue
+ edge = candidate[3]
+ value = table.get(edge, [])
+ value.append(candidate[2])
+ table[edge] = value
+ ret = {}
+ traverse_candidates(target.pending_candidates(), ret)
+ traverse_candidates(target.current_candidates, ret)
+ traverse_candidates(target.next_candidates, ret)
+ return ret
+
+# REDFLAG: get rid of unused methods.
+# Hmmm... feels like coding my way out of a design problem.
+class SaltingState:
+ """ INTERNAL: Helper class to keep track of metadata salting state.
+ """
+ def __init__(self, target):
+ self.table = build_salting_table(target)
+
+ def full_request(self, edge):
+ """ Return True if a full request is scheduled for the edge. """
+ if not edge in self.table:
+ return False
+
+ for value in self.table[edge]:
+ if not value:
+ return True
+ return False
+
+ def add(self, edge, is_partial):
+ """ Add an entry to the table. """
+ value = self.table.get(edge, [])
+ value.append(is_partial)
+ self.table[edge] = value
+
+ def needs_full_request(self, graph, edge):
+ """ Returns True if a full request is required. """
+ assert len(edge) == 3
+ if not graph.is_redundant(edge):
+ return False
+ return not (self.full_request(edge) or
+ self.full_request((edge[0], edge[1], int(not edge[2]))))
diff --git a/infocalypse/devnotes.txt b/infocalypse/devnotes.txt
--- a/infocalypse/devnotes.txt
+++ b/infocalypse/devnotes.txt
@@ -1,3 +1,14 @@
+djk20090425
+I reworked the graph representation to handle multiple
+heads correctly.
+
+Repositories inserted with the previous code won't work
+with the new code because I had to change the
+top key format.
+
+djk20090422
+pylint -fparseable --include-ids=y *.py
+
djk20090414
KNOWN LIMITATIONS:
@@ -10,3 +21,4 @@ o 1208 SSK reinserts of same data fail w
o 1208 RemoveRequest kills the FCP connection.
This can cause fn-pull to fail.
It should work if you run it again.
+
diff --git a/infocalypse/fcpconnection.py b/infocalypse/fcpconnection.py
--- a/infocalypse/fcpconnection.py
+++ b/infocalypse/fcpconnection.py
@@ -194,9 +194,6 @@ class NonBlockingSocket(IAsyncSocket):
"""
data = self.socket.recv(RECV_BLOCK)
if not data:
- #self.close()
- #ret = False
- #break
return None
#print "FROM_WIRE:"
@@ -432,8 +429,6 @@ class FileDataSource(IDataSource):
assert self.file
return self.file.read(READ_BLOCK)
-
-
# MESSAGE LEVEL
class FCPConnection:
@@ -605,8 +600,7 @@ class FCPConnection:
break
time.sleep(POLL_TIME_SECS)
- # Doh saw this trip 20080124. Regression from
- # NonBlockingSocket changes?
+ # Doh saw this trip 20080124. Regression from NonBlockingSocket changes?
# assert client.response
if not client.response:
raise IOError("No response. Maybe the socket dropped?")
@@ -727,9 +721,8 @@ class FCPConnection:
# Copy metadata into final message
msg[1]['Metadata.ContentType'] = client.context.metadata
- # Add a third entry to the msg tuple containing
- # the raw data, or a comment saying where it was
- # written.
+ # Add a third entry to the msg tuple containing the raw data,
+ # or a comment saying where it was written.
assert len(msg) == 2
msg = list(msg)
if client.context.data_sink.file_name:
@@ -763,17 +756,15 @@ class FCPConnection:
def closed_handler(self):
""" INTERNAL: Callback called by the IAsyncSocket delegate when the
socket closes. """
- # REDFLAG: DCI: Remove
- def dropping(data):
+ def dropping(data): # REDFLAG: Harmless but remove eventually.
+ """ INTERNAL: Print warning when data is dropped after close. """
print "DROPPING %i BYTES OF DATA AFTER CLOSE!" % len(data)
self.node_hello = None
if not self.socket is None:
- # REDFLAG: DCI: test!
- # Ignore any subsequent data.
self.socket.recv_callback = lambda x:None
- self.socket.recv_callback = dropping
-
+ self.socket.recv_callback = dropping # Ignore any subsequent data.
+
# Hmmmm... other info, ok to share this?
fake_msg = ('ProtocolError', {'CodeDescription':'Socket closed'})
#print "NOTIFIED: CLOSED"
diff --git a/infocalypse/graph.py b/infocalypse/graph.py
--- a/infocalypse/graph.py
+++ b/infocalypse/graph.py
@@ -23,9 +23,9 @@
# REDFLAG: Document how pruning works.
# REDFLAG: Remove unused crap from this file
# REDFLAG: push MAX_PATH_LEN into graph class -> max_cannonical_len
-
+# REDFLAG: stash version map info in the graph?
+# REDFLAG: DOCUMENT version sorting assumptions/requirements
import copy
-import mercurial
import os
import random
@@ -37,6 +37,9 @@ FIRST_INDEX = -1
NULL_REV = '0000000000000000000000000000000000000000'
PENDING_INSERT = 'pending'
PENDING_INSERT1 = 'pending1'
+
+# Values greater than 4 won't work without fixing the implementation
+# of canonical_paths().
MAX_PATH_LEN = 4
INSERT_NORMAL = 1 # Don't transform inserted data.
@@ -105,31 +108,132 @@ def pull_bundle(repo, ui_, bundle_file):
############################################################
-def cmp_age_weight(path_a, path_b):
- """ Comparison function used to sort paths in ascending order
- of 'canonicalness'. """
- # Only works for equivalent paths!
- assert path_a[0][0] == path_b[0][0]
- assert path_b[-1][1] == path_b[-1][1]
+def edges_containing(graph, index):
+ """ INTERNAL: Returns a list of edges containing index in order of
+ ascending 'canonicalness'.
+ """
+ def cmp_edge(edge_a, edge_b):
+ """ INTERNAL: Comparison function. """
+ # First, ascending final index. == Most recent.
+ diff = edge_a[1] - edge_b[1]
+ if diff == 0:
+ # Then, descending initial index. == Most redundant
+ diff = edge_b[0] - edge_a[0]
+ if diff == 0:
+ # Finally, descending 'canonicalness'
+ diff = edge_b[2] - edge_a[2]
+ return diff
- # NO! path step tuples contain a third entry which keeps this
- # from working.
- # if path_a == path_b:
- # return 0
+ edges = graph.contain(index)
+ edges.sort(cmp_edge) # Best last so you can pop
+ #print "--- dumping edges_containing ---"
+ #print '\n'.join([str(edge) for edge in edges])
+ #print "---"
+ return edges
- index = 0
- while index < len(path_a) and index < len(path_b):
- if path_a[index][1] == path_b[index][1]:
- if path_a[index][2] == path_b[index][2]:
- index += 1
- continue
- # If the edges are the same age prefer the one
- # the the lower (i.e. older) CHK ordinal.
- return path_b[index][2] - path_a[index][2]
- return path_a[index][1] - path_b[index][1]
+def tail(list_value):
+ """ Returns the tail of a list. """
+ return list_value[len(list_value) - 1]
- #print "CMP == ", path_a, path_b
- return 0
+def canonical_path_itr(graph, from_index, to_index, max_search_len):
+ """ A generator which returns a sequence of canonical paths in
+ descending order of 'canonicalness'. """
+
+ returned = set([])
+ min_search_len = -1
+ while min_search_len <= max_search_len:
+ visited = set([]) # Retraverse for each length! REDFLAG: Do better?
+ steps = [edges_containing(graph, from_index), ]
+ current_search_len = max_search_len
+ while len(steps) > 0:
+ while len(tail(steps)) > 0:
+ #candidate = [tail(paths) for paths in steps]
+ #print "candidate: ", candidate
+ #print "end: ", tail(tail(steps))
+ if tail(tail(steps))[1] >= to_index:
+ # The edge at the bottom of every list.
+ value = [tail(step) for step in steps]
+ #print "HIT:"
+ #print value
+
+ if min_search_len == -1:
+ min_search_len = len(steps)
+
+ current_search_len = max(len(steps), min_search_len)
+ tag = str(value)
+ if not tag in returned:
+ returned.add(tag)
+
+ # Shorter paths should already be in returned.
+ assert len(value) >= min_search_len
+ assert len(value) <= max_search_len
+ yield value
+ tail(steps).pop()
+ elif len(steps) < current_search_len:
+ tag = str([tail(step) for step in steps])
+ if not tag in visited:
+ # Follow the path one more step.
+ visited.add(tag)
+ steps.append(edges_containing(graph,
+ tail(tail(steps))[1] + 1))
+ else:
+ tail(steps).pop()
+ else:
+ # Abandon the path because it's too long.
+ tail(steps).pop()
+
+ # Get rid of the empty list
+ assert len(tail(steps)) == 0
+ steps.pop()
+ if min_search_len == -1:
+ #print "No such path."
+ return
+ min_search_len += 1
+
+ #print "exiting"
+ # Done iterating.
+
+def get_changes(repo, version_map, versions):
+ """ INTERNAL: Helper function used by UpdateGraph.update()
+ to determine which changes need to be added. """
+ if versions == None:
+ versions = [hexlify(head) for head in repo.heads()]
+ else:
+ versions = list(versions) # Hmmmm...
+ # Normalize all versions to 40 digit hex strings.
+ for index, version in enumerate(versions):
+ versions[index] = hex_version(repo, version)
+
+ if NULL_REV in versions:
+ versions.remove(NULL_REV)
+
+ new_heads = []
+ for version in versions:
+ if not version in version_map:
+ new_heads.append(version)
+
+ if len(new_heads) == 0:
+ if len(versions) > 0:
+ versions.sort()
+ raise UpToDate("Already in repo: " + ' '.join([ver[:12] for
+ ver in versions]))
+ else:
+ raise UpToDate("Empty repository. Nothing to add.")
+
+ if len(version_map) == 1:
+ return ((NULL_REV,), new_heads)
+
+ #print "VERSION MAP:"
+ #print version_map
+ # Determine base revs.
+ base_revs = set([])
+ traversed = set([])
+ for head in new_heads:
+ find_latest_bases(repo, head, version_map, traversed, base_revs)
+
+ return (base_revs, new_heads)
+
+############################################################
def block_cost(length):
""" Return the number of Freenet blocks required to store
@@ -139,79 +243,6 @@ def block_cost(length):
blocks += 1
return blocks
-############################################################
-# Doesn't dump FIRST_INDEX entry.
-def graph_to_string(graph):
- """ Returns a human readable representation of the graph. """
- lines = []
- # Indices
- indices = graph.index_table.keys()
- indices.sort()
- for index in indices:
- if index == FIRST_INDEX:
- continue
-
- entry = graph.index_table[index]
- #print entry
- lines.append("I:%i:%s:%s" % (index, entry[0], entry[1]))
-
- # Edges
- index_pairs = graph.edge_table.keys()
- for index_pair in index_pairs:
- edge_info = graph.edge_table[index_pair]
- as_str = ':'.join(edge_info[1:])
- if as_str != '':
- as_str = ':' + as_str
- lines.append("E:%i:%i:%i%s" % (index_pair[0], index_pair[1],
- edge_info[0],
- as_str))
-
- return '\n'.join(lines) + '\n'
-
-def parse_graph(text):
- """ Returns a graph parsed from text.
- text must be in the format used by graph_to_string().
- Lines starting with '#' are ignored.
- """
-
- graph = UpdateGraph()
- lines = text.split('\n')
- for line in lines:
- fields = line.split(':')
- if fields[0] == 'I':
- if len(fields) != 4:
- raise ValueError("Exception parsing index values.")
- index = int(fields[1])
- if index in graph.index_table:
- print "OVERWRITING INDEX: " , index
- if len(tuple(fields[2:])) != 2:
- raise ValueError("Error parsing index value: %i" % index)
- graph.index_table[index] = tuple(fields[2:])
- elif fields[0] == 'E':
- #print fields
- if len(fields) < 5:
- raise ValueError("Exception parsing edge values.")
- index_pair = (int(fields[1]), int(fields[2]))
- length = int(fields[3])
- chk_list = []
- for chk in fields[4:]:
- chk_list.append(chk)
- graph.edge_table[index_pair] = tuple([length, ] + chk_list)
- #else:
- # print "SKIPPED LINE:"
- # print line
- indices = graph.index_table.keys()
- if len(indices) == 0:
- raise ValueError("No indices?")
- indices.sort()
- graph.latest_index = indices[-1]
-
- graph.rep_invariant()
-
- return graph
-
-############################################################
-
class UpdateGraphException(Exception):
""" Base class for UpdateGraph exceptions. """
def __init__(self, msg):
@@ -225,12 +256,16 @@ class UpToDate(UpdateGraphException):
class UpdateGraph:
""" A digraph representing an Infocalypse Freenet
- hg repository. """
+ hg repository. """ # REDFLAG: digraph of what dude?
def __init__(self):
# Vertices in the update digraph.
- # index_ordinal -> (start_rev, end_rev)
- self.index_table = {FIRST_INDEX:(NULL_REV, NULL_REV)}
+ #
+ # An indice is an encapsulation of the parameters that you
+ # need to bundle a collection of changes.
+ #
+ # index_ordinal -> ((base_revs, ), (tip_revs, ))
+ self.index_table = {FIRST_INDEX:((), (NULL_REV,))}
# These are edges in the update digraph.
# There can be multiple redundant edges.
@@ -241,9 +276,6 @@ class UpdateGraph:
# (start_index, end_index) -> (length, chk@, chk@, ...)
self.edge_table = {}
- # Bound path search length.
- self.max_search_path = 10
-
self.latest_index = -1
def clone(self):
@@ -271,27 +303,6 @@ class UpdateGraph:
return (index_pair[0], index_pair[1],
len(self.edge_table[index_pair]) - 2)
- def subgraph(self, containing_paths):
- """ Return a subgraph which contains the vertices and
- edges in containing_paths. """
- self.rep_invariant()
- graph = UpdateGraph()
- max_index = -1
-
- for path in containing_paths:
- for step in path:
- pair = step[:2]
- # REDFLAG: copies ALL redundant paths
- graph.edge_table[pair] = self.edge_table[pair][:]
- for index in pair:
- if index not in graph.index_table:
- graph.index_table[index] = self.index_table[index][:]
- max_index = max(max_index, index)
-
- graph.latest_index = max_index
- graph.rep_invariant()
- return graph
-
############################################################
# Helper functions used when inserting / requesting
# the edge CHKs.
@@ -375,7 +386,7 @@ class UpdateGraph:
length = self.edge_table[edge_triple[:2]][0]
- # REDFLAG: DCI. MUST DEAL WITH ==32k case
+ # REDFLAG: MUST DEAL WITH ==32k case, djk20080425 -- I think this is ok
if length <= FREENET_BLOCK_LEN:
# Made redundant path by padding.
return INSERT_PADDED
@@ -403,10 +414,24 @@ class UpdateGraph:
############################################################
+ def add_index(self, base_revs, new_heads):
+ """ Add changes to the graph. """
+ assert not NULL_REV in new_heads
+ assert len(base_revs) > 0
+ assert len(new_heads) > 0
+ base_revs.sort()
+ new_heads.sort()
+ if self.latest_index != FIRST_INDEX and NULL_REV in base_revs:
+ print "add_index -- base=null in base_revs. Really do that?"
+ self.latest_index += 1
+ self.index_table[self.latest_index] = (tuple(base_revs),
+ tuple(new_heads))
+ return self.latest_index
+
# REDFLAG: really no need for ui? if so, remove arg
# Index and edges to insert
# Returns index triples with new edges that need to be inserted.
- def update(self, repo, dummy, version, cache):
+ def update(self, repo, dummy, versions, cache):
""" Update the graph to include versions up to version
in repo.
@@ -416,49 +441,50 @@ class UpdateGraph:
The client code is responsible for setting their CHKs!"""
- if self.latest_index > FIRST_INDEX:
- if (repo.changectx(version).rev() <=
- repo.changectx(self.index_table[self.latest_index][1]).rev()):
- raise UpToDate("Version: %s is already in the repo." %
- hex_version(repo, version)[:12])
+ version_map = build_version_table(self, repo)
+ base_revs, new_heads = get_changes(repo, version_map, versions)
+
+ # IMPORTANT: Order matters. Must be after find_latest_bases above.
+ # Update the map. REDFLAG: required?
+ #for version in new_heads:
+ # version_map[version] = self.latest_index + 1
+
+ index = self.add_index(list(base_revs), new_heads)
new_edges = []
- # Add changes to graph.
- prev_changes = self.index_table[self.latest_index]
- parent_rev = prev_changes[1]
- # REDFLAG: Think. What are the implicit assumptions here?
- first_rev = hex_version(repo, prev_changes[1], 1)
- latest_rev = hex_version(repo, version)
-
- index = self._add_changes(parent_rev, first_rev, latest_rev)
#print "ADDED INDEX: ", index
#print self.index_table
# Insert index w/ rollup if possible.
- first_bundle = cache.make_redundant_bundle(self, index)
+ first_bundle = cache.make_redundant_bundle(self, version_map, index)
new_edges.append(self.add_edge(first_bundle[2],
(first_bundle[0], PENDING_INSERT)))
#print "ADDED EDGE: ", new_edges[-1]
+ bundle = None
+ try:
+ canonical_path = self.canonical_path(index, MAX_PATH_LEN)
+ assert len(canonical_path) <= MAX_PATH_LEN
+ except UpdateGraphException:
+ # We need to compress the path.
+ short_cut = self._compress_canonical_path(index, MAX_PATH_LEN + 1)
- canonical_path = self.canonical_path(index, MAX_PATH_LEN + 1)
- assert len(canonical_path) <= MAX_PATH_LEN + 1
+ bundle = cache.make_bundle(self, version_map, short_cut)
- bundle = None
- if len(canonical_path) > MAX_PATH_LEN:
- print "CANNONICAL LEN: ", len(canonical_path)
- short_cut = self._compress_canonical_path(index, MAX_PATH_LEN + 1)
- bundle = cache.make_bundle(self, short_cut)
new_edges.append(self.add_edge(bundle[2],
(bundle[0], PENDING_INSERT)))
+ # MAX_PATH_LEN + 1 search can be very slow.
canonical_path = self.canonical_path(index, MAX_PATH_LEN + 1)
+
assert len(canonical_path) <= MAX_PATH_LEN
if bundle == None:
if (first_bundle[0] <= FREENET_BLOCK_LEN and
first_bundle[2][0] < index - 1):
# This gives us redundancy at the cost of one 32K block.
+
bundle = cache.make_bundle(self,
+ version_map,
(first_bundle[2][0] + 1,
index))
new_edges.append(self.add_edge(bundle[2],
@@ -564,22 +590,12 @@ class UpdateGraph:
to latest_index.
This is what you would use to bootstrap from hg rev -1. """
-
- return self.canonical_paths(to_index, max_search_len)[-1]
-
- def canonical_paths(self, to_index, max_search_len):
- """ Returns a list of paths from no updates to to_index in
- ascending order of 'canonicalness'. i.e. so you
- can pop() the candidates off the list. """
-
- paths = self.enumerate_update_paths(0, to_index, max_search_len)
- if len(paths) == 0:
+ try:
+ return canonical_path_itr(self, 0, to_index, max_search_len).next()
+ except StopIteration:
raise UpdateGraphException("No such path: %s"
% str((0, to_index)))
- paths.sort(cmp_age_weight)
- return paths
-
def path_cost(self, path, blocks=False):
""" The sum of the lengths of the hg bundles required to update
using the path. """
@@ -628,15 +644,6 @@ class UpdateGraph:
# descending initial update. i.e. Most recent first.
return step_b[1] - step_a[1]
- # REDFLAG: add_index instead ???
- # REDFLAG: rethink parent_rev
- def _add_changes(self, parent_rev, first_rev, last_rev):
- """ Add changes to the graph. """
- assert parent_rev == self.index_table[self.latest_index][1]
- self.latest_index += 1
- self.index_table[self.latest_index] = (first_rev, last_rev)
- return self.latest_index
-
def _cmp_block_cost(self, path_a, path_b):
""" INTERNAL: A comparison function for sorting single edge paths
in order of ascending order of block count. """
@@ -720,17 +727,80 @@ class UpdateGraph:
ret.append(edge)
return ret
- def rep_invariant(self):
+ def rep_invariant(self, repo=None, full=True):
""" Debugging function to check invariants. """
max_index = -1
+ min_index = -1
for index in self.index_table.keys():
max_index = max(index, max_index)
+ min_index = min(index, min_index)
+ assert self.latest_index == max_index
+ assert min_index == FIRST_INDEX
- assert self.latest_index == max_index
+ assert self.index_table[FIRST_INDEX][0] == ()
+ assert self.index_table[FIRST_INDEX][1] == (NULL_REV, )
+ for index in range(0, self.latest_index + 1):
+ # Indices must be contiguous.
+ assert index in self.index_table
+ # Each index except for the empty graph sentinel
+ # must have at least one base and head rev.
+ assert len(self.index_table[index][0]) > 0
+ assert len(self.index_table[index][1]) > 0
+
+ # All edges must be resolvable.
for edge in self.edge_table.keys():
assert edge[0] in self.index_table
assert edge[1] in self.index_table
+ assert edge[0] < edge[1]
+
+
+ if repo is None:
+ return
+
+ # Slow
+ version_map = build_version_table(self, repo)
+
+ values = set(version_map.values())
+ values = list(values)
+ values.sort()
+ assert values[-1] == max_index
+ assert values[0] == FIRST_INDEX
+ # Indices contiguous
+ assert values == range(FIRST_INDEX, max_index + 1)
+
+ if full:
+ # Verify that version map is complete.
+ copied = version_map.copy()
+ for rev in range(-1, repo['tip'].rev() + 1):
+ version = hex_version(repo, rev)
+ assert version in copied
+ del copied[version]
+
+ assert len(copied) == 0
+
+ every_head = set([])
+ for index in range(FIRST_INDEX, max_index + 1):
+ versions = set([])
+ for version in (self.index_table[index][0]
+ + self.index_table[index][0]):
+ assert version in version_map
+ if version in versions:
+ continue
+
+ assert has_version(repo, version)
+ versions.add(version)
+
+ # Base versions must have a lower index.
+ for version in self.index_table[index][0]:
+ assert version_map[version] < index
+
+ # Heads must have index == index.
+ for version in self.index_table[index][1]:
+ assert version_map[version] == index
+ # Each head should appear in one and only one index.
+ assert not version in every_head
+ every_head.add(version)
# REDFLAG: O(n), has_index().
def latest_index(graph, repo):
@@ -740,62 +810,19 @@ def latest_index(graph, repo):
for index in range(graph.latest_index, FIRST_INDEX - 1, -1):
if not index in graph.index_table:
continue
- if has_version(repo, graph.index_table[index][1]):
- return index
+ # BUG: Dog slow for big repos? cache index -> heads map
+ skip = False
+ for head in get_heads(graph, index):
+ if not has_version(repo, head):
+ skip = True
+ break # Inner loop... grrr named continue?
+
+ if skip:
+ continue
+ return index
+
return FIRST_INDEX
-# REDFLAG: fix this so that it always includes pending edges.
-def minimal_update_graph(graph, max_size=32*1024,
- formatter_func=graph_to_string):
- """ Returns a subgraph that can be formatted to <= max_size
- bytes with formatter_func. """
-
- index = graph.latest_index
- assert index > FIRST_INDEX
-
- # All the edges that would be included in the top key.
- # This includes the canonical bootstrap path and the
- # two cheapest updates from the previous index.
- paths = [[edge, ] for edge in graph.get_top_key_edges()]
-
- minimal = graph.subgraph(paths)
- if len(formatter_func(minimal)) > max_size:
- raise UpdateGraphException("Too big with only required paths.")
-
- # REDFLAG: read up on clone()
- prev_minimal = minimal.clone()
-
- # Then add all other full bootstrap paths.
- canonical_paths = graph.canonical_paths(index, MAX_PATH_LEN)
-
- while len(canonical_paths):
- if minimal.copy_path(graph, canonical_paths.pop()):
- size = len(formatter_func(minimal))
- #print "minimal_update_graph -- size: %i " % size
- if size > max_size:
- return prev_minimal
- else:
- prev_minimal = minimal.clone()
-
- if index == 0:
- return prev_minimal
-
- # Favors older edges
- # Then add bootstrap paths back to previous indices
- for upper_index in range(index - 1, FIRST_INDEX, - 1):
- canonical_paths = graph.canonical_paths(upper_index, MAX_PATH_LEN)
- while len(canonical_paths):
- if minimal.copy_path(graph, canonical_paths.pop()):
- size = len(formatter_func(minimal))
- #print "minimal_update_graph -- size(1): %i" % size
- if size > max_size:
- return prev_minimal
- else:
- prev_minimal = minimal.clone()
-
- return prev_minimal
-
-
def chk_to_edge_triple_map(graph):
""" Returns a CHK -> edge triple map. """
ret = {}
@@ -862,4 +889,77 @@ def print_list(msg, values):
print " ", value
if len(values) == 0:
print
+# REDFLAG: is it a version_map or a version_table? decide an fix all names
+# REDFLAG: Scales to what? 10k nodes?
+# Returns version -> index mapping
+# REQUIRES: Every version is in an index!
+def build_version_table(graph, repo):
+ """ INTERNAL: Build a version -> index ordinal map for all changesets
+ in the graph. """
+ table = {NULL_REV:-1}
+ for index in range(0, graph.latest_index + 1):
+ assert index in graph.index_table
+ dummy, heads = graph.index_table[index]
+ for head in heads:
+ if not head in table:
+ assert not head in table
+ table[head] = index
+ ancestors = repo[head].ancestors()
+ for ancestor in ancestors:
+ version = hexlify(ancestor.node())
+ if version in table:
+ continue
+ table[version] = index
+ return table
+
+# Find most recent ancestors for version which are already in
+# the version map. REDFLAG: fix. don't make reference to time
+
+def find_latest_bases(repo, version, version_map, traversed, base_revs):
+ """ INTERNAL: Add latest known base revs for version to base_revs. """
+ #print "find_latest_bases -- called: ", version[:12]
+ assert version_map != {NULL_REV:FIRST_INDEX}
+ if version in traversed:
+ return
+ traversed.add(version)
+ if version in version_map:
+ #print " find_latest_bases -- adding: ", version[:12]
+ base_revs.add(version)
+ return
+ parents = [hexlify(parent.node()) for parent in repo[version].parents()]
+ for parent in parents:
+ find_latest_bases(repo, parent, version_map, traversed, base_revs)
+
+
+# REDFLAG: correct? I can't come up with a counter example.
+def get_heads(graph, to_index=None):
+ """ Returns the 40 digit hex changeset ids of the heads. """
+ if to_index is None:
+ to_index = graph.latest_index
+
+ heads = set([])
+ bases = set([])
+ for index in range(FIRST_INDEX, to_index + 1):
+ for base in graph.index_table[index][0]:
+ bases.add(base)
+ for head in graph.index_table[index][1]:
+ heads.add(head)
+ heads = list(heads - bases)
+ heads.sort()
+ return tuple(heads)
+
+# ASSUMPTIONS:
+# 0) head which don't appear in bases are tip heads. True?
+
+# INVARIANTS:
+# o every changeset must exist "in" one and only one index
+# -> contiguousness
+# o the parent revs for all the changesets in every index
+# must exist in a previous index (though not necessarily the
+# immediate predecessor)
+# o indices referenced by edges must exist
+# o latest index must be set correctly
+# o inices must be contiguous
+# o FIRST_INDEX in index_table
+
diff --git a/infocalypse/graphutil.py b/infocalypse/graphutil.py
new file mode 100644
--- /dev/null
+++ b/infocalypse/graphutil.py
@@ -0,0 +1,397 @@
+""" Functions for manipulating UpdateGraphs.
+
+ Copyright (C) 2009 Darrell Karbott
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public
+ License as published by the Free Software Foundation; either
+ version 2.0 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ Author: djk@isFiaD04zgAgnrEC5XJt1i4IE7AkNPqhBG5bONi6Yks
+"""
+
+
+from binascii import hexlify
+
+from graph import FIRST_INDEX, MAX_PATH_LEN, UpdateGraph, \
+ UpdateGraphException, canonical_path_itr
+
+############################################################
+# Doesn't dump FIRST_INDEX entry.
+def graph_to_string(graph):
+ """ Returns a human readable representation of the graph. """
+ lines = []
+ # Indices
+ indices = graph.index_table.keys()
+ indices.sort()
+ for index in indices:
+ if index == FIRST_INDEX:
+ continue
+
+ entry = graph.index_table[index]
+
+ # Example:
+ # I:0:aaaaaaaaaaaa:|:bbbbbbbbbbbb:cccccccccccc
+ lines.append(':'.join(('I', str(index), ':'.join(entry[0]), '|',
+ ':'.join(entry[1]))))
+
+ # Edges
+ index_pairs = graph.edge_table.keys()
+ # MUST sort so you get the same CHK for the same graph instance.
+ index_pairs.sort()
+ for index_pair in index_pairs:
+ edge_info = graph.edge_table[index_pair]
+ as_str = ':'.join(edge_info[1:])
+ if as_str != '':
+ as_str = ':' + as_str
+ lines.append("E:%i:%i:%i%s" % (index_pair[0], index_pair[1],
+ edge_info[0],
+ as_str))
+
+ return '\n'.join(lines) + '\n'
+
+def parse_graph(text):
+ """ Returns a graph parsed from text.
+ text must be in the format used by graph_to_string().
+ Lines starting with '#' are ignored.
+ """
+
+ graph = UpdateGraph()
+ lines = text.split('\n')
+ for line in lines:
+ fields = line.split(':')
+ if fields[0] == 'I':
+ fields.pop(0)
+ try:
+ if len(fields) == 0:
+ raise ValueError("HACK")
+ index = int(fields.pop(0))
+ except ValueError:
+ raise ValueError("Syntax error reading index")
+ try:
+ divider = fields.index('|')
+ except ValueError:
+ raise ValueError("Syntax error reading index %i" % index)
+ parents = fields[:divider]
+ heads = fields[divider + 1:]
+
+ if index in graph.index_table:
+ print "OVERWRITING INDEX: " , index
+ if len(parents) < 1:
+ raise ValueError("index %i has no parent revs" % index)
+ if len(heads) < 1:
+ raise ValueError("index %i has no head revs" % index)
+
+ graph.index_table[index] = (tuple(parents), tuple(heads))
+ elif fields[0] == 'E':
+ #print fields
+ if len(fields) < 5:
+ raise ValueError("Exception parsing edge values.")
+ index_pair = (int(fields[1]), int(fields[2]))
+ length = int(fields[3])
+ chk_list = []
+ for chk in fields[4:]:
+ chk_list.append(chk)
+ graph.edge_table[index_pair] = tuple([length, ] + chk_list)
+ #else:
+ # print "SKIPPED LINE:"
+ # print line
+ indices = graph.index_table.keys()
+ if len(indices) == 0:
+ raise ValueError("No indices?")
+ indices.sort()
+ graph.latest_index = indices[-1]
+
+ graph.rep_invariant()
+
+ return graph
+
+
+def parse_v100_graph(text):
+ """ Returns a graph parsed from text in old format.
+ text must be in the format used by graph_to_string().
+ Lines starting with '#' are ignored.
+ """
+
+ graph = UpdateGraph()
+ lines = text.split('\n')
+ for line in lines:
+ fields = line.split(':')
+ if fields[0] == 'I':
+ if len(fields) != 4:
+ raise ValueError("Exception parsing index values.")
+ index = int(fields[1])
+ if index in graph.index_table:
+ print "OVERWRITING INDEX: " , index
+ if len(tuple(fields[2:])) != 2:
+ raise ValueError("Error parsing index value: %i" % index)
+ versions = tuple(fields[2:])
+ graph.index_table[index] = ((versions[0], ), (versions[1], ))
+ elif fields[0] == 'E':
+ #print fields
+ if len(fields) < 5:
+ raise ValueError("Exception parsing edge values.")
+ index_pair = (int(fields[1]), int(fields[2]))
+ length = int(fields[3])
+ chk_list = []
+ for chk in fields[4:]:
+ chk_list.append(chk)
+ graph.edge_table[index_pair] = tuple([length, ] + chk_list)
+ #else:
+ # print "SKIPPED LINE:"
+ # print line
+ indices = graph.index_table.keys()
+ if len(indices) == 0:
+ raise ValueError("No indices?")
+ indices.sort()
+ graph.latest_index = indices[-1]
+
+ graph.rep_invariant()
+
+ return graph
+
+############################################################
+
+
+def should_add_head(repo, version_table, head, to_index):
+ """ INTERNAL: Helper function used by get_rollup_bounds. """
+ children = [hexlify(child.node()) for child in repo[head].children()]
+ for child in children:
+ # Versions that we don't know about, don't count.
+ # REDFLAG: Think this through
+ if not child in version_table:
+ #print "head: %s %s not in version table. IGNORING" \
+ # % (head[:12], child[:12])
+ continue
+
+ # REDFLAG: Check. This graph stuff makes me crazy.
+ child_index = version_table[child]
+ if child_index <= to_index:
+ # Has a child in or under the index we are rolling up to.
+ # Not a head!
+ #print "should_add_head -- returned False, %i:%s" %
+ # (child_index, child[:12])
+ return False
+
+ #print "should_add_head -- returned True"
+ return True
+
+# TRICKY:
+# You need the repository changset DAG in order to determine
+# the base revs. because new changes might have branched from
+# a change in the middle of a previous index which doesn't
+# appear explictly in the graph.
+#
+def get_rollup_bounds(graph, repo, from_index, to_index, version_table):
+ """ Return a ((parent_revs, ), (head_revs,) tuple required to
+ create a bundle with all the changes [from_index, to_index] (inclusive).
+ """
+ assert from_index <= to_index
+ assert to_index > FIRST_INDEX
+ #print "get_rollup_bounds -- ", from_index, to_index
+ #print "version_table:", len(version_table)
+
+ new_bases = set([])
+ new_heads = set([])
+
+ for index in range(from_index, to_index + 1):
+ bases, heads = graph.index_table[index]
+ for base in bases:
+ #print " considering base ", base[:12], version_table[base]
+ if version_table[base] < from_index:
+ #print " adding base ", base[:12], version_table[base]
+ new_bases.add(base)
+ for head in heads:
+ if should_add_head(repo, version_table, head, to_index):
+ new_heads.add(head)
+
+ new_bases = list(new_bases)
+ new_bases.sort()
+ new_heads = list(new_heads)
+ new_heads.sort()
+
+ #print "get_rollup_bounds -- returning"
+ #print " bases: ", new_bases
+ #print " heads: ", new_heads
+ assert len(new_bases) > 0
+ assert len(new_heads) > 0
+ return (tuple(new_bases), tuple(new_heads))
+
+
+# call this from subgraph
+def coalesce_indices(original_graph, graph, repo, version_table):
+ """ INTERNAL: Coalesce changes so that indices (and changes)
+ are contiguous. """
+ original_graph.rep_invariant()
+ # graph invariants are broken !
+ assert FIRST_INDEX in graph.index_table
+ assert len(graph.index_table) > 1
+
+ # Roll up info in missing indices into existing ones.
+ lacuna = False
+ prev_index = graph.latest_index
+ for index in range(graph.latest_index - 1, FIRST_INDEX -1, -1):
+ # REDFLAG: There was a bad bug here. Better testing?
+ if index in graph.index_table:
+ if lacuna:
+ # Rollup all changes in the missing indices into
+ # the latest one.
+ graph.index_table[prev_index] = (
+ get_rollup_bounds(original_graph,
+ repo,
+ index + 1,
+ prev_index,
+ version_table))
+ lacuna = False
+ prev_index = index
+ else:
+ lacuna = True
+ # Hmmm... or graph is empty
+ assert lacuna == False
+
+ # Make indices contiguous.
+ indices = graph.index_table.keys()
+ indices.sort()
+
+ assert indices[0] == FIRST_INDEX
+ assert FIRST_INDEX == -1
+
+ fixups = {}
+ for ordinal, value in enumerate(indices):
+ fixups[value] = ordinal - 1
+
+ new_indices = {}
+ for old_index in indices:
+ # Ok not to copy, value is immutable (a tuple).
+ new_indices[fixups[old_index]] = graph.index_table[old_index]
+
+ new_edges = {}
+ for edge in graph.edge_table:
+ # Deep copy? Nothing else has a ref to the values.
+ new_edges[(fixups[edge[0]], fixups[edge[1]])] = graph.edge_table[edge]
+
+ graph.index_table.clear()
+ graph.edge_table.clear()
+ graph.index_table.update(new_indices)
+ graph.edge_table.update(new_edges)
+ graph.latest_index = max(graph.index_table.keys())
+
+ original_graph.rep_invariant()
+ #print "FAILING:"
+ #print graph_to_string(graph)
+ graph.rep_invariant()
+
+def subgraph(graph, repo, version_table, containing_paths):
+ """ Return a subgraph which contains the vertices and
+ edges in containing_paths. """
+ graph.rep_invariant()
+ small_graph = UpdateGraph()
+ max_index = -1
+
+ # Copy edges and indices.
+ for path in containing_paths:
+ for step in path:
+ pair = step[:2]
+ # REDFLAG: copies ALL redundant paths
+ small_graph.edge_table[pair] = graph.edge_table[pair][:]
+ for index in pair:
+ if index not in small_graph.index_table:
+ # Don't need to deep copy because index info is
+ # immutable. (a tuple)
+ small_graph.index_table[index] = graph.index_table[index]
+ max_index = max(max_index, index)
+
+ small_graph.latest_index = max_index
+
+ # Fix contiguousness.
+ coalesce_indices(graph, small_graph, repo, version_table)
+
+ # Invariants should be fixed.
+ small_graph.rep_invariant()
+ graph.rep_invariant()
+
+ return small_graph
+
+# REDFLAG: TERMINATE when all edges in graph have been yielded?
+def important_edge_itr(graph, known_paths):
+ """ INTERNAL: A generator which returns a sequence of edges in order
+ of descending criticalness."""
+ known_edges = set([])
+ for path in known_paths:
+ for edge in path:
+ known_edges.add(edge)
+
+ # Edges which are in the canonical path
+ index = graph.latest_index
+ canonical_paths = canonical_path_itr(graph, 0, index, MAX_PATH_LEN)
+
+ for path in canonical_paths:
+ for edge in path:
+ if edge in known_edges:
+ continue
+ known_edges.add(edge)
+ yield edge
+
+ if index == 0:
+ return
+
+ # Then add bootstrap paths back to previous indices
+ # Favors older edges.
+ for upper_index in range(index - 1, FIRST_INDEX, - 1):
+ canonical_paths = canonical_path_itr(graph, 0, upper_index,
+ MAX_PATH_LEN)
+ for path in canonical_paths:
+ for edge in path:
+ if edge in known_edges:
+ continue
+ known_edges.add(edge)
+ yield edge
+ return
+
+# Really slow
+def minimal_graph(graph, repo, version_table, max_size=32*1024,
+ formatter_func=graph_to_string):
+ """ Returns a subgraph that can be formatted to <= max_size
+ bytes with formatter_func. """
+
+ length = len(formatter_func(graph))
+ if length <= max_size:
+ #print "minimal_update_graph -- graph fits as is: ", length
+ # Hmmm... must clone for consistent semantics.
+ return graph.clone()
+
+ index = graph.latest_index
+ assert index > FIRST_INDEX
+
+ # All the edges that would be included in the top key.
+ # This includes the canonical bootstrap path and the
+ # two cheapest updates from the previous index.
+ paths = [[edge, ] for edge in graph.get_top_key_edges()]
+ minimal = subgraph(graph, repo, version_table, paths)
+ length = len(formatter_func(minimal))
+ if length > max_size:
+ raise UpdateGraphException("Too big with only required paths (%i > %i)"
+ % (length, max_size))
+
+ prev_minimal = minimal.clone()
+
+ for edge in important_edge_itr(graph, paths):
+ paths.append([edge, ])
+ minimal = subgraph(graph, repo, version_table, paths)
+ length = len(formatter_func(minimal))
+ if length > max_size:
+ return prev_minimal
+ else:
+ prev_minimal = minimal.clone()
+
+ return prev_minimal
+
diff --git a/infocalypse/infcmds.py b/infocalypse/infcmds.py
--- a/infocalypse/infcmds.py
+++ b/infocalypse/infcmds.py
@@ -37,12 +37,12 @@ from fcpconnection import FCPConnection,
get_code, FCPError
from requestqueue import RequestRunner
-from graph import UpdateGraph, hex_version
+from graph import UpdateGraph
from bundlecache import BundleCache, is_writable
from updatesm import UpdateStateMachine, QUIESCENT, FINISHING, REQUESTING_URI, \
REQUESTING_GRAPH, REQUESTING_BUNDLES, INVERTING_URI, \
REQUESTING_URI_4_INSERT, INSERTING_BUNDLES, INSERTING_GRAPH, \
- INSERTING_URI, FAILING, REQUESTING_URI_4_COPY
+ INSERTING_URI, FAILING, REQUESTING_URI_4_COPY, CANCELING, CleaningUp
from config import Config, DEFAULT_CFG_PATH
@@ -52,14 +52,16 @@ DEFAULT_PARAMS = {
'PriorityClass':1,
'DontCompress':True, # hg bundles are already compressed.
'Verbosity':1023, # MUST set this to get progress messages.
+ #'GetCHKOnly':True, # REDFLAG: DCI! remove
# Non-FCP stuff
'N_CONCURRENT':4, # Maximum number of concurrent FCP requests.
'CANCEL_TIME_SECS': 10 * 60, # Bound request time.
'POLL_SECS':0.25, # Time to sleep in the polling loop.
+ #'TEST_DISABLE_GRAPH': True, # Disable reading the graph.
+ #'TEST_DISABLE_UPDATES': True, # Don't update info in the top key.
}
-
MSG_TABLE = {(QUIESCENT, REQUESTING_URI_4_INSERT)
:"Requesting previous URI...",
(QUIESCENT, REQUESTING_URI_4_COPY)
@@ -115,6 +117,14 @@ class UICallbacks:
def monitor_callback(self, update_sm, client, msg):
""" FCP message status callback which writes to a ui. """
+ # REDFLAG: remove when 1209 comes out.
+ if (msg[0] == 'PutFailed' and get_code(msg) == 9 and
+ update_sm.params['FREENET_BUILD'] == '1208' and
+ update_sm.ctx.get('REINSERT', 0) > 0):
+ self.ui_.warn('There is a KNOWN BUG in 1208 which '
+ + 'causes code==9 failures for re-inserts.\n'
+ + 'The re-insert might actually have succeeded.\n'
+ + 'Who knows???\n')
if self.verbosity < 2:
return
@@ -152,13 +162,10 @@ class UICallbacks:
self.ui_.status("%s%s:%s\n" % (prefix, str(client.tag), text))
# REDFLAG: re-add full dumping of FCP errors at debug level?
#if msg[0].find('Failed') != -1 or msg[0].find('Error') != -1:
- # print client.in_params.pretty()
- # print msg
- # print "FINISHED:" , client.is_finished(),
- #bool(client.is_finished())
+ #print client.in_params.pretty()
+ #print msg
+ #print "FINISHED:" , bool(client.is_finished())
-
-# Paranoia? Just stat? I'm afraid of problems/differences w/ Windoze.
# Hmmmm... SUSPECT. Abuse of mercurial ui design intent.
# ISSUE: I don't just want to suppress/include output.
# I use this value to keep from running code which isn't
@@ -192,7 +199,8 @@ def get_config_info(ui_, opts):
params['TMP_DIR'] = cfg.defaults['TMP_DIR']
params['VERBOSITY'] = get_verbosity(ui_)
params['NO_SEARCH'] = (bool(opts.get('nosearch')) and
- (opts.get('uri', None) or opts.get('requesturi', None)))
+ (opts.get('uri', None) or
+ opts.get('requesturi', None)))
request_uri = opts.get('uri') or opts.get('requesturi')
if bool(opts.get('nosearch')) and not request_uri:
@@ -228,6 +236,31 @@ def check_uri(ui_, uri):
+ "\nUse --aggressive instead. \n")
raise util.Abort("Negative USK %s\n" % uri)
+
+def disable_cancel(updatesm, disable=True):
+ """ INTERNAL: Hack to work around 1208 cancel kills FCP connection bug. """
+ if disable:
+ if not hasattr(updatesm.runner, 'old_cancel_request'):
+ updatesm.runner.old_cancel_request = updatesm.runner.cancel_request
+ msg = ("RequestRunner.cancel_request() disabled to work around "
+ + "1208 bug\n")
+ updatesm.runner.cancel_request = (
+ lambda dummy : updatesm.ctx.ui_.status(msg))
+ else:
+ if hasattr(updatesm.runner, 'old_cancel_request'):
+ updatesm.runner.cancel_request = updatesm.runner.old_cancel_request
+ updatesm.ctx.ui_.status("Re-enabled canceling so that "
+ + "shutdown works.\n")
+class PatchedCleaningUp(CleaningUp):
+ """ INTERNAL: 1208 bug work around to re-enable canceling. """
+ def __init__(self, parent, name, finished_state):
+ CleaningUp.__init__(self, parent, name, finished_state)
+
+ def enter(self, from_state):
+ """ Override to back out 1208 cancel hack. """
+ disable_cancel(self.parent, False)
+ CleaningUp.enter(self, from_state)
+
# REDFLAG: remove store_cfg
def setup(ui_, repo, params, stored_cfg):
""" INTERNAL: Setup to run an Infocalypse extension command. """
@@ -273,12 +306,31 @@ def setup(ui_, repo, params, stored_cfg)
raise err
runner = RequestRunner(connection, params['N_CONCURRENT'])
-
update_sm = UpdateStateMachine(runner, repo, ui_, cache)
update_sm.params = params.copy()
update_sm.transition_callback = callbacks.transition_callback
update_sm.monitor_callback = callbacks.monitor_callback
+ # Modify only after copy.
+ update_sm.params['FREENET_BUILD'] = runner.connection.node_hello[1]['Build']
+
+ # REDFLAG: Hack to work around 1208 cancel bug. Remove.
+ if update_sm.params['FREENET_BUILD'] == '1208':
+ ui_.warn("DISABLING request canceling to work around 1208 FCP bug.\n"
+ "This may cause requests to hang. :-(\n")
+ disable_cancel(update_sm)
+
+ # Patch state machine to re-enable canceling on shutdown.
+ #CANCELING:CleaningUp(self, CANCELING, QUIESCENT),
+ #FAILING:CleaningUp(self, FAILING, QUIESCENT),
+ #FINISHING:CleaningUp(self, FINISHING, QUIESCENT),
+ update_sm.states[CANCELING] = PatchedCleaningUp(update_sm,
+ CANCELING, QUIESCENT)
+ update_sm.states[FAILING] = PatchedCleaningUp(update_sm,
+ FAILING, QUIESCENT)
+ update_sm.states[FINISHING] = PatchedCleaningUp(update_sm,
+ FINISHING, QUIESCENT)
+
return update_sm
def run_until_quiescent(update_sm, poll_secs, close_socket=True):
@@ -300,12 +352,12 @@ def run_until_quiescent(update_sm, poll_
# Indirectly nudge the state machine.
update_sm.runner.kick()
except socket.error: # Not an IOError until 2.6.
- update_sm.ui_.warn("Exiting because of an error on "
- + "the FCP socket.\n")
+ update_sm.ctx.ui_.warn("Exiting because of an error on "
+ + "the FCP socket.\n")
raise
except IOError:
# REDLAG: better message.
- update_sm.ui_.warn("Exiting because of an IO error.\n")
+ update_sm.ctx.ui_.warn("Exiting because of an IO error.\n")
raise
# Rest :-)
time.sleep(poll_secs)
@@ -460,7 +512,7 @@ def execute_create(ui_, repo, params, st
#ui_.status("Current tip: %s\n" % hex_version(repo)[:12])
update_sm.start_inserting(UpdateGraph(),
- params.get('TO_VERSION', 'tip'),
+ params.get('TO_VERSIONS', ('tip',)),
params['INSERT_URI'])
run_until_quiescent(update_sm, params['POLL_SECS'])
@@ -568,7 +620,7 @@ def execute_push(ui_, repo, params, stor
#ui_.status("Current tip: %s\n" % hex_version(repo)[:12])
update_sm.start_pushing(params['INSERT_URI'],
- params.get('TO_VERSION', 'tip'),
+ params.get('TO_VERSIONS', ('tip',)),
request_uri, # None is allowed
is_keypair)
run_until_quiescent(update_sm, params['POLL_SECS'])
@@ -601,7 +653,7 @@ def execute_pull(ui_, repo, params, stor
ui_.status("Pulled from:\n%s\n" %
update_sm.get_state('REQUESTING_URI').
get_latest_uri())
- ui_.status("New tip: %s\n" % hex_version(repo)[:12])
+ #ui_.status("New tip: %s\n" % hex_version(repo)[:12])
else:
ui_.status("Pull failed.\n")
diff --git a/infocalypse/insertingbundles.py b/infocalypse/insertingbundles.py
--- a/infocalypse/insertingbundles.py
+++ b/infocalypse/insertingbundles.py
@@ -20,8 +20,9 @@
Author: djk@isFiaD04zgAgnrEC5XJt1i4IE7AkNPqhBG5bONi6Yks
"""
-from graph import graph_to_string, UpToDate, INSERT_SALTED_METADATA, \
- FREENET_BLOCK_LEN
+from graph import UpToDate, INSERT_SALTED_METADATA, \
+ FREENET_BLOCK_LEN, build_version_table, get_heads
+from graphutil import graph_to_string
from bundlecache import BundleException
from statemachine import RequestQueueState
@@ -67,13 +68,16 @@ class InsertingBundles(RequestQueueState
self.parent.ctx.ui_.status("--- Initial Graph ---\n")
self.parent.ctx.ui_.status(graph_to_string(graph) +'\n')
- latest_rev = graph.index_table[graph.latest_index][1]
- self.parent.ctx.ui_.warn("Latest version in Freenet: %s\n"
- % latest_rev[:12])
- if not self.parent.ctx.has_version(latest_rev):
- self.parent.ctx.ui_.warn("The latest version in Freenet isn't in "
- "the local repository.\n"
- "Try doing an fn-pull to update.\n")
+
+ latest_revs = get_heads(graph)
+
+ self.parent.ctx.ui_.status("Latest heads(s) in Freenet: %s\n"
+ % ' '.join([ver[:12] for ver in latest_revs]))
+
+ if not self.parent.ctx.has_versions(latest_revs):
+ self.parent.ctx.ui_.warn("The local repository isn't up "
+ + "to date.\n"
+ + "Try doing an fn-pull.\n")
self.parent.transition(FAILING) # Hmmm... hard coded state name
return
@@ -240,11 +244,17 @@ class InsertingBundles(RequestQueueState
def set_new_edges(self, graph):
""" INTERNAL: Set the list of new edges to insert. """
+
+ # REDFLAG: Think this through.
+ self.parent.ctx.version_table = build_version_table(graph,
+ self.parent.ctx.
+ repo)
if self.parent.ctx.get('REINSERT', 0) == 0:
self.new_edges = graph.update(self.parent.ctx.repo,
self.parent.ctx.ui_,
- self.parent.ctx['TARGET_VERSION'],
+ self.parent.ctx['TARGET_VERSIONS'],
self.parent.ctx.bundle_cache)
+
return
# Hmmmm... later support different int values of REINSERT?
diff --git a/infocalypse/requestingbundles.py b/infocalypse/requestingbundles.py
--- a/infocalypse/requestingbundles.py
+++ b/infocalypse/requestingbundles.py
@@ -28,15 +28,14 @@ import random # Hmmm... good enough?
from fcpmessage import GET_DEF
from bundlecache import make_temp_file
-from graph import parse_graph, latest_index, \
+from graph import latest_index, \
FREENET_BLOCK_LEN, chk_to_edge_triple_map, \
- dump_paths, MAX_PATH_LEN
-
-from choose import get_update_edges, dump_update_edges
+ dump_paths, MAX_PATH_LEN, get_heads, canonical_path_itr
+from graphutil import parse_graph
+from choose import get_update_edges, dump_update_edges, SaltingState
from statemachine import RetryingRequestList, CandidateRequest
-#from topkey import dump_top_key_tuple
from chk import clear_control_bytes
# REDFLAG: Make sure that you are copying lists. eg. updates
@@ -45,7 +44,7 @@ from chk import clear_control_bytes
# 1) Single block fetch alternate keys.
# 2) Choose between primary and alternate keys "fairly"
# 3) transition from no graph to graph case.
-# 4) deal with padding hack
+# 4) deal with padding hacks
# 5) Optionally disable alternate single block fetching?
# ?6) serialize? Easier to write from scratch?
@@ -56,58 +55,7 @@ from chk import clear_control_bytes
# Can unwind padding hack w/o graph
# len < 32K done
# len == 32K re-request DONE
-#
-# REDFLAG: get rid of pending_candidates by subclassing StatefulRequest
-# to include a .candidate attribute. ???
-def build_salting_table(target):
- """ INTERNAL: Build table used to keep track of metadata salting. """
- def traverse_candidates(candidate_list, table):
- """ INTERNAL: Helper function to traverse a single candidate list. """
- for candidate in candidate_list:
- if candidate[6]:
- continue
- edge = candidate[3]
- value = table.get(edge, [])
- value.append(candidate[2])
- table[edge] = value
- ret = {}
- traverse_candidates(target.pending_candidates(), ret)
- traverse_candidates(target.current_candidates, ret)
- traverse_candidates(target.next_candidates, ret)
- return ret
-
-# REDFLAG: get rid of unused methods.
-# Hmmm... feels like coding my way out of a design problem.
-class SaltingState:
- """ INTERNAL: Helper class to keep track of metadata salting state.
- """
- def __init__(self, target):
- self.table = build_salting_table(target)
-
- def full_request(self, edge):
- """ Return True if a full request is scheduled for the edge. """
- if not edge in self.table:
- return False
-
- for value in self.table[edge]:
- if not value:
- return True
- return False
-
- def add(self, edge, is_partial):
- """ Add an entry to the table. """
- value = self.table.get(edge, [])
- value.append(is_partial)
- self.table[edge] = value
-
- def needs_full_request(self, graph, edge):
- """ Returns True if a full request is required. """
- assert len(edge) == 3
- if not graph.is_redundant(edge):
- return False
- return not (self.full_request(edge) or
- self.full_request((edge[0], edge[1], int(not edge[2]))))
# What this does:
# 0) Fetches graph(s)
# 1) Fetches early bundles in parallel with graphs
@@ -126,6 +74,7 @@ class RequestingBundles(RetryingRequestL
self.success_state = success_state
self.failure_state = failure_state
self.top_key_tuple = None # FNA sskdata
+ self.freenet_heads = None
############################################################
# State implementation
@@ -165,7 +114,8 @@ class RequestingBundles(RetryingRequestL
# Catch state machine stalls.
if (self.parent.current_state == self and
self.is_stalled()):
- print "STALLED, BAILING OUT!"
+ self.parent.ctx.ui_.warn("Giving up because the state "
+ + "machine stalled.\n")
self.parent.transition(self.failure_state)
# DONT add to pending. Base clase does that.
@@ -209,6 +159,9 @@ class RequestingBundles(RetryingRequestL
############################################################
+
+ # DEALING: With partial heads, partial bases?
+
# REDFLAG: deal with optional request serialization?
# REDFLAG: Move
# ASSUMPTION: Keys are in descenting order of latest_rev.
@@ -229,6 +182,12 @@ class RequestingBundles(RetryingRequestL
if index < start_index:
# REDFLAG: do better?
continue
+ if not update[4] or not update[5]:
+ # Don't attempt to queue updates if we don't know
+ # full parent/head info.
+ # REDFLAG: remove test code
+ print "_queue_from_updates -- bailing out", update[4], update[5]
+ break
if only_latest and update[0] > 5 * FREENET_BLOCK_LEN:
# Short circuit (-1, top_index) rollup case.
@@ -238,7 +197,7 @@ class RequestingBundles(RetryingRequestL
# Only full updates.
break
- if not self.parent.ctx.has_version(update[1]):
+ if not self.parent.ctx.has_versions(update[1]):
# Only updates we can pull.
if only_latest:
# Don't want big bundles from the canonical path.
@@ -246,7 +205,7 @@ class RequestingBundles(RetryingRequestL
else:
continue
- if self.parent.ctx.has_version(update[2]):
+ if self.parent.ctx.has_versions(update[2]):
# Only updates we need.
continue
@@ -266,6 +225,42 @@ class RequestingBundles(RetryingRequestL
return last_queued
+
+ def _handle_testing_hacks(self):
+ """ INTERNAL: Helper function to implement TEST_DISABLE_UPDATES
+ and TEST_DISABLE_GRAPH testing params. """
+ if self.top_key_tuple is None:
+ return
+ if self.parent.params.get("TEST_DISABLE_UPDATES", False):
+ updates = list(self.top_key_tuple[1])
+ for index in range(0, len(updates)):
+ update = list(updates[index])
+ update[4] = False
+ update[5] = False
+ updates[index] = tuple(update)
+ top = list(self.top_key_tuple)
+ top[1] = tuple(updates)
+ self.top_key_tuple = tuple(top)
+ self.parent.ctx.ui_.warn("TEST_DISABLE_UPDATES == True\n"
+ + "Disabled updating w/o graph\n")
+
+ if self.parent.params.get("TEST_DISABLE_GRAPH", False):
+ top = list(self.top_key_tuple)
+ # REDFLAG: Fix post 1208
+ # Using bad keys is a more realistic test but there's
+ # an FCP bug in 1208 that kills the connection on
+ # cancel. Go back to this when 1209 comes out.
+ top[0] = ('CHK@badroutingkeyA55JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8',
+ 'CHK@badroutingkeyB55JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8',
+ )
+ top[0] = ()
+ self.top_key_tuple = tuple(top)
+ self.parent.ctx.ui_.warn("TEST_DISABLE_GRAPH == True\n"
+ + "Disabled graph by removing graph "
+ + "chks.\n")
+
# Hack special case code to add the graph.
def _initialize(self, top_key_tuple=None):
""" INTERNAL: Initialize.
@@ -279,6 +274,7 @@ class RequestingBundles(RetryingRequestL
"""
self.top_key_tuple = top_key_tuple
+ self._handle_testing_hacks()
############################################################
# Hack used to test graph request failure.
#bad_chk = ('CHK@badroutingkeyA55JblbGup0yNSpoDJgVPnL8E5WXoc,'
@@ -297,28 +293,41 @@ class RequestingBundles(RetryingRequestL
if self.top_key_tuple is None:
raise Exception("No top key data.")
- #if self.parent.params.get('DUMP_TOP_KEY', False):
- # dump_top_key_tuple(top_key_tuple)
+ updates = self.top_key_tuple[1]
+ if updates[0][5]:
+ self.freenet_heads = updates[0][2]
+ self.parent.ctx.ui_.status('Freenet heads: %s\n' %
+ ' '.join([ver[:12] for ver in
+ updates[0][2]]))
- updates = self.top_key_tuple[1]
+ if self.parent.ctx.has_versions(updates[0][2]):
+ self.parent.ctx.ui_.warn("All remote heads are already "
+ + "in the local repo.\n")
+ self.parent.transition(self.success_state)
+ return
- if self.parent.ctx.has_version(updates[0][2]):
- self.parent.ctx.ui_.warn(("Version: %s is already in the "
- + "local repo.\n")
- % updates[0][2][:12])
- self.parent.transition(self.success_state)
- return
+ # INTENT: Improve throughput for most common update case.
+ # If it is possible to update fully in one fetch, queue the
+ # (possibly redundant) key(s) BEFORE graph requests.
+ latest_queued = self._queue_from_updates(self.
+ current_candidates,
+ -1, False, True)
- # INTENT: Improve throughput for most common update case.
- # If it is possible to update fully in one fetch, queue the
- # (possibly redundant) key(s) BEFORE graph requests.
- latest_queued = self._queue_from_updates(self.current_candidates,
- -1, False, True)
+ if latest_queued != -1:
+ self.parent.ctx.ui_.status("Full update is possible in a "
+ + "single FCP fetch. :-)\n")
- if latest_queued != -1:
- self.parent.ctx.ui_.status("Full update is possible in a "
- + "single FCP fetch. :-)\n")
+ else:
+ self.parent.ctx.ui_.warn("Couldn't read all Freenet heads from "
+ + "top key.\n"
+ + "Dunno if you're up to date :-(\n"
+ + "Waiting for graph...\n")
+ if len(self.top_key_tuple[0]) == 0:
+ self.parent.ctx.ui_.warn("No graph CHKs in top key! "
+ + "Giving up...\n")
+ self.parent.transition(self.failure_state)
+ return
# Kick off the fetch(es) for the full update graph.
# REDFLAG: make a parameter
parallel_graph_fetch = True
@@ -333,6 +342,11 @@ class RequestingBundles(RetryingRequestL
if not parallel_graph_fetch:
break
+
+ if self.freenet_heads is None:
+ # Need to wait for the graph.
+ return
+
# Queue remaining fetchable keys in the NEXT pass.
# INTENT:
# The graph might have a better update path. So we don't try these
@@ -392,7 +406,11 @@ class RequestingBundles(RetryingRequestL
text += " BAD TOP KEY DATA!" + ":" + chk + "\n"
self.parent.ctx.ui_.status(text)
+ all_heads = get_heads(graph)
+ assert (self.freenet_heads is None or
+ self.freenet_heads == all_heads)
+ self.freenet_heads = all_heads
self.parent.ctx.graph = graph
self.rep_invariant()
@@ -404,6 +422,7 @@ class RequestingBundles(RetryingRequestL
#break_edges(graph, kill_prob, skip_chks)
# "fix" (i.e. break) pending good chks.
+ # REDFLAG: comment this out too?
for candidate in self.current_candidates + self.next_candidates:
if candidate[6]:
continue
@@ -435,6 +454,25 @@ class RequestingBundles(RetryingRequestL
self.parent.ctx.ui_.warn("Couldn't read graph from Freenet!\n")
self.parent.transition(self.failure_state)
+ def _handle_dump_canonical_paths(self, graph):
+ """ INTERNAL: Dump the top 20 canonical paths. """
+ if not self.parent.params.get('DUMP_CANONICAL_PATHS', False):
+ return
+
+ paths = canonical_path_itr(graph, 0, graph.latest_index,
+ MAX_PATH_LEN)
+ first_paths = []
+ # REDFLAG: Magick number
+ while len(first_paths) < 20:
+ try:
+ first_paths.append(paths.next())
+ except StopIteration:
+ break
+
+ dump_paths(graph,
+ first_paths,
+ "Canonical paths")
+
def _graph_request_done(self, client, msg, candidate):
""" INTERNAL: Handle requests for the graph. """
#print "CANDIDATE:", candidate
@@ -456,13 +494,7 @@ class RequestingBundles(RetryingRequestL
self.parent.ctx.ui_.status(data)
self.parent.ctx.ui_.status("\n---\n")
graph = parse_graph(data)
- if self.parent.params.get('DUMP_CANONICAL_PATHS', False):
- paths = graph.canonical_paths(graph.latest_index,
- MAX_PATH_LEN)[-20:]
- paths.reverse()
- dump_paths(graph,
- paths,
- "Canonical paths")
+ self._handle_dump_canonical_paths(graph)
self._set_graph(graph)
self._reevaluate()
finally:
@@ -582,23 +614,20 @@ class RequestingBundles(RetryingRequestL
candidate[5] = msg
self.finished_candidates.append(candidate)
#print "_handle_success -- pulling!"
+ name = str(candidate[3])
+ if name == 'None':
+ name = "%s:%s" % (','.join([ver[:12] for ver in candidate[4][1]]),
+ ','.join([ver[:12] for ver in candidate[4][2]]))
+
+ #print "Trying to pull: ", name
self._pull_bundle(client, msg, candidate)
#print "_handle_success -- pulled bundle ", candidate[3]
- name = str(candidate[3])
- if name == 'None':
- name = "%s:%s" % (candidate[4][1][:12], candidate[4][2][:12])
self.parent.ctx.ui_.status("Pulled bundle: %s\n" % name)
- graph = self.parent.ctx.graph
- if graph is None:
- latest_version = self.top_key_tuple[1][0][2]
- else:
- latest_version = graph.index_table[graph.latest_index][1]
-
- if self.parent.ctx.has_version(latest_version):
+ if self.parent.ctx.has_versions(self.freenet_heads):
# Done and done!
- print "DONE, UP TO DATE!"
+ #print "SUCCEEDED!"
self.parent.transition(self.success_state)
return
@@ -691,11 +720,11 @@ class RequestingBundles(RetryingRequestL
could be pulled and contains changes that we don't already have. """
versions = self._get_versions(candidate)
#print "_needs_bundle -- ", versions
- if not self.parent.ctx.has_version(versions[0]):
+ if not self.parent.ctx.has_versions(versions[0]):
#print "Doesn't have parent ", versions
return False # Doesn't have parent.
- return not self.parent.ctx.has_version(versions[1])
+ return not self.parent.ctx.has_versions(versions[1])
# REDFLAGE: remove msg arg?
def _pull_bundle(self, client, dummy_msg, candidate):
@@ -730,12 +759,15 @@ class RequestingBundles(RetryingRequestL
all_chks = pending.union(current).union(next).union(finished)
for update in self.top_key_tuple[1]:
- if not self.parent.ctx.has_version(update[1]):
+ if not self.parent.ctx.has_versions(update[1]):
+ # Still works with incomplete base.
continue # Don't have parent.
- if self.parent.ctx.has_version(update[2]):
+ if self.parent.ctx.has_versions(update[2]):
+ # Not guaranteed to work with incomplete heads.
continue # Already have the update's changes.
+
new_chks = []
for chk in update[3]:
if not chk in all_chks:
@@ -849,14 +881,14 @@ class RequestingBundles(RetryingRequestL
if candidate[6]:
continue # Skip graph requests.
versions = self._get_versions(candidate)
- if self.parent.ctx.has_version(versions[1]):
+ if self.parent.ctx.has_versions(versions[1]):
self.parent.runner.cancel_request(client)
# "finish" requests which are no longer required.
victims = []
for candidate in self.current_candidates:
versions = self._get_versions(candidate)
- if self.parent.ctx.has_version(versions[1]):
+ if self.parent.ctx.has_versions(versions[1]):
victims.append(candidate)
for victim in victims:
self.current_candidates.remove(victim)
@@ -866,7 +898,7 @@ class RequestingBundles(RetryingRequestL
victims = []
for candidate in self.next_candidates:
versions = self._get_versions(candidate)
- if self.parent.ctx.has_version(versions[1]):
+ if self.parent.ctx.has_versions(versions[1]):
victims.append(candidate)
for victim in victims:
self.next_candidates.remove(victim)
@@ -875,7 +907,7 @@ class RequestingBundles(RetryingRequestL
def _get_versions(self, candidate):
""" Return the mercurial 40 digit hex version strings for the
- parent version and latest version of the candidate's edge. """
+ parent versions and latest versions of the candidate's edge. """
assert not candidate[6] # graph request!
graph = self.parent.ctx.graph
if graph is None:
@@ -891,7 +923,7 @@ class RequestingBundles(RetryingRequestL
#print "_get_versions -- ", step, graph.index_table[step[0]][1], \
# graph.index_table[step[1]][2]
- return (graph.index_table[step[0]][1],
+ return (graph.index_table[step[0] + 1][0],
graph.index_table[step[1]][1])
def _known_chks(self):
@@ -958,6 +990,3 @@ class RequestingBundles(RetryingRequestL
print_list("pending_candidates", self.pending_candidates())
print_list("current_candidates", self.current_candidates)
print_list("next_candidates", self.next_candidates)
-
-
-# LocalWords: requeueing
diff --git a/infocalypse/test_graph.py b/infocalypse/test_graph.py
new file mode 100644
--- /dev/null
+++ b/infocalypse/test_graph.py
@@ -0,0 +1,620 @@
+""" Smoke test graph.
+
+ Copyright (C) 2009 Darrell Karbott
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public
+ License as published by the Free Software Foundation; either
+ version 2.0 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ Author: djk@isFiaD04zgAgnrEC5XJt1i4IE7AkNPqhBG5bONi6Yks
+"""
+
+
+# We can be a little sloppy for test code.
+# pylint: disable-msg=R0915, R0914
+import binascii
+import os
+import random
+import shutil
+
+from binascii import unhexlify
+
+from mercurial import hg, ui
+from bundlecache import BundleCache
+from graph import UpdateGraph, \
+ build_version_table, UpdateGraphException, \
+ pull_bundle, FIRST_INDEX, hex_version, UpToDate
+from graphutil import parse_graph, graph_to_string, get_rollup_bounds, \
+ minimal_graph
+from chk import bytes_to_chk, CHK_SIZE
+
+# Fix these paths as necessary
+CACHE_DIR = '/tmp/bundle_cache' # MUST exist
+TST_REPO_DIR = '/tmp/TST_REPO' # MUST not exist
+
+# Must exist and contain the hg repo unbundled from:
+# CHK@5fdjppBySiW2uFGd1nZNFD6U9xaadSPYTut9C3CdZa0,
+# 33fQQwKXcjnhpAqI3nJw9kvjXYL~R9kVckAoFqbQ4IY,AAIC--8
+#
+# (Inserted from hgsvn_freenet_9f093d2c85c3.hg)
+HGSVN_FREENET_REPO = '/tmp/HGSVN_FREENET'
+
+VER_1 = '0000000000000000000000000000000000000000'
+VER_2 = '1111111111111111111111111111111111111111'
+VER_3 = '2222222222222222222222222222222222222222'
+VER_4 = '3333333333333333333333333333333333333333'
+VER_5 = '4444444444444444444444444444444444444444'
+VER_6 = '5555555555555555555555555555555555555555'
+
+def fake_chks():
+ """ Return a random CHK. """
+ size = CHK_SIZE - 5
+ while True:
+ #yield bytes_to_chk('\x00\x02\x02\xff\xff'
+ # + ''.join(map(chr, map(random.randrange,
+ # [0] * size, [256] * size))))
+ yield bytes_to_chk('\x00\x02\x02\xff\xff'
+ + ''.join([chr(random.randrange(0, 256)) for dummy
+ in range(0, size)]))
+
+
+
+def set_chks(graph, edges, chks):
+ """ Set the chks for edges to random values. """
+ for edge in edges:
+ length = graph.get_length(edge)
+ graph.set_chk(edge[:2], edge[2], length, chks.next())
+
+def test_presentation():
+ """ Smoke test graph_to_string and parse_graph. """
+ graph = UpdateGraph()
+ print "EMPTY:"
+ print graph_to_string(graph)
+ print "Adding index: ", graph.add_index([VER_1, ], [VER_2, ])
+ print "Adding index: ", graph.add_index([VER_2, ], [VER_3, VER_4])
+ print "Adding index: ", graph.add_index([VER_3, VER_2], [VER_5, ])
+ chks = fake_chks()
+ graph.add_edge((-1, 0), (100, chks.next()))
+ graph.add_edge((1, 2), (200, chks.next()))
+ graph.add_edge((-1, 2), (500, chks.next()))
+ text = graph_to_string(graph)
+ print
+ print text
+ print
+ graph1 = parse_graph(text)
+ print
+ text1 = graph_to_string(graph1)
+ print "Round trip:"
+ print text1
+ assert text == text1
+
+def test_update(repo_dir):
+ """ OBSOLETE? """
+ ui_ = ui.ui()
+ repo = hg.repository(ui_, repo_dir)
+ cache = BundleCache(repo, ui_, CACHE_DIR)
+ cache.remove_files()
+ graph = UpdateGraph()
+ graph.update(repo, ui, [1, 2], cache)
+ print graph_to_string(graph)
+ print
+ print
+ graph.update(repo, ui, [3, 4], cache)
+
+ print graph_to_string(graph)
+ print
+ print
+ graph.update(repo, ui, [6, ], cache)
+
+ print graph_to_string(graph)
+
+def test_update_real(repo_dir, version_list=None, full=False):
+ """ Smoke test graph.update(). """
+ ui_ = ui.ui()
+ repo = hg.repository(ui_, repo_dir)
+ cache = BundleCache(repo, ui_, CACHE_DIR)
+ cache.remove_files()
+ graph = UpdateGraph()
+ if version_list is None:
+ latest = repo['tip'].rev()
+ version_list = [[ordinal, ] for ordinal in range(0, latest + 1)]
+
+ chks = fake_chks()
+ for vers in version_list:
+ print "UPDATING TO: ", vers
+ new_edges = graph.update(repo, ui, vers, cache)
+ for edge in new_edges:
+ length = graph.get_length(edge)
+ graph.set_chk(edge[:2], edge[2], length, chks.next())
+
+ # REDFLAG: should call minimal_graph for "real" behavior
+ text = graph_to_string(graph)
+ print "GRAPH_LEN: ", len(text)
+ print text
+
+ if full:
+ print "UPDATING TO: latest heads"
+ try:
+ new_edges = graph.update(repo, ui, None, cache)
+ for edge in new_edges:
+ length = graph.get_length(edge)
+ graph.set_chk(edge[:2], edge[2], length, chks.next())
+
+ # REDFLAG: should call minimal_graph for "real" behavior
+ text = graph_to_string(graph)
+ print "GRAPH_LEN: ", len(text)
+ print text
+ except UpToDate:
+ print "Already has the head revs."
+
+ return (graph, repo, cache)
+
+def test_minimal_graph(repo_dir, version_list, file_name=None):
+ """ Smoke test minimal_graph(). """
+ ui_ = ui.ui()
+ if file_name is None:
+ graph, repo, cache = test_update_real(repo_dir, version_list, True)
+ open('/tmp/latest_graph.txt', 'wb').write(graph_to_string(graph))
+ else:
+ repo = hg.repository(ui_, repo_dir)
+ cache = BundleCache(repo, ui_, CACHE_DIR)
+ cache.remove_files()
+ graph = parse_graph(open(file_name, 'rb').read())
+ print "--- from file: %s ---" % file_name
+ print graph_to_string(graph)
+ version_map = build_version_table(graph, repo)
+
+ # Incomplete, but better than nothing.
+ # Verify that the chk bounds are the same after shrinking.
+ chk_bounds = {}
+ initial_edges = graph.get_top_key_edges()
+ for edge in initial_edges:
+ chk_bounds[graph.get_chk(edge)] = (
+ get_rollup_bounds(graph, repo, edge[0] + 1, edge[1], version_map))
+
+ print "CHK BOUNDS:"
+ for value in chk_bounds:
+ print value
+ print " ", chk_bounds[value]
+ print
+ sizes = (512, 1024, 2048, 4096, 16 * 1024)
+ for max_size in sizes:
+ try:
+ print "MAX:", max(version_map.values())
+ small = minimal_graph(graph, repo, version_map, max_size)
+ print "--- size == %i" % max_size
+ print graph_to_string(small)
+
+ small.rep_invariant(repo, True) # Full check
+ chks = chk_bounds.keys()
+ path = small.get_top_key_edges()
+ print "TOP KEY EDGES:"
+ print path
+ for edge in path:
+ # MUST rebuild the version map because the indices changed.
+ new_map = build_version_table(small, repo)
+ bounds = get_rollup_bounds(small, repo, edge[0] + 1,
+ edge[1], new_map)
+ print "CHK:", small.get_chk(edge)
+ print "BOUNDS: ", bounds
+ assert chk_bounds[small.get_chk(edge)] == bounds
+ print "DELETING: ", edge, small.get_chk(edge)
+ chks.remove(small.get_chk(edge))
+ assert len(chks) == 0
+ except UpdateGraphException, err:
+ print "IGNORED: ", err
+
+def versions_str(version_list):
+ """ Format a list of 40 digit hex versions for humans. """
+ return ' '.join([version[:12] for version in version_list])
+
+# def test_rollup(repo_dir):
+# version_list = [[1, ], [2, 3], [4, ], [7, ], [8, ], [9, 10]]
+# graph, repo, dummy = test_update_real(repo_dir, version_list)
+# print graph_to_string(graph)
+# print
+# version_map = build_version_table(graph, repo)
+# reverse_map = {}
+# for version in version_map:
+# index = version_map[version]
+# entry = reverse_map.get(index, set([]))
+# entry.add(version)
+# reverse_map[index] = entry
+
+# indices = reverse_map.keys()
+# indices.sort()
+# print "VERSION MAP:"
+# for index in indices:
+# print "%i:" % index
+# for version in reverse_map[index]:
+# print " ", version
+
+# for index in range(0, graph.latest_index + 1):
+# parents, heads = get_rollup_bounds(graph, repo, 0, index, version_map)
+# print "%i: %s" % (index, versions_str(heads))
+# print " ", versions_str(parents)
+
+# # Final roll
+# parents, heads = get_rollup_bounds(graph, repo, 3, 5,
+# version_map)
+
+# print "edge: %s" % versions_str(heads)
+# print " ", versions_str(parents)
+
+# for index in range(0, graph.latest_index + 1):
+# heads = get_heads(graph, index)
+# print "[%i]:%s" % (index, versions_str(heads))
+
+
+def hexlify_file(in_file):
+ """ Dump the hex rep of a file. """
+ data = binascii.hexlify(open(in_file, 'rb').read())
+ while len(data):
+ chunk = data[:64]
+ print '+ "%s"' % chunk
+ data = data[len(chunk):]
+
+
+HGSVN_FREENET_REVS = (
+ '1c33735d20b6',
+ '815ca7018bf6',
+ '3e2436fe3928',
+ 'ae954303d1dd',
+ '723bd8953983',
+ '40c11333daf8',
+ '12eb1c81a1ec',
+ 'b02a0c6a859a',
+ 'a754303da0e5',
+ '20c6ae2419bf',
+ '2f8a676bb4c3',
+ 'c27794351de7',
+ '1ef183fa59f6',
+ '6479bf5a3eb9',
+ '3f912b103873',
+ '3a2204acb83c',
+ '3aaad6480514',
+ '76419812d2b7',
+ 'b5ba8a35c801',
+ 'ffcad749bed9',
+ '31acbabecc22',
+ 'f5dd66d8e676',
+ '3726fc577853',
+ 'efe0d89e6e8f',
+ '87a25acc07e3',
+ 'ba9f937fed0e',
+ '28f5a21c8e6e',
+ 'b0797db2ab16',
+ 'bc2e0f5d4a90',
+ '3c9bb5cf63f6',
+ 'ffd58f1accde',
+ '39ed8f43e65d',
+ 'b574671511ab',
+ 'b01c9e1811a8',
+ '158e1087d72b',
+ 'ac5cfb495ef7',
+ '32af1ded78d6',
+ '950457d1f557',
+ '42552b6d3b36',
+# '8ec2ceb1545d',
+ )
+
+ROLLUP_TEST_HG = (
+ "48473130425a6839314159265359fb23d3670000be7fffffffffffdfffffffff"
+ + "fff7effffffffffffffffffffffffffffffffdffffffdfe00b7d97c6d8346f2a"
+ + "a8001806d52a9dc0000000200000000000000000000000000000000d34000000"
+ + "000000000000000000000000d034929fa9a9a3d53c934d3f5469903ca6268c46"
+ + "8da9934d1a00686468d34d18434d0699068c0134000d34321a6101880d0c4610"
+ + "d01a61346801a34683201a1a0000d4d026d0264429a4f5004c04c03400013000"
+ + "02600069300000000130046000d0046269800000013469800000000d1000a604"
+ + "3553daa68d03d400343401a07ea80034000d34d068d000034001a06800000190"
+ + "00d001a0001a0001a00d00f500200000000000000000000000000000000d3400"
+ + "0000000000000000000000000000d0152a44533406129a69ed1368536a9fa4f0"
+ + "9a60a78984d354fc14f29a9fea9e9a9ea329fa0d0c53268d3c149ec93c990f48"
+ + "69a1a69a53f53349e933527e493d3689a6a6d3c93d0a7b53d32989a793d4d26d"
+ + "340d29b6a9f88694f1a9e8d2901f6ddff8f5ec575ff465bd3fab2dc5755caa32"
+ + "4b441ed5c323427a9a4c5af0fc4860d6dd17fb7cf99b3ccc2aeda2c7cb39d4aa"
+ + "9bc89edd7f5125aa4b7ddf5f586c3698ead8d358835139365eef4d1735cdea5c"
+ + "af2dc4408cd4825724082fdc126cde4c81320dc5dd8258c8b53b8a6bcc400212"
+ + "24254c08ccab995733a68ab9578801b19002531c250dbf70e6411833bc444350"
+ + "33304a049e3881247361014a4958d6929430744a56992df40a747d7ac91248c0"
+ + "2510914e144945122850851424a2502461a50d6adf15ae6d5118ba05144e3c5f"
+ + "d49551449181675497595bb8ecea27d54e896f62e364a95e4719d1c904e21ac2"
+ + "23860c1883ab4215072d98bb108921a0ccb22220f3d0add0bb4d09984c6da8c9"
+ + "e4f0fc0ba79c886089ccc8cc806add24224f0a4aa7766862ea8982c43924308f"
+ + "022a618464dd6535f99b6bde4ba37c33d09915a45b57eb9ff28cc52d43d58cb2"
+ + "c1ea2d5066aad487e8a09858d6292166e0ad1773c09e2c6d1908ddd5374b5b25"
+ + "1b754fc0e6b0b43ff6a97477bc2f428a4a14605997e28a8a9a9e8631332af6a3"
+ + "1eb634aea0c3b3d18df493571b672adb57451a0f2ea9a48fbadb2c3b9516b538"
+ + "e89e0bf8ba7c2f329808f7d6e744af7223bd77ca738d1cec77f1f82db6530702"
+ + "d737c6f60dd6401e02f0822eb9444ea0e32d43345ac5e54640113682c0108f0b"
+ + "46bad9addf8b11af8dadafb4daaea64dc79faa2d1d9455beb3f447e43a68dd2e"
+ + "31ae4b679aa32d16b5575d179544170adba450770cc522786609698eadfd23ef"
+ + "3a5a393c6356e9dd64dd3c2788c6689f4380f9d3fbad64f2f492455ceff86f29"
+ + "d7631273541b382feaa080bfa911e201986a8101abdf6dfbfc1a34111ad98788"
+ + "704e3049274ae3308ae664c838da4b88e103cd6c047c605590a08b542f730ea1"
+ + "eeb5771ba2919b8e5c23f3408d8f44d246730ad9f24eb5c6cc4eceb2807605d8"
+ + "91121052327622bf04e080a6f50cbaaad69442b0f4c90e4de935f531180d1158"
+ + "b8c997712e4538c1fb10f9c2dfcf4b00955b5b056fcb1d64ed6402ef840dd962"
+ + "a6805f1c81e28a4a546428db81c848028320f0715b904402e46a118acec8bc06"
+ + "a0c3db4850b05d09cdb1745cc71b2f1122178b5ac9134828312f11508b66b7a6"
+ + "427687aa78e1b0691cfa6ad4c87f51ada6f84a6a96c5db654e734dad72cd3761"
+ + "70dc1a64834037a508761100a8b5a86e0c01c64d7d5d0719e28b4390642022b1"
+ + "2be5c30f2d02f865009d3230080181004eb862d7285ed6b1958b9e61ed144e03"
+ + "4b81138200269601355eb4605ba660dd28a58c7cbc7908bdd5a4e13456db50f9"
+ + "1b570685151ac3532c704c0ab93c5166aa10e9ac848bc60d0f0a136d812915ad"
+ + "81980303d4b27285182d2a0c2e11b0cd2d4b85c85899bcb60709ae01a3575ca0"
+ + "f0aa08d1ef18f5163242cc4a4259434c6a1587212c740d606a7408aff741dd24"
+ + "e352dc24b4b6554816a405ff59330e2c6504e2b155a3272113785872570a21ec"
+ + "8624ba27494109d1c232da401df528ce41b91baa24a7581a707d62cc8bfbf1fc"
+ + "d037d1de2063a06ee1f7ba3702408cef175cc75e09589ebc641270125830b641"
+ + "6a0a8131817062a16038444403c68c04cb6fded01ae0f11091443941816608d3"
+ + "26d968b08467032c7032b24232a3e6c6ec738f5822b5e20e556eadcf585d984a"
+ + "fc8442af283048c961acb138084b2fb178d4345a8a2a8da4196ce80d36295182"
+ + "c1b858525499005156173a792ebc4a61a5729269baac9dac8242afbe0a6d2362"
+ + "430192df6c6f58ac6260a25646513689f80129388708404ea2aeba9554a9e536"
+ + "8e71ecc6fe3dd7931f65ec46363f83db6aa8a28aa5852fdef2231b1e2ba5b9e3"
+ + "948df4d96ef4abab1ca8c2db549cfcf22340d0d8bebbd3e5af0f156c7dbe1ba8"
+ + "68debafce13ab61df95ce641d4af6b8ffcf0fdc984d0c5a97dd1e0a39e8f477b"
+ + "dc47389e52ad94a3417de43d49a88d4daa36f1b758464a2959b90b434aca64b9"
+ + "88f10d82dfbb649d9bc13f3b08c4b3cde3b73ca7b0d0ab5725939cf1edd1b85c"
+ + "fa4526ce38abf7abf4c5d9848f7b4ec239575fcef82fd98c8ac75397374d4c79"
+ + "2b04ebe74b3d5699a97aefc33b499ced958c3b1bc66815eab8d23471b8f9e363"
+ + "de5ef573fc3daec18e535d22eb06e5ee69a5094508a28f3e306ccee9d4c5c0af"
+ + "756c57637c63eefd852bb52fadc90dff920ecf52d0c6a8f1691c2a16b9a23063"
+ + "06ad8a4aec588bad4b80f007f21b6a66bb0d3a7202a6db7004dce201244d2b7b"
+ + "a1c72076e812a120385279dff4a4db913b45d5634d6cc015b025cb707899b013"
+ + "1c6c19255e906a18c48bb3b05569eab42cfd48596ae36024a1ec80b6b3887324"
+ + "bb4b1cde2d5cd1c4846e23fb164d68ba62e355114d4cb4b558bb2926ad95ada9"
+ + "10b6906faadc902dc8c26d396279d39a10a278a1ac25a1b4c9c9639413033429"
+ + "1140a4293086281018913e64325594d55e4517134b2f524d8757bacaa42ce0b0"
+ + "ba026b2f0e09174db4b6618d8328811888b92504b2d3187441b011adaf5331de"
+ + "bfbc308a3509f3822215de9595158a7d018930ba41e1747d609887d8e6b53786"
+ + "b5e22420983160a4af3073e1cd2186db0e85717366d152d89d8a0c5c2a44c24c"
+ + "5328c0c890f60ac02dc29172abb4188d5431ed70a2b63058ba90aaa4b7456624"
+ + "264209517b658e126ccd74d6d46c625f4043142415dad8541980ea9256113491"
+ + "110864b38431af70934444633e107a77209c02c8b12ea59e48cce1fb542f97fd"
+ + "dc7975ee1cd726b9c9fe6cbed294bbb948e6bbb3b24c7491ef15a861e311476f"
+ + "1d3bea29f2ce510f390bff329654d0d5e21f0b6b1cec6c18043ee626463e8a0a"
+ + "b89631b8c6dc6a1669f246a57ad5cfb7f458768f58f4ac582b775ffa663a9f52"
+ + "a0280d345118d53e657e9d37af7f6fb276bca7fa5f2973dcc54e4792bc2c5555"
+ + "79c9238ceea308f9d709aef77e57fc7a6aa50a4a350de25ce2a6a6b1cccf59ac"
+ + "5276b17d665ad996923cc5eb6b30e7fbb3687f0db3e68e42e05b63f54ff2b279"
+ + "b174772ca3191e333a9edf0238876d5df69c452f7dbf7eb54ef22ca79f2e6a88"
+ + "c7c7f77865f55113e659c7eb763fe741868a3ecc53c6c5f5b53efbe07f67ee97"
+ + "0a162ad3871b454f09cc392d5ad8decdff7564c12bd8f79ea51a78f6985534e0"
+ + "ba658caf8be354eea3bb8c84e5be35af6370b2ee4cb7033549d3f54ae6fa3e1d"
+ + "ce61b759ac951cbeb766ad8eecfeb1c0564d67e9e145fcf65b2b357a97239d6b"
+ + "566d33f2c7d335ed92bdf14584f398a9b964e3d1fa89472f61f61fb65f7511e8"
+ + "297e78d4b3714e2ef1477d44dac50cdb41c64d9c6466d1dcad26ce3fc2a5954f"
+ + "18e025ee3f036cfcd2b3731a73d96763bcc8de721728f1d9f4e856a9776a9a97"
+ + "dd57e89c556fb77cb7df13d57612f050ab6763111c18bb3f0ba4748cc3ca5b63"
+ + "1ce24d0b68e146fdcfbee1cdc6fe2be6563dc8f53afb7e2d817bd97a3b88cc3f"
+ + "13ce2d4d84705e7a77d612f4cd38eeb22edd6fb5170609f62324b5c67a3091cf"
+ + "9c752ef23b2705d69736963d1bc3e2958db5de9e93fa1cbc53bdb03819bb65d5"
+ + "a6bcf9b8bc5b7706328a9e7be552b6bb19965d9df3ed278cae741ad2895945a6"
+ + "2e4cb33f15115b1948a53191bd2f4dc9c568a5b12c6366efdbceae28c79896d2"
+ + "39b619dc3dc6196e9969dbc67de9be48e8e3a337ef9d62cf9f41ef35cdc3ad9d"
+ + "b4699f1aa52caf3fb93026ca38ae3aa79f5c5e229ec5ab53cd6565d63fed9d76"
+ + "f55bde61c88f95f5638ce55716bfe38c44d74ece2c716af8c84790a73932bd81"
+ + "3a469f492fef816f786e99d42af7d9e71e69de5bf1de6d11b88b645c9fd5e39d"
+ + "e9c8981786ae8f357b9eeb44c9baaabcd9d725a3b1736e4350d5c5e9fb2338ce"
+ + "342bc6be8e3cfbca75cd645a5ac8fa57b378a3f9c5ba799729e8b4f197f09d09"
+ + "efadb1a397460cfc897466a5628b8c652297b1314d3b62d546e990decd547fe4"
+ + "ab798f0a7f26f8bf2ff191b4a603f6b79332b6be28f972af9188c3ede7271a47"
+ + "df658ff68d8bb58c44c51d2baece4c5a6fcf53151e93d66a5c4564725a5eb70d"
+ + "a23a05f16733f1805ee2eecf4de33297168e94a3dd755167388aef6ebb60a783"
+ + "a14fe98bfc6c1eb1e03a0f3b3f146858964cfc6f49aa7ff8bb9229c28487d91e"
+ + "9b38")
+
+def setup_rollup_test_repo(dir_name):
+ """ INTERNAL: Setup for rollup test. """
+ assert dir_name.endswith('TST_REPO')
+ if os.path.exists(dir_name):
+ shutil.rmtree(dir_name)
+
+ assert not os.path.exists(dir_name)
+ os.makedirs(dir_name)
+ ui_ = ui.ui()
+ repo = hg.repository(ui_, dir_name, True)
+ bundle_path = os.path.join(dir_name, 'bundle.hg')
+ bundle_file = open(bundle_path, 'wb')
+ bundle_file.write(unhexlify(ROLLUP_TEST_HG))
+ bundle_file.close()
+ pull_bundle(repo, ui_, bundle_path)
+ return (repo, ui_)
+
+def dump_version_map(version_map):
+ """ Print a version map table in a human readable format. """
+ reverse_map = {}
+ for version in version_map:
+ index = version_map[version]
+ entry = reverse_map.get(index, set([]))
+ entry.add(version)
+ reverse_map[index] = entry
+
+ indices = reverse_map.keys()
+ indices.sort()
+ print "---Version map---"
+ for index in indices:
+ print "%i:" % index
+ for version in reverse_map[index]:
+ print " ", version
+
+# Only compares first 12 digits so full ids can be compared
+# against short ones.
+def check_result(result_a, result_b):
+ """ INTERNAL: Helper function. """
+ assert len(result_a) == 2
+ assert len(result_b) == 2
+ assert len(result_a[0]) == len(result_b[0])
+ assert len(result_a[1]) == len(result_b[1])
+ for outer in range(0, 2):
+ for inner in range(0, len(result_a[outer])):
+ if result_a[outer][inner][:12] != result_b[outer][inner][:12]:
+ print "MISMATCH:"
+ print result_a
+ print result_b
+ assert False
+
+def dump_changesets(repo):
+ """ Print all the changesets in a repo. """
+ print "---"
+ max_rev = repo['tip'].rev()
+ for rev in range(-1, max_rev + 1):
+ print hex_version(repo, rev)
+ print "---"
+# There are many, many ways to fail.
+# More testing would be good.
+
+EXPECTED_VERSION_MAP = {
+ '0000000000000000000000000000000000000000':-1,
+ '716c293192c7b2e26860ade38e1b279e905cd197':0,
+ '2aa9c462481a05287e7b97d7abc48ca53b24b33c':1,
+ '4636fd812094cf54aeb58c7f5edf35d19ebe79e3':1,
+ '076aec9f34c96c62a3069a98af1927bf710430b4':1,
+ '62a72a238ffc748c11d115d8ceab44daf517fd76':2,
+ '4409936ef21f3cb20e443b6ec37110978fccb484':2,
+ '90374996e95f994e8925301fb91252fe509661e6':3,
+ '75a57040197d15bde53148157403284727bcaba4':3,
+ 'a2c749d99d546c3db4f1fdb8c5c77ec9bef30aeb':3,
+ '138466bcf8027a765b77b13a456598e74fe65115':4,
+ '8ddce595000df42d9abbc81c7654fa36457b2081':4,
+ 'fd1e6832820b1a7a33f6e69d3ca561c09af2e015':5,
+ '7429bf7b11f56d016a1cd7b7ec5cf130e48108b7':6,
+ 'f6248cd464e3f8fc8bd9a03dcc78943615d0e148':4,
+ 'fcc2e90dbf0dc2736c119c6ae995edf092f3f6cb':7,
+ '03c047d036ca0f3aab3a47451fbde2b02026ee99':8,
+ '9eaabc277b994c299aa4341178b416728fd279ff':9,
+ '2f6c65f64ce59060c08dae82b7dcbeb8e4d2d976':9,
+}
+
+def test_rollup():
+ """ Smoke test get_rollup_bounds(). """
+ repo, ui_ = setup_rollup_test_repo(TST_REPO_DIR)
+ dump_changesets(repo)
+ cache = BundleCache(repo, ui_, CACHE_DIR)
+ cache.remove_files()
+ graph = UpdateGraph()
+
+ chks = fake_chks()
+ # 0 Single changeset
+ edges = graph.update(repo, ui_, ['716c293192c7', ], cache)
+ set_chks(graph, edges, chks)
+ # 1 Multiple changesets
+ edges = graph.update(repo, ui_, ['076aec9f34c9', ], cache)
+ set_chks(graph, edges, chks)
+ # 2 Multiple heads, single base
+ edges = graph.update(repo, ui_, ['62a72a238ffc', '4409936ef21f'], cache)
+ set_chks(graph, edges, chks)
+ # 3 Multiple bases, single head
+ edges = graph.update(repo, ui_, ['a2c749d99d54', ], cache)
+ set_chks(graph, edges, chks)
+ # 4
+ edges = graph.update(repo, ui_, ['f6248cd464e3', ], cache)
+ set_chks(graph, edges, chks)
+ # 5
+ edges = graph.update(repo, ui_, ['fd1e6832820b', ], cache)
+ set_chks(graph, edges, chks)
+ # 6
+ edges = graph.update(repo, ui_, ['7429bf7b11f5', ], cache)
+ set_chks(graph, edges, chks)
+ # 7
+ edges = graph.update(repo, ui_, ['fcc2e90dbf0d', ], cache)
+ set_chks(graph, edges, chks)
+ # 8
+ edges = graph.update(repo, ui_, ['03c047d036ca', ], cache)
+ set_chks(graph, edges, chks)
+
+ # 9
+ edges = graph.update(repo, ui_, ['2f6c65f64ce5', ], cache)
+ set_chks(graph, edges, chks)
+
+ print
+ print graph_to_string(graph)
+ version_map = build_version_table(graph, repo)
+
+ dump_version_map(version_map)
+ assert version_map == EXPECTED_VERSION_MAP
+
+ graph.rep_invariant(repo, True) # Verify contiguousness.
+
+ print "From earliest..."
+ for index in range(0, graph.latest_index + 1):
+ parents, heads = get_rollup_bounds(graph, repo, 0, index, version_map)
+ print "(%i->%i): %s" % (0, index, versions_str(heads))
+ print " ", versions_str(parents)
+
+
+ print "To latest..."
+ for index in range(0, graph.latest_index + 1):
+ parents, heads = get_rollup_bounds(graph, repo, index,
+ graph.latest_index,
+ version_map)
+ print "(%i->%i): %s" % (index, graph.latest_index, versions_str(heads))
+ print " ", versions_str(parents)
+
+
+ # Empty
+ try:
+ get_rollup_bounds(graph, repo, FIRST_INDEX, FIRST_INDEX,
+ version_map)
+ except AssertionError:
+ # Asserted as expected for to_index == FIRST_INDEX
+ print "Got expected assertion."
+
+ # Rollup of one changeset index.
+ result = get_rollup_bounds(graph, repo, 0, 0, version_map)
+ check_result(result, (('000000000000', ), ('716c293192c7',)))
+
+ # Rollup of multiple changeset index.
+ result = get_rollup_bounds(graph, repo, 1, 1, version_map)
+ check_result(result, (('716c293192c7', ), ('076aec9f34c9',)))
+
+ # Rollup of with multiple heads.
+ result = get_rollup_bounds(graph, repo, 1, 2, version_map)
+ check_result(result, (('716c293192c7', ), ('4409936ef21f','62a72a238ffc')))
+
+ # Rollup of with multiple bases.
+ result = get_rollup_bounds(graph, repo, 3, 4, version_map)
+ check_result(result, (('4409936ef21f', '62a72a238ffc', ),
+ ('f6248cd464e3',)))
+
+ # Rollup with head pulled in from earlier base.
+ result = get_rollup_bounds(graph, repo, 3, 8, version_map)
+ print result
+ check_result(result, (('4409936ef21f', '62a72a238ffc', ),
+ ('03c047d036ca', '7429bf7b11f5')))
+
+ # Rollup after remerge to a single head.
+ result = get_rollup_bounds(graph, repo, 0, 9, version_map)
+ print result
+ check_result(result, (('000000000000', ), ('2f6c65f64ce5', )))
+
+if __name__ == "__main__":
+ test_presentation()
+ VERSIONS = [(ver, ) for ver in HGSVN_FREENET_REVS]
+ test_minimal_graph(HGSVN_FREENET_REPO, VERSIONS)
+ test_rollup()
+
+# Testing minimal graph.
+# - contains the right edges [Inspection. not aut]
+# x revision bounds of edges don't change
+# - backmap from chks
+# ? indexes are contiguous [Lean on graph.rep_invariant)()]
+# a) ordinals -- easy
+# b) changesets -- hard
+# ?? depend on version map
+# CONCERNS:
+# - creating real use test cases
+# - so hard that I will "waste" a lot of time without finding bugs
+
diff --git a/infocalypse/test_topkey.py b/infocalypse/test_topkey.py
new file mode 100644
--- /dev/null
+++ b/infocalypse/test_topkey.py
@@ -0,0 +1,69 @@
+""" Smoke test topkey.
+
+ Copyright (C) 2009 Darrell Karbott
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public
+ License as published by the Free Software Foundation; either
+ version 2.0 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ Author: djk@isFiaD04zgAgnrEC5XJt1i4IE7AkNPqhBG5bONi6Yks
+"""
+
+
+from topkey import top_key_tuple_to_bytes, bytes_to_top_key_tuple, \
+ dump_top_key_tuple
+
+BAD_CHK1 = ('CHK@badroutingkey155JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8')
+BAD_CHK2 = ('CHK@badroutingkey255JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8')
+BAD_CHK3 = ('CHK@badroutingkey355JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8')
+BAD_CHK4 = ('CHK@badroutingkey455JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8')
+BAD_CHK5 = ('CHK@badroutingkey555JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8')
+BAD_CHK6 = ('CHK@badroutingkey655JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8')
+BAD_CHK7 = ('CHK@badroutingkey755JblbGup0yNSpoDJgVPnL8E5WXoc,'
+ +'KZ6azHOwEm4ga6dLy6UfbdSzVhJEz3OvIbSS4o5BMKU,AAIC--8')
+
+TOP = ((BAD_CHK6,),
+ ((10, ('0' * 40, '1' * 40, '2' * 40), ('a' * 40, 'b' * 40,),
+ (BAD_CHK1,), True, True),
+ (20, ('3' * 40,), ('c' * 40,),
+ (BAD_CHK2,), False, True),
+ (30, ('3' * 40,), ('d' * 40,),
+ (BAD_CHK3, BAD_CHK4), True, False),
+ (40, ('2' * 40,), ('e' * 40,),
+ (BAD_CHK5,), False, False),
+ ))
+
+def smoke_test_topkey():
+ """ Smoke test top key functions. """
+ # To binary rep...
+ bytes0 = top_key_tuple_to_bytes(TOP)
+ bytes1 = top_key_tuple_to_bytes(TOP, 0xcc)
+
+ # Check salting.
+ assert bytes0 != bytes1
+ assert len(bytes0) == len(bytes1)
+
+ # ... and back
+ assert bytes_to_top_key_tuple(bytes0)[0] == TOP
+ assert bytes_to_top_key_tuple(bytes1)[0] == TOP
+
+ dump_top_key_tuple(TOP)
+
+if __name__ == "__main__":
+ smoke_test_topkey()
diff --git a/infocalypse/topkey.py b/infocalypse/topkey.py
--- a/infocalypse/topkey.py
+++ b/infocalypse/topkey.py
@@ -24,7 +24,11 @@
((graph_a_chk, graph_b_chk), (<update>,...))
Where:
- <update> := (length, parent_rev, latest_rev, (CHK, ...))
+ <update> := (length, (parent_rev, ...), (head_revs, ...), (CHK, ...),
+ all_parent_revs, all_head_revs)
+
+ all_parent_revs is True iff all parent revs are included.
+ all_head_revs is True iff all parent revs are included.
top_key_data_to_bytes() converts from the tuple format to
a compact binary rep.
@@ -38,15 +42,22 @@ import struct
from binascii import hexlify, unhexlify
+from fcpconnection import sha1_hexdigest
+
from chk import CHK_SIZE, bytes_to_chk, chk_to_bytes
-from fcpconnection import sha1_hexdigest
+# Known versions:
+# 1.00 -- Initial release.
+# 2.00 -- Support for multiple head and parent versions and incomplete lists.
-MAJOR_VERSION = '1'
+HDR_V1 = 'HGINF100' # Obsolete
+
+MAJOR_VERSION = '2'
MINOR_VERSION = '00'
HDR_VERSION = MAJOR_VERSION + MINOR_VERSION
-HDR_BYTES = 'HGINF%s' % HDR_VERSION
+HDR_PREFIX = 'HGINF'
+HDR_BYTES = HDR_PREFIX + HDR_VERSION
# Header length 'HGINF100'
HDR_SIZE = 8
@@ -55,75 +66,137 @@ assert len(HDR_BYTES) == HDR_SIZE
# Length of the binary rep of an hg version
HGVER_SIZE = 20
-# <header bytes><salt byte><num graph chks>
-BASE_FMT = "!%isBB" % HDR_SIZE
-# bundle_len:parent_rev:latest_rev:CHK [:CHK]
-BASE_UPDATE_FMT = "!q%is%isB" % (HGVER_SIZE, HGVER_SIZE)
-# Binary rep of a single CHK
-CHK_FMT = "!%is" % CHK_SIZE
+# <header bytes><salt byte><num graph chks><num updates>
+BASE_FMT = "!%isBBB" % HDR_SIZE
+# <bundle_len><flags><parent_count><head_count><chk_count> \
+# [parent data][head data][chk data]
+BASE_UPDATE_FMT = "!qBBBB"
BASE_LEN = struct.calcsize(BASE_FMT)
BASE_UPDATE_LEN = struct.calcsize(BASE_UPDATE_FMT)
+# More pythonic way?
+# Hmmm... why are you using bit bashing in the 21st century?
+HAS_PARENTS = 0x01
+HAS_HEADS = 0x02
+
+def versions_to_bytes(versions):
+ """ INTERNAL: Return raw byte string from hg 40 digit hex
+ version list. """
+ bytes = ''
+ for version in versions:
+ try:
+ raw = unhexlify(version)
+ if len(raw) != HGVER_SIZE:
+ raise TypeError() # Hmmm... git'r done.
+ except TypeError:
+ # REDFLAG: Test code path.
+ raise ValueError("Couldn't parse 40 digit hex version from: "
+ + str(version))
+ bytes += raw
+ return bytes
+
def top_key_tuple_to_bytes(top_key_tuple, salt_byte=0):
""" Returns a binary representation of top_key_tuple. """
- ret = struct.pack(BASE_FMT, HDR_BYTES, salt_byte, len(top_key_tuple[0]))
+ ret = struct.pack(BASE_FMT, HDR_BYTES, salt_byte,
+ len(top_key_tuple[0]), len(top_key_tuple[1]))
for graph_chk in top_key_tuple[0]:
ret += chk_to_bytes(graph_chk)
+ # Can't find doc. True for all modern Python
+ assert int(True) == 1 and int(False) == 0
for update in top_key_tuple[1]:
- assert len(update[1]) == 40
- assert len(update[2]) == 40
- ret += struct.pack(BASE_UPDATE_FMT, update[0],
- unhexlify(update[1]),
- unhexlify(update[2]),
+ flags = (((int(update[4]) * 0xff) & HAS_PARENTS)
+ | ((int(update[5]) * 0xff) & HAS_HEADS))
+
+ ret += struct.pack(BASE_UPDATE_FMT,
+ update[0], flags,
+ len(update[1]), len(update[2]),
len(update[3]))
+
+ ret += versions_to_bytes(update[1]) # parents
+ ret += versions_to_bytes(update[2]) # heads
for chk in update[3]:
- chk_bytes = struct.pack(CHK_FMT, chk_to_bytes(chk))
+ chk_bytes = chk_to_bytes(chk)
assert len(chk_bytes) == CHK_SIZE
ret += chk_bytes
return ret
+def versions_from_bytes(version_bytes):
+ """ INTERNAL: Parse a list of hg 40 digit hex version strings from
+ a raw byte block. """
+ assert (len(version_bytes) % HGVER_SIZE) == 0
+ ret = []
+ for count in range(0, len(version_bytes) / HGVER_SIZE):
+ try:
+ ret.append(hexlify(version_bytes[count * HGVER_SIZE:
+ (count + 1) * HGVER_SIZE]))
+ except TypeError:
+ raise ValueError("Error parsing an hg version.")
+ return tuple(ret)
+
+def bytes_to_update_tuple(bytes):
+ """ INTERNAL: Read a single update from raw bytes. """
+ length, flags, parent_count, head_count, chk_count = struct.unpack(
+ BASE_UPDATE_FMT,
+ bytes[:BASE_UPDATE_LEN])
+
+ bytes = bytes[BASE_UPDATE_LEN:]
+
+ parents = versions_from_bytes(bytes[:HGVER_SIZE * parent_count])
+ bytes = bytes[HGVER_SIZE * parent_count:]
+
+ heads = versions_from_bytes(bytes[:HGVER_SIZE * head_count])
+ bytes = bytes[HGVER_SIZE * head_count:]
+
+ chks = []
+ for dummy in range(0, chk_count):
+ chks.append(bytes_to_chk(bytes[:CHK_SIZE]))
+ bytes = bytes[CHK_SIZE:]
+
+ return ((length, parents, heads, tuple(chks),
+ bool(flags & HAS_PARENTS), bool(flags & HAS_HEADS)),
+ bytes)
+
+
def bytes_to_top_key_tuple(bytes):
- """ Parses the top key data from a byte block and returns a tuple. """
+ """ Parses the top key data from a byte block and
+ returns a (top_key_tuple, header_string, salt_byte) tuple. """
if len(bytes) < BASE_LEN:
raise ValueError("Not enough data to parse static fields.")
+ if not bytes.startswith(HDR_PREFIX):
+ raise ValueError("Doesn't look like top key binary data.")
+
# Hmmm... return the salt byte?
- hdr, dummy, graph_chk_count = struct.unpack(BASE_FMT, bytes[:BASE_LEN])
+ hdr, salt, graph_chk_count, update_count = struct.unpack(BASE_FMT,
+ bytes[:BASE_LEN])
#print "bytes_to_top_key_data -- salt: ", dummy
bytes = bytes[BASE_LEN:]
if hdr != HDR_BYTES:
- print "bytes_to_top_key_data -- header doesn't match! Expect problems."
+ if hdr[5] != MAJOR_VERSION:
+ # DOH! should have done this in initial release.
+ raise ValueError("Format version mismatch. "
+ + "Maybe you're running old code?")
+ print "bytes_to_top_key_data -- minor version mismatch: ", hdr
if len(bytes) == 0:
print "bytes_to_top_key_data -- No updates?"
graph_chks = []
for dummy in range(0, graph_chk_count):
- graph_chks.append(bytes_to_chk(struct.unpack(CHK_FMT,
- bytes[:CHK_SIZE])[0]))
+ graph_chks.append(bytes_to_chk(bytes[:CHK_SIZE]))
bytes = bytes[CHK_SIZE:]
+ # REDFLAG: Fix range errors for incomplete / bad data.
updates = []
- while len(bytes) > BASE_UPDATE_LEN:
- length, raw_parent, raw_latest, chk_count = struct.unpack(
- BASE_UPDATE_FMT,
- bytes[:BASE_UPDATE_LEN])
+ for dummy in range(0, update_count):
+ update, bytes = bytes_to_update_tuple(bytes)
+ updates.append(update)
- bytes = bytes[BASE_UPDATE_LEN:]
- chks = []
- for dummy in range(0, chk_count):
- chks.append(bytes_to_chk(struct.unpack(CHK_FMT,
- bytes[:CHK_SIZE])[0]))
- bytes = bytes[CHK_SIZE:]
-
- updates.append((length, hexlify(raw_parent), hexlify(raw_latest),
- tuple(chks)))
-
- return (tuple(graph_chks), tuple(updates))
+ return ((tuple(graph_chks), tuple(updates)), hdr, salt)
def default_out(text):
""" Default output function for dump_top_key_tuple(). """
@@ -137,10 +210,18 @@ def dump_top_key_tuple(top_key_tuple, ou
for index, chk in enumerate(top_key_tuple[0]):
out_func("graph_%s:%s\n" % (chr(ord('a') + index), chk))
for index, update in enumerate(top_key_tuple[1]):
- out_func("update[%i]\n" % index)
- out_func(" length : %i\n" % update[0])
- out_func(" parent_rev: %s\n" % update[1])
- out_func(" latest_rev: %s\n" % update[2])
+ if update[4] and update[5]:
+ text = "full graph info"
+ elif not (update[4] or update[5]):
+ text = "incomplete parent, head lists"
+ elif not update[4]:
+ text = "incomplete parent list"
+ else:
+ text = "incomplete head list"
+ out_func("update[%i] (%s)\n" % (index, text))
+ out_func(" length : %i\n" % update[0])
+ out_func(" parents: %s\n" % ' '.join([ver[:12] for ver in update[1]]))
+ out_func(" heads : %s\n" % ' '.join([ver[:12] for ver in update[2]]))
for index, chk in enumerate(update[3]):
out_func(" CHK[%i]:%s\n" % (index, chk))
out_func("binary rep sha1:\n0x00:%s\n0xff:%s\n" %
diff --git a/infocalypse/updatesm.py b/infocalypse/updatesm.py
--- a/infocalypse/updatesm.py
+++ b/infocalypse/updatesm.py
@@ -36,12 +36,14 @@ from requestqueue import RequestQueue
from chk import clear_control_bytes
from bundlecache import make_temp_file, BundleException
from graph import INSERT_NORMAL, INSERT_PADDED, INSERT_SALTED_METADATA, \
- minimal_update_graph, graph_to_string, \
- FREENET_BLOCK_LEN, has_version, pull_bundle, parse_graph, hex_version
-
+ FREENET_BLOCK_LEN, has_version, \
+ pull_bundle, hex_version
+from graphutil import minimal_graph, graph_to_string, parse_graph
+from choose import get_top_key_updates
from topkey import bytes_to_top_key_tuple, top_key_tuple_to_bytes, \
dump_top_key_tuple
+
from statemachine import StatefulRequest, RequestQueueState, StateMachine, \
Quiescent, Canceling, RetryingRequestList, CandidateRequest, \
require_state, delete_client_file
@@ -55,6 +57,8 @@ HG_MIME_TYPE_FMT = HG_MIME_TYPE + ';%i'
METADATA_MARKER = HG_MIME_TYPE + ';'
PAD_BYTE = '\xff'
+MAX_SSK_LEN = 1024
+
class UpdateContext(dict):
""" A class to hold inter-state data used while the state machine is
running. """
@@ -80,14 +84,23 @@ class UpdateContext(dict):
# public key to update the private key.
self['IS_KEYPAIR'] = False
- self['TARGET_VERSION'] = None
+ self['TARGET_VERSIONS'] = None
self['INSERT_URI'] = 'CHK@'
self['REQUEST_URI'] = None
- def has_version(self, version):
- """ Returns True if version is already in the hg repository,
+ def has_versions(self, versions):
+ """ Returns True if all versions are already in the hg repository,
False otherwise. """
- return has_version(self.repo, version)
+ if versions is None:
+ return False # Allowed.
+
+ assert (type(versions) == type((0, )) or
+ type(versions) == type([0, ]))
+ assert len(versions) > 0
+ for version in versions:
+ if not has_version(self.repo, version):
+ return False
+ return True
def pull(self, file_name):
""" Pulls an hg bundle file into the local repository. """
@@ -177,8 +190,10 @@ class UpdateContext(dict):
raised = False
try:
bundle = self.parent.ctx.bundle_cache.make_bundle(self.graph,
- edge[:2],
- tmp_file)
+ self.parent.ctx.
+ version_table,
+ edge[:2],
+ tmp_file)
if bundle[0] != original_len:
raise BundleException("Wrong size. Expected: %i. Got: %i"
@@ -376,14 +391,16 @@ class InsertingGraph(StaticRequestList):
+ '\n')
# Create minimal graph that will fit in a 32k block.
- self.working_graph = minimal_update_graph(self.parent.ctx.graph,
- 31 * 1024, graph_to_string)
+ assert not self.parent.ctx.version_table is None
+ self.working_graph = minimal_graph(self.parent.ctx.graph,
+ self.parent.ctx.repo,
+ self.parent.ctx.version_table,
+ 31*1024)
if self.parent.params.get('DUMP_GRAPH', False):
self.parent.ctx.ui_.status("--- Minimal Graph ---\n")
- self.parent.ctx.ui_.status(graph_to_string(minimal_update_graph(
- self.working_graph,
- 31 * 1024, graph_to_string)) + '\n---\n')
+ self.parent.ctx.ui_.status(graph_to_string(self.working_graph)
+ + '\n---\n')
# Make sure the string rep is small enough!
graph_bytes = graph_to_string(self.working_graph)
@@ -408,46 +425,42 @@ class InsertingGraph(StaticRequestList):
StaticRequestList.reset(self)
self.working_graph = None
+ # REDFLAG: cache value? not cheap
def get_top_key_tuple(self):
""" Get the python rep of the data required to insert a new URI
with the updated graph CHK(s). """
graph = self.parent.ctx.graph
assert not graph is None
- return ((self.get_result(0)[1]['URI'],
- self.get_result(1)[1]['URI']),
- get_top_key_updates(graph))
-def get_top_key_updates(graph):
- """ Returns the update tuples needed to build the top key."""
+ # REDFLAG: graph redundancy hard coded to 2.
+ chks = (self.get_result(0)[1]['URI'], self.get_result(1)[1]['URI'])
- graph.rep_invariant()
+ # Slow.
+ updates = get_top_key_updates(graph, self.parent.ctx.repo)
- edges = graph.get_top_key_edges()
+ # Head revs are more important because they allow us to
+ # check whether the local repo is up to date.
- coalesced_edges = []
- ordinals = {}
- for edge in edges:
- assert edge[2] >= 0 and edge[2] < 2
- assert edge[2] == 0 or (edge[0], edge[1], 0) in edges
- ordinal = ordinals.get(edge[:2])
- if ordinal is None:
- ordinal = 0
- coalesced_edges.append(edge[:2])
- ordinals[edge[:2]] = max(ordinal, edge[2])
+ # Walk from the oldest to the newest update discarding
+ # base revs, then head revs until the binary rep will
+ # fit in an ssk.
+ index = len(updates) - 1
+ zorch_base = True
+ while (len(top_key_tuple_to_bytes((chks, updates))) >= MAX_SSK_LEN
+ and index >= 0):
+ victim = list(updates[index])
+ victim[1] = victim[1 + int(zorch_base)][:1] # Discard versions
+ victim[4 + int(zorch_base)] = False
+ updates[index] = tuple(victim)
+ if not zorch_base:
+ zorch_base = True
+ index -= 1
+ continue
+ zorch_base = False
- ret = []
- for edge in coalesced_edges:
- parent_rev = graph.index_table[edge[0]][1]
- latest_rev = graph.index_table[edge[1]][1]
- length = graph.get_length(edge)
- assert len(graph.edge_table[edge][1:]) > 0
+ assert len(top_key_tuple_to_bytes((chks, updates))) < MAX_SSK_LEN
- #(length, parent_rev, latest_rev, (CHK, ...))
- update = (length, parent_rev, latest_rev,
- graph.edge_table[edge][1:])
- ret.append(update)
-
- return ret
+ return (chks, updates)
class InsertingUri(StaticRequestList):
""" A state to insert the top level URI for an Infocalypse repository
@@ -579,7 +592,6 @@ class RequestingUri(StaticRequestList):
dump_top_key_tuple(self.get_top_key_tuple(),
self.parent.ctx.ui_.status)
-
def get_top_key_tuple(self):
""" Get the python rep of the data in the URI. """
top_key_tuple = None
@@ -587,7 +599,7 @@ class RequestingUri(StaticRequestList):
result = candidate[5]
if result is None or result[0] != 'AllData':
continue
- top_key_tuple = bytes_to_top_key_tuple(result[2])
+ top_key_tuple = bytes_to_top_key_tuple(result[2])[0]
break
assert not top_key_tuple is None
return top_key_tuple
@@ -700,26 +712,13 @@ class RequestingGraph(StaticRequestList)
StaticRequestList.__init__(self, parent, name, success_state,
failure_state)
- # REDFLAG: remove this? why aren't I just calling get_top_key_tuple
- # on REQUESTING_URI_4_INSERT???
- def get_top_key_tuple(self):
- """ Returns the Python rep of the data in the request uri. """
- results = [candidate[5] for candidate in
- self.parent.get_state(REQUESTING_URI_4_INSERT).ordered]
- top_key_tuple = None
- for result in results:
- if result is None or result[0] != 'AllData':
- continue
- top_key_tuple = bytes_to_top_key_tuple(result[2])
- break
- assert not top_key_tuple is None
- return top_key_tuple
-
def enter(self, from_state):
""" Implementation of State virtual. """
require_state(from_state, REQUESTING_URI_4_INSERT)
+ top_key_tuple = (self.parent.get_state(REQUESTING_URI_4_INSERT).
+ get_top_key_tuple())
- top_key_tuple = self.get_top_key_tuple()
+ #top_key_tuple = self.get_top_key_tuple() REDFLAG: remove
#print "TOP_KEY_TUPLE", top_key_tuple
#[uri, tries, is_insert, raw_data, mime_type, last_msg]
for uri in top_key_tuple[0]:
@@ -736,7 +735,7 @@ class RequestingGraph(StaticRequestList)
result = candidate[5]
if not result is None and result[0] == 'AllData':
graph = parse_graph(result[2])
- break
+
assert not graph is None
self.parent.ctx.graph = graph
@@ -868,19 +867,19 @@ class UpdateStateMachine(RequestQueue, S
self.ctx = ctx
- def start_inserting(self, graph, to_version, insert_uri='CHK@'):
+ def start_inserting(self, graph, to_versions, insert_uri='CHK@'):
""" Start and insert of the graph and any required new edge CHKs
to the insert URI. """
self.require_state(QUIESCENT)
self.reset()
self.ctx.graph = graph
- self.ctx['TARGET_VERSION'] = to_version
+ self.ctx['TARGET_VERSIONS'] = to_versions
self.ctx['INSERT_URI'] = insert_uri
self.transition(INSERTING_BUNDLES)
# Update a repo USK.
# REDFLAG: later, keys_match=False arg
- def start_pushing(self, insert_uri, to_version='tip', request_uri=None,
+ def start_pushing(self, insert_uri, to_versions=('tip',), request_uri=None,
is_keypair=False):
""" Start pushing local changes up to to_version to an existing
@@ -892,7 +891,8 @@ class UpdateStateMachine(RequestQueue, S
self.ctx['INSERT_URI'] = insert_uri
self.ctx['REQUEST_URI'] = request_uri
# Hmmmm... better exception if to_version isn't in the repo?
- self.ctx['TARGET_VERSION'] = hex_version(self.ctx.repo, to_version)
+ self.ctx['TARGET_VERSIONS'] = tuple([hex_version(self.ctx.repo, ver)
+ for ver in to_versions])
if request_uri is None:
self.ctx['IS_KEYPAIR'] = True
self.transition(INVERTING_URI_4_INSERT)