← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_annotator_pyx.pyx

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-03-28 06:58:22 UTC
  • mfrom: (2379.2.3 hpss-chroot)
  • Revision ID: pqm@pqm.ubuntu.com-20070328065822-999550a858a3ced3
(robertc) Fix chroot urls to not expose the url of the transport they are protecting, allowing regular url operations to work on them. (Robert Collins, Andrew Bennetts)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_annotator_pyx.pyx
1
 
# Copyright (C) 2009, 2010 Canonical Ltd
2
 
#
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.
7
 
#
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.
12
 
#
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
16
 
 
17
 
"""Functionality for doing annotations in the 'optimal' way"""
18
 
 
19
 
cdef extern from "python-compat.h":
20
 
    pass
21
 
 
22
 
cdef extern from "Python.h":
23
 
    ctypedef int Py_ssize_t
24
 
    ctypedef struct PyObject:
25
 
        pass
26
 
    ctypedef struct PyListObject:
27
 
        PyObject **ob_item
28
 
    int PyList_CheckExact(object)
29
 
    PyObject *PyList_GET_ITEM(object, Py_ssize_t o)
30
 
    Py_ssize_t PyList_GET_SIZE(object)
31
 
    int PyList_Append(object, object) except -1
32
 
    int PyList_SetItem(object, Py_ssize_t o, object) except -1
33
 
    int PyList_Sort(object) except -1
34
 
 
35
 
    int PyTuple_CheckExact(object)
36
 
    object PyTuple_New(Py_ssize_t len)
37
 
    void PyTuple_SET_ITEM(object, Py_ssize_t pos, object)
38
 
    void PyTuple_SET_ITEM_ptr "PyTuple_SET_ITEM" (object, Py_ssize_t,
39
 
                                                  PyObject *)
40
 
    int PyTuple_Resize(PyObject **, Py_ssize_t newlen)
41
 
    PyObject *PyTuple_GET_ITEM(object, Py_ssize_t o)
42
 
    Py_ssize_t PyTuple_GET_SIZE(object)
43
 
 
44
 
    PyObject *PyDict_GetItem(object d, object k)
45
 
    int PyDict_SetItem(object d, object k, object v) except -1
46
 
 
47
 
    void Py_INCREF(object)
48
 
    void Py_INCREF_ptr "Py_INCREF" (PyObject *)
49
 
    void Py_DECREF_ptr "Py_DECREF" (PyObject *)
50
 
 
51
 
    int Py_EQ
52
 
    int Py_LT
53
 
    int PyObject_RichCompareBool(object, object, int opid) except -1
54
 
    int PyObject_RichCompareBool_ptr "PyObject_RichCompareBool" (
55
 
        PyObject *, PyObject *, int opid)
56
 
 
57
 
 
58
 
from bzrlib import _annotator_py
59
 
 
60
 
 
61
 
cdef int _check_annotations_are_lists(annotations,
62
 
                                      parent_annotations) except -1:
63
 
    if not PyList_CheckExact(annotations):
64
 
        raise TypeError('annotations must be a list')
65
 
    if not PyList_CheckExact(parent_annotations):
66
 
        raise TypeError('parent_annotations must be a list')
67
 
    return 0
68
 
 
69
 
 
70
 
cdef int _check_match_ranges(parent_annotations, annotations,
71
 
                             Py_ssize_t parent_idx, Py_ssize_t lines_idx,
72
 
                             Py_ssize_t match_len) except -1:
73
 
    if parent_idx + match_len > PyList_GET_SIZE(parent_annotations):
74
 
        raise ValueError('Match length exceeds len of'
75
 
                         ' parent_annotations %s > %s'
76
 
                         % (parent_idx + match_len,
77
 
                            PyList_GET_SIZE(parent_annotations)))
78
 
    if lines_idx + match_len > PyList_GET_SIZE(annotations):
79
 
        raise ValueError('Match length exceeds len of'
80
 
                         ' annotations %s > %s'
81
 
                         % (lines_idx + match_len,
82
 
                            PyList_GET_SIZE(annotations)))
83
 
    return 0
84
 
 
85
 
 
86
 
cdef PyObject *_next_tuple_entry(object tpl, Py_ssize_t *pos): # cannot_raise
87
 
    """Return the next entry from this tuple.
88
 
 
89
 
    :param tpl: The tuple we are investigating, *must* be a PyTuple
90
 
    :param pos: The last item we found. Will be updated to the new position.
91
 
    
92
 
    This cannot raise an exception, as it does no error checking.
93
 
    """
94
 
    pos[0] = pos[0] + 1
95
 
    if pos[0] >= PyTuple_GET_SIZE(tpl):
96
 
        return NULL
97
 
    return PyTuple_GET_ITEM(tpl, pos[0])
98
 
 
99
 
 
100
 
cdef object _combine_annotations(ann_one, ann_two, cache):
101
 
    """Combine the annotations from both sides."""
102
 
    cdef Py_ssize_t pos_one, pos_two, len_one, len_two
103
 
    cdef Py_ssize_t out_pos
104
 
    cdef PyObject *temp, *left, *right
105
 
 
106
 
    if (PyObject_RichCompareBool(ann_one, ann_two, Py_LT)):
107
 
        cache_key = (ann_one, ann_two)
108
 
    else:
109
 
        cache_key = (ann_two, ann_one)
110
 
    temp = PyDict_GetItem(cache, cache_key)
111
 
    if temp != NULL:
112
 
        return <object>temp
113
 
 
114
 
    if not PyTuple_CheckExact(ann_one) or not PyTuple_CheckExact(ann_two):
115
 
        raise TypeError('annotations must be tuples')
116
 
    # We know that annotations are tuples, and that both sides are already
117
 
    # sorted, so we can just walk and update a new list.
118
 
    pos_one = -1
119
 
    pos_two = -1
120
 
    out_pos = 0
121
 
    left = _next_tuple_entry(ann_one, &pos_one)
122
 
    right = _next_tuple_entry(ann_two, &pos_two)
123
 
    new_ann = PyTuple_New(PyTuple_GET_SIZE(ann_one)
124
 
                          + PyTuple_GET_SIZE(ann_two))
125
 
    while left != NULL and right != NULL:
126
 
        # left == right is done by PyObject_RichCompareBool_ptr, however it
127
 
        # avoids a function call for a very common case. Drops 'time bzr
128
 
        # annotate NEWS' from 7.25s to 7.16s, so it *is* a visible impact.
129
 
        if (left == right
130
 
            or PyObject_RichCompareBool_ptr(left, right, Py_EQ)):
131
 
            # Identical values, step both
132
 
            Py_INCREF_ptr(left)
133
 
            PyTuple_SET_ITEM_ptr(new_ann, out_pos, left)
134
 
            left = _next_tuple_entry(ann_one, &pos_one)
135
 
            right = _next_tuple_entry(ann_two, &pos_two)
136
 
        elif (PyObject_RichCompareBool_ptr(left, right, Py_LT)):
137
 
            # left < right or right == NULL
138
 
            Py_INCREF_ptr(left)
139
 
            PyTuple_SET_ITEM_ptr(new_ann, out_pos, left)
140
 
            left = _next_tuple_entry(ann_one, &pos_one)
141
 
        else: # right < left or left == NULL
142
 
            Py_INCREF_ptr(right)
143
 
            PyTuple_SET_ITEM_ptr(new_ann, out_pos, right)
144
 
            right = _next_tuple_entry(ann_two, &pos_two)
145
 
        out_pos = out_pos + 1
146
 
    while left != NULL:
147
 
        Py_INCREF_ptr(left)
148
 
        PyTuple_SET_ITEM_ptr(new_ann, out_pos, left)
149
 
        left = _next_tuple_entry(ann_one, &pos_one)
150
 
        out_pos = out_pos + 1
151
 
    while right != NULL:
152
 
        Py_INCREF_ptr(right)
153
 
        PyTuple_SET_ITEM_ptr(new_ann, out_pos, right)
154
 
        right = _next_tuple_entry(ann_two, &pos_two)
155
 
        out_pos = out_pos + 1
156
 
    if out_pos != PyTuple_GET_SIZE(new_ann):
157
 
        # Timing _PyTuple_Resize was not significantly faster that slicing
158
 
        # PyTuple_Resize((<PyObject **>new_ann), out_pos)
159
 
        new_ann = new_ann[0:out_pos]
160
 
    PyDict_SetItem(cache, cache_key, new_ann)
161
 
    return new_ann
162
 
 
163
 
 
164
 
cdef int _apply_parent_annotations(annotations, parent_annotations,
165
 
                                   matching_blocks) except -1:
166
 
    """Apply the annotations from parent_annotations into annotations.
167
 
 
168
 
    matching_blocks defines the ranges that match.
169
 
    """
170
 
    cdef Py_ssize_t parent_idx, lines_idx, match_len, idx
171
 
    cdef PyListObject *par_list, *ann_list
172
 
    cdef PyObject **par_temp, **ann_temp
173
 
 
174
 
    _check_annotations_are_lists(annotations, parent_annotations)
175
 
    par_list = <PyListObject *>parent_annotations
176
 
    ann_list = <PyListObject *>annotations
177
 
    # For NEWS and bzrlib/builtins.py, over 99% of the lines are simply copied
178
 
    # across from the parent entry. So this routine is heavily optimized for
179
 
    # that. Would be interesting if we could use memcpy() but we have to incref
180
 
    # and decref
181
 
    for parent_idx, lines_idx, match_len in matching_blocks:
182
 
        _check_match_ranges(parent_annotations, annotations,
183
 
                            parent_idx, lines_idx, match_len)
184
 
        par_temp = par_list.ob_item + parent_idx
185
 
        ann_temp = ann_list.ob_item + lines_idx
186
 
        for idx from 0 <= idx < match_len:
187
 
            Py_INCREF_ptr(par_temp[idx])
188
 
            Py_DECREF_ptr(ann_temp[idx])
189
 
            ann_temp[idx] = par_temp[idx]
190
 
    return 0
191
 
 
192
 
 
193
 
cdef int _merge_annotations(this_annotation, annotations, parent_annotations,
194
 
                            matching_blocks, ann_cache) except -1:
195
 
    cdef Py_ssize_t parent_idx, ann_idx, lines_idx, match_len, idx
196
 
    cdef Py_ssize_t pos
197
 
    cdef PyObject *ann_temp, *par_temp
198
 
 
199
 
    _check_annotations_are_lists(annotations, parent_annotations)
200
 
    last_ann = None
201
 
    last_parent = None
202
 
    last_res = None
203
 
    for parent_idx, lines_idx, match_len in matching_blocks:
204
 
        _check_match_ranges(parent_annotations, annotations,
205
 
                            parent_idx, lines_idx, match_len)
206
 
        # For lines which match this parent, we will now resolve whether
207
 
        # this parent wins over the current annotation
208
 
        for idx from 0 <= idx < match_len:
209
 
            ann_idx = lines_idx + idx
210
 
            ann_temp = PyList_GET_ITEM(annotations, ann_idx)
211
 
            par_temp = PyList_GET_ITEM(parent_annotations, parent_idx + idx)
212
 
            if (ann_temp == par_temp):
213
 
                # This is parent, do nothing
214
 
                # Pointer comparison is fine here. Value comparison would
215
 
                # be ok, but it will be handled in the final if clause by
216
 
                # merging the two tuples into the same tuple
217
 
                # Avoiding the Py_INCREF and function call to
218
 
                # PyObject_RichCompareBool using pointer comparison drops
219
 
                # timing from 215ms => 125ms
220
 
                continue
221
 
            par_ann = <object>par_temp
222
 
            ann = <object>ann_temp
223
 
            if (ann is this_annotation):
224
 
                # Originally claimed 'this', but it was really in this
225
 
                # parent
226
 
                Py_INCREF(par_ann)
227
 
                PyList_SetItem(annotations, ann_idx, par_ann)
228
 
                continue
229
 
            # Resolve the fact that both sides have a different value for
230
 
            # last modified
231
 
            if (ann is last_ann and par_ann is last_parent):
232
 
                Py_INCREF(last_res)
233
 
                PyList_SetItem(annotations, ann_idx, last_res)
234
 
            else:
235
 
                new_ann = _combine_annotations(ann, par_ann, ann_cache)
236
 
                Py_INCREF(new_ann)
237
 
                PyList_SetItem(annotations, ann_idx, new_ann)
238
 
                last_ann = ann
239
 
                last_parent = par_ann
240
 
                last_res = new_ann
241
 
    return 0
242
 
 
243
 
 
244
 
class Annotator(_annotator_py.Annotator):
245
 
    """Class that drives performing annotations."""
246
 
 
247
 
    def _update_from_first_parent(self, key, annotations, lines, parent_key):
248
 
        """Reannotate this text relative to its first parent."""
249
 
        (parent_annotations,
250
 
         matching_blocks) = self._get_parent_annotations_and_matches(
251
 
                                key, lines, parent_key)
252
 
 
253
 
        _apply_parent_annotations(annotations, parent_annotations,
254
 
                                  matching_blocks)
255
 
 
256
 
    def _update_from_other_parents(self, key, annotations, lines,
257
 
                                   this_annotation, parent_key):
258
 
        """Reannotate this text relative to a second (or more) parent."""
259
 
        (parent_annotations,
260
 
         matching_blocks) = self._get_parent_annotations_and_matches(
261
 
                                key, lines, parent_key)
262
 
        _merge_annotations(this_annotation, annotations, parent_annotations,
263
 
                           matching_blocks, self._ann_tuple_cache)
264
 
 
265
 
    def annotate_flat(self, key):
266
 
        """Determine the single-best-revision to source for each line.
267
 
 
268
 
        This is meant as a compatibility thunk to how annotate() used to work.
269
 
        """
270
 
        cdef Py_ssize_t pos, num_lines
271
 
 
272
 
        from bzrlib import annotate
273
 
 
274
 
        custom_tiebreaker = annotate._break_annotation_tie
275
 
        annotations, lines = self.annotate(key)
276
 
        num_lines = len(lines)
277
 
        out = []
278
 
        heads = self._get_heads_provider().heads
279
 
        for pos from 0 <= pos < num_lines:
280
 
            annotation = annotations[pos]
281
 
            line = lines[pos]
282
 
            if len(annotation) == 1:
283
 
                head = annotation[0]
284
 
            else:
285
 
                the_heads = heads(annotation)
286
 
                if len(the_heads) == 1:
287
 
                    for head in the_heads: break # get the item out of the set
288
 
                else:
289
 
                    # We need to resolve the ambiguity, for now just pick the
290
 
                    # sorted smallest
291
 
                    head = self._resolve_annotation_tie(the_heads, line,
292
 
                                                        custom_tiebreaker)
293
 
            PyList_Append(out, (head, line))
294
 
        return out