404
420
After finishing iteration the sorter is empty and you cannot continue
407
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:
408
517
# loop until this call completes.
409
parents_to_visit = self._pending_parents_stack[-1]
518
parents_to_visit = pending_parents_stack[-1]
410
519
# if all parents are done, the revision is done
411
520
if not parents_to_visit:
412
521
# append the revision to the topo sorted scheduled list:
413
522
# all the nodes parents have been scheduled added, now
414
523
# we can add it to the output.
417
while self._pending_parents_stack[-1]:
418
if not self._left_subtree_pushed_stack[-1]:
526
while pending_parents_stack[-1]:
527
if not left_subtree_pushed_stack[-1]:
419
528
# recurse depth first into the primary parent
420
next_node_name = self._pending_parents_stack[-1].pop(0)
529
next_node_name = pending_parents_stack[-1].pop(0)
422
531
# place any merges in right-to-left order for scheduling
423
532
# which gives us left-to-right order after we reverse
426
535
# subtree rather than the left most, which will
427
536
# display nicely (you get smaller trees at the top
428
537
# of the combined merge).
429
next_node_name = self._pending_parents_stack[-1].pop()
430
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:
431
540
# this parent was completed by a child on the
432
541
# call stack. skip it.
434
543
# otherwise transfer it from the source graph into the
435
544
# top of the current depth first search stack.
437
parents = self._graph.pop(next_node_name)
546
parents = graph_pop(next_node_name)
439
548
# if the next node is not in the source graph it has
440
549
# already been popped from it and placed into the
441
550
# current search stack (but not completed or we would
442
551
# have hit the continue 4 lines up.
443
552
# this indicates a cycle.
444
raise errors.GraphCycleError(self._node_name_stack)
553
raise errors.GraphCycleError(node_name_stack)
445
554
next_merge_depth = 0
446
if self._left_subtree_pushed_stack[-1]:
555
if left_subtree_pushed_stack[-1]:
447
556
# a new child branch from name_stack[-1]
448
557
next_merge_depth = 1
450
559
next_merge_depth = 0
451
self._left_subtree_pushed_stack[-1] = True
560
left_subtree_pushed_stack[-1] = True
452
561
next_merge_depth = (
453
self._node_merge_depth_stack[-1] + next_merge_depth)
562
node_merge_depth_stack[-1] + next_merge_depth)
456
565
next_merge_depth,
458
567
# and do not continue processing parents until this 'call'
461
571
# We have scheduled the graph. Now deliver the ordered output:
462
572
sequence_number = 0
463
while self._scheduled_nodes:
464
node_name, merge_depth, revno = self._scheduled_nodes.pop()
465
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:
467
if not len(self._scheduled_nodes):
581
if not len(scheduled_nodes):
468
582
# last revision is the end of a merge
469
583
end_of_merge = True
470
elif self._scheduled_nodes[-1][1] < merge_depth:
584
elif scheduled_nodes[-1][1] < merge_depth:
471
585
# the next node is to our left
472
586
end_of_merge = True
473
elif (self._scheduled_nodes[-1][1] == merge_depth and
474
(self._scheduled_nodes[-1][0] not in
475
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])):
476
590
# the next node was part of a multiple-merge.
477
591
end_of_merge = True
479
593
end_of_merge = False
480
if self._generate_revno:
481
595
yield (sequence_number, node_name, merge_depth, revno, end_of_merge)
483
597
yield (sequence_number, node_name, merge_depth, end_of_merge)
added
removed
bzrlib/tsort.py
