/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: John Arbash Meinel
  • Date: 2009-06-12 18:05:15 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090612180515-t0cwbjsnve094oik
Add a failing test for handling nodes that are in the same linear chain.

It fails because the ancestry skipping causes us to miss the fact that the two nodes
are actually directly related. We could check at the beginning, as the 
code used to do, but I think that will be incomplete for the more-than-two
heads cases.

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