/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: Martin Pool
  • Date: 2009-07-27 06:28:35 UTC
  • mto: This revision was merged to the branch mainline in revision 4587.
  • Revision ID: mbp@sourcefrog.net-20090727062835-o66p8it658tq1sma
Add CountedLock.get_physical_lock_status

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