« back to all changes in this revision
Viewing changes to bzrlib/_known_graph_pyx.pyx
- browse files at revision 4465.1.3
- compare with another revision
- compare with revision 6020
- download diff
- download tarball
- view history from revision 4465.1.3
- Committer: Aaron Bentley
- Date: 2009-06-26 03:44:30 UTC
- mfrom: (4481 +trunk)
- mto: This revision was merged to the branch mainline in revision 4482.
- Revision ID: aaron@aaronbentley.com-20090626034430-5btbqa44ikywccsu
Merge bzr.dev into vpipe
- files renamed:
- bzrlib/_btree_serializer_c.pyx => bzrlib/_btree_serializer_pyx.pyx
- bzrlib/_dirstate_helpers_c.h => bzrlib/_dirstate_helpers_pyx.h
- bzrlib/_dirstate_helpers_c.pyx => bzrlib/_dirstate_helpers_pyx.pyx
- bzrlib/_knit_load_data_c.pyx => bzrlib/_knit_load_data_pyx.pyx
- files modified:
- .bzrignore
added
removed
bzrlib/_known_graph_pyx.pyx
26
26
pass
27
27
28
28
object PyFrozenSet_New(object)
29
29
30
object PyTuple_New(Py_ssize_t n)
31
Py_ssize_t PyTuple_GET_SIZE(object t)
32
PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
30
33
void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
31
PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
32
Py_ssize_t PyTuple_GET_SIZE(object t)
34
35
Py_ssize_t PyList_GET_SIZE(object l)
36
PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
37
int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
38
int PyList_Append(object l, object v) except -1
39
40
int PyDict_CheckExact(object d)
41
Py_ssize_t PyDict_Size(object d) except -1
33
42
PyObject * PyDict_GetItem(object d, object k)
34
Py_ssize_t PyDict_Size(object d) except -1
35
int PyDict_CheckExact(object d)
43
int PyDict_SetItem(object d, object k, object v) except -1
44
int PyDict_DelItem(object d, object k) except -1
36
45
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)
39
Py_ssize_t PyList_GET_SIZE(object l)
40
int PyDict_SetItem(object d, object k, object v) except -1
41
int PySet_Add(object s, object k) except -1
46
42
47
void Py_INCREF(object)
43
48
44
49
45
import heapq
46
47
50
from bzrlib import revision
48
51
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
52
cdef object NULL_REVISION
53
NULL_REVISION = revision.NULL_REVISION
55
54
56
55
57
56
cdef class _KnownGraphNode:
60
59
cdef object key
61
60
cdef object parents
62
61
cdef object children
63
cdef _KnownGraphNode linear_dominator_node
64
cdef public object gdfo # Int
65
# This could also be simplified
66
cdef object ancestor_of
62
cdef public long gdfo
63
cdef int seen
67
64
68
65
def __init__(self, key):
69
66
cdef int i
72
69
self.parents = None
73
70
74
71
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
72
# Greatest distance from origin
79
73
self.gdfo = -1
80
# This will become a tuple of known heads that have this node as an
81
# ancestor
82
self.ancestor_of = None
74
self.seen = 0
83
75
84
76
property child_keys:
85
77
def __get__(self):
90
82
PyList_Append(keys, child.key)
91
83
return keys
92
84
93
property linear_dominator:
94
def __get__(self):
95
if self.linear_dominator_node is None:
96
return None
97
else:
98
return self.linear_dominator_node.key
99
100
85
cdef clear_references(self):
101
86
self.parents = None
102
87
self.children = None
103
self.linear_dominator_node = None
104
88
105
89
def __repr__(self):
106
90
cdef _KnownGraphNode node
113
97
if self.children is not None:
114
98
for node in self.children:
115
99
child_keys.append(node.key)
116
return '%s(%s gdfo:%s par:%s child:%s %s)' % (
100
return '%s(%s gdfo:%s par:%s child:%s)' % (
117
101
self.__class__.__name__, self.key, self.gdfo,
118
parent_keys, child_keys,
119
self.linear_dominator)
102
parent_keys, child_keys)
120
103
121
104
122
105
cdef _KnownGraphNode _get_list_node(lst, Py_ssize_t pos):
134
117
return <_KnownGraphNode>temp_node
135
118
136
119
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
120
# TODO: slab allocate all _KnownGraphNode objects.
146
121
# We already know how many we are going to need, except for a couple of
147
122
# ghosts that could be allocated on demand.
152
127
cdef public object _nodes
153
128
cdef object _known_heads
154
129
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
158
130
159
131
def __init__(self, parent_map, do_cache=True):
160
132
"""Create a new KnownGraph instance.
161
133
162
134
:param parent_map: A dictionary mapping key => parent_keys
163
135
"""
136
# tests at pre-allocating the node dict actually slowed things down
164
137
self._nodes = {}
165
138
# Maps {sorted(revision_id, revision_id): heads}
166
139
self._known_heads = {}
167
self._to_cleanup = []
168
140
self.do_cache = int(do_cache)
169
141
self._initialize_nodes(parent_map)
170
self._find_linear_dominators()
171
142
self._find_gdfo()
172
143
173
144
def __dealloc__(self):
194
165
def _initialize_nodes(self, parent_map):
195
166
"""Populate self._nodes.
196
167
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.
168
After this has finished:
169
- self._nodes will have an entry for every entry in parent_map.
170
- ghosts will have a parent_keys = None,
171
- all nodes found will also have child_keys populated with all known
172
child keys,
200
173
"""
201
174
cdef PyObject *temp_key, *temp_parent_keys, *temp_node
202
175
cdef Py_ssize_t pos, pos2, num_parent_keys
203
176
cdef _KnownGraphNode node
204
177
cdef _KnownGraphNode parent_node
205
178
206
nodes = self._nodes
207
208
179
if not PyDict_CheckExact(parent_map):
209
180
raise TypeError('parent_map should be a dict of {key:parent_keys}')
210
181
# for key, parent_keys in parent_map.iteritems():
212
183
while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
213
184
key = <object>temp_key
214
185
parent_keys = <object>temp_parent_keys
186
num_parent_keys = len(parent_keys)
215
187
node = self._get_or_create_node(key)
216
188
# We know how many parents, so we could pre allocate an exact sized
217
189
# tuple here
218
num_parent_keys = len(parent_keys)
219
190
parent_nodes = PyTuple_New(num_parent_keys)
220
191
# We use iter here, because parent_keys maybe be a list or tuple
221
192
for pos2 from 0 <= pos2 < num_parent_keys:
222
parent_key = parent_keys[pos2]
223
193
parent_node = self._get_or_create_node(parent_keys[pos2])
224
194
# PyTuple_SET_ITEM will steal a reference, so INCREF first
225
195
Py_INCREF(parent_node)
227
197
PyList_Append(parent_node.children, node)
228
198
node.parents = parent_nodes
229
199
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
200
def _find_tails(self):
201
cdef PyObject *temp_node
202
cdef _KnownGraphNode node
203
cdef Py_ssize_t pos
303
204
304
205
tails = []
305
206
pos = 0
306
207
while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
307
208
node = <_KnownGraphNode>temp_node
308
209
if node.parents is None or PyTuple_GET_SIZE(node.parents) == 0:
210
node.gdfo = 1
309
211
PyList_Append(tails, node)
310
212
return tails
311
213
312
214
def _find_gdfo(self):
313
cdef Py_ssize_t pos, pos2
314
215
cdef _KnownGraphNode node
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)
216
cdef _KnownGraphNode child
217
cdef PyObject *temp
218
cdef Py_ssize_t pos
219
cdef int replace
220
cdef Py_ssize_t last_item
221
cdef long next_gdfo
222
223
pending = self._find_tails()
224
225
last_item = PyList_GET_SIZE(pending) - 1
226
while last_item >= 0:
227
# Avoid pop followed by push, instead, peek, and replace
228
# timing shows this is 930ms => 770ms for OOo
229
node = _get_list_node(pending, last_item)
230
last_item = last_item - 1
328
231
next_gdfo = node.gdfo + 1
329
replace_node = 1
330
232
for pos from 0 <= pos < PyList_GET_SIZE(node.children):
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
356
else:
357
heappush(todo, (child_gdfo, child_node))
358
if replace_node:
359
heappop(todo)
233
child = _get_list_node(node.children, pos)
234
if next_gdfo > child.gdfo:
235
child.gdfo = next_gdfo
236
child.seen = child.seen + 1
237
if child.seen == PyTuple_GET_SIZE(child.parents):
238
# This child is populated, queue it to be walked
239
last_item = last_item + 1
240
if last_item < PyList_GET_SIZE(pending):
241
Py_INCREF(child) # SetItem steals a ref
242
PyList_SetItem(pending, last_item, child)
243
else:
244
PyList_Append(pending, child)
245
# We have queued this node, we don't need to track it
246
# anymore
247
child.seen = 0
360
248
361
249
def heads(self, keys):
362
250
"""Return the heads from amongst keys.
364
252
This is done by searching the ancestries of each key. Any key that is
365
253
reachable from another key is not returned; all the others are.
366
254
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.
255
This operation scales with the relative depth between any two keys. It
256
uses gdfo to avoid walking all ancestry.
370
257
371
258
:param keys: An iterable of keys.
372
259
:return: A set of the heads. Note that as a set there is no ordering
375
262
"""
376
263
cdef PyObject *maybe_node
377
264
cdef PyObject *maybe_heads
265
cdef PyObject *temp_node
266
cdef _KnownGraphNode node
267
cdef Py_ssize_t pos, last_item
268
cdef long min_gdfo
378
269
379
270
heads_key = PyFrozenSet_New(keys)
380
271
maybe_heads = PyDict_GetItem(self._known_heads, heads_key)
381
272
if maybe_heads != NULL:
382
273
return <object>maybe_heads
383
384
274
# Not cached, compute it ourselves
385
275
candidate_nodes = {}
386
nodes = self._nodes
387
276
for key in keys:
388
maybe_node = PyDict_GetItem(nodes, key)
277
maybe_node = PyDict_GetItem(self._nodes, key)
389
278
if maybe_node == NULL:
390
279
raise KeyError('key %s not in nodes' % (key,))
391
280
PyDict_SetItem(candidate_nodes, key, <object>maybe_node)
392
if revision.NULL_REVISION in candidate_nodes:
281
maybe_node = PyDict_GetItem(candidate_nodes, NULL_REVISION)
282
if maybe_node != NULL:
393
283
# NULL_REVISION is only a head if it is the only entry
394
candidate_nodes.pop(revision.NULL_REVISION)
284
candidate_nodes.pop(NULL_REVISION)
395
285
if not candidate_nodes:
396
return set([revision.NULL_REVISION])
286
return frozenset([NULL_REVISION])
397
287
# The keys changed, so recalculate heads_key
398
288
heads_key = PyFrozenSet_New(candidate_nodes)
399
if len(candidate_nodes) < 2:
289
if PyDict_Size(candidate_nodes) < 2:
400
290
return heads_key
401
dom_to_node = self._get_dominators_to_nodes(candidate_nodes)
402
if PyDict_Size(candidate_nodes) < 2:
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)
291
292
cleanup = []
293
pending = []
294
# we know a gdfo cannot be longer than a linear chain of all nodes
295
min_gdfo = PyDict_Size(self._nodes) + 1
296
# Build up nodes that need to be walked, note that starting nodes are
297
# not added to seen()
298
pos = 0
299
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
300
node = <_KnownGraphNode>temp_node
301
if node.parents is not None:
302
pending.extend(node.parents)
303
if node.gdfo < min_gdfo:
304
min_gdfo = node.gdfo
305
306
# Now do all the real work
307
last_item = PyList_GET_SIZE(pending) - 1
308
while last_item >= 0:
309
node = _get_list_node(pending, last_item)
310
last_item = last_item - 1
311
if node.seen:
312
# node already appears in some ancestry
313
continue
314
PyList_Append(cleanup, node)
315
node.seen = 1
316
if node.gdfo <= min_gdfo:
317
continue
318
if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
319
for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
320
parent_node = _get_parent(node.parents, pos)
321
last_item = last_item + 1
322
if last_item < PyList_GET_SIZE(pending):
323
Py_INCREF(parent_node) # SetItem steals a ref
324
PyList_SetItem(pending, last_item, parent_node)
325
else:
326
PyList_Append(pending, parent_node)
327
heads = []
328
pos = 0
329
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
330
node = <_KnownGraphNode>temp_node
331
if not node.seen:
332
PyList_Append(heads, node.key)
333
heads = PyFrozenSet_New(heads)
334
for pos from 0 <= pos < PyList_GET_SIZE(cleanup):
335
node = _get_list_node(cleanup, pos)
336
node.seen = 0
413
337
if self.do_cache:
414
self._cache_heads(heads, heads_key, dom_lookup_key, candidate_nodes)
338
PyDict_SetItem(self._known_heads, heads_key, heads)
415
339
return heads
416
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))
539
return 0
540
541
cdef object _heads_from_candidate_nodes(self, candidate_nodes, dom_to_node):
542
cdef _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
547
cdef PyObject *temp_node
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)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1