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
__slots__ = ['_node_name_stack',
190
'_node_merge_depth_stack',
191
'_pending_parents_stack',
192
'_assigned_sequence_stack',
193
'_left_subtree_pushed_stack',
196
'_mainline_revisions',
201
'_completed_node_names',
205
def __init__(self, graph, branch_tip, mainline_revisions=None,
206
generate_revno=False):
189
207
"""Merge-aware topological sorting of a graph.
191
209
:param graph: sequence of pairs of node_name->parent_names_list.
204
222
old revision listed in the mainline revisions
206
224
The order for this parameter is oldest-first.
225
:param generate_revno: Optional parameter controlling the generation of
226
revision number sequences in the output. See the output description
229
The result is a list sorted so that all parents come before
230
their children. Each element of the list is a tuple containing:
231
(sequence_number, node_name, merge_depth, end_of_merge)
232
* sequence_number: The sequence of this row in the output. Useful for
234
* node_name: The node name: opaque text to the merge routine.
235
* merge_depth: How many levels of merging deep this node has been
237
* revno_sequence: When requested this field provides a sequence of
238
revision numbers for all revisions. The format is:
239
REVNO[[.BRANCHREVNO.REVNO] ...]. BRANCHREVNO is the number of the
240
branch that the revno is on. From left to right the REVNO numbers
241
are the sequence numbers within that branch of the revision.
242
For instance, the graph {A:[], B:['A'], C:['A', 'B']} will get
243
the following revno_sequences assigned: A:(1,), B:(1,1,1), C:(2,).
244
This should be read as 'A is the first commit in the trunk',
245
'B is the first commit on the first branch made from A', 'C is the
246
second commit in the trunk'.
247
* end_of_merge: When True the next node is part of a different merge.
209
250
node identifiers can be any hashable object, and are typically strings.
315
357
# which requires the parents to be accessible: its easier for now
316
358
# to just keep the original graph around.
317
359
self._original_graph = dict(self._graph.items())
360
# we need to know the revision numbers of revisions to determine
361
# the revision numbers of their descendants
362
# this is a graph from node to [revno_tuple, sequence_number]
363
# where sequence is the number of branches made from the node,
364
# and revno_tuple is the tuple that was assigned to the node.
365
# we dont know revnos to start with, so we start it seeded with
367
self._revnos = dict((revision, [None, 0]) for revision in self._graph)
368
# the global implicit root node has revno 0, but we need to know
369
# the sequence number for it too:
370
self._root_sequence = 0
319
372
# this is a stack storing the depth first search into the graph.
320
373
self._node_name_stack = []
363
420
After finishing iteration the sorter is empty and you cannot continue
366
while self._node_name_stack:
423
# These are safe to offload to local variables, because they are used
424
# as a stack and modified in place, never assigned to.
425
node_name_stack = self._node_name_stack
426
node_merge_depth_stack = self._node_merge_depth_stack
427
pending_parents_stack = self._pending_parents_stack
428
left_subtree_pushed_stack = self._left_subtree_pushed_stack
429
completed_node_names = self._completed_node_names
430
scheduled_nodes = self._scheduled_nodes
432
graph_pop = self._graph.pop
434
def push_node(node_name, merge_depth, parents,
435
node_name_stack_append=node_name_stack.append,
436
node_merge_depth_stack_append=node_merge_depth_stack.append,
437
left_subtree_pushed_stack_append=left_subtree_pushed_stack.append,
438
pending_parents_stack_append=pending_parents_stack.append,
439
assigned_sequence_stack_append=self._assigned_sequence_stack.append,
440
original_graph=self._original_graph,
443
"""Add node_name to the pending node stack.
445
Names in this stack will get emitted into the output as they are popped
448
This inlines a lot of self._variable.append functions as local
451
node_name_stack_append(node_name)
452
node_merge_depth_stack_append(merge_depth)
453
left_subtree_pushed_stack_append(False)
454
pending_parents_stack_append(list(parents))
455
# as we push it, assign it a sequence number against its parent:
456
parents = original_graph[node_name]
458
# node has parents, assign from the left most parent.
459
parent_revno = revnos[parents[0]]
460
sequence = parent_revno[1]
463
# no parents, use the root sequence
464
sequence = self._root_sequence
465
self._root_sequence +=1
466
assigned_sequence_stack_append(sequence)
468
def pop_node(node_name_stack_pop=node_name_stack.pop,
469
node_merge_depth_stack_pop=node_merge_depth_stack.pop,
470
assigned_sequence_stack_pop=self._assigned_sequence_stack.pop,
471
left_subtree_pushed_stack_pop=left_subtree_pushed_stack.pop,
472
pending_parents_stack_pop=pending_parents_stack.pop,
473
original_graph=self._original_graph,
475
completed_node_names_add=self._completed_node_names.add,
476
scheduled_nodes_append=scheduled_nodes.append,
478
"""Pop the top node off the stack
480
The node is appended to the sorted output.
482
# we are returning from the flattened call frame:
483
# pop off the local variables
484
node_name = node_name_stack_pop()
485
merge_depth = node_merge_depth_stack_pop()
486
sequence = assigned_sequence_stack_pop()
487
# remove this node from the pending lists:
488
left_subtree_pushed_stack_pop()
489
pending_parents_stack_pop()
491
parents = original_graph[node_name]
493
# node has parents, assign from the left most parent.
494
parent_revno = revnos[parents[0]]
496
# not the first child, make a new branch
497
revno = parent_revno[0] + (sequence, 1)
499
# increment the sequence number within the branch
500
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
502
# no parents, use the root sequence
504
# make a parallel import revision number
505
revno = (0, sequence, 1)
509
# store the revno for this node for future reference
510
revnos[node_name][0] = revno
511
completed_node_names_add(node_name)
512
scheduled_nodes_append((node_name, merge_depth, revno))
516
while node_name_stack:
367
517
# loop until this call completes.
368
parents_to_visit = self._pending_parents_stack[-1]
518
parents_to_visit = pending_parents_stack[-1]
369
519
# if all parents are done, the revision is done
370
520
if not parents_to_visit:
371
521
# append the revision to the topo sorted scheduled list:
372
522
# all the nodes parents have been scheduled added, now
373
523
# we can add it to the output.
376
while self._pending_parents_stack[-1]:
377
if not self._left_subtree_done_stack[-1]:
526
while pending_parents_stack[-1]:
527
if not left_subtree_pushed_stack[-1]:
378
528
# recurse depth first into the primary parent
379
next_node_name = self._pending_parents_stack[-1].pop(0)
529
next_node_name = pending_parents_stack[-1].pop(0)
381
531
# place any merges in right-to-left order for scheduling
382
532
# which gives us left-to-right order after we reverse
385
535
# subtree rather than the left most, which will
386
536
# display nicely (you get smaller trees at the top
387
537
# of the combined merge).
388
next_node_name = self._pending_parents_stack[-1].pop()
389
if next_node_name in self._completed_node_names:
538
next_node_name = pending_parents_stack[-1].pop()
539
if next_node_name in completed_node_names:
390
540
# this parent was completed by a child on the
391
541
# call stack. skip it.
393
543
# otherwise transfer it from the source graph into the
394
544
# top of the current depth first search stack.
396
parents = self._graph.pop(next_node_name)
546
parents = graph_pop(next_node_name)
398
548
# if the next node is not in the source graph it has
399
549
# already been popped from it and placed into the
400
550
# current search stack (but not completed or we would
401
551
# have hit the continue 4 lines up.
402
552
# this indicates a cycle.
403
raise errors.GraphCycleError(self._node_name_stack)
553
raise errors.GraphCycleError(node_name_stack)
404
554
next_merge_depth = 0
405
if self._left_subtree_done_stack[-1]:
555
if left_subtree_pushed_stack[-1]:
556
# a new child branch from name_stack[-1]
406
557
next_merge_depth = 1
408
559
next_merge_depth = 0
409
self._left_subtree_done_stack[-1] = True
560
left_subtree_pushed_stack[-1] = True
410
561
next_merge_depth = (
411
self._node_merge_depth_stack[-1] + next_merge_depth)
562
node_merge_depth_stack[-1] + next_merge_depth)
414
565
next_merge_depth,
416
567
# and do not continue processing parents until this 'call'
419
571
# We have scheduled the graph. Now deliver the ordered output:
420
572
sequence_number = 0
421
while self._scheduled_nodes:
422
node_name, merge_depth = self._scheduled_nodes.pop()
423
if node_name == self._stop_revision:
573
stop_revision = self._stop_revision
574
generate_revno = self._generate_revno
575
original_graph = self._original_graph
577
while scheduled_nodes:
578
node_name, merge_depth, revno = scheduled_nodes.pop()
579
if node_name == stop_revision:
425
if not len(self._scheduled_nodes):
581
if not len(scheduled_nodes):
582
# last revision is the end of a merge
426
583
end_of_merge = True
427
elif self._scheduled_nodes[-1][1] < merge_depth:
584
elif scheduled_nodes[-1][1] < merge_depth:
428
585
# the next node is to our left
429
586
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])):
587
elif (scheduled_nodes[-1][1] == merge_depth and
588
(scheduled_nodes[-1][0] not in
589
original_graph[node_name])):
433
590
# the next node was part of a multiple-merge.
434
591
end_of_merge = True
436
593
end_of_merge = False
437
yield (sequence_number, node_name, merge_depth, end_of_merge)
595
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
597
yield (sequence_number, node_name, merge_depth, end_of_merge)
438
598
sequence_number += 1
440
600
def _push_node(self, node_name, merge_depth, parents):
457
629
# pop off the local variables
458
630
node_name = self._node_name_stack.pop()
459
631
merge_depth = self._node_merge_depth_stack.pop()
460
self._left_subtree_done_stack.pop()
632
sequence = self._assigned_sequence_stack.pop()
633
# remove this node from the pending lists:
634
self._left_subtree_pushed_stack.pop()
461
635
self._pending_parents_stack.pop()
637
parents = self._original_graph[node_name]
639
# node has parents, assign from the left most parent.
640
parent_revno = self._revnos[parents[0]]
642
# not the first child, make a new branch
643
revno = parent_revno[0] + (sequence, 1)
645
# increment the sequence number within the branch
646
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
648
# no parents, use the root sequence
650
# make a parallel import revision number
651
revno = (0, sequence, 1)
655
# store the revno for this node for future reference
656
self._revnos[node_name][0] = revno
463
657
self._completed_node_names.add(node_name)
464
self._scheduled_nodes.append((node_name, merge_depth))
658
self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
added
removed
bzrlib/tsort.py
