174
178
old revision listed in the mainline revisions
176
180
The order for this parameter is oldest-first.
178
The result is a list of node names, such that all parents come before
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.
181
185
node identifiers can be any hashable object, and are typically strings.
183
return MergeSorter(graph, branch_tip, mainline_revisions).sorted()
187
return MergeSorter(graph, branch_tip, mainline_revisions,
188
generate_revno).sorted()
186
191
class MergeSorter(object):
188
def __init__(self, graph, branch_tip, mainline_revisions=None):
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):
189
211
"""Merge-aware topological sorting of a graph.
191
213
:param graph: sequence of pairs of node_name->parent_names_list.
204
226
old revision listed in the mainline revisions
206
228
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.
209
254
node identifiers can be any hashable object, and are typically strings.
315
367
# which requires the parents to be accessible: its easier for now
316
368
# to just keep the original graph around.
317
369
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 = {}
319
382
# this is a stack storing the depth first search into the graph.
320
383
self._node_name_stack = []
363
431
After finishing iteration the sorter is empty and you cannot continue
366
while self._node_name_stack:
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:
367
535
# loop until this call completes.
368
parents_to_visit = self._pending_parents_stack[-1]
536
parents_to_visit = pending_parents_stack[-1]
369
537
# if all parents are done, the revision is done
370
538
if not parents_to_visit:
371
539
# append the revision to the topo sorted scheduled list:
372
540
# all the nodes parents have been scheduled added, now
373
541
# we can add it to the output.
376
while self._pending_parents_stack[-1]:
377
if not self._left_subtree_done_stack[-1]:
544
while pending_parents_stack[-1]:
545
if not left_subtree_pushed_stack[-1]:
378
546
# recurse depth first into the primary parent
379
next_node_name = self._pending_parents_stack[-1].pop(0)
547
next_node_name = pending_parents_stack[-1].pop(0)
381
549
# place any merges in right-to-left order for scheduling
382
550
# which gives us left-to-right order after we reverse
385
553
# subtree rather than the left most, which will
386
554
# display nicely (you get smaller trees at the top
387
555
# of the combined merge).
388
next_node_name = self._pending_parents_stack[-1].pop()
389
if next_node_name in self._completed_node_names:
556
next_node_name = pending_parents_stack[-1].pop()
557
if next_node_name in completed_node_names:
390
558
# this parent was completed by a child on the
391
559
# call stack. skip it.
393
561
# otherwise transfer it from the source graph into the
394
562
# top of the current depth first search stack.
396
parents = self._graph.pop(next_node_name)
564
parents = graph_pop(next_node_name)
398
566
# if the next node is not in the source graph it has
399
567
# already been popped from it and placed into the
400
568
# current search stack (but not completed or we would
401
569
# have hit the continue 4 lines up.
402
570
# this indicates a cycle.
403
raise errors.GraphCycleError(self._node_name_stack)
571
raise errors.GraphCycleError(node_name_stack)
404
572
next_merge_depth = 0
405
if self._left_subtree_done_stack[-1]:
573
if left_subtree_pushed_stack[-1]:
574
# a new child branch from name_stack[-1]
406
575
next_merge_depth = 1
408
577
next_merge_depth = 0
409
self._left_subtree_done_stack[-1] = True
578
left_subtree_pushed_stack[-1] = True
410
579
next_merge_depth = (
411
self._node_merge_depth_stack[-1] + next_merge_depth)
580
node_merge_depth_stack[-1] + next_merge_depth)
414
583
next_merge_depth,
416
585
# and do not continue processing parents until this 'call'
419
589
# We have scheduled the graph. Now deliver the ordered output:
420
590
sequence_number = 0
421
while self._scheduled_nodes:
422
node_name, merge_depth = self._scheduled_nodes.pop()
423
if node_name == self._stop_revision:
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:
425
if not len(self._scheduled_nodes):
599
if not len(scheduled_nodes):
600
# last revision is the end of a merge
426
601
end_of_merge = True
427
elif self._scheduled_nodes[-1][1] < merge_depth:
602
elif scheduled_nodes[-1][1] < merge_depth:
428
603
# the next node is to our left
429
604
end_of_merge = True
430
elif (self._scheduled_nodes[-1][1] == merge_depth and
431
(self._scheduled_nodes[-1][0] not in
432
self._original_graph[node_name])):
605
elif (scheduled_nodes[-1][1] == merge_depth and
606
(scheduled_nodes[-1][0] not in
607
original_graph[node_name])):
433
608
# the next node was part of a multiple-merge.
434
609
end_of_merge = True
436
611
end_of_merge = False
437
yield (sequence_number, node_name, merge_depth, end_of_merge)
613
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
615
yield (sequence_number, node_name, merge_depth, end_of_merge)
438
616
sequence_number += 1
440
618
def _push_node(self, node_name, merge_depth, parents):
457
647
# pop off the local variables
458
648
node_name = self._node_name_stack.pop()
459
649
merge_depth = self._node_merge_depth_stack.pop()
460
self._left_subtree_done_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()
461
653
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
463
683
self._completed_node_names.add(node_name)
464
self._scheduled_nodes.append((node_name, merge_depth))
684
self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
added
removed
bzrlib/tsort.py
