192
192
__slots__ = ['_node_name_stack',
193
193
'_node_merge_depth_stack',
194
194
'_pending_parents_stack',
195
'_first_child_stack',
195
'_assigned_sequence_stack',
196
196
'_left_subtree_pushed_stack',
197
197
'_generate_revno',
240
240
* revno_sequence: When requested this field provides a sequence of
241
241
revision numbers for all revisions. The format is:
242
(REVNO, BRANCHNUM, BRANCHREVNO). BRANCHNUM is the number of the
242
REVNO[[.BRANCHREVNO.REVNO] ...]. BRANCHREVNO is the number of the
243
243
branch that the revno is on. From left to right the REVNO numbers
244
244
are the sequence numbers within that branch of the revision.
245
245
For instance, the graph {A:[], B:['A'], C:['A', 'B']} will get
362
362
self._original_graph = dict(self._graph.items())
363
363
# we need to know the revision numbers of revisions to determine
364
364
# the revision numbers of their descendants
365
# this is a graph from node to [revno_tuple, first_child]
366
# where first_child is True if no other children have seen this node
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
367
# and revno_tuple is the tuple that was assigned to the node.
368
368
# we dont know revnos to start with, so we start it seeded with
370
self._revnos = dict((revision, [None, True])
371
for revision in self._graph)
372
# Each mainline revision counts how many child branches have spawned from it.
373
self._revno_to_branch_count = {}
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
375
# this is a stack storing the depth first search into the graph.
376
376
self._node_name_stack = []
382
382
self._pending_parents_stack = []
383
383
# When we first look at a node we assign it a seqence number from its
384
384
# leftmost parent.
385
self._first_child_stack = []
385
self._assigned_sequence_stack = []
386
386
# this is a set of the nodes who have been completely analysed for fast
387
387
# membership checking
388
388
self._completed_node_names = set()
439
439
node_merge_depth_stack_append=node_merge_depth_stack.append,
440
440
left_subtree_pushed_stack_append=left_subtree_pushed_stack.append,
441
441
pending_parents_stack_append=pending_parents_stack.append,
442
first_child_stack_append=self._first_child_stack.append,
442
assigned_sequence_stack_append=self._assigned_sequence_stack.append,
443
original_graph=self._original_graph,
443
444
revnos=self._revnos,
445
446
"""Add node_name to the pending node stack.
454
455
node_merge_depth_stack_append(merge_depth)
455
456
left_subtree_pushed_stack_append(False)
456
457
pending_parents_stack_append(list(parents))
457
# as we push it, check if it is the first child
458
# as we push it, assign it a sequence number against its parent:
459
parents = original_graph[node_name]
459
461
# node has parents, assign from the left most parent.
460
parent_info = revnos[parents[0]]
461
first_child = parent_info[1]
462
parent_info[1] = False
462
parent_revno = revnos[parents[0]]
463
sequence = parent_revno[1]
464
# We don't use the same algorithm here, but we need to keep the
467
first_child_stack_append(first_child)
466
# no parents, use the root sequence
467
sequence = self._root_sequence
468
self._root_sequence +=1
469
assigned_sequence_stack_append(sequence)
469
471
def pop_node(node_name_stack_pop=node_name_stack.pop,
470
472
node_merge_depth_stack_pop=node_merge_depth_stack.pop,
471
first_child_stack_pop=self._first_child_stack.pop,
473
assigned_sequence_stack_pop=self._assigned_sequence_stack.pop,
472
474
left_subtree_pushed_stack_pop=left_subtree_pushed_stack.pop,
473
475
pending_parents_stack_pop=pending_parents_stack.pop,
474
476
original_graph=self._original_graph,
475
477
revnos=self._revnos,
476
478
completed_node_names_add=self._completed_node_names.add,
477
479
scheduled_nodes_append=scheduled_nodes.append,
478
revno_to_branch_count=self._revno_to_branch_count,
480
481
"""Pop the top node off the stack
485
486
# pop off the local variables
486
487
node_name = node_name_stack_pop()
487
488
merge_depth = node_merge_depth_stack_pop()
488
first_child = first_child_stack_pop()
489
sequence = assigned_sequence_stack_pop()
489
490
# remove this node from the pending lists:
490
491
left_subtree_pushed_stack_pop()
491
492
pending_parents_stack_pop()
493
494
parents = original_graph[node_name]
495
496
# node has parents, assign from the left most parent.
496
parent_revno = revnos[parents[0]][0]
497
parent_revno = revnos[parents[0]]
498
499
# not the first child, make a new branch
499
base_revno = parent_revno[0]
500
branch_count = revno_to_branch_count.get(base_revno, 0)
502
revno_to_branch_count[base_revno] = branch_count
503
revno = (parent_revno[0], branch_count, 1)
504
# revno = (parent_revno[0], branch_count, parent_revno[-1]+1)
500
revno = parent_revno[0] + (sequence, 1)
506
# as the first child, we just increase the final revision
508
revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
502
# increment the sequence number within the branch
503
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
510
505
# no parents, use the root sequence
511
root_count = revno_to_branch_count.get(0, 0)
513
revno = (0, root_count, 1)
507
# make a parallel import revision number
508
revno = (0, sequence, 1)
517
revno_to_branch_count[0] = root_count
519
512
# store the revno for this node for future reference
520
513
revnos[node_name][0] = revno
617
610
self._node_merge_depth_stack.append(merge_depth)
618
611
self._left_subtree_pushed_stack.append(False)
619
612
self._pending_parents_stack.append(list(parents))
620
# as we push it, figure out if this is the first child
613
# as we push it, assign it a sequence number against its parent:
621
614
parents = self._original_graph[node_name]
623
616
# node has parents, assign from the left most parent.
624
parent_info = self._revnos[parents[0]]
625
first_child = parent_info[1]
626
parent_info[1] = False
617
parent_revno = self._revnos[parents[0]]
618
sequence = parent_revno[1]
628
# We don't use the same algorithm here, but we need to keep the
631
self._first_child_stack.append(first_child)
621
# no parents, use the root sequence
622
sequence = self._root_sequence
623
self._root_sequence +=1
624
self._assigned_sequence_stack.append(sequence)
633
626
def _pop_node(self):
634
627
"""Pop the top node off the stack
639
632
# pop off the local variables
640
633
node_name = self._node_name_stack.pop()
641
634
merge_depth = self._node_merge_depth_stack.pop()
642
first_child = self._first_child_stack.pop()
635
sequence = self._assigned_sequence_stack.pop()
643
636
# remove this node from the pending lists:
644
637
self._left_subtree_pushed_stack.pop()
645
638
self._pending_parents_stack.pop()
647
640
parents = self._original_graph[node_name]
649
642
# node has parents, assign from the left most parent.
650
parent_revno = self._revnos[parents[0]][0]
643
parent_revno = self._revnos[parents[0]]
652
645
# not the first child, make a new branch
653
base_revno = parent_revno[0]
654
branch_count = self._revno_to_branch_count.get(base_revno, 0)
656
self._revno_to_branch_count[base_revno] = branch_count
657
revno = (parent_revno[0], branch_count, 1)
658
# revno = (parent_revno[0], branch_count, parent_revno[-1]+1)
646
revno = parent_revno[0] + (sequence, 1)
660
# as the first child, we just increase the final revision
662
revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
648
# increment the sequence number within the branch
649
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
664
651
# no parents, use the root sequence
665
root_count = self._revno_to_branch_count.get(0, 0)
667
revno = (0, root_count, 1)
653
# make a parallel import revision number
654
revno = (0, sequence, 1)
671
self._revno_to_branch_count[0] = root_count
673
658
# store the revno for this node for future reference
674
659
self._revnos[node_name][0] = revno
added
removed
bzrlib/tsort.py
