← 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: Aaron Bentley
  • Date: 2009-06-19 21:16:31 UTC
  • mto: This revision was merged to the branch mainline in revision 4481.
  • Revision ID: aaron@aaronbentley.com-20090619211631-4fnkv2uui98xj7ux
Provide control over switch and shelver messaging.

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)
34
29
    object PyTuple_New(Py_ssize_t n)
 
30
    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
 
31
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
35
32
    Py_ssize_t PyTuple_GET_SIZE(object t)
36
 
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
37
 
    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
38
 
 
39
 
    int PyList_CheckExact(object)
 
33
    PyObject * PyDict_GetItem(object d, object k)
 
34
    Py_ssize_t PyDict_Size(object d) except -1
 
35
    int PyDict_CheckExact(object d)
 
36
    int PyDict_Next(object d, Py_ssize_t *pos, PyObject **k, PyObject **v)
 
37
    int PyList_Append(object l, object v) except -1
 
38
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
40
39
    Py_ssize_t PyList_GET_SIZE(object l)
41
 
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
42
 
    int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
43
 
    int PyList_Append(object l, object v) except -1
44
 
 
45
 
    int PyDict_CheckExact(object d)
46
 
    Py_ssize_t PyDict_Size(object d) except -1
47
 
    PyObject * PyDict_GetItem(object d, object k)
48
40
    int PyDict_SetItem(object d, object k, object v) except -1
49
 
    int PyDict_DelItem(object d, object k) except -1
50
 
    int PyDict_Next(object d, Py_ssize_t *pos, PyObject **k, PyObject **v)
51
 
 
 
41
    int PySet_Add(object s, object k) except -1
52
42
    void Py_INCREF(object)
53
43
 
54
 
from collections import deque
55
 
import gc
56
 
 
57
 
from bzrlib import errors, revision
58
 
 
59
 
cdef object NULL_REVISION
60
 
NULL_REVISION = revision.NULL_REVISION
 
44
 
 
45
import heapq
 
46
 
 
47
from bzrlib import revision
 
48
 
 
49
# Define these as cdef objects, so we don't have to getattr them later
 
50
cdef object heappush, heappop, heapify, heapreplace
 
51
heappush = heapq.heappush
 
52
heappop = heapq.heappop
 
53
heapify = heapq.heapify
 
54
heapreplace = heapq.heapreplace
61
55
 
62
56
 
63
57
cdef class _KnownGraphNode:
66
60
    cdef object key
67
61
    cdef object parents
68
62
    cdef object children
69
 
    cdef public long gdfo
70
 
    cdef int seen
71
 
    cdef object extra
 
63
    cdef _KnownGraphNode linear_dominator_node
 
64
    cdef public object gdfo # Int
 
65
    # This could also be simplified
 
66
    cdef object ancestor_of
72
67
 
73
68
    def __init__(self, key):
 
69
        cdef int i
 
70
 
74
71
        self.key = key
75
72
        self.parents = None
76
73
 
77
74
        self.children = []
 
75
        # oldest ancestor, such that no parents between here and there have >1
 
76
        # child or >1 parent.
 
77
        self.linear_dominator_node = None
78
78
        # Greatest distance from origin
79
79
        self.gdfo = -1
80
 
        self.seen = 0
81
 
        self.extra = None
 
80
        # This will become a tuple of known heads that have this node as an
 
81
        # ancestor
 
82
        self.ancestor_of = None
82
83
 
83
84
    property child_keys:
84
85
        def __get__(self):
89
90
                PyList_Append(keys, child.key)
90
91
            return keys
91
92
 
92
 
    property parent_keys:
 
93
    property linear_dominator:
93
94
        def __get__(self):
94
 
            if self.parents is None:
 
95
            if self.linear_dominator_node is None:
95
96
                return None
96
 
            
97
 
            cdef _KnownGraphNode parent
 
97
            else:
 
98
                return self.linear_dominator_node.key
98
99
 
99
 
            keys = []
100
 
            for parent in self.parents:
101
 
                PyList_Append(keys, parent.key)
102
 
            return keys
103
 
    
104
100
    cdef clear_references(self):
105
101
        self.parents = None
106
102
        self.children = None
 
103
        self.linear_dominator_node = None
107
104
 
108
105
    def __repr__(self):
109
106
        cdef _KnownGraphNode node
116
113
        if self.children is not None:
117
114
            for node in self.children:
118
115
                child_keys.append(node.key)
119
 
        return '%s(%s  gdfo:%s par:%s child:%s)' % (
 
116
        return '%s(%s  gdfo:%s par:%s child:%s %s)' % (
120
117
            self.__class__.__name__, self.key, self.gdfo,
121
 
            parent_keys, child_keys)
 
118
            parent_keys, child_keys,
 
119
            self.linear_dominator)
122
120
 
123
121
 
124
122
cdef _KnownGraphNode _get_list_node(lst, Py_ssize_t pos):
128
126
    return <_KnownGraphNode>temp_node
129
127
 
130
128
 
131
 
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
 
129
cdef _KnownGraphNode _get_parent(parents, Py_ssize_t pos):
132
130
    cdef PyObject *temp_node
 
131
    cdef _KnownGraphNode node
133
132
 
134
 
    temp_node = PyTuple_GET_ITEM(tpl, pos)
 
133
    temp_node = PyTuple_GET_ITEM(parents, pos)
135
134
    return <_KnownGraphNode>temp_node
136
135
 
137
136
 
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
 
137
cdef _KnownGraphNode _peek_node(queue):
 
138
    cdef PyObject *temp_node
 
139
    cdef _KnownGraphNode node
 
140
 
 
141
    temp_node = PyTuple_GET_ITEM(<object>PyList_GET_ITEM(queue, 0), 1)
 
142
    node = <_KnownGraphNode>temp_node
 
143
    return node
 
144
 
 
145
# TODO: slab allocate all _KnownGraphNode objects.
 
146
#       We already know how many we are going to need, except for a couple of
 
147
#       ghosts that could be allocated on demand.
191
148
 
192
149
cdef class KnownGraph:
193
150
    """This is a class which assumes we already know the full graph."""
194
151
 
195
152
    cdef public object _nodes
196
 
    cdef public object _known_heads
 
153
    cdef object _known_heads
197
154
    cdef public int do_cache
 
155
    # Nodes we've touched that we'll need to reset their info when heads() is
 
156
    # done
 
157
    cdef object _to_cleanup
198
158
 
199
159
    def __init__(self, parent_map, do_cache=True):
200
160
        """Create a new KnownGraph instance.
201
161
 
202
162
        :param parent_map: A dictionary mapping key => parent_keys
203
163
        """
204
 
        # tests at pre-allocating the node dict actually slowed things down
205
164
        self._nodes = {}
206
165
        # Maps {sorted(revision_id, revision_id): heads}
207
166
        self._known_heads = {}
 
167
        self._to_cleanup = []
208
168
        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
169
        self._initialize_nodes(parent_map)
 
170
        self._find_linear_dominators()
213
171
        self._find_gdfo()
214
172
 
215
173
    def __dealloc__(self):
233
191
            node = <_KnownGraphNode>temp_node
234
192
        return node
235
193
 
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
194
    def _initialize_nodes(self, parent_map):
259
195
        """Populate self._nodes.
260
196
 
261
 
        After this has finished:
262
 
        - self._nodes will have an entry for every entry in parent_map.
263
 
        - ghosts will have a parent_keys = None,
264
 
        - all nodes found will also have child_keys populated with all known
265
 
          child keys,
 
197
        After this has finished, self._nodes will have an entry for every entry
 
198
        in parent_map. Ghosts will have a parent_keys = None, all nodes found
 
199
        will also have .child_keys populated with all known child_keys.
266
200
        """
267
201
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
268
 
        cdef Py_ssize_t pos
 
202
        cdef Py_ssize_t pos, pos2, num_parent_keys
269
203
        cdef _KnownGraphNode node
270
204
        cdef _KnownGraphNode parent_node
271
205
 
 
206
        nodes = self._nodes
 
207
 
272
208
        if not PyDict_CheckExact(parent_map):
273
209
            raise TypeError('parent_map should be a dict of {key:parent_keys}')
274
210
        # for key, parent_keys in parent_map.iteritems():
277
213
            key = <object>temp_key
278
214
            parent_keys = <object>temp_parent_keys
279
215
            node = self._get_or_create_node(key)
280
 
            self._populate_parents(node, parent_keys)
281
 
 
282
 
    def _find_tails(self):
283
 
        cdef PyObject *temp_node
284
 
        cdef _KnownGraphNode node
285
 
        cdef Py_ssize_t pos
 
216
            # We know how many parents, so we could pre allocate an exact sized
 
217
            # tuple here
 
218
            num_parent_keys = len(parent_keys)
 
219
            parent_nodes = PyTuple_New(num_parent_keys)
 
220
            # We use iter here, because parent_keys maybe be a list or tuple
 
221
            for pos2 from 0 <= pos2 < num_parent_keys:
 
222
                parent_key = parent_keys[pos2]
 
223
                parent_node = self._get_or_create_node(parent_keys[pos2])
 
224
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
 
225
                Py_INCREF(parent_node)
 
226
                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
 
227
                PyList_Append(parent_node.children, node)
 
228
            node.parents = parent_nodes
 
229
 
 
230
    cdef _KnownGraphNode _check_is_linear(self, _KnownGraphNode node):
 
231
        """Check to see if a given node is part of a linear chain."""
 
232
        cdef _KnownGraphNode parent_node
 
233
        if node.parents is None or PyTuple_GET_SIZE(node.parents) != 1:
 
234
            # This node is either a ghost, a tail, or has multiple parents
 
235
            # It its own dominator
 
236
            node.linear_dominator_node = node
 
237
            return None
 
238
        parent_node = _get_parent(node.parents, 0)
 
239
        if PyList_GET_SIZE(parent_node.children) > 1:
 
240
            # The parent has multiple children, so *this* node is the
 
241
            # dominator
 
242
            node.linear_dominator_node = node
 
243
            return None
 
244
        # The parent is already filled in, so add and continue
 
245
        if parent_node.linear_dominator_node is not None:
 
246
            node.linear_dominator_node = parent_node.linear_dominator_node
 
247
            return None
 
248
        # We don't know this node, or its parent node, so start walking to
 
249
        # next
 
250
        return parent_node
 
251
 
 
252
    def _find_linear_dominators(self):
 
253
        """
 
254
        For any given node, the 'linear dominator' is an ancestor, such that
 
255
        all parents between this node and that one have a single parent, and a
 
256
        single child. So if A->B->C->D then B,C,D all have a linear dominator
 
257
        of A.
 
258
 
 
259
        There are two main benefits:
 
260
        1) When walking the graph, we can jump to the nearest linear dominator,
 
261
           rather than walking all of the nodes inbetween.
 
262
        2) When caching heads() results, dominators give the "same" results as
 
263
           their children. (If the dominator is a head, then the descendant is
 
264
           a head, if the dominator is not a head, then the child isn't
 
265
           either.)
 
266
        """
 
267
        cdef PyObject *temp_node
 
268
        cdef Py_ssize_t pos
 
269
        cdef _KnownGraphNode node
 
270
        cdef _KnownGraphNode next_node
 
271
        cdef _KnownGraphNode dominator
 
272
        cdef int i, num_elements
 
273
 
 
274
        pos = 0
 
275
        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
 
276
            node = <_KnownGraphNode>temp_node
 
277
            # The parent is not filled in, so walk until we get somewhere
 
278
            if node.linear_dominator_node is not None: #already done
 
279
                continue
 
280
            next_node = self._check_is_linear(node)
 
281
            if next_node is None:
 
282
                # Nothing more needs to be done
 
283
                continue
 
284
            stack = []
 
285
            while next_node is not None:
 
286
                PyList_Append(stack, node)
 
287
                node = next_node
 
288
                next_node = self._check_is_linear(node)
 
289
            # The stack now contains the linear chain, and 'node' should have
 
290
            # been labeled
 
291
            dominator = node.linear_dominator_node
 
292
            num_elements = len(stack)
 
293
            for i from num_elements > i >= 0:
 
294
                next_node = _get_list_node(stack, i)
 
295
                next_node.linear_dominator_node = dominator
 
296
                node = next_node
 
297
 
 
298
    cdef object _find_tails(self):
 
299
        cdef object tails
 
300
        cdef PyObject *temp_node
 
301
        cdef Py_ssize_t pos
 
302
        cdef _KnownGraphNode node
286
303
 
287
304
        tails = []
288
305
        pos = 0
289
306
        while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
290
307
            node = <_KnownGraphNode>temp_node
291
308
            if node.parents is None or PyTuple_GET_SIZE(node.parents) == 0:
292
 
                node.gdfo = 1
293
309
                PyList_Append(tails, node)
294
310
        return tails
295
311
 
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
312
    def _find_gdfo(self):
 
313
        cdef Py_ssize_t pos, pos2
310
314
        cdef _KnownGraphNode node
311
 
        cdef _KnownGraphNode child
312
 
        cdef PyObject *temp
313
 
        cdef Py_ssize_t pos
314
 
        cdef int replace
315
 
        cdef Py_ssize_t last_item
316
 
        cdef long next_gdfo
317
 
 
318
 
        pending = self._find_tails()
319
 
 
320
 
        last_item = PyList_GET_SIZE(pending) - 1
321
 
        while last_item >= 0:
322
 
            # Avoid pop followed by push, instead, peek, and replace
323
 
            # timing shows this is 930ms => 770ms for OOo
324
 
            node = _get_list_node(pending, last_item)
325
 
            last_item = last_item - 1
 
315
        cdef _KnownGraphNode child_node
 
316
        cdef _KnownGraphNode parent_node
 
317
        cdef int replace_node, missing_parent
 
318
 
 
319
        tails = self._find_tails()
 
320
        todo = []
 
321
        for pos from 0 <= pos < PyList_GET_SIZE(tails):
 
322
            node = _get_list_node(tails, pos)
 
323
            node.gdfo = 1
 
324
            PyList_Append(todo, (1, node))
 
325
        # No need to heapify, because all tails have priority=1
 
326
        while PyList_GET_SIZE(todo) > 0:
 
327
            node = _peek_node(todo)
326
328
            next_gdfo = node.gdfo + 1
 
329
            replace_node = 1
327
330
            for pos from 0 <= pos < PyList_GET_SIZE(node.children):
328
 
                child = _get_list_node(node.children, pos)
329
 
                if next_gdfo > child.gdfo:
330
 
                    child.gdfo = next_gdfo
331
 
                child.seen = child.seen + 1
332
 
                if child.seen == PyTuple_GET_SIZE(child.parents):
333
 
                    # This child is populated, queue it to be walked
334
 
                    last_item = last_item + 1
335
 
                    if last_item < PyList_GET_SIZE(pending):
336
 
                        Py_INCREF(child) # SetItem steals a ref
337
 
                        PyList_SetItem(pending, last_item, child)
338
 
                    else:
339
 
                        PyList_Append(pending, child)
340
 
                    # We have queued this node, we don't need to track it
341
 
                    # anymore
342
 
                    child.seen = 0
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
 
331
                child_node = _get_list_node(node.children, pos)
 
332
                # We should never have numbered children before we numbered
 
333
                # a parent
 
334
                if child_node.gdfo != -1:
 
335
                    continue
 
336
                # Only enque children when all of their parents have been
 
337
                # resolved. With a single parent, we can just take 'this' value
 
338
                child_gdfo = next_gdfo
 
339
                if PyTuple_GET_SIZE(child_node.parents) > 1:
 
340
                    missing_parent = 0
 
341
                    for pos2 from 0 <= pos2 < PyTuple_GET_SIZE(child_node.parents):
 
342
                        parent_node = _get_parent(child_node.parents, pos2)
 
343
                        if parent_node.gdfo == -1:
 
344
                            missing_parent = 1
 
345
                            break
 
346
                        if parent_node.gdfo >= child_gdfo:
 
347
                            child_gdfo = parent_node.gdfo + 1
 
348
                    if missing_parent:
 
349
                        # One of the parents is not numbered, so wait until we get
 
350
                        # back here
 
351
                        continue
 
352
                child_node.gdfo = child_gdfo
 
353
                if replace_node:
 
354
                    heapreplace(todo, (child_gdfo, child_node))
 
355
                    replace_node = 0
377
356
                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)
 
357
                    heappush(todo, (child_gdfo, child_node))
 
358
            if replace_node:
 
359
                heappop(todo)
413
360
 
414
361
    def heads(self, keys):
415
362
        """Return the heads from amongst keys.
417
364
        This is done by searching the ancestries of each key.  Any key that is
418
365
        reachable from another key is not returned; all the others are.
419
366
 
420
 
        This operation scales with the relative depth between any two keys. It
421
 
        uses gdfo to avoid walking all ancestry.
 
367
        This operation scales with the relative depth between any two keys. If
 
368
        any two keys are completely disconnected all ancestry of both sides
 
369
        will be retrieved.
422
370
 
423
371
        :param keys: An iterable of keys.
424
372
        :return: A set of the heads. Note that as a set there is no ordering
427
375
        """
428
376
        cdef PyObject *maybe_node
429
377
        cdef PyObject *maybe_heads
430
 
        cdef PyObject *temp_node
431
 
        cdef _KnownGraphNode node
432
 
        cdef Py_ssize_t pos, last_item
433
 
        cdef long min_gdfo
434
378
 
435
 
        heads_key = frozenset(keys)
 
379
        heads_key = PyFrozenSet_New(keys)
436
380
        maybe_heads = PyDict_GetItem(self._known_heads, heads_key)
437
381
        if maybe_heads != NULL:
438
382
            return <object>maybe_heads
 
383
 
439
384
        # Not cached, compute it ourselves
440
385
        candidate_nodes = {}
 
386
        nodes = self._nodes
441
387
        for key in keys:
442
 
            maybe_node = PyDict_GetItem(self._nodes, key)
 
388
            maybe_node = PyDict_GetItem(nodes, key)
443
389
            if maybe_node == NULL:
444
390
                raise KeyError('key %s not in nodes' % (key,))
445
391
            PyDict_SetItem(candidate_nodes, key, <object>maybe_node)
446
 
        maybe_node = PyDict_GetItem(candidate_nodes, NULL_REVISION)
447
 
        if maybe_node != NULL:
 
392
        if revision.NULL_REVISION in candidate_nodes:
448
393
            # NULL_REVISION is only a head if it is the only entry
449
 
            candidate_nodes.pop(NULL_REVISION)
 
394
            candidate_nodes.pop(revision.NULL_REVISION)
450
395
            if not candidate_nodes:
451
 
                return frozenset([NULL_REVISION])
 
396
                return set([revision.NULL_REVISION])
452
397
            # The keys changed, so recalculate heads_key
453
 
            heads_key = frozenset(candidate_nodes)
 
398
            heads_key = PyFrozenSet_New(candidate_nodes)
 
399
        if len(candidate_nodes) < 2:
 
400
            return heads_key
 
401
        dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
454
402
        if PyDict_Size(candidate_nodes) < 2:
455
 
            return heads_key
456
 
 
457
 
        cleanup = []
458
 
        pending = []
459
 
        # we know a gdfo cannot be longer than a linear chain of all nodes
460
 
        min_gdfo = PyDict_Size(self._nodes) + 1
461
 
        # Build up nodes that need to be walked, note that starting nodes are
462
 
        # not added to seen()
463
 
        pos = 0
464
 
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
465
 
            node = <_KnownGraphNode>temp_node
466
 
            if node.parents is not None:
467
 
                pending.extend(node.parents)
468
 
            if node.gdfo < min_gdfo:
469
 
                min_gdfo = node.gdfo
470
 
 
471
 
        # Now do all the real work
472
 
        last_item = PyList_GET_SIZE(pending) - 1
473
 
        while last_item >= 0:
474
 
            node = _get_list_node(pending, last_item)
475
 
            last_item = last_item - 1
476
 
            if node.seen:
477
 
                # node already appears in some ancestry
478
 
                continue
479
 
            PyList_Append(cleanup, node)
480
 
            node.seen = 1
481
 
            if node.gdfo <= min_gdfo:
482
 
                continue
483
 
            if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
484
 
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
485
 
                    parent_node = _get_tuple_node(node.parents, pos)
486
 
                    last_item = last_item + 1
487
 
                    if last_item < PyList_GET_SIZE(pending):
488
 
                        Py_INCREF(parent_node) # SetItem steals a ref
489
 
                        PyList_SetItem(pending, last_item, parent_node)
490
 
                    else:
491
 
                        PyList_Append(pending, parent_node)
492
 
        heads = []
493
 
        pos = 0
494
 
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
495
 
            node = <_KnownGraphNode>temp_node
496
 
            if not node.seen:
497
 
                PyList_Append(heads, node.key)
498
 
        heads = frozenset(heads)
499
 
        for pos from 0 <= pos < PyList_GET_SIZE(cleanup):
500
 
            node = _get_list_node(cleanup, pos)
501
 
            node.seen = 0
 
403
            return frozenset(candidate_nodes)
 
404
        dom_lookup_key, heads = self._heads_from_dominators(candidate_nodes,
 
405
                                                            dom_to_node)
 
406
        if heads is not None:
 
407
            if self.do_cache:
 
408
                # This heads was not in the cache, or it would have been caught
 
409
                # earlier, but the dom head *was*, so do the simple cache
 
410
                PyDict_SetItem(self._known_heads, heads_key, heads)
 
411
            return heads
 
412
        heads = self._heads_from_candidate_nodes(candidate_nodes, dom_to_node)
502
413
        if self.do_cache:
503
 
            PyDict_SetItem(self._known_heads, heads_key, heads)
 
414
            self._cache_heads(heads, heads_key, dom_lookup_key, candidate_nodes)
504
415
        return heads
505
416
 
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
 
417
    cdef object _cache_heads(self, heads, heads_key, dom_lookup_key,
 
418
                             candidate_nodes):
 
419
        cdef PyObject *maybe_node
 
420
        cdef _KnownGraphNode node
 
421
 
 
422
        PyDict_SetItem(self._known_heads, heads_key, heads)
 
423
        dom_heads = []
 
424
        for key in heads:
 
425
            maybe_node = PyDict_GetItem(candidate_nodes, key)
 
426
            if maybe_node == NULL:
 
427
                raise KeyError
 
428
            node = <_KnownGraphNode>maybe_node
 
429
            PyList_Append(dom_heads, node.linear_dominator_node.key)
 
430
        PyDict_SetItem(self._known_heads, dom_lookup_key,
 
431
                       PyFrozenSet_New(dom_heads))
 
432
 
 
433
    cdef _get_dominators_to_nodes(self, candidate_nodes):
 
434
        """Get the reverse mapping from dominator_key => candidate_nodes.
 
435
 
 
436
        As a side effect, this can also remove potential candidate nodes if we
 
437
        determine that they share a dominator.
 
438
        """
 
439
        cdef Py_ssize_t pos
 
440
        cdef _KnownGraphNode node, other_node
 
441
        cdef PyObject *temp_node
 
442
        cdef PyObject *maybe_node
 
443
 
 
444
        dom_to_node = {}
 
445
        keys_to_remove = []
 
446
        pos = 0
 
447
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
 
448
            node = <_KnownGraphNode>temp_node
 
449
            dom_key = node.linear_dominator_node.key
 
450
            maybe_node = PyDict_GetItem(dom_to_node, dom_key)
 
451
            if maybe_node == NULL:
 
452
                PyDict_SetItem(dom_to_node, dom_key, node)
 
453
            else:
 
454
                other_node = <_KnownGraphNode>maybe_node
 
455
                # These nodes share a dominator, one of them obviously
 
456
                # supersedes the other, figure out which
 
457
                if other_node.gdfo > node.gdfo:
 
458
                    PyList_Append(keys_to_remove, node.key)
 
459
                else:
 
460
                    # This wins, replace the other
 
461
                    PyList_Append(keys_to_remove, other_node.key)
 
462
                    PyDict_SetItem(dom_to_node, dom_key, node)
 
463
        for pos from 0 <= pos < PyList_GET_SIZE(keys_to_remove):
 
464
            key = <object>PyList_GET_ITEM(keys_to_remove, pos)
 
465
            candidate_nodes.pop(key)
 
466
        return dom_to_node
 
467
 
 
468
    cdef object _heads_from_dominators(self, candidate_nodes, dom_to_node):
 
469
        cdef PyObject *maybe_heads
 
470
        cdef PyObject *maybe_node
 
471
        cdef _KnownGraphNode node
 
472
        cdef Py_ssize_t pos
 
473
        cdef PyObject *temp_node
 
474
 
 
475
        dom_list_key = []
 
476
        pos = 0
 
477
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
 
478
            node = <_KnownGraphNode>temp_node
 
479
            PyList_Append(dom_list_key, node.linear_dominator_node.key)
 
480
        dom_lookup_key = PyFrozenSet_New(dom_list_key)
 
481
        maybe_heads = PyDict_GetItem(self._known_heads, dom_lookup_key)
 
482
        if maybe_heads == NULL:
 
483
            return dom_lookup_key, None
 
484
        # We need to map back from the dominator head to the original keys
 
485
        dom_heads = <object>maybe_heads
 
486
        heads = []
 
487
        for dom_key in dom_heads:
 
488
            maybe_node = PyDict_GetItem(dom_to_node, dom_key)
 
489
            if maybe_node == NULL:
 
490
                # Should never happen
 
491
                raise KeyError
 
492
            node = <_KnownGraphNode>maybe_node
 
493
            PyList_Append(heads, node.key)
 
494
        return dom_lookup_key, PyFrozenSet_New(heads)
 
495
 
 
496
    cdef int _process_parent(self, _KnownGraphNode node,
 
497
                             _KnownGraphNode parent_node,
 
498
                             candidate_nodes, dom_to_node,
 
499
                             queue, int *replace_item) except -1:
 
500
        """Process the parent of a node, seeing if we need to walk it."""
 
501
        cdef PyObject *maybe_candidate
 
502
        cdef PyObject *maybe_node
 
503
        cdef _KnownGraphNode dom_child_node
 
504
        maybe_candidate = PyDict_GetItem(candidate_nodes, parent_node.key)
 
505
        if maybe_candidate != NULL:
 
506
            candidate_nodes.pop(parent_node.key)
 
507
            # We could pass up a flag that tells the caller to stop processing,
 
508
            # but it doesn't help much, and makes the code uglier
 
509
            return 0
 
510
        maybe_node = PyDict_GetItem(dom_to_node, parent_node.key)
 
511
        if maybe_node != NULL:
 
512
            # This is a dominator of a node
 
513
            dom_child_node = <_KnownGraphNode>maybe_node
 
514
            if dom_child_node is not node:
 
515
                # It isn't a dominator of a node we are searching, so we should
 
516
                # remove it from the search
 
517
                maybe_candidate = PyDict_GetItem(candidate_nodes, dom_child_node.key)
 
518
                if maybe_candidate != NULL:
 
519
                    candidate_nodes.pop(dom_child_node.key)
 
520
                    return 0
 
521
        if parent_node.ancestor_of is None:
 
522
            # This node hasn't been walked yet, so just project node's ancestor
 
523
            # info directly to parent_node, and enqueue it for later processing
 
524
            parent_node.ancestor_of = node.ancestor_of
 
525
            if replace_item[0]:
 
526
                heapreplace(queue, (-parent_node.gdfo, parent_node))
 
527
                replace_item[0] = 0
 
528
            else:
 
529
                heappush(queue, (-parent_node.gdfo, parent_node))
 
530
            PyList_Append(self._to_cleanup, parent_node)
 
531
        elif parent_node.ancestor_of != node.ancestor_of:
 
532
            # Combine to get the full set of parents
 
533
            # Rewrite using PySet_* functions, unfortunately you have to use
 
534
            # PySet_Add since there is no PySet_Update... :(
 
535
            all_ancestors = set(parent_node.ancestor_of)
 
536
            for k in node.ancestor_of:
 
537
                PySet_Add(all_ancestors, k)
 
538
            parent_node.ancestor_of = tuple(sorted(all_ancestors))
709
539
        return 0
710
540
 
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):
 
541
    cdef object _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
744
542
        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):
 
543
        cdef _KnownGraphNode parent_node
 
544
        cdef Py_ssize_t num_candidates
 
545
        cdef int num_parents, replace_item
 
546
        cdef Py_ssize_t pos
758
547
        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
 
548
 
 
549
        queue = []
 
550
        pos = 0
 
551
        while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
 
552
            node = <_KnownGraphNode>temp_node
 
553
            node.ancestor_of = (node.key,)
 
554
            PyList_Append(queue, (-node.gdfo, node))
 
555
            PyList_Append(self._to_cleanup, node)
 
556
        heapify(queue)
 
557
        # These are nodes that we determined are 'common' that we are no longer
 
558
        # walking
 
559
        # Now we walk nodes until all nodes that are being walked are 'common'
 
560
        num_candidates = len(candidate_nodes)
 
561
        replace_item = 0
 
562
        while PyList_GET_SIZE(queue) > 0 and PyDict_Size(candidate_nodes) > 1:
 
563
            if replace_item:
 
564
                # We still need to pop the smallest member out of the queue
 
565
                # before we peek again
 
566
                heappop(queue)
 
567
                if PyList_GET_SIZE(queue) == 0:
 
568
                    break
 
569
            # peek at the smallest item. We don't pop, because we expect we'll
 
570
            # need to push more things into the queue anyway
 
571
            node = _peek_node(queue)
 
572
            replace_item = 1
 
573
            if PyTuple_GET_SIZE(node.ancestor_of) == num_candidates:
 
574
                # This node is now considered 'common'
 
575
                # Make sure all parent nodes are marked as such
 
576
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
 
577
                    parent_node = _get_parent(node.parents, pos)
 
578
                    if parent_node.ancestor_of is not None:
 
579
                        parent_node.ancestor_of = node.ancestor_of
 
580
                if node.linear_dominator_node is not node:
 
581
                    parent_node = node.linear_dominator_node
 
582
                    if parent_node.ancestor_of is not None:
 
583
                        parent_node.ancestor_of = node.ancestor_of
 
584
                continue
 
585
            if node.parents is None:
 
586
                # This is a ghost
 
587
                continue
 
588
            # Now project the current nodes ancestor list to the parent nodes,
 
589
            # and queue them up to be walked
 
590
            if node.linear_dominator_node is not node:
 
591
                # We are at the tip of a long linear region
 
592
                # We know that there is nothing between here and the tail
 
593
                # that is interesting, so skip to the end
 
594
                self._process_parent(node, node.linear_dominator_node,
 
595
                                     candidate_nodes, dom_to_node, queue, &replace_item)
 
596
            else:
 
597
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
 
598
                    parent_node = _get_parent(node.parents, pos)
 
599
                    self._process_parent(node, parent_node, candidate_nodes,
 
600
                                         dom_to_node, queue, &replace_item)
 
601
        for pos from 0 <= pos < PyList_GET_SIZE(self._to_cleanup):
 
602
            node = _get_list_node(self._to_cleanup, pos)
 
603
            node.ancestor_of = None
 
604
        self._to_cleanup = []
 
605
        return PyFrozenSet_New(candidate_nodes)