/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-08-25 18:45:40 UTC
  • mto: (4634.6.15 2.0)
  • mto: This revision was merged to the branch mainline in revision 4667.
  • Revision ID: john@arbash-meinel.com-20090825184540-6dn3xjq62xhgj2gq
Add support for skipping ghost nodes.

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
27
27
 
28
28
    int PyString_CheckExact(object)
29
29
 
30
 
    int PyObject_RichCompareBool(object, object, int)
31
 
    int Py_LT
32
 
 
33
 
    int PyTuple_CheckExact(object)
34
30
    object PyTuple_New(Py_ssize_t n)
35
31
    Py_ssize_t PyTuple_GET_SIZE(object t)
36
32
    PyObject * PyTuple_GET_ITEM(object t, Py_ssize_t o)
37
33
    void PyTuple_SET_ITEM(object t, Py_ssize_t o, object v)
38
34
 
39
 
    int PyList_CheckExact(object)
40
35
    Py_ssize_t PyList_GET_SIZE(object l)
41
36
    PyObject * PyList_GET_ITEM(object l, Py_ssize_t o)
42
37
    int PyList_SetItem(object l, Py_ssize_t o, object l) except -1
51
46
 
52
47
    void Py_INCREF(object)
53
48
 
54
 
from collections import deque
55
49
import gc
56
50
 
57
51
from bzrlib import errors, revision
89
83
                PyList_Append(keys, child.key)
90
84
            return keys
91
85
 
92
 
    property parent_keys:
93
 
        def __get__(self):
94
 
            if self.parents is None:
95
 
                return None
96
 
            
97
 
            cdef _KnownGraphNode parent
98
 
 
99
 
            keys = []
100
 
            for parent in self.parents:
101
 
                PyList_Append(keys, parent.key)
102
 
            return keys
103
 
    
104
86
    cdef clear_references(self):
105
87
        self.parents = None
106
88
        self.children = None
128
110
    return <_KnownGraphNode>temp_node
129
111
 
130
112
 
131
 
cdef _KnownGraphNode _get_tuple_node(tpl, Py_ssize_t pos):
 
113
cdef _KnownGraphNode _get_parent(parents, Py_ssize_t pos):
132
114
    cdef PyObject *temp_node
 
115
    cdef _KnownGraphNode node
133
116
 
134
 
    temp_node = PyTuple_GET_ITEM(tpl, pos)
 
117
    temp_node = PyTuple_GET_ITEM(parents, pos)
135
118
    return <_KnownGraphNode>temp_node
136
119
 
137
120
 
138
121
def get_key(node):
139
122
    cdef _KnownGraphNode real_node
140
 
    real_node = node
 
123
    real_node = <_KnownGraphNode>node
141
124
    return real_node.key
142
125
 
143
126
 
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
 
    """
 
127
cdef object _sort_list_nodes(object lst, int reverse):
 
128
    """Sort a list of _KnownGraphNode objects."""
150
129
    cdef _KnownGraphNode node1, node2
151
 
    cdef int do_swap, is_tuple
152
 
    cdef Py_ssize_t length
 
130
    cdef int do_swap
153
131
 
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)
 
132
    if PyList_GET_SIZE(lst) == 0 or PyList_GET_SIZE(lst) == 1:
 
133
        return lst
 
134
    if PyList_GET_SIZE(lst) == 2:
 
135
        node1 = _get_list_node(lst, 0)
 
136
        node2 = _get_list_node(lst, 1)
167
137
        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
 
138
            do_swap = (node1.key < node2.key)
 
139
        else:
 
140
            do_swap = (node2.key < node1.key)
 
141
        if do_swap:
177
142
            Py_INCREF(node1)
178
 
            PyList_SetItem(lst_or_tpl, 1, node1)
 
143
            PyList_SetItem(lst, 0, node2)
179
144
            Py_INCREF(node2)
180
 
            PyList_SetItem(lst_or_tpl, 0, node2)
181
 
            return lst_or_tpl
 
145
            PyList_SetItem(lst, 1, node1)
 
146
        return lst
182
147
    # 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
 
148
    return sorted(lst, key=get_key, reverse=reverse)
188
149
 
189
150
 
190
151
cdef class _MergeSorter
193
154
    """This is a class which assumes we already know the full graph."""
194
155
 
195
156
    cdef public object _nodes
196
 
    cdef public object _known_heads
 
157
    cdef object _known_heads
197
158
    cdef public int do_cache
198
159
 
199
160
    def __init__(self, parent_map, do_cache=True):
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
 
265
204
          child keys,
266
205
        """
267
206
        cdef PyObject *temp_key, *temp_parent_keys, *temp_node
268
 
        cdef Py_ssize_t pos
 
207
        cdef Py_ssize_t pos, pos2, num_parent_keys
269
208
        cdef _KnownGraphNode node
270
209
        cdef _KnownGraphNode parent_node
271
210
 
276
215
        while PyDict_Next(parent_map, &pos, &temp_key, &temp_parent_keys):
277
216
            key = <object>temp_key
278
217
            parent_keys = <object>temp_parent_keys
 
218
            num_parent_keys = len(parent_keys)
279
219
            node = self._get_or_create_node(key)
280
 
            self._populate_parents(node, parent_keys)
 
220
            # We know how many parents, so we pre allocate the tuple
 
221
            parent_nodes = PyTuple_New(num_parent_keys)
 
222
            for pos2 from 0 <= pos2 < num_parent_keys:
 
223
                # Note: it costs us 10ms out of 40ms to lookup all of these
 
224
                #       parents, it doesn't seem to be an allocation overhead,
 
225
                #       but rather a lookup overhead. There doesn't seem to be
 
226
                #       a way around it, and that is one reason why
 
227
                #       KnownGraphNode maintains a direct pointer to the parent
 
228
                #       node.
 
229
                # We use [] because parent_keys may be a tuple or list
 
230
                parent_node = self._get_or_create_node(parent_keys[pos2])
 
231
                # PyTuple_SET_ITEM will steal a reference, so INCREF first
 
232
                Py_INCREF(parent_node)
 
233
                PyTuple_SET_ITEM(parent_nodes, pos2, parent_node)
 
234
                PyList_Append(parent_node.children, node)
 
235
            node.parents = parent_nodes
281
236
 
282
237
    def _find_tails(self):
283
238
        cdef PyObject *temp_node
341
296
                    # anymore
342
297
                    child.seen = 0
343
298
 
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
377
 
                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)
413
 
 
414
299
    def heads(self, keys):
415
300
        """Return the heads from amongst keys.
416
301
 
482
367
                continue
483
368
            if node.parents is not None and PyTuple_GET_SIZE(node.parents) > 0:
484
369
                for pos from 0 <= pos < PyTuple_GET_SIZE(node.parents):
485
 
                    parent_node = _get_tuple_node(node.parents, pos)
 
370
                    parent_node = _get_parent(node.parents, pos)
486
371
                    last_item = last_item + 1
487
372
                    if last_item < PyList_GET_SIZE(pending):
488
373
                        Py_INCREF(parent_node) # SetItem steals a ref
569
454
        aren't sure what node to access next, we sort them lexicographically.
570
455
        """
571
456
        cdef PyObject *temp
572
 
        cdef Py_ssize_t pos, last_item
 
457
        cdef Py_ssize_t pos
573
458
        cdef _KnownGraphNode node, node2, parent_node
574
459
 
575
460
        tips = self._find_tips()
581
466
                prefix = ''
582
467
            else:
583
468
                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)
 
469
            prefix_tips.setdefault(prefix, []).append(node)
590
470
 
591
471
        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
 
472
        for prefix, nodes in sorted(prefix_tips.iteritems()):
 
473
            pending = _sort_list_nodes(nodes, 1)
 
474
            while pending:
 
475
                node = pending.pop()
601
476
                if node.parents is None:
602
 
                    # Ghost
603
477
                    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)
 
478
                result.append(node.key)
 
479
                parents = _sort_list_nodes(list(node.parents), 1)
 
480
                for pos from 0 <= pos < PyList_GET_SIZE(parents):
 
481
                    parent_node = _get_list_node(parents, pos)
617
482
                    # TODO: GraphCycle detection
618
483
                    parent_node.seen = parent_node.seen + 1
619
484
                    if (parent_node.seen
620
485
                        == PyList_GET_SIZE(parent_node.children)):
621
486
                        # All children have been processed, queue up this
622
487
                        # 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)
 
488
                        pending.append(parent_node)
629
489
                        parent_node.seen = 0
630
490
        return result
631
491
 
638
498
        #       shown a specific impact, yet.
639
499
        sorter = _MergeSorter(self, tip_key)
640
500
        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
501
 
665
502
 
666
503
cdef class _MergeSortNode:
697
534
        self.completed = 0
698
535
 
699
536
    def __repr__(self):
700
 
        return '%s(%s depth:%s rev:%s,%s,%s first:%s seen:%s)' % (
701
 
            self.__class__.__name__, self.key,
 
537
        return '%s(depth:%s rev:%s,%s,%s first:%s seen:%s)' % (self.__class__.__name__,
702
538
            self.merge_depth,
703
539
            self._revno_first, self._revno_second, self._revno_last,
704
540
            self.is_first_child, self.seen_by_child)
705
541
 
706
 
    cdef int has_pending_parents(self): # cannot_raise
 
542
    cdef int has_pending_parents(self):
707
543
        if self.left_pending_parent is not None or self.pending_parents:
708
544
            return 1
709
545
        return 0
752
588
        if (tip_key is not None and tip_key != NULL_REVISION
753
589
            and tip_key != (NULL_REVISION,)):
754
590
            node = self.graph._nodes[tip_key]
 
591
            self._get_ms_node(node)
755
592
            self._push_node(node, 0)
756
593
 
757
594
    cdef _MergeSortNode _get_ms_node(self, _KnownGraphNode node):
772
609
 
773
610
        ms_node = self._get_ms_node(node)
774
611
        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
612
        if PyTuple_GET_SIZE(node.parents) > 0:
779
 
            parent_node = _get_tuple_node(node.parents, 0)
 
613
            parent_node = _get_parent(node.parents, 0)
780
614
            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
 
615
            ms_node.left_pending_parent = parent_node
786
616
        if PyTuple_GET_SIZE(node.parents) > 1:
787
617
            ms_node.pending_parents = []
788
618
            for pos from 1 <= pos < PyTuple_GET_SIZE(node.parents):
789
 
                parent_node = _get_tuple_node(node.parents, pos)
 
619
                parent_node = _get_parent(node.parents, pos)
790
620
                if parent_node.parents is None: # ghost
791
621
                    continue
792
622
                PyList_Append(ms_node.pending_parents, parent_node)