1
# Copyright (C) 2009 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
"""Implementation of Graph algorithms when we have already loaded everything.
20
cdef extern from "python-compat.h":
23
cdef extern from "Python.h":
24
ctypedef int Py_ssize_t
25
ctypedef struct PyObject:
28
int PyString_CheckExact(object)
30
int PyObject_RichCompareBool(object, object, int)
33
int PyTuple_CheckExact(object)
34
object PyTuple_New(Py_ssize_t n)
35
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)
39
int PyList_CheckExact(object)
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
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
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)
52
void Py_INCREF(object)
56
from bzrlib import errors, revision
58
cdef object NULL_REVISION
59
NULL_REVISION = revision.NULL_REVISION
62
cdef class _KnownGraphNode:
63
"""Represents a single object in the known graph."""
72
def __init__(self, key):
77
# Greatest distance from origin
84
cdef _KnownGraphNode child
87
for child in self.children:
88
PyList_Append(keys, child.key)
91
cdef clear_references(self):
96
cdef _KnownGraphNode node
99
if self.parents is not None:
100
for node in self.parents:
101
parent_keys.append(node.key)
103
if self.children is not None:
104
for node in self.children:
105
child_keys.append(node.key)
106
return '%s(%s gdfo:%s par:%s child:%s)' % (
107
self.__class__.__name__, self.key, self.gdfo,
108
parent_keys, child_keys)
111
cdef _KnownGraphNode _get_list_node(lst, Py_ssize_t pos):
112
cdef PyObject *temp_node
114
temp_node = PyList_GET_ITEM(lst, pos)
115
return <_KnownGraphNode>temp_node
118
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
119
cdef PyObject *temp_node
121
temp_node = PyTuple_GET_ITEM(tpl, pos)
122
return <_KnownGraphNode>temp_node
126
cdef _KnownGraphNode real_node
131
cdef object _sort_list_nodes(object lst_or_tpl, int reverse):
132
"""Sort a list of _KnownGraphNode objects.
134
If lst_or_tpl is a list, it is allowed to mutate in place. It may also
135
just return the input list if everything is already sorted.
137
cdef _KnownGraphNode node1, node2
138
cdef int do_swap, is_tuple
139
cdef Py_ssize_t length
141
is_tuple = PyTuple_CheckExact(lst_or_tpl)
142
if not (is_tuple or PyList_CheckExact(lst_or_tpl)):
143
raise TypeError('lst_or_tpl must be a list or tuple.')
144
length = len(lst_or_tpl)
145
if length == 0 or length == 1:
149
node1 = _get_tuple_node(lst_or_tpl, 0)
150
node2 = _get_tuple_node(lst_or_tpl, 1)
152
node1 = _get_list_node(lst_or_tpl, 0)
153
node2 = _get_list_node(lst_or_tpl, 1)
155
do_swap = PyObject_RichCompareBool(node1.key, node2.key, Py_LT)
157
do_swap = PyObject_RichCompareBool(node2.key, node1.key, Py_LT)
161
return (node2, node1)
163
# Swap 'in-place', since lists are mutable
165
PyList_SetItem(lst_or_tpl, 1, node1)
167
PyList_SetItem(lst_or_tpl, 0, node2)
169
# For all other sizes, we just use 'sorted()'
171
# Note that sorted() is just list(iterable).sort()
172
lst_or_tpl = list(lst_or_tpl)
173
lst_or_tpl.sort(key=get_key, reverse=reverse)
177
cdef class _MergeSorter
179
cdef class KnownGraph:
180
"""This is a class which assumes we already know the full graph."""
182
cdef public object _nodes
183
cdef object _known_heads
184
cdef public int do_cache
186
def __init__(self, parent_map, do_cache=True):
187
"""Create a new KnownGraph instance.
189
:param parent_map: A dictionary mapping key => parent_keys
191
# tests at pre-allocating the node dict actually slowed things down
193
# Maps {sorted(revision_id, revision_id): heads}
194
self._known_heads = {}
195
self.do_cache = int(do_cache)
196
# TODO: consider disabling gc since we are allocating a lot of nodes
197
# that won't be collectable anyway. real world testing has not
198
# shown a specific impact, yet.
199
self._initialize_nodes(parent_map)
202
def __dealloc__(self):
203
cdef _KnownGraphNode child
205
cdef PyObject *temp_node
207
while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
208
child = <_KnownGraphNode>temp_node
209
child.clear_references()
211
cdef _KnownGraphNode _get_or_create_node(self, key):
212
cdef PyObject *temp_node
213
cdef _KnownGraphNode node
215
temp_node = PyDict_GetItem(self._nodes, key)
216
if temp_node == NULL:
217
node = _KnownGraphNode(key)
218
PyDict_SetItem(self._nodes, key, node)
220
node = <_KnownGraphNode>temp_node
223
def _initialize_nodes(self, parent_map):
224
"""Populate self._nodes.
226
After this has finished:
227
- self._nodes will have an entry for every entry in parent_map.
228
- ghosts will have a parent_keys = None,
229
- all nodes found will also have child_keys populated with all known
232
cdef PyObject *temp_key, *temp_parent_keys, *temp_node
233
cdef Py_ssize_t pos, pos2, num_parent_keys
234
cdef _KnownGraphNode node
235
cdef _KnownGraphNode parent_node
237
if not PyDict_CheckExact(parent_map):
238
raise TypeError('parent_map should be a dict of {key:parent_keys}')
239
# for key, parent_keys in parent_map.iteritems():
241
while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
242
key = <object>temp_key
243
parent_keys = <object>temp_parent_keys
244
num_parent_keys = len(parent_keys)
245
node = self._get_or_create_node(key)
246
# We know how many parents, so we pre allocate the tuple
247
parent_nodes = PyTuple_New(num_parent_keys)
248
for pos2 from 0 <= pos2 < num_parent_keys:
249
# Note: it costs us 10ms out of 40ms to lookup all of these
250
# parents, it doesn't seem to be an allocation overhead,
251
# but rather a lookup overhead. There doesn't seem to be
252
# a way around it, and that is one reason why
253
# KnownGraphNode maintains a direct pointer to the parent
255
# We use [] because parent_keys may be a tuple or list
256
parent_node = self._get_or_create_node(parent_keys[pos2])
257
# PyTuple_SET_ITEM will steal a reference, so INCREF first
258
Py_INCREF(parent_node)
259
PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
260
PyList_Append(parent_node.children, node)
261
node.parents = parent_nodes
263
def _find_tails(self):
264
cdef PyObject *temp_node
265
cdef _KnownGraphNode node
270
while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
271
node = <_KnownGraphNode>temp_node
272
if node.parents is None or PyTuple_GET_SIZE(node.parents) == 0:
274
PyList_Append(tails, node)
277
def _find_tips(self):
278
cdef PyObject *temp_node
279
cdef _KnownGraphNode node
284
while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
285
node = <_KnownGraphNode>temp_node
286
if PyList_GET_SIZE(node.children) == 0:
287
PyList_Append(tips, node)
290
def _find_gdfo(self):
291
cdef _KnownGraphNode node
292
cdef _KnownGraphNode child
296
cdef Py_ssize_t last_item
299
pending = self._find_tails()
301
last_item = PyList_GET_SIZE(pending) - 1
302
while last_item >= 0:
303
# Avoid pop followed by push, instead, peek, and replace
304
# timing shows this is 930ms => 770ms for OOo
305
node = _get_list_node(pending, last_item)
306
last_item = last_item - 1
307
next_gdfo = node.gdfo + 1
308
for pos from 0 <= pos < PyList_GET_SIZE(node.children):
309
child = _get_list_node(node.children, pos)
310
if next_gdfo > child.gdfo:
311
child.gdfo = next_gdfo
312
child.seen = child.seen + 1
313
if child.seen == PyTuple_GET_SIZE(child.parents):
314
# This child is populated, queue it to be walked
315
last_item = last_item + 1
316
if last_item < PyList_GET_SIZE(pending):
317
Py_INCREF(child) # SetItem steals a ref
318
PyList_SetItem(pending, last_item, child)
320
PyList_Append(pending, child)
321
# We have queued this node, we don't need to track it
325
def heads(self, keys):
326
"""Return the heads from amongst keys.
328
This is done by searching the ancestries of each key. Any key that is
329
reachable from another key is not returned; all the others are.
331
This operation scales with the relative depth between any two keys. It
332
uses gdfo to avoid walking all ancestry.
334
:param keys: An iterable of keys.
335
:return: A set of the heads. Note that as a set there is no ordering
336
information. Callers will need to filter their input to create
337
order if they need it.
339
cdef PyObject *maybe_node
340
cdef PyObject *maybe_heads
341
cdef PyObject *temp_node
342
cdef _KnownGraphNode node
343
cdef Py_ssize_t pos, last_item
346
heads_key = frozenset(keys)
347
maybe_heads = PyDict_GetItem(self._known_heads, heads_key)
348
if maybe_heads != NULL:
349
return <object>maybe_heads
350
# Not cached, compute it ourselves
353
maybe_node = PyDict_GetItem(self._nodes, key)
354
if maybe_node == NULL:
355
raise KeyError('key %s not in nodes' % (key,))
356
PyDict_SetItem(candidate_nodes, key, <object>maybe_node)
357
maybe_node = PyDict_GetItem(candidate_nodes, NULL_REVISION)
358
if maybe_node != NULL:
359
# NULL_REVISION is only a head if it is the only entry
360
candidate_nodes.pop(NULL_REVISION)
361
if not candidate_nodes:
362
return frozenset([NULL_REVISION])
363
# The keys changed, so recalculate heads_key
364
heads_key = frozenset(candidate_nodes)
365
if PyDict_Size(candidate_nodes) < 2:
370
# we know a gdfo cannot be longer than a linear chain of all nodes
371
min_gdfo = PyDict_Size(self._nodes) + 1
372
# Build up nodes that need to be walked, note that starting nodes are
373
# not added to seen()
375
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
376
node = <_KnownGraphNode>temp_node
377
if node.parents is not None:
378
pending.extend(node.parents)
379
if node.gdfo < min_gdfo:
382
# Now do all the real work
383
last_item = PyList_GET_SIZE(pending) - 1
384
while last_item >= 0:
385
node = _get_list_node(pending, last_item)
386
last_item = last_item - 1
388
# node already appears in some ancestry
390
PyList_Append(cleanup, node)
392
if node.gdfo <= min_gdfo:
394
if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
395
for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
396
parent_node = _get_tuple_node(node.parents, pos)
397
last_item = last_item + 1
398
if last_item < PyList_GET_SIZE(pending):
399
Py_INCREF(parent_node) # SetItem steals a ref
400
PyList_SetItem(pending, last_item, parent_node)
402
PyList_Append(pending, parent_node)
405
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
406
node = <_KnownGraphNode>temp_node
408
PyList_Append(heads, node.key)
409
heads = frozenset(heads)
410
for pos from 0 <= pos < PyList_GET_SIZE(cleanup):
411
node = _get_list_node(cleanup, pos)
414
PyDict_SetItem(self._known_heads, heads_key, heads)
418
"""Return the nodes in topological order.
420
All parents must occur before all children.
422
# This is, for the most part, the same iteration order that we used for
423
# _find_gdfo, consider finding a way to remove the duplication
424
# In general, we find the 'tails' (nodes with no parents), and then
425
# walk to the children. For children that have all of their parents
426
# yielded, we queue up the child to be yielded as well.
427
cdef _KnownGraphNode node
428
cdef _KnownGraphNode child
432
cdef Py_ssize_t last_item
434
pending = self._find_tails()
435
if PyList_GET_SIZE(pending) == 0 and len(self._nodes) > 0:
436
raise errors.GraphCycleError(self._nodes)
440
last_item = PyList_GET_SIZE(pending) - 1
441
while last_item >= 0:
442
# Avoid pop followed by push, instead, peek, and replace
443
# timing shows this is 930ms => 770ms for OOo
444
node = _get_list_node(pending, last_item)
445
last_item = last_item - 1
446
if node.parents is not None:
447
# We don't include ghost parents
448
PyList_Append(topo_order, node.key)
449
for pos from 0 <= pos < PyList_GET_SIZE(node.children):
450
child = _get_list_node(node.children, pos)
452
# We know we have a graph cycle because a node has a parent
453
# which we couldn't find
454
raise errors.GraphCycleError(self._nodes)
455
child.seen = child.seen + 1
456
if child.seen == PyTuple_GET_SIZE(child.parents):
457
# All parents of this child have been yielded, queue this
458
# one to be yielded as well
459
last_item = last_item + 1
460
if last_item < PyList_GET_SIZE(pending):
461
Py_INCREF(child) # SetItem steals a ref
462
PyList_SetItem(pending, last_item, child)
464
PyList_Append(pending, child)
465
# We have queued this node, we don't need to track it
468
# We started from the parents, so we don't need to do anymore work
472
"""Return a reverse topological ordering which is 'stable'.
474
There are a few constraints:
475
1) Reverse topological (all children before all parents)
477
3) 'stable' sorting, so that we get the same result, independent of
478
machine, or extra data.
479
To do this, we use the same basic algorithm as topo_sort, but when we
480
aren't sure what node to access next, we sort them lexicographically.
483
cdef Py_ssize_t pos, last_item
484
cdef _KnownGraphNode node, node2, parent_node
486
tips = self._find_tips()
487
# Split the tips based on prefix
489
for pos from 0 <= pos < PyList_GET_SIZE(tips):
490
node = _get_list_node(tips, pos)
491
if PyString_CheckExact(node.key) or len(node.key) == 1:
495
temp = PyDict_GetItem(prefix_tips, prefix)
497
prefix_tips[prefix] = [node]
499
tip_nodes = <object>temp
500
PyList_Append(tip_nodes, node)
503
for prefix in sorted(prefix_tips):
504
temp = PyDict_GetItem(prefix_tips, prefix)
506
tip_nodes = <object>temp
507
pending = _sort_list_nodes(tip_nodes, 1)
508
last_item = PyList_GET_SIZE(pending) - 1
509
while last_item >= 0:
510
node = _get_list_node(pending, last_item)
511
last_item = last_item - 1
512
if node.parents is None:
515
PyList_Append(result, node.key)
516
# Sorting the parent keys isn't strictly necessary for stable
517
# sorting of a given graph. But it does help minimize the
518
# differences between graphs
519
# For bzr.dev ancestry:
521
# 7.73ms RichCompareBool sort
522
parents = _sort_list_nodes(node.parents, 1)
523
for pos from 0 <= pos < len(parents):
524
if PyTuple_CheckExact(parents):
525
parent_node = _get_tuple_node(parents, pos)
527
parent_node = _get_list_node(parents, pos)
528
# TODO: GraphCycle detection
529
parent_node.seen = parent_node.seen + 1
531
== PyList_GET_SIZE(parent_node.children)):
532
# All children have been processed, queue up this
534
last_item = last_item + 1
535
if last_item < PyList_GET_SIZE(pending):
536
Py_INCREF(parent_node) # SetItem steals a ref
537
PyList_SetItem(pending, last_item, parent_node)
539
PyList_Append(pending, parent_node)
543
def merge_sort(self, tip_key):
544
"""Compute the merge sorted graph output."""
545
cdef _MergeSorter sorter
547
# TODO: consider disabling gc since we are allocating a lot of nodes
548
# that won't be collectable anyway. real world testing has not
549
# shown a specific impact, yet.
550
sorter = _MergeSorter(self, tip_key)
551
return sorter.topo_order()
554
cdef class _MergeSortNode:
555
"""Tracks information about a node during the merge_sort operation."""
558
cdef public object key
559
cdef public long merge_depth
560
cdef public object end_of_merge # True/False Is this the end of the current merge
562
# Private api, used while computing the information
563
cdef _KnownGraphNode left_parent
564
cdef _KnownGraphNode left_pending_parent
565
cdef object pending_parents # list of _KnownGraphNode for non-left parents
566
cdef long _revno_first
567
cdef long _revno_second
568
cdef long _revno_last
569
# TODO: turn these into flag/bit fields rather than individual members
570
cdef int is_first_child # Is this the first child?
571
cdef int seen_by_child # A child node has seen this parent
572
cdef int completed # Fully Processed
574
def __init__(self, key):
576
self.merge_depth = -1
577
self.left_parent = None
578
self.left_pending_parent = None
579
self.pending_parents = None
580
self._revno_first = -1
581
self._revno_second = -1
582
self._revno_last = -1
583
self.is_first_child = 0
584
self.seen_by_child = 0
588
return '%s(%s depth:%s rev:%s,%s,%s first:%s seen:%s)' % (
589
self.__class__.__name__, self.key,
591
self._revno_first, self._revno_second, self._revno_last,
592
self.is_first_child, self.seen_by_child)
594
cdef int has_pending_parents(self):
595
if self.left_pending_parent is not None or self.pending_parents:
599
cdef object _revno(self):
600
if self._revno_first == -1:
601
if self._revno_second != -1:
602
raise RuntimeError('Something wrong with: %s' % (self,))
603
return (self._revno_last,)
605
return (self._revno_first, self._revno_second, self._revno_last)
612
cdef class _MergeSorter:
613
"""This class does the work of computing the merge_sort ordering.
615
We have some small advantages, in that we get all the extra information
616
that KnownGraph knows, like knowing the child lists, etc.
619
# Current performance numbers for merge_sort(bzr_dev_parent_map):
620
# 302ms tsort.merge_sort()
621
# 91ms graph.KnownGraph().merge_sort()
622
# 40ms kg.merge_sort()
624
cdef KnownGraph graph
625
cdef object _depth_first_stack # list
626
cdef Py_ssize_t _last_stack_item # offset to last item on stack
627
# cdef object _ms_nodes # dict of key => _MergeSortNode
628
cdef object _revno_to_branch_count # {revno => num child branches}
629
cdef object _scheduled_nodes # List of nodes ready to be yielded
631
def __init__(self, known_graph, tip_key):
632
cdef _KnownGraphNode node
634
self.graph = known_graph
635
# self._ms_nodes = {}
636
self._revno_to_branch_count = {}
637
self._depth_first_stack = []
638
self._last_stack_item = -1
639
self._scheduled_nodes = []
640
if (tip_key is not None and tip_key != NULL_REVISION
641
and tip_key != (NULL_REVISION,)):
642
node = self.graph._nodes[tip_key]
643
self._push_node(node, 0)
645
cdef _MergeSortNode _get_ms_node(self, _KnownGraphNode node):
646
cdef PyObject *temp_node
647
cdef _MergeSortNode ms_node
649
if node.extra is None:
650
ms_node = _MergeSortNode(node.key)
653
ms_node = <_MergeSortNode>node.extra
656
cdef _push_node(self, _KnownGraphNode node, long merge_depth):
657
cdef _KnownGraphNode parent_node
658
cdef _MergeSortNode ms_node, ms_parent_node
661
ms_node = self._get_ms_node(node)
662
ms_node.merge_depth = merge_depth
663
if node.parents is None:
664
raise RuntimeError('ghost nodes should not be pushed'
665
' onto the stack: %s' % (node,))
666
if PyTuple_GET_SIZE(node.parents) > 0:
667
parent_node = _get_tuple_node(node.parents, 0)
668
ms_node.left_parent = parent_node
669
if parent_node.parents is None: # left-hand ghost
670
ms_node.left_pending_parent = None
671
ms_node.left_parent = None
673
ms_node.left_pending_parent = parent_node
674
if PyTuple_GET_SIZE(node.parents) > 1:
675
ms_node.pending_parents = []
676
for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
677
parent_node = _get_tuple_node(node.parents, pos)
678
if parent_node.parents is None: # ghost
680
PyList_Append(ms_node.pending_parents, parent_node)
682
ms_node.is_first_child = 1
683
if ms_node.left_parent is not None:
684
ms_parent_node = self._get_ms_node(ms_node.left_parent)
685
if ms_parent_node.seen_by_child:
686
ms_node.is_first_child = 0
687
ms_parent_node.seen_by_child = 1
688
self._last_stack_item = self._last_stack_item + 1
689
if self._last_stack_item < PyList_GET_SIZE(self._depth_first_stack):
690
Py_INCREF(node) # SetItem steals a ref
691
PyList_SetItem(self._depth_first_stack, self._last_stack_item,
694
PyList_Append(self._depth_first_stack, node)
696
cdef _pop_node(self):
698
cdef _MergeSortNode ms_node, ms_parent_node, ms_prev_node
699
cdef _KnownGraphNode node, parent_node, prev_node
701
node = _get_list_node(self._depth_first_stack, self._last_stack_item)
702
ms_node = <_MergeSortNode>node.extra
703
self._last_stack_item = self._last_stack_item - 1
704
if ms_node.left_parent is not None:
705
# Assign the revision number from the left-hand parent
706
ms_parent_node = <_MergeSortNode>ms_node.left_parent.extra
707
if ms_node.is_first_child:
708
# First child just increments the final digit
709
ms_node._revno_first = ms_parent_node._revno_first
710
ms_node._revno_second = ms_parent_node._revno_second
711
ms_node._revno_last = ms_parent_node._revno_last + 1
713
# Not the first child, make a new branch
714
# (mainline_revno, branch_count, 1)
715
if ms_parent_node._revno_first == -1:
716
# Mainline ancestor, the increment is on the last digit
717
base_revno = ms_parent_node._revno_last
719
base_revno = ms_parent_node._revno_first
720
temp = PyDict_GetItem(self._revno_to_branch_count,
725
branch_count = (<object>temp) + 1
726
PyDict_SetItem(self._revno_to_branch_count, base_revno,
728
ms_node._revno_first = base_revno
729
ms_node._revno_second = branch_count
730
ms_node._revno_last = 1
732
temp = PyDict_GetItem(self._revno_to_branch_count, 0)
734
# The first root node doesn't have a 3-digit revno
736
ms_node._revno_first = -1
737
ms_node._revno_second = -1
738
ms_node._revno_last = 1
740
root_count = (<object>temp) + 1
741
ms_node._revno_first = 0
742
ms_node._revno_second = root_count
743
ms_node._revno_last = 1
744
PyDict_SetItem(self._revno_to_branch_count, 0, root_count)
745
ms_node.completed = 1
746
if PyList_GET_SIZE(self._scheduled_nodes) == 0:
747
# The first scheduled node is always the end of merge
748
ms_node.end_of_merge = True
750
prev_node = _get_list_node(self._scheduled_nodes,
751
PyList_GET_SIZE(self._scheduled_nodes) - 1)
752
ms_prev_node = <_MergeSortNode>prev_node.extra
753
if ms_prev_node.merge_depth < ms_node.merge_depth:
754
# The previously pushed node is to our left, so this is the end
755
# of this right-hand chain
756
ms_node.end_of_merge = True
757
elif (ms_prev_node.merge_depth == ms_node.merge_depth
758
and prev_node not in node.parents):
759
# The next node is not a direct parent of this node
760
ms_node.end_of_merge = True
762
ms_node.end_of_merge = False
763
PyList_Append(self._scheduled_nodes, node)
765
cdef _schedule_stack(self):
766
cdef _KnownGraphNode last_node, next_node
767
cdef _MergeSortNode ms_node, ms_last_node, ms_next_node
768
cdef long next_merge_depth
770
while self._last_stack_item >= 0:
771
# Peek at the last item on the stack
772
last_node = _get_list_node(self._depth_first_stack,
773
self._last_stack_item)
774
if last_node.gdfo == -1:
775
# if _find_gdfo skipped a node, that means there is a graph
776
# cycle, error out now
777
raise errors.GraphCycleError(self.graph._nodes)
778
ms_last_node = <_MergeSortNode>last_node.extra
779
if not ms_last_node.has_pending_parents():
780
# Processed all parents, pop this node
783
while ms_last_node.has_pending_parents():
784
if ms_last_node.left_pending_parent is not None:
785
# recurse depth first into the primary parent
786
next_node = ms_last_node.left_pending_parent
787
ms_last_node.left_pending_parent = None
789
# place any merges in right-to-left order for scheduling
790
# which gives us left-to-right order after we reverse
791
# the scheduled queue.
792
# Note: This has the effect of allocating common-new
793
# revisions to the right-most subtree rather than the
794
# left most, which will display nicely (you get
795
# smaller trees at the top of the combined merge).
796
next_node = ms_last_node.pending_parents.pop()
797
ms_next_node = self._get_ms_node(next_node)
798
if ms_next_node.completed:
799
# this parent was completed by a child on the
800
# call stack. skip it.
802
# otherwise transfer it from the source graph into the
803
# top of the current depth first search stack.
805
if next_node is ms_last_node.left_parent:
806
next_merge_depth = ms_last_node.merge_depth
808
next_merge_depth = ms_last_node.merge_depth + 1
809
self._push_node(next_node, next_merge_depth)
810
# and do not continue processing parents until this 'call'
814
cdef topo_order(self):
815
cdef _MergeSortNode ms_node
816
cdef _KnownGraphNode node
818
cdef PyObject *temp_key, *temp_node
820
# Note: allocating a _MergeSortNode and deallocating it for all nodes
821
# costs approx 8.52ms (21%) of the total runtime
822
# We might consider moving the attributes into the base
824
self._schedule_stack()
826
# We've set up the basic schedule, now we can continue processing the
828
# Note: This final loop costs us 40.0ms => 28.8ms (11ms, 25%) on
829
# bzr.dev, to convert the internal Object representation into a
830
# Tuple representation...
831
# 2ms is walking the data and computing revno tuples
832
# 7ms is computing the return tuple
833
# 4ms is PyList_Append()
835
# output the result in reverse order, and separate the generated info
836
for pos from PyList_GET_SIZE(self._scheduled_nodes) > pos >= 0:
837
node = _get_list_node(self._scheduled_nodes, pos)
838
ms_node = <_MergeSortNode>node.extra
839
PyList_Append(ordered, ms_node)
841
# Clear out the scheduled nodes now that we're done
842
self._scheduled_nodes = []
added
removed
bzrlib/_known_graph_pyx.pyx
