1
# Copyright (C) 2009, 2010 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
from cpython.bytes cimport (
26
from cpython.dict cimport (
34
from cpython.list cimport (
41
from cpython.object cimport (
44
PyObject_RichCompareBool,
46
from cpython.ref cimport (
49
from cpython.tuple cimport (
60
from . import errors, revision
62
cdef object NULL_REVISION
63
NULL_REVISION = revision.NULL_REVISION
66
cdef class _KnownGraphNode:
67
"""Represents a single object in the known graph."""
76
def __init__(self, key):
81
# Greatest distance from origin
88
cdef _KnownGraphNode child
91
for child in self.children:
92
PyList_Append(keys, child.key)
97
if self.parents is None:
100
cdef _KnownGraphNode parent
103
for parent in self.parents:
104
PyList_Append(keys, parent.key)
107
cdef clear_references(self):
112
cdef _KnownGraphNode node
115
if self.parents is not None:
116
for node in self.parents:
117
parent_keys.append(node.key)
119
if self.children is not None:
120
for node in self.children:
121
child_keys.append(node.key)
122
return '%s(%s gdfo:%s par:%s child:%s)' % (
123
self.__class__.__name__, self.key, self.gdfo,
124
parent_keys, child_keys)
127
cdef _KnownGraphNode _get_list_node(lst, Py_ssize_t pos):
128
cdef PyObject *temp_node
130
temp_node = PyList_GET_ITEM(lst, pos)
131
return <_KnownGraphNode>temp_node
134
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
135
cdef PyObject *temp_node
137
temp_node = PyTuple_GET_ITEM(tpl, pos)
138
return <_KnownGraphNode>temp_node
142
cdef _KnownGraphNode real_node
147
cdef object _sort_list_nodes(object lst_or_tpl, int reverse):
148
"""Sort a list of _KnownGraphNode objects.
150
If lst_or_tpl is a list, it is allowed to mutate in place. It may also
151
just return the input list if everything is already sorted.
153
cdef _KnownGraphNode node1, node2
154
cdef int do_swap, is_tuple
155
cdef Py_ssize_t length
157
is_tuple = PyTuple_CheckExact(lst_or_tpl)
158
if not (is_tuple or PyList_CheckExact(lst_or_tpl)):
159
raise TypeError('lst_or_tpl must be a list or tuple.')
160
length = len(lst_or_tpl)
161
if length == 0 or length == 1:
165
node1 = _get_tuple_node(lst_or_tpl, 0)
166
node2 = _get_tuple_node(lst_or_tpl, 1)
168
node1 = _get_list_node(lst_or_tpl, 0)
169
node2 = _get_list_node(lst_or_tpl, 1)
171
do_swap = PyObject_RichCompareBool(node1.key, node2.key, Py_LT)
173
do_swap = PyObject_RichCompareBool(node2.key, node1.key, Py_LT)
177
return (node2, node1)
179
# Swap 'in-place', since lists are mutable
181
PyList_SetItem(lst_or_tpl, 1, node1)
183
PyList_SetItem(lst_or_tpl, 0, node2)
185
# For all other sizes, we just use 'sorted()'
187
# Note that sorted() is just list(iterable).sort()
188
lst_or_tpl = list(lst_or_tpl)
189
lst_or_tpl.sort(key=get_key, reverse=reverse)
193
cdef class _MergeSorter
195
cdef class KnownGraph:
196
"""This is a class which assumes we already know the full graph."""
198
cdef public object _nodes
199
cdef public object _known_heads
200
cdef public int do_cache
202
def __init__(self, parent_map, do_cache=True):
203
"""Create a new KnownGraph instance.
205
:param parent_map: A dictionary mapping key => parent_keys
207
# tests at pre-allocating the node dict actually slowed things down
209
# Maps {sorted(revision_id, revision_id): heads}
210
self._known_heads = {}
211
self.do_cache = int(do_cache)
212
# TODO: consider disabling gc since we are allocating a lot of nodes
213
# that won't be collectable anyway. real world testing has not
214
# shown a specific impact, yet.
215
self._initialize_nodes(parent_map)
218
def __dealloc__(self):
219
cdef _KnownGraphNode child
221
cdef PyObject *temp_node
223
while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
224
child = <_KnownGraphNode>temp_node
225
child.clear_references()
227
cdef _KnownGraphNode _get_or_create_node(self, key):
228
cdef PyObject *temp_node
229
cdef _KnownGraphNode node
231
temp_node = PyDict_GetItem(self._nodes, key)
232
if temp_node == NULL:
233
node = _KnownGraphNode(key)
234
PyDict_SetItem(self._nodes, key, node)
236
node = <_KnownGraphNode>temp_node
239
cdef _populate_parents(self, _KnownGraphNode node, parent_keys):
240
cdef Py_ssize_t num_parent_keys, pos
241
cdef _KnownGraphNode parent_node
243
num_parent_keys = len(parent_keys)
244
# We know how many parents, so we pre allocate the tuple
245
parent_nodes = PyTuple_New(num_parent_keys)
246
for pos from 0 <= pos < num_parent_keys:
247
# Note: it costs us 10ms out of 40ms to lookup all of these
248
# parents, it doesn't seem to be an allocation overhead,
249
# but rather a lookup overhead. There doesn't seem to be
250
# a way around it, and that is one reason why
251
# KnownGraphNode maintains a direct pointer to the parent
253
# We use [] because parent_keys may be a tuple or list
254
parent_node = self._get_or_create_node(parent_keys[pos])
255
# PyTuple_SET_ITEM will steal a reference, so INCREF first
256
Py_INCREF(parent_node)
257
PyTuple_SET_ITEM(parent_nodes, pos, parent_node)
258
PyList_Append(parent_node.children, node)
259
node.parents = parent_nodes
261
def _initialize_nodes(self, parent_map):
262
"""Populate self._nodes.
264
After this has finished:
265
- self._nodes will have an entry for every entry in parent_map.
266
- ghosts will have a parent_keys = None,
267
- all nodes found will also have child_keys populated with all known
270
cdef PyObject *temp_key
271
cdef PyObject *temp_parent_keys
272
cdef PyObject *temp_node
274
cdef _KnownGraphNode node
275
cdef _KnownGraphNode parent_node
277
if not PyDict_CheckExact(parent_map):
278
raise TypeError('parent_map should be a dict of {key:parent_keys}')
279
# for key, parent_keys in parent_map.iteritems():
281
while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
282
key = <object>temp_key
283
parent_keys = <object>temp_parent_keys
284
node = self._get_or_create_node(key)
285
self._populate_parents(node, parent_keys)
287
def _find_tails(self):
288
cdef PyObject *temp_node
289
cdef _KnownGraphNode node
294
while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
295
node = <_KnownGraphNode>temp_node
296
if node.parents is None or PyTuple_GET_SIZE(node.parents) == 0:
298
PyList_Append(tails, node)
301
def _find_tips(self):
302
cdef PyObject *temp_node
303
cdef _KnownGraphNode node
308
while PyDict_Next(self._nodes, &pos, NULL, &temp_node):
309
node = <_KnownGraphNode>temp_node
310
if PyList_GET_SIZE(node.children) == 0:
311
PyList_Append(tips, node)
314
def _find_gdfo(self):
315
cdef _KnownGraphNode node
316
cdef _KnownGraphNode child
320
cdef Py_ssize_t last_item
323
pending = self._find_tails()
325
last_item = PyList_GET_SIZE(pending) - 1
326
while last_item >= 0:
327
# Avoid pop followed by push, instead, peek, and replace
328
# timing shows this is 930ms => 770ms for OOo
329
node = _get_list_node(pending, last_item)
330
last_item = last_item - 1
331
next_gdfo = node.gdfo + 1
332
for pos from 0 <= pos < PyList_GET_SIZE(node.children):
333
child = _get_list_node(node.children, pos)
334
if next_gdfo > child.gdfo:
335
child.gdfo = next_gdfo
336
child.seen = child.seen + 1
337
if child.seen == PyTuple_GET_SIZE(child.parents):
338
# This child is populated, queue it to be walked
339
last_item = last_item + 1
340
if last_item < PyList_GET_SIZE(pending):
341
Py_INCREF(child) # SetItem steals a ref
342
PyList_SetItem(pending, last_item, child)
344
PyList_Append(pending, child)
345
# We have queued this node, we don't need to track it
349
def add_node(self, key, parent_keys):
350
"""Add a new node to the graph.
352
If this fills in a ghost, then the gdfos of all children will be
355
:param key: The node being added. If this is a duplicate, this is a
357
:param parent_keys: The parents of the given node.
358
:return: None (should we return if this was a ghost, etc?)
360
cdef PyObject *maybe_node
361
cdef _KnownGraphNode node, parent_node, child_node
362
cdef long parent_gdfo, next_gdfo
364
maybe_node = PyDict_GetItem(self._nodes, key)
365
if maybe_node != NULL:
366
node = <_KnownGraphNode>maybe_node
367
if node.parents is None:
368
# We are filling in a ghost
369
self._populate_parents(node, parent_keys)
370
# We can't trust cached heads anymore
371
self._known_heads.clear()
372
else: # Ensure that the parent_key list matches
373
existing_parent_keys = []
374
for parent_node in node.parents:
375
existing_parent_keys.append(parent_node.key)
376
# Make sure we use a list for the comparison, in case it was a
378
parent_keys = list(parent_keys)
379
if existing_parent_keys == parent_keys:
380
# Exact match, nothing more to do
383
raise ValueError('Parent key mismatch, existing node %s'
384
' has parents of %s not %s'
385
% (key, existing_parent_keys, parent_keys))
387
node = _KnownGraphNode(key)
388
PyDict_SetItem(self._nodes, key, node)
389
self._populate_parents(node, parent_keys)
391
for parent_node in node.parents:
392
if parent_node.gdfo == -1:
393
# This is a newly introduced ghost, so it gets gdfo of 1
395
if parent_gdfo < parent_node.gdfo:
396
parent_gdfo = parent_node.gdfo
397
node.gdfo = parent_gdfo + 1
398
# Now fill the gdfo to all children
399
# Note that this loop is slightly inefficient, in that we may visit the
400
# same child (and its decendents) more than once, however, it is
401
# 'efficient' in that we only walk to nodes that would be updated,
402
# rather than all nodes
403
# We use a deque rather than a simple list stack, to go for BFD rather
404
# than DFD. So that if a longer path is possible, we walk it before we
405
# get to the final child
406
pending = collections.deque([node])
407
pending_popleft = pending.popleft
408
pending_append = pending.append
410
node = pending_popleft()
411
next_gdfo = node.gdfo + 1
412
for child_node in node.children:
413
if child_node.gdfo < next_gdfo:
414
# This child is being updated, we need to check its
416
child_node.gdfo = next_gdfo
417
pending_append(child_node)
419
def heads(self, keys):
420
"""Return the heads from amongst keys.
422
This is done by searching the ancestries of each key. Any key that is
423
reachable from another key is not returned; all the others are.
425
This operation scales with the relative depth between any two keys. It
426
uses gdfo to avoid walking all ancestry.
428
:param keys: An iterable of keys.
429
:return: A set of the heads. Note that as a set there is no ordering
430
information. Callers will need to filter their input to create
431
order if they need it.
433
cdef PyObject *maybe_node
434
cdef PyObject *maybe_heads
435
cdef PyObject *temp_node
436
cdef _KnownGraphNode node
437
cdef Py_ssize_t pos, last_item
440
heads_key = frozenset(keys)
441
maybe_heads = PyDict_GetItem(self._known_heads, heads_key)
442
if maybe_heads != NULL:
443
return <object>maybe_heads
444
# Not cached, compute it ourselves
447
maybe_node = PyDict_GetItem(self._nodes, key)
448
if maybe_node == NULL:
449
raise KeyError('key %s not in nodes' % (key,))
450
PyDict_SetItem(candidate_nodes, key, <object>maybe_node)
451
maybe_node = PyDict_GetItem(candidate_nodes, NULL_REVISION)
452
if maybe_node != NULL:
453
# NULL_REVISION is only a head if it is the only entry
454
candidate_nodes.pop(NULL_REVISION)
455
if not candidate_nodes:
456
return frozenset([NULL_REVISION])
457
# The keys changed, so recalculate heads_key
458
heads_key = frozenset(candidate_nodes)
459
if PyDict_Size(candidate_nodes) < 2:
464
# we know a gdfo cannot be longer than a linear chain of all nodes
465
min_gdfo = PyDict_Size(self._nodes) + 1
466
# Build up nodes that need to be walked, note that starting nodes are
467
# not added to seen()
469
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
470
node = <_KnownGraphNode>temp_node
471
if node.parents is not None:
472
pending.extend(node.parents)
473
if node.gdfo < min_gdfo:
476
# Now do all the real work
477
last_item = PyList_GET_SIZE(pending) - 1
478
while last_item >= 0:
479
node = _get_list_node(pending, last_item)
480
last_item = last_item - 1
482
# node already appears in some ancestry
484
PyList_Append(cleanup, node)
486
if node.gdfo <= min_gdfo:
488
if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
489
for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
490
parent_node = _get_tuple_node(node.parents, pos)
491
last_item = last_item + 1
492
if last_item < PyList_GET_SIZE(pending):
493
Py_INCREF(parent_node) # SetItem steals a ref
494
PyList_SetItem(pending, last_item, parent_node)
496
PyList_Append(pending, parent_node)
499
while PyDict_Next(candidate_nodes, &pos, NULL, &temp_node):
500
node = <_KnownGraphNode>temp_node
502
PyList_Append(heads, node.key)
503
heads = frozenset(heads)
504
for pos from 0 <= pos < PyList_GET_SIZE(cleanup):
505
node = _get_list_node(cleanup, pos)
508
PyDict_SetItem(self._known_heads, heads_key, heads)
512
"""Return the nodes in topological order.
514
All parents must occur before all children.
516
# This is, for the most part, the same iteration order that we used for
517
# _find_gdfo, consider finding a way to remove the duplication
518
# In general, we find the 'tails' (nodes with no parents), and then
519
# walk to the children. For children that have all of their parents
520
# yielded, we queue up the child to be yielded as well.
521
cdef _KnownGraphNode node
522
cdef _KnownGraphNode child
526
cdef Py_ssize_t last_item
528
pending = self._find_tails()
529
if PyList_GET_SIZE(pending) == 0 and len(self._nodes) > 0:
530
raise errors.GraphCycleError(self._nodes)
534
last_item = PyList_GET_SIZE(pending) - 1
535
while last_item >= 0:
536
# Avoid pop followed by push, instead, peek, and replace
537
# timing shows this is 930ms => 770ms for OOo
538
node = _get_list_node(pending, last_item)
539
last_item = last_item - 1
540
if node.parents is not None:
541
# We don't include ghost parents
542
PyList_Append(topo_order, node.key)
543
for pos from 0 <= pos < PyList_GET_SIZE(node.children):
544
child = _get_list_node(node.children, pos)
546
# We know we have a graph cycle because a node has a parent
547
# which we couldn't find
548
raise errors.GraphCycleError(self._nodes)
549
child.seen = child.seen + 1
550
if child.seen == PyTuple_GET_SIZE(child.parents):
551
# All parents of this child have been yielded, queue this
552
# one to be yielded as well
553
last_item = last_item + 1
554
if last_item < PyList_GET_SIZE(pending):
555
Py_INCREF(child) # SetItem steals a ref
556
PyList_SetItem(pending, last_item, child)
558
PyList_Append(pending, child)
559
# We have queued this node, we don't need to track it
562
# We started from the parents, so we don't need to do anymore work
566
"""Return a reverse topological ordering which is 'stable'.
568
There are a few constraints:
569
1) Reverse topological (all children before all parents)
571
3) 'stable' sorting, so that we get the same result, independent of
572
machine, or extra data.
573
To do this, we use the same basic algorithm as topo_sort, but when we
574
aren't sure what node to access next, we sort them lexicographically.
577
cdef Py_ssize_t pos, last_item
578
cdef _KnownGraphNode node, node2, parent_node
580
tips = self._find_tips()
581
# Split the tips based on prefix
583
for pos from 0 <= pos < PyList_GET_SIZE(tips):
584
node = _get_list_node(tips, pos)
585
if PyBytes_CheckExact(node.key) or len(node.key) == 1:
589
temp = PyDict_GetItem(prefix_tips, prefix)
591
prefix_tips[prefix] = [node]
593
tip_nodes = <object>temp
594
PyList_Append(tip_nodes, node)
597
for prefix in sorted(prefix_tips):
598
temp = PyDict_GetItem(prefix_tips, prefix)
600
tip_nodes = <object>temp
601
pending = _sort_list_nodes(tip_nodes, 1)
602
last_item = PyList_GET_SIZE(pending) - 1
603
while last_item >= 0:
604
node = _get_list_node(pending, last_item)
605
last_item = last_item - 1
606
if node.parents is None:
609
PyList_Append(result, node.key)
610
# Sorting the parent keys isn't strictly necessary for stable
611
# sorting of a given graph. But it does help minimize the
612
# differences between graphs
613
# For bzr.dev ancestry:
615
# 7.73ms RichCompareBool sort
616
parents = _sort_list_nodes(node.parents, 1)
617
for pos from 0 <= pos < len(parents):
618
if PyTuple_CheckExact(parents):
619
parent_node = _get_tuple_node(parents, pos)
621
parent_node = _get_list_node(parents, pos)
622
# TODO: GraphCycle detection
623
parent_node.seen = parent_node.seen + 1
625
== PyList_GET_SIZE(parent_node.children)):
626
# All children have been processed, queue up this
628
last_item = last_item + 1
629
if last_item < PyList_GET_SIZE(pending):
630
Py_INCREF(parent_node) # SetItem steals a ref
631
PyList_SetItem(pending, last_item, parent_node)
633
PyList_Append(pending, parent_node)
637
def merge_sort(self, tip_key):
638
"""Compute the merge sorted graph output."""
639
cdef _MergeSorter sorter
641
# TODO: consider disabling gc since we are allocating a lot of nodes
642
# that won't be collectable anyway. real world testing has not
643
# shown a specific impact, yet.
644
sorter = _MergeSorter(self, tip_key)
645
return sorter.topo_order()
647
def get_parent_keys(self, key):
648
"""Get the parents for a key
650
Returns a list containing the parents keys. If the key is a ghost,
651
None is returned. A KeyError will be raised if the key is not in
654
:param keys: Key to check (eg revision_id)
655
:return: A list of parents
657
return self._nodes[key].parent_keys
659
def get_child_keys(self, key):
660
"""Get the children for a key
662
Returns a list containing the children keys. A KeyError will be raised
663
if the key is not in the graph.
665
:param keys: Key to check (eg revision_id)
666
:return: A list of children
668
return self._nodes[key].child_keys
671
cdef class _MergeSortNode:
672
"""Tracks information about a node during the merge_sort operation."""
675
cdef public object key
676
cdef public long merge_depth
677
cdef public object end_of_merge # True/False Is this the end of the current merge
679
# Private api, used while computing the information
680
cdef _KnownGraphNode left_parent
681
cdef _KnownGraphNode left_pending_parent
682
cdef object pending_parents # list of _KnownGraphNode for non-left parents
683
cdef long _revno_first
684
cdef long _revno_second
685
cdef long _revno_last
686
# TODO: turn these into flag/bit fields rather than individual members
687
cdef int is_first_child # Is this the first child?
688
cdef int seen_by_child # A child node has seen this parent
689
cdef int completed # Fully Processed
691
def __init__(self, key):
693
self.merge_depth = -1
694
self.left_parent = None
695
self.left_pending_parent = None
696
self.pending_parents = None
697
self._revno_first = -1
698
self._revno_second = -1
699
self._revno_last = -1
700
self.is_first_child = 0
701
self.seen_by_child = 0
705
return '%s(%s depth:%s rev:%s,%s,%s first:%s seen:%s)' % (
706
self.__class__.__name__, self.key,
708
self._revno_first, self._revno_second, self._revno_last,
709
self.is_first_child, self.seen_by_child)
711
cdef int has_pending_parents(self): # cannot_raise
712
if self.left_pending_parent is not None or self.pending_parents:
716
cdef object _revno(self):
717
if self._revno_first == -1:
718
if self._revno_second != -1:
719
raise RuntimeError('Something wrong with: %s' % (self,))
720
return (self._revno_last,)
722
return (self._revno_first, self._revno_second, self._revno_last)
729
cdef class _MergeSorter:
730
"""This class does the work of computing the merge_sort ordering.
732
We have some small advantages, in that we get all the extra information
733
that KnownGraph knows, like knowing the child lists, etc.
736
# Current performance numbers for merge_sort(bzr_dev_parent_map):
737
# 302ms tsort.merge_sort()
738
# 91ms graph.KnownGraph().merge_sort()
739
# 40ms kg.merge_sort()
741
cdef KnownGraph graph
742
cdef object _depth_first_stack # list
743
cdef Py_ssize_t _last_stack_item # offset to last item on stack
744
# cdef object _ms_nodes # dict of key => _MergeSortNode
745
cdef object _revno_to_branch_count # {revno => num child branches}
746
cdef object _scheduled_nodes # List of nodes ready to be yielded
748
def __init__(self, known_graph, tip_key):
749
cdef _KnownGraphNode node
751
self.graph = known_graph
752
# self._ms_nodes = {}
753
self._revno_to_branch_count = {}
754
self._depth_first_stack = []
755
self._last_stack_item = -1
756
self._scheduled_nodes = []
757
if (tip_key is not None and tip_key != NULL_REVISION
758
and tip_key != (NULL_REVISION,)):
759
node = self.graph._nodes[tip_key]
760
self._push_node(node, 0)
762
cdef _MergeSortNode _get_ms_node(self, _KnownGraphNode node):
763
cdef PyObject *temp_node
764
cdef _MergeSortNode ms_node
766
if node.extra is None:
767
ms_node = _MergeSortNode(node.key)
770
ms_node = <_MergeSortNode>node.extra
773
cdef _push_node(self, _KnownGraphNode node, long merge_depth):
774
cdef _KnownGraphNode parent_node
775
cdef _MergeSortNode ms_node, ms_parent_node
778
ms_node = self._get_ms_node(node)
779
ms_node.merge_depth = merge_depth
780
if node.parents is None:
781
raise RuntimeError('ghost nodes should not be pushed'
782
' onto the stack: %s' % (node,))
783
if PyTuple_GET_SIZE(node.parents) > 0:
784
parent_node = _get_tuple_node(node.parents, 0)
785
ms_node.left_parent = parent_node
786
if parent_node.parents is None: # left-hand ghost
787
ms_node.left_pending_parent = None
788
ms_node.left_parent = None
790
ms_node.left_pending_parent = parent_node
791
if PyTuple_GET_SIZE(node.parents) > 1:
792
ms_node.pending_parents = []
793
for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
794
parent_node = _get_tuple_node(node.parents, pos)
795
if parent_node.parents is None: # ghost
797
PyList_Append(ms_node.pending_parents, parent_node)
799
ms_node.is_first_child = 1
800
if ms_node.left_parent is not None:
801
ms_parent_node = self._get_ms_node(ms_node.left_parent)
802
if ms_parent_node.seen_by_child:
803
ms_node.is_first_child = 0
804
ms_parent_node.seen_by_child = 1
805
self._last_stack_item = self._last_stack_item + 1
806
if self._last_stack_item < PyList_GET_SIZE(self._depth_first_stack):
807
Py_INCREF(node) # SetItem steals a ref
808
PyList_SetItem(self._depth_first_stack, self._last_stack_item,
811
PyList_Append(self._depth_first_stack, node)
813
cdef _pop_node(self):
815
cdef _MergeSortNode ms_node, ms_parent_node, ms_prev_node
816
cdef _KnownGraphNode node, parent_node, prev_node
818
node = _get_list_node(self._depth_first_stack, self._last_stack_item)
819
ms_node = <_MergeSortNode>node.extra
820
self._last_stack_item = self._last_stack_item - 1
821
if ms_node.left_parent is not None:
822
# Assign the revision number from the left-hand parent
823
ms_parent_node = <_MergeSortNode>ms_node.left_parent.extra
824
if ms_node.is_first_child:
825
# First child just increments the final digit
826
ms_node._revno_first = ms_parent_node._revno_first
827
ms_node._revno_second = ms_parent_node._revno_second
828
ms_node._revno_last = ms_parent_node._revno_last + 1
830
# Not the first child, make a new branch
831
# (mainline_revno, branch_count, 1)
832
if ms_parent_node._revno_first == -1:
833
# Mainline ancestor, the increment is on the last digit
834
base_revno = ms_parent_node._revno_last
836
base_revno = ms_parent_node._revno_first
837
temp = PyDict_GetItem(self._revno_to_branch_count,
842
branch_count = (<object>temp) + 1
843
PyDict_SetItem(self._revno_to_branch_count, base_revno,
845
ms_node._revno_first = base_revno
846
ms_node._revno_second = branch_count
847
ms_node._revno_last = 1
849
temp = PyDict_GetItem(self._revno_to_branch_count, 0)
851
# The first root node doesn't have a 3-digit revno
853
ms_node._revno_first = -1
854
ms_node._revno_second = -1
855
ms_node._revno_last = 1
857
root_count = (<object>temp) + 1
858
ms_node._revno_first = 0
859
ms_node._revno_second = root_count
860
ms_node._revno_last = 1
861
PyDict_SetItem(self._revno_to_branch_count, 0, root_count)
862
ms_node.completed = 1
863
if PyList_GET_SIZE(self._scheduled_nodes) == 0:
864
# The first scheduled node is always the end of merge
865
ms_node.end_of_merge = True
867
prev_node = _get_list_node(self._scheduled_nodes,
868
PyList_GET_SIZE(self._scheduled_nodes) - 1)
869
ms_prev_node = <_MergeSortNode>prev_node.extra
870
if ms_prev_node.merge_depth < ms_node.merge_depth:
871
# The previously pushed node is to our left, so this is the end
872
# of this right-hand chain
873
ms_node.end_of_merge = True
874
elif (ms_prev_node.merge_depth == ms_node.merge_depth
875
and prev_node not in node.parents):
876
# The next node is not a direct parent of this node
877
ms_node.end_of_merge = True
879
ms_node.end_of_merge = False
880
PyList_Append(self._scheduled_nodes, node)
882
cdef _schedule_stack(self):
883
cdef _KnownGraphNode last_node, next_node
884
cdef _MergeSortNode ms_node, ms_last_node, ms_next_node
885
cdef long next_merge_depth
887
while self._last_stack_item >= 0:
888
# Peek at the last item on the stack
889
last_node = _get_list_node(self._depth_first_stack,
890
self._last_stack_item)
891
if last_node.gdfo == -1:
892
# if _find_gdfo skipped a node, that means there is a graph
893
# cycle, error out now
894
raise errors.GraphCycleError(self.graph._nodes)
895
ms_last_node = <_MergeSortNode>last_node.extra
896
if not ms_last_node.has_pending_parents():
897
# Processed all parents, pop this node
900
while ms_last_node.has_pending_parents():
901
if ms_last_node.left_pending_parent is not None:
902
# recurse depth first into the primary parent
903
next_node = ms_last_node.left_pending_parent
904
ms_last_node.left_pending_parent = None
906
# place any merges in right-to-left order for scheduling
907
# which gives us left-to-right order after we reverse
908
# the scheduled queue.
909
# Note: This has the effect of allocating common-new
910
# revisions to the right-most subtree rather than the
911
# left most, which will display nicely (you get
912
# smaller trees at the top of the combined merge).
913
next_node = ms_last_node.pending_parents.pop()
914
ms_next_node = self._get_ms_node(next_node)
915
if ms_next_node.completed:
916
# this parent was completed by a child on the
917
# call stack. skip it.
919
# otherwise transfer it from the source graph into the
920
# top of the current depth first search stack.
922
if next_node is ms_last_node.left_parent:
923
next_merge_depth = ms_last_node.merge_depth
925
next_merge_depth = ms_last_node.merge_depth + 1
926
self._push_node(next_node, next_merge_depth)
927
# and do not continue processing parents until this 'call'
931
cdef topo_order(self):
932
cdef _MergeSortNode ms_node
933
cdef _KnownGraphNode node
935
cdef PyObject *temp_key
936
cdef PyObject *temp_node
938
# Note: allocating a _MergeSortNode and deallocating it for all nodes
939
# costs approx 8.52ms (21%) of the total runtime
940
# We might consider moving the attributes into the base
942
self._schedule_stack()
944
# We've set up the basic schedule, now we can continue processing the
946
# Note: This final loop costs us 40.0ms => 28.8ms (11ms, 25%) on
947
# bzr.dev, to convert the internal Object representation into a
948
# Tuple representation...
949
# 2ms is walking the data and computing revno tuples
950
# 7ms is computing the return tuple
951
# 4ms is PyList_Append()
953
# output the result in reverse order, and separate the generated info
954
for pos from PyList_GET_SIZE(self._scheduled_nodes) > pos >= 0:
955
node = _get_list_node(self._scheduled_nodes, pos)
956
ms_node = <_MergeSortNode>node.extra
957
PyList_Append(ordered, ms_node)
959
# Clear out the scheduled nodes now that we're done
960
self._scheduled_nodes = []
added
removed
breezy/_known_graph_pyx.pyx
