« back to all changes in this revision
Viewing changes to bzrlib/annotate.py
- browse files at revision 3280
- compare with another revision
- compare with revision 3185.1.10
- download diff
- download tarball
- view history from revision 3280
- Committer: Canonical.com Patch Queue Manager
- Date: 2008-03-15 17:44:41 UTC
- mfrom: (3224.1.29 annotate_finish)
- Revision ID: pqm@pqm.ubuntu.com-20080315174441-l8xpw6femn0syal1
(jam) Tweak annotate performance for pack repositories,
improving speed and decreasing memory consumption.
improving speed and decreasing memory consumption.
added
removed
bzrlib/annotate.py
156
156
157
157
158
158
def reannotate(parents_lines, new_lines, new_revision_id,
159
_left_matching_blocks=None):
159
_left_matching_blocks=None,
160
heads_provider=None):
160
161
"""Create a new annotated version from new lines and parent annotations.
161
162
162
163
:param parents_lines: List of annotated lines for all parents
165
166
(will often be CURRENT_REVISION)
166
167
:param left_matching_blocks: a hint about which areas are common
167
168
between the text and its left-hand-parent. The format is
168
the SequenceMatcher.get_matching_blocks format.
169
the SequenceMatcher.get_matching_blocks format
170
(start_left, start_right, length_of_match).
171
:param heads_provider: An object which provids a .heads() call to resolve
172
if any revision ids are children of others.
173
If None, then any ancestry disputes will be resolved with
174
new_revision_id
169
175
"""
170
176
if len(parents_lines) == 0:
171
177
lines = [(new_revision_id, line) for line in new_lines]
175
181
elif len(parents_lines) == 2:
176
182
left = _reannotate(parents_lines[0], new_lines, new_revision_id,
177
183
_left_matching_blocks)
178
right = _reannotate(parents_lines[1], new_lines, new_revision_id)
179
lines = []
180
for idx in xrange(len(new_lines)):
181
if left[idx][0] == right[idx][0]:
182
# The annotations match, just return the left one
183
lines.append(left[idx])
184
elif left[idx][0] == new_revision_id:
185
# The left parent claims a new value, return the right one
186
lines.append(right[idx])
187
elif right[idx][0] == new_revision_id:
188
# The right parent claims a new value, return the left one
189
lines.append(left[idx])
190
else:
191
# Both claim different origins
192
lines.append((new_revision_id, left[idx][1]))
184
lines = _reannotate_annotated(parents_lines[1], new_lines,
185
new_revision_id, left,
186
heads_provider)
193
187
else:
194
188
reannotations = [_reannotate(parents_lines[0], new_lines,
195
189
new_revision_id, _left_matching_blocks)]
227
221
lines.extend(parent_lines[i:i+n])
228
222
new_cur = j + n
229
223
return lines
224
225
226
def _get_matching_blocks(old, new):
227
matcher = patiencediff.PatienceSequenceMatcher(None,
228
old, new)
229
return matcher.get_matching_blocks()
230
231
232
def _find_matching_unannotated_lines(output_lines, plain_child_lines,
233
child_lines, start_child, end_child,
234
right_lines, start_right, end_right,
235
heads_provider, revision_id):
236
"""Find lines in plain_right_lines that match the existing lines.
237
238
:param output_lines: Append final annotated lines to this list
239
:param plain_child_lines: The unannotated new lines for the child text
240
:param child_lines: Lines for the child text which have been annotated
241
for the left parent
242
:param start_child: Position in plain_child_lines and child_lines to start the
243
match searching
244
:param end_child: Last position in plain_child_lines and child_lines to search
245
for a match
246
:param right_lines: The annotated lines for the whole text for the right
247
parent
248
:param start_right: Position in right_lines to start the match
249
:param end_right: Last position in right_lines to search for a match
250
:param heads_provider: When parents disagree on the lineage of a line, we
251
need to check if one side supersedes the other
252
:param revision_id: The label to give if a line should be labeled 'tip'
253
"""
254
output_extend = output_lines.extend
255
output_append = output_lines.append
256
# We need to see if any of the unannotated lines match
257
plain_right_subset = [l for a,l in right_lines[start_right:end_right]]
258
plain_child_subset = plain_child_lines[start_child:end_child]
259
match_blocks = _get_matching_blocks(plain_right_subset, plain_child_subset)
260
261
last_child_idx = 0
262
263
for right_idx, child_idx, match_len in match_blocks:
264
# All the lines that don't match are just passed along
265
if child_idx > last_child_idx:
266
output_extend(child_lines[start_child + last_child_idx
267
:start_child + child_idx])
268
for offset in xrange(match_len):
269
left = child_lines[start_child+child_idx+offset]
270
right = right_lines[start_right+right_idx+offset]
271
if left[0] == right[0]:
272
# The annotations match, just return the left one
273
output_append(left)
274
elif left[0] == revision_id:
275
# The left parent marked this as unmatched, so let the
276
# right parent claim it
277
output_append(right)
278
else:
279
# Left and Right both claim this line
280
if heads_provider is None:
281
output_append((revision_id, left[1]))
282
else:
283
heads = heads_provider.heads((left[0], right[0]))
284
if len(heads) == 1:
285
output_append((iter(heads).next(), left[1]))
286
else:
287
# Both claim different origins
288
output_append((revision_id, left[1]))
289
# We know that revision_id is the head for
290
# left and right, so cache it
291
heads_provider.cache(
292
(revision_id, left[0]),
293
(revision_id,))
294
heads_provider.cache(
295
(revision_id, right[0]),
296
(revision_id,))
297
last_child_idx = child_idx + match_len
298
299
300
def _reannotate_annotated(right_parent_lines, new_lines, new_revision_id,
301
annotated_lines, heads_provider):
302
"""Update the annotations for a node based on another parent.
303
304
:param right_parent_lines: A list of annotated lines for the right-hand
305
parent.
306
:param new_lines: The unannotated new lines.
307
:param new_revision_id: The revision_id to attribute to lines which are not
308
present in either parent.
309
:param annotated_lines: A list of annotated lines. This should be the
310
annotation of new_lines based on parents seen so far.
311
:param heads_provider: When parents disagree on the lineage of a line, we
312
need to check if one side supersedes the other.
313
"""
314
assert len(new_lines) == len(annotated_lines)
315
# First compare the newly annotated lines with the right annotated lines.
316
# Lines which were not changed in left or right should match. This tends to
317
# be the bulk of the lines, and they will need no further processing.
318
lines = []
319
lines_extend = lines.extend
320
last_right_idx = 0 # The line just after the last match from the right side
321
last_left_idx = 0
322
matching_left_and_right = _get_matching_blocks(right_parent_lines,
323
annotated_lines)
324
for right_idx, left_idx, match_len in matching_left_and_right:
325
# annotated lines from last_left_idx to left_idx did not match the lines from
326
# last_right_idx
327
# to right_idx, the raw lines should be compared to determine what annotations
328
# need to be updated
329
if last_right_idx == right_idx or last_left_idx == left_idx:
330
# One of the sides is empty, so this is a pure insertion
331
lines_extend(annotated_lines[last_left_idx:left_idx])
332
else:
333
# We need to see if any of the unannotated lines match
334
_find_matching_unannotated_lines(lines,
335
new_lines, annotated_lines,
336
last_left_idx, left_idx,
337
right_parent_lines,
338
last_right_idx, right_idx,
339
heads_provider,
340
new_revision_id)
341
last_right_idx = right_idx + match_len
342
last_left_idx = left_idx + match_len
343
# If left and right agree on a range, just push that into the output
344
assert len(lines) == left_idx
345
lines_extend(annotated_lines[left_idx:left_idx + match_len])
346
return lines
Loggerhead is a web-based interface for Breezy
Version: 2.0.1