← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: Martin Pool
  • Date: 2009-07-10 06:46:10 UTC
  • mto: (4525.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4526.
  • Revision ID: mbp@sourcefrog.net-20090710064610-sqviksbqp5i34sw2
Rename to per_interrepository

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
1
 
# Copyright (C) 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2009 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
    object PyFrozenSet_New(object)
 
29
 
34
30
    object PyTuple_New(Py_ssize_t n)
35
31
    Py_ssize_t PyTuple_GET_SIZE(object t)
36
32
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
37
33
    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
38
34
 
39
 
    int PyList_CheckExact(object)
40
35
    Py_ssize_t PyList_GET_SIZE(object l)
41
36
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
42
37
    int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
51
46
 
52
47
    void Py_INCREF(object)
53
48
 
54
 
from collections import deque
55
 
import gc
56
49
 
57
 
from bzrlib import errors, revision
 
50
from bzrlib import revision
58
51
 
59
52
cdef object NULL_REVISION
60
53
NULL_REVISION = revision.NULL_REVISION
68
61
    cdef object children
69
62
    cdef public long gdfo
70
63
    cdef int seen
71
 
    cdef object extra
72
64
 
73
65
    def __init__(self, key):
 
66
        cdef int i
 
67
 
74
68
        self.key = key
75
69
        self.parents = None
76
70
 
78
72
        # Greatest distance from origin
79
73
        self.gdfo = -1
80
74
        self.seen = 0
81
 
        self.extra = None
82
75
 
83
76
    property child_keys:
84
77
        def __get__(self):
89
82
                PyList_Append(keys, child.key)
90
83
            return keys
91
84
 
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
 
    
104
85
    cdef clear_references(self):
105
86
        self.parents = None
106
87
        self.children = None
128
109
    return <_KnownGraphNode>temp_node
129
110
 
130
111
 
131
 
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
 
112
cdef _KnownGraphNode _get_parent(parents, Py_ssize_t pos):
132
113
    cdef PyObject *temp_node
 
114
    cdef _KnownGraphNode node
133
115
 
134
 
    temp_node = PyTuple_GET_ITEM(tpl, pos)
 
116
    temp_node = PyTuple_GET_ITEM(parents, pos)
135
117
    return <_KnownGraphNode>temp_node
136
118
 
137
119
 
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
 
120
# TODO: slab allocate all _KnownGraphNode objects.
 
121
#       We already know how many we are going to need, except for a couple of
 
122
#       ghosts that could be allocated on demand.
191
123
 
192
124
cdef class KnownGraph:
193
125
    """This is a class which assumes we already know the full graph."""
194
126
 
195
127
    cdef public object _nodes
196
 
    cdef public object _known_heads
 
128
    cdef object _known_heads
197
129
    cdef public int do_cache
198
130
 
199
131
    def __init__(self, parent_map, do_cache=True):
206
138
        # Maps {sorted(revision_id, revision_id): heads}
207
139
        self._known_heads = {}
208
140
        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.
212
141
        self._initialize_nodes(parent_map)
213
142
        self._find_gdfo()
214
143
 
233
162
            node = <_KnownGraphNode>temp_node
234
163
        return node
235
164
 
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
 
 
258
165
    def _initialize_nodes(self, parent_map):
259
166
        """Populate self._nodes.
260
167
 
265
172
          child keys,
266
173
        """
267
174
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
268
 
        cdef Py_ssize_t pos
 
175
        cdef Py_ssize_t pos, pos2, num_parent_keys
269
176
        cdef _KnownGraphNode node
270
177
        cdef _KnownGraphNode parent_node
271
178
 
276
183
        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
277
184
            key = <object>temp_key
278
185
            parent_keys = <object>temp_parent_keys
 
186
            num_parent_keys = len(parent_keys)
279
187
            node = self._get_or_create_node(key)
280
 
            self._populate_parents(node, parent_keys)
 
188
            # We know how many parents, so we could pre allocate an exact sized
 
189
            # tuple here
 
190
            parent_nodes = PyTuple_New(num_parent_keys)
 
191
            # We use iter here, because parent_keys maybe be a list or tuple
 
192
            for pos2 from 0 <= pos2 < num_parent_keys:
 
193
                parent_node = self._get_or_create_node(parent_keys[pos2])
 
194
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
 
195
                Py_INCREF(parent_node)
 
196
                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
 
197
                PyList_Append(parent_node.children, node)
 
198
            node.parents = parent_nodes
281
199
 
282
200
    def _find_tails(self):
283
201
        cdef PyObject *temp_node
293
211
                PyList_Append(tails, node)
294
212
        return tails
295
213
 
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
 
 
309
214
    def _find_gdfo(self):
310
215
        cdef _KnownGraphNode node
311
216
        cdef _KnownGraphNode child
341
246
                    # anymore
342
247
                    child.seen = 0
343
248
 
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
 
 
414
249
    def heads(self, keys):
415
250
        """Return the heads from amongst keys.
416
251
 
432
267
        cdef Py_ssize_t pos, last_item
433
268
        cdef long min_gdfo
434
269
 
435
 
        heads_key = frozenset(keys)
 
270
        heads_key = PyFrozenSet_New(keys)
436
271
        maybe_heads = PyDict_GetItem(self._known_heads, heads_key)
437
272
        if maybe_heads != NULL:
438
273
            return <object>maybe_heads
450
285
            if not candidate_nodes:
451
286
                return frozenset([NULL_REVISION])
452
287
            # The keys changed, so recalculate heads_key
453
 
            heads_key = frozenset(candidate_nodes)
 
288
            heads_key = PyFrozenSet_New(candidate_nodes)
454
289
        if PyDict_Size(candidate_nodes) < 2:
455
290
            return heads_key
456
291
 
482
317
                continue
483
318
            if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
484
319
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
485
 
                    parent_node = _get_tuple_node(node.parents, pos)
 
320
                    parent_node = _get_parent(node.parents, pos)
486
321
                    last_item = last_item + 1
487
322
                    if last_item < PyList_GET_SIZE(pending):
488
323
                        Py_INCREF(parent_node) # SetItem steals a ref
495
330
            node = <_KnownGraphNode>temp_node
496
331
            if not node.seen:
497
332
                PyList_Append(heads, node.key)
498
 
        heads = frozenset(heads)
 
333
        heads = PyFrozenSet_New(heads)
499
334
        for pos from 0 <= pos < PyList_GET_SIZE(cleanup):
500
335
            node = _get_list_node(cleanup, pos)
501
336
            node.seen = 0
502
337
        if self.do_cache:
503
338
            PyDict_SetItem(self._known_heads, heads_key, heads)
504
339
        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