← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

(vila) Make all transport put_bytes() raises TypeError when given unicode
 strings rather than bytes (Vincent Ladeuil)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
1
 
# Copyright (C) 2009 Canonical Ltd
 
1
# Copyright (C) 2009, 2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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
from collections import deque
 
55
import gc
47
56
 
48
 
from bzrlib import revision
 
57
from bzrlib import errors, revision
49
58
 
50
59
cdef object NULL_REVISION
51
60
NULL_REVISION = revision.NULL_REVISION
59
68
    cdef object children
60
69
    cdef public long gdfo
61
70
    cdef int seen
 
71
    cdef object extra
62
72
 
63
73
    def __init__(self, key):
64
 
        cdef int i
65
 
 
66
74
        self.key = key
67
75
        self.parents = None
68
76
 
70
78
        # Greatest distance from origin
71
79
        self.gdfo = -1
72
80
        self.seen = 0
 
81
        self.extra = None
73
82
 
74
83
    property child_keys:
75
84
        def __get__(self):
80
89
                PyList_Append(keys, child.key)
81
90
            return keys
82
91
 
 
92
    property parent_keys:
 
93
        def __get__(self):
 
94
            if self.parents is None:
 
95
                return None
 
96
            
 
97
            cdef _KnownGraphNode parent
 
98
 
 
99
            keys = []
 
100
            for parent in self.parents:
 
101
                PyList_Append(keys, parent.key)
 
102
            return keys
 
103
    
83
104
    cdef clear_references(self):
84
105
        self.parents = None
85
106
        self.children = None
107
128
    return <_KnownGraphNode>temp_node
108
129
 
109
130
 
110
 
cdef _KnownGraphNode _get_parent(parents, Py_ssize_t pos):
 
131
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
111
132
    cdef PyObject *temp_node
112
 
    cdef _KnownGraphNode node
113
133
 
114
 
    temp_node = PyTuple_GET_ITEM(parents, pos)
 
134
    temp_node = PyTuple_GET_ITEM(tpl, pos)
115
135
    return <_KnownGraphNode>temp_node
116
136
 
117
137
 
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.
 
138
def get_key(node):
 
139
    cdef _KnownGraphNode real_node
 
140
    real_node = node
 
141
    return real_node.key
 
142
 
 
143
 
 
144
cdef object _sort_list_nodes(object lst_or_tpl, int reverse):
 
145
    """Sort a list of _KnownGraphNode objects.
 
146
 
 
147
    If lst_or_tpl is a list, it is allowed to mutate in place. It may also
 
148
    just return the input list if everything is already sorted.
 
149
    """
 
150
    cdef _KnownGraphNode node1, node2
 
151
    cdef int do_swap, is_tuple
 
152
    cdef Py_ssize_t length
 
153
 
 
154
    is_tuple = PyTuple_CheckExact(lst_or_tpl)
 
155
    if not (is_tuple or PyList_CheckExact(lst_or_tpl)):
 
156
        raise TypeError('lst_or_tpl must be a list or tuple.')
 
157
    length = len(lst_or_tpl)
 
158
    if length == 0 or length == 1:
 
159
        return lst_or_tpl
 
160
    if length == 2:
 
161
        if is_tuple:
 
162
            node1 = _get_tuple_node(lst_or_tpl, 0)
 
163
            node2 = _get_tuple_node(lst_or_tpl, 1)
 
164
        else:
 
165
            node1 = _get_list_node(lst_or_tpl, 0)
 
166
            node2 = _get_list_node(lst_or_tpl, 1)
 
167
        if reverse:
 
168
            do_swap = PyObject_RichCompareBool(node1.key, node2.key, Py_LT)
 
169
        else:
 
170
            do_swap = PyObject_RichCompareBool(node2.key, node1.key, Py_LT)
 
171
        if not do_swap:
 
172
            return lst_or_tpl
 
173
        if is_tuple:
 
174
            return (node2, node1)
 
175
        else:
 
176
            # Swap 'in-place', since lists are mutable
 
177
            Py_INCREF(node1)
 
178
            PyList_SetItem(lst_or_tpl, 1, node1)
 
179
            Py_INCREF(node2)
 
180
            PyList_SetItem(lst_or_tpl, 0, node2)
 
181
            return lst_or_tpl
 
182
    # For all other sizes, we just use 'sorted()'
 
183
    if is_tuple:
 
184
        # Note that sorted() is just list(iterable).sort()
 
185
        lst_or_tpl = list(lst_or_tpl)
 
186
    lst_or_tpl.sort(key=get_key, reverse=reverse)
 
187
    return lst_or_tpl
 
188
 
 
189
 
 
190
cdef class _MergeSorter
121
191
 
122
192
cdef class KnownGraph:
123
193
    """This is a class which assumes we already know the full graph."""
124
194
 
125
195
    cdef public object _nodes
126
 
    cdef object _known_heads
 
196
    cdef public object _known_heads
127
197
    cdef public int do_cache
128
198
 
129
199
    def __init__(self, parent_map, do_cache=True):
136
206
        # Maps {sorted(revision_id, revision_id): heads}
137
207
        self._known_heads = {}
138
208
        self.do_cache = int(do_cache)
 
209
        # TODO: consider disabling gc since we are allocating a lot of nodes
 
210
        #       that won't be collectable anyway. real world testing has not
 
211
        #       shown a specific impact, yet.
139
212
        self._initialize_nodes(parent_map)
140
213
        self._find_gdfo()
141
214
 
160
233
            node = <_KnownGraphNode>temp_node
161
234
        return node
162
235
 
 
236
    cdef _populate_parents(self, _KnownGraphNode node, parent_keys):
 
237
        cdef Py_ssize_t num_parent_keys, pos
 
238
        cdef _KnownGraphNode parent_node
 
239
 
 
240
        num_parent_keys = len(parent_keys)
 
241
        # We know how many parents, so we pre allocate the tuple
 
242
        parent_nodes = PyTuple_New(num_parent_keys)
 
243
        for pos from 0 <= pos < num_parent_keys:
 
244
            # Note: it costs us 10ms out of 40ms to lookup all of these
 
245
            #       parents, it doesn't seem to be an allocation overhead,
 
246
            #       but rather a lookup overhead. There doesn't seem to be
 
247
            #       a way around it, and that is one reason why
 
248
            #       KnownGraphNode maintains a direct pointer to the parent
 
249
            #       node.
 
250
            # We use [] because parent_keys may be a tuple or list
 
251
            parent_node = self._get_or_create_node(parent_keys[pos])
 
252
            # PyTuple_SET_ITEM will steal a reference, so INCREF first
 
253
            Py_INCREF(parent_node)
 
254
            PyTuple_SET_ITEM(parent_nodes, pos, parent_node)
 
255
            PyList_Append(parent_node.children, node)
 
256
        node.parents = parent_nodes
 
257
 
163
258
    def _initialize_nodes(self, parent_map):
164
259
        """Populate self._nodes.
165
260
 
170
265
          child keys,
171
266
        """
172
267
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
173
 
        cdef Py_ssize_t pos, pos2, num_parent_keys
 
268
        cdef Py_ssize_t pos
174
269
        cdef _KnownGraphNode node
175
270
        cdef _KnownGraphNode parent_node
176
271
 
181
276
        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
182
277
            key = <object>temp_key
183
278
            parent_keys = <object>temp_parent_keys
184
 
            num_parent_keys = len(parent_keys)
185
279
            node = self._get_or_create_node(key)
186
 
            # We know how many parents, so we could pre allocate an exact sized
187
 
            # tuple here
188
 
            parent_nodes = PyTuple_New(num_parent_keys)
189
 
            # We use iter here, because parent_keys maybe be a list or tuple
190
 
            for pos2 from 0 <= pos2 < num_parent_keys:
191
 
                parent_node = self._get_or_create_node(parent_keys[pos2])
192
 
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
193
 
                Py_INCREF(parent_node)
194
 
                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
195
 
                PyList_Append(parent_node.children, node)
196
 
            node.parents = parent_nodes
 
280
            self._populate_parents(node, parent_keys)
197
281
 
198
282
    def _find_tails(self):
199
283
        cdef PyObject *temp_node
209
293
                PyList_Append(tails, node)
210
294
        return tails
211
295
 
 
296
    def _find_tips(self):
 
297
        cdef PyObject *temp_node
 
298
        cdef _KnownGraphNode node
 
299
        cdef Py_ssize_t pos
 
300
 
 
301
        tips = []
 
302
        pos = 0
 
303
        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
 
304
            node = <_KnownGraphNode>temp_node
 
305
            if PyList_GET_SIZE(node.children) == 0:
 
306
                PyList_Append(tips, node)
 
307
        return tips
 
308
 
212
309
    def _find_gdfo(self):
213
310
        cdef _KnownGraphNode node
214
311
        cdef _KnownGraphNode child
244
341
                    # anymore
245
342
                    child.seen = 0
246
343
 
 
344
    def add_node(self, key, parent_keys):
 
345
        """Add a new node to the graph.
 
346
 
 
347
        If this fills in a ghost, then the gdfos of all children will be
 
348
        updated accordingly.
 
349
        
 
350
        :param key: The node being added. If this is a duplicate, this is a
 
351
            no-op.
 
352
        :param parent_keys: The parents of the given node.
 
353
        :return: None (should we return if this was a ghost, etc?)
 
354
        """
 
355
        cdef PyObject *maybe_node
 
356
        cdef _KnownGraphNode node, parent_node, child_node
 
357
        cdef long parent_gdfo, next_gdfo
 
358
 
 
359
        maybe_node = PyDict_GetItem(self._nodes, key)
 
360
        if maybe_node != NULL:
 
361
            node = <_KnownGraphNode>maybe_node
 
362
            if node.parents is None:
 
363
                # We are filling in a ghost
 
364
                self._populate_parents(node, parent_keys)
 
365
                # We can't trust cached heads anymore
 
366
                self._known_heads.clear()
 
367
            else: # Ensure that the parent_key list matches
 
368
                existing_parent_keys = []
 
369
                for parent_node in node.parents:
 
370
                    existing_parent_keys.append(parent_node.key)
 
371
                # Make sure we use a list for the comparison, in case it was a
 
372
                # tuple, etc
 
373
                parent_keys = list(parent_keys)
 
374
                if existing_parent_keys == parent_keys:
 
375
                    # Exact match, nothing more to do
 
376
                    return
 
377
                else:
 
378
                    raise ValueError('Parent key mismatch, existing node %s'
 
379
                        ' has parents of %s not %s'
 
380
                        % (key, existing_parent_keys, parent_keys))
 
381
        else:
 
382
            node = _KnownGraphNode(key)
 
383
            PyDict_SetItem(self._nodes, key, node)
 
384
            self._populate_parents(node, parent_keys)
 
385
        parent_gdfo = 0
 
386
        for parent_node in node.parents:
 
387
            if parent_node.gdfo == -1:
 
388
                # This is a newly introduced ghost, so it gets gdfo of 1
 
389
                parent_node.gdfo = 1
 
390
            if parent_gdfo < parent_node.gdfo:
 
391
                parent_gdfo = parent_node.gdfo
 
392
        node.gdfo = parent_gdfo + 1
 
393
        # Now fill the gdfo to all children
 
394
        # Note that this loop is slightly inefficient, in that we may visit the
 
395
        # same child (and its decendents) more than once, however, it is
 
396
        # 'efficient' in that we only walk to nodes that would be updated,
 
397
        # rather than all nodes
 
398
        # We use a deque rather than a simple list stack, to go for BFD rather
 
399
        # than DFD. So that if a longer path is possible, we walk it before we
 
400
        # get to the final child
 
401
        pending = deque([node])
 
402
        pending_popleft = pending.popleft
 
403
        pending_append = pending.append
 
404
        while pending:
 
405
            node = pending_popleft()
 
406
            next_gdfo = node.gdfo + 1
 
407
            for child_node in node.children:
 
408
                if child_node.gdfo < next_gdfo:
 
409
                    # This child is being updated, we need to check its
 
410
                    # children
 
411
                    child_node.gdfo = next_gdfo
 
412
                    pending_append(child_node)
 
413
 
247
414
    def heads(self, keys):
248
415
        """Return the heads from amongst keys.
249
416
 
315
482
                continue
316
483
            if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
317
484
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
318
 
                    parent_node = _get_parent(node.parents, pos)
 
485
                    parent_node = _get_tuple_node(node.parents, pos)
319
486
                    last_item = last_item + 1
320
487
                    if last_item < PyList_GET_SIZE(pending):
321
488
                        Py_INCREF(parent_node) # SetItem steals a ref
335
502
        if self.do_cache:
336
503
            PyDict_SetItem(self._known_heads, heads_key, heads)
337
504
        return heads
 
505
 
 
506
    def topo_sort(self):
 
507
        """Return the nodes in topological order.
 
508
 
 
509
        All parents must occur before all children.
 
510
        """
 
511
        # This is, for the most part, the same iteration order that we used for
 
512
        # _find_gdfo, consider finding a way to remove the duplication
 
513
        # In general, we find the 'tails' (nodes with no parents), and then
 
514
        # walk to the children. For children that have all of their parents
 
515
        # yielded, we queue up the child to be yielded as well.
 
516
        cdef _KnownGraphNode node
 
517
        cdef _KnownGraphNode child
 
518
        cdef PyObject *temp
 
519
        cdef Py_ssize_t pos
 
520
        cdef int replace
 
521
        cdef Py_ssize_t last_item
 
522
 
 
523
        pending = self._find_tails()
 
524
        if PyList_GET_SIZE(pending) == 0 and len(self._nodes) > 0:
 
525
            raise errors.GraphCycleError(self._nodes)
 
526
 
 
527
        topo_order = []
 
528
 
 
529
        last_item = PyList_GET_SIZE(pending) - 1
 
530
        while last_item >= 0:
 
531
            # Avoid pop followed by push, instead, peek, and replace
 
532
            # timing shows this is 930ms => 770ms for OOo
 
533
            node = _get_list_node(pending, last_item)
 
534
            last_item = last_item - 1
 
535
            if node.parents is not None:
 
536
                # We don't include ghost parents
 
537
                PyList_Append(topo_order, node.key)
 
538
            for pos from 0 <= pos < PyList_GET_SIZE(node.children):
 
539
                child = _get_list_node(node.children, pos)
 
540
                if child.gdfo == -1:
 
541
                    # We know we have a graph cycle because a node has a parent
 
542
                    # which we couldn't find
 
543
                    raise errors.GraphCycleError(self._nodes)
 
544
                child.seen = child.seen + 1
 
545
                if child.seen == PyTuple_GET_SIZE(child.parents):
 
546
                    # All parents of this child have been yielded, queue this
 
547
                    # one to be yielded as well
 
548
                    last_item = last_item + 1
 
549
                    if last_item < PyList_GET_SIZE(pending):
 
550
                        Py_INCREF(child) # SetItem steals a ref
 
551
                        PyList_SetItem(pending, last_item, child)
 
552
                    else:
 
553
                        PyList_Append(pending, child)
 
554
                    # We have queued this node, we don't need to track it
 
555
                    # anymore
 
556
                    child.seen = 0
 
557
        # We started from the parents, so we don't need to do anymore work
 
558
        return topo_order
 
559
 
 
560
    def gc_sort(self):
 
561
        """Return a reverse topological ordering which is 'stable'.
 
562
 
 
563
        There are a few constraints:
 
564
          1) Reverse topological (all children before all parents)
 
565
          2) Grouped by prefix
 
566
          3) 'stable' sorting, so that we get the same result, independent of
 
567
             machine, or extra data.
 
568
        To do this, we use the same basic algorithm as topo_sort, but when we
 
569
        aren't sure what node to access next, we sort them lexicographically.
 
570
        """
 
571
        cdef PyObject *temp
 
572
        cdef Py_ssize_t pos, last_item
 
573
        cdef _KnownGraphNode node, node2, parent_node
 
574
 
 
575
        tips = self._find_tips()
 
576
        # Split the tips based on prefix
 
577
        prefix_tips = {}
 
578
        for pos from 0 <= pos < PyList_GET_SIZE(tips):
 
579
            node = _get_list_node(tips, pos)
 
580
            if PyString_CheckExact(node.key) or len(node.key) == 1:
 
581
                prefix = ''
 
582
            else:
 
583
                prefix = node.key[0]
 
584
            temp = PyDict_GetItem(prefix_tips, prefix)
 
585
            if temp == NULL:
 
586
                prefix_tips[prefix] = [node]
 
587
            else:
 
588
                tip_nodes = <object>temp
 
589
                PyList_Append(tip_nodes, node)
 
590
 
 
591
        result = []
 
592
        for prefix in sorted(prefix_tips):
 
593
            temp = PyDict_GetItem(prefix_tips, prefix)
 
594
            assert temp != NULL
 
595
            tip_nodes = <object>temp
 
596
            pending = _sort_list_nodes(tip_nodes, 1)
 
597
            last_item = PyList_GET_SIZE(pending) - 1
 
598
            while last_item >= 0:
 
599
                node = _get_list_node(pending, last_item)
 
600
                last_item = last_item - 1
 
601
                if node.parents is None:
 
602
                    # Ghost
 
603
                    continue
 
604
                PyList_Append(result, node.key)
 
605
                # Sorting the parent keys isn't strictly necessary for stable
 
606
                # sorting of a given graph. But it does help minimize the
 
607
                # differences between graphs
 
608
                # For bzr.dev ancestry:
 
609
                #   4.73ms  no sort
 
610
                #   7.73ms  RichCompareBool sort
 
611
                parents = _sort_list_nodes(node.parents, 1)
 
612
                for pos from 0 <= pos < len(parents):
 
613
                    if PyTuple_CheckExact(parents):
 
614
                        parent_node = _get_tuple_node(parents, pos)
 
615
                    else:
 
616
                        parent_node = _get_list_node(parents, pos)
 
617
                    # TODO: GraphCycle detection
 
618
                    parent_node.seen = parent_node.seen + 1
 
619
                    if (parent_node.seen
 
620
                        == PyList_GET_SIZE(parent_node.children)):
 
621
                        # All children have been processed, queue up this
 
622
                        # parent
 
623
                        last_item = last_item + 1
 
624
                        if last_item < PyList_GET_SIZE(pending):
 
625
                            Py_INCREF(parent_node) # SetItem steals a ref
 
626
                            PyList_SetItem(pending, last_item, parent_node)
 
627
                        else:
 
628
                            PyList_Append(pending, parent_node)
 
629
                        parent_node.seen = 0
 
630
        return result
 
631
 
 
632
    def merge_sort(self, tip_key):
 
633
        """Compute the merge sorted graph output."""
 
634
        cdef _MergeSorter sorter
 
635
 
 
636
        # TODO: consider disabling gc since we are allocating a lot of nodes
 
637
        #       that won't be collectable anyway. real world testing has not
 
638
        #       shown a specific impact, yet.
 
639
        sorter = _MergeSorter(self, tip_key)
 
640
        return sorter.topo_order()
 
641
    
 
642
    def get_parent_keys(self, key):
 
643
        """Get the parents for a key
 
644
        
 
645
        Returns a list containg the parents keys. If the key is a ghost,
 
646
        None is returned. A KeyError will be raised if the key is not in
 
647
        the graph.
 
648
        
 
649
        :param keys: Key to check (eg revision_id)
 
650
        :return: A list of parents
 
651
        """
 
652
        return self._nodes[key].parent_keys 
 
653
 
 
654
    def get_child_keys(self, key):
 
655
        """Get the children for a key
 
656
        
 
657
        Returns a list containg the children keys. A KeyError will be raised
 
658
        if the key is not in the graph.
 
659
        
 
660
        :param keys: Key to check (eg revision_id)
 
661
        :return: A list of children
 
662
        """
 
663
        return self._nodes[key].child_keys    
 
664
 
 
665
 
 
666
cdef class _MergeSortNode:
 
667
    """Tracks information about a node during the merge_sort operation."""
 
668
 
 
669
    # Public api
 
670
    cdef public object key
 
671
    cdef public long merge_depth
 
672
    cdef public object end_of_merge # True/False Is this the end of the current merge
 
673
 
 
674
    # Private api, used while computing the information
 
675
    cdef _KnownGraphNode left_parent
 
676
    cdef _KnownGraphNode left_pending_parent
 
677
    cdef object pending_parents # list of _KnownGraphNode for non-left parents
 
678
    cdef long _revno_first
 
679
    cdef long _revno_second
 
680
    cdef long _revno_last
 
681
    # TODO: turn these into flag/bit fields rather than individual members
 
682
    cdef int is_first_child # Is this the first child?
 
683
    cdef int seen_by_child # A child node has seen this parent
 
684
    cdef int completed # Fully Processed
 
685
 
 
686
    def __init__(self, key):
 
687
        self.key = key
 
688
        self.merge_depth = -1
 
689
        self.left_parent = None
 
690
        self.left_pending_parent = None
 
691
        self.pending_parents = None
 
692
        self._revno_first = -1
 
693
        self._revno_second = -1
 
694
        self._revno_last = -1
 
695
        self.is_first_child = 0
 
696
        self.seen_by_child = 0
 
697
        self.completed = 0
 
698
 
 
699
    def __repr__(self):
 
700
        return '%s(%s depth:%s rev:%s,%s,%s first:%s seen:%s)' % (
 
701
            self.__class__.__name__, self.key,
 
702
            self.merge_depth,
 
703
            self._revno_first, self._revno_second, self._revno_last,
 
704
            self.is_first_child, self.seen_by_child)
 
705
 
 
706
    cdef int has_pending_parents(self): # cannot_raise
 
707
        if self.left_pending_parent is not None or self.pending_parents:
 
708
            return 1
 
709
        return 0
 
710
 
 
711
    cdef object _revno(self):
 
712
        if self._revno_first == -1:
 
713
            if self._revno_second != -1:
 
714
                raise RuntimeError('Something wrong with: %s' % (self,))
 
715
            return (self._revno_last,)
 
716
        else:
 
717
            return (self._revno_first, self._revno_second, self._revno_last)
 
718
 
 
719
    property revno:
 
720
        def __get__(self):
 
721
            return self._revno()
 
722
 
 
723
 
 
724
cdef class _MergeSorter:
 
725
    """This class does the work of computing the merge_sort ordering.
 
726
 
 
727
    We have some small advantages, in that we get all the extra information
 
728
    that KnownGraph knows, like knowing the child lists, etc.
 
729
    """
 
730
 
 
731
    # Current performance numbers for merge_sort(bzr_dev_parent_map):
 
732
    #  302ms tsort.merge_sort()
 
733
    #   91ms graph.KnownGraph().merge_sort()
 
734
    #   40ms kg.merge_sort()
 
735
 
 
736
    cdef KnownGraph graph
 
737
    cdef object _depth_first_stack  # list
 
738
    cdef Py_ssize_t _last_stack_item # offset to last item on stack
 
739
    # cdef object _ms_nodes # dict of key => _MergeSortNode
 
740
    cdef object _revno_to_branch_count # {revno => num child branches}
 
741
    cdef object _scheduled_nodes # List of nodes ready to be yielded
 
742
 
 
743
    def __init__(self, known_graph, tip_key):
 
744
        cdef _KnownGraphNode node
 
745
 
 
746
        self.graph = known_graph
 
747
        # self._ms_nodes = {}
 
748
        self._revno_to_branch_count = {}
 
749
        self._depth_first_stack = []
 
750
        self._last_stack_item = -1
 
751
        self._scheduled_nodes = []
 
752
        if (tip_key is not None and tip_key != NULL_REVISION
 
753
            and tip_key != (NULL_REVISION,)):
 
754
            node = self.graph._nodes[tip_key]
 
755
            self._push_node(node, 0)
 
756
 
 
757
    cdef _MergeSortNode _get_ms_node(self, _KnownGraphNode node):
 
758
        cdef PyObject *temp_node
 
759
        cdef _MergeSortNode ms_node
 
760
 
 
761
        if node.extra is None:
 
762
            ms_node = _MergeSortNode(node.key)
 
763
            node.extra = ms_node
 
764
        else:
 
765
            ms_node = <_MergeSortNode>node.extra
 
766
        return ms_node
 
767
 
 
768
    cdef _push_node(self, _KnownGraphNode node, long merge_depth):
 
769
        cdef _KnownGraphNode parent_node
 
770
        cdef _MergeSortNode ms_node, ms_parent_node
 
771
        cdef Py_ssize_t pos
 
772
 
 
773
        ms_node = self._get_ms_node(node)
 
774
        ms_node.merge_depth = merge_depth
 
775
        if node.parents is None:
 
776
            raise RuntimeError('ghost nodes should not be pushed'
 
777
                               ' onto the stack: %s' % (node,))
 
778
        if PyTuple_GET_SIZE(node.parents) > 0:
 
779
            parent_node = _get_tuple_node(node.parents, 0)
 
780
            ms_node.left_parent = parent_node
 
781
            if parent_node.parents is None: # left-hand ghost
 
782
                ms_node.left_pending_parent = None
 
783
                ms_node.left_parent = None
 
784
            else:
 
785
                ms_node.left_pending_parent = parent_node
 
786
        if PyTuple_GET_SIZE(node.parents) > 1:
 
787
            ms_node.pending_parents = []
 
788
            for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
 
789
                parent_node = _get_tuple_node(node.parents, pos)
 
790
                if parent_node.parents is None: # ghost
 
791
                    continue
 
792
                PyList_Append(ms_node.pending_parents, parent_node)
 
793
 
 
794
        ms_node.is_first_child = 1
 
795
        if ms_node.left_parent is not None:
 
796
            ms_parent_node = self._get_ms_node(ms_node.left_parent)
 
797
            if ms_parent_node.seen_by_child:
 
798
                ms_node.is_first_child = 0
 
799
            ms_parent_node.seen_by_child = 1
 
800
        self._last_stack_item = self._last_stack_item + 1
 
801
        if self._last_stack_item < PyList_GET_SIZE(self._depth_first_stack):
 
802
            Py_INCREF(node) # SetItem steals a ref
 
803
            PyList_SetItem(self._depth_first_stack, self._last_stack_item,
 
804
                           node)
 
805
        else:
 
806
            PyList_Append(self._depth_first_stack, node)
 
807
 
 
808
    cdef _pop_node(self):
 
809
        cdef PyObject *temp
 
810
        cdef _MergeSortNode ms_node, ms_parent_node, ms_prev_node
 
811
        cdef _KnownGraphNode node, parent_node, prev_node
 
812
 
 
813
        node = _get_list_node(self._depth_first_stack, self._last_stack_item)
 
814
        ms_node = <_MergeSortNode>node.extra
 
815
        self._last_stack_item = self._last_stack_item - 1
 
816
        if ms_node.left_parent is not None:
 
817
            # Assign the revision number from the left-hand parent
 
818
            ms_parent_node = <_MergeSortNode>ms_node.left_parent.extra
 
819
            if ms_node.is_first_child:
 
820
                # First child just increments the final digit
 
821
                ms_node._revno_first = ms_parent_node._revno_first
 
822
                ms_node._revno_second = ms_parent_node._revno_second
 
823
                ms_node._revno_last = ms_parent_node._revno_last + 1
 
824
            else:
 
825
                # Not the first child, make a new branch
 
826
                #  (mainline_revno, branch_count, 1)
 
827
                if ms_parent_node._revno_first == -1:
 
828
                    # Mainline ancestor, the increment is on the last digit
 
829
                    base_revno = ms_parent_node._revno_last
 
830
                else:
 
831
                    base_revno = ms_parent_node._revno_first
 
832
                temp = PyDict_GetItem(self._revno_to_branch_count,
 
833
                                      base_revno)
 
834
                if temp == NULL:
 
835
                    branch_count = 1
 
836
                else:
 
837
                    branch_count = (<object>temp) + 1
 
838
                PyDict_SetItem(self._revno_to_branch_count, base_revno,
 
839
                               branch_count)
 
840
                ms_node._revno_first = base_revno
 
841
                ms_node._revno_second = branch_count
 
842
                ms_node._revno_last = 1
 
843
        else:
 
844
            temp = PyDict_GetItem(self._revno_to_branch_count, 0)
 
845
            if temp == NULL:
 
846
                # The first root node doesn't have a 3-digit revno
 
847
                root_count = 0
 
848
                ms_node._revno_first = -1
 
849
                ms_node._revno_second = -1
 
850
                ms_node._revno_last = 1
 
851
            else:
 
852
                root_count = (<object>temp) + 1
 
853
                ms_node._revno_first = 0
 
854
                ms_node._revno_second = root_count
 
855
                ms_node._revno_last = 1
 
856
            PyDict_SetItem(self._revno_to_branch_count, 0, root_count)
 
857
        ms_node.completed = 1
 
858
        if PyList_GET_SIZE(self._scheduled_nodes) == 0:
 
859
            # The first scheduled node is always the end of merge
 
860
            ms_node.end_of_merge = True
 
861
        else:
 
862
            prev_node = _get_list_node(self._scheduled_nodes,
 
863
                                    PyList_GET_SIZE(self._scheduled_nodes) - 1)
 
864
            ms_prev_node = <_MergeSortNode>prev_node.extra
 
865
            if ms_prev_node.merge_depth < ms_node.merge_depth:
 
866
                # The previously pushed node is to our left, so this is the end
 
867
                # of this right-hand chain
 
868
                ms_node.end_of_merge = True
 
869
            elif (ms_prev_node.merge_depth == ms_node.merge_depth
 
870
                  and prev_node not in node.parents):
 
871
                # The next node is not a direct parent of this node
 
872
                ms_node.end_of_merge = True
 
873
            else:
 
874
                ms_node.end_of_merge = False
 
875
        PyList_Append(self._scheduled_nodes, node)
 
876
 
 
877
    cdef _schedule_stack(self):
 
878
        cdef _KnownGraphNode last_node, next_node
 
879
        cdef _MergeSortNode ms_node, ms_last_node, ms_next_node
 
880
        cdef long next_merge_depth
 
881
        ordered = []
 
882
        while self._last_stack_item >= 0:
 
883
            # Peek at the last item on the stack
 
884
            last_node = _get_list_node(self._depth_first_stack,
 
885
                                       self._last_stack_item)
 
886
            if last_node.gdfo == -1:
 
887
                # if _find_gdfo skipped a node, that means there is a graph
 
888
                # cycle, error out now
 
889
                raise errors.GraphCycleError(self.graph._nodes)
 
890
            ms_last_node = <_MergeSortNode>last_node.extra
 
891
            if not ms_last_node.has_pending_parents():
 
892
                # Processed all parents, pop this node
 
893
                self._pop_node()
 
894
                continue
 
895
            while ms_last_node.has_pending_parents():
 
896
                if ms_last_node.left_pending_parent is not None:
 
897
                    # recurse depth first into the primary parent
 
898
                    next_node = ms_last_node.left_pending_parent
 
899
                    ms_last_node.left_pending_parent = None
 
900
                else:
 
901
                    # place any merges in right-to-left order for scheduling
 
902
                    # which gives us left-to-right order after we reverse
 
903
                    # the scheduled queue.
 
904
                    # Note: This has the effect of allocating common-new
 
905
                    #       revisions to the right-most subtree rather than the
 
906
                    #       left most, which will display nicely (you get
 
907
                    #       smaller trees at the top of the combined merge).
 
908
                    next_node = ms_last_node.pending_parents.pop()
 
909
                ms_next_node = self._get_ms_node(next_node)
 
910
                if ms_next_node.completed:
 
911
                    # this parent was completed by a child on the
 
912
                    # call stack. skip it.
 
913
                    continue
 
914
                # otherwise transfer it from the source graph into the
 
915
                # top of the current depth first search stack.
 
916
 
 
917
                if next_node is ms_last_node.left_parent:
 
918
                    next_merge_depth = ms_last_node.merge_depth
 
919
                else:
 
920
                    next_merge_depth = ms_last_node.merge_depth + 1
 
921
                self._push_node(next_node, next_merge_depth)
 
922
                # and do not continue processing parents until this 'call'
 
923
                # has recursed.
 
924
                break
 
925
 
 
926
    cdef topo_order(self):
 
927
        cdef _MergeSortNode ms_node
 
928
        cdef _KnownGraphNode node
 
929
        cdef Py_ssize_t pos
 
930
        cdef PyObject *temp_key, *temp_node
 
931
 
 
932
        # Note: allocating a _MergeSortNode and deallocating it for all nodes
 
933
        #       costs approx 8.52ms (21%) of the total runtime
 
934
        #       We might consider moving the attributes into the base
 
935
        #       KnownGraph object.
 
936
        self._schedule_stack()
 
937
 
 
938
        # We've set up the basic schedule, now we can continue processing the
 
939
        # output.
 
940
        # Note: This final loop costs us 40.0ms => 28.8ms (11ms, 25%) on
 
941
        #       bzr.dev, to convert the internal Object representation into a
 
942
        #       Tuple representation...
 
943
        #       2ms is walking the data and computing revno tuples
 
944
        #       7ms is computing the return tuple
 
945
        #       4ms is PyList_Append()
 
946
        ordered = []
 
947
        # output the result in reverse order, and separate the generated info
 
948
        for pos from PyList_GET_SIZE(self._scheduled_nodes) > pos >= 0:
 
949
            node = _get_list_node(self._scheduled_nodes, pos)
 
950
            ms_node = <_MergeSortNode>node.extra
 
951
            PyList_Append(ordered, ms_node)
 
952
            node.extra = None
 
953
        # Clear out the scheduled nodes now that we're done
 
954
        self._scheduled_nodes = []
 
955
        return ordered