174
177
old revision listed in the mainline revisions
176
179
The order for this parameter is oldest-first.
178
The result is a list of node names, such that all parents come before
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.
181
184
node identifiers can be any hashable object, and are typically strings.
183
return MergeSorter(graph, branch_tip, mainline_revisions).sorted()
186
return MergeSorter(graph, branch_tip, mainline_revisions,
187
generate_revno).sorted()
186
190
class MergeSorter(object):
188
def __init__(self, graph, branch_tip, mainline_revisions=None):
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):
189
210
"""Merge-aware topological sorting of a graph.
191
212
:param graph: sequence of pairs of node_name->parent_names_list.
204
225
old revision listed in the mainline revisions
206
227
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.
209
253
node identifiers can be any hashable object, and are typically strings.
315
360
# which requires the parents to be accessible: its easier for now
316
361
# to just keep the original graph around.
317
362
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
319
375
# this is a stack storing the depth first search into the graph.
320
376
self._node_name_stack = []
363
423
After finishing iteration the sorter is empty and you cannot continue
366
while self._node_name_stack:
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:
367
520
# loop until this call completes.
368
parents_to_visit = self._pending_parents_stack[-1]
521
parents_to_visit = pending_parents_stack[-1]
369
522
# if all parents are done, the revision is done
370
523
if not parents_to_visit:
371
524
# append the revision to the topo sorted scheduled list:
372
525
# all the nodes parents have been scheduled added, now
373
526
# we can add it to the output.
376
while self._pending_parents_stack[-1]:
377
if not self._left_subtree_done_stack[-1]:
529
while pending_parents_stack[-1]:
530
if not left_subtree_pushed_stack[-1]:
378
531
# recurse depth first into the primary parent
379
next_node_name = self._pending_parents_stack[-1].pop(0)
532
next_node_name = pending_parents_stack[-1].pop(0)
381
534
# place any merges in right-to-left order for scheduling
382
535
# which gives us left-to-right order after we reverse
385
538
# subtree rather than the left most, which will
386
539
# display nicely (you get smaller trees at the top
387
540
# of the combined merge).
388
next_node_name = self._pending_parents_stack[-1].pop()
389
if next_node_name in self._completed_node_names:
541
next_node_name = pending_parents_stack[-1].pop()
542
if next_node_name in completed_node_names:
390
543
# this parent was completed by a child on the
391
544
# call stack. skip it.
393
546
# otherwise transfer it from the source graph into the
394
547
# top of the current depth first search stack.
396
parents = self._graph.pop(next_node_name)
549
parents = graph_pop(next_node_name)
398
551
# if the next node is not in the source graph it has
399
552
# already been popped from it and placed into the
400
553
# current search stack (but not completed or we would
401
554
# have hit the continue 4 lines up.
402
555
# this indicates a cycle.
403
raise errors.GraphCycleError(self._node_name_stack)
556
raise errors.GraphCycleError(node_name_stack)
404
557
next_merge_depth = 0
405
if self._left_subtree_done_stack[-1]:
558
if left_subtree_pushed_stack[-1]:
559
# a new child branch from name_stack[-1]
406
560
next_merge_depth = 1
408
562
next_merge_depth = 0
409
self._left_subtree_done_stack[-1] = True
563
left_subtree_pushed_stack[-1] = True
410
564
next_merge_depth = (
411
self._node_merge_depth_stack[-1] + next_merge_depth)
565
node_merge_depth_stack[-1] + next_merge_depth)
414
568
next_merge_depth,
416
570
# and do not continue processing parents until this 'call'
419
574
# We have scheduled the graph. Now deliver the ordered output:
420
575
sequence_number = 0
421
while self._scheduled_nodes:
422
node_name, merge_depth = self._scheduled_nodes.pop()
423
if node_name == self._stop_revision:
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:
425
if not len(self._scheduled_nodes):
584
if not len(scheduled_nodes):
585
# last revision is the end of a merge
426
586
end_of_merge = True
427
elif self._scheduled_nodes[-1][1] < merge_depth:
587
elif scheduled_nodes[-1][1] < merge_depth:
428
588
# the next node is to our left
429
589
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])):
590
elif (scheduled_nodes[-1][1] == merge_depth and
591
(scheduled_nodes[-1][0] not in
592
original_graph[node_name])):
433
593
# the next node was part of a multiple-merge.
434
594
end_of_merge = True
436
596
end_of_merge = False
437
yield (sequence_number, node_name, merge_depth, end_of_merge)
598
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
600
yield (sequence_number, node_name, merge_depth, end_of_merge)
438
601
sequence_number += 1
440
603
def _push_node(self, node_name, merge_depth, parents):
457
632
# pop off the local variables
458
633
node_name = self._node_name_stack.pop()
459
634
merge_depth = self._node_merge_depth_stack.pop()
460
self._left_subtree_done_stack.pop()
635
sequence = self._assigned_sequence_stack.pop()
636
# remove this node from the pending lists:
637
self._left_subtree_pushed_stack.pop()
461
638
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
463
660
self._completed_node_names.add(node_name)
464
self._scheduled_nodes.append((node_name, merge_depth))
661
self._scheduled_nodes.append((node_name, merge_depth, self._revnos[node_name][0]))
added
removed
bzrlib/tsort.py
