1
# (C) 2005, 2006 Canonical Limited.
1
# Copyright (C) 2005, 2006 Canonical Ltd
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):
162
def merge_sort(graph, branch_tip, mainline_revisions=None, generate_revno=False):
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.
178
The result is a list of node names, such that all parents come before
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.
181
181
node identifiers can be any hashable object, and are typically strings.
183
return MergeSorter(graph, branch_tip, mainline_revisions).sorted()
183
return MergeSorter(graph, branch_tip, mainline_revisions,
184
generate_revno).sorted()
186
187
class MergeSorter(object):
188
def __init__(self, graph, branch_tip, mainline_revisions=None):
189
def __init__(self, graph, branch_tip, mainline_revisions=None,
190
generate_revno=False):
189
191
"""Merge-aware topological sorting of a graph.
191
193
:param graph: sequence of pairs of node_name->parent_names_list.
204
206
old revision listed in the mainline revisions
206
208
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.
209
234
node identifiers can be any hashable object, and are typically strings.
285
310
XXXX revisit when awake. ddaa asks about the relevance of each one
286
311
- maybe more than one parent is relevant
313
self._generate_revno = generate_revno
288
314
# a dict of the graph.
289
315
self._graph = dict(graph)
290
316
# if there is an explicit mainline, alter the graph to match. This is
315
341
# which requires the parents to be accessible: its easier for now
316
342
# to just keep the original graph around.
317
343
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
319
356
# this is a stack storing the depth first search into the graph.
320
357
self._node_name_stack = []
324
361
# stack stores the parents we have not yet checked for the node at the
325
362
# matching depth in _node_name_stack
326
363
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 = []
327
367
# this is a set of the nodes who have been completely analysed for fast
328
368
# membership checking
329
369
self._completed_node_names = set()
343
383
# This records for each node when we have processed its left most
344
384
# unmerged subtree. After this subtree is scheduled, all other subtrees
345
385
# have their merge depth increased by one from this nodes merge depth.
346
self._left_subtree_done_stack = []
386
# it contains tuples - name, merge_depth
387
self._left_subtree_pushed_stack = []
348
389
# seed the search with the tip of the branch
349
390
if branch_tip is not None:
376
417
while self._pending_parents_stack[-1]:
377
if not self._left_subtree_done_stack[-1]:
418
if not self._left_subtree_pushed_stack[-1]:
378
419
# recurse depth first into the primary parent
379
420
next_node_name = self._pending_parents_stack[-1].pop(0)
402
443
# this indicates a cycle.
403
444
raise errors.GraphCycleError(self._node_name_stack)
404
445
next_merge_depth = 0
405
if self._left_subtree_done_stack[-1]:
446
if self._left_subtree_pushed_stack[-1]:
447
# a new child branch from name_stack[-1]
406
448
next_merge_depth = 1
408
450
next_merge_depth = 0
409
self._left_subtree_done_stack[-1] = True
451
self._left_subtree_pushed_stack[-1] = True
410
452
next_merge_depth = (
411
453
self._node_merge_depth_stack[-1] + next_merge_depth)
419
461
# We have scheduled the graph. Now deliver the ordered output:
420
462
sequence_number = 0
421
463
while self._scheduled_nodes:
422
node_name, merge_depth = self._scheduled_nodes.pop()
464
node_name, merge_depth, revno = self._scheduled_nodes.pop()
423
465
if node_name == self._stop_revision:
425
467
if not len(self._scheduled_nodes):
468
# last revision is the end of a merge
426
469
end_of_merge = True
427
470
elif self._scheduled_nodes[-1][1] < merge_depth:
428
471
# the next node is to our left
434
477
end_of_merge = True
436
479
end_of_merge = False
437
yield (sequence_number, node_name, merge_depth, end_of_merge)
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)
438
484
sequence_number += 1
440
486
def _push_node(self, node_name, merge_depth, parents):
446
492
self._node_name_stack.append(node_name)
447
493
self._node_merge_depth_stack.append(merge_depth)
448
self._left_subtree_done_stack.append(False)
494
self._left_subtree_pushed_stack.append(False)
449
495
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)
451
509
def _pop_node(self):
452
510
"""Pop the top node off the stack
457
515
# pop off the local variables
458
516
node_name = self._node_name_stack.pop()
459
517
merge_depth = self._node_merge_depth_stack.pop()
460
self._left_subtree_done_stack.pop()
518
sequence = self._assigned_sequence_stack.pop()
519
# remove this node from the pending lists:
520
self._left_subtree_pushed_stack.pop()
461
521
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
463
543
self._completed_node_names.add(node_name)
464
self._scheduled_nodes.append((node_name, merge_depth))
544
self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
added
removed
bzrlib/tsort.py
