« back to all changes in this revision
Viewing changes to bzrlib/tsort.py
- browse files at revision 3188
- compare with another revision
- compare with revision 3170.3.2
- download diff
- download tarball
- view history from revision 3188
- Committer: Canonical.com Patch Queue Manager
- Date: 2008-01-16 21:12:01 UTC
- mfrom: (3170.3.8 dotted_revnos)
- Revision ID: pqm@pqm.ubuntu.com-20080116211201-fy431qtj4d3vre5x
(jameinel) Switch dotted revnos to always be 3 digits long.
added
removed
bzrlib/tsort.py
192
192
__slots__ = ['_node_name_stack',
193
193
'_node_merge_depth_stack',
194
194
'_pending_parents_stack',
195
'_assigned_sequence_stack',
195
'_first_child_stack',
196
196
'_left_subtree_pushed_stack',
197
197
'_generate_revno',
198
198
'_graph',
200
200
'_stop_revision',
201
201
'_original_graph',
202
202
'_revnos',
203
'_root_sequence',
203
'_revno_to_branch_count',
204
204
'_completed_node_names',
205
205
'_scheduled_nodes',
206
206
]
239
239
found.
240
240
* revno_sequence: When requested this field provides a sequence of
241
241
revision numbers for all revisions. The format is:
242
REVNO[[.BRANCHREVNO.REVNO] ...]. BRANCHREVNO is the number of the
242
(REVNO, BRANCHNUM, BRANCHREVNO). BRANCHNUM 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, sequence_number]
366
# where sequence is the number of branches made from the node,
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
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
369
# [None, 0]
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
369
# [None, True]
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 = {}
374
374
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._assigned_sequence_stack = []
385
self._first_child_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
assigned_sequence_stack_append=self._assigned_sequence_stack.append,
443
original_graph=self._original_graph,
442
first_child_stack_append=self._first_child_stack.append,
444
443
revnos=self._revnos,
445
444
):
446
445
"""Add node_name to the pending node stack.
455
454
node_merge_depth_stack_append(merge_depth)
456
455
left_subtree_pushed_stack_append(False)
457
456
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]
457
# as we push it, check if it is the first child
460
458
if parents:
461
459
# node has parents, assign from the left most parent.
462
parent_revno = revnos[parents[0]]
463
sequence = parent_revno[1]
464
parent_revno[1] += 1
460
parent_info = revnos[parents[0]]
461
first_child = parent_info[1]
462
parent_info[1] = False
465
463
else:
466
# no parents, use the root sequence
467
sequence = self._root_sequence
468
self._root_sequence +=1
469
assigned_sequence_stack_append(sequence)
464
# We don't use the same algorithm here, but we need to keep the
465
# stack in line
466
first_child = None
467
first_child_stack_append(first_child)
470
468
471
469
def pop_node(node_name_stack_pop=node_name_stack.pop,
472
470
node_merge_depth_stack_pop=node_merge_depth_stack.pop,
473
assigned_sequence_stack_pop=self._assigned_sequence_stack.pop,
471
first_child_stack_pop=self._first_child_stack.pop,
474
472
left_subtree_pushed_stack_pop=left_subtree_pushed_stack.pop,
475
473
pending_parents_stack_pop=pending_parents_stack.pop,
476
474
original_graph=self._original_graph,
477
475
revnos=self._revnos,
478
476
completed_node_names_add=self._completed_node_names.add,
479
477
scheduled_nodes_append=scheduled_nodes.append,
478
revno_to_branch_count=self._revno_to_branch_count,
480
479
):
481
480
"""Pop the top node off the stack
482
481
486
485
# pop off the local variables
487
486
node_name = node_name_stack_pop()
488
487
merge_depth = node_merge_depth_stack_pop()
489
sequence = assigned_sequence_stack_pop()
488
first_child = first_child_stack_pop()
490
489
# remove this node from the pending lists:
491
490
left_subtree_pushed_stack_pop()
492
491
pending_parents_stack_pop()
494
493
parents = original_graph[node_name]
495
494
if parents:
496
495
# node has parents, assign from the left most parent.
497
parent_revno = revnos[parents[0]]
498
if sequence:
496
parent_revno = revnos[parents[0]][0]
497
if not first_child:
499
498
# not the first child, make a new branch
500
revno = parent_revno[0] + (sequence, 1)
499
base_revno = parent_revno[0]
500
branch_count = revno_to_branch_count.get(base_revno, 0)
501
branch_count += 1
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)
501
505
else:
502
# increment the sequence number within the branch
503
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
506
# as the first child, we just increase the final revision
507
# number
508
revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
504
509
else:
505
510
# no parents, use the root sequence
506
if sequence:
507
# make a parallel import revision number
508
revno = (0, sequence, 1)
511
root_count = revno_to_branch_count.get(0, 0)
512
if root_count:
513
revno = (0, root_count, 1)
509
514
else:
510
515
revno = (1,)
516
root_count += 1
517
revno_to_branch_count[0] = root_count
511
518
512
519
# store the revno for this node for future reference
513
520
revnos[node_name][0] = revno
610
617
self._node_merge_depth_stack.append(merge_depth)
611
618
self._left_subtree_pushed_stack.append(False)
612
619
self._pending_parents_stack.append(list(parents))
613
# as we push it, assign it a sequence number against its parent:
620
# as we push it, figure out if this is the first child
614
621
parents = self._original_graph[node_name]
615
622
if parents:
616
623
# node has parents, assign from the left most parent.
617
parent_revno = self._revnos[parents[0]]
618
sequence = parent_revno[1]
619
parent_revno[1] += 1
624
parent_info = self._revnos[parents[0]]
625
first_child = parent_info[1]
626
parent_info[1] = False
620
627
else:
621
# no parents, use the root sequence
622
sequence = self._root_sequence
623
self._root_sequence +=1
624
self._assigned_sequence_stack.append(sequence)
628
# We don't use the same algorithm here, but we need to keep the
629
# stack in line
630
first_child = None
631
self._first_child_stack.append(first_child)
625
632
626
633
def _pop_node(self):
627
634
"""Pop the top node off the stack
632
639
# pop off the local variables
633
640
node_name = self._node_name_stack.pop()
634
641
merge_depth = self._node_merge_depth_stack.pop()
635
sequence = self._assigned_sequence_stack.pop()
642
first_child = self._first_child_stack.pop()
636
643
# remove this node from the pending lists:
637
644
self._left_subtree_pushed_stack.pop()
638
645
self._pending_parents_stack.pop()
640
647
parents = self._original_graph[node_name]
641
648
if parents:
642
649
# node has parents, assign from the left most parent.
643
parent_revno = self._revnos[parents[0]]
644
if sequence:
650
parent_revno = self._revnos[parents[0]][0]
651
if not first_child:
645
652
# not the first child, make a new branch
646
revno = parent_revno[0] + (sequence, 1)
653
base_revno = parent_revno[0]
654
branch_count = self._revno_to_branch_count.get(base_revno, 0)
655
branch_count += 1
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)
647
659
else:
648
# increment the sequence number within the branch
649
revno = parent_revno[0][:-1] + (parent_revno[0][-1] + 1,)
660
# as the first child, we just increase the final revision
661
# number
662
revno = parent_revno[:-1] + (parent_revno[-1] + 1,)
650
663
else:
651
664
# no parents, use the root sequence
652
if sequence:
653
# make a parallel import revision number
654
revno = (0, sequence, 1)
665
root_count = self._revno_to_branch_count.get(0, 0)
666
if root_count:
667
revno = (0, root_count, 1)
655
668
else:
656
669
revno = (1,)
670
root_count += 1
671
self._revno_to_branch_count[0] = root_count
657
672
658
673
# store the revno for this node for future reference
659
674
self._revnos[node_name][0] = revno
Loggerhead is a web-based interface for Breezy
Version: 2.0.1