← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

https://launchpad.net/bugs/524184
NEWS section template into a separate file

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