Fixed fn-reinsert --level 3 so that every update appears in at least two re-inserted CHKs if possible.
diff --git a/infocalypse/graph.py b/infocalypse/graph.py
--- a/infocalypse/graph.py
+++ b/infocalypse/graph.py
@@ -953,33 +953,6 @@ def get_heads(graph, to_index=None):
heads.sort()
return tuple(heads)
-def get_huge_top_key_edges(graph, extant=False):
- """ Get the list of edges in the top key edges (and
- alternates) that are too big to salt.
-
- If extant is True, return existing edges.
- If extent is False, return edges that could be added. """
- ret = []
- edges = graph.get_top_key_edges()
- for edge in edges:
- if graph.get_length(edge) > MAX_METADATA_HACK_LEN:
- if edge[2] == 1:
- assert graph.insert_type(edge) == INSERT_HUGE
- if extant and (not alternate in ret):
- ret.append(edge)
- else:
- assert edge[2] == 0
- assert graph.insert_type(edge) == INSERT_NORMAL
- alternate = (edge[0], edge[1], 1)
- if graph.is_redundant(edge):
- assert graph.insert_type(alternate) == INSERT_HUGE
- if extant and (not alternate in ret):
- ret.append(alternate)
- else:
- if (not extant) and (not alternate in ret):
- ret.append(alternate)
-
- return ret
# ASSUMPTIONS:
# 0) head which don't appear in bases are tip heads. True?
diff --git a/infocalypse/graphutil.py b/infocalypse/graphutil.py
--- a/infocalypse/graphutil.py
+++ b/infocalypse/graphutil.py
@@ -23,7 +23,8 @@
from binascii import hexlify
from graph import FIRST_INDEX, MAX_PATH_LEN, UpdateGraph, \
- UpdateGraphException, canonical_path_itr
+ UpdateGraphException, canonical_path_itr, edges_containing, INSERT_HUGE, \
+ INSERT_NORMAL, MAX_METADATA_HACK_LEN
############################################################
# Doesn't dump FIRST_INDEX entry.
@@ -395,3 +396,80 @@ def minimal_graph(graph, repo, version_t
return prev_minimal
+# REDFLAG: todo, find other places where I should be using this func.
+def find_alternate_edges(graph, edges):
+ """ Find alternate redundant edges that aren't already in edges. """
+ alternate_edges = []
+ for edge in edges:
+ if graph.is_redundant(edge):
+ alternate_edge = (edge[0], edge[1], int(not edge[2]))
+ if not alternate_edge in edges:
+ alternate_edges.append(alternate_edge)
+ return alternate_edges
+
+def find_redundant_edges(graph, current_edges, skip_huge=True):
+ """ Find the edges you would need to add to make current_edges
+ fully redundant.
+
+ Return an (edge_list, failed_indices) with the alternate edges
+ and indices which only appear in a single edge.
+ """
+ def increment_counts(counts, for_edge):
+ """ INTERNAL: Increment count for every index contained by for_edge.
+ """
+ for index in range(for_edge[0] + 1, for_edge[1] + 1):
+ counts[index] = counts[index] + 1
+
+ # Empty redundancy counts for all indexes
+ redundancy = [0, ] * (graph.latest_index + 1)
+
+ edges = set(current_edges)
+ for edge in edges:
+ increment_counts(redundancy, edge)
+
+ failed_indices = []
+ redundant_edges = []
+ for index in range(0, len(redundancy)):
+ if redundancy[index] < 2:
+ candidates = edges_containing(graph, index)
+ while len(candidates) and redundancy[index] < 2:
+ candidate = candidates.pop()
+ if candidate in edges:
+ continue
+ if graph.insert_type(candidate) == INSERT_HUGE and skip_huge:
+ continue
+ redundant_edges.append(candidate)
+ increment_counts(redundancy, candidate)
+ if redundancy[index] < 2:
+ failed_indices.append(index)
+
+ return (redundant_edges, failed_indices)
+
+def get_huge_top_key_edges(graph, extant=False):
+ """ Get the list of edges in the top key edges (and
+ alternates) that are too big to salt.
+
+ If extant is True, return existing edges.
+ If extent is False, return edges that could be added. """
+ ret = []
+ edges = graph.get_top_key_edges()
+ edges += find_redundant_edges(graph, edges, False)[0]
+ for edge in edges:
+ if graph.get_length(edge) > MAX_METADATA_HACK_LEN:
+ if edge[2] == 1:
+ assert graph.insert_type(edge) == INSERT_HUGE
+ if extant and (not alternate in ret):
+ ret.append(edge)
+ else:
+ assert edge[2] == 0
+ assert graph.insert_type(edge) == INSERT_NORMAL
+ alternate = (edge[0], edge[1], 1)
+ if graph.is_redundant(edge):
+ assert graph.insert_type(alternate) == INSERT_HUGE
+ if extant and (not alternate in ret):
+ ret.append(alternate)
+ else:
+ if (not extant) and (not alternate in ret):
+ ret.append(alternate)
+
+ return ret
diff --git a/infocalypse/insertingbundles.py b/infocalypse/insertingbundles.py
--- a/infocalypse/insertingbundles.py
+++ b/infocalypse/insertingbundles.py
@@ -22,8 +22,9 @@
from graph import UpToDate, INSERT_SALTED_METADATA, INSERT_HUGE, \
FREENET_BLOCK_LEN, build_version_table, get_heads, \
- PENDING_INSERT1, get_huge_top_key_edges
-from graphutil import graph_to_string
+ PENDING_INSERT1
+from graphutil import graph_to_string, find_redundant_edges, \
+ find_alternate_edges, get_huge_top_key_edges
from bundlecache import BundleException
from statemachine import RequestQueueState
@@ -283,13 +284,22 @@ class InsertingBundles(RequestQueueState
# Only the latest update.
self.new_edges = self.new_edges[:1]
- redundant = []
- for edge in self.new_edges:
- if graph.is_redundant(edge):
- alternate_edge = (edge[0], edge[1], int(not edge[2]))
- if not alternate_edge in self.new_edges:
- redundant.append(alternate_edge)
- self.new_edges += redundant
+ else:
+ pass
+
+ # Add alternate CHKs for the same bundle.
+ self.new_edges += find_alternate_edges(graph, self.new_edges)
+ if level == 3:
+ # Add CHKs for other bundles to make sure that each
+ # change occurs in at least two CHKS (i.e. edges) if
+ # possible.
+ other_edges, failed = find_redundant_edges(graph,
+ self.new_edges,
+ True)
+ self.new_edges += other_edges
+ for index in failed:
+ self.parent.ctx.ui_.status("Non-redundant index: %i\n"
+ % index)
for edge in self.new_edges[:]: # Deep copy!
if graph.insert_type(edge) == INSERT_HUGE:
# User can do this with level == 5
@@ -305,5 +315,5 @@ class InsertingBundles(RequestQueueState
graph.add_edge(edge[:2],
(graph.get_length(edge), PENDING_INSERT1))
elif level == 5: # Reinsert big updates.
- self.new_edges = get_huge_top_key_edges(graph, True)
+ self.new_edges = get_huge_top_key_edges(graph, True)
self._check_new_edges("There are no big edges to re-insert.")