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
"""Functionality for doing annotations in the 'optimal' way"""
19
cdef extern from "python-compat.h":
22
cdef extern from "Python.h":
23
ctypedef int Py_ssize_t
24
ctypedef struct PyObject:
26
ctypedef struct PyListObject:
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
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,
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)
44
PyObject *PyDict_GetItem(object d, object k)
45
int PyDict_SetItem(object d, object k, object v) except -1
47
void Py_INCREF(object)
48
void Py_INCREF_ptr "Py_INCREF" (PyObject *)
49
void Py_DECREF_ptr "Py_DECREF" (PyObject *)
53
int PyObject_RichCompareBool(object, object, int opid) except -1
54
int PyObject_RichCompareBool_ptr "PyObject_RichCompareBool" (
55
PyObject *, PyObject *, int opid)
58
from bzrlib import _annotator_py
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')
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)))
86
cdef PyObject *_next_tuple_entry(object tpl, Py_ssize_t *pos): # cannot_raise
87
"""Return the next entry from this tuple.
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.
92
This cannot raise an exception, as it does no error checking.
95
if pos[0] >= PyTuple_GET_SIZE(tpl):
97
return PyTuple_GET_ITEM(tpl, pos[0])
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
106
if (PyObject_RichCompareBool(ann_one, ann_two, Py_LT)):
107
cache_key = (ann_one, ann_two)
109
cache_key = (ann_two, ann_one)
110
temp = PyDict_GetItem(cache, cache_key)
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.
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.
130
or PyObject_RichCompareBool_ptr(left, right, Py_EQ)):
131
# Identical values, step both
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
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
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
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
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)
164
cdef int _apply_parent_annotations(annotations, parent_annotations,
165
matching_blocks) except -1:
166
"""Apply the annotations from parent_annotations into annotations.
168
matching_blocks defines the ranges that match.
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
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
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]
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
197
cdef PyObject *ann_temp, *par_temp
199
_check_annotations_are_lists(annotations, parent_annotations)
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
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
227
PyList_SetItem(annotations, ann_idx, par_ann)
229
# Resolve the fact that both sides have a different value for
231
if (ann is last_ann and par_ann is last_parent):
233
PyList_SetItem(annotations, ann_idx, last_res)
235
new_ann = _combine_annotations(ann, par_ann, ann_cache)
237
PyList_SetItem(annotations, ann_idx, new_ann)
239
last_parent = par_ann
244
class Annotator(_annotator_py.Annotator):
245
"""Class that drives performing annotations."""
247
def _update_from_first_parent(self, key, annotations, lines, parent_key):
248
"""Reannotate this text relative to its first parent."""
250
matching_blocks) = self._get_parent_annotations_and_matches(
251
key, lines, parent_key)
253
_apply_parent_annotations(annotations, parent_annotations,
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."""
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)
265
def annotate_flat(self, key):
266
"""Determine the single-best-revision to source for each line.
268
This is meant as a compatibility thunk to how annotate() used to work.
270
cdef Py_ssize_t pos, num_lines
272
from bzrlib import annotate
274
custom_tiebreaker = annotate._break_annotation_tie
275
annotations, lines = self.annotate(key)
276
num_lines = len(lines)
278
heads = self._get_heads_provider().heads
279
for pos from 0 <= pos < num_lines:
280
annotation = annotations[pos]
282
if len(annotation) == 1:
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
289
# We need to resolve the ambiguity, for now just pick the
291
head = self._resolve_annotation_tie(the_heads, line,
293
PyList_Append(out, (head, line))
added
removed
bzrlib/_annotator_pyx.pyx
