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