/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: Martin
  • Date: 2009-11-07 08:02:13 UTC
  • mfrom: (4789 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4809.
  • Revision ID: gzlist@googlemail.com-20091107080213-jad185091b3l69ih
Merge bzr.dev 4789 to resolve conflict from the disabling of plink auto-detection, and relocate NEWS

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
25
25
    ctypedef struct PyObject:
26
26
        pass
27
27
 
 
28
    int PyString_CheckExact(object)
 
29
 
 
30
    int PyObject_RichCompareBool(object, object, int)
 
31
    int Py_LT
 
32
 
 
33
    int PyTuple_CheckExact(object)
28
34
    object PyTuple_New(Py_ssize_t n)
29
35
    Py_ssize_t PyTuple_GET_SIZE(object t)
30
36
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
31
37
    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
32
38
 
 
39
    int PyList_CheckExact(object)
33
40
    Py_ssize_t PyList_GET_SIZE(object l)
34
41
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
35
42
    int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
44
51
 
45
52
    void Py_INCREF(object)
46
53
 
 
54
import gc
47
55
 
48
 
from bzrlib import revision
 
56
from bzrlib import errors, revision
49
57
 
50
58
cdef object NULL_REVISION
51
59
NULL_REVISION = revision.NULL_REVISION
59
67
    cdef object children
60
68
    cdef public long gdfo
61
69
    cdef int seen
 
70
    cdef object extra
62
71
 
63
72
    def __init__(self, key):
64
 
        cdef int i
65
 
 
66
73
        self.key = key
67
74
        self.parents = None
68
75
 
70
77
        # Greatest distance from origin
71
78
        self.gdfo = -1
72
79
        self.seen = 0
 
80
        self.extra = None
73
81
 
74
82
    property child_keys:
75
83
        def __get__(self):
80
88
                PyList_Append(keys, child.key)
81
89
            return keys
82
90
 
 
91
    property parent_keys:
 
92
        def __get__(self):
 
93
            if self.parents is None:
 
94
                return None
 
95
            
 
96
            cdef _KnownGraphNode parent
 
97
 
 
98
            keys = []
 
99
            for parent in self.parents:
 
100
                PyList_Append(keys, parent.key)
 
101
            return keys
 
102
    
83
103
    cdef clear_references(self):
84
104
        self.parents = None
85
105
        self.children = None
107
127
    return <_KnownGraphNode>temp_node
108
128
 
109
129
 
110
 
cdef _KnownGraphNode _get_parent(parents, Py_ssize_t pos):
 
130
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
111
131
    cdef PyObject *temp_node
112
 
    cdef _KnownGraphNode node
113
132
 
114
 
    temp_node = PyTuple_GET_ITEM(parents, pos)
 
133
    temp_node = PyTuple_GET_ITEM(tpl, pos)
115
134
    return <_KnownGraphNode>temp_node
116
135
 
117
136
 
118
 
# TODO: slab allocate all _KnownGraphNode objects.
119
 
#       We already know how many we are going to need, except for a couple of
120
 
#       ghosts that could be allocated on demand.
 
137
def get_key(node):
 
138
    cdef _KnownGraphNode real_node
 
139
    real_node = node
 
140
    return real_node.key
 
141
 
 
142
 
 
143
cdef object _sort_list_nodes(object lst_or_tpl, int reverse):
 
144
    """Sort a list of _KnownGraphNode objects.
 
145
 
 
146
    If lst_or_tpl is a list, it is allowed to mutate in place. It may also
 
147
    just return the input list if everything is already sorted.
 
148
    """
 
149
    cdef _KnownGraphNode node1, node2
 
150
    cdef int do_swap, is_tuple
 
151
    cdef Py_ssize_t length
 
152
 
 
153
    is_tuple = PyTuple_CheckExact(lst_or_tpl)
 
154
    if not (is_tuple or PyList_CheckExact(lst_or_tpl)):
 
155
        raise TypeError('lst_or_tpl must be a list or tuple.')
 
156
    length = len(lst_or_tpl)
 
157
    if length == 0 or length == 1:
 
158
        return lst_or_tpl
 
159
    if length == 2:
 
160
        if is_tuple:
 
161
            node1 = _get_tuple_node(lst_or_tpl, 0)
 
162
            node2 = _get_tuple_node(lst_or_tpl, 1)
 
163
        else:
 
164
            node1 = _get_list_node(lst_or_tpl, 0)
 
165
            node2 = _get_list_node(lst_or_tpl, 1)
 
166
        if reverse:
 
167
            do_swap = PyObject_RichCompareBool(node1.key, node2.key, Py_LT)
 
168
        else:
 
169
            do_swap = PyObject_RichCompareBool(node2.key, node1.key, Py_LT)
 
170
        if not do_swap:
 
171
            return lst_or_tpl
 
172
        if is_tuple:
 
173
            return (node2, node1)
 
174
        else:
 
175
            # Swap 'in-place', since lists are mutable
 
176
            Py_INCREF(node1)
 
177
            PyList_SetItem(lst_or_tpl, 1, node1)
 
178
            Py_INCREF(node2)
 
179
            PyList_SetItem(lst_or_tpl, 0, node2)
 
180
            return lst_or_tpl
 
181
    # For all other sizes, we just use 'sorted()'
 
182
    if is_tuple:
 
183
        # Note that sorted() is just list(iterable).sort()
 
184
        lst_or_tpl = list(lst_or_tpl)
 
185
    lst_or_tpl.sort(key=get_key, reverse=reverse)
 
186
    return lst_or_tpl
 
187
 
 
188
 
 
189
cdef class _MergeSorter
121
190
 
122
191
cdef class KnownGraph:
123
192
    """This is a class which assumes we already know the full graph."""
136
205
        # Maps {sorted(revision_id, revision_id): heads}
137
206
        self._known_heads = {}
138
207
        self.do_cache = int(do_cache)
 
208
        # TODO: consider disabling gc since we are allocating a lot of nodes
 
209
        #       that won't be collectable anyway. real world testing has not
 
210
        #       shown a specific impact, yet.
139
211
        self._initialize_nodes(parent_map)
140
212
        self._find_gdfo()
141
213
 
183
255
            parent_keys = <object>temp_parent_keys
184
256
            num_parent_keys = len(parent_keys)
185
257
            node = self._get_or_create_node(key)
186
 
            # We know how many parents, so we could pre allocate an exact sized
187
 
            # tuple here
 
258
            # We know how many parents, so we pre allocate the tuple
188
259
            parent_nodes = PyTuple_New(num_parent_keys)
189
 
            # We use iter here, because parent_keys maybe be a list or tuple
190
260
            for pos2 from 0 <= pos2 < num_parent_keys:
 
261
                # Note: it costs us 10ms out of 40ms to lookup all of these
 
262
                #       parents, it doesn't seem to be an allocation overhead,
 
263
                #       but rather a lookup overhead. There doesn't seem to be
 
264
                #       a way around it, and that is one reason why
 
265
                #       KnownGraphNode maintains a direct pointer to the parent
 
266
                #       node.
 
267
                # We use [] because parent_keys may be a tuple or list
191
268
                parent_node = self._get_or_create_node(parent_keys[pos2])
192
269
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
193
270
                Py_INCREF(parent_node)
209
286
                PyList_Append(tails, node)
210
287
        return tails
211
288
 
 
289
    def _find_tips(self):
 
290
        cdef PyObject *temp_node
 
291
        cdef _KnownGraphNode node
 
292
        cdef Py_ssize_t pos
 
293
 
 
294
        tips = []
 
295
        pos = 0
 
296
        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
 
297
            node = <_KnownGraphNode>temp_node
 
298
            if PyList_GET_SIZE(node.children) == 0:
 
299
                PyList_Append(tips, node)
 
300
        return tips
 
301
 
212
302
    def _find_gdfo(self):
213
303
        cdef _KnownGraphNode node
214
304
        cdef _KnownGraphNode child
315
405
                continue
316
406
            if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
317
407
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
318
 
                    parent_node = _get_parent(node.parents, pos)
 
408
                    parent_node = _get_tuple_node(node.parents, pos)
319
409
                    last_item = last_item + 1
320
410
                    if last_item < PyList_GET_SIZE(pending):
321
411
                        Py_INCREF(parent_node) # SetItem steals a ref
335
425
        if self.do_cache:
336
426
            PyDict_SetItem(self._known_heads, heads_key, heads)
337
427
        return heads
 
428
 
 
429
    def topo_sort(self):
 
430
        """Return the nodes in topological order.
 
431
 
 
432
        All parents must occur before all children.
 
433
        """
 
434
        # This is, for the most part, the same iteration order that we used for
 
435
        # _find_gdfo, consider finding a way to remove the duplication
 
436
        # In general, we find the 'tails' (nodes with no parents), and then
 
437
        # walk to the children. For children that have all of their parents
 
438
        # yielded, we queue up the child to be yielded as well.
 
439
        cdef _KnownGraphNode node
 
440
        cdef _KnownGraphNode child
 
441
        cdef PyObject *temp
 
442
        cdef Py_ssize_t pos
 
443
        cdef int replace
 
444
        cdef Py_ssize_t last_item
 
445
 
 
446
        pending = self._find_tails()
 
447
        if PyList_GET_SIZE(pending) == 0 and len(self._nodes) > 0:
 
448
            raise errors.GraphCycleError(self._nodes)
 
449
 
 
450
        topo_order = []
 
451
 
 
452
        last_item = PyList_GET_SIZE(pending) - 1
 
453
        while last_item >= 0:
 
454
            # Avoid pop followed by push, instead, peek, and replace
 
455
            # timing shows this is 930ms => 770ms for OOo
 
456
            node = _get_list_node(pending, last_item)
 
457
            last_item = last_item - 1
 
458
            if node.parents is not None:
 
459
                # We don't include ghost parents
 
460
                PyList_Append(topo_order, node.key)
 
461
            for pos from 0 <= pos < PyList_GET_SIZE(node.children):
 
462
                child = _get_list_node(node.children, pos)
 
463
                if child.gdfo == -1:
 
464
                    # We know we have a graph cycle because a node has a parent
 
465
                    # which we couldn't find
 
466
                    raise errors.GraphCycleError(self._nodes)
 
467
                child.seen = child.seen + 1
 
468
                if child.seen == PyTuple_GET_SIZE(child.parents):
 
469
                    # All parents of this child have been yielded, queue this
 
470
                    # one to be yielded as well
 
471
                    last_item = last_item + 1
 
472
                    if last_item < PyList_GET_SIZE(pending):
 
473
                        Py_INCREF(child) # SetItem steals a ref
 
474
                        PyList_SetItem(pending, last_item, child)
 
475
                    else:
 
476
                        PyList_Append(pending, child)
 
477
                    # We have queued this node, we don't need to track it
 
478
                    # anymore
 
479
                    child.seen = 0
 
480
        # We started from the parents, so we don't need to do anymore work
 
481
        return topo_order
 
482
 
 
483
    def gc_sort(self):
 
484
        """Return a reverse topological ordering which is 'stable'.
 
485
 
 
486
        There are a few constraints:
 
487
          1) Reverse topological (all children before all parents)
 
488
          2) Grouped by prefix
 
489
          3) 'stable' sorting, so that we get the same result, independent of
 
490
             machine, or extra data.
 
491
        To do this, we use the same basic algorithm as topo_sort, but when we
 
492
        aren't sure what node to access next, we sort them lexicographically.
 
493
        """
 
494
        cdef PyObject *temp
 
495
        cdef Py_ssize_t pos, last_item
 
496
        cdef _KnownGraphNode node, node2, parent_node
 
497
 
 
498
        tips = self._find_tips()
 
499
        # Split the tips based on prefix
 
500
        prefix_tips = {}
 
501
        for pos from 0 <= pos < PyList_GET_SIZE(tips):
 
502
            node = _get_list_node(tips, pos)
 
503
            if PyString_CheckExact(node.key) or len(node.key) == 1:
 
504
                prefix = ''
 
505
            else:
 
506
                prefix = node.key[0]
 
507
            temp = PyDict_GetItem(prefix_tips, prefix)
 
508
            if temp == NULL:
 
509
                prefix_tips[prefix] = [node]
 
510
            else:
 
511
                tip_nodes = <object>temp
 
512
                PyList_Append(tip_nodes, node)
 
513
 
 
514
        result = []
 
515
        for prefix in sorted(prefix_tips):
 
516
            temp = PyDict_GetItem(prefix_tips, prefix)
 
517
            assert temp != NULL
 
518
            tip_nodes = <object>temp
 
519
            pending = _sort_list_nodes(tip_nodes, 1)
 
520
            last_item = PyList_GET_SIZE(pending) - 1
 
521
            while last_item >= 0:
 
522
                node = _get_list_node(pending, last_item)
 
523
                last_item = last_item - 1
 
524
                if node.parents is None:
 
525
                    # Ghost
 
526
                    continue
 
527
                PyList_Append(result, node.key)
 
528
                # Sorting the parent keys isn't strictly necessary for stable
 
529
                # sorting of a given graph. But it does help minimize the
 
530
                # differences between graphs
 
531
                # For bzr.dev ancestry:
 
532
                #   4.73ms  no sort
 
533
                #   7.73ms  RichCompareBool sort
 
534
                parents = _sort_list_nodes(node.parents, 1)
 
535
                for pos from 0 <= pos < len(parents):
 
536
                    if PyTuple_CheckExact(parents):
 
537
                        parent_node = _get_tuple_node(parents, pos)
 
538
                    else:
 
539
                        parent_node = _get_list_node(parents, pos)
 
540
                    # TODO: GraphCycle detection
 
541
                    parent_node.seen = parent_node.seen + 1
 
542
                    if (parent_node.seen
 
543
                        == PyList_GET_SIZE(parent_node.children)):
 
544
                        # All children have been processed, queue up this
 
545
                        # parent
 
546
                        last_item = last_item + 1
 
547
                        if last_item < PyList_GET_SIZE(pending):
 
548
                            Py_INCREF(parent_node) # SetItem steals a ref
 
549
                            PyList_SetItem(pending, last_item, parent_node)
 
550
                        else:
 
551
                            PyList_Append(pending, parent_node)
 
552
                        parent_node.seen = 0
 
553
        return result
 
554
 
 
555
    def merge_sort(self, tip_key):
 
556
        """Compute the merge sorted graph output."""
 
557
        cdef _MergeSorter sorter
 
558
 
 
559
        # TODO: consider disabling gc since we are allocating a lot of nodes
 
560
        #       that won't be collectable anyway. real world testing has not
 
561
        #       shown a specific impact, yet.
 
562
        sorter = _MergeSorter(self, tip_key)
 
563
        return sorter.topo_order()
 
564
    
 
565
    def get_parent_keys(self, key):
 
566
        """Get the parents for a key
 
567
        
 
568
        Returns a list containg the parents keys. If the key is a ghost,
 
569
        None is returned. A KeyError will be raised if the key is not in
 
570
        the graph.
 
571
        
 
572
        :param keys: Key to check (eg revision_id)
 
573
        :return: A list of parents
 
574
        """
 
575
        return self._nodes[key].parent_keys 
 
576
 
 
577
    def get_child_keys(self, key):
 
578
        """Get the children for a key
 
579
        
 
580
        Returns a list containg the children keys. A KeyError will be raised
 
581
        if the key is not in the graph.
 
582
        
 
583
        :param keys: Key to check (eg revision_id)
 
584
        :return: A list of children
 
585
        """
 
586
        return self._nodes[key].child_keys    
 
587
 
 
588
 
 
589
cdef class _MergeSortNode:
 
590
    """Tracks information about a node during the merge_sort operation."""
 
591
 
 
592
    # Public api
 
593
    cdef public object key
 
594
    cdef public long merge_depth
 
595
    cdef public object end_of_merge # True/False Is this the end of the current merge
 
596
 
 
597
    # Private api, used while computing the information
 
598
    cdef _KnownGraphNode left_parent
 
599
    cdef _KnownGraphNode left_pending_parent
 
600
    cdef object pending_parents # list of _KnownGraphNode for non-left parents
 
601
    cdef long _revno_first
 
602
    cdef long _revno_second
 
603
    cdef long _revno_last
 
604
    # TODO: turn these into flag/bit fields rather than individual members
 
605
    cdef int is_first_child # Is this the first child?
 
606
    cdef int seen_by_child # A child node has seen this parent
 
607
    cdef int completed # Fully Processed
 
608
 
 
609
    def __init__(self, key):
 
610
        self.key = key
 
611
        self.merge_depth = -1
 
612
        self.left_parent = None
 
613
        self.left_pending_parent = None
 
614
        self.pending_parents = None
 
615
        self._revno_first = -1
 
616
        self._revno_second = -1
 
617
        self._revno_last = -1
 
618
        self.is_first_child = 0
 
619
        self.seen_by_child = 0
 
620
        self.completed = 0
 
621
 
 
622
    def __repr__(self):
 
623
        return '%s(%s depth:%s rev:%s,%s,%s first:%s seen:%s)' % (
 
624
            self.__class__.__name__, self.key,
 
625
            self.merge_depth,
 
626
            self._revno_first, self._revno_second, self._revno_last,
 
627
            self.is_first_child, self.seen_by_child)
 
628
 
 
629
    cdef int has_pending_parents(self):
 
630
        if self.left_pending_parent is not None or self.pending_parents:
 
631
            return 1
 
632
        return 0
 
633
 
 
634
    cdef object _revno(self):
 
635
        if self._revno_first == -1:
 
636
            if self._revno_second != -1:
 
637
                raise RuntimeError('Something wrong with: %s' % (self,))
 
638
            return (self._revno_last,)
 
639
        else:
 
640
            return (self._revno_first, self._revno_second, self._revno_last)
 
641
 
 
642
    property revno:
 
643
        def __get__(self):
 
644
            return self._revno()
 
645
 
 
646
 
 
647
cdef class _MergeSorter:
 
648
    """This class does the work of computing the merge_sort ordering.
 
649
 
 
650
    We have some small advantages, in that we get all the extra information
 
651
    that KnownGraph knows, like knowing the child lists, etc.
 
652
    """
 
653
 
 
654
    # Current performance numbers for merge_sort(bzr_dev_parent_map):
 
655
    #  302ms tsort.merge_sort()
 
656
    #   91ms graph.KnownGraph().merge_sort()
 
657
    #   40ms kg.merge_sort()
 
658
 
 
659
    cdef KnownGraph graph
 
660
    cdef object _depth_first_stack  # list
 
661
    cdef Py_ssize_t _last_stack_item # offset to last item on stack
 
662
    # cdef object _ms_nodes # dict of key => _MergeSortNode
 
663
    cdef object _revno_to_branch_count # {revno => num child branches}
 
664
    cdef object _scheduled_nodes # List of nodes ready to be yielded
 
665
 
 
666
    def __init__(self, known_graph, tip_key):
 
667
        cdef _KnownGraphNode node
 
668
 
 
669
        self.graph = known_graph
 
670
        # self._ms_nodes = {}
 
671
        self._revno_to_branch_count = {}
 
672
        self._depth_first_stack = []
 
673
        self._last_stack_item = -1
 
674
        self._scheduled_nodes = []
 
675
        if (tip_key is not None and tip_key != NULL_REVISION
 
676
            and tip_key != (NULL_REVISION,)):
 
677
            node = self.graph._nodes[tip_key]
 
678
            self._push_node(node, 0)
 
679
 
 
680
    cdef _MergeSortNode _get_ms_node(self, _KnownGraphNode node):
 
681
        cdef PyObject *temp_node
 
682
        cdef _MergeSortNode ms_node
 
683
 
 
684
        if node.extra is None:
 
685
            ms_node = _MergeSortNode(node.key)
 
686
            node.extra = ms_node
 
687
        else:
 
688
            ms_node = <_MergeSortNode>node.extra
 
689
        return ms_node
 
690
 
 
691
    cdef _push_node(self, _KnownGraphNode node, long merge_depth):
 
692
        cdef _KnownGraphNode parent_node
 
693
        cdef _MergeSortNode ms_node, ms_parent_node
 
694
        cdef Py_ssize_t pos
 
695
 
 
696
        ms_node = self._get_ms_node(node)
 
697
        ms_node.merge_depth = merge_depth
 
698
        if node.parents is None:
 
699
            raise RuntimeError('ghost nodes should not be pushed'
 
700
                               ' onto the stack: %s' % (node,))
 
701
        if PyTuple_GET_SIZE(node.parents) > 0:
 
702
            parent_node = _get_tuple_node(node.parents, 0)
 
703
            ms_node.left_parent = parent_node
 
704
            if parent_node.parents is None: # left-hand ghost
 
705
                ms_node.left_pending_parent = None
 
706
                ms_node.left_parent = None
 
707
            else:
 
708
                ms_node.left_pending_parent = parent_node
 
709
        if PyTuple_GET_SIZE(node.parents) > 1:
 
710
            ms_node.pending_parents = []
 
711
            for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
 
712
                parent_node = _get_tuple_node(node.parents, pos)
 
713
                if parent_node.parents is None: # ghost
 
714
                    continue
 
715
                PyList_Append(ms_node.pending_parents, parent_node)
 
716
 
 
717
        ms_node.is_first_child = 1
 
718
        if ms_node.left_parent is not None:
 
719
            ms_parent_node = self._get_ms_node(ms_node.left_parent)
 
720
            if ms_parent_node.seen_by_child:
 
721
                ms_node.is_first_child = 0
 
722
            ms_parent_node.seen_by_child = 1
 
723
        self._last_stack_item = self._last_stack_item + 1
 
724
        if self._last_stack_item < PyList_GET_SIZE(self._depth_first_stack):
 
725
            Py_INCREF(node) # SetItem steals a ref
 
726
            PyList_SetItem(self._depth_first_stack, self._last_stack_item,
 
727
                           node)
 
728
        else:
 
729
            PyList_Append(self._depth_first_stack, node)
 
730
 
 
731
    cdef _pop_node(self):
 
732
        cdef PyObject *temp
 
733
        cdef _MergeSortNode ms_node, ms_parent_node, ms_prev_node
 
734
        cdef _KnownGraphNode node, parent_node, prev_node
 
735
 
 
736
        node = _get_list_node(self._depth_first_stack, self._last_stack_item)
 
737
        ms_node = <_MergeSortNode>node.extra
 
738
        self._last_stack_item = self._last_stack_item - 1
 
739
        if ms_node.left_parent is not None:
 
740
            # Assign the revision number from the left-hand parent
 
741
            ms_parent_node = <_MergeSortNode>ms_node.left_parent.extra
 
742
            if ms_node.is_first_child:
 
743
                # First child just increments the final digit
 
744
                ms_node._revno_first = ms_parent_node._revno_first
 
745
                ms_node._revno_second = ms_parent_node._revno_second
 
746
                ms_node._revno_last = ms_parent_node._revno_last + 1
 
747
            else:
 
748
                # Not the first child, make a new branch
 
749
                #  (mainline_revno, branch_count, 1)
 
750
                if ms_parent_node._revno_first == -1:
 
751
                    # Mainline ancestor, the increment is on the last digit
 
752
                    base_revno = ms_parent_node._revno_last
 
753
                else:
 
754
                    base_revno = ms_parent_node._revno_first
 
755
                temp = PyDict_GetItem(self._revno_to_branch_count,
 
756
                                      base_revno)
 
757
                if temp == NULL:
 
758
                    branch_count = 1
 
759
                else:
 
760
                    branch_count = (<object>temp) + 1
 
761
                PyDict_SetItem(self._revno_to_branch_count, base_revno,
 
762
                               branch_count)
 
763
                ms_node._revno_first = base_revno
 
764
                ms_node._revno_second = branch_count
 
765
                ms_node._revno_last = 1
 
766
        else:
 
767
            temp = PyDict_GetItem(self._revno_to_branch_count, 0)
 
768
            if temp == NULL:
 
769
                # The first root node doesn't have a 3-digit revno
 
770
                root_count = 0
 
771
                ms_node._revno_first = -1
 
772
                ms_node._revno_second = -1
 
773
                ms_node._revno_last = 1
 
774
            else:
 
775
                root_count = (<object>temp) + 1
 
776
                ms_node._revno_first = 0
 
777
                ms_node._revno_second = root_count
 
778
                ms_node._revno_last = 1
 
779
            PyDict_SetItem(self._revno_to_branch_count, 0, root_count)
 
780
        ms_node.completed = 1
 
781
        if PyList_GET_SIZE(self._scheduled_nodes) == 0:
 
782
            # The first scheduled node is always the end of merge
 
783
            ms_node.end_of_merge = True
 
784
        else:
 
785
            prev_node = _get_list_node(self._scheduled_nodes,
 
786
                                    PyList_GET_SIZE(self._scheduled_nodes) - 1)
 
787
            ms_prev_node = <_MergeSortNode>prev_node.extra
 
788
            if ms_prev_node.merge_depth < ms_node.merge_depth:
 
789
                # The previously pushed node is to our left, so this is the end
 
790
                # of this right-hand chain
 
791
                ms_node.end_of_merge = True
 
792
            elif (ms_prev_node.merge_depth == ms_node.merge_depth
 
793
                  and prev_node not in node.parents):
 
794
                # The next node is not a direct parent of this node
 
795
                ms_node.end_of_merge = True
 
796
            else:
 
797
                ms_node.end_of_merge = False
 
798
        PyList_Append(self._scheduled_nodes, node)
 
799
 
 
800
    cdef _schedule_stack(self):
 
801
        cdef _KnownGraphNode last_node, next_node
 
802
        cdef _MergeSortNode ms_node, ms_last_node, ms_next_node
 
803
        cdef long next_merge_depth
 
804
        ordered = []
 
805
        while self._last_stack_item >= 0:
 
806
            # Peek at the last item on the stack
 
807
            last_node = _get_list_node(self._depth_first_stack,
 
808
                                       self._last_stack_item)
 
809
            if last_node.gdfo == -1:
 
810
                # if _find_gdfo skipped a node, that means there is a graph
 
811
                # cycle, error out now
 
812
                raise errors.GraphCycleError(self.graph._nodes)
 
813
            ms_last_node = <_MergeSortNode>last_node.extra
 
814
            if not ms_last_node.has_pending_parents():
 
815
                # Processed all parents, pop this node
 
816
                self._pop_node()
 
817
                continue
 
818
            while ms_last_node.has_pending_parents():
 
819
                if ms_last_node.left_pending_parent is not None:
 
820
                    # recurse depth first into the primary parent
 
821
                    next_node = ms_last_node.left_pending_parent
 
822
                    ms_last_node.left_pending_parent = None
 
823
                else:
 
824
                    # place any merges in right-to-left order for scheduling
 
825
                    # which gives us left-to-right order after we reverse
 
826
                    # the scheduled queue.
 
827
                    # Note: This has the effect of allocating common-new
 
828
                    #       revisions to the right-most subtree rather than the
 
829
                    #       left most, which will display nicely (you get
 
830
                    #       smaller trees at the top of the combined merge).
 
831
                    next_node = ms_last_node.pending_parents.pop()
 
832
                ms_next_node = self._get_ms_node(next_node)
 
833
                if ms_next_node.completed:
 
834
                    # this parent was completed by a child on the
 
835
                    # call stack. skip it.
 
836
                    continue
 
837
                # otherwise transfer it from the source graph into the
 
838
                # top of the current depth first search stack.
 
839
 
 
840
                if next_node is ms_last_node.left_parent:
 
841
                    next_merge_depth = ms_last_node.merge_depth
 
842
                else:
 
843
                    next_merge_depth = ms_last_node.merge_depth + 1
 
844
                self._push_node(next_node, next_merge_depth)
 
845
                # and do not continue processing parents until this 'call'
 
846
                # has recursed.
 
847
                break
 
848
 
 
849
    cdef topo_order(self):
 
850
        cdef _MergeSortNode ms_node
 
851
        cdef _KnownGraphNode node
 
852
        cdef Py_ssize_t pos
 
853
        cdef PyObject *temp_key, *temp_node
 
854
 
 
855
        # Note: allocating a _MergeSortNode and deallocating it for all nodes
 
856
        #       costs approx 8.52ms (21%) of the total runtime
 
857
        #       We might consider moving the attributes into the base
 
858
        #       KnownGraph object.
 
859
        self._schedule_stack()
 
860
 
 
861
        # We've set up the basic schedule, now we can continue processing the
 
862
        # output.
 
863
        # Note: This final loop costs us 40.0ms => 28.8ms (11ms, 25%) on
 
864
        #       bzr.dev, to convert the internal Object representation into a
 
865
        #       Tuple representation...
 
866
        #       2ms is walking the data and computing revno tuples
 
867
        #       7ms is computing the return tuple
 
868
        #       4ms is PyList_Append()
 
869
        ordered = []
 
870
        # output the result in reverse order, and separate the generated info
 
871
        for pos from PyList_GET_SIZE(self._scheduled_nodes) > pos >= 0:
 
872
            node = _get_list_node(self._scheduled_nodes, pos)
 
873
            ms_node = <_MergeSortNode>node.extra
 
874
            PyList_Append(ordered, ms_node)
 
875
            node.extra = None
 
876
        # Clear out the scheduled nodes now that we're done
 
877
        self._scheduled_nodes = []
 
878
        return ordered