177
174
old revision listed in the mainline revisions
179
176
The order for this parameter is oldest-first.
180
:param generate_revno: Optional parameter controlling the generation of
181
revision number sequences in the output. See the output description of
182
the MergeSorter docstring for details.
183
:result: See the MergeSorter docstring for details.
178
The result is a list of node names, such that all parents come before
184
181
node identifiers can be any hashable object, and are typically strings.
186
return MergeSorter(graph, branch_tip, mainline_revisions,
187
generate_revno).sorted()
183
return MergeSorter(graph, branch_tip, mainline_revisions).sorted()
190
186
class MergeSorter(object):
192
__slots__ = ['_node_name_stack',
193
'_node_merge_depth_stack',
194
'_pending_parents_stack',
195
'_assigned_sequence_stack',
196
'_left_subtree_pushed_stack',
199
'_mainline_revisions',
204
'_completed_node_names',
208
def __init__(self, graph, branch_tip, mainline_revisions=None,
209
generate_revno=False):
188
def __init__(self, graph, branch_tip, mainline_revisions=None):
210
189
"""Merge-aware topological sorting of a graph.
212
191
:param graph: sequence of pairs of node_name->parent_names_list.
225
204
old revision listed in the mainline revisions
227
206
The order for this parameter is oldest-first.
228
:param generate_revno: Optional parameter controlling the generation of
229
revision number sequences in the output. See the output description
232
The result is a list sorted so that all parents come before
233
their children. Each element of the list is a tuple containing:
234
(sequence_number, node_name, merge_depth, end_of_merge)
235
* sequence_number: The sequence of this row in the output. Useful for
237
* node_name: The node name: opaque text to the merge routine.
238
* merge_depth: How many levels of merging deep this node has been
240
* revno_sequence: When requested this field provides a sequence of
241
revision numbers for all revisions. The format is:
242
REVNO[[.BRANCHREVNO.REVNO] ...]. BRANCHREVNO is the number of the
243
branch that the revno is on. From left to right the REVNO numbers
244
are the sequence numbers within that branch of the revision.
245
For instance, the graph {A:[], B:['A'], C:['A', 'B']} will get
246
the following revno_sequences assigned: A:(1,), B:(1,1,1), C:(2,).
247
This should be read as 'A is the first commit in the trunk',
248
'B is the first commit on the first branch made from A', 'C is the
249
second commit in the trunk'.
250
* end_of_merge: When True the next node is part of a different merge.
253
209
node identifiers can be any hashable object, and are typically strings.
360
315
# which requires the parents to be accessible: its easier for now
361
316
# to just keep the original graph around.
362
317
self._original_graph = dict(self._graph.items())
363
# we need to know the revision numbers of revisions to determine
364
# the revision numbers of their descendants
365
# this is a graph from node to [revno_tuple, sequence_number]
366
# where sequence is the number of branches made from the node,
367
# and revno_tuple is the tuple that was assigned to the node.
368
# we dont know revnos to start with, so we start it seeded with
370
self._revnos = dict((revision, [None, 0]) for revision in self._graph)
371
# the global implicit root node has revno 0, but we need to know
372
# the sequence number for it too:
373
self._root_sequence = 0
375
319
# this is a stack storing the depth first search into the graph.
376
320
self._node_name_stack = []
423
363
After finishing iteration the sorter is empty and you cannot continue
426
# These are safe to offload to local variables, because they are used
427
# as a stack and modified in place, never assigned to.
428
node_name_stack = self._node_name_stack
429
node_merge_depth_stack = self._node_merge_depth_stack
430
pending_parents_stack = self._pending_parents_stack
431
left_subtree_pushed_stack = self._left_subtree_pushed_stack
432
completed_node_names = self._completed_node_names
433
scheduled_nodes = self._scheduled_nodes
435
graph_pop = self._graph.pop
437
def push_node(node_name, merge_depth, parents,
438
node_name_stack_append=node_name_stack.append,
439
node_merge_depth_stack_append=node_merge_depth_stack.append,
440
left_subtree_pushed_stack_append=left_subtree_pushed_stack.append,
441
pending_parents_stack_append=pending_parents_stack.append,
442
assigned_sequence_stack_append=self._assigned_sequence_stack.append,
443
original_graph=self._original_graph,
446
"""Add node_name to the pending node stack.
448
Names in this stack will get emitted into the output as they are popped
451
This inlines a lot of self._variable.append functions as local
454
node_name_stack_append(node_name)
455
node_merge_depth_stack_append(merge_depth)
456
left_subtree_pushed_stack_append(False)
457
pending_parents_stack_append(list(parents))
458
# as we push it, assign it a sequence number against its parent:
459
parents = original_graph[node_name]
461
# node has parents, assign from the left most parent.
462
parent_revno = revnos[parents[0]]
463
sequence = parent_revno[1]
466
# no parents, use the root sequence
467
sequence = self._root_sequence
468
self._root_sequence +=1
469
assigned_sequence_stack_append(sequence)
471
def pop_node(node_name_stack_pop=node_name_stack.pop,
472
node_merge_depth_stack_pop=node_merge_depth_stack.pop,
473
assigned_sequence_stack_pop=self._assigned_sequence_stack.pop,
474
left_subtree_pushed_stack_pop=left_subtree_pushed_stack.pop,
475
pending_parents_stack_pop=pending_parents_stack.pop,
476
original_graph=self._original_graph,
478
completed_node_names_add=self._completed_node_names.add,
479
scheduled_nodes_append=scheduled_nodes.append,
481
"""Pop the top node off the stack
483
The node is appended to the sorted output.
485
# we are returning from the flattened call frame:
486
# pop off the local variables
487
node_name = node_name_stack_pop()
488
merge_depth = node_merge_depth_stack_pop()
489
sequence = assigned_sequence_stack_pop()
490
# remove this node from the pending lists:
491
left_subtree_pushed_stack_pop()
492
pending_parents_stack_pop()
494
parents = original_graph[node_name]
496
# node has parents, assign from the left most parent.
497
parent_revno = revnos[parents[0]]
499
# not the first child, make a new branch
500
revno = parent_revno[0] + (sequence, 1)
502
# increment the sequence number within the branch
503
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
505
# no parents, use the root sequence
507
# make a parallel import revision number
508
revno = (0, sequence, 1)
512
# store the revno for this node for future reference
513
revnos[node_name][0] = revno
514
completed_node_names_add(node_name)
515
scheduled_nodes_append((node_name, merge_depth, revno))
519
while node_name_stack:
366
while self._node_name_stack:
520
367
# loop until this call completes.
521
parents_to_visit = pending_parents_stack[-1]
368
parents_to_visit = self._pending_parents_stack[-1]
522
369
# if all parents are done, the revision is done
523
370
if not parents_to_visit:
524
371
# append the revision to the topo sorted scheduled list:
525
372
# all the nodes parents have been scheduled added, now
526
373
# we can add it to the output.
529
while pending_parents_stack[-1]:
530
if not left_subtree_pushed_stack[-1]:
376
while self._pending_parents_stack[-1]:
377
if not self._left_subtree_done_stack[-1]:
531
378
# recurse depth first into the primary parent
532
next_node_name = pending_parents_stack[-1].pop(0)
379
next_node_name = self._pending_parents_stack[-1].pop(0)
534
381
# place any merges in right-to-left order for scheduling
535
382
# which gives us left-to-right order after we reverse
538
385
# subtree rather than the left most, which will
539
386
# display nicely (you get smaller trees at the top
540
387
# of the combined merge).
541
next_node_name = pending_parents_stack[-1].pop()
542
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:
543
390
# this parent was completed by a child on the
544
391
# call stack. skip it.
546
393
# otherwise transfer it from the source graph into the
547
394
# top of the current depth first search stack.
549
parents = graph_pop(next_node_name)
396
parents = self._graph.pop(next_node_name)
551
398
# if the next node is not in the source graph it has
552
399
# already been popped from it and placed into the
553
400
# current search stack (but not completed or we would
554
401
# have hit the continue 4 lines up.
555
402
# this indicates a cycle.
556
raise errors.GraphCycleError(node_name_stack)
403
raise errors.GraphCycleError(self._node_name_stack)
557
404
next_merge_depth = 0
558
if left_subtree_pushed_stack[-1]:
559
# a new child branch from name_stack[-1]
405
if self._left_subtree_done_stack[-1]:
560
406
next_merge_depth = 1
562
408
next_merge_depth = 0
563
left_subtree_pushed_stack[-1] = True
409
self._left_subtree_done_stack[-1] = True
564
410
next_merge_depth = (
565
node_merge_depth_stack[-1] + next_merge_depth)
411
self._node_merge_depth_stack[-1] + next_merge_depth)
568
414
next_merge_depth,
570
416
# and do not continue processing parents until this 'call'
574
419
# We have scheduled the graph. Now deliver the ordered output:
575
420
sequence_number = 0
576
stop_revision = self._stop_revision
577
generate_revno = self._generate_revno
578
original_graph = self._original_graph
580
while scheduled_nodes:
581
node_name, merge_depth, revno = scheduled_nodes.pop()
582
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:
584
if not len(scheduled_nodes):
585
# last revision is the end of a merge
425
if not len(self._scheduled_nodes):
586
426
end_of_merge = True
587
elif scheduled_nodes[-1][1] < merge_depth:
427
elif self._scheduled_nodes[-1][1] < merge_depth:
588
428
# the next node is to our left
589
429
end_of_merge = True
590
elif (scheduled_nodes[-1][1] == merge_depth and
591
(scheduled_nodes[-1][0] not in
592
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])):
593
433
# the next node was part of a multiple-merge.
594
434
end_of_merge = True
596
436
end_of_merge = False
598
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
600
yield (sequence_number, node_name, merge_depth, end_of_merge)
437
yield (sequence_number, node_name, merge_depth, end_of_merge)
601
438
sequence_number += 1
603
440
def _push_node(self, node_name, merge_depth, parents):
632
457
# pop off the local variables
633
458
node_name = self._node_name_stack.pop()
634
459
merge_depth = self._node_merge_depth_stack.pop()
635
sequence = self._assigned_sequence_stack.pop()
636
# remove this node from the pending lists:
637
self._left_subtree_pushed_stack.pop()
460
self._left_subtree_done_stack.pop()
638
461
self._pending_parents_stack.pop()
640
parents = self._original_graph[node_name]
642
# node has parents, assign from the left most parent.
643
parent_revno = self._revnos[parents[0]]
645
# not the first child, make a new branch
646
revno = parent_revno[0] + (sequence, 1)
648
# increment the sequence number within the branch
649
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
651
# no parents, use the root sequence
653
# make a parallel import revision number
654
revno = (0, sequence, 1)
658
# store the revno for this node for future reference
659
self._revnos[node_name][0] = revno
660
463
self._completed_node_names.add(node_name)
661
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
