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