40
41
self.parent_keys, self.child_keys)
44
class _MergeSortNode(object):
45
"""Information about a specific node in the merge graph."""
47
__slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge')
49
def __init__(self, key, merge_depth, revno, end_of_merge):
51
self.merge_depth = merge_depth
53
self.end_of_merge = end_of_merge
43
56
class KnownGraph(object):
44
57
"""This is a class which assumes we already know the full graph."""
171
184
self._known_heads[heads_key] = heads
188
"""Return the nodes in topological order.
190
All parents must occur before all children.
192
for node in self._nodes.itervalues():
193
if node.gdfo is None:
194
raise errors.GraphCycleError(self._nodes)
195
pending = self._find_tails()
196
pending_pop = pending.pop
197
pending_append = pending.append
200
topo_order_append = topo_order.append
202
num_seen_parents = dict.fromkeys(self._nodes, 0)
205
if node.parent_keys is not None:
206
# We don't include ghost parents
207
topo_order_append(node.key)
208
for child_key in node.child_keys:
209
child_node = self._nodes[child_key]
210
seen_parents = num_seen_parents[child_key] + 1
211
if seen_parents == len(child_node.parent_keys):
212
# All parents have been processed, enqueue this child
213
pending_append(child_node)
214
# This has been queued up, stop tracking it
215
del num_seen_parents[child_key]
217
num_seen_parents[child_key] = seen_parents
218
# We started from the parents, so we don't need to do anymore work
221
def merge_sort(self, tip_key):
222
"""Compute the merge sorted graph output."""
223
from bzrlib import tsort
224
as_parent_map = dict((node.key, node.parent_keys)
225
for node in self._nodes.itervalues()
226
if node.parent_keys is not None)
227
# We intentionally always generate revnos and never force the
229
# Strip the sequence_number that merge_sort generates
230
return [_MergeSortNode(key, merge_depth, revno, end_of_merge)
231
for _, key, merge_depth, revno, end_of_merge
232
in tsort.merge_sort(as_parent_map, tip_key,
233
mainline_revisions=None,
234
generate_revno=True)]
added
removed
bzrlib/_known_graph_py.py
