1
# Copyright (C) 2005, 2006 Canonical Ltd
1
# (C) 2005, 2006 Canonical Limited.
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
162
def merge_sort(graph, branch_tip, mainline_revisions=None, generate_revno=False):
162
def merge_sort(graph, branch_tip, mainline_revisions=None):
163
163
"""Topological sort a graph which groups merges.
165
165
:param graph: sequence of pairs of node->parents_list.
174
174
old revision listed in the mainline revisions
176
176
The order for this parameter is oldest-first.
177
:param generate_revno: Optional parameter controlling the generation of
178
revision number sequences in the output. See the output description of
179
the MergeSorter docstring for details.
180
:result: See the MergeSorter docstring for details.
178
The result is a list of node names, such that all parents come before
181
181
node identifiers can be any hashable object, and are typically strings.
183
return MergeSorter(graph, branch_tip, mainline_revisions,
184
generate_revno).sorted()
183
return MergeSorter(graph, branch_tip, mainline_revisions).sorted()
187
186
class MergeSorter(object):
189
def __init__(self, graph, branch_tip, mainline_revisions=None,
190
generate_revno=False):
188
def __init__(self, graph, branch_tip, mainline_revisions=None):
191
189
"""Merge-aware topological sorting of a graph.
193
191
:param graph: sequence of pairs of node_name->parent_names_list.
206
204
old revision listed in the mainline revisions
208
206
The order for this parameter is oldest-first.
209
:param generate_revno: Optional parameter controlling the generation of
210
revision number sequences in the output. See the output description
213
The result is a list sorted so that all parents come before
214
their children. Each element of the list is a tuple containing:
215
(sequence_number, node_name, merge_depth, end_of_merge)
216
* sequence_number: The sequence of this row in the output. Useful for
218
* node_name: The node name: opaque text to the merge routine.
219
* merge_depth: How many levels of merging deep this node has been
221
* revno_sequence: When requested this field provides a sequence of
222
revision numbers for all revisions. The format is:
223
REVNO[[.BRANCHREVNO.REVNO] ...]. BRANCHREVNO is the number of the
224
branch that the revno is on. From left to right the REVNO numbers
225
are the sequence numbers within that branch of the revision.
226
For instance, the graph {A:[], B:['A'], C:['A', 'B']} will get
227
the following revno_sequences assigned: A:(1,), B:(1,1,1), C:(2,).
228
This should be read as 'A is the first commit in the trunk',
229
'B is the first commit on the first branch made from A', 'C is the
230
second commit in the trunk'.
231
* end_of_merge: When True the next node is part of a different merge.
234
209
node identifiers can be any hashable object, and are typically strings.
310
285
XXXX revisit when awake. ddaa asks about the relevance of each one
311
286
- maybe more than one parent is relevant
313
self._generate_revno = generate_revno
314
288
# a dict of the graph.
315
289
self._graph = dict(graph)
316
290
# if there is an explicit mainline, alter the graph to match. This is
341
315
# which requires the parents to be accessible: its easier for now
342
316
# to just keep the original graph around.
343
317
self._original_graph = dict(self._graph.items())
344
# we need to know the revision numbers of revisions to determine
345
# the revision numbers of their descendants
346
# this is a graph from node to [revno_tuple, sequence_number]
347
# where sequence is the number of branches made from the node,
348
# and revno_tuple is the tuple that was assigned to the node.
349
# we dont know revnos to start with, so we start it seeded with
351
self._revnos = dict((revision, [None, 0]) for revision in self._graph)
352
# the global implicit root node has revno 0, but we need to know
353
# the sequence number for it too:
354
self._root_sequence = 0
356
319
# this is a stack storing the depth first search into the graph.
357
320
self._node_name_stack = []
361
324
# stack stores the parents we have not yet checked for the node at the
362
325
# matching depth in _node_name_stack
363
326
self._pending_parents_stack = []
364
# When we first look at a node we assign it a seqence number from its
366
self._assigned_sequence_stack = []
367
327
# this is a set of the nodes who have been completely analysed for fast
368
328
# membership checking
369
329
self._completed_node_names = set()
383
343
# This records for each node when we have processed its left most
384
344
# unmerged subtree. After this subtree is scheduled, all other subtrees
385
345
# have their merge depth increased by one from this nodes merge depth.
386
# it contains tuples - name, merge_depth
387
self._left_subtree_pushed_stack = []
346
self._left_subtree_done_stack = []
389
348
# seed the search with the tip of the branch
390
349
if branch_tip is not None:
417
376
while self._pending_parents_stack[-1]:
418
if not self._left_subtree_pushed_stack[-1]:
377
if not self._left_subtree_done_stack[-1]:
419
378
# recurse depth first into the primary parent
420
379
next_node_name = self._pending_parents_stack[-1].pop(0)
443
402
# this indicates a cycle.
444
403
raise errors.GraphCycleError(self._node_name_stack)
445
404
next_merge_depth = 0
446
if self._left_subtree_pushed_stack[-1]:
447
# a new child branch from name_stack[-1]
405
if self._left_subtree_done_stack[-1]:
448
406
next_merge_depth = 1
450
408
next_merge_depth = 0
451
self._left_subtree_pushed_stack[-1] = True
409
self._left_subtree_done_stack[-1] = True
452
410
next_merge_depth = (
453
411
self._node_merge_depth_stack[-1] + next_merge_depth)
461
419
# We have scheduled the graph. Now deliver the ordered output:
462
420
sequence_number = 0
463
421
while self._scheduled_nodes:
464
node_name, merge_depth, revno = self._scheduled_nodes.pop()
422
node_name, merge_depth = self._scheduled_nodes.pop()
465
423
if node_name == self._stop_revision:
467
425
if not len(self._scheduled_nodes):
468
# last revision is the end of a merge
469
426
end_of_merge = True
470
427
elif self._scheduled_nodes[-1][1] < merge_depth:
471
428
# the next node is to our left
477
434
end_of_merge = True
479
436
end_of_merge = False
480
if self._generate_revno:
481
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
483
yield (sequence_number, node_name, merge_depth, end_of_merge)
437
yield (sequence_number, node_name, merge_depth, end_of_merge)
484
438
sequence_number += 1
486
440
def _push_node(self, node_name, merge_depth, parents):
492
446
self._node_name_stack.append(node_name)
493
447
self._node_merge_depth_stack.append(merge_depth)
494
self._left_subtree_pushed_stack.append(False)
448
self._left_subtree_done_stack.append(False)
495
449
self._pending_parents_stack.append(list(parents))
496
# as we push it, assign it a sequence number against its parent:
497
parents = self._original_graph[node_name]
499
# node has parents, assign from the left most parent.
500
parent_revno = self._revnos[parents[0]]
501
sequence = parent_revno[1]
504
# no parents, use the root sequence
505
sequence = self._root_sequence
506
self._root_sequence +=1
507
self._assigned_sequence_stack.append(sequence)
509
451
def _pop_node(self):
510
452
"""Pop the top node off the stack
515
457
# pop off the local variables
516
458
node_name = self._node_name_stack.pop()
517
459
merge_depth = self._node_merge_depth_stack.pop()
518
sequence = self._assigned_sequence_stack.pop()
519
# remove this node from the pending lists:
520
self._left_subtree_pushed_stack.pop()
460
self._left_subtree_done_stack.pop()
521
461
self._pending_parents_stack.pop()
523
parents = self._original_graph[node_name]
525
# node has parents, assign from the left most parent.
526
parent_revno = self._revnos[parents[0]]
528
# not the first child, make a new branch
529
revno = parent_revno[0] + (sequence, 1)
531
# increment the sequence number within the branch
532
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
534
# no parents, use the root sequence
536
# make a parallel import revision number
537
revno = (0, sequence, 1)
541
# store the revno for this node for future reference
542
self._revnos[node_name][0] = revno
543
463
self._completed_node_names.add(node_name)
544
self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
464
self._scheduled_nodes.append((node_name, merge_depth))
added
removed
bzrlib/tsort.py
