178
174
old revision listed in the mainline revisions
180
176
The order for this parameter is oldest-first.
181
:param generate_revno: Optional parameter controlling the generation of
182
revision number sequences in the output. See the output description of
183
the MergeSorter docstring for details.
184
:result: See the MergeSorter docstring for details.
178
The result is a list of node names, such that all parents come before
185
181
node identifiers can be any hashable object, and are typically strings.
187
return MergeSorter(graph, branch_tip, mainline_revisions,
188
generate_revno).sorted()
183
return MergeSorter(graph, branch_tip, mainline_revisions).sorted()
191
186
class MergeSorter(object):
193
__slots__ = ['_node_name_stack',
194
'_node_merge_depth_stack',
195
'_pending_parents_stack',
196
'_first_child_stack',
197
'_left_subtree_pushed_stack',
200
'_mainline_revisions',
204
'_revno_to_branch_count',
205
'_completed_node_names',
209
def __init__(self, graph, branch_tip, mainline_revisions=None,
210
generate_revno=False):
188
def __init__(self, graph, branch_tip, mainline_revisions=None):
211
189
"""Merge-aware topological sorting of a graph.
213
191
:param graph: sequence of pairs of node_name->parent_names_list.
226
204
old revision listed in the mainline revisions
228
206
The order for this parameter is oldest-first.
229
:param generate_revno: Optional parameter controlling the generation of
230
revision number sequences in the output. See the output description
233
The result is a list sorted so that all parents come before
234
their children. Each element of the list is a tuple containing:
235
(sequence_number, node_name, merge_depth, end_of_merge)
236
* sequence_number: The sequence of this row in the output. Useful for
238
* node_name: The node name: opaque text to the merge routine.
239
* merge_depth: How many levels of merging deep this node has been
241
* revno_sequence: When requested this field provides a sequence of
242
revision numbers for all revisions. The format is:
243
(REVNO, BRANCHNUM, BRANCHREVNO). BRANCHNUM is the number of the
244
branch that the revno is on. From left to right the REVNO numbers
245
are the sequence numbers within that branch of the revision.
246
For instance, the graph {A:[], B:['A'], C:['A', 'B']} will get
247
the following revno_sequences assigned: A:(1,), B:(1,1,1), C:(2,).
248
This should be read as 'A is the first commit in the trunk',
249
'B is the first commit on the first branch made from A', 'C is the
250
second commit in the trunk'.
251
* end_of_merge: When True the next node is part of a different merge.
254
209
node identifiers can be any hashable object, and are typically strings.
367
315
# which requires the parents to be accessible: its easier for now
368
316
# to just keep the original graph around.
369
317
self._original_graph = dict(self._graph.items())
370
# we need to know the revision numbers of revisions to determine
371
# the revision numbers of their descendants
372
# this is a graph from node to [revno_tuple, first_child]
373
# where first_child is True if no other children have seen this node
374
# and revno_tuple is the tuple that was assigned to the node.
375
# we dont know revnos to start with, so we start it seeded with
377
self._revnos = dict((revision, [None, True])
378
for revision in self._graph)
379
# Each mainline revision counts how many child branches have spawned from it.
380
self._revno_to_branch_count = {}
382
319
# this is a stack storing the depth first search into the graph.
383
320
self._node_name_stack = []
431
363
After finishing iteration the sorter is empty and you cannot continue
434
# These are safe to offload to local variables, because they are used
435
# as a stack and modified in place, never assigned to.
436
node_name_stack = self._node_name_stack
437
node_merge_depth_stack = self._node_merge_depth_stack
438
pending_parents_stack = self._pending_parents_stack
439
left_subtree_pushed_stack = self._left_subtree_pushed_stack
440
completed_node_names = self._completed_node_names
441
scheduled_nodes = self._scheduled_nodes
443
graph_pop = self._graph.pop
445
def push_node(node_name, merge_depth, parents,
446
node_name_stack_append=node_name_stack.append,
447
node_merge_depth_stack_append=node_merge_depth_stack.append,
448
left_subtree_pushed_stack_append=left_subtree_pushed_stack.append,
449
pending_parents_stack_append=pending_parents_stack.append,
450
first_child_stack_append=self._first_child_stack.append,
453
"""Add node_name to the pending node stack.
455
Names in this stack will get emitted into the output as they are popped
458
This inlines a lot of self._variable.append functions as local
461
node_name_stack_append(node_name)
462
node_merge_depth_stack_append(merge_depth)
463
left_subtree_pushed_stack_append(False)
464
pending_parents_stack_append(list(parents))
465
# as we push it, check if it is the first child
467
# node has parents, assign from the left most parent.
468
parent_info = revnos[parents[0]]
469
first_child = parent_info[1]
470
parent_info[1] = False
472
# We don't use the same algorithm here, but we need to keep the
475
first_child_stack_append(first_child)
477
def pop_node(node_name_stack_pop=node_name_stack.pop,
478
node_merge_depth_stack_pop=node_merge_depth_stack.pop,
479
first_child_stack_pop=self._first_child_stack.pop,
480
left_subtree_pushed_stack_pop=left_subtree_pushed_stack.pop,
481
pending_parents_stack_pop=pending_parents_stack.pop,
482
original_graph=self._original_graph,
484
completed_node_names_add=self._completed_node_names.add,
485
scheduled_nodes_append=scheduled_nodes.append,
486
revno_to_branch_count=self._revno_to_branch_count,
488
"""Pop the top node off the stack
490
The node is appended to the sorted output.
492
# we are returning from the flattened call frame:
493
# pop off the local variables
494
node_name = node_name_stack_pop()
495
merge_depth = node_merge_depth_stack_pop()
496
first_child = first_child_stack_pop()
497
# remove this node from the pending lists:
498
left_subtree_pushed_stack_pop()
499
pending_parents_stack_pop()
501
parents = original_graph[node_name]
503
# node has parents, assign from the left most parent.
504
parent_revno = revnos[parents[0]][0]
506
# not the first child, make a new branch
507
base_revno = parent_revno[0]
508
branch_count = revno_to_branch_count.get(base_revno, 0)
510
revno_to_branch_count[base_revno] = branch_count
511
revno = (parent_revno[0], branch_count, 1)
512
# revno = (parent_revno[0], branch_count, parent_revno[-1]+1)
514
# as the first child, we just increase the final revision
516
revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
518
# no parents, use the root sequence
519
root_count = revno_to_branch_count.get(0, -1)
522
revno = (0, root_count, 1)
525
revno_to_branch_count[0] = root_count
527
# store the revno for this node for future reference
528
revnos[node_name][0] = revno
529
completed_node_names_add(node_name)
530
scheduled_nodes_append((node_name, merge_depth, revno))
534
while node_name_stack:
366
while self._node_name_stack:
535
367
# loop until this call completes.
536
parents_to_visit = pending_parents_stack[-1]
368
parents_to_visit = self._pending_parents_stack[-1]
537
369
# if all parents are done, the revision is done
538
370
if not parents_to_visit:
539
371
# append the revision to the topo sorted scheduled list:
540
372
# all the nodes parents have been scheduled added, now
541
373
# we can add it to the output.
544
while pending_parents_stack[-1]:
545
if not left_subtree_pushed_stack[-1]:
376
while self._pending_parents_stack[-1]:
377
if not self._left_subtree_done_stack[-1]:
546
378
# recurse depth first into the primary parent
547
next_node_name = pending_parents_stack[-1].pop(0)
379
next_node_name = self._pending_parents_stack[-1].pop(0)
549
381
# place any merges in right-to-left order for scheduling
550
382
# which gives us left-to-right order after we reverse
553
385
# subtree rather than the left most, which will
554
386
# display nicely (you get smaller trees at the top
555
387
# of the combined merge).
556
next_node_name = pending_parents_stack[-1].pop()
557
if next_node_name in completed_node_names:
388
next_node_name = self._pending_parents_stack[-1].pop()
389
if next_node_name in self._completed_node_names:
558
390
# this parent was completed by a child on the
559
391
# call stack. skip it.
561
393
# otherwise transfer it from the source graph into the
562
394
# top of the current depth first search stack.
564
parents = graph_pop(next_node_name)
396
parents = self._graph.pop(next_node_name)
566
398
# if the next node is not in the source graph it has
567
399
# already been popped from it and placed into the
568
400
# current search stack (but not completed or we would
569
401
# have hit the continue 4 lines up.
570
402
# this indicates a cycle.
571
raise errors.GraphCycleError(node_name_stack)
403
raise errors.GraphCycleError(self._node_name_stack)
572
404
next_merge_depth = 0
573
if left_subtree_pushed_stack[-1]:
574
# a new child branch from name_stack[-1]
405
if self._left_subtree_done_stack[-1]:
575
406
next_merge_depth = 1
577
408
next_merge_depth = 0
578
left_subtree_pushed_stack[-1] = True
409
self._left_subtree_done_stack[-1] = True
579
410
next_merge_depth = (
580
node_merge_depth_stack[-1] + next_merge_depth)
411
self._node_merge_depth_stack[-1] + next_merge_depth)
583
414
next_merge_depth,
585
416
# and do not continue processing parents until this 'call'
589
419
# We have scheduled the graph. Now deliver the ordered output:
590
420
sequence_number = 0
591
stop_revision = self._stop_revision
592
generate_revno = self._generate_revno
593
original_graph = self._original_graph
595
while scheduled_nodes:
596
node_name, merge_depth, revno = scheduled_nodes.pop()
597
if node_name == stop_revision:
421
while self._scheduled_nodes:
422
node_name, merge_depth = self._scheduled_nodes.pop()
423
if node_name == self._stop_revision:
599
if not len(scheduled_nodes):
600
# last revision is the end of a merge
425
if not len(self._scheduled_nodes):
601
426
end_of_merge = True
602
elif scheduled_nodes[-1][1] < merge_depth:
427
elif self._scheduled_nodes[-1][1] < merge_depth:
603
428
# the next node is to our left
604
429
end_of_merge = True
605
elif (scheduled_nodes[-1][1] == merge_depth and
606
(scheduled_nodes[-1][0] not in
607
original_graph[node_name])):
430
elif (self._scheduled_nodes[-1][1] == merge_depth and
431
(self._scheduled_nodes[-1][0] not in
432
self._original_graph[node_name])):
608
433
# the next node was part of a multiple-merge.
609
434
end_of_merge = True
611
436
end_of_merge = False
613
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
615
yield (sequence_number, node_name, merge_depth, end_of_merge)
437
yield (sequence_number, node_name, merge_depth, end_of_merge)
616
438
sequence_number += 1
618
440
def _push_node(self, node_name, merge_depth, parents):
647
457
# pop off the local variables
648
458
node_name = self._node_name_stack.pop()
649
459
merge_depth = self._node_merge_depth_stack.pop()
650
first_child = self._first_child_stack.pop()
651
# remove this node from the pending lists:
652
self._left_subtree_pushed_stack.pop()
460
self._left_subtree_done_stack.pop()
653
461
self._pending_parents_stack.pop()
655
parents = self._original_graph[node_name]
657
# node has parents, assign from the left most parent.
658
parent_revno = self._revnos[parents[0]][0]
660
# not the first child, make a new branch
661
base_revno = parent_revno[0]
662
branch_count = self._revno_to_branch_count.get(base_revno, 0)
664
self._revno_to_branch_count[base_revno] = branch_count
665
revno = (parent_revno[0], branch_count, 1)
666
# revno = (parent_revno[0], branch_count, parent_revno[-1]+1)
668
# as the first child, we just increase the final revision
670
revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
672
# no parents, use the root sequence
673
root_count = self._revno_to_branch_count.get(0, 0)
675
revno = (0, root_count, 1)
679
self._revno_to_branch_count[0] = root_count
681
# store the revno for this node for future reference
682
self._revnos[node_name][0] = revno
683
463
self._completed_node_names.add(node_name)
684
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
