363
343
self._original_graph = dict(self._graph.items())
364
344
# we need to know the revision numbers of revisions to determine
365
345
# the revision numbers of their descendants
366
# this is a graph from node to [revno_tuple, first_child]
367
# where first_child is True if no other children have seen this node
346
# this is a graph from node to [revno_tuple, sequence_number]
347
# where sequence is the number of branches made from the node,
368
348
# and revno_tuple is the tuple that was assigned to the node.
369
349
# we dont know revnos to start with, so we start it seeded with
371
self._revnos = dict((revision, [None, True])
372
for revision in self._graph)
373
# Each mainline revision counts how many child branches have spawned from it.
374
self._revno_to_branch_count = {}
351
self._revnos = dict((revision, [None, 0]) for revision in self._graph)
352
# the global implicit root node has revno 0, but we need to know
353
# the sequence number for it too:
354
self._root_sequence = 0
376
356
# this is a stack storing the depth first search into the graph.
377
357
self._node_name_stack = []
425
404
After finishing iteration the sorter is empty and you cannot continue
428
# These are safe to offload to local variables, because they are used
429
# as a stack and modified in place, never assigned to.
430
node_name_stack = self._node_name_stack
431
node_merge_depth_stack = self._node_merge_depth_stack
432
pending_parents_stack = self._pending_parents_stack
433
left_subtree_pushed_stack = self._left_subtree_pushed_stack
434
completed_node_names = self._completed_node_names
435
scheduled_nodes = self._scheduled_nodes
437
graph_pop = self._graph.pop
439
def push_node(node_name, merge_depth, parents,
440
node_name_stack_append=node_name_stack.append,
441
node_merge_depth_stack_append=node_merge_depth_stack.append,
442
left_subtree_pushed_stack_append=left_subtree_pushed_stack.append,
443
pending_parents_stack_append=pending_parents_stack.append,
444
first_child_stack_append=self._first_child_stack.append,
447
"""Add node_name to the pending node stack.
449
Names in this stack will get emitted into the output as they are popped
452
This inlines a lot of self._variable.append functions as local
455
node_name_stack_append(node_name)
456
node_merge_depth_stack_append(merge_depth)
457
left_subtree_pushed_stack_append(False)
458
pending_parents_stack_append(list(parents))
459
# as we push it, check if it is the first child
461
# node has parents, assign from the left most parent.
462
parent_info = revnos[parents[0]]
463
first_child = parent_info[1]
464
parent_info[1] = False
466
# We don't use the same algorithm here, but we need to keep the
469
first_child_stack_append(first_child)
471
def pop_node(node_name_stack_pop=node_name_stack.pop,
472
node_merge_depth_stack_pop=node_merge_depth_stack.pop,
473
first_child_stack_pop=self._first_child_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,
480
revno_to_branch_count=self._revno_to_branch_count,
482
"""Pop the top node off the stack
484
The node is appended to the sorted output.
486
# we are returning from the flattened call frame:
487
# pop off the local variables
488
node_name = node_name_stack_pop()
489
merge_depth = node_merge_depth_stack_pop()
490
first_child = first_child_stack_pop()
491
# remove this node from the pending lists:
492
left_subtree_pushed_stack_pop()
493
pending_parents_stack_pop()
495
parents = original_graph[node_name]
497
# node has parents, assign from the left most parent.
498
parent_revno = revnos[parents[0]][0]
500
# not the first child, make a new branch
501
base_revno = parent_revno[0]
502
branch_count = revno_to_branch_count.get(base_revno, 0)
504
revno_to_branch_count[base_revno] = branch_count
505
revno = (parent_revno[0], branch_count, 1)
506
# revno = (parent_revno[0], branch_count, parent_revno[-1]+1)
508
# as the first child, we just increase the final revision
510
revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
512
# no parents, use the root sequence
513
root_count = revno_to_branch_count.get(0, 0)
515
revno = (0, root_count, 1)
519
revno_to_branch_count[0] = root_count
521
# store the revno for this node for future reference
522
revnos[node_name][0] = revno
523
completed_node_names_add(node_name)
524
scheduled_nodes_append((node_name, merge_depth, revno))
528
while node_name_stack:
407
while self._node_name_stack:
529
408
# loop until this call completes.
530
parents_to_visit = pending_parents_stack[-1]
409
parents_to_visit = self._pending_parents_stack[-1]
531
410
# if all parents are done, the revision is done
532
411
if not parents_to_visit:
533
412
# append the revision to the topo sorted scheduled list:
534
413
# all the nodes parents have been scheduled added, now
535
414
# we can add it to the output.
538
while pending_parents_stack[-1]:
539
if not left_subtree_pushed_stack[-1]:
417
while self._pending_parents_stack[-1]:
418
if not self._left_subtree_pushed_stack[-1]:
540
419
# recurse depth first into the primary parent
541
next_node_name = pending_parents_stack[-1].pop(0)
420
next_node_name = self._pending_parents_stack[-1].pop(0)
543
422
# place any merges in right-to-left order for scheduling
544
423
# which gives us left-to-right order after we reverse
547
426
# subtree rather than the left most, which will
548
427
# display nicely (you get smaller trees at the top
549
428
# of the combined merge).
550
next_node_name = pending_parents_stack[-1].pop()
551
if next_node_name in completed_node_names:
429
next_node_name = self._pending_parents_stack[-1].pop()
430
if next_node_name in self._completed_node_names:
552
431
# this parent was completed by a child on the
553
432
# call stack. skip it.
555
434
# otherwise transfer it from the source graph into the
556
435
# top of the current depth first search stack.
558
parents = graph_pop(next_node_name)
437
parents = self._graph.pop(next_node_name)
560
439
# if the next node is not in the source graph it has
561
440
# already been popped from it and placed into the
562
441
# current search stack (but not completed or we would
563
442
# have hit the continue 4 lines up.
564
443
# this indicates a cycle.
565
raise errors.GraphCycleError(node_name_stack)
444
raise errors.GraphCycleError(self._node_name_stack)
566
445
next_merge_depth = 0
567
if left_subtree_pushed_stack[-1]:
446
if self._left_subtree_pushed_stack[-1]:
568
447
# a new child branch from name_stack[-1]
569
448
next_merge_depth = 1
571
450
next_merge_depth = 0
572
left_subtree_pushed_stack[-1] = True
451
self._left_subtree_pushed_stack[-1] = True
573
452
next_merge_depth = (
574
node_merge_depth_stack[-1] + next_merge_depth)
453
self._node_merge_depth_stack[-1] + next_merge_depth)
577
456
next_merge_depth,
579
458
# and do not continue processing parents until this 'call'
583
461
# We have scheduled the graph. Now deliver the ordered output:
584
462
sequence_number = 0
585
stop_revision = self._stop_revision
586
generate_revno = self._generate_revno
587
original_graph = self._original_graph
589
while scheduled_nodes:
590
node_name, merge_depth, revno = scheduled_nodes.pop()
591
if node_name == stop_revision:
463
while self._scheduled_nodes:
464
node_name, merge_depth, revno = self._scheduled_nodes.pop()
465
if node_name == self._stop_revision:
593
if not len(scheduled_nodes):
467
if not len(self._scheduled_nodes):
594
468
# last revision is the end of a merge
595
469
end_of_merge = True
596
elif scheduled_nodes[-1][1] < merge_depth:
470
elif self._scheduled_nodes[-1][1] < merge_depth:
597
471
# the next node is to our left
598
472
end_of_merge = True
599
elif (scheduled_nodes[-1][1] == merge_depth and
600
(scheduled_nodes[-1][0] not in
601
original_graph[node_name])):
473
elif (self._scheduled_nodes[-1][1] == merge_depth and
474
(self._scheduled_nodes[-1][0] not in
475
self._original_graph[node_name])):
602
476
# the next node was part of a multiple-merge.
603
477
end_of_merge = True
605
479
end_of_merge = False
480
if self._generate_revno:
607
481
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
609
483
yield (sequence_number, node_name, merge_depth, end_of_merge)
619
493
self._node_merge_depth_stack.append(merge_depth)
620
494
self._left_subtree_pushed_stack.append(False)
621
495
self._pending_parents_stack.append(list(parents))
622
# as we push it, figure out if this is the first child
496
# as we push it, assign it a sequence number against its parent:
623
497
parents = self._original_graph[node_name]
625
499
# node has parents, assign from the left most parent.
626
parent_info = self._revnos[parents[0]]
627
first_child = parent_info[1]
628
parent_info[1] = False
500
parent_revno = self._revnos[parents[0]]
501
sequence = parent_revno[1]
630
# We don't use the same algorithm here, but we need to keep the
633
self._first_child_stack.append(first_child)
504
# no parents, use the root sequence
505
sequence = self._root_sequence
506
self._root_sequence +=1
507
self._assigned_sequence_stack.append(sequence)
635
509
def _pop_node(self):
636
510
"""Pop the top node off the stack
649
523
parents = self._original_graph[node_name]
651
525
# node has parents, assign from the left most parent.
652
parent_revno = self._revnos[parents[0]][0]
526
parent_revno = self._revnos[parents[0]]
654
528
# not the first child, make a new branch
655
base_revno = parent_revno[0]
656
branch_count = self._revno_to_branch_count.get(base_revno, 0)
658
self._revno_to_branch_count[base_revno] = branch_count
659
revno = (parent_revno[0], branch_count, 1)
660
# revno = (parent_revno[0], branch_count, parent_revno[-1]+1)
529
revno = parent_revno[0] + (sequence, 1)
662
# as the first child, we just increase the final revision
664
revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
531
# increment the sequence number within the branch
532
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
666
534
# no parents, use the root sequence
667
root_count = self._revno_to_branch_count.get(0, 0)
669
revno = (0, root_count, 1)
536
# make a parallel import revision number
537
revno = (0, sequence, 1)
673
self._revno_to_branch_count[0] = root_count
675
541
# store the revno for this node for future reference
676
542
self._revnos[node_name][0] = revno
added
removed
bzrlib/tsort.py
